1.6 最近鄰?

sklearn.neighbors提供了基于近鄰的無監督和有監督的學習方法的功能。無監督最近鄰是許多其他學習方法的基礎，特別是流形學習(manifold learning)和光譜聚類(spectral clustering)。有監督的 neighbors-based (基于鄰居的) 學習有兩種方式：離散標簽數據的分類和連續標簽數據的回歸。

最近鄰方法背后的原理是找到在距離上離新樣本最近的一些樣本， 并且從這些樣本中預測標簽。最近鄰的樣本數可以是用戶定義的常數(k-最近鄰)，也可以根據不同的點的局部密度(基于半徑的近鄰學習)確定。一般來說，距離可以用任意來度量：標準的歐氏距離是最常見的選擇。基于鄰居的方法被稱為非泛化機器學習方法，因為它們只是“記住”它的所有訓練數據(可能轉換成一個快速的索引結構，比如Ball樹或KD樹)。

盡管它很簡單，但最近鄰已經成功地解決了大量的分類和回歸問題，包括手寫數字和衛星圖像等場景。作為一種非參數方法，在決策邊界非常不規則的情況下通常是成功的。

sklearn.neighbors 中的類輸入不管是numpy中的array數組， 還是scipy.sparse矩陣都可以處理。對于密集矩陣，可以支持大量的距離度量。于稀疏矩陣，支持任意的Minkowski度量進行搜索。

有許多學習規則都是依賴于它們的核心近鄰。一個例子是核密度估計( kernel density estimation,)，在密度估計( density estimation)部分討論。

1.6.1.無監督最近鄰

NearestNeighbors實現了無監督的最近鄰學習。它充當三個不同的最近鄰算法的統一接口：BallTree和KDTree和一個基于sklearn.emeics.pair中規則的暴力算法。最近鄰搜索算法的選擇是通過關鍵字algorithm來控制的, 其選擇必須是['auto', 'ball_tree', 'kd_tree', 'brute']中的一個。當傳遞默認值‘auto’時，該算法嘗試從訓練數據中自動查出最佳的方法。有關每個選項的優缺點的討論，請參見Nearest Neighbor Algorithms。

1.6.1.1 找到最近鄰

對于在兩組數據之間尋找最近鄰的簡單任務，可以使用sklearn.neighbors中的無監督算法：

>>> 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]])

因為查詢集與訓練集匹配，所以每個點的最近鄰居就是該點本身，距離為零。

還可以有效地生成表示相鄰點之間的連接的稀疏圖：

>>> 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.]])

1.6.1.2 KDTree和BallTree類

或者，可以直接使用KDTree或BallTree類來查找最近的鄰居。這是上文使用過的NearestNeighbors類包裝的功能， Ball Tree和KD Tree具有相同的接口；我們將在這里展示使用KD Tree的示例：

>>> 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類文檔，包括查詢策略規范、距離度量等。有關可用度量的列表，請參見DistanceMetric 類的文檔。

1.6.2 最近鄰分類

基于近鄰的分類是一種基于實例的學習或非泛化學習：它不是試圖構造一個通用的內部模型，而是簡單地存儲訓練數據的實例。分類是由每個點的最近鄰的簡單多數投票中計算得到的：一個查詢點被標記的數據標簽是由它最近鄰點中最具代表性的數據標簽來決定的。

scikit-learn實現了兩個不同的最近鄰分類器： KNeighborsClassifier 分類器根據每個查詢點的k個最近鄰實現學習，其中k是用戶指定的整數值。 RadiusNeighborsClassifier分類器根據每個訓練點的固定半徑內的鄰居數實現學習，其中 是用戶指定的浮點值。

KNeighborsClassifier 中的K近鄰分類是最常用的分類方法。k值的最佳選擇是高度依賴于數據的：一般來說，較大的 會抑制噪聲的影響，但使分類邊界不那么清晰。

在數據不均勻采樣的情況下， RadiusNeighborsClassifier中基于半徑的近鄰分類是更好的選擇。用戶指定一個固定的半徑，以便在稀疏的鄰居中使用更少的最近鄰居來進行分類。對于高維參數空間，這種方法由于所謂的 “維度災難” 而變得不那么有效。

基本的最近鄰分類使用一樣的權重：也就是說，分配給查詢點的值是根據最近鄰居的簡單多數投票計算的。在某些情況下，最好是對鄰居進行加權，這樣更靠近的鄰居對擬合來說貢獻更大。這可以通過weights關鍵字來實現。默認值是weights=“uniform”，為每個鄰居分配同樣的權重。weights = 'distance'分配的權重與到查詢點的距離成反比。或者，可以提供用戶定義的距離函數來計算權重.

1.6.3 最近鄰回歸

如果數據標簽是連續的，而不是離散的變量，則可以使用基于鄰居的回歸。分配給查詢點的標簽是根據其最近鄰居的標簽的平均值計算的。

scikit-learn實現了兩個不同的近鄰回歸器：KNeighborsRegressor實現基于每個查詢點的k個最近鄰的學習，其中k是用戶指定的整數值。 RadiusNeighborsRegressor實現了基于查詢點的固定半徑r內的近鄰的學習，其中r是用戶指定的浮點數值。

最基本的最近鄰回歸使用的是一樣的權重：即，局部鄰域中的每個點對查詢點的分類都有一樣的貢獻。在某些情況下，它可以是有利的，即距離更近的點對回歸的貢獻要大于更遠的點。這可以通過weights關鍵字來實現。默認值是weights = 'uniform'，為所有點分配一樣的權重。 weights = 'distance'分配權重與到查詢點的距離成反比。或者，可以提供用戶定義的距離函數，該函數將用于計算權重。

在 基于多輸出估計的人臉繪制中演示了多輸出最近鄰回歸的使用。在這個示例中，輸入 X 是臉上半部分像素，輸出 Y 是臉下半部分像素。

1.6.4.最近鄰算法

1.6.4.1 暴力計算

最近鄰的快速計算是機器學習中一個活躍的研究領域。最樸素的近鄰搜索的實現涉及到數據集中所有成對點之間距離的暴力計算：對于維中的個樣本來說，這種方法的復雜度為。高效的暴力近鄰搜索對于小數據樣本來說是非常有競爭力的。然而，隨著樣本的增加，暴力法很快就變得不可行了。在類sklearn.neighbors中，暴力近鄰搜索是使用關鍵字algorithm = 'brute'指定的，并使用 sklearn.metrics.pairwise中可用的程序來計算。

1.6.4.2 K-D樹

為了解決暴力法計算效率低下的問題，人們發明了多種基于樹的數據結構。通常，這些結構試圖通過有效編碼樣本的聚合距離(aggregate distance)信息來減少所需的距離計算量。基本思想是，如果點離點很遠，點離點很近，那么我們就知道點和是很遠的，不需要顯式地計算它們的距離。這樣，最近鄰搜索的計算成本可以降低到或更好。這是一個在大型的數據集上超越暴力法的重要實現。

利用這些聚合信息的早期方法是KD樹數據結構(K-dimensional tree的縮寫)，它將二維Quad-trees和三維Oct-trees推廣到任意維數。KD樹是一種二叉樹結構，它遞歸地沿數據軸劃分參數空間，將其劃分為嵌套的正交異性區域，然后將數據點放入其中。KD樹的構造非常快：因為分區只沿數據軸執行，所以不需要計算維距離。一旦構造，僅通過復雜度為的距離計算就可以確定查詢點的最近鄰居。雖然KD樹方法對于低維()鄰域搜索非常快速，但隨著增大，它變得效率低下：這是所謂的“維度詛咒”的一種表現。在scikit-learn中，KD樹近鄰搜索使用關鍵字algorithm = 'kd_tree'指定，并使用 KDTree類進行計算。

參考

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

1.6.4.3 Ball樹

針對KD樹高維度下效率低的問題，提出了球狀樹的數據結構。其中KD樹沿著笛卡爾軸劃分數據，球樹在一系列嵌套超球(hyper-spheres)中劃分數據。這使得樹的構建比KD樹的代價更高，但是導致了一種對高度結構化非常有效的數據結構，即使在非常高的維度上也是如此。

球樹遞歸地將數據劃分為由質心和半徑定義的節點，這樣節點中的每個點都位于和定義的超球面內，通過使用三角不等式減少了鄰居搜索的候選點數：

使用此設置，測試點和質心之間的單個距離計算就足以確定節點內所有點之間距離的上下界。由于球狀樹節點的球形幾何特性，雖然實際性能與訓練數據的結構有很大的關系，但它可以在高維上表現出一棵KD樹。在scikit-learn中，基于球樹的鄰居搜索是使用關鍵字algorithm = 'ball_tree'指定的，并且是使用類 sklearn.neighbors.BallTree計算的。或者，用戶可以直接使用 BallTree 類。

參考文獻

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

1.6.4.4 最近鄰算法的選擇

給定數據集的優化算法是一個復雜的選擇，取決于以下幾個因素：

• 樣本數(即n_samples)和維數(即n_features)。

  • Brute force查詢的時間以增長
  • Ball tree查詢時間以增長
  • KD樹查詢時間隨變化，難以精確描述。對于較小的(小于20)，代價約為?，KD樹查詢效率很高。對于較大的，成本增加到接近，而樹結構造成的開銷可能導致比暴力更慢的查詢。

  對于小數據集(小于30)，可與相比較，而蠻力算法比基于樹的方法更有效。 KDTree 和 BallTree都通過提供一個leaf size參數來解決這個問題：這控制了查詢切換到暴力的樣本數。這使得這兩種算法都能接近小樣本的暴力計算的效率。

• 數據結構：數據的 intrinsic dimensionality(本征維數) 和/或數據的 sparsity (稀疏度)。本征維數是指數據所在的流形的維數，它可以線性嵌入參數空間，也可以非線性嵌入參數空間。稀疏性是指數據填充參數空間的程度(這與“稀疏”矩陣中使用的概念不同。數據矩陣可能沒有零項，但結構在這個意義上仍然是“稀疏”的)。

  • Brute force (暴力查詢)時間不受數據結構的影響。
  • 數據結構對球狀樹和KD樹的查詢次數有很大的影響。通常，內部維數較小的稀疏數據會導致更快的查詢時間。由于KD樹的內部表示是與參數軸對齊的，所以對于任意結構的數據，它通常不會像球狀樹那樣顯示出更多的改進。

  機器學習中使用的數據集往往非常結構化，非常適合基于樹的查詢。

• 查詢點的鄰居數。

  • 的值很大程度上不影響暴力查詢的時間
  • 隨著的增加，球樹和KD樹的查詢時間會變慢。這有兩個原因：首先，較大的k需要搜索參數空間的更大部分。其次，使用k>1需要在遍歷樹時對結果進行內部排隊。

  與相比，當變得很大時，在基于樹的查詢中剪支的能力就降低了。在這種情況下，BruteForce查詢可以更高效。

• 查詢點的數量。球狀樹和KD樹都需要一個構建階段。當對許多查詢進行攤銷時，這種結構的成本可以忽略不計。但是，如果只執行少量的查詢，那么構建就可以占總成本的很大一部分。如果查詢點很少，暴力法比基于樹的方法更好。

目前，如果，輸入的數據是稀疏的，或者effective_metric_不在“kd_tree”或“ball_tree”的VALID_METRICS列表中，那么 algorithm = 'auto'選擇'brute'。否則，它將從'kd_tree'和'ball_tree' 的VALID_METRICS列表中選擇第一個effective_metric_。此選擇基于這樣的假設：查詢點的數量至少與訓練點數相同，而且 leaf_size接近其默認值30。

1.6.4.5 leaf_size的影響

如上所述，對于小樣本大小，暴力搜索比基于樹的查詢更有效。在球樹和KD樹中，通過內部切換到葉節點內的暴力搜索來解釋這一事實。此開關的級別可以使用參數leaf_size指定。這個參數的選擇有許多影響：

構建時間

更大的leaf_size會導致更快的樹構建時間，因為需要創建的節點更少

查詢時間

無論是大的還是小的 leaf_size都會導致次優的查詢成本。對于接近1的leaf_size，遍歷節點所涉及的開銷可以顯著降低查詢時間。對于接近訓練集大小的 leaf_size，查詢本質上是暴力的。兩者之間的一個很好的折衷方法是leaf_size = 30，這是參數的默認值。

內存

隨著 leaf_size的增加，存儲樹結構所需的內存減少。這在球樹中尤為重要，它為每個節點存儲一個D維質心。 BallTree所需的存儲空間大約是訓練集大小的1 / leaf_size。

對于暴力查詢，不引用leaf_size。

1.6.5 最近質心分類器

NearestCentroid是一個簡單的算法，它用成員的質心表示每個類。實際上，這使得它類似于 sklearn.cluster.KMeans算法的標簽更新階段。它也沒有參數可供選擇，因此它是一個很好的基線分類器。然而，在非凸類上，以及當類具有截然不同的方差時，當所有維度上的方差相等時，它都會受到影響。見線性判別分析。

(sklearn.discriminant_analysis.LinearDiscriminantAnalysis) 和二次判別分析

(sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis) 用于更復雜的方法，這些方法不作此假設。

默認的NearestCentroid的使用很簡單：

>>> from sklearn.neighbors 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()
>>> print(clf.predict([[-0.8, -1]]))
[1]

1.6.5.1最近收縮質心

NearestCentroid分類器有一個 shrink_threshold參數，它實現最近收縮質心分類器。實際上，每個質心的每個特征的值除以該特征的類內方差。然后，通過 shrink_threshold降低特征值。最值得注意的是，如果一個特定的特征值超過零，則它被設置為零。功能上，這將從影響分類的功能中刪除。例如，這對于消除噪聲特特征是有用的。

在下面的例子中，使用一個小的收縮閾值( shrink threshold)將模型的精度從0.81提高到0.82。

1.6.6 最近鄰轉換

許多scikit-learn的估計器依賴最近鄰：幾個分類器和回歸器，比如KNeighborsClassifier 和KNeighborsRegressor, 還有一些聚類方法，如 DBSCAN和SpectralClustering，以及一些多種嵌入，如 TSNE和 Isomap。

所有這些估計都可以在內部計算最近鄰，但大多數估計器也接受由 kneighbors_graph 和radius_neighbors_graph給出的預先計算過的最近鄰稀疏圖sparse graph。對于模式 mode='connectivity'，這些函數根據需要返回二分類鄰居稀疏圖，例如，在 SpectralClustering中。然而，如果使用mode='distance'，則會根據需要返回一個距離稀疏圖，例如，在 DBSCAN中。要將這些功能包含在scikit-learn的 (pipeline)管道(pipeline)中，還可以使用相應的類KNeighborsTransformer和RadiusNeighborsTransformer。這個稀疏圖API的好處是多方面的。

首先，預先計算的圖可以重復使用多次，例如，在改變估計器的參數時。這可以由用戶手動完成，也可以使用scikit-learn的管道的緩存屬性：

>>> from sklearn.manifold import Isomap
>>> from sklearn.neighbors import KNeighborsTransformer
>>> from sklearn.pipeline import make_pipeline
>>> estimator = make_pipeline(
...     KNeighborsTransformer(n_neighbors=5, mode='distance'),
...     Isomap(neighbors_algorithm='precomputed'),
...     memory='/path/to/cache')

第二，預計算圖可以對最近鄰估計提供更好的控制，例如，通過參數n_jobs實現多處理，這在所有的估計器中可能都不是可用的。

最后，預計算可以由自定義估計器執行，以使用不同的實現，例如近似的最近鄰方法，或使用特定數據類型的實現。預先計算過的鄰居稀疏圖sparse graph需要轉化化為 radius_neighbors_graph 的輸出：

• 一個CSR矩陣(雖然COO、CSC或LIL也會被接受)。
• 僅顯式地存儲每個樣本相對于訓練數據的最近鄰。這應該包括與查詢點0的距離，包括在計算訓練數據與其本身之間最近的鄰域時的矩陣對角線。
• 每一行的數據應按遞增順序存儲距離(可選)。未排序的數據將是穩定排序的，增加了計算開銷)。
• 數據中的所有值都應該是非負的。
• 在任何一行中都不應該有重復的索引indices。(看https://github.com/scipy/scipy/issues/5807)。
• 如果要傳遞的算法--預先計算的矩陣--使用k個最近鄰(相對于半徑鄰域)，則必須在每一行中存儲至少k個鄰居(或k+1，如下注所述)。

注意：

當詢問特定數量的鄰居時(使用 KNeighborsTransformer)，n_neighbors的定義是不明確的，因為它可以將每個訓練點作為自己的鄰居，也可以將它們排除在外。這兩種選擇都不是完美的，因為在訓練和測試中包含它們會導致不同數量的非自身鄰居，而排除它們會導致fit(X).transform(X) and fit_transform(X)之間的不同，這與scikit-learn的API是背道而馳的。在KNeighborsTransformer 中，我們使用了一個定義，每個訓練點作為自己的鄰居被計算在n_neighbors中。但是，由于與使用另一個定義的其他估計器的兼容性原因，當 mode == 'distance'時，將計算出一個額外的鄰居。為了最大化與所有估計器的兼容性，一個安全的選擇是總是在自定義的最近鄰估計器中包含一個額外的鄰居，因為不必要的鄰居將通過以下估計器進行過濾。

1.6.7 鄰域成分分析

鄰域成分分析(NCA，NeighborhoodComponentAnalysis)是一種距離度量學習算法，其目的是與標準歐氏距離相比，提高最近鄰分類的準確性。該算法直接在訓練集上使用 leave-one-out k近鄰(KNN)得分的隨機變量最大化。它還可以學習數據的低維線性投影，用于數據可視化和快速分類。

在上面的說明圖中，我們考慮了隨機生成的數據集中的一些點。重點研究了樣本3的隨機KNN分類。樣本3和另一點之間的連接厚度與它們之間的距離成正比，可以看作是隨機最近鄰預測規則給這一點分配的相對權重(或概率)。在原始空間中，樣本3有許多來自不同類的隨機鄰居，所以不太可能找到正確的類。然而，在NCA學習的投影空間中，唯一具有不可忽略權重的隨機鄰居來自與樣本3相同的類，從而保證后者將被很好地分類。有關更多細節，請參見數學公式。

1.6.7.1 分類

與最近鄰分類器(KNeighborsClassifier)相結合，NCA對分類很有吸引力，因為它可以自然地處理多類問題而不增加模型大小，并且不引入需要用戶微調的額外參數。

NCA分類在不同規模和難度的數據集的實際應用中得到了很好的表現。與線性判別分析等相關方法相比，NCA對類分布不作任何假設。最近鄰分類可以自然地產生高度不規則的決策邊界。

要使用此模型進行分類，需要將學習最優轉換的NeighborhoodComponentsAnalysis實例與在投影空間中執行分類的KNeighborsClassifier 實例相結合。下面是一個使用這兩個類的示例：

>>> from sklearn.neighbors import (NeighborhoodComponentsAnalysis,
... KNeighborsClassifier)
>>> from sklearn.datasets import load_iris
>>> from sklearn.model_selection import train_test_split
>>> from sklearn.pipeline import Pipeline
>>> X, y = load_iris(return_X_y=True)
>>> X_train, X_test, y_train, y_test = train_test_split(X, y,
... stratify=y, test_size=0.7, random_state=42)
>>> nca = NeighborhoodComponentsAnalysis(random_state=42)
>>> knn = KNeighborsClassifier(n_neighbors=3)
>>> nca_pipe = Pipeline([('nca', nca), ('knn', knn)])
>>> nca_pipe.fit(X_train, y_train)
Pipeline(...)
>>> print(nca_pipe.score(X_test, y_test))
0.96190476...

圖中顯示了 iris數據集上最近鄰分類和鄰域成分分析分類的決策邊界，當訓練和得分僅針對兩個特征時，用于可視化目的。

1.6.7.2 降維

NCA可用于有監督降維。將輸入數據投影到一個線性子空間，該子空間由最小化NCA目標的方向組成。可以使用參數n_components設置所需的維數。例如，下圖顯示了與數字數據集上的主成分分析(sklearn.decomposition.PCA)、線性判別分析((sklearn.discriminant_analysis.LinearDiscriminantAnalysis))和鄰域成分分析(NeighborhoodComponentsAnalysis)的降維效果的比較, 這個數據集有 個樣本， 個特征。數據集被劃分為大小相同的訓練集和測試集，然后進行標準化。為了評價該方法的分類精度，對每種方法找到的二維投影點進行了3-最近鄰分類精度的計算。每個數據樣本屬于10個類中的一個。

1.6.7.3 數學公式

NCA的目標是學習一個形狀為((n_components, n_features))的最優線性變換矩陣，它使所有樣本正確分類的概率的和最大，即：

其中=n_samples, 是樣本在學習的嵌入空間中按照隨機最近鄰規則正確分類的概率：

其中是與樣本相同類中的點集，是嵌入空間中歐氏距離上的歸一化指數Softmax：

1.6.7.3.1 Mahalanobis距離

NCA可以看作是學習(平方)Mahalanobis距離度量：

其中，是一個對稱的半正定的矩陣((n_features, n_features))。

1.6.7.4 實現

該實現遵循了最初論文[1]中的解釋，對于優化方法，目前使用的是scipy的L-BFGS-B，每次迭代都進行完全梯度計算，以避免調整學習速度，提供穩定的擬合。

請參閱下面的示例和 NeighborhoodComponentsAnalysis.fit的文檔以獲得更多信息。

1.6.7.5 復雜度

1.6.7.5.1 訓練

NCA存儲一對距離矩陣，占用了n_samples ** 2的內存。時間復雜度取決于優化算法的迭代次數。但是，可以使用參數max_iter設置迭代的最大次數。對于每個迭代，時間復雜度為O(n_components x n_samples x min(n_samples, n_features))。

1.6.7.5.2 轉換

這里轉換操作返回值的是，因此它的時間復雜度等于n_components x n_features x n_samples_test。操作中沒有增加空間復雜度。

參考

[1] “Neighbourhood Components Analysis”, J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov, Advances in Neural Information Processing Systems, Vol. 17, May 2005, pp. 513-520.

Wikipedia entry on Neighborhood Components Analysis