概念

K-NN 算法采用测量不同特征值之间的距离的方法进行分类。工作原理：存在一个样本数据集，也称作训练样本集，并且样本集中每个数据都存在标签。输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应特征进行比较，然后算法提取样本集中特征最相似的数据（最邻近）的分类标签。一般来说，只选择样本数据集中前 k 个最相似的数据，这就是 k-NN 算法中 k 的出处，通常 k 是不大于 20 的整数。最后选择在 k 个最相似的数据中出现次数最多的分类，作为新数据的分类。

简单来说，K-NN 算法使用了一种计算特征之间的距离的公式，然后选择距离前 k 近的数据，获取这些数据的标签。通过一个简单的统计，获取这 k 项数据中最多的类别。最后我们将新数据看作是这个类别。

代码

import numpy as np
import operator


np.random.seed(12)


def create_dataset():
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


def classify(input, dataset, labels, k):
    """
    K-NN 分类
    :param input: 输入数据，即待分类的数据
    :param dataset: 训练数据集
    :param labels: dataset 对应的标签
    :param k: 显而易见
    :return: input 的类别
    """
    # 计算特征之间的距离，只是一个很简单的算法
    # 先算差，再平方，然后将一个项数据的所有特征累加，最后开方
    all_distances = np.sqrt(np.sum(np.power((input - dataset), 2), 1))
    # 对距离进行逆序排序
    sorted_distance_indices = all_distances.argsort()
    # 对类别进行计数
    class_count = {}
    # 选取前 k 项数据
    for i in range(k):
        # 第 i 项数据的标签
        label = labels[sorted_distance_indices[i]]
        # 标签存在则加 1，不存在就默认是 0 再加 1
        class_count[label] = class_count.get(label, 0) + 1

    # 根据标签的数量排序
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]


if __name__ == '__main__':
    X, Y = create_dataset()
    res = classify([0, 0], X, Y, 3)
    print(res)

均值归一化

由于有些数据范围波动较大，可以进行均值归一化处理。

应用

引用《机器学习实战》中的应用。 1. 可以分类电影的类别，已知数据：打斗镜头、接吻镜头、电影的类别。如果给定一部新电影，则可以根据该电影的打斗镜头、接吻镜头来计算此部电影属于哪种类别。 2. 改进约会网站配对效果。已知数据：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数、用户交往对象的类别。其中用户交往对象的类别指： - 不喜欢的人 - 魅力一般的人 - 极具魅力的人则可以输入一个新的约会对象的数据，从而判断此人属于哪种类别，如果属于不喜欢的人的类别，那么用户可以提前得知，并且决定不去约会。 3. 甚至可以识别手写数字。将图片转换成 0 1 表示，即数字部分用 1 表示，其他部分用 0 表示。组成一个 32 x 32 数字矩阵，然后将矩阵转换为 1 x 1024 的向量。其中的每一维度的值可以看作为一个特征。算法类似。

博客

机器学习算法（七）：K-NN

概念

代码

均值归一化

应用