1 k近鄰法（k-nearest neighbor, kNN）
給定測試實例岩灭，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個實例點，然后基于這k個最近鄰的信息來進行預(yù)測堕绩。
通常，在分類任務(wù)中可使用“投票法”，即選擇這k個實例中出現(xiàn)最多的標(biāo)記類別作為預(yù)測結(jié)果榕茧；在回歸任務(wù)中可使用“平均法”，即將這k個實例的實值輸出標(biāo)記的平均值作為預(yù)測結(jié)果客给；還可基于距離遠近進行加權(quán)平均或加權(quán)投票用押，距離越近的實例權(quán)重越大。
k近鄰法不具有顯式的學(xué)習(xí)過程靶剑，事實上蜻拨，它是懶惰學(xué)習(xí)（lazy learning）的著名代表，此類學(xué)習(xí)技術(shù)在訓(xùn)練階段僅僅是把樣本保存起來桩引，訓(xùn)練時間開銷為零缎讼，待收到測試樣本后再進行處理。
2 距離度量
KNN一般采用歐氏距離坑匠，也可采用其他距離度量血崭，一般的Lp距離：
3 K值得選擇
KNN中的K值選取對K近鄰算法的結(jié)果會產(chǎn)生重大影響。如果選擇較小的K值厘灼，就相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實例進行預(yù)測夹纫，“學(xué)習(xí)”近似誤差（近似誤差：可以理解為對現(xiàn)有訓(xùn)練集的訓(xùn)練誤差）會減小，只有與輸入實例較近或相似的訓(xùn)練實例才會對預(yù)測結(jié)果起作用设凹，與此同時帶來的問題是“學(xué)習(xí)”的估計誤差會增大舰讹，換句話說，K值的減小就意味著整體模型變得復(fù)雜闪朱，容易發(fā)生過擬合月匣；
如果選擇較大的K值匈睁，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實例進行預(yù)測，其優(yōu)點是可以減少學(xué)習(xí)的估計誤差桶错，但缺點是學(xué)習(xí)的近似誤差會增大航唆。這時候，與輸入實例較遠（不相似的）訓(xùn)練實例也會對預(yù)測器作用院刁，使預(yù)測發(fā)生錯誤糯钙，且K值的增大就意味著整體的模型變得簡單。
在實際應(yīng)用中退腥，K值一般取一個比較小的數(shù)值任岸，例如采用交叉驗證法來選擇最優(yōu)的K值。經(jīng)驗規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根
4 KNN的決策過程
1狡刘、計算測試對象到訓(xùn)練集中每個對象的距離
2享潜、按照距離的遠近排序
3、選取與當(dāng)前測試對象最近的k的訓(xùn)練對象嗅蔬，作為該測試對象的鄰居
4剑按、統(tǒng)計這k個鄰居的類別頻率
5、k個鄰居里頻率最高的類別澜术，即為測試對象的類別
5 KNN如何優(yōu)化數(shù)據(jù)量很大時艺蝴，暴力計算困難的問題
輸入X可以采用BallTree或KDTree兩種數(shù)據(jù)結(jié)構(gòu)，優(yōu)化計算效率鸟废，可以在實例化KNeighborsClassifier的時候指定猜敢。
KDTree
基本思想是，若A點距離B點非常遠盒延，B點距離C點非常近缩擂， 可知A點與C點很遙遠，不需要明確計算它們的距離添寺。 通過這樣的方式胯盯，近鄰搜索的計算成本可以降低為O[DNlog(N)]或更低。 這是對于暴力搜索在大樣本數(shù)N中表現(xiàn)的顯著改善畦贸。KD 樹的構(gòu)造非吃赡郑快，對于低維度 (D<20) 近鄰搜索也非潮』担快, 當(dāng)D增長到很大時，效率變低： 這就是所謂的 “維度災(zāi)難” 的一種體現(xiàn)寨闹。
KD 樹是一個二叉樹結(jié)構(gòu)胶坠，它沿著數(shù)據(jù)軸遞歸地劃分參數(shù)空間，將其劃分為嵌入數(shù)據(jù)點的嵌套的各向異性區(qū)域繁堡。 KD 樹的構(gòu)造非成蛏疲快：因為只需沿數(shù)據(jù)軸執(zhí)行分區(qū), 無需計算D-dimensional 距離乡数。 一旦構(gòu)建完成, 查詢點的最近鄰距離計算復(fù)雜度僅為O[log(N)]。 雖然 KD 樹的方法對于低維度 (D<20) 近鄰搜索非澄拍担快, 當(dāng)D增長到很大時, 效率變低净赴。
KD樹的特性適合使用歐氏距離。
BallTree
BallTree解決了KDTree在高維上效率低下的問題罩润，這種方法構(gòu)建的樹要比 KD 樹消耗更多的時間玖翅，但是這種數(shù)據(jù)結(jié)構(gòu)對于高結(jié)構(gòu)化的數(shù)據(jù)是非常有效的， 即使在高維度上也是一樣割以。
KD樹是依次對K維坐標(biāo)軸金度，以中值切分構(gòu)造的樹；ball tree 是以質(zhì)心C和半徑r分割樣本空間严沥，每一個節(jié)點是一個超球體猜极。換句簡單的話來說，對于目標(biāo)空間(q, r)消玄，所有被該超球體截斷的子超球體內(nèi)的所有子空間都將被遍歷搜索跟伏。
BallTree通過使用三角不等式減少近鄰搜索的候選點數(shù):|x+y|<=|x|+|y|通過這種設(shè)置, 測試點和質(zhì)心之間的單一距離計算足以確定距節(jié)點內(nèi)所有點的距離的下限和上限. 由于 ball 樹節(jié)點的球形幾何, 它在高維度上的性能超出 KD-tree, 盡管實際的性能高度依賴于訓(xùn)練數(shù)據(jù)的結(jié)構(gòu)。
BallTree適用于更一般的距離翩瓜。
6 KNN算法的優(yōu)缺點
1酬姆、優(yōu)點
非常簡單的分類算法沒有之一，人性化奥溺，易于理解辞色，易于實現(xiàn)
適合處理多分類問題，比如推薦用戶
可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)浮定，既可以用來做分類也可以用來做回歸
對異常值不敏感
2相满、缺點
屬于懶惰算法，時間復(fù)雜度較高桦卒，因為需要計算未知樣本到所有已知樣本的距離
樣本平衡度依賴高立美，當(dāng)出現(xiàn)極端情況樣本不平衡時，分類絕對會出現(xiàn)偏差方灾，可以調(diào)整樣本權(quán)值改善
可解釋性差建蹄，無法給出類似決策樹那樣的規(guī)則
向量的維度越高，歐式距離的區(qū)分能力就越弱
樣本空間太大不適合裕偿，因為計算量太大洞慎，預(yù)測緩慢
7 KNN算法的應(yīng)用場景
文本分類
用戶推薦
回歸問題
8 K-means聚類算法
1）所有的觀測實例中隨機抽取出k個觀測點，作為聚類中心點嘿棘，然后遍歷其余的觀測點找到距離各自最近的聚類中心點劲腿，將其加入到該聚類中。這樣鸟妙，我們就有了一個初始的聚類結(jié)果焦人，這是一次迭代的過程挥吵。
2）我們每個聚類中心都至少有一個觀測實例，這樣花椭，我們可以求出每個聚類的中心點（means）忽匈，作為新的聚類中心，然后再遍歷所有的觀測點矿辽，找到距離其最近的中心點泛鸟，加入到該聚類中藕畔。然后繼續(xù)運行2）。
3）如此往復(fù)2），直到前后兩次迭代得到的聚類中心點一模一樣歧斟。
本算法的時間復(fù)雜度：O(tkmn)鹊奖，其中长窄，t為迭代次數(shù)按厘，k為簇的數(shù)目，m為記錄數(shù)碳默，n為維數(shù)贾陷；
空間復(fù)雜度：O((m+k)n)，其中嘱根，k為簇的數(shù)目髓废，m為記錄數(shù)，n為維數(shù)该抒。
適用范圍：
K-menas算法試圖找到使平凡誤差準則函數(shù)最小的簇慌洪。當(dāng)潛在的簇形狀是凸面的，簇與簇之間區(qū)別較明顯凑保，且簇大小相近時冈爹，其聚類結(jié)果較理想。前面提到欧引，該算法時間復(fù)雜度為O(tkmn)频伤，與樣本數(shù)量線性相關(guān)，所以芝此，對于處理大數(shù)據(jù)集合憋肖，該算法非常高效，且伸縮性較好婚苹。但該算法除了要事先確定簇數(shù)K和對初始聚類中心敏感外岸更，經(jīng)常以局部最優(yōu)結(jié)束，同時對“噪聲”和孤立點敏感租副，并且該方法不適于發(fā)現(xiàn)非凸面形狀的簇或大小差別很大的簇坐慰。
9 K-means算法的問題
1）首先，算法只能找到局部最優(yōu)的聚類用僧，而不是全局最優(yōu)的聚類结胀。而且算法的結(jié)果非常依賴于初始隨機選擇的聚類中心的位置。我們通過多次運行算法责循，使用不同的隨機生成的聚類中心點運行算法糟港，然后對各自結(jié)果C通過evaluate(C)函數(shù)進行評估，選擇多次結(jié)果中evaluate(C)值最小的那一個院仿。k-means++算法選擇初始seeds的基本思想就是：初始的聚類中心之間的相互距離要盡可能的遠
2）關(guān)于初始k值選擇的問題秸抚。首先的想法是，從一個起始值開始歹垫，到一個最大值剥汤，每一個值運行k-means算法聚類，通過一個評價函數(shù)計算出最好的一次聚類結(jié)果排惨，這個k就是最優(yōu)的k吭敢。我們首先想到了上面用到的evaluate(C)。然而暮芭，k越大鹿驼，聚類中心越多，顯然每個觀測點距離其中心的距離的平方和會越小辕宏，這在實踐中也得到了驗證畜晰。第四節(jié)中的實驗結(jié)果分析中將詳細討論這個問題。
3）關(guān)于性能問題瑞筐。原始的算法凄鼻，每一次迭代都要計算每一個觀測點與所有聚類中心的距離。有沒有方法能夠提高效率呢聚假？是有的块蚌，可以使用k-d tree或者ball tree這種數(shù)據(jù)結(jié)構(gòu)來提高算法的效率。特定條件下魔策，對于一定區(qū)域內(nèi)的觀測點匈子，無需遍歷每一個觀測點，就可以把這個區(qū)域內(nèi)所有的點放到距離最近的一個聚類中去闯袒。這將在第三節(jié)中詳細地介紹虎敦。
10 KNN和K-means的區(qū)別
- KNN屬于監(jiān)督學(xué)習(xí)算法，K-means屬于非監(jiān)督學(xué)習(xí)算法政敢；
- KNN沒有前期訓(xùn)練過程其徙，K-means有訓(xùn)練過程；
- KNN屬于分類算法喷户，目的是為了確定一個點的類別唾那。K-means屬于聚類算法，目的是為了將一系列點集分成k類褪尝；
相似點：都包含這樣的過程闹获，給定一個點期犬，在數(shù)據(jù)集中找離它最近的點。即二者都用到了NN(Nears Neighbor)算法避诽，一般用KD樹來實現(xiàn)NN龟虎。
k-d tree 與 ball tree
1）k-d tree[5]
把n維特征的觀測實例放到n維空間中，k-d tree每次通過某種算法選擇一個特征(坐標(biāo)軸)沙庐，以它的某一個值作為分界做超平面鲤妥，把當(dāng)前所有觀測點分為兩部分，然后對每一個部分使用同樣的方法拱雏，直到達到某個條件為止棉安。
上面的表述中，有幾個地方下面將會詳細說明：（1）選擇特征（坐標(biāo)軸）的方法 （2）以該特征的哪一個為界 （3）達到什么條件算法結(jié)束铸抑。
(1)選擇特征的方法
計算當(dāng)前觀測點集合中每個特征的方差贡耽，選擇方差最大的一個特征，然后畫一個垂直于這個特征的超平面將所有觀測點分為兩個集合羡滑。
（2)以該特征的哪一個值為界 即垂直選擇坐標(biāo)軸的超平面的具體位置菇爪。
第一種是以各個點的方差的中值（median）為界。這樣會使建好的樹非常地平衡柒昏，會均勻地分開一個集合凳宙。這樣做的問題是，如果點的分布非常不好地偏斜的职祷，選擇中值會造成連續(xù)相同方向的分割氏涩，形成細長的超矩形(hyperrectangles)。
替代的方法是計算這些點該坐標(biāo)軸的平均值有梆，選擇距離這個平均值最近的點作為超平面與這個坐標(biāo)軸的交點是尖。這樣這個樹不會完美地平衡，但區(qū)域會傾向于正方地被劃分泥耀，連續(xù)的分割更有可能在不同方向上發(fā)生饺汹。
（3）達到什么條件算法結(jié)束
實際中，不用指導(dǎo)葉子結(jié)點只包含兩個點時才結(jié)束算法痰催。你可以設(shè)定一個預(yù)先設(shè)定的最小值兜辞，當(dāng)這個最小值達到時結(jié)束算法。
圖6中夸溶，星號標(biāo)注的是目標(biāo)點逸吵，我們在k-d tree中找到這個點所處的區(qū)域后，依次計算此區(qū)域包含的點的距離缝裁，找出最近的一個點（黑色點）扫皱，如果在其他region中還包含更近的點則一定在以這兩個點為半徑的圓中。假設(shè)這個圓如圖中所示包含其他區(qū)域。先看這個區(qū)域兄弟結(jié)點對應(yīng)區(qū)域韩脑，與圓不重疊氢妈；再看其雙親結(jié)點的兄弟結(jié)點對應(yīng)區(qū)域。從它的子結(jié)點對應(yīng)區(qū)域中尋找（圖中確實與這個雙親結(jié)點的兄弟結(jié)點的子結(jié)點對應(yīng)區(qū)域重疊了）扰才。在其中找是否有更近的結(jié)點允懂。
k-d tree的優(yōu)勢是可以遞增更新厕怜。新的觀測點可以不斷地加入進來衩匣。找到新觀測點應(yīng)該在的區(qū)域，如果它是空的粥航，就把它添加進去琅捏，否則，沿著最長的邊分割這個區(qū)域來保持接近正方形的性質(zhì)递雀。這樣會破壞樹的平衡性柄延，同時讓區(qū)域不利于找最近鄰。我們可以當(dāng)樹的深度到達一定值時重建這棵樹缀程。
然而搜吧，k-d tree也有問題。矩形并不是用到這里最好的方式杨凑。偏斜的數(shù)據(jù)集會造成我們想要保持樹的平衡與保持區(qū)域的正方形特性的沖突滤奈。另外，矩形甚至是正方形并不是用在這里最完美的形狀撩满，由于它的角蜒程。如果圖6中的圓再大一些，即黑點距離目標(biāo)點點再遠一些伺帘，圓就會與左上角的矩形相交昭躺，需要多檢查一個區(qū)域的點，而且那個區(qū)域是當(dāng)前區(qū)域雙親結(jié)點的兄弟結(jié)點的子結(jié)點伪嫁。
為了解決上面的問題领炫，我們引入了ball tree。
2）ball tree[4]
解決上面問題的方案就是使用超球面而不是超矩形劃分區(qū)域张咳。使用球面可能會造成球面間的重疊帝洪，但卻沒有關(guān)系。ball tree就是一個k維超球面來覆蓋這些觀測點晶伦，把它們放到樹里面碟狞。圖7（a)顯示了一個2維平面包含16個觀測實例的圖,圖7（b）是其對應(yīng)的ball tree，其中結(jié)點中的數(shù)字表示包含的觀測點數(shù)婚陪。
不同層次的圓被用不同的風(fēng)格畫出族沃。樹中的每個結(jié)點對應(yīng)一個圓，結(jié)點的數(shù)字表示該區(qū)域保含的觀測點數(shù)，但不一定就是圖中該區(qū)域囊括的點數(shù)脆淹，因為有重疊的情況常空，并且一個觀測點只能屬于一個區(qū)域。實際的ball tree的結(jié)點保存圓心和半徑盖溺。葉子結(jié)點保存它包含的觀測點漓糙。
使用ball tree時，先自上而下找到包含target的葉子結(jié)點烘嘱，從此結(jié)點中找到離它最近的觀測點昆禽。這個距離就是最近鄰的距離的上界。檢查它的兄弟結(jié)點中是否包含比這個上界更小的觀測點蝇庭。方法是：如果目標(biāo)點距離兄弟結(jié)點的圓心的距離大于這個圓的圓心加上前面的上界的值醉鳖，則這個兄弟結(jié)點不可能包含所要的觀測點。（如圖8）否則哮内，檢查這個兄弟結(jié)點是否包含符合條件的觀測點盗棵。
那么，ball tree的分割算法是什么呢北发？
選擇一個距離當(dāng)前圓心最遠的觀測點i1纹因，和距離i1最遠的觀測點 i2，將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心琳拨，然后計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑瞭恰。對包含n個觀測點的超圓進行分割，只需要線性的時間从绘。
與k-d tree一樣寄疏，如果結(jié)點包含的觀測點到達了預(yù)先設(shè)定的最小值，這個頂點就可以不再分割了僵井。
