机器学习实战笔记 – k-近邻算法(K Nearest Neighbors)

Intro

k-近邻算法通过计算输入向量与训练集向量的距离来进行分类,在本书中我们使用欧式距离(Euclidean Distance):

$$d_{12} = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2 + (z_1 – z_2)^2}$$

本算法将输入向量与训练集中所有向量的欧氏距离从小到大排序,通过对比前k个训练集中的向量的标签,选择出现次数较多的标签,作为分类结果。

优点:精度高、鲁棒性好、只需要做简单的预处理。

缺点:时间、空间复杂度高。

适用数据类型:数值型、标称型。

在本节中,作者通过一部电影中出现打斗镜头和接吻镜头的的次数来判定一部电影是否是动作片还是爱情片。

Algorithm

  • 数据预处理,对于数值型问题,首先需要对输入向量与训练集进行归一化处理(Normalize),防止较大的数据对欧氏距离的结果造成干扰;
  • 计算输入向量与训练集中所有向量的欧氏距离;
  • 将计算结果从小到大排序;
  • 选取前k个样本集中的向量,统计每个向量所对应的标签在k个标签中出现的频率。
  • 返回出现频率最高的标签作为分类结果。

Code

def classify(x, training_set, training_labels, k):

    rows, columns = training_set.shape                              # 获取训练集矩阵的行、列数

    offset_matrix = tile(x, (rows, 1)) - training_set               # 将输入向量复制 rows 行,并与训练集矩阵相减

    square_offset_matrix = offset_matrix ** 2                       # 对结果矩阵中每一组行向量求平方

    offset_sum = square_offset_matrix.sum(axis=1) ** 0.5            # 求每一组行向量的和并开方

    sorted_index_of_offset_sum = offset_sum.argsort()               # 对欧氏距离数组的索引从小到大排序

    label_count = {}                                                # 创建标签字典,键为标签名,值为标签出现次数

    for i in range(k):
        label = training_labels[sorted_index_of_offset_sum[i]]      # 获得第k个索引对应的向量的标签
        label_count[label] = label_count.get(label, 0) + 1          # 将第k个索引对应的向量的标签出现次数+1并存储在标签字典

    sorted_class_count = sorted(label_count.iteritems(),            # 对标签字典的值(标签出现次数)逆序排序
                                key=operator.itemgetter(1),
                                reverse=True)

    return sorted_class_count[0][0]                                 # 输出出现次数最大的键值

Summary

以上是对k-近邻算法在机器学习实战中的总结,在下一节我们将介绍决策树。