Scikit Learn - K近鄰演算法 (KNN)

本章將幫助您理解 Sklearn 中的最近鄰方法。

基於鄰域的學習方法有兩種型別，即監督和無監督。監督的基於鄰域的學習可用於分類和迴歸預測問題，但在工業中主要用於分類預測問題。

基於鄰域的學習方法沒有專門的訓練階段，並在分類期間使用所有資料進行訓練。它也不對底層資料做任何假設。這就是它們本質上是懶惰的和非引數的原因。

最近鄰方法背後的主要原理是：

這裡，樣本數量可以是使用者定義的常數，如 K 近鄰學習，或者根據點的區域性密度變化，如基於半徑的鄰域學習。

Scikit-learn 擁有sklearn.neighbors模組，該模組提供了用於無監督和監督基於鄰域的學習方法的功能。作為輸入，此模組中的類可以處理 NumPy 陣列或scipy.sparse矩陣。

演算法型別

基於鄰域方法實現中可使用的不同型別的演算法如下：

資料集所有點對之間距離的蠻力計算提供了最簡單的鄰域搜尋實現。在數學上，對於 D 維中的 N 個樣本，蠻力方法的規模為0[DN²]

對於小樣本資料，此演算法非常有用，但隨著樣本數量的增長，它變得不可行。蠻力鄰域搜尋可以透過編寫關鍵字algorithm='brute'來啟用。

為了解決蠻力方法的計算效率低下問題，人們發明了一種基於樹的資料結構，即 KD 樹資料結構。基本上，KD 樹是一種二叉樹結構，稱為 K 維樹。它透過將引數空間沿資料軸遞迴地劃分成巢狀的正交區域，並將資料點填充到這些區域中，從而遞迴地劃分引數空間。

以下是 KD 樹演算法的一些優點：

構建速度快 - 由於分割槽僅沿資料軸執行，因此 KD 樹的構建速度非常快。

距離計算少 - 此演算法只需要很少的距離計算即可確定查詢點的最近鄰。它只需要𝑶[𝐥𝐨𝐠 (𝑵)]距離計算。

僅適用於低維鄰域搜尋 - 對於低維 (D < 20) 鄰域搜尋速度非常快，但隨著 D 的增長，它變得效率低下。由於分割槽僅沿資料軸執行，

可以透過編寫關鍵字algorithm='kd_tree'來啟用 KD 樹鄰域搜尋。

眾所周知，KD 樹在高維情況下效率低下，因此為了解決 KD 樹的這種效率低下問題，開發了球樹資料結構。在數學上，它將資料遞迴地劃分為由質心 C 和半徑 r 定義的節點，以使節點中的每個點都位於由質心C和半徑r定義的超球體內。它使用以下給出的三角不等式，這減少了鄰域搜尋的候選點數

$$\arrowvert X+Y\arrowvert\leq \arrowvert X\arrowvert+\arrowvert Y\arrowvert$$

以下是球樹演算法的一些優點：

在高度結構化的資料上高效 - 由於球樹將資料劃分為一系列巢狀的超球體，因此它在高度結構化的資料上效率很高。

效能優於 KD 樹 - 球樹在高維情況下優於 KD 樹，因為它具有球樹節點的球形幾何形狀。

代價高昂 - 將資料劃分為一系列巢狀的超球體使其構建非常昂貴。

可以透過編寫關鍵字algorithm='ball_tree'來啟用球樹鄰域搜尋。

對於給定資料集選擇最佳演算法取決於以下因素：

在選擇最近鄰演算法時，這些是最重要的因素。這是因為以下原因：

蠻力演算法的查詢時間增長為 O[DN]。
球樹演算法的查詢時間增長為 O[D log(N)]。
KD 樹演算法的查詢時間以一種難以描述的奇怪方式隨 D 變化。當 D < 20 時，成本為 O[D log(N)]，並且此演算法非常高效。另一方面，當 D > 20 時，它效率低下，因為成本增加到接近 O[DN]。

影響這些演算法效能的另一個因素是資料的內在維度或資料的稀疏性。這是因為球樹和 KD 樹演算法的查詢時間可能會受到其很大影響。而蠻力演算法的查詢時間不受資料結構的影響。通常，當在具有較小內在維度的更稀疏資料上實現時，球樹和 KD 樹演算法會產生更快的查詢時間。

為查詢點請求的鄰居數 (k) 會影響球樹和 KD 樹演算法的查詢時間。隨著鄰居數 (k) 的增加，它們的查詢時間會變慢。而蠻力演算法的查詢時間不會受到 k 值的影響。

因為它們需要構建階段，所以如果查詢點數很多，KD 樹和球樹演算法將非常有效。另一方面，如果查詢點數較少，則蠻力演算法的效能優於 KD 樹和球樹演算法。

列印頁面