K邻近分类算法详解

其实这是一个非常简单的算法，但由于网上的资料专业术语太多，把事情弄复杂化了，为了能更好的理解这个算法，这里尽量不使用过多的专业术语，而采用更接近生活的语句来写这篇文章。

K邻近算法是一个分类算法，采用的是“物以类聚人以群分”的思想，通过统计某个未知事物周边的同类数量，然后把未知的事物归为某一类，例如：假设某个人最经常联系的朋友有10个，2个是宅男，6个是喜欢踢足球的，1个是打篮球的，1个是偶尔运动下的，那么可以猜测，这个人很有可能喜欢运动，而且运动项目可能是踢足球。

可以看出，K邻近算法实现的前提就是：必须先有已经正确分类好的数据，才可以将未知事物归类。

下面有个例子，就是如何将一部电影归类：

假设已经有分类好的数据如下：

视频A是战争片，所以整部视频里，有武器和战斗的镜头是非常多的；
视频B是军事讲座，主要是介绍武器，过程中偶尔穿插了一些战斗场景；
视频C是枪战片，武器镜头不是很多，战斗场景的镜头不多也不少。
视频D是一部激烈的枪战片，武器镜头虽然很少，但是战斗场面镜头很多。
视频E是战争片，稍微比视频A打得激烈点。
视频F是一部激烈的战争片，战斗场景非常多，显然就是人狠话不多，不服就干的类型。
视频G是本例的主角，属于未知类型，需要计算机去判断并归类，这部片子的武器镜头是600次，有战斗场景的镜头500次，从直觉上来说，这有可能是一部历史题材的纪录片，也有可能是一部战争片。计算机到底会将视频G归类成什么类型的视频呢？



首先，需要将未知电影和已分类好的电影展现在一个坐标轴里，X轴是武器镜头数量，Y轴代表战斗场景的镜头数量，得出下面的图：



然后将红色G点（未知电影的点）与其他每一个点都计算距离，将这个距离看作判断准则，越近代表越相似。这个计算方法就不用我说了，其实就是计算三角形的边长，经过计算得到如下结果（小数点不要，四舍五入）：



G点到A的的距离：GA=412
G点到B的的距离：GB=424
G点到C的的距离：GC=447
G点到D的的距离：GD=510
G点到E的的距离：GE=447
G点到F的的距离：GF=361

取最靠近的一个点，那么F点是最靠近G点的，那么将G归类为跟F一样的类型（战争片）。那么取最靠近的两个点F和A，G还是被归类为战争片，所以G基本上就是被归类为战争片了，这就是整个算法的工作原理。

影响最终判断结果准确率的因素：

1 取最近点的数量

取三个点？四个点？到底取多少个点？其实在现实操作中，并没有统一标准做法，是根据实际应用场景来决定的。有些在计算机算力许可前提下，取的数量尽量多，而有些取的数量是有范围限制的。

2 距离

实际操作中，并不是每一个点的权重都一样的，还有一个因素的，距离也是影响权重的因素，距离越近的点权重越大，距离越远的点权重越小。权重就相当于权威程度。打个比方：你的邻居跟你住的很近，你邻居对你的评价要比小区里其他人有较高的权威度，但是这并不代表100%正确，有时候小区里大部分人对你的评价才是正确的评价。

3 判断特征

训练样本都有一个到多个特征，每个特征也是有权重的，对于本例子来说，“有战斗场景的镜头”这个特征才是比较重要的判断因素，毕竟都是枪战题材的视频，视频里出现武器的现象是很平常的事情，它们之间区别比较大的就是战斗场面的数量和激烈程度。

4 每一类样本数据的数量

在本例中，假设有1000个已经分类好的数据，但是只有1个是战争片的样本，其他999个都是军事题材的样本，那么无论再怎么调整参数，未知视频基本上都会被判断成军事题材的视频。

总结：这个算法简单有效，容易理解，但操作起来不能太死板，必须根据实际应用场景设置各种参数，有些因素需要有权重之分，有些因素不能有权重之分，等等，当参数设置得当，得到的结果准确率是非常高的。例如本例中，距离就没有权重之分，因为视频是一个虚拟事物，它不具备有主观思维去评判未知事物的能力；但是如果是人或动物的话，那距离就有权重之分了，因为动物是带有主观性的物体。另外，特征也一样，有些样本它们的所有特征都同样重要，没有轻重之分，而有些样本的一个到几特征是比较重要的，那特征就有轻重之分，也就有权重之分。

K邻近算法每个点的距离的计算方法

可以把样本的每个特征看作所以一维向量，点与点之间的距离计算公式：一般采用欧氏距离或哈曼顿距离。

K邻近算法的实现方法：

最简单的方法就是，每次判断一个未知事物，就把未知点和所有样本点的距离都计算一遍，然后再从计算结果中取距离最近的几个进行判断。

问题是，当数据量非常大的时候，每次都这样计算，实在太耗时间了，得想办法找个好的计算方法，K-D树或LSH位置敏感哈希法。

K-D树是一个二叉树的结构，它适用于多属性查找，树的每个节点就是一个样本数据，每个节点都是一个属性分割点，左边子节点里对应的特征值小于父节点的分割属性值，右边子节点里对应的特征值大于或等于父节点的分割属性值。这种分割方法有点像排序二叉树，但又不是排序二叉树，因为K-D树里面，有些特征值是相同的。K-D树的建立有很多种方法，其中一种常用方法是可以建立一个平衡的排序二叉树，但是在现实使用中，平衡二叉树并不是所有的应用场景中最优的。构建K-D树的详细步骤。

LSH能高效处理海量高维数据的最近邻问题，用hash的方法把数据映射到一个新的空间中，因为有一些哈希算法会把相似的数据计算出相似的结果，利用这种特征，将计算结果映射到一个空间上面，使得相似的原始数据在新的空间中也相似的概率很大，而原始数据不相似的数据，在新的空间中相似的概率很小。

K-D树和LSH的区别是：

K-D树能算出比较准确的数据（但也有误差），LSH能准确率没那么高；
K-D树运行速度比LSH慢很多；

也没有哪种最优的说法，还是要看实际应用场景，有些应用场景要求速度快，而且允许有误差的就用LSH。