原文章為scikit-learn中"用戶指南"-->"監(jiān)督學(xué)習(xí)的第六節(jié)：Nearest Neighbors"######

sklearn.neighbors
提供了一些在無(wú)監(jiān)督和有監(jiān)督學(xué)習(xí)中基于近鄰的學(xué)習(xí)方法。無(wú)監(jiān)督近鄰是許多其他學(xué)習(xí)方法的基石甚疟，特別是在流學(xué)習(xí)和光譜聚類方面仗岖。有監(jiān)督的基于近鄰的學(xué)習(xí)有兩個(gè)方面：對(duì)帶有離散標(biāo)簽的數(shù)據(jù)進(jìn)行分類 ，對(duì)帶有連續(xù)標(biāo)簽的數(shù)據(jù)計(jì)算回歸览妖。

最近鄰的原則上是先找出距離新點(diǎn)（預(yù)測(cè)點(diǎn)）最近的預(yù)定數(shù)量的訓(xùn)練樣本轧拄，繼而預(yù)測(cè)其所屬的標(biāo)簽。樣本數(shù)可以是用戶所定義的常數(shù)（此處即為K近鄰算法讽膏，KNN）檩电，或基于點(diǎn)的局部密度而變化的值（基于半徑的近鄰學(xué)習(xí)）。近鄰的距離通常是可以通過(guò)任何度量方式來(lái)測(cè)量：所以一般使用標(biāo)準(zhǔn)歐幾里得距離來(lái)判斷點(diǎn)與點(diǎn)的距離桅打。近鄰方式同樣以非泛化機(jī)器學(xué)習(xí)方式被人所知是嗜，因?yàn)樗鼤?huì)簡(jiǎn)單的“記住”了所有的訓(xùn)練數(shù)據(jù)（可能是被轉(zhuǎn)化成一種能夠快速索引的格式，例如 Ball Tree 或 KD Tree）挺尾。

盡管看起來(lái)他的實(shí)現(xiàn)原理看起來(lái)很簡(jiǎn)單，但是近鄰已經(jīng)成功的應(yīng)用在一些大規(guī)模的分類和回歸問(wèn)題上了站绪，例如手寫文字識(shí)別和衛(wèi)星圖像場(chǎng)景遭铺。因?yàn)樗且粋€(gè)無(wú)參數(shù)方法，所以通常能夠很成功地應(yīng)用在一個(gè)有無(wú)規(guī)則的決策邊界的分類問(wèn)題上恢准。

sklearn.neighbors
能夠同時(shí)接受** Numpy 數(shù)組或 scipy.sparse **矩陣作為輸入魂挂。對(duì)于密集矩陣同樣也支持其超大的可能距離度量。而對(duì)于稀疏矩陣則支持搜索任意的 Minkowski 度量馁筐。

這里有許多學(xué)習(xí)事務(wù)使用近鄰作為他們的計(jì)算核心涂召。一個(gè)例子是核密度估計(jì)，我們會(huì)在 密度估計(jì) 一節(jié)中來(lái)進(jìn)行討論敏沉。

1.6.1. 無(wú)監(jiān)督近鄰#

NearestNeighbors
實(shí)現(xiàn)了一個(gè)無(wú)監(jiān)督近鄰學(xué)習(xí)果正。它作為一個(gè)統(tǒng)一的接口應(yīng)用在了三種不同的近鄰算法中炎码，分別是：BallTree
，KDTree
和 sklearn.metrics.pairwise
中一個(gè)基于事務(wù)的brute方法秋泳×氏校可以通過(guò)關(guān)鍵字** algorithm 來(lái)選擇需要使用哪種近鄰搜索算法，可選值有： [‘a(chǎn)uto’, 'ball_tree', 'kd_tree', 'brute'] 迫皱。在輸入默認(rèn)值 'auto' **時(shí)歉闰，會(huì)自動(dòng)從這些算法中試圖找到對(duì)訓(xùn)練集最合適的算法。如果想要知道知道這些算法各自的長(zhǎng)短處的話卓起，可以查看這篇近鄰算法文章和敬。

警告：關(guān)于近鄰算法，如果兩個(gè)鄰居戏阅，k + 1** 和 ** k 擁有著相同的距離昼弟，但卻屬于不同的標(biāo)簽時(shí)，計(jì)算結(jié)果將根據(jù)訓(xùn)練數(shù)據(jù)的排序來(lái)決定饲握。

1.6.1.1. 尋找最近鄰##

對(duì)于在兩組數(shù)據(jù)之間尋找最近鄰的簡(jiǎn)單任務(wù)私杜， 可以使用 sklearn.neighbors
這一無(wú)監(jiān)督算法來(lái)完成：

>>> from sklearn.neighbors import NearestNeighbors
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)
>>> indices                                           
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)
>>> distances
array([[ 0.        ,  1.        ],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.41421356],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.41421356]])

所以查詢集跟訓(xùn)練集一樣，因?yàn)樽羁拷狞c(diǎn)就是他自身（距離為0）救欧。

另外還可以使用它來(lái)有效地產(chǎn)生表示相鄰點(diǎn)之間關(guān)系的稀疏圖：

>>> nbrs.kneighbors_graph(X).toarray()
array([[ 1.,  1.,  0.,  0.,  0.,  0.],
       [ 1.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  1.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  1.,  0.],
       [ 0.,  0.,  0.,  1.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  1.]])

因?yàn)槲覀兊臄?shù)據(jù)集是經(jīng)過(guò)結(jié)構(gòu)化了衰粹，所以使得數(shù)據(jù)點(diǎn)會(huì)順序排列在參數(shù)空間旁邊，得出K個(gè)鄰居的一個(gè)近似對(duì)角矩陣（也就是上方代碼塊所排列的矩陣笆怠，因?yàn)樽约号c自己必定"相鄰"铝耻，所以對(duì)角線是1）。這樣的稀疏圖在各種情況下都是很有用的蹬刷，能夠在無(wú)監(jiān)督學(xué)習(xí)的情況下利用各樣本點(diǎn)的空間關(guān)系：尤其是 sklearn.manifold.Isomap
瓢捉，sklearn.manifold.LocallyLinearEmbedding
和 sklearn.cluster.SpectralClustering
對(duì)這三個(gè)類來(lái)說(shuō)。

1.6.1.2. KD樹和Ball樹類##

另外一種尋找最近鄰的可選方式是使用 KDTree
或 BallTree
類办成。這些類是 NearestNeighbors
經(jīng)過(guò)包裝后生成的類泡态。Ball樹和KD樹都擁有著相同的接口（即有著相同的使用方式），以下方的KD樹為例：

>>> from sklearn.neighbors import KDTree
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> kdt = KDTree(X, leaf_size=30, metric='euclidean')
>>> kdt.query(X, k=2, return_distance=False)          
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)

可以在 KDTree
和 BallTree
的文檔里找到更多關(guān)于鄰居搜索的設(shè)置迂卢，包括如何規(guī)范化搜索策略某弦，各種距離度量的規(guī)范等等。對(duì)于所有可用的矩陣列表而克，可用查看 DistanceMetric
類的文檔靶壮。

1.6.2. 近鄰分類#

基于鄰居的分類是基于實(shí)例的學(xué)習(xí)或非泛化學(xué)習(xí)的一種：它不需要試圖去構(gòu)造一個(gè)通用的泛化模型，而是通過(guò)使用簡(jiǎn)單的儲(chǔ)存訓(xùn)練樣本的實(shí)例來(lái)進(jìn)行分類员萍。這種分類是遍歷每個(gè)樣本點(diǎn)腾降，然后對(duì)其的"最近鄰居"進(jìn)行簡(jiǎn)單的多數(shù)表決來(lái)進(jìn)行分類：查詢點(diǎn)通過(guò)與其最相鄰，最能代表它的點(diǎn)來(lái)分配它的所屬類碎绎。

scikit-learn 實(shí)現(xiàn)了兩種不同的近鄰分類器：

• KNeighborsClassifier
  實(shí)現(xiàn)了對(duì)每個(gè)查詢點(diǎn)的基于** K 近鄰算法螃壤，其中 K **為通過(guò)用戶輸入的整數(shù)抗果。
• RadiusNeighborsClassifier
  實(shí)現(xiàn)了一個(gè)基于每個(gè)訓(xùn)練點(diǎn)的固定半徑** r 內(nèi)的"鄰居"的數(shù)量的學(xué)習(xí)，其中 r **是用戶輸入的浮點(diǎn)數(shù)映穗。

KNeighborsClassifier
里的 **K 鄰分類是上述兩種技術(shù)中最常用的一個(gè)窖张。K 的最優(yōu)值是與數(shù)據(jù)高度依賴的：一般來(lái)說(shuō) K **值越大就越能夠降低噪音對(duì)模型的影響，但同樣也會(huì)使分類邊界變得不明顯蚁滋。

當(dāng)數(shù)據(jù)樣本不均勻時(shí)宿接，使用 RadiusNeighborsClassifier
中基于半徑的鄰居分類也許是一個(gè)比較好的選擇。用戶要指定一個(gè)固定的半徑值** r **辕录，這樣位于稀疏近鄰內(nèi)的樣本點(diǎn)會(huì)使用對(duì)應(yīng)的鄰居數(shù)量（應(yīng)該是根據(jù)半徑來(lái)搜索）來(lái)進(jìn)行分類睦霎。但是對(duì)高維參數(shù)空間來(lái)說(shuō)，因?yàn)榇嬖谒^的"維度災(zāi)難"（過(guò)多的特征導(dǎo)致分類的誤差增大）走诞，所以使用這一方式有可能會(huì)變使分類得低效副女。

基于近鄰分類的實(shí)現(xiàn)類在默認(rèn)情況下都有著一致的設(shè)置權(quán)重的方法：也就是說(shuō)分配到查詢點(diǎn)的值是只通過(guò)計(jì)算其附近鄰居點(diǎn)的多數(shù)表決（統(tǒng)計(jì)）來(lái)得到的。在某些情況下蚣旱，最好是通過(guò)對(duì)"鄰居"添加一個(gè)權(quán)重碑幅，使得越"近"的鄰居對(duì)擬合的貢獻(xiàn)更大。所以這一操作可以通過(guò)關(guān)鍵字** weight 來(lái)完成塞绿。一般情況下這個(gè)參數(shù)的默認(rèn)值是 uniform 沟涨，此時(shí)會(huì)使得所有"鄰居"都有相同的權(quán)重；而當(dāng)該參數(shù)設(shè)置為 distance **時(shí)异吻，權(quán)重值以取反比的方式裹赴，距離查詢點(diǎn)越進(jìn)的點(diǎn)權(quán)重越高。當(dāng)然也可以通過(guò)用戶自定義的權(quán)重來(lái)對(duì)“鄰居”進(jìn)行計(jì)算诀浪。

使用 'uniform' 權(quán)重設(shè)置的分類

使用 'distance' 權(quán)重設(shè)置的分類

示例

• 近鄰分類: 一個(gè)使用近鄰算法來(lái)進(jìn)行分類的例子棋返。

1.6.3. 近鄰回歸#

近鄰回歸能夠用在數(shù)據(jù)標(biāo)簽是連續(xù)的而不是離散變量的情況下。這種標(biāo)簽的分配方式為其值是根據(jù)查詢點(diǎn)的“鄰居”標(biāo)簽的平均數(shù)來(lái)決定的雷猪。

scikit-learn實(shí)現(xiàn)了兩種不同的近鄰回歸：

• KNeighborsRegressor
  實(shí)現(xiàn)了一個(gè)基于每個(gè)查詢點(diǎn)的** K 近鄰學(xué)習(xí)睛竣，其中 K **是通過(guò)用戶輸入的整數(shù)。
• RadiusNeighborsRegressor
  實(shí)現(xiàn)了一個(gè)基于查詢點(diǎn)在固定半徑** r 內(nèi)的近鄰學(xué)習(xí)求摇，其中 r **是一個(gè)用戶指定的浮點(diǎn)數(shù)酵颁。

基于近鄰回歸的實(shí)現(xiàn)類在默認(rèn)情況下都有著一致的設(shè)置權(quán)重的方法：對(duì)查詢點(diǎn)來(lái)說(shuō)，所有樣本點(diǎn)對(duì)他的貢獻(xiàn)度都是一致的月帝。在某些情況下，最好是通過(guò)對(duì)"鄰居"添加一個(gè)權(quán)重幽污，使得越"近"的鄰居對(duì)擬合的貢獻(xiàn)更大嚷辅。所以這一操作可以通過(guò)關(guān)鍵字** weight 來(lái)完成。一般情況下這個(gè)參數(shù)的默認(rèn)值是 uniform 距误，此時(shí)會(huì)使得所有"鄰居"都有相同的權(quán)重；而當(dāng)該參數(shù)設(shè)置為 distance **時(shí)，權(quán)重值以取反比的方式耘纱，距離查詢點(diǎn)越進(jìn)的點(diǎn)權(quán)重越高贷岸。當(dāng)然也可以通過(guò)用戶自定義的權(quán)重來(lái)對(duì)“鄰居”進(jìn)行計(jì)算。

有關(guān)多路輸出的近鄰回歸可以在 使用多路輸出估計(jì)器的臉部補(bǔ)全 這篇文章中找到其功能演示糊探。在這個(gè)例子中，輸入** X 是包括臉部的上半部分，輸出 Y **則是臉部的下半部分暇务。

例子

• 近鄰回歸: 一個(gè)使用近鄰回歸的例子。
• 使用多路輸出估計(jì)器的臉部補(bǔ)全: 一個(gè)使用多路輸出的近鄰回歸例子怔软。

1.6.4. 近鄰算法#

1.6.4.1. 暴力算法（BF）##

在機(jī)器學(xué)習(xí)中垦细，如何快速地計(jì)算近鄰一直都是一個(gè)很活躍的研究課題。最原始的近鄰搜索所涉及到的就是使用BF去計(jì)算數(shù)據(jù)集中的所有點(diǎn)對(duì)之間的距離：對(duì)于** D 維中的 N 個(gè)樣本挡逼，其規(guī)模有 O(D·N^2) 括改。高效的BF近鄰搜索對(duì)于小數(shù)量的數(shù)據(jù)樣本來(lái)說(shuō)還是很具有競(jìng)爭(zhēng)力的。但是隨著樣本數(shù)量 N 的贈(zèng)面積家坎，BF就會(huì)越來(lái)越快的變得不可行嘱能。在類 sklearn.neighbors
里，BF近鄰搜索可以通過(guò)設(shè)置關(guān)鍵字 algorithm='brute' **來(lái)實(shí)現(xiàn)虱疏，并且使用 sklearn.metrics.pairwise
中的事務(wù)來(lái)進(jìn)行計(jì)算惹骂。

1.6.4.2. K-D 樹##

為了解決BF在大規(guī)模數(shù)據(jù)下的低效的計(jì)算能力，已經(jīng)發(fā)明了各種基于樹的數(shù)據(jù)結(jié)構(gòu)订框。一般來(lái)說(shuō)析苫，這些結(jié)構(gòu)都通過(guò)其結(jié)構(gòu)來(lái)有效地編碼樣本的聚合距離的信息來(lái)試圖減少需要計(jì)算的距離數(shù)量。其基本思想是穿扳，如果一個(gè)樣本點(diǎn)** A 對(duì)另一個(gè)樣本點(diǎn) B 的距離很遙遠(yuǎn)衩侥，但是樣本點(diǎn) B 的又很靠近點(diǎn) C ，因此我們可以知道點(diǎn) A 同樣距離點(diǎn) C 很遙遠(yuǎn)矛物，而這樣就不需要再額外計(jì)算他們的距離茫死。所以使用這種方式后，近鄰的計(jì)算成本就減少為 O[D·N·log(N)] 或更好履羞。這在大規(guī)模 N **的情況下比BF有著更顯著的效果峦萎。

KD樹（K維樹的簡(jiǎn)稱）數(shù)據(jù)結(jié)構(gòu)則是一種應(yīng)用了這種綜合信息的早期方法，其使用生成二維的四叉樹和三維的八叉樹來(lái)匹配任意維度的數(shù)據(jù)忆首。KD樹是一種二叉樹結(jié)構(gòu)爱榔，其沿著數(shù)據(jù)的軸遞歸地分割參數(shù)空間，然后再將其分配到原來(lái)的區(qū)域內(nèi)糙及，最后再填充數(shù)據(jù)點(diǎn)详幽。KD樹的構(gòu)建過(guò)程是非常快的：因?yàn)橹粫?huì)沿著數(shù)據(jù)軸來(lái)進(jìn)行分區(qū)，不需要計(jì)算** D 維的距離唇聘。一旦構(gòu)建完成后版姑，查詢點(diǎn)的近鄰只需要計(jì)算 O[Log(N)] 的距離就足夠了。因?yàn)镵D樹在低維度（ D < 20迟郎，但是這里的低維度相對(duì)于BF而言是高維度的）下的近鄰搜索非嘲眨快，但還是會(huì)因?yàn)?/strong> D 的增加而該搜索過(guò)程會(huì)變得不怎么有效率宪肖。造成這個(gè)原因的同樣也是因?yàn)?維度災(zāi)難"的存在表制。在scikit-learn里，KD樹近鄰搜索可以通過(guò)關(guān)鍵字 algorithm 將其設(shè)置為 td_tree **來(lái)使用匈庭，這會(huì)使得計(jì)算過(guò)程是通過(guò) KDTree
類來(lái)完成夫凸。

引用

• “Multidimensional binary search trees used for associative searching”, Bentley, J.L., Communications of the ACM (1975)

1.6.4.3. Ball樹##

同樣為了解決KD樹在高維度下的低效能，ball樹數(shù)據(jù)結(jié)構(gòu)被發(fā)明了出來(lái)阱持。相對(duì)于KD樹的分區(qū)是沿著笛卡爾軸來(lái)進(jìn)行分割夭拌，Ball樹則是將數(shù)據(jù)分割成一系列的超球體。當(dāng)然這會(huì)使得Ball樹的開銷比KD樹要打衷咽，但是卻獲得了一種對(duì)高度數(shù)據(jù)化的數(shù)據(jù)仍然具有高效的數(shù)據(jù)結(jié)構(gòu)鸽扁，即使是用于處理?yè)碛懈呔S的數(shù)據(jù)也不例外。

Ball樹的遞歸分割是通過(guò)定義一個(gè)質(zhì)心** C （如果不知道什么是質(zhì)心镶骗，可以查看該網(wǎng)址的Q1）和半徑 r 桶现，使得節(jié)點(diǎn)中的每個(gè)點(diǎn)都位于由 r 和 C 定義的超球體內(nèi)。然后使用三角不等式**來(lái)減少用于鄰居搜索的候選點(diǎn)的數(shù)量：

這樣測(cè)試點(diǎn)到質(zhì)心的距離就足以用來(lái)決定該測(cè)試點(diǎn)與其近鄰距離的上下限鼎姊。因?yàn)锽all樹的節(jié)點(diǎn)就是球形的幾何骡和，所以它能夠在高維上執(zhí)行KD樹，雖然實(shí)際性能是高度依賴于訓(xùn)練數(shù)據(jù)的結(jié)構(gòu)相寇。在scikit-learn慰于，可以通過(guò)使用設(shè)置關(guān)鍵字** algorithm 為 ball_tree **來(lái)使用基于Ball樹的近鄰搜索，且它是通過(guò) sklearn.neighbors.BallTree
類來(lái)進(jìn)行計(jì)算的唤衫。不過(guò)用戶也可以直接使用 BallTree
類來(lái)進(jìn)行計(jì)算婆赠。

引用

• “Five balltree construction algorithms”, Omohundro, S.M., International Computer Science Institute Technical Report (1989)

1.6.4.4. 近鄰算法的選擇##

對(duì)給定的數(shù)據(jù)集選擇一個(gè)的最佳算法是一個(gè)很復(fù)雜的過(guò)程，要考慮的因素有多個(gè)：

• 樣本的數(shù)量** N （即 n_samples）和維度 D （即n_features **）
• BF查詢時(shí)間的增長(zhǎng)為** O[D·N]**
• Ball樹查詢時(shí)間的增長(zhǎng)近似為** O[D·log(N)] **
• KD樹查詢時(shí)間以一種難以表達(dá)的方式進(jìn)行改變：
• D <= 20 左右 時(shí)佳励，近似于 O[D·log(N)]
• D > 20時(shí)休里，可能接近于** O[D·N] **或者是更糟。

對(duì)小數(shù)據(jù)集（N <= 30 左右）赃承，**log(N) 與 N 相當(dāng)妙黍，并且此時(shí)的BF比基于樹的搜索更具效率。為了應(yīng)對(duì)這種情況瞧剖，KDTree和BallTree都通過(guò)提供參數(shù) 葉子大小 **來(lái)解決這個(gè)問(wèn)題：這個(gè)參數(shù)能夠控制在處理多少樣本數(shù)時(shí)切換算法到BF废境。這樣處理的話允許每一個(gè)算法都能夠在小數(shù)據(jù)集上獲得BF的高效率。

• 數(shù)據(jù)的結(jié)構(gòu)：數(shù)據(jù)的內(nèi)在維度與其稀疏性。內(nèi)在維度是指數(shù)據(jù)的流形維度（d <= D）噩凹，其可以以線性或者非線性的形式來(lái)嵌入?yún)?shù)空間中。稀疏性是指數(shù)據(jù)在參數(shù)空間的填充程度（這將與在“稀疏”矩陣中使用的概念不同毡咏。數(shù)據(jù)上的矩陣可能不是零驮宴，但是他在** 結(jié)構(gòu) **上也是有可能“稀疏”的）
  • BF的查詢時(shí)間跟數(shù)據(jù)的結(jié)構(gòu)無(wú)關(guān)。
  • Ball樹和KD樹的查詢時(shí)間跟數(shù)據(jù)的結(jié)構(gòu)有很大的關(guān)系呕缭。一般來(lái)說(shuō)堵泽，有較小的內(nèi)在維度的稀疏數(shù)據(jù)能夠使用很少的處理時(shí)間，因?yàn)镵D樹的內(nèi)部是與參數(shù)軸對(duì)其的恢总，他一般不會(huì)在對(duì)有任意結(jié)構(gòu)的數(shù)據(jù)上迎罗，像Ball樹那樣有著太多的性能提升。

因?yàn)橛糜跈C(jī)器學(xué)習(xí)的數(shù)據(jù)集一般是高度結(jié)構(gòu)化的片仿，所以很適合使用基于樹的算法來(lái)進(jìn)行查詢搜索纹安。

• 查詢點(diǎn)所需要的近鄰數(shù)量** K**：
• **K **的值不會(huì)影響B(tài)F的查詢時(shí)間。
• 當(dāng)** K 值增加時(shí)砂豌，Ball樹和KD樹的查詢時(shí)間會(huì)變得越來(lái)越慢厢岂。這是因?yàn)閮煞矫娴脑颍旱谝唬酱蟮?/strong> K 值會(huì)導(dǎo)致需要在參數(shù)空間搜索的部分變大阳距。第二塔粒，對(duì)K > 1**的情況下，需要對(duì)結(jié)果遍歷排序成樹筐摘。

當(dāng)** K 變得比 N **還要大時(shí)卒茬，修建基于查詢結(jié)果所生成的樹的能力會(huì)降低。在這種情況下咖熟，BF查詢可能會(huì)更有效圃酵。

• 查詢點(diǎn)的數(shù)量。Ball樹和KD樹同樣需要一個(gè)構(gòu)造階段球恤。但是在面對(duì)分?jǐn)偛樵兯牡臅r(shí)間上辜昵，在構(gòu)造時(shí)所消耗的時(shí)間對(duì)此相比也不多了。如果只是進(jìn)行少量的查詢的話咽斧，那么構(gòu)造的時(shí)間就會(huì)在總體時(shí)間內(nèi)占據(jù)很大的比例了堪置。如果只需要查詢少量的幾個(gè)點(diǎn)的話（即查詢點(diǎn)旁邊的點(diǎn)的數(shù)量確實(shí)不怎么多），此時(shí)BF比所有基于樹的算法要好张惹。
  基于這些情況舀锨，在** algorithm='auto' 的情況下，如果 K < N / 2 且 'effective_metric_' 存在于 'kd_tree' 中的 'VALID_METRICS' 列表宛逗，則會(huì)自動(dòng)設(shè)置成 kd_tree 坎匿。如果 K < N / 2 且 'effective_metric_' 不存在于 'kd_tree' 中的 'VALID_METRICS' 列表，則會(huì)自動(dòng)設(shè)置成 ball_tree。如果 K >= N / 2 且查詢的點(diǎn)數(shù)量至少與訓(xùn)練點(diǎn)的數(shù)量相同替蔬，并且 leaf_size 接近默認(rèn)值 30 時(shí)告私，則會(huì)設(shè)置為 'brute' **。

1.6.4.5 **leaf_size **的影響##

綜上所述承桥，對(duì)于小的樣本數(shù)來(lái)說(shuō)驻粟，BF比其他基于樹的算法要更有效率⌒滓欤基于這個(gè)現(xiàn)狀可以通過(guò)在Ball樹或KD樹的葉子節(jié)點(diǎn)數(shù)量來(lái)從內(nèi)部切換搜索算法到BF蜀撑。可以通過(guò)設(shè)置** leaf_size **參數(shù)來(lái)切換的標(biāo)準(zhǔn)剩彬。這個(gè)參數(shù)的取值會(huì)導(dǎo)致以下幾種影響：

• 構(gòu)造時(shí)間
  越大的** leaf_size **會(huì)有更快的構(gòu)造時(shí)間酷麦，因?yàn)檫@樣只需要?jiǎng)?chuàng)建更少的節(jié)點(diǎn)。
• 查詢時(shí)間
  對(duì)很大或很小的** leaf_size 都會(huì)獲得一個(gè)次優(yōu)的查詢成本喉恋。對(duì)于 leaf_size 接近1的情況沃饶，遍歷所有節(jié)點(diǎn)所需的開銷會(huì)顯著的減慢查詢所需的時(shí)間。對(duì) leaf_size 接近訓(xùn)練集的數(shù)目時(shí)瀑晒，就基本上是直接使用BF了绍坝。一個(gè)比較好的妥協(xié)方法是將其設(shè)置為 30，并且這也是 leaf_size **的默認(rèn)值苔悦。
• 內(nèi)存
  隨著** leaf_size 增加轩褐，需要用來(lái)儲(chǔ)存樹結(jié)構(gòu)的內(nèi)存也會(huì)下降。這一點(diǎn)對(duì)Ball樹來(lái)說(shuō)尤其重要玖详，因?yàn)锽all樹的每一個(gè)節(jié)點(diǎn)都是存放有一個(gè) D 維的質(zhì)心球體把介。BallTree
  所需要的內(nèi)存近似為訓(xùn)練集大小的 1 / leaf_size **倍。

**leaf_size **不會(huì)在BF查詢里使用蟋座。

1.6.5. 最近鄰質(zhì)心分類器#

NearestCentroid
分類器是一個(gè)用其成員的質(zhì)心來(lái)代表每一類的簡(jiǎn)單的算法的實(shí)現(xiàn)拗踢。但是在實(shí)際上，這個(gè)操作類似于** sklearn.KMeans **算法的標(biāo)簽更新階段向臀。同樣這個(gè)算法因?yàn)椴恍枰x擇參數(shù)這一點(diǎn)巢墅，使得它同樣也是一個(gè)良好的基準(zhǔn)分類器。當(dāng)類之間有著太大的方差就好收到非凸類的影響券膀，因?yàn)樵诩僭O(shè)的情況下君纫，在所有維度中的方差都是相等的。對(duì)于沒有做這個(gè)假設(shè)的更復(fù)雜的方法芹彬，可以查看 線性判別法 和 二次判別分析法
蓄髓。以下是使用默認(rèn)的 NearestCentroid
例子：

>>> from sklearn.neighbors.nearest_centroid import NearestCentroid
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> y = np.array([1, 1, 1, 2, 2, 2])
>>> clf = NearestCentroid()
>>> clf.fit(X, y)
NearestCentroid(metric='euclidean', shrink_threshold=None)
>>> print(clf.predict([[-0.8, -1]]))
[1]

1.6.5.1. 最近收縮質(zhì)心##

NearestCentroid
分類器擁有一個(gè)** shrink_threshold 參數(shù)，其實(shí)現(xiàn)了一個(gè)最近收縮質(zhì)心分類器舒帮。實(shí)際上每個(gè)質(zhì)心的每個(gè)特征值被其類內(nèi)的特征方差所劃分会喝。然后特征值就會(huì)根據(jù) shrink_threshold **的值來(lái)減少陡叠。最顯著的是如果一個(gè)特定的特征值越過(guò)0值，那么其值會(huì)被設(shè)置為0肢执。實(shí)際上這操作直接消除了毫無(wú)作用的特征枉阵。因此這可以用來(lái)去除無(wú)用的噪音特征。

在線的路子蔚万，使用一個(gè)較小的收縮閾值將模型的準(zhǔn)確度從0.81增加到0.82.

示例

• 近鄰質(zhì)心分類: 一個(gè)使用了擁有不同收縮閾值的近鄰質(zhì)分類的例子岭妖。

1.6.6. 近似最近鄰#

在處理低維度** d （值近似50）的問(wèn)題上，有許多高效且精確的近鄰搜索算法可以使用反璃。但是這些算法都存在當(dāng) d **增加時(shí)，相對(duì)的占用空間和查詢時(shí)間都會(huì)增加假夺。在高維空間中淮蜈，這些算法跟遍歷數(shù)據(jù)集中查詢點(diǎn)旁的所有點(diǎn)的算法（也就是 BF了）并沒有什么優(yōu)越的地方。造成這一點(diǎn)的原因自然是“維度災(zāi)難”這一現(xiàn)象了已卷。

對(duì)一些應(yīng)用來(lái)說(shuō)其并不需要獲得有多精確的近鄰梧田，相反他只需要做出一個(gè)“合格的猜測(cè)”就足夠了。當(dāng)預(yù)測(cè)結(jié)果不需要太過(guò)于精確時(shí)侧蘸，LSHForest
類實(shí)現(xiàn)了一個(gè)近似近鄰搜索裁眯。近似近鄰搜索是設(shè)計(jì)來(lái)試圖加速在高維數(shù)據(jù)中的查詢速度。這項(xiàng)技術(shù)在表現(xiàn)"鄰里關(guān)系"讳癌，而不是需要精確的結(jié)果（例如K近鄰分類與回歸）時(shí)十分有用穿稳。一些受歡迎的近似近鄰搜索技術(shù)都是局部敏感哈希，即一種基于best bin first（BBF）和Balanced box-decomposition tree的搜索技術(shù)晌坤。

1.6.6.1. 局部敏感哈希樹##

局部敏感哈希的Vanilla實(shí)現(xiàn)擁有一個(gè)在實(shí)踐中難以調(diào)整的超參數(shù)逢艘，因此scikit-learn實(shí)現(xiàn)了一種叫 LSHForest
的變體算法，其擁有較多的合理超參數(shù)骤菠。這兩種方式都是用了內(nèi)部隨機(jī)超平面去把樣本索引成"桶"它改，并且只計(jì)算樣本的實(shí)際的余弦相似性，以此來(lái)對(duì)查詢結(jié)果進(jìn)行碰撞以實(shí)現(xiàn)一個(gè)子線性的對(duì)樣本縮放（詳細(xì)情況可以查看局部敏感哈希的數(shù)學(xué)描述）商乎。

LSHForest
有兩個(gè)主要的超參數(shù)：**n_estimators 和 n_candidates **央拖。可以通過(guò)下圖來(lái)證明這些參數(shù)能夠用來(lái)控制查詢的準(zhǔn)確度：

根據(jù)經(jīng)驗(yàn)來(lái)看鹉戚，一個(gè)用戶可以通過(guò)設(shè)置** n_estimators 為一個(gè)足夠大的值（例如10到50之間）鲜戒，然后在查詢時(shí)間來(lái)調(diào)整 n_candidates **的值以平衡準(zhǔn)確度。

對(duì)小數(shù)據(jù)集來(lái)說(shuō)崩瓤，BF仍舊要比LSH樹要快袍啡。但是LSH樹可以通過(guò)索引的大小來(lái)?yè)碛幸粋€(gè)可收縮的子線性的查詢時(shí)間。LSH樹與BF的性能平衡點(diǎn)取決于數(shù)據(jù)集的維度結(jié)構(gòu)境输，所需的精度，運(yùn)行環(huán)境的差別嗅剖，例如BLAS優(yōu)化的可用性，CPU的性能及其緩存信粮。

在固定的 LSHForest
參數(shù)下强缘，隨著數(shù)據(jù)集的增加，查詢結(jié)果的準(zhǔn)確度傾向于緩慢下降旅掂。上述圖表中的錯(cuò)誤條代表在不同查詢情況下的標(biāo)準(zhǔn)差。

示例

• 近似最近鄰的超參數(shù): 一個(gè)使用LSH樹的近似最近鄰搜索的超參數(shù)的行為例子觉阅。
• 近似最近鄰的可擴(kuò)展性: 一個(gè)使用LSH數(shù)的近似最近鄰的可伸縮性的例子秘车。

1.6.6.2. 局部敏感哈希的數(shù)學(xué)描述##

局部敏感哈希（LSH）技術(shù)能夠使用在很多領(lǐng)域上典勇，其中最多的是用在高維中來(lái)執(zhí)行近鄰搜索。LSH背后的主要概念是使用多個(gè)（通常是簡(jiǎn)單的）哈希函數(shù)來(lái)哈希數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)叮趴，將其形成一個(gè)索引列表割笙。對(duì)于哈希碰撞的可能性，當(dāng)兩個(gè)對(duì)象有相似的索引時(shí)疫向，彼此距離相近的兩個(gè)節(jié)點(diǎn)比起其他點(diǎn)而言產(chǎn)生碰撞的概率要高得多咳蔚。散列函數(shù)族對(duì)局部敏感的要求如下。

從一個(gè)域** S 到另一個(gè)范圍 U 的一系列函數(shù)族 H 被稱為（r, e, p1, p2）-敏感搔驼，其中 r, e > 0, p1 > p2 > 0 谈火，如果對(duì)任意 p, q ∈ S ，都滿足以下條件（D **是距離函數(shù)）：

• 如果** D(p, q) <= r 舌涨，且 P[h(p) = h(q)] >= p1**糯耍。
• 如果** D(p, q) < r(1 + e) ，且 P[h(p) = h(q)] >= p1**囊嘉。

跟定義的一樣温技，距離為** r 之內(nèi)的點(diǎn)很容易以 p1 的概率發(fā)生碰撞。相反扭粱，距離大于 r(1 + e) 的點(diǎn)則是會(huì)以以 p2 的小概率發(fā)生碰撞舵鳞。
假設(shè)這里有一個(gè)LSH的函數(shù)族 H**。LSH索引的建立如下：

1. 從** H 中隨機(jī)均勻選擇出 k 個(gè)函數(shù)（h1, h2, ..., hk）琢蛤。對(duì)任意的 p ∈ S 抛虏，使用標(biāo)簽 g(p) = (h1(p), h2(p), ..., hk(p)) 來(lái)替換掉原來(lái)的 p。如果每個(gè) hi 輸出一位數(shù)字套才，可以觀察到每個(gè)桶都會(huì)有 k **位數(shù)字的標(biāo)簽迂猴。
2. 然后再獨(dú)立執(zhí)行步驟1，ι次去構(gòu)造出ι個(gè)分別具有** g1, g2, ..., gl **哈希函數(shù)的估量器背伴。

在步驟1中使用連續(xù)的哈希函數(shù)的原因是盡可能地減少于遠(yuǎn)處節(jié)點(diǎn)的碰撞概率。然后碰撞的概率從** p2 降低到 p2^k息尺，并且是對(duì)于 k 來(lái)說(shuō)是可以忽略的小數(shù)掷倔。k 值的選擇強(qiáng)烈取決于數(shù)據(jù)集的大小和結(jié)構(gòu)，因此在數(shù)據(jù)集中很難以對(duì) k 調(diào)參巴柿。對(duì)較大的 k **值來(lái)說(shuō)還有一個(gè)副作用就是：它有可能會(huì)降低臨近點(diǎn)發(fā)生碰撞的幾率广恢。為了解決這個(gè)問(wèn)題钉迷，所以就在步驟2中構(gòu)造了多個(gè)估量器糠聪。

因?yàn)樾枰獙?duì)給定的數(shù)據(jù)集的** k **進(jìn)行調(diào)參舰蟆，所以在實(shí)踐中很難應(yīng)用經(jīng)典的LSH算法身害。所以就有一種設(shè)計(jì)來(lái)緩解這個(gè)問(wèn)題的LSH樹的變種塌鸯，其通過(guò)自動(dòng)地調(diào)整哈希樣本所需的位數(shù)來(lái)解決這個(gè)問(wèn)題丙猬。

LSH樹是由前綴樹形成的，樹的每個(gè)葉子節(jié)點(diǎn)代表著數(shù)據(jù)庫(kù)中實(shí)際的數(shù)據(jù)點(diǎn)咐低。使用** ι 個(gè)這樣樹組成樹林见擦，然后再使用從 H 中隨機(jī)抽取的哈希函數(shù)來(lái)獨(dú)立地構(gòu)造他們鲤屡。在這個(gè)實(shí)例中使用了隨機(jī)投影**作為L(zhǎng)SH的技術(shù)酒来，其為余弦距離的近似值堰汉。哈希函數(shù)序列的長(zhǎng)度被固定為32翘鸭。此外還使用了已排序的數(shù)組和折半搜索實(shí)現(xiàn)了一個(gè)前綴樹就乓。

為了找出查詢點(diǎn)** q 的 m 個(gè)臨近點(diǎn)，需要使用樹的兩個(gè)遍歷階段戏自。首先浦妄，從一個(gè)自頂向下的遍歷來(lái)用折半搜索找出經(jīng)過(guò)哈希函數(shù)處理過(guò)后的 q 標(biāo)簽的最長(zhǎng)前綴（最大深度）葉子剂娄。然后從森林中提取出M 遠(yuǎn)大于 m的節(jié)點(diǎn)（候選集）阅懦，然后再自底向上的遍歷中同步地將找到的節(jié)點(diǎn)向根部移動(dòng)耳胎。其中 M 是設(shè)置為 c·l，其中 c 是從樹中提取出的候選集的常數(shù)數(shù)量淹魄。最后這些 M 個(gè)點(diǎn)各自對(duì) q 點(diǎn)的相似度甲锡，然后返回前 m 個(gè)最相似的點(diǎn)作為 q 點(diǎn)的近鄰缤沦。由于在查詢近鄰的過(guò)程中缸废，大部分的時(shí)間都是花費(fèi)在計(jì)算點(diǎn)之間的距離企量，所以這個(gè)方法比起B(yǎng)F搜索要快 N / M 左右梁钾，其中 N **是數(shù)據(jù)集中的數(shù)量。

引用

• “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions”, Alexandr, A., Indyk, P., Foundations of Computer Science, 2006. FOCS ‘06. 47th Annual IEEE Symposium
• “LSH Forest: Self-Tuning Indexes for Similarity Search”, Bawa, M., Condie, T., Ganesan, P., WWW ‘05 Proceedings of the 14th international conference on World Wide Web Pages 651-660

---

（在嘗試翻譯這篇文檔的時(shí)候難免會(huì)因?yàn)楦鞣N問(wèn)題而出現(xiàn)錯(cuò)翻冒嫡，如果發(fā)現(xiàn)的話孝凌，煩請(qǐng)指出蟀架，謝謝> <）