机器学习（一）：k-近邻算法（kNN）

矫情吗；* 2022-05-24 07:55 256阅读 0赞

文中的代码和数据集下载地址：  
[https://github.com/TimePickerWang/MachineLearningInAction][https_github.com_TimePickerWang_MachineLearningInAction]

k-近邻算法是一个比较简单的算法，它的基本思路是这样的：存在一个样本数据集（即训练集），样本集中的每个样本都存在标签（目标变量），即我们知道样本集中每一数据与所属分类的对应关系。在输入没有标签的新数据后，将新数据和样本集中的每个样本进行比较，然后用算法提取样本集中和待分类样本最相似的前k个样本，然后选择k个最相似样本中出现次数最多的类别，作为待分类样本的类别。

那么，怎么判断两个样本的相似程度呢？这里使用[欧式距离][Link 1]来进行判断，判断方式如下：  
设有两个n维向量：  
a=\[a1,a2,......,an\]  a = \[ a 1 , a 2 , . . . . . . , a n \]   
b=\[b1,b2,......,bn\]  b = \[ b 1 , b 2 , . . . . . . , b n \]   
那么，它们的欧式距离如下：  
da,b=(a1−b1)2\+(a2−b2)2\+......\+(an−bn)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√  d a , b = ( a 1 − b 1 ) 2 + ( a 2 − b 2 ) 2 + . . . . . . + ( a n − b n ) 2   
da,b  d a , b 的值越小，代表 a,b  a , b  的距离越近，它们越相似。

kNN算法的描述如下：

对待分类数据集中的每个样本依次执行以下操作：
      1.计算训练集中每个样本和待分类数据的欧式距离；
      2.按照距离递增次序排序；
      3.选取与当前距离最小的k个样本；
      4.确定3中k个样本所属类别的出现频率，并把出现频率最高的类别作为当前待分类数据的类别

以上步骤的python代码如下：

''' Input: inX: 待分类的向量 (1xN) dataSet: m个已完成分类的向量 (MxN) labels: m个已完成分类向量的类别标签 (Mx1) k: 需要比较的最近邻数目 Output:待分类向量最合适的类别 '''
    def classify(inX, data_set, labels, k):
        data_size = data_set.shape[0]  # 训练集样本个数
        # 以下3行计算欧式距离
        diff_mat = np.tile(inX, (data_size, 1)) - data_set
        # axis=1表示将矩阵的每行元素相加
        sq_distances = np.power(diff_mat, 2).sum(axis=1)
        distances = np.sqrt(sq_distances)
    
        sorted_distances = distances.argsort()
        class_count = {}
        for i in range(k):
            vote_label = labels[sorted_distances[i]]
            class_count[vote_label] = class_count.get(vote_label, 0) + 1
        # 按k个样本类别的出现频率倒序排序
        sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True)
        return sorted_class_count[0][0]

以上代码是kNN算法的核心部分。但在实际应用中，在计算两个样本之间的距离时，我们还需要注意到它们每个特征的”尺度”，举个例子如下：  
a=\[10,15000,300\]  a = \[ 10 , 15000 , 300 \]   
b=\[20,18000,150\]  b = \[ 20 , 18000 , 150 \]   
它们的欧式距离计算如下：  
da,b=(10−20)2\+(15000−18000)2\+(300−150)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√  d a , b = ( 10 − 20 ) 2 + ( 15000 − 18000 ) 2 + ( 300 − 150 ) 2   
可以看出，它们第2维的数据会对结果产生较大的影响，从而使得第1维，第3维对结果的影响变小。但我们希望这3个特征是同等重要的，因此我们需要对结果进行**归一化**，这里归一化的方式如下(max,min  m a x , m i n 代表数据某一维的最大、最小值)：  
newValue=(oldValue−min)/(max−min)  n e w V a l u e = ( o l d V a l u e − m i n ) / ( m a x − m i n )

归一化的代码如下：

''' Input: dataSet: 需要进行归一化的数据 Output:归一化后的结果 '''
    def normalization(data_set):
        min_value = data_set.min(0)  # 行向量，值为每一列中的最小值
        max_value = data_set.max(0)
        ranges = max_value - min_value
        m = data_set.shape[0]
        norm_mat = data_set - np.tile(min_value, (m, 1))
        norm_mat = norm_mat/np.tile(ranges, (m, 1))
        return norm_mat

kNN算法的准备工作就是这么多了，下面开始进行实例部分：

## 实例：约会网站的配对 ##

数据集里的部分数据如下图：

![这里写图片描述][70]

每列特征的含义分别表示为：每年获得的飞行常客里程数，玩视频游戏所耗时间，每周消费的冰淇淋公升数，魅力值（即所属类别）。接下来我们把数据显示出来，看一下它们的关系。代码如下：

# 读数据，输入文件路径，返回数据集的特征矩阵和标签向量
    def file_to_matrix(filename):
        # 这里跟书上不同，使用pandas自带的方法用读文件，以sep的值为分隔符，默认为逗号
        data = pd.read_csv(filename, sep='\t', header=None, names=['fly_miles', 'games', 'ice_cream', 'feeling'])
        data_mat = data.iloc[:, 0:3]
        class_label_veaotr = data.iloc[:, 3]
        # DataFrame.as_matrix(columns=None)将DataFrame转为numpy的ndarray
        data_mat = data_mat.as_matrix()
        class_label_veaotr = class_label_veaotr.as_matrix()
        return data_mat, class_label_veaotr
    
    
    # 显示数据，输入训练集的特征矩阵和标签向量
    def show_pic(data_mat, date_label):
        fig = plt.figure(figsize=(12, 10))
    
        # gemes and ice_cream
        ax = fig.add_subplot(221)
        ax.scatter(data_mat[:, 1].getA1(), data_mat[:, 2].getA1(), 10*np.array(date_label),
                    10*np.array(date_label), alpha=0.5)
        ax.set_title('gemes and ice cream')
        ax.legend()
    
        # fly_miles and games
        ax = fig.add_subplot(222)
        ax.scatter(data_mat[:, 0].getA1(), data_mat[:, 1].getA1(), 10 * np.array(date_label),
                    10 * np.array(date_label), alpha=0.5)
        ax.set_title('fly miles and games')
        ax.legend()
    
        # fly_miles and ice_cream
        ax = fig.add_subplot(223)
        ax.scatter(data_mat[:, 0].getA1(), data_mat[:, 2].getA1(), 10 * np.array(date_label),
                    10 * np.array(date_label), alpha=0.5)
        ax.set_title('fly miles and ice cream')
        ax.legend()
        # plt.savefig("../pic/knn_appointment.jpg")
        plt.show()

用以下代码来显示数据

data_mat, date_label = file_to_matrix("./Data/datingTestSet.txt")  # 读数据
    show_pic(data_mat, date_label)  # 显示数据

数据关系的显示效果如下：  
![这里写图片描述][70 1]

从第二张图上我们可以看出3个不同的样本分类区域，接下来测试算法，添加如下代码：

# 输入分别为特征矩阵、标签向量、k的值。输出为错误率
    def dating_class_test(data, label, k):
        ho_ratio = 0.15  # 取数据集的15%为测试集
        wrong_num = 0
        m = data.shape[0]
        test_data_num = int(m * ho_ratio)
        data_mat = data[test_data_num:m, :]  # 训练集
        label_mat = label[test_data_num:m]
        for i in range(test_data_num):
            test_result = knn.classify(data[i, :], data_mat, label_mat, k)
            real_result = label[i]
            if test_result != real_result:
                wrong_num += 1
                print("wrong result:" + str(test_result) + ",real_result: " + str(real_result))
        error_rate = float(wrong_num/test_data_num)
        return error_rate

用以下代码来进行测试：

norm_mat = knn.normalization(data_mat)  # 归一化
    print("error rate:" + str(dating_class_test(norm_mat, date_label, 5)))  # 测试算法5为k的值

上述代码中，我选择了原始数据集的85%作为训练集，15%作为测试集，k的值取5，然后打印出分类错误的信息和最后的错误率。打印结果如下图：  
![这里写图片描述][70 2]  
最后的错误率为5.333%，可以说是很好的结果了。最后我们可以看一下不同的k值对应的错误率分别是多少，添加代码如下：

# 绘制k的值从3到k的错误率图像，输入分别为特征矩阵、标签向量、最大的k值
    def error_rate_line(data_set, label_vect, max_k):
        k_list = np.array(range(3, max_k + 1))
        error_rate_list = []
        for k in k_list:
            error_rate_list.append(dating_class_test(data_set, label_vect, k))
        plt.plot(k_list, error_rate_list, alpha=0.5)
        plt.title("error rate with different k value")
        plt.show()

通过以下代码来显示不同k值对应的错误率：

error_rate_line(norm_mat, date_label, 15)  # 绘制k的值从3到15的错误率图像

以上代码绘制的是k从3到15的错误率，最后的结果如下：  
![这里写图片描述][70 3]  
可以看出k的值为5、6、7时错误率最小。

书上还有一个例子是识别手写数字的，其原理都差不多，这里不再啰嗦。我只把书上没有的拿出来，就是不同的k值对应的错误率，其图像如下：

![这里写图片描述][70 4]

可以看出当k取3是可以得到最小的错误率。

kNN算法是最简单的算法，但是计算时必须保存全部的数据集，时间复杂度和空间复杂度都很高是kNN最致命的缺点。

[https_github.com_TimePickerWang_MachineLearningInAction]: https://github.com/TimePickerWang/MachineLearningInAction
[Link 1]: https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E5%BA%A6%E9%87%8F/1274107?fr=aladdin&fromid=2809635&fromtitle=%E6%AC%A7%E5%BC%8F%E8%B7%9D%E7%A6%BB
[70]: /images/20220524/571fc8795996461db0087abd7d02281b.png
[70 1]: /images/20220524/7835eee88f174eb5931d6f87bc96c1fa.png
[70 2]: /images/20220524/4d5e4642ca4446ceacd457b6c56bc966.png
[70 3]: /images/20220524/893c2a17eaad4f39a4c96af66d1dc304.png
[70 4]: /images/20220524/1c336f3890cb4a2da4843933fba3b51a.png