机器学习之k-NN算法实战——约会网站配对效果判定

前言

问题及解决思路来源：https://cuijiahua.com/blog/2017/11/ml_1_knn.html

经过优化，相较于原代码，此版本代码运行效率约提升十倍。

问题描述

海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选，但她并不是喜欢每一个人。经过总结，她发现可以对自己交往过的人进行如下分类：

  1. 没感觉（didntLike）
  2. 感觉还行（smallDoses）
  3. 非常喜欢（largeDoses）

海伦收集约会数据已经有一段时间，她把这些数据存放在文件 datingTestSet.csv 中，每个样本数据占据一行，共1000行。datingTestSet.csv 数据下载： 数据集下载

海伦收集的样本数据主要包含以下3种特征：

  1. 每年的航班飞行里程数（miles_FL_per_yr）
  2. 玩游戏所消耗时间占总时间的百分比（pc_of_gaming）
  3. 每周所消费冰淇淋公升数（litres_of_IC_con_per_wk）

要求：根据这3种主要特征，判断海伦女士对该约会对象的交往态度。

将文件前 90% 的内容用作训练集，剩余内容用作测试验证集。

解题逻辑

  1. 数据解析

    将主要特征与海伦对每个人的感觉相分离，分别存储在两种对象中。

    • 创建二维数组，内层表格中的内容为上述3种主要特征，即文件内容前3列。
    • 创建表格，用于存储海伦对每个人的交往态度，其中 didntLike 用 1 代表，smallDoses 用 2 代表，largeDoses 用 3 代表。

  2. 数据归一化

    减小过大的数目为计算结果带来的误差。

  3. k-NN预测算法

    • 将测试集二维数组中每个表格的内容，看作一个三维坐标点，计算该点与训练集中其他点的距离。并按照距离远近排序，提取 k 个距离最近的点。在这些点中出现次数最多的海伦的态度（Attitude），即为预测结果。
    • 遍历二维数组，批量进行预测。

  4. 验证机制

    将预测结果与文件中海伦真实态度相对比，计算正确率。

分步实现

数据处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import pandas as pd
import numpy as np
import matplotlib
from matplotlib import pyplot as plt
from matplotlib import lines as mlines
import operator
import time


# 取消 PyCharm 对 DataFrame 的显示限制
pd.set_option('display.max_columns', None)
pd.set_option('display.max_rows', None)


# 解析数据，并进行分类
def file_matrix(filepath):
    # 读取文件
    dt = pd.read_csv(filepath)
    # 引入0矩阵，行数为原文件的行数，3列
    date_mat = np.zeros((dt.shape[0], 3))
    # 分类标签向量
    class_label_vec = []
    # 列名。也可通过 list(dt.columns.values) 来实现 >>> numpy.ndarray --> list
    col_val = list(dt)
    # 取前3列填充进0矩阵，即特征矩阵
    for i in col_val[:3]:
        ind = col_val.index(i)
        date_mat[:, ind] = dt[i]
    # 根据交往态度进行分类，1代表没感觉，2代表感觉还行，3代表非常喜欢
    for row in dt.itertuples():
        att = getattr(row, 'Attitude')
        if att == "didntLike":
            class_label_vec.append(1)
        elif att == "smallDoses":
            class_label_vec.append(2)
        elif att == "largeDoses":
            class_label_vec.append(3)
    return date_mat, class_label_vec

数据可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 数据可视化
def visualize(date_mat, class_label_vec):
    # 设置字体样式
    font = {"family" : "MicroSoft YaHei",
            "weight" : 6,
            "size" : 6}
    matplotlib.rc("font", **font)
    # 设置子图板式
    fig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8), dpi=300)
    colors_lab = []
    for i in class_label_vec:
        if i == 1:
            colors_lab.append("black")
        elif i == 2:
            colors_lab.append("orange")
        elif i == 3:
            colors_lab.append("red")
    # 图一，以矩阵的第一(飞行里程)、第二(游戏)列数据画散点数据，散点大小为15，透明度为0.5
    axs[0][0].scatter(x=date_mat[:, 0], y=date_mat[:, 1], color=colors_lab, s=15, alpha=.5)
    axs0_title = axs[0][0].set_title("每年获得的飞行常客里程数与玩视频游戏所消耗时间占比")
    axs0_xlabel = axs[0][0].set_xlabel("每年获得的飞行常客里程数")
    axs0_ylabel = axs[0][0].set_ylabel("玩视频游戏所消耗时间占")
    plt.setp(axs0_title, size=8, weight="bold", color="black")
    plt.setp(axs0_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs0_ylabel, size=7, weight="bold", color="black")
    # 图二，以矩阵的第一(飞行里程)、第三(冰激凌)列数据画散点数据
    axs[0][1].scatter(x=date_mat[:, 0], y=date_mat[:, 2], color=colors_lab, s=15, alpha=.5)
    axs1_title = axs[0][1].set_title("每年获得的飞行常客里程数与每周消费的冰激凌公升数")
    axs1_xlabel = axs[0][1].set_xlabel("每年获得的飞行常客里程数")
    axs1_ylabel = axs[0][1].set_ylabel("每周消费的冰激凌公升数")
    plt.setp(axs1_title, size=8, weight="bold", color="black")
    plt.setp(axs1_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs1_ylabel, size=7, weight="bold", color="black")
    # 图三，以矩阵的第二(游戏)、第三(冰激凌)列数据画散点数据
    axs[1][0].scatter(x=date_mat[:, 1], y=date_mat[:, 2], color=colors_lab, s=15, alpha=.5)
    axs2_title = axs[1][0].set_title("每年获得的飞行常客里程数与每周消费的冰激凌公升数")
    axs2_xlabel = axs[1][0].set_xlabel("每年获得的飞行常客里程数")
    axs2_ylabel = axs[1][0].set_ylabel("每周消费的冰激凌公升数")
    plt.setp(axs2_title, size=8, weight="bold", color="black")
    plt.setp(axs2_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs2_ylabel, size=7, weight="bold", color="black")
    # 设置图例样式
    didntLike = mlines.Line2D([], [], color='black', marker='.', markersize=6, label='didntLike')
    smallDoses = mlines.Line2D([], [], color='orange', marker='.', markersize=6, label='smallDoses')
    largeDoses = mlines.Line2D([], [], color='red', marker='.', markersize=6, label='largeDoses')
    # 添加图例
    axs[0][0].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[0][1].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[1][0].legend(handles=[didntLike, smallDoses, largeDoses])
    plt.show()

可视化结果如下图所示：

由于我这里用的是 PyCharm 的 SciView 工具窗口，再衬以背景图，代码中设置的透明感就可以很好地表现出来。

数据归一化

显而易见的，飞行里程数远大于其他特征值，这将给计算结果带来巨大的误差。因此，我们需要通过进行数值归一化来减小这种误差。我将采用 newValue = (oldValue - min) / (max - min) 的公式进行数据归一化：

1
2
3
4
5
6
7
8
9
10
11
12

# 数值归一化
def auto_norm(date_mat):
    min_vals = date_mat.min(0)
    max_vals = date_mat.max(0)
    ranges = max_vals - min_vals
    norm_data = np.zeros(np.shape(date_mat))
    l = date_mat.shape[0]
    norm_data = date_mat - np.tile(min_vals, (l, 1))
    norm_data = norm_data / np.tile(ranges, (l, 1))
    return norm_data

分类器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 分类器——k-NN算法
def classify(inX, dataset, labels, k):
    """
    :param inX: 用于测试的数据(测试集)
    :param dataset: 用于训练的数据(训练集)
    :param labels: 分类标签
    :param k: 距离最小的k个点
    :return: 预测结果
    """
    dataset_size = dataset.shape[0]
    diff_mat = np.tile(inX, (dataset_size, 1)) - dataset
    sq_diff_mat = diff_mat ** 2
    # 按行将所有元素相加
    sq_distances = sq_diff_mat.sum(1)
    # 计算距离
    distances = sq_distances ** 0.5
    # 返回 distances 中元素从小到大排序后的索引值
    sorted_distances = distances.argsort()
    # 计数字典
    class_count = {}
    for i in range(k):
        # 取出前k个元素的类别
        votelabel = labels[sorted_distances[i]]
        # 计算类别次数。
        class_count[votelabel] = class_count.get(votelabel, 0) + 1
    # 根据字典的值对字典进行降序排序
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    # 次数最多的类别
    return sorted_class_count[0][0]

验证器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 验证器
def test(filepath):
    date_mat, class_label_vec = file_matrix(filepath)
    # 取所有数据的百分之十
    ratio = 0.10
    # 数据归一化
    norm_mat = auto_norm(date_mat)
    # 获取norm_mat行数
    m = norm_mat.shape[0]
    # 获取百分之十的测试数据的个数
    num_test_vecs = int(m * ratio)
    # 分类错误计数
    error_count = 0.0
    for i in range(num_test_vecs):
        # 前 num_test_vecs 个数据作为测试集,后 m-num_test_vecs 个数据作为训练集，取 k 为7
        classifier_result = classify(
            norm_mat[i, :],
            norm_mat[num_test_vecs:, :],
            class_label_vec[num_test_vecs:],
            7
        )
        # 输出预测结果与真实类别，并进行比较
        print("分类结果:%d\t真实类别:%d" % (classifier_result, class_label_vec[i]))
        if classifier_result != class_label_vec[i]:
            error_count += 1.0
    # 输出正确率
    print("正确率:%f%%" % ((1.00 - error_count / float(num_test_vecs)) * 100))
    # visualize(date_mat, class_label_vec)


if __name__ == '__main__':
    filepath = r"C:\Users\ASUS\Desktop\datingKNN\datingTestSet.csv"
    test(filepath)
    print("\n")
    print("程序运行时间为：", time.process_time(), "秒")

运行结果

程序运行结果如下图所示。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

import pandas as pd
import numpy as np
import matplotlib
from matplotlib import pyplot as plt
from matplotlib import lines as mlines
import operator
import time

start = time.time()

# 取消 PyCharm 对 DataFrame 的显示限制
pd.set_option('display.max_columns', None)
pd.set_option('display.max_rows', None)


# 解析数据，并进行分类
def file_matrix(filepath):
    dt = pd.read_csv(filepath)
    date_mat = np.zeros((dt.shape[0], 3))
    # 分类标签向量
    class_label_vec = []
    col_val = list(dt)
    for i in col_val[:3]:
        ind = col_val.index(i)
        date_mat[:, ind] = dt[i]
    for row in dt.itertuples():
        att = getattr(row, 'Attitude')
        if att == "didntLike":
            class_label_vec.append(1)
        elif att == "smallDoses":
            class_label_vec.append(2)
        elif att == "largeDoses":
            class_label_vec.append(3)
    return date_mat, class_label_vec


# 数据可视化
def visualize(date_mat, class_label_vec):
    # 字体样式
    font = {"family" : "MicroSoft YaHei",
            "weight" : 6,
            "size" : 6}
    matplotlib.rc("font", **font)
    # 子图板式
    fig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8), dpi=300)
    colors_lab = []
    for i in class_label_vec:
        if i == 1:
            colors_lab.append("black")
        elif i == 2:
            colors_lab.append("orange")
        elif i == 3:
            colors_lab.append("red")
    # 图一，以矩阵的第一(飞行里程)、第二(游戏)列数据画散点数据
    axs[0][0].scatter(x=date_mat[:, 0], y=date_mat[:, 1], color=colors_lab, s=15, alpha=.5)
    axs0_title = axs[0][0].set_title("每年获得的飞行常客里程数与玩视频游戏所消耗时间占比")
    axs0_xlabel = axs[0][0].set_xlabel("每年获得的飞行常客里程数")
    axs0_ylabel = axs[0][0].set_ylabel("玩视频游戏所消耗时间占")
    plt.setp(axs0_title, size=8, weight="bold", color="black")
    plt.setp(axs0_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs0_ylabel, size=7, weight="bold", color="black")
    # 图二，以矩阵的第一(飞行里程)、第三(冰激凌)列数据画散点数据
    axs[0][1].scatter(x=date_mat[:, 0], y=date_mat[:, 2], color=colors_lab, s=15, alpha=.5)
    axs1_title = axs[0][1].set_title("每年获得的飞行常客里程数与每周消费的冰激凌公升数")
    axs1_xlabel = axs[0][1].set_xlabel("每年获得的飞行常客里程数")
    axs1_ylabel = axs[0][1].set_ylabel("每周消费的冰激凌公升数")
    plt.setp(axs1_title, size=8, weight="bold", color="black")
    plt.setp(axs1_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs1_ylabel, size=7, weight="bold", color="black")
    # 图三，以矩阵的第二(游戏)、第三(冰激凌)列数据画散点数据
    axs[1][0].scatter(x=date_mat[:, 1], y=date_mat[:, 2], color=colors_lab, s=15, alpha=.5)
    axs2_title = axs[1][0].set_title("每年获得的飞行常客里程数与每周消费的冰激凌公升数")
    axs2_xlabel = axs[1][0].set_xlabel("每年获得的飞行常客里程数")
    axs2_ylabel = axs[1][0].set_ylabel("每周消费的冰激凌公升数")
    plt.setp(axs2_title, size=8, weight="bold", color="black")
    plt.setp(axs2_xlabel, size=7, weight="bold", color="black")
    plt.setp(axs2_ylabel, size=7, weight="bold", color="black")
    # 设置图例样式
    didntLike = mlines.Line2D([], [], color='black', marker='.', markersize=6, label='didntLike')
    smallDoses = mlines.Line2D([], [], color='orange', marker='.', markersize=6, label='smallDoses')
    largeDoses = mlines.Line2D([], [], color='red', marker='.', markersize=6, label='largeDoses')
    # 添加图例
    axs[0][0].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[0][1].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[1][0].legend(handles=[didntLike, smallDoses, largeDoses])
    plt.show()


# 数值归一化
def auto_norm(date_mat):
    min_vals = date_mat.min(0)
    max_vals = date_mat.max(0)
    ranges = max_vals - min_vals
    norm_data = np.zeros(np.shape(date_mat))
    l = date_mat.shape[0]
    norm_data = date_mat - np.tile(min_vals, (l, 1))
    norm_data = norm_data / np.tile(ranges, (l, 1))
    return norm_data


# 分类器——k-NN算法
def classify(inX, dataset, labels, k):
    # 计算距离
    dataset_size = dataset.shape[0]
    diff_mat = np.tile(inX, (dataset_size, 1)) - dataset
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(1)
    distances = sq_distances ** 0.5
    sorted_distances = distances.argsort()
    # 计数字典
    class_count = {}
    for i in range(k):
        votelabel = labels[sorted_distances[i]]
        class_count[votelabel] = class_count.get(votelabel, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    # 次数最多的类别
    return sorted_class_count[0][0]


# 验证器
def test(filepath):
    date_mat, class_label_vec = file_matrix(filepath)
    ratio = 0.10
    norm_mat = auto_norm(date_mat)
    m = norm_mat.shape[0]
    num_test_vecs = int(m * ratio)
    # 分类错误计数
    error_count = 0.0
    for i in range(num_test_vecs):
        # 前 num_test_vecs 个数据作为测试集,后 m-num_test_vecs 个数据作为训练集，取 k 为7
        classifier_result = classify(
            norm_mat[i, :],
            norm_mat[num_test_vecs:, :],
            class_label_vec[num_test_vecs:],
            7
        )
        print("分类结果:%d\t真实类别:%d" % (classifier_result, class_label_vec[i]))
        if classifier_result != class_label_vec[i]:
            error_count += 1.0
    # 输出正确率
    print("正确率:%f%%" % ((1.00 - error_count / float(num_test_vecs)) * 100))
    # visualize(date_mat, class_label_vec)


if __name__ == '__main__':
    filepath = r"C:\Users\ASUS\Desktop\datingKNN\datingTestSet.csv"
    test(filepath)
    print("\n")
    
    end = time.time()
    print("程序运行时间为：", end-start, "秒")