sklearn.neighbors提供基于鄰居的有監(jiān)督和無監(jiān)督的學(xué)習方法及汉。無監(jiān)督最近鄰方法是很多學(xué)習方法的基礎(chǔ)，特別是流形學(xué)習和譜聚類矢沿。有監(jiān)督的最近鄰方法包括：離散數(shù)據(jù)的分類滥搭、連續(xù)數(shù)據(jù)的回歸。
最近鄰方法的原理是捣鲸，找到指定數(shù)量的最近樣本點瑟匆，然后根據(jù)這些點去預(yù)測新的點。樣本點的數(shù)量可以由用戶定義（k-最近鄰）或者基于點的局部密度。距離度量標準可以有很多種愁溜，歐式距離是最常用的選擇疾嗅。基于鄰居的方法被稱為non-generalizing machine learning冕象，因為它只是“記住”訓(xùn)練數(shù)據(jù)（可能轉(zhuǎn)化為一個快速的索引結(jié)構(gòu)代承，如BallTree或KDTree）。
盡管很簡單渐扮，但是最近鄰方法能解決大量分類和回歸問題论悴，包括手寫數(shù)字或衛(wèi)星圖像識別，作為一種非參數(shù)方法墓律，在分類邊界不規(guī)則的情況下通常是有效的膀估。

無監(jiān)督的最近鄰

NearestNeighbors 執(zhí)行無監(jiān)督的最近鄰方法，有三種不同的最近鄰算法：BallTree耻讽、KDTree察纯、a brute-force algorithm based on routines in sklearn.metrics.pairwise，鄰居的搜索算法通過關(guān)鍵詞 ‘a(chǎn)lgorithm’ 控制针肥，選項包括['auto', 'ball_tree', 'kd_tree', 'brute']饼记，當設(shè)置為‘a(chǎn)uto’時，算法將通過訓(xùn)練數(shù)據(jù)決定最好的方法慰枕。
Warning：在最近鄰算法中具则，當有兩個點和預(yù)測點的距離相同但標簽不同時，結(jié)果將依賴點在訓(xùn)練數(shù)據(jù)中的順序捺僻。

KDTree和BallTree

可以使用KDTree或BallTree直接發(fā)現(xiàn)最近鄰乡洼。
KDTree和BallTree的詳細解釋：
http://blog.csdn.net/skyline0623/article/details/8154911

最近鄰分類

基于鄰居的分類是一種基于實例的學(xué)習或者非泛化學(xué)習（a type of instance-based learning or non-generalizing learning），它不試圖構(gòu)建一個通用的內(nèi)部模型匕坯，只是簡單的存儲訓(xùn)練數(shù)據(jù)的實例束昵。通過每個點的最近鄰的簡單多數(shù)投票來分類，一個查詢點被分配給它的最近鄰中最有代表性的那個數(shù)據(jù)類葛峻。
scikit-learn 包括兩種最近鄰分類器：KNeighborsClassifier 和 RadiusNeighborsClassifier锹雏。KNeighborsClassifier是比較常用的一種，一般的术奖，一個比較大的k值能抑制異常值的影響礁遵，但是也讓分類邊界的區(qū)分性下降。
如果是不均勻采樣數(shù)據(jù)采记，RadiusNeighborsClassifier中的基于半徑的最近鄰分類是一個比較好的選擇佣耐。用戶指定一個固定的半徑 r ，那些稀疏區(qū)域中的點使用較少的最近鄰去分類唧龄，在高維參數(shù)空間兼砖，由于所謂的“維災(zāi)難”，這種方法就變得不那么有效。
基本的最近鄰分類器使用一致權(quán)重讽挟，即采用最近鄰數(shù)據(jù)的簡單多數(shù)表決懒叛。在某些情況下，更近的數(shù)據(jù)點對模型的貢獻更大耽梅，可以通過參數(shù) weights 來設(shè)置薛窥。默認情況下，weights=‘uniform’眼姐，所有鄰居的權(quán)重是相同的诅迷。weights=‘distance’ ，權(quán)重正比于到查詢點的距離的倒數(shù)众旗。另外竟贯，用戶也可以自定義函數(shù)計算權(quán)重。

最近鄰回歸

當數(shù)據(jù)標簽是離散的而不是連續(xù)的逝钥，可以使用最近鄰回歸方法。查詢點的標簽通過最近鄰點的平均標簽計算拱镐。
scikit-learn有兩種最近鄰回歸方法：KNeighborsRegressor 和 RadiusNeighborsRegressor艘款。

最近鄰算法

Brute Force

快速計算最近鄰是機器學(xué)習中一個活躍的研究領(lǐng)域。最簡單的方法是計算數(shù)據(jù)集中每兩個點之間的距離沃琅，在小型數(shù)據(jù)集上哗咆，brute-force很有競爭力，然而隨著樣本數(shù)的增長益眉，brute-force變得不可行晌柬。

KDTree

為了解決brute-force方法計算效率低下，發(fā)明了各種基于樹的數(shù)據(jù)結(jié)構(gòu)郭脂。一般情況下年碘，這些結(jié)構(gòu)通過有效編碼匯總樣本距離信息，來減少所需的距離計算量展鸡∮煨疲基本思想是，如果A離B比較遠莹弊，B 離C比較近涤久，所以A 離C比較遠，而不用明確計算忍弛。

構(gòu)建k-d樹（createKDTree）

輸入：數(shù)據(jù)點集Data-set和其所在的空間Range
輸出：Kd响迂，類型為k-d tree
1.If Data-set為空，則返回空的k-d tree
2.調(diào)用節(jié)點生成程序：
（1）確定split域：對于所有描述子數(shù)據(jù)（特征矢量）细疚，統(tǒng)計它們在每個維上的數(shù)據(jù)方差蔗彤。
以SURF特征為例，描述子為64維，可計算64個方差幕与。挑選出最大值挑势，對應(yīng)的維就是split域的值。
數(shù)據(jù)方差大表明沿該坐標軸方向上的數(shù)據(jù)分散得比較開啦鸣，在這個方向上進行數(shù)據(jù)分割有較好的分辨率潮饱；
（2）確定Node-data域：數(shù)據(jù)點集Data-set按其第split域的值排序。
位于正中間的那個數(shù)據(jù)點被選為Node-data诫给。此時新的Data-set' = Data-set\Node-data（除去其中Node-data這一點）香拉。
3.dataleft = {d屬于Data-set' && d[split] ≤ Node-data[split]}
Left_Range = {Range && dataleft} dataright = {d屬于Data-set' && d[split] > Node-data[split]}
Right_Range = {Range && dataright}
4.left = 由（dataleft，Left_Range）建立的k-d tree中狂，即遞歸調(diào)用createKDTree（dataleft凫碌，Left_
Range）。并設(shè)置left的parent域為Kd胃榕；
right = 由（dataright植袍，Right_Range）建立的k-d tree，即調(diào)用createKDTree（dataright赂鲤，Right_
Range）八拱。并設(shè)置right的parent域為Kd。

查找算法

從root節(jié)點開始楔壤，DFS搜索直到葉子節(jié)點鹤啡，同時在stack中順序存儲已經(jīng)訪問的節(jié)點。
如果搜索到葉子節(jié)點蹲嚣，當前的葉子節(jié)點被設(shè)為最近鄰節(jié)點递瑰。
然后通過stack回溯:
如果當前點的距離比最近鄰點距離近，更新最近鄰節(jié)點.
然后檢查以最近距離為半徑的圓是否和父節(jié)點的超平面相交.
如果相交隙畜，則必須到父節(jié)點的另外一側(cè)抖部，用同樣的DFS搜索法，開始檢查最近鄰節(jié)點议惰。
如果不相交您朽，則繼續(xù)往上回溯，而父節(jié)點的另一側(cè)子節(jié)點都被淘汰换淆，不再考慮的范圍中.
當搜索回到root節(jié)點時哗总，搜索完成，得到最近鄰節(jié)點倍试。

選擇方差最大的維度作為當前節(jié)點的劃分維度讯屈，方差越大，說明這個維度上的數(shù)據(jù)波動越大县习，也就說明了他們就越不可能屬于同一空間涮母，需要在這個維度上對數(shù)據(jù)點進行劃分谆趾。KDTree在維度小于20的情況下搜索是非常快的叛本。

BallTree

為了解決高維問題沪蓬，發(fā)明了BallTree。KDTree沿著笛卡爾軸劃分數(shù)據(jù)来候，BallTree使用超球面跷叉。雖然建立樹的成本大于KDTree，但是在高維數(shù)據(jù)上非常有效营搅。
BallTree 遞歸地將數(shù)據(jù)劃分成一個質(zhì)心C和半徑R定義的節(jié)點云挟，使得每個點位于由R和C定義的超球體內(nèi)。通過使用三角不等式減少搜索次數(shù)转质。
有了這個設(shè)置园欣，測試點和質(zhì)心之間的距離計算，已經(jīng)足夠確定測試點和這個節(jié)點內(nèi)所有點的距離的上界和下界休蟹。由于BallTree 節(jié)點的球形幾何形狀沸枯，它可以執(zhí)行高維的KD樹，但實際的性能是高度依賴于訓(xùn)練數(shù)據(jù)的結(jié)構(gòu)赂弓。

最近鄰算法選擇

選擇最佳算法依賴很多因素：

• 樣本數(shù)N和維度D
  1.Brute force 時間復(fù)雜度 O(D N)辉饱，
  2.BallTree 時間復(fù)雜度 O(D log(N)),
  3.KDTree，if D<20 拣展，O(D log(N))；else O(D N)缔逛。
  在樣本數(shù)小于30的情況下备埃，Brute force比BallTree和KDTree高效。
• 數(shù)據(jù)結(jié)構(gòu)
  數(shù)據(jù)內(nèi)在維度和數(shù)據(jù)稀疏性褐奴。數(shù)據(jù)內(nèi)在維度（秩）小于數(shù)據(jù)維度按脚，參數(shù)空間是存在線性或非線性關(guān)系。稀疏性指數(shù)據(jù)填充參數(shù)空間的程度（這與“稀疏”矩陣中的概念區(qū)別開來）敦冬。數(shù)據(jù)矩陣可能沒有零項辅搬，但結(jié)構(gòu)仍然可以是“稀疏”在這個意義上說。
  1.Brute force 與數(shù)據(jù)結(jié)構(gòu)無關(guān)脖旱。
  2 BallTree和KDTree在低內(nèi)在維度的稀疏數(shù)據(jù)上將很快堪遂。
• K值
  1.Brute force 不受影響，
  2 BallTree和KDTree 隨著K值的增大而變慢萌庆，首先溶褪，更大的K值導(dǎo)致需要搜索更大的參數(shù)空間，Second, using k > 1 requires internal queueing of results as the tree is traversed.
• 查詢數(shù)量
  BallTree和KDTree都需要一個創(chuàng)建過程践险，當有大量查詢時猿妈，創(chuàng)建的開銷可以忽略吹菱。如果只是少量的查詢，則Brute force 較好彭则。

葉子大小

Brute force 在小樣本上比樹結(jié)構(gòu)更高效鳍刷，這解釋了BallTree和KDTree 在葉子節(jié)點內(nèi)部轉(zhuǎn)換到Brute force 搜索。這種轉(zhuǎn)換可以通過參數(shù) leaf_size 設(shè)置俯抖，這個參數(shù)有很多影響：
創(chuàng)建時間：比較大的leaf_size 输瓜，創(chuàng)建比較快，因為需要創(chuàng)建的節(jié)點變少蚌成；
查詢時間：默認 leaf_size=30
內(nèi)存：隨著leaf_size 增加前痘，存儲一棵樹所需要的內(nèi)存是下降的，在BallTree中這非常重要担忧。BallTree 需要的內(nèi)存空間近似是訓(xùn)練數(shù)據(jù)規(guī)模的1/leaf_size芹缔。

Nearest Centroid Classifier

Approximate Nearest Neighbors

來源：http://scikit-learn.org/stable/modules/neighbors.html