机器学习实战 K-近邻算法

K-近邻算法概述

简单地说，k-近邻算法采用测量不同特征值之间的距离的方法进行分类。他的优点是精度高、对异常值不敏感、无数据输入设定。缺点是计算复杂度高、空间复杂度高。使用数据范围为：数值型和标称型。

k-近邻算法（kNN）的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集合中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似数据的数据，这就是k-近邻算法中k的出处，通常，k是不大于20的整数。最后，选择k个最相似的数据中出现的次数最多的分类，作为新数据的分类。

k-近邻算法的一般流程

1. 收集数据： 可以使用任何方法

2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式

3. 分析数据：可以使用任何方法

4. 训练算法：此步骤不适合k-近邻算法

5. 测试算法：计算错误率

6. 使用算法：首先需要输入样本数据和结构化的输出结果。然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

k-近邻算法的实施

对未知类别属性的数据集中的每个点依次执行以下操作：

1. 计算已知类别数据集中的点中的每个点与当前点之间的距离

2. 按照距离递增次序排序

3. 选取与当前距离最小的k个点

4. 确定前k个点所在类别的出现频率

5. 返回前k个点出现频率最高的类别作为当前点的预测分类

点与点之间的距离的算法有很多，这里使用了欧氏距离公式：

​

例如，点（0,0）与（1,2）之间的距离计算为：​

数据的归一化

对于某些数据，其特征值之间的数值差异比较大，而差值最大的属性对结果影响也很大。这会大大提高分类模型的错误率。因此将该类数据归一化是一个重要的操作。下面的公式可以将任取值范围的特征值转换为0到1之间的值：​。其中，min和max分别是数据集中的最小特征值和最大特征值。

如何测试分类器

分类器并不会得到百分百正确的结果，我们可以使用多种方法检测分类器的正确率。此外分类器的性能也会受到多种因素的影响，如分类器设置和数据集等。不同的算法在不同数据集上的表现可能完全不同。

为了测试分类器的效果，我们可以使用已知答案的数据，检验分类器给出的结果是否符合预期结果。通过大量的测试数据，我们可以得到分类器的错误率----分类器给出错误结果的次数除以测试执行的总数。错误率是常用的评估方法，主要用于评估分类器在某个数据集上的执行效果。完美分类器的错误率为0，最差分类器的错误率是1.0。

示例： 使用k-近邻算法改进约会网站的配对效果

数据集见：datingTestSet.txt(提取码：80ms)。数据一共分四列，前三列为三种特征，第四列为三种人物类型。我们将通过前三种特征值，生成一个kNN分类器，来预测不同人对于你的吸引力。

飞行里程数/年	视频游戏时间百分比	每周消费冰激凌公升数	吸引力
40920	8.326976	0.953952	largeDoses
14488	7.153469	1.673904	smallDoses
26052	1.441871	0.805124	didntLike

约会网站K-近邻分类器生成步骤：

1. 收集数据：提供文本文件

2. 准备数据：使用python解析文本文件

3. 测试算法：使用部分数据作为测试样本。计算分类器的错误率

4. 使用算法：产生简单的命令行程序，然后可以输入一些特征数据以判断对方是否为自己喜欢的类型。

python3代码实现

#!/usr/bin/env python3
# coding: utf-8
# Author：Shen Yi
# Date ：2020/2/13 21:19
​
"""机器学习实战 第二章 k-近邻算法
​
k-近邻算法的完整实现，包含了k-近邻算法的距离计算，错误率统计，数据集矩阵标准化以及一个恋爱网站的demo.
​
"""
​
from collections import Counter
from numpy import *
​
​
def knn_classify(in_x, data_set, labels, k_num):
    """ implementation of algorithm of knn
​
    calculation of distance between prediction and training, then sorted and extract the most common labels in top k_num closer data
​
     :param in_x: the vector to predict
     :param data_set: training data
     :param labels:  label of training data
     :param k_num:  number of k
     :return:  label of predict
 """
​
    # calculation of distance
    data_set_size = data_set.shape[0]
    diff_mat = tile(in_x, (data_set_size, 1)) - data_set
    distances = ((diff_mat ** 2).sum(axis=1)) ** 0.5
    sort_distances_index = distances.argsort()
​
    # extract the most common label
    vote_labels = [labels[index] for index in sort_distances_index[0: k_num]]
    most_label = Counter(vote_labels).most_common(1)[0][0]
    return most_label
​
​
def auto_norm(data_set):
    """data normalization"""
​
    min_vals = data_set.min(0)
    max_vals = data_set.max(0)
    ranges = max_vals - min_vals
    m = data_set.shape[0]
    norm_data_set = data_set - tile(min_vals, (m, 1))
    norm_data_set = norm_data_set / tile(ranges, (m, 1))
    return norm_data_set, ranges, min_vals
​
​
def dating_class_test(data_mat, labels, ho_ratio, k_num):
    """calculate the accuracy of the model"""
​
    m = data_mat.shape[0]
    error_count = 0
    number_test_vecs = int(m * ho_ratio)
    for i in range(number_test_vecs):
        classifier_rslt = knn_classify(data_mat[i, :], data_mat[number_test_vecs: m, :], labels[number_test_vecs: m], k_num)
        if classifier_rslt != labels[i]:
            error_count += 1
     print(f"the total error rate is: {error_count / number_test_vecs}")
     return error_count / number_test_vecs
​
​
def demo_date():
     """demo： used knn algorithm model to predict the matching effect of dating websites"""
​
     file_name = "data\\Ch02\\datingTestSet.txt"
     lines = open(file_name).readlines()
     lines_number = len(lines)
     data_mat = zeros((lines_number, 3))
     labels = []
     index = 0
     for line in lines:
         line = line.strip().split('\t')
         data_mat[index, :] = line[0: 3]
         labels.append(line[-1])
         index += 1
​
     norm_data_set, ranges, min_vals = auto_norm(data_mat)
     dating_class_test(norm_data_set, labels, 0.1, 3)
​
     percent_tas = float(input("percentage of time spent playing video games: "))
     ffmiles = float(input("frequent flier miles earned per year: "))
     ice_cream = float(input("liters of ice cream consumed per year:"))
     in_array = (array([ffmiles, percent_tas, ice_cream]) - min_vals) / ranges
     classifier_result = knn_classify(in_array, norm_data_set, labels, 3)
     print(f"you will probably like this person: {classifier_result}")
​
​
if __name__ == '__main__':
    demo_date()

运行结果：

the total error rate is: 0.05
percentage of time spent playing video games: 10
frequent flier miles earned per year: 10000
liters of ice cream consumed per year:0.5
you will probably like this person: smallDoses</pre>

从结果可以看出，该分类器的错误率为5%，在输出一组特征值后，得到了预期的分类标签。