0x03 近朱者赤，相亲knn

摘要：城市越大，圈子越小，人越感到孤单。相亲，在对对方一无所知的情况下，怎么快速的掌握对方的信息呢？想知道眼前的帅哥有没有房子，KNN，即K近邻算法，便可以很好解决相亲的问题。

城市越大，圈子越小，人越感到孤单。怀念家乡的小城市，随便走一圈，几乎处处都有熟人。城市大了，汇聚了全国的人，逛上一天，也不见得遇到个熟人。于是，寻找异性伴侣的新兴方式--相亲，便出现了。

01 朴素的思想

相亲，在对对方一无所知的情况下，怎么快速的掌握对方的信息呢？可以通过对方的朋友来识别。聊一下对方的亲密朋友，聊他们去哪儿旅行，聊她们平时常逛的地方。话题也多，也不至于太直白地问对方收入，兴趣等等。

通过她的朋友，你便可以间接的了解她。因为人都会和自己有共同兴趣爱好的人交朋友。或者说，她们在一起久了，自然会有很多相似的地方。这便是古老的哲学思想：“近朱者赤，近墨者黑”。我们便由她的朋友来推断出她的兴趣爱好等等。

02 算法介绍

在数据挖掘里面，最常用也是简单一个算法，便是：KNN，英文为K-Nearest Neighbor，即K近邻算法，这个算法便可以很好解决相亲的问题。

算法非常简单，一句话便可以说清楚，要想知道一个未知事物的类别，找出和它的最近的几个邻居，统计邻居中的多数情况，便可以代表未知事物的情况。比如，想知道眼前的帅哥有没有房子，假设你知道他的5个朋友中的3个都有房子，那么，他很有可能是有房子的。

上面我们对这个帅哥进行划分类别，有房子还是没有房子。便是用KNN的思想，其中的“邻居”便用“朋友”关系来代替。他和这些人做朋友，表示他和这些人走得近，换句专业术语来说，他和这些人的相似度很高，比如平时都喜欢出去唱K，都周末都喜欢去钓鱼，甚至很可能都是搞IT的。

总结起来便是：在一堆物品之间，通过计算他们各属性的相似度，找到和某个样本最近的N个样本，通过计算这N个样本所属的类别中的最多数，来归类未知样本的类别。这是一个基于案例的算法，没有实际上的模型训练阶段，直接就是测试。因为不需要事先建立好模型，便可直接对物品进行分类。

上面中还隐藏了一个思想，即由邻居进行投票决定，每人一票：少数服从多数，近邻中哪个类别的数目最多就划分为该类。

03 分类与回归

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。比如，在一个大会中，你想知道小扎的身家值多少钱。于是你便观察，发现马云，马化腾，小扎他们三个经常聚在一起讨论，那么你便可以通过计算马云和马化腾身家的平均值，来近似表示小扎的身家。虽然，现实中可能误差比较大，但至少你不会认为小扎的身家和一个屌丝程序员没有区别。

这便是回归与数值预测的应用。当然，更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。这便是加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（可以取权重为距离的倒数），如小扎和马云站的距离近些，和马化腾的距离远些，那么最后算平均的时候，就按他们距离的的倒数来进行加权求取平均，通常在某些情况下，这样会比单纯求平均的误差要小些。

04 算法与调优

KNN算法通常只有两个参数需要注意，第一个是到底取多少个近邻比较好（K参数），第二个是如何计算出样本的K个近邻。

对于参数K的取值，通常会根据具体问题来分析和尝试，多次尝试应该会有一个比较好的结果。如果实在没有好的方法，可以试着取3，也许结果并不会太差，正所谓一生二，二生三，三生万物。

至于计算相似度，这算是数据挖掘中非常通用的一个问题了，很多地方都会遇到。最简单的方法当然是取两者的欧氏距离了，直观理解就是二维平面或者三维空间中的两个点的直线距离，越近表示越相似。还有很多计算相似性度量的方法，请查询相关手册。

在实际应用中，通过对样本进行特征向量的提取，预先选择参数K和相似性度量方法，便可以开始计算了。KNN是一种lazy-learning（懒惰学习）算法，分类器不需要使用训练集进行训练，因此对测试样本进行分类/回归时的计算量比较大，内存开销也大。但最后的结果比较具有解释性，因为你可以分析样本的K个近邻的特征。从而判别结论的好坏。

另外一些常用的tricks（技巧），一个是如何进行加权计算，使得结果更准确。可以采用均衡投票，也可以使用相似性的线性函数来表示。

减小计算方面，还可以通过缩小训练计算的样本数来进行，比如你可以排队掉相亲美女周围的已婚女性，毕竟她们的行为有很多不一致的地方，这些人通常不太会出现在她的近邻里面。也可以对她的朋友进行聚类，比如把她朋友中20-30岁的聚在一起，已婚和未婚的聚在一起，这样在每个类别里面找出一个具有代表性的人出来进行KNN算法。

最后，为了能有效的找到最近邻，通常还有两种优化的数据结构：kd-tree和ball-tree，他们都会事先对所有样本进行结构划分和存储，以便在测试的时候更快的找到需要的近邻样本。如果使用Python的话，Scikit-learn实现的KNN内置支持这两种数据结构，可以加快算法的执行速度。

05 具体应用

用于手写数字识别；
文本分类；
异常检测（攻击检测，欺诈侦测）；
二手车价格预测；
……

对于相亲，如果你是真心想找个靠谱的人结婚，通过各种渠道掌握了她的5个好朋友的各种信息，你通过统计发现，其中三个经常会用某约P神器，那么可以得出结论，你……应该离她远点。