算法(八)：图解KNN算法

K最相邻算法(K-NearestNeighbor Classification Algorithm,KNN)是数据挖掘分类技术中最简单的方法之一,所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻居来代表。

KNN算法的核心思想是如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的K个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。

案例

这边的案例来自"算法图解"一书，来自书上的例子，只是为了对KNN算法有一个基础认识。

案例一

假设有一个水果(橙子或者柚子)， 如何判断它是橙子或者柚子呢？ 这时大脑思维过程一般类似:存在一个水果特征图表，假设个头越大、颜色越黄的就是柚子，如下图，然后会判断该神秘水果特征最接近橙子或者柚子，最接近的就是该水果的种类。

一种方法是看它的邻居分别是什么水果来进行判断，假设看3个邻居，由上图所示1，4，7这三个距离最近，因为橙子有2个即1和4节点，柚子只有1个即7节点。橙子比柚子多，所以该未知的水果很有可能为橙子。这简单的判断分类的过程便是使用了简单的KNN算法来达到分类的目的。

计算2点间的距离可以使用公式(√为平方根符号)：

d = √((x1 - x2)² + (y1 - y2)²)

我们进行分类判断所抽取的特征为水果的个头、颜色这2个特征点，节点3的位置(3,10),节点7的位置(8,15),则2点之间的距离为:

d = √((3 - 8)² + (10 - 15)²) = √(50)

多维坐标同上述二维坐标一样，可以使用比如四维度的(x1,y1,z1,w1)与(x2,y2,z2,w2)：

d = √((x1 - x2)² + (y1 - y2)² + (z1 - z2)² + (w1 - w2)²)

余弦相似度

前面计算两位用户的距离时，使用的都是距离公式。还有更合适的公式吗？在实际工作中， 经常使用余弦相似度（cosine similarity）。假设有两位品味类似的用户，但其中一位打分时更 保守。他们都很喜欢Manmohan Desai的电影Amar Akbar Anthony，但Paul给了5星，而Rowan只 给4星。如果你使用距离公式，这两位用户可能不是邻居，虽然他们的品味非常接近。 余弦相似度不计算两个矢量的距离，而比较它们的角度，因此更适合处理前面所说的情况。

案例二

电影推荐系统：

假设有电影网站，用户注册时要求他们对喜欢的电影类别进行评分，现在获取到如下表的评分数据(满分5分)。

根据KNN，评分越相近的人，喜爱的电影就会越一致，现在需要给小张推荐电影，就可以把喜好与他最接近的人所收藏的电影推荐给他。

计算出小张与其它人的距离：

比如小张与小王: d = √((3 - 2)² + (1 - 4)² + (3 - 4)² + (5 - 4)² ) = 2√3 ，各种距离如下：

可以看到小张与小林距离最近，所以可以将小林喜欢的电影推荐给小张。实际中如果给电影网站更多的电影进行评分的话，就可以获取更加精准的推送，因为网站更能准确判断你和哪些用户类似。

使用KNN回归预测某个值：

假设有无数个用户，选取以下5个距离小杨最近的用户(实际中合理距离内的邻居数量越多，预测越准确)，预测小杨将对各部电影的评分：

可以简单的求出这5个邻居对电影A的平均分： (3 + 3.5 + 3 + 2.5 + 2.5) /5 = 2.9 上述使用了KNN执行2件事：

• 1.分类：编组，相近的编为一组
• 2.回归：预测结果

假设要从下列5个用户对电影B评分的平均分来作为电影B最终平均得分的话，则 (1 + 4 + 3 + 1 + 4)/5 = 2.6，但是 上述计算是基于每个人评分的的标准都是一致的，但一般不同的人评分标准不同，比如有的人会给有点喜欢的电影评上4分，但是有的人要求高只会给有点喜欢的电影评上3分。

所以我们可以计算出每个人大致的平均分，以此简单判断每个人的评分标准，比如以小张为每个人的标准模板，则小王所占权重为 3/3.5 = 0.85(因为小王评分普遍偏高，所以下调点权重)，

则电影电影B最终平均得分： （1 1 + 4 0.85 + 3 1 + 1 0.83 + 4* 0.92）/5 = 2.22