本节书摘来自异步社区出版社《写给程序员的数据挖掘实践指南》一书中的第5章，第5.6节，作者：【美】Ron Zacharski（扎哈尔斯基），更多章节内容可以访问云栖社区“异步社区”公众号查看。

5.6近邻算法的改进

一个普通的分类器的例子是Rote分类器，它只记忆所有的训练集，仅当实例与训练样本精确匹配时才对实例进行分类。如果只在训练集上进行评估，那么Rote分类器的精确率一直是100%。在实际中，由于有些待分类的实例不在训练集中出现，因此Rote分类器并不是一个好的选择。我们可以将前面介绍的近邻分类器看成是Rote分类器的一个扩展。与Rote分类器寻找精确匹配不同的是，近邻方法寻找近似的匹配。Pang Ning Tan、Michael Steinbach和Vipin Kumar在他们所著的数据挖掘教材1中称这种做法为“如果某个东西走路像鸭子，叫起来像鸭子，看上去也像鸭子，那么它可能就是一只鸭子”。

近邻算法在遇到离群点时会发生问题。下面对此进行解释。我们再次回到女子运动员那个例子，这次只考察体操运动员和马拉松运动员。假设有一个个子特别矮、体重特别轻的马拉松运动员。该数据可以用下面的图来表示，其中m表示马拉松运动员，g表示体操运动员。

可以看到，那个个子矮、体重轻的马拉松运动员处于很多g中间的那个m上。假设x是待分类的实例，其最近邻是那个离群点m，因此它被会分为马拉松运动员。如果我们仔细观察上图，我们会说x更像是一名体操运动员，这是因为它出现在一堆体操运动员中间。

kNN
当前的最近邻分类器的一种改进方法是考察k个而不只是1个最近的邻居（kNN）。每个邻居会进行投票，分类器会将实例分到具有最高投票数目的类别中去。例如，假设使用的是3个最近邻（k=3）。上图中会有2票投向体操运动员，1票投向马拉松运动员，因此我们预计x是一名体操运动员。

因此当预测离散型类别（例如，马拉松运动员、体操运动员或篮球运动员）时，可以利用上述投票方法。具有最高得票的类别将被分配给实例。如果存在多个得票相同的类别，则从中随机选择最后的类别。当进行数值预测时（比如给乐队Funky Meters打几星），可以通过计算距离权重值来将影响分摊给多个近邻。这里稍微更深入地分析一下。假设我们想预测Ben喜欢Funky Meters乐队的程度，而Ben的3个最近邻分别是Sally、Tara和Jade。下面给出了他们到Ben的距离以及他们对Funky Meters的评分结果。

因此，Sally离Ben最近，她给Funky Meters的评分为4。由于我希望最近用户的评分在最终评分结果中的权重大于其他近邻的评分，因此第一步就是对距离进行转换以使数值越大用户越近。一种实现的方法就是求距离的倒数（即1除以距离）。于是Sally的距离的倒数为：

下面将每个距离的倒数除以所有倒数之和。所有距离倒数的和为0.2+0.1+0.067=0.367。

我们应该注意到两件事。第一，所有的影响因子之和为1；第二，从原始距离来看，Sally到Ben的距离是她到Tara的距离的两倍，而在最后的影响因子中，两倍的关系仍然保留，也就是说Sally的影响是Tara的两倍。最后，我们将每个人的影响因子乘上评分然后求和，有：

Ben的预测评分
= (0.545×4) + (0.272×5) + (0.183×5)

= 2.18 + 1.36 + 0.915 = 4.455

我想知道Sofia对爵士乐钢琴家Hiromi的喜欢程度，下列数据使用k近邻得到的预测值是多少(k=3)？

第一步是计算每个距离的倒数（1除以距离），得到：

距离倒数之和为0.475。下面通过将每个距离倒数除以距离倒数之和来计算每个用户的影响因子，有：

最后，将影响因子乘上评分并进行累加得到：