详解K邻近（KNN）模型以及代码剖析

这一篇文章当中我们将会和大家一起来学习KNN(K nearest neighbours)这个模型，在我们进行这个模型的学习之前，让我们先来对机器学习的模型简单的有一个概念。

有监督学习、无监督学习与奇葩

机器学习当中的模型可以简单分成两个类别，一种是有监督模型一种是无监督模型。监督这个概念源于英文supervisor，直接翻译过来理解总觉得有些别扭，其实比较合适的表达是有标注的模型和无标注的模型。标注就是结果，也可以理解成目标，模型在学习的时候明确的知道每一条样本的学习目标。就好像我们学习的时候做选择题，选择题都是有正确答案的，这就是有监督学习。

有监督学习理解了，无监督也就不难理解了。无监督学习就像是考试当中的主观题，没有标准答案，就看你写得好不好。对应到机器学习领域当中，针对的是我们也不知道样本对应结果的问题。比较常见的场景就是聚类问题，我们想要把相似的数据聚集到一个类簇当中，但是呢，我们事先并不知道每一个样本对应的类别是什么，希望算法自己完成这个过程。

虽然我把KNN模型放在无监督模型当中，但其实这是不准确的。因为KNN模型是一个奇葩，理论上说起来它应该既不属于有监督模型也不属于无监督模型。因为KNN模型当中的样本都有自己的目标，也就是说我们知道问题对应的答案。但是呢，模型在学习的时候并不会参考这个目标来学习。说是监督学习模型吧，它不参考这个label学习，而是处通过其他的方式来获得结果。说是无监督模型吧，它的样本当中又必须要有学习的目标。所以它是一个特殊的模型，也有的书中将它归类为基于样本的模型。

KNN模型的原理

KNN模型的英文全称翻译成中文非常直白，意思是K个最近邻居模型。说白了就是用样本的最近邻居的整体情况来代表样本的情况。

举个例子，比如说我们抽样调查了某一个小区的100名业主，发现其中的66名有自己的车。那么我们就拍脑袋做出一个决定，我们认为凡是住在这个小区的业主，都有车。这个结论准确的概率应该也接近66%。

所以如果你能理解上面这个通俗易懂的例子，你就可以理解KNN模型究竟做了一件什么事情。当然原理虽然简单，但是这个模型当中也有很多细节。比如说现实生活当中的邻居好定义，隔壁的楼上的都算，但是对于样本来说这个“邻居”的概念怎么定义？并且又怎么定义邻居的远近呢？

要解释这个问题，我们需要先来简单介绍一下机器学习当中的样本的概念，以及样本的表示。

我们一般用大写字母X表示样本的集合，小写的字母 $x_i$ 表示具体的第i条样本。我们知道样本是由特征组成的，对于绝大多数模型来说，只能接受数字类型的特征。也就是说字符串、结构体或者是其他的内容是不可以作为特征的。如果有字符串、图片这种数据怎么办？一般情况下只能把它们处理成数字。

我们用字母m表示样本的数量，字母n表示特征的数量。所以对于一条样本而言，其实就是含有n个数字型特征的向量。整个样本集，其实就是m条向量组成的矩阵（二维数组）。我们结合一下，一条具体的样本 $x_i$ 可以写成 $(a_1, a_2, \cdots, a_n)$ ，一个样本集 $X$ 也就是样本的集合： $(x_1, x_2, \cdots, x_m)^T$ 。这里加了一个上标T，表示的矩阵的转置，也就是矩阵行变列，列变行。这个是线性代数里的基本常识，就不深入解释了。

另外一点是同一个模型的样本的维度必须是一样的，也就是这一条样本有n个特征，其他的样本也必须是n维的。如果有缺失，则要进行填充，维度必须一致。既然如此，那么就好办了，我们知道向量之间是可以计算距离的。所以再回到KNN这个模型的原理上来，我们就知道了，所谓的K个最近的邻居，其实也就是K个距离最近的样本。

我们假设一条样本是 $A=(a_1, a_2,\cdots, a_n)$ ，另外一条样本是 $B=(b_1, b2_2, \cdots , b_n)$ ，那么AB之间的距离利用两点之间的距离公式就是：

$dis<A, B> = \sqrt{\sum_{i=1}^n (a_i - b_i)^2}$

这里多说一句，两点之间的距离的定义有很多，并不是只有这一个公式。上面这个公式计算的是欧式距离，除此之外还有曼哈顿距离以及切比雪夫距离等等。一般来说我们用欧氏距离就可以了，这里就不多赘述其他的计算方式，感兴趣的可以自行了解一下。

样本的构成以及向量距离计算搞清楚了之后，我们就可以来看算法的原理了。

算法原理

通过上面这个例子，其实我们已经把算法的整个运行过程讲解清楚了。所谓的k-邻近算法，其实就是使用距离样本最近的k个样本的结果来代表当前样本的结果。

整个算法的流程如下：

采集一批有标注结果的样本，设为s
遍历每一个未知结果的样本 $x_i$
遍历s，计算s中的每一个样本和 $x_i$ 的距离
根据距离进行排序，选出距离最小的k个样本
选出这k个样本中出现频次最多的类别作为 $x_i$ 的结果

说白了对于一个样本来说，它的最近的邻居们都是什么样的，它大概率就是什么样的。就好像国外的小区会区分富人区还是穷人区，你的邻居们都住在富人区都有车有房，那么你大概率也是富人有车有房，就是这么一个简单的逻辑。

一般来说我们使用KNN算法都是为了解决分类问题，我们会选择一个比较合适的K，取与样本最接近的K个邻居样本当中的出现次数最多的类别作为它的类别。也就是说KNN算法本身并不涉及对样本本身内容的任何分析或者是计算，所以这个模型并没有直观地体现出“学习”这个概念，模型的目标也不是学习样本的结果，这也是它和其他机器学习模型的最大区别。

代码实现

纸上得来终觉浅，我们学习完了模型之后还需要来亲自动手实现以下算法和模型加深一下印象才算是真正学会了。实际上KNN代码的编写也经常出现在各大公司的笔试题当中，因为KNN的原理比较简单，代码也不复杂，非常适合作为笔试题考察候选人的代码功底和实力。

所以这里还是非常推荐我们来亲自用代码来实现以下这个模型，一方面加深一下印象，一方面也是为之后的面试和笔试做准备。

我们仔细来思考一下，会发现KNN这个模型好像只有一个函数，因为我们既不需要分析样本里的特征，也不需要拟合样本的label，只是需要寻找一下最近的K个样本。完全可以用一个函数搞定，函数的输入是K，需要预测类别的样本和以及所有知道label的样本，输出就是最后要预测的这个样本的label。

我们把这里面的逻辑想清楚了之后，代码就水到渠成了，并不复杂。如果你不知道怎么下手呢，可以参考一下我下面这段代码。在这段代码当中我没有使用任何其他的库函数，只用了原生Python当中的功能。

def calculate_distance(vectorA, vectorB):
    # 计算两个向量的距离
    d = 0
    for i in range(len(vectorA)):
        d += (vectorA[i] - vectorB[i]) * (vectorA[i] - vectorB[i])
    return math.sqrt(d)


def classify(vector, dataSet, labels, k):
    """
    vector: 待预测样本
    dataSet: 全体样本
    labels: 全体样本的label
    """
    dis = []
    # 遍历样本，计算距离
    for i in range(len(dataSet)):
        data = dataSet[i]
        d = calculate_distance(vector, data)
        dis.append(d)
    # 根据距离进行排序
    dis_index = sorted(enumerate(dis), key=lambda x: x[1])
    label_map = {}
    # 筛选出前k个类别
    for i in range(k):
        label = labels[dis_index[i][0]]
        if label in label_map:
            label_map[label] += 1
        else:
            label_map[label] = 1
    maxi = 0
    label = None
    # 找到其中数量最大的那个
    for i in label_map:
        if label_map[i] > maxi:
            maxi = label_map[i]
            label = i

    return label

上面这段代码是写得有些繁琐的，因为我们什么工具库都没有用，全部用的原生的功能来计算的。实际上如果你读过之前的numpy相关使用的文章，对机器学习和Python中一些常用的库有所了解的话，那么上面这段代码还可以大大得简化，甚至简化成只有几行，也就是下面这个版本。

import random

import numpy as np
from collections import Counter


def classify(x, dataset, labels, K):
    x, dataset = np.array(x), np.array(dataset)
    # 通过numpy计算距离，numpy有广播机制
    # 会自动将x和dataset当中的每一行计算距离
    dis = np.sqrt(np.sum((x - dataset) ** 2, axis=1))
    # 按照距离排序，返回结果对应的下标
    topKIdices = np.argsort(dis)[:K]
    labels = np.array(labels)
    # 使用Counter进行计数，返回数量最多的
    counter = Counter(labels[topKIdices])
    return counter.most_common(1)[0][0]

想想看如果你是在笔试当中写出这样漂亮的代码，我想审核官肯定是会给你一个大大的赞的。

优化

到这里虽然我们已经把算法的原理都介绍完了，实现的代码也写出来了，但是整个流程并没有结束。原因很简单，有一个问题被我们忽略了，而且还是挺关键的问题。

问题出在哪里呢？就出在特征上面。

我们前面介绍说在机器学习模型当中，大部分特征都应该是数字型，这样我们方便用各种各样的公式或者是数据结构去计算。这当然是没有问题的，问题在于一些特征的量纲可能不太一样。

举个很简单的例子，假设说我们的模型是预测用户是否有车，我们的特征是用户的性别、年龄、职业和收入。很明显收入是是否有车的一个非常关键的指标，但是这里有一个问题就是收入的范围太广了。马云一个人的收入可能是普通人的上万倍不止，而其他特征的波动幅度则要小得多。比如说性别基本就只有两种，职业可能也就至多几千种，但是收入的差别比它们加起来都要大。

在KNN当中由于我们要计算两个向量的距离，而距离是通过每一个特征的平方和来算的，那么显然在收入这个巨无霸特征面前，其他的特征都是弟弟，对于结果毫无影响。这会导致模型被一个或者少数几个特征带偏，而对其他的特征几乎无视。这对于最后的结果显然是不好的，这是一个极度影响模型结果的问题，也是一个很容易被初学者忽略的问题。实际上并不只是KNN，对于几乎所有机器学习的模型来说，这个问题都是很要命的。

针对这个问题的解决方法有很多，其中比较常用的是归一化。所谓的归一化也就是说通过某一种公式把特征的波动范围标准化，也就是说每个特征都同一起跑线，这样来尽可能得消除量纲以及特征分布带来的影响。

归一化的方式很多，比较常用的有两种。一种是Standardization，又称为Z-score normalization，归一化之后的数据服从正态分布，它的公式如下：