scikit-learn 最近鄰

sklearn.neighbors提供了基于近鄰的無(wú)監(jiān)督和有監(jiān)督的學(xué)習(xí)方法的功能。無(wú)監(jiān)督最近鄰是許多其他學(xué)習(xí)方法的基礎(chǔ)，特別是流形學(xué)習(xí)(manifold learning)和光譜聚類(lèi)(spectral clustering)。有監(jiān)督的 neighbors-based (基于鄰居的) 學(xué)習(xí)有兩種方式：離散標(biāo)簽數(shù)據(jù)的分類(lèi)和連續(xù)標(biāo)簽數(shù)據(jù)的回歸。

最近鄰方法背后的原理是找到在距離上離新樣本最近的一些樣本， 并且從這些樣本中預(yù)測(cè)標(biāo)簽。最近鄰的樣本數(shù)可以是用戶(hù)定義的常數(shù)(k-最近鄰)，也可以根據(jù)不同的點(diǎn)的局部密度(基于半徑的近鄰學(xué)習(xí))確定。一般來(lái)說(shuō)，距離可以用任意來(lái)度量：標(biāo)準(zhǔn)的歐氏距離是最常見(jiàn)的選擇?；卩従拥姆椒ū环Q(chēng)為非泛化機(jī)器學(xué)習(xí)方法，因?yàn)樗鼈冎皇恰坝涀　彼乃杏?xùn)練數(shù)據(jù)(可能轉(zhuǎn)換成一個(gè)快速的索引結(jié)構(gòu)，比如Ball樹(shù)或KD樹(shù))。

盡管它很簡(jiǎn)單，但最近鄰已經(jīng)成功地解決了大量的分類(lèi)和回歸問(wèn)題，包括手寫(xiě)數(shù)字和衛(wèi)星圖像等場(chǎng)景。作為一種非參數(shù)方法，在決策邊界非常不規(guī)則的情況下通常是成功的。

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

有許多學(xué)習(xí)規(guī)則都是依賴(lài)于它們的核心近鄰。一個(gè)例子是核密度估計(jì)( kernel density estimation,)，在密度估計(jì)( density estimation)部分討論。

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

NearestNeighbors實(shí)現(xiàn)了無(wú)監(jiān)督的最近鄰學(xué)習(xí)。它充當(dāng)三個(gè)不同的最近鄰算法的統(tǒng)一接口：BallTree和KDTree和一個(gè)基于sklearn.emeics.pair中規(guī)則的暴力算法。最近鄰搜索算法的選擇是通過(guò)關(guān)鍵字algorithm來(lái)控制的, 其選擇必須是['auto', 'ball_tree', 'kd_tree', 'brute']中的一個(gè)。當(dāng)傳遞默認(rèn)值‘a(chǎn)uto’時(shí)，該算法嘗試從訓(xùn)練數(shù)據(jù)中自動(dòng)查出最佳的方法。有關(guān)每個(gè)選項(xiàng)的優(yōu)缺點(diǎn)的討論，請(qǐng)參見(jiàn)Nearest Neighbor Algorithms。

1.6.1.1 找到最近鄰

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

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

因?yàn)椴樵?xún)集與訓(xùn)練集匹配，所以每個(gè)點(diǎn)的最近鄰居就是該點(diǎn)本身，距離為零。

還可以有效地生成表示相鄰點(diǎ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.]])

1.6.1.2 KDTree和BallTree類(lèi)

或者，可以直接使用KDTree或BallTree類(lèi)來(lái)查找最近的鄰居。這是上文使用過(guò)的NearestNeighbors類(lèi)包裝的功能， 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]]...)

有關(guān)最近鄰搜索可用選項(xiàng)的更多信息，請(qǐng)參閱KDTree和BallTree類(lèi)文檔，包括查詢(xún)策略規(guī)范、距離度量等。有關(guān)可用度量的列表，請(qǐng)參見(jiàn)DistanceMetric 類(lèi)的文檔。

1.6.2 最近鄰分類(lèi)

基于近鄰的分類(lèi)是一種基于實(shí)例的學(xué)習(xí)或非泛化學(xué)習(xí)：它不是試圖構(gòu)造一個(gè)通用的內(nèi)部模型，而是簡(jiǎn)單地存儲(chǔ)訓(xùn)練數(shù)據(jù)的實(shí)例。分類(lèi)是由每個(gè)點(diǎn)的最近鄰的簡(jiǎn)單多數(shù)投票中計(jì)算得到的：一個(gè)查詢(xún)點(diǎn)被標(biāo)記的數(shù)據(jù)標(biāo)簽是由它最近鄰點(diǎn)中最具代表性的數(shù)據(jù)標(biāo)簽來(lái)決定的。

scikit-learn實(shí)現(xiàn)了兩個(gè)不同的最近鄰分類(lèi)器： KNeighborsClassifier 分類(lèi)器根據(jù)每個(gè)查詢(xún)點(diǎn)的k個(gè)最近鄰實(shí)現(xiàn)學(xué)習(xí)，其中k是用戶(hù)指定的整數(shù)值。 RadiusNeighborsClassifier分類(lèi)器根據(jù)每個(gè)訓(xùn)練點(diǎn)的固定半徑內(nèi)的鄰居數(shù)實(shí)現(xiàn)學(xué)習(xí)，其中 是用戶(hù)指定的浮點(diǎn)值。

KNeighborsClassifier 中的K近鄰分類(lèi)是最常用的分類(lèi)方法。k值的最佳選擇是高度依賴(lài)于數(shù)據(jù)的：一般來(lái)說(shuō)，較大的 會(huì)抑制噪聲的影響，但使分類(lèi)邊界不那么清晰。

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

基本的最近鄰分類(lèi)使用一樣的權(quán)重：也就是說(shuō)，分配給查詢(xún)點(diǎn)的值是根據(jù)最近鄰居的簡(jiǎn)單多數(shù)投票計(jì)算的。在某些情況下，最好是對(duì)鄰居進(jìn)行加權(quán)，這樣更靠近的鄰居對(duì)擬合來(lái)說(shuō)貢獻(xiàn)更大。這可以通過(guò)weights關(guān)鍵字來(lái)實(shí)現(xiàn)。默認(rèn)值是weights=“uniform”，為每個(gè)鄰居分配同樣的權(quán)重。weights = 'distance'分配的權(quán)重與到查詢(xún)點(diǎn)的距離成反比?；蛘撸梢蕴峁┯脩?hù)定義的距離函數(shù)來(lái)計(jì)算權(quán)重.

1.6.3 最近鄰回歸

如果數(shù)據(jù)標(biāo)簽是連續(xù)的，而不是離散的變量，則可以使用基于鄰居的回歸。分配給查詢(xún)點(diǎn)的標(biāo)簽是根據(jù)其最近鄰居的標(biāo)簽的平均值計(jì)算的。

scikit-learn實(shí)現(xiàn)了兩個(gè)不同的近鄰回歸器：KNeighborsRegressor實(shí)現(xiàn)基于每個(gè)查詢(xún)點(diǎn)的k個(gè)最近鄰的學(xué)習(xí)，其中k是用戶(hù)指定的整數(shù)值。 RadiusNeighborsRegressor實(shí)現(xiàn)了基于查詢(xún)點(diǎn)的固定半徑r內(nèi)的近鄰的學(xué)習(xí)，其中r是用戶(hù)指定的浮點(diǎn)數(shù)值。

最基本的最近鄰回歸使用的是一樣的權(quán)重：即，局部鄰域中的每個(gè)點(diǎn)對(duì)查詢(xún)點(diǎn)的分類(lèi)都有一樣的貢獻(xiàn)。在某些情況下，它可以是有利的，即距離更近的點(diǎn)對(duì)回歸的貢獻(xiàn)要大于更遠(yuǎn)的點(diǎn)。這可以通過(guò)weights關(guān)鍵字來(lái)實(shí)現(xiàn)。默認(rèn)值是weights = 'uniform'，為所有點(diǎn)分配一樣的權(quán)重。 weights = 'distance'分配權(quán)重與到查詢(xún)點(diǎn)的距離成反比?；蛘撸梢蕴峁┯脩?hù)定義的距離函數(shù)，該函數(shù)將用于計(jì)算權(quán)重。

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

1.6.4.最近鄰算法

1.6.4.1 暴力計(jì)算

最近鄰的快速計(jì)算是機(jī)器學(xué)習(xí)中一個(gè)活躍的研究領(lǐng)域。最樸素的近鄰搜索的實(shí)現(xiàn)涉及到數(shù)據(jù)集中所有成對(duì)點(diǎn)之間距離的暴力計(jì)算：對(duì)于維中的個(gè)樣本來(lái)說(shuō)，這種方法的復(fù)雜度為。高效的暴力近鄰搜索對(duì)于小數(shù)據(jù)樣本來(lái)說(shuō)是非常有競(jìng)爭(zhēng)力的。然而，隨著樣本的增加，暴力法很快就變得不可行了。在類(lèi)sklearn.neighbors中，暴力近鄰搜索是使用關(guān)鍵字algorithm = 'brute'指定的，并使用 sklearn.metrics.pairwise中可用的程序來(lái)計(jì)算。

1.6.4.2 K-D樹(shù)

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

利用這些聚合信息的早期方法是KD樹(shù)數(shù)據(jù)結(jié)構(gòu)(K-dimensional tree的縮寫(xiě))，它將二維Quad-trees和三維Oct-trees推廣到任意維數(shù)。KD樹(shù)是一種二叉樹(shù)結(jié)構(gòu)，它遞歸地沿?cái)?shù)據(jù)軸劃分參數(shù)空間，將其劃分為嵌套的正交異性區(qū)域，然后將數(shù)據(jù)點(diǎn)放入其中。KD樹(shù)的構(gòu)造非?？欤阂?yàn)榉謪^(qū)只沿?cái)?shù)據(jù)軸執(zhí)行，所以不需要計(jì)算維距離。一旦構(gòu)造，僅通過(guò)復(fù)雜度為的距離計(jì)算就可以確定查詢(xún)點(diǎn)的最近鄰居。雖然KD樹(shù)方法對(duì)于低維()鄰域搜索非常快速，但隨著增大，它變得效率低下：這是所謂的“維度詛咒”的一種表現(xiàn)。在scikit-learn中，KD樹(shù)近鄰搜索使用關(guān)鍵字algorithm = 'kd_tree'指定，并使用 KDTree類(lèi)進(jìn)行計(jì)算。

參考

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

1.6.4.3 Ball樹(shù)

針對(duì)KD樹(shù)高維度下效率低的問(wèn)題，提出了球狀樹(shù)的數(shù)據(jù)結(jié)構(gòu)。其中KD樹(shù)沿著笛卡爾軸劃分?jǐn)?shù)據(jù)，球樹(shù)在一系列嵌套超球(hyper-spheres)中劃分?jǐn)?shù)據(jù)。這使得樹(shù)的構(gòu)建比KD樹(shù)的代價(jià)更高，但是導(dǎo)致了一種對(duì)高度結(jié)構(gòu)化非常有效的數(shù)據(jù)結(jié)構(gòu)，即使在非常高的維度上也是如此。

球樹(shù)遞歸地將數(shù)據(jù)劃分為由質(zhì)心和半徑定義的節(jié)點(diǎn)，這樣節(jié)點(diǎn)中的每個(gè)點(diǎn)都位于和定義的超球面內(nèi)，通過(guò)使用三角不等式減少了鄰居搜索的候選點(diǎn)數(shù)：

使用此設(shè)置，測(cè)試點(diǎn)和質(zhì)心之間的單個(gè)距離計(jì)算就足以確定節(jié)點(diǎn)內(nèi)所有點(diǎn)之間距離的上下界。由于球狀樹(shù)節(jié)點(diǎn)的球形幾何特性，雖然實(shí)際性能與訓(xùn)練數(shù)據(jù)的結(jié)構(gòu)有很大的關(guān)系，但它可以在高維上表現(xiàn)出一棵KD樹(shù)。在scikit-learn中，基于球樹(shù)的鄰居搜索是使用關(guān)鍵字algorithm = 'ball_tree'指定的，并且是使用類(lèi) sklearn.neighbors.BallTree計(jì)算的?；蛘撸脩?hù)可以直接使用 BallTree 類(lèi)。

參考文獻(xiàn)

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

1.6.4.4 最近鄰算法的選擇

給定數(shù)據(jù)集的優(yōu)化算法是一個(gè)復(fù)雜的選擇，取決于以下幾個(gè)因素：

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

  • Brute force查詢(xún)的時(shí)間以增長(zhǎng)
  • Ball tree查詢(xún)時(shí)間以增長(zhǎng)
  • KD樹(shù)查詢(xún)時(shí)間隨變化，難以精確描述。對(duì)于較小的(小于20)，代價(jià)約為?，KD樹(shù)查詢(xún)效率很高。對(duì)于較大的，成本增加到接近，而樹(shù)結(jié)構(gòu)造成的開(kāi)銷(xiāo)可能導(dǎo)致比暴力更慢的查詢(xún)。

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

• 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的 intrinsic dimensionality(本征維數(shù)) 和/或數(shù)據(jù)的 sparsity (稀疏度)。本征維數(shù)是指數(shù)據(jù)所在的流形的維數(shù)，它可以線(xiàn)性嵌入?yún)?shù)空間，也可以非線(xiàn)性嵌入?yún)?shù)空間。稀疏性是指數(shù)據(jù)填充參數(shù)空間的程度(這與“稀疏”矩陣中使用的概念不同。數(shù)據(jù)矩陣可能沒(méi)有零項(xiàng)，但結(jié)構(gòu)在這個(gè)意義上仍然是“稀疏”的)。

  • Brute force (暴力查詢(xún))時(shí)間不受數(shù)據(jù)結(jié)構(gòu)的影響。
  • 數(shù)據(jù)結(jié)構(gòu)對(duì)球狀樹(shù)和KD樹(shù)的查詢(xún)次數(shù)有很大的影響。通常，內(nèi)部維數(shù)較小的稀疏數(shù)據(jù)會(huì)導(dǎo)致更快的查詢(xún)時(shí)間。由于KD樹(shù)的內(nèi)部表示是與參數(shù)軸對(duì)齊的，所以對(duì)于任意結(jié)構(gòu)的數(shù)據(jù)，它通常不會(huì)像球狀樹(shù)那樣顯示出更多的改進(jìn)。

  機(jī)器學(xué)習(xí)中使用的數(shù)據(jù)集往往非常結(jié)構(gòu)化，非常適合基于樹(shù)的查詢(xún)。

• 查詢(xún)點(diǎn)的鄰居數(shù)。

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

  與相比，當(dāng)變得很大時(shí)，在基于樹(shù)的查詢(xún)中剪支的能力就降低了。在這種情況下，BruteForce查詢(xún)可以更高效。

• 查詢(xún)點(diǎn)的數(shù)量。球狀樹(shù)和KD樹(shù)都需要一個(gè)構(gòu)建階段。當(dāng)對(duì)許多查詢(xún)進(jìn)行攤銷(xiāo)時(shí)，這種結(jié)構(gòu)的成本可以忽略不計(jì)。但是，如果只執(zhí)行少量的查詢(xún)，那么構(gòu)建就可以占總成本的很大一部分。如果查詢(xún)點(diǎn)很少，暴力法比基于樹(shù)的方法更好。

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

1.6.4.5 leaf_size的影響

如上所述，對(duì)于小樣本大小，暴力搜索比基于樹(shù)的查詢(xún)更有效。在球樹(shù)和KD樹(shù)中，通過(guò)內(nèi)部切換到葉節(jié)點(diǎn)內(nèi)的暴力搜索來(lái)解釋這一事實(shí)。此開(kāi)關(guān)的級(jí)別可以使用參數(shù)leaf_size指定。這個(gè)參數(shù)的選擇有許多影響：

構(gòu)建時(shí)間

更大的leaf_size會(huì)導(dǎo)致更快的樹(shù)構(gòu)建時(shí)間，因?yàn)樾枰獎(jiǎng)?chuàng)建的節(jié)點(diǎn)更少

查詢(xún)時(shí)間

無(wú)論是大的還是小的 leaf_size都會(huì)導(dǎo)致次優(yōu)的查詢(xún)成本。對(duì)于接近1的leaf_size，遍歷節(jié)點(diǎn)所涉及的開(kāi)銷(xiāo)可以顯著降低查詢(xún)時(shí)間。對(duì)于接近訓(xùn)練集大小的 leaf_size，查詢(xún)本質(zhì)上是暴力的。兩者之間的一個(gè)很好的折衷方法是leaf_size = 30，這是參數(shù)的默認(rèn)值。

內(nèi)存

隨著 leaf_size的增加，存儲(chǔ)樹(shù)結(jié)構(gòu)所需的內(nèi)存減少。這在球樹(shù)中尤為重要，它為每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)D維質(zhì)心。 BallTree所需的存儲(chǔ)空間大約是訓(xùn)練集大小的1 / leaf_size。

對(duì)于暴力查詢(xún)，不引用leaf_size。

1.6.5 最近質(zhì)心分類(lèi)器

NearestCentroid是一個(gè)簡(jiǎn)單的算法，它用成員的質(zhì)心表示每個(gè)類(lèi)。實(shí)際上，這使得它類(lèi)似于 sklearn.cluster.KMeans算法的標(biāo)簽更新階段。它也沒(méi)有參數(shù)可供選擇，因此它是一個(gè)很好的基線(xiàn)分類(lèi)器。然而，在非凸類(lèi)上，以及當(dāng)類(lèi)具有截然不同的方差時(shí)，當(dāng)所有維度上的方差相等時(shí)，它都會(huì)受到影響。見(jiàn)線(xiàn)性判別分析。

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

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

默認(rèn)的NearestCentroid的使用很簡(jiǎn)單：

>>> 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最近收縮質(zhì)心

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

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

1.6.6 最近鄰轉(zhuǎn)換

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

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

首先，預(yù)先計(jì)算的圖可以重復(fù)使用多次，例如，在改變估計(jì)器的參數(shù)時(shí)。這可以由用戶(hù)手動(dòng)完成，也可以使用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')

第二，預(yù)計(jì)算圖可以對(duì)最近鄰估計(jì)提供更好的控制，例如，通過(guò)參數(shù)n_jobs實(shí)現(xiàn)多處理，這在所有的估計(jì)器中可能都不是可用的。

最后，預(yù)計(jì)算可以由自定義估計(jì)器執(zhí)行，以使用不同的實(shí)現(xiàn)，例如近似的最近鄰方法，或使用特定數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)。預(yù)先計(jì)算過(guò)的鄰居稀疏圖sparse graph需要轉(zhuǎn)化化為 radius_neighbors_graph 的輸出：

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

注意：

當(dāng)詢(xún)問(wèn)特定數(shù)量的鄰居時(shí)(使用 KNeighborsTransformer)，n_neighbors的定義是不明確的，因?yàn)樗梢詫⒚總€(gè)訓(xùn)練點(diǎn)作為自己的鄰居，也可以將它們排除在外。這兩種選擇都不是完美的，因?yàn)樵谟?xùn)練和測(cè)試中包含它們會(huì)導(dǎo)致不同數(shù)量的非自身鄰居，而排除它們會(huì)導(dǎo)致fit(X).transform(X) and fit_transform(X)之間的不同，這與scikit-learn的API是背道而馳的。在KNeighborsTransformer 中，我們使用了一個(gè)定義，每個(gè)訓(xùn)練點(diǎn)作為自己的鄰居被計(jì)算在n_neighbors中。但是，由于與使用另一個(gè)定義的其他估計(jì)器的兼容性原因，當(dāng) mode == 'distance'時(shí)，將計(jì)算出一個(gè)額外的鄰居。為了最大化與所有估計(jì)器的兼容性，一個(gè)安全的選擇是總是在自定義的最近鄰估計(jì)器中包含一個(gè)額外的鄰居，因?yàn)椴槐匾泥従訉⑼ㄟ^(guò)以下估計(jì)器進(jìn)行過(guò)濾。

1.6.7 鄰域成分分析

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

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

1.6.7.1 分類(lèi)

與最近鄰分類(lèi)器(KNeighborsClassifier)相結(jié)合，NCA對(duì)分類(lèi)很有吸引力，因?yàn)樗梢宰匀坏靥幚矶囝?lèi)問(wèn)題而不增加模型大小，并且不引入需要用戶(hù)微調(diào)的額外參數(shù)。

NCA分類(lèi)在不同規(guī)模和難度的數(shù)據(jù)集的實(shí)際應(yīng)用中得到了很好的表現(xiàn)。與線(xiàn)性判別分析等相關(guān)方法相比，NCA對(duì)類(lèi)分布不作任何假設(shè)。最近鄰分類(lèi)可以自然地產(chǎn)生高度不規(guī)則的決策邊界。

要使用此模型進(jìn)行分類(lèi)，需要將學(xué)習(xí)最優(yōu)轉(zhuǎn)換的NeighborhoodComponentsAnalysis實(shí)例與在投影空間中執(zhí)行分類(lèi)的KNeighborsClassifier 實(shí)例相結(jié)合。下面是一個(gè)使用這兩個(gè)類(lèi)的示例：

>>> 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數(shù)據(jù)集上最近鄰分類(lèi)和鄰域成分分析分類(lèi)的決策邊界，當(dāng)訓(xùn)練和得分僅針對(duì)兩個(gè)特征時(shí)，用于可視化目的。

1.6.7.2 降維

NCA可用于有監(jiān)督降維。將輸入數(shù)據(jù)投影到一個(gè)線(xiàn)性子空間，該子空間由最小化NCA目標(biāo)的方向組成?？梢允褂脜?shù)n_components設(shè)置所需的維數(shù)。例如，下圖顯示了與數(shù)字?jǐn)?shù)據(jù)集上的主成分分析(sklearn.decomposition.PCA)、線(xiàn)性判別分析((sklearn.discriminant_analysis.LinearDiscriminantAnalysis))和鄰域成分分析(NeighborhoodComponentsAnalysis)的降維效果的比較, 這個(gè)數(shù)據(jù)集有 個(gè)樣本， 個(gè)特征。數(shù)據(jù)集被劃分為大小相同的訓(xùn)練集和測(cè)試集，然后進(jìn)行標(biāo)準(zhǔn)化。為了評(píng)價(jià)該方法的分類(lèi)精度，對(duì)每種方法找到的二維投影點(diǎn)進(jìn)行了3-最近鄰分類(lèi)精度的計(jì)算。每個(gè)數(shù)據(jù)樣本屬于10個(gè)類(lèi)中的一個(gè)。

1.6.7.3 數(shù)學(xué)公式

NCA的目標(biāo)是學(xué)習(xí)一個(gè)形狀為((n_components, n_features))的最優(yōu)線(xiàn)性變換矩陣，它使所有樣本正確分類(lèi)的概率的和最大，即：

其中=n_samples, 是樣本在學(xué)習(xí)的嵌入空間中按照隨機(jī)最近鄰規(guī)則正確分類(lèi)的概率：

其中是與樣本相同類(lèi)中的點(diǎn)集，是嵌入空間中歐氏距離上的歸一化指數(shù)Softmax：

1.6.7.3.1 Mahalanobis距離

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

其中，是一個(gè)對(duì)稱(chēng)的半正定的矩陣((n_features, n_features))。

1.6.7.4 實(shí)現(xiàn)

該實(shí)現(xiàn)遵循了最初論文[1]中的解釋?zhuān)瑢?duì)于優(yōu)化方法，目前使用的是scipy的L-BFGS-B，每次迭代都進(jìn)行完全梯度計(jì)算，以避免調(diào)整學(xué)習(xí)速度，提供穩(wěn)定的擬合。

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

1.6.7.5 復(fù)雜度

1.6.7.5.1 訓(xùn)練

NCA存儲(chǔ)一對(duì)距離矩陣，占用了n_samples ** 2的內(nèi)存。時(shí)間復(fù)雜度取決于優(yōu)化算法的迭代次數(shù)。但是，可以使用參數(shù)max_iter設(shè)置迭代的最大次數(shù)。對(duì)于每個(gè)迭代，時(shí)間復(fù)雜度為O(n_components x n_samples x min(n_samples, n_features))。

1.6.7.5.2 轉(zhuǎn)換

這里轉(zhuǎn)換操作返回值的是，因此它的時(shí)間復(fù)雜度等于n_components x n_features x n_samples_test。操作中沒(méi)有增加空間復(fù)雜度。

參考

[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