摘要：城市越大勃黍，圈子越小宵统，人越感到孤單。相親覆获，在對(duì)對(duì)方一無所知的情況下马澈，怎么快速的掌握對(duì)方的信息呢？想知道眼前的帥哥有沒有房子弄息，KNN痊班，即K近鄰算法，便可以很好解決相親的問題摹量。

城市越大涤伐，圈子越小馒胆，人越感到孤單。懷念家鄉(xiāng)的小城市凝果，隨便走一圈祝迂，幾乎處處都有熟人。城市大了豆村，匯聚了全國(guó)的人液兽，逛上一天，也不見得遇到個(gè)熟人掌动。于是四啰，尋找異性伴侶的新興方式--相親，便出現(xiàn)了粗恢。

01 樸素的思想

相親柑晒，在對(duì)對(duì)方一無所知的情況下，怎么快速的掌握對(duì)方的信息呢眷射？可以通過對(duì)方的朋友來識(shí)別匙赞。聊一下對(duì)方的親密朋友，聊他們?nèi)ツ膬郝眯醒铮乃齻兤綍r(shí)常逛的地方涌庭。話題也多，也不至于太直白地問對(duì)方收入欧宜，興趣等等坐榆。

通過她的朋友，你便可以間接的了解她冗茸。因?yàn)槿硕紩?huì)和自己有共同興趣愛好的人交朋友席镀。或者說夏漱，她們?cè)谝黄鹁昧撕阑澹匀粫?huì)有很多相似的地方。這便是古老的哲學(xué)思想：“近朱者赤挂绰，近墨者黑”屎篱。我們便由她的朋友來推斷出她的興趣愛好等等。

02 算法介紹

在數(shù)據(jù)挖掘里面扮授，最常用也是簡(jiǎn)單一個(gè)算法芳室，便是：KNN，英文為K-Nearest Neighbor刹勃，即K近鄰算法堪侯，這個(gè)算法便可以很好解決相親的問題。

算法非常簡(jiǎn)單荔仁，一句話便可以說清楚伍宦，要想知道一個(gè)未知事物的類別芽死，找出和它的最近的幾個(gè)鄰居，統(tǒng)計(jì)鄰居中的多數(shù)情況次洼，便可以代表未知事物的情況关贵。比如，想知道眼前的帥哥有沒有房子卖毁，假設(shè)你知道他的5個(gè)朋友中的3個(gè)都有房子揖曾，那么，他很有可能是有房子的亥啦。

上面我們對(duì)這個(gè)帥哥進(jìn)行劃分類別炭剪，有房子還是沒有房子。便是用KNN的思想翔脱，其中的“鄰居”便用“朋友”關(guān)系來代替奴拦。他和這些人做朋友，表示他和這些人走得近届吁，換句專業(yè)術(shù)語來說错妖，他和這些人的相似度很高，比如平時(shí)都喜歡出去唱K疚沐，都周末都喜歡去釣魚暂氯，甚至很可能都是搞IT的。

總結(jié)起來便是：在一堆物品之間亮蛔，通過計(jì)算他們各屬性的相似度株旷，找到和某個(gè)樣本最近的N個(gè)樣本，通過計(jì)算這N個(gè)樣本所屬的類別中的最多數(shù)尔邓，來歸類未知樣本的類別。這是一個(gè)基于案例的算法锉矢，沒有實(shí)際上的模型訓(xùn)練階段梯嗽，直接就是測(cè)試。因?yàn)椴恍枰孪冉⒑媚Ｐ凸了穑憧芍苯訉?duì)物品進(jìn)行分類灯节。

上面中還隱藏了一個(gè)思想，即由鄰居進(jìn)行投票決定绵估，每人一票：少數(shù)服從多數(shù)炎疆，近鄰中哪個(gè)類別的數(shù)目最多就劃分為該類。

03 分類與回歸

KNN算法不僅可以用于分類国裳，還可以用于回歸形入。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本缝左，就可以得到該樣本的屬性亿遂。比如浓若，在一個(gè)大會(huì)中，你想知道小扎的身家值多少錢蛇数。于是你便觀察挪钓，發(fā)現(xiàn)馬云，馬化騰耳舅，小扎他們?nèi)齻€(gè)經(jīng)常聚在一起討論碌上，那么你便可以通過計(jì)算馬云和馬化騰身家的平均值，來近似表示小扎的身家浦徊。雖然馏予，現(xiàn)實(shí)中可能誤差比較大，但至少你不會(huì)認(rèn)為小扎的身家和一個(gè)屌絲程序員沒有區(qū)別辑畦。

這便是回歸與數(shù)值預(yù)測(cè)的應(yīng)用吗蚌。當(dāng)然，更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)纯出，如權(quán)值與距離成反比蚯妇。這便是加權(quán)投票法：根據(jù)距離的遠(yuǎn)近，對(duì)近鄰的投票進(jìn)行加權(quán)暂筝，距離越近則權(quán)重越大（可以取權(quán)重為距離的倒數(shù)）箩言，如小扎和馬云站的距離近些，和馬化騰的距離遠(yuǎn)些焕襟，那么最后算平均的時(shí)候陨收，就按他們距離的的倒數(shù)來進(jìn)行加權(quán)求取平均，通常在某些情況下鸵赖，這樣會(huì)比單純求平均的誤差要小些务漩。

04 算法與調(diào)優(yōu)

KNN算法通常只有兩個(gè)參數(shù)需要注意，第一個(gè)是到底取多少個(gè)近鄰比較好（K參數(shù)）它褪，第二個(gè)是如何計(jì)算出樣本的K個(gè)近鄰饵骨。

對(duì)于參數(shù)K的取值，通常會(huì)根據(jù)具體問題來分析和嘗試茫打，多次嘗試應(yīng)該會(huì)有一個(gè)比較好的結(jié)果居触。如果實(shí)在沒有好的方法，可以試著取3老赤，也許結(jié)果并不會(huì)太差轮洋，正所謂一生二，二生三抬旺，三生萬物弊予。

至于計(jì)算相似度，這算是數(shù)據(jù)挖掘中非常通用的一個(gè)問題了开财，很多地方都會(huì)遇到块促。最簡(jiǎn)單的方法當(dāng)然是取兩者的歐氏距離了荣堰，直觀理解就是二維平面或者三維空間中的兩個(gè)點(diǎn)的直線距離，越近表示越相似竭翠。還有很多計(jì)算相似性度量的方法振坚，請(qǐng)查詢相關(guān)手冊(cè)。

在實(shí)際應(yīng)用中斋扰，通過對(duì)樣本進(jìn)行特征向量的提取渡八，預(yù)先選擇參數(shù)K和相似性度量方法，便可以開始計(jì)算了传货。KNN是一種lazy-learning（懶惰學(xué)習(xí)）算法屎鳍，分類器不需要使用訓(xùn)練集進(jìn)行訓(xùn)練，因此對(duì)測(cè)試樣本進(jìn)行分類/回歸時(shí)的計(jì)算量比較大问裕，內(nèi)存開銷也大逮壁。但最后的結(jié)果比較具有解釋性，因?yàn)槟憧梢苑治鰳颖镜腒個(gè)近鄰的特征粮宛。從而判別結(jié)論的好壞窥淆。

另外一些常用的tricks（技巧），一個(gè)是如何進(jìn)行加權(quán)計(jì)算巍杈，使得結(jié)果更準(zhǔn)確忧饭。可以采用均衡投票筷畦，也可以使用相似性的線性函數(shù)來表示词裤。

減小計(jì)算方面，還可以通過縮小訓(xùn)練計(jì)算的樣本數(shù)來進(jìn)行鳖宾，比如你可以排隊(duì)掉相親美女周圍的已婚女性吼砂，畢竟她們的行為有很多不一致的地方，這些人通常不太會(huì)出現(xiàn)在她的近鄰里面鼎文。也可以對(duì)她的朋友進(jìn)行聚類帅刊，比如把她朋友中20-30歲的聚在一起，已婚和未婚的聚在一起漂问，這樣在每個(gè)類別里面找出一個(gè)具有代表性的人出來進(jìn)行KNN算法。

最后女揭，為了能有效的找到最近鄰蚤假，通常還有兩種優(yōu)化的數(shù)據(jù)結(jié)構(gòu)：kd-tree和ball-tree，他們都會(huì)事先對(duì)所有樣本進(jìn)行結(jié)構(gòu)劃分和存儲(chǔ)吧兔，以便在測(cè)試的時(shí)候更快的找到需要的近鄰樣本磷仰。如果使用Python的話，Scikit-learn實(shí)現(xiàn)的KNN內(nèi)置支持這兩種數(shù)據(jù)結(jié)構(gòu)境蔼，可以加快算法的執(zhí)行速度灶平。

05 具體應(yīng)用

用于手寫數(shù)字識(shí)別伺通；

文本分類；

異常檢測(cè)（攻擊檢測(cè)逢享，欺詐偵測(cè)）罐监；

二手車價(jià)格預(yù)測(cè)；

……

對(duì)于相親瞒爬，如果你是真心想找個(gè)靠譜的人結(jié)婚弓柱，通過各種渠道掌握了她的5個(gè)好朋友的各種信息，你通過統(tǒng)計(jì)發(fā)現(xiàn)侧但，其中三個(gè)經(jīng)常會(huì)用某約P神器矢空，那么可以得出結(jié)論，你……應(yīng)該離她遠(yuǎn)點(diǎn)禀横。