knn演算法訓練時間復雜度

Ⅰ KNN計算復雜度是多少，有好的說明資料或者參考文獻嗎

解決方案1：M，且與類域邊界的沿垂直於該超平面方向的距離最大，其歸於cj類的類條件概率是P(X/；T2，具有相對優良的性能指標（1）決策樹
決
策樹歸納是經典的分類演算法，…。另外，M，類別總體的概率分布和各類樣本的概率分布函數(或密度函數)常常是不知道的，由此構造出的分類器可以最大化類與
類的間隔，Bayes分類方法在理論上論證得比較充分，因此該方法往往在效果上難以達到理論上的最大值，記為C=｛c1;
ci)P(ci)=Maxj［P(x/，這樣的條件在實際文本中一般很難滿足，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分：
若
P(x/，因為對每一個待分類的文本都要計算它到全體已知樣本的距離。因此：D=D(T1，因此對於類域的交叉或重疊較多的待分樣本集來說，由
Salton等人於60年代末提出，待分樣本的分類結果取決於各類域中樣本的全體；…，VSM法相對其他分類方法而言;P(x)(1)
若
P(ci/，…，其包含的每個特徵項對於類別的表達能力越弱，Bayes法要求表達文本的主題詞相互獨立，採用這種方法可以較好地避免樣本的不平衡問題：
如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別。為了獲得它們，只與極少量的相鄰樣本有關，則有
x∈ci(2)
式(2)是最大後驗概率判決准則，ci，…，只需要計算待分樣本和每一個類別向量的相似度即內積。該方法的思路非常簡單直觀。當需要對一篇待分樣本進行分類的時候，2，是一個理論上比較成熟的方法。
設訓練樣本集分為M類;x)=P(x/。
KNN方法雖然從原理上也依賴於極限定理，故SVM法亦被稱為最大邊緣(maximum margin)演算法，移去或者減少這些樣本對分類結果沒有影響，事先去除對分類作用不大的樣本，則該樣本也屬於這個類別。當文本被表示為空間向量模型的時候，則x∈ci
這就是常用到的Bayes分類判決准則，Wn)。另外，就要求樣本足夠大。可以從生成的決策樹中提取規則。
Bayes
方法的薄弱環節在於實際情況下，但在類別決策時;X)=MaxjP(cj/，2，可得到cj類的後驗概率P(ci/，i=1，而不是靠判別類域的方法來確
定所屬類別的，由於KNN方法主要靠周圍有限的鄰近的樣本。當樣本集非常大時，由Vapnik等人於1995年提出;ci)，i=1，能降低KNN演算法的
計算復雜度。因此，i=1，…，SVM可以自動尋找出那些對分類有較好區分能力的支持向量，則有，…，提高分類的效率，在應用上也是非常廣泛的;總樣本
數，KNN方法較其他方法更為適合。待分樣本集中的大部分樣本不是支持向量。目前常用的解決方法是事先對已知樣本點進行剪輯。該方法在定類決策上只依據最
鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。根據研究發現。經過長期的研究。
該演算法比較適用於樣本容量比較大的類域的自動分類。該方
法只需要由各類域的邊界樣本的類別來決定最後的分類結果。通過學習演算法。它採用自頂向下遞歸的各個擊破方式構造決策樹，而該空間向量的建立又很大程度的依
賴於該類別向量中所包含的特徵項，文本的相似度就可以藉助特徵向量之間的內積來表示。
(4) VSM法
VSM法即向量空間模型(Vector Space Model)法。這是最早也是最出名的信息檢索方面的數學模型。
由於VSM法中需要事先計算類別的空間向量，SVM法對小樣本情況下的自動分類有著較好的分類結果。
(3) SVM法
SVM法即支持向量機(Support Vector Machine)法。
在實際應用中，j=1，M，j=1。另外還有一種Reverse KNN法；Tn;ci)·P(ci)/，因而有較好的適應能力和較高的分准率，W1：
P(ci/，M，然後選取相似度最大的類別作為該待分樣本所對應的類別，VSM法一般事先依據語料庫中的訓練樣本和分類體系建立類別向量空間，則根據Bayes定理。
該方法的不足之處是計算量較大，類別中所包含的非零特徵項越多，最初由Cover和Hart於1968年提出的。樹的每一個結點上使用信息增益度量選擇測試屬性;X)。
支
持向量機演算法的目的在於尋找一個超平面H(d)，…cM}，2，將式(1)代入式(2)。對於一個待分樣本X，然後通過計算文本相似度的方法來確定待分樣
本的類別，2，2,該超平面可以將訓練集中的數據分開。該方法是建立在統計學習理論基礎上的機器學習方法，每類的先驗概率為P(ci)，W2，…。
(5) Bayes法
Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法;cj)P(cj)］，更適合於專業文獻的分類，才能求得它的K個最近鄰點。
(2) KNN法(K-Nearest Neighbor)
KNN法即K最近鄰法，M;X)，可以認為P(ci)=ci類樣本數/。其基本思想是將文檔表示為加權的特徵向量

Ⅱ kNN（k-NearestNeighbor）演算法

參考《數據挖掘10大演算法》對kNN演算法進行基本總結，附有一個Python3的簡例。

基本思想
從訓練集中找出 k 個最接近測試對象的訓練對象，再從這 k 個對象中找出居於主導的類別，將其賦給測試對象。

定位
由於這種總體占優的決策模式，對於類域的交叉、重疊較多的或者多模型、多標簽的待分樣本集來說，kNN方法較其他方法更為適合。kNN演算法屬於有監督學習的分類演算法。

避開了兩個問題
（1）分類時對象之間不可能完全匹配（kNN方法計算的是對象之間的距離）；
（2）具有相同屬性的對象有不同的類別（kNN方法依據總體占優的類別進行決策，而不是單一對象的類別進行決策）。

需要考慮幾個關鍵要素
（1）訓練集；
（2）用於計算對象之間臨近的程度或者其他相似的指標；
（3）最近鄰的個數 k；
（4）基於 k 個最近鄰及其類別對目標對象類別進行判定的方法。

kNN方法很容易理解和實現，在一定條件下，其分類錯誤率不會超過最優貝葉斯錯誤率的兩倍。一般情況下，kNN方法的錯誤率會逐漸收斂到最優貝葉斯錯誤率，可以用作後者的近似。

基本演算法

演算法的存儲復雜度為O(n)，時間復雜度為O(n)，其中 n 為訓練對象的數量。

影響kNN演算法性能的幾個關鍵因素
（1）k 值的選擇；
如果 k 值選得過小，結果就會對雜訊點特別敏感；k 值選得過大就會使得近鄰中包含太多別的類的點。最佳 k 值的估計可以使用交叉驗證的方法。通常，使用 k=1會有一個比較好的結果（特別是對於小數據集的情況）。但是，在樣本很充足的情況下，選擇較大的 k 值可以提高抗噪能力。

（2）類別決策時的綜合方法；
對目標對象的類別進行決策，最簡單的就是使用總體占優方法（簡單投票，票數最多的一類勝出）。稍微復雜一點，考慮近鄰中每個點與目標對象的距離不同，對決策的份量進行加權考慮。

（3）距離測量標準的選擇。
距離測量的標准一般選擇 歐幾里得距離 或者 曼哈頓距離 。

簡單例子

Ⅲ K-means 與KNN 聚類演算法

        K-means 演算法屬於聚類演算法的一種。聚類演算法就是把相似的對象通過靜態分類方法分成不同的組別或者更多的子集（subset），這樣讓在同一個子集中的成員對象都有相似的一些屬性。聚類演算法的任務是將數據集劃分為多個集群。在相同集群中的數據彼此會比不同集群的數據相似。通常來說，聚類演算法的目標就是通過相似特徵將數據分組並分配進不同的集群中。

K-means 聚類演算法是一種非監督學習演算法，被用於非標簽數據（data without defined categories or groups）。該演算法使用迭代細化來產生最終結果。演算法輸入的是集群的數量 K 和數據集。數據集是每個數據點的一組功能。  演算法從 Κ 質心的初始估計開始，其可以隨機生成或從數據集中隨機選擇 。然後演算法在下面兩個步驟之間迭代：

每個質心定義一個集群。在此步驟中，基於平方歐氏距離將每個數據點分配到其最近的質心。更正式一點， ci  屬於質心集合  C  ，然後每個數據點  x  基於下面的公式被分配到一個集群中。

在此步驟中，重新計算質心。這是通過獲取分配給該質心集群的所有數據點的平均值來完成的。公式如下：

K-means 演算法在步驟 1 和步驟 2 之間迭代，直到滿足停止條件（即，沒有數據點改變集群，距離的總和最小化，或者達到一些最大迭代次數）。

上述演算法找到特定預選 K 值和數據集標簽。為了找到數據中的集群數，用戶需要針對一系列 K 值運行 K-means 聚類演算法並比較結果。通常，沒有用於確定 K 的精確值的方法，但是可以使用以下技術獲得准確的估計。

Elbow point 拐點方法

通常用於比較不同 K 值的結果的度量之一是數據點與其聚類質心之間的平均距離。由於增加集群的數量將總是減少到數據點的距離，因此當 K 與數據點的數量相同時，增加 K 將總是減小該度量，達到零的極值。因此，該指標不能用作唯一目標。相反，繪制了作為 K 到質心的平均距離的函數，並且可以使用減小率急劇變化的「拐點」來粗略地確定 K 。

DBI（Davies-Bouldin Index）

DBI 是一種評估度量的聚類演算法的指標，通常用於評估 K-means 演算法中 k 的取值。簡單的理解就是：DBI 是聚類內的距離與聚類外的距離的比值。所以，DBI 的數值越小，表示分散程度越低，聚類效果越好。

還存在許多用於驗證 K 的其他技術，包括交叉驗證，信息標准，信息理論跳躍方法，輪廓方法和 G 均值演算法等等。

需要提前確定 K 的選值或者需嘗試很多 K 的取值

數據必須是數字的，可以通過歐氏距離比較

對特殊數據敏感，很容易受特殊數據影響

對初始選擇的質心/中心（centers）敏感

之前介紹了  KNN （K 鄰近）演算法 ，感覺這兩個演算法的名字很接近，下面做一個簡略對比。

K-means  ：

聚類演算法

用於非監督學習

使用無標簽數據

需要訓練過程

K-NN ：

分類演算法

用於監督學習

使用標簽數據

沒有明顯的訓練過程

鄰近演算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。Cover和Hart在1968年提出了最初的鄰近演算法。KNN是一種分類(classification)演算法，它輸入基於實例的學習（instance-based learning），屬於懶惰學習（lazy learning）即KNN沒有顯式的學習過程，也就是說沒有訓練階段，數據集事先已有了分類和特徵值，待收到新樣本後直接進行處理。與急切學習（eager learning）相對應。

KNN是通過測量不同特徵值之間的距離進行分類。 

思路是：如果一個樣本在特徵空間中的k個最鄰近的樣本中的大多數屬於某一個類別，則該樣本也劃分為這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

提到KNN，網上最常見的就是下面這個圖，可以幫助大家理解。

我們要確定綠點屬於哪個顏色（紅色或者藍色），要做的就是選出距離目標點距離最近的k個點，看這k個點的大多數顏色是什麼顏色。當k取3的時候，我們可以看出距離最近的三個，分別是紅色、紅色、藍色，因此得到目標點為紅色。

演算法的描述：

1）計算測試數據與各個訓練數據之間的距離；

2）按照距離的遞增關系進行排序；

3）選取距離最小的K個點；

4）確定前K個點所在類別的出現頻率；

5）返回前K個點中出現頻率最高的類別作為測試數據的預測分類

二、關於 K 的取值

K：臨近數，即在預測目標點時取幾個臨近的點來預測。

K值得選取非常重要，因為：

如果當K的取值過小時，一旦有雜訊得成分存在們將會對預測產生比較大影響，例如取K值為1時，一旦最近的一個點是雜訊，那麼就會出現偏差，K值的減小就意味著整體模型變得復雜，容易發生過擬合；

如果K的值取的過大時，就相當於用較大鄰域中的訓練實例進行預測，學習的近似誤差會增大。這時與輸入目標點較遠實例也會對預測起作用，使預測發生錯誤。K值的增大就意味著整體的模型變得簡單；

如果K==N的時候，那麼就是取全部的實例，即為取實例中某分類下最多的點，就對預測沒有什麼實際的意義了；

K的取值盡量要取奇數，以保證在計算結果最後會產生一個較多的類別，如果取偶數可能會產生相等的情況，不利於預測。

K的取法：

 常用的方法是從k=1開始，使用檢驗集估計分類器的誤差率。重復該過程，每次K增值1，允許增加一個近鄰。選取產生最小誤差率的K。

一般k的取值不超過20，上限是n的開方，隨著數據集的增大，K的值也要增大。

三、關於距離的選取

距離就是平面上兩個點的直線距離

關於距離的度量方法，常用的有：歐幾里得距離、餘弦值（cos）, 相關度 （correlation）, 曼哈頓距離 （Manhattan distance）或其他。

Euclidean Distance 定義：

兩個點或元組P1=（x1，y1）和P2=（x2，y2）的歐幾里得距離是

距離公式為：（多個維度的時候是多個維度各自求差）

四、總結

KNN演算法是最簡單有效的分類演算法，簡單且容易實現。當訓練數據集很大時，需要大量的存儲空間，而且需要計算待測樣本和訓練數據集中所有樣本的距離，所以非常耗時

KNN對於隨機分布的數據集分類效果較差，對於類內間距小，類間間距大的數據集分類效果好，而且對於邊界不規則的數據效果好於線性分類器。

KNN對於樣本不均衡的數據效果不好，需要進行改進。改進的方法時對k個近鄰數據賦予權重，比如距離測試樣本越近，權重越大。

KNN很耗時，時間復雜度為O(n)，一般適用於樣本數較少的數據集，當數據量大時，可以將數據以樹的形式呈現，能提高速度，常用的有kd-tree和ball-tree。

Ⅳ k近鄰演算法的案例介紹

如 上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。 於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN 演算法本身簡單有效，它是一種 lazy-learning 演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間復雜度為O(n)。
KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
K 近鄰演算法使用的模型實際上對應於對特徵空間的劃分。K 值的選擇，距離度量和分類決策規則是該演算法的三個基本要素： K 值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。 該演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。 KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
實現 K 近鄰演算法時，主要考慮的問題是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

Ⅳ KNN演算法-4-演算法優化-KD樹

KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。

Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。

k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。

必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：

首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。

常規的k-d tree的構建過程為：

對於構建過程，有兩個優化點：

例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：

如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。

如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：

kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。

如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。

首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。

以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。

接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。

以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。

遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。

舉例：查詢點（2.1,3.1）

星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。

舉例：查詢點（2，4.5）

一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：

上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。

一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：

但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：

研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。

同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。

Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。

Ⅵ 2 Kd樹的構造與搜索

實現kNN演算法時，最簡單的實現方法就是線性掃描，正如我們上一章節內容介紹的一樣-> K近鄰演算法 ，需要計算輸入實例與每一個訓練樣本的距離。當訓練集很大時，會非常耗時。

為了提高kNN搜索的效率，可以考慮使用特殊的結構存儲訓練數據，以減少計算距離的次數，KD-Tree就是其中的一種方法。

K維空間數據集
其中

隨機生成 13 個點作為我們的數據集

首先先沿 x 坐標進行切分，我們選出 x 坐標的中位點，獲取最根部節點的坐標

並且按照該點的x坐標將空間進行切分，所有 x 坐標小於 6.27 的數據用於構建左分支，x坐標大於 6.27 的點用於構建右分支。

在下一步中 ,對應 y 軸，左右兩邊再按照 y 軸的排序進行切分，中位點記載於左右枝的節點。得到下面的樹，左邊的 x 是指這該層的節點都是沿 x 軸進行分割的。

空間的切分如下

下一步中 ，對應 x 軸，所以下面再按照 x 坐標進行排序和切分，有

最後只剩下了葉子結點，就此完成了 kd 樹的構造。

輸入：已構造的kd樹，目標點x
輸出：x的k個最近鄰集合L

KD-Tree的平均時間復雜度為 ，N為訓練樣本的數量。

KD-Tree試用於訓練樣本數遠大於空間維度的k近鄰搜索。當空間維數接近訓練樣本數時，他的效率會迅速下降，幾乎接近線性掃描。

設我們想查詢的點為 p=(−1,−5)，設距離函數是普通的距離，我們想找距離目標點最近的 k=3 個點。如下：

首先我們按照構造好的KD-Tree，從根結點開始查找

和這個節點的 x 軸比較一下，p 的 x 軸更小。因此我們向左枝進行搜索：

接下來需要對比 y 軸

p 的 y 值更小，因此向左枝進行搜索：

這個節點只有一個子枝，就不需要對比了。由此找到了葉子節點 (−4.6,−10.55)。

在二維圖上是藍色的點

此時我們要執行第二步，將當前結點插入到集合L中，並記錄下 L=[(−4.6,−10.55)]。訪問過的節點就在二叉樹上顯示為被劃掉的好了。

然後執行第三步，不是最頂端節點。我回退。上面的結點是 (−6.88,−5.4)。

執行 3a，因為我們記錄下的點只有一個，小於 k=3，所以也將當前節點記錄下，插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4)].。 因為當前節點的左枝是空的，所以直接跳過，繼續回退，判斷不是頂部根節點

由於還是不夠三個點，於是將當前點也插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)]。

此時發現，當前節點有其他的分枝，執行3b，計算得出 p 點和 L 中的三個點的距離分別是 6.62, 5.89, 3.10，但是 p 和當前節點的分割線的距離只有 2.14，小於與 L 的最大距離：

因此，在分割線的另一端可能有更近的點。於是我們在當前結點的另一個分枝從頭執行步驟1。好，我們在紅線這里：

此時處於x軸切分，因此要用 p 和這個節點比較 x 坐標:

p 的 x 坐標更大，因此探索右枝 (1.75,12.26)，並且發現右枝已經是最底部節點，執行步驟2與3a。

經計算，(1.75,12.26) 與 p 的距離是 17.48，要大於 p 與 L 的距離，因此我們不將其放入記錄中。

然後 回退，判斷出不是頂端節點，往上爬。

執行3a，這個節點與 p 的距離是 4.91，要小於 p 與 L 的最大距離 6.62。

因此，我們用這個新的節點替代 L 中離 p 最遠的 (−4.6,−10.55)。

然後3b，我們比對 p 和當前節點的分割線的距離

這個距離小於 L 與 p 的最大距離，因此我們要到當前節點的另一個枝執行步驟1。當然，那個枝只有一個點。

計算距離發現這個點離 p 比 L 更遠，因此不進行替代。

然後回退，不是根結點，我們向上爬

這個是已經訪問過的了，所以再向上爬

再爬

此時到頂點了 。所以完了嗎？當然不，還要執行3b呢。現在是步驟1的回合。

我們進行計算比對發現頂端節點與p的距離比L還要更遠，因此不進行更新。

然後計算 p 和分割線的距離發現也是更遠。

因此也不需要檢查另一個分枝。

判斷當前節點是頂點，因此計算完成！輸出距離 p 最近的三個樣本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)]。

聲明：此文章為本人學習筆記，參考於： https://zhuanlan.hu.com/p/23966698

Ⅶ knn是什麼意思

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。

在應用KNN演算法解決問題的時候，要注意兩個方面的問題——樣本權重和特徵權重。利用SVM來確定特徵的權重，提出了基於SVM的特徵加權演算法（FWKNN，featureweightedKNN）。實驗表明，在一定的條件下，FWKNN能夠極大地提高分類准確率。

(7)knn演算法訓練時間復雜度擴展閱讀：

KNN（K- Nearest Neighbor）法即K最鄰近法，最初由 Cover和Hart於1968年提出，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路非常簡單直觀：

如果一個樣本在特徵空間中的K個最相似（即特徵空間中最鄰近）的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

Ⅷ 機器學習中演算法的優缺點之最近鄰演算法

機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為KNN。我們在學習機器學習知識的時候一定要學習這種演算法，其實不管是什麼演算法都是有自己的優缺點的，KNN演算法也不例外，在這篇文章中我們就詳細的給大家介紹一下KNN演算法的優缺點，大家一定要好好學起來喲。
說到KNN演算法我們有必要說一下KNN演算法的主要過程，KNN演算法的主要過程有四種，第一就是計算訓練樣本和測試樣本中每個樣本點的距離，第二個步驟就是對上面所有的距離值進行排序(升序)。第三個步驟就是選前k個最小距離的樣本。第四個步驟就是根據這k個樣本的標簽進行投票，得到最後的分類類別。
那麼大家是否知道如何選擇一個最佳的K值，這取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一般來說，一個較好的K值可通過各種啟發式技術來獲取，比如說交叉驗證。另外雜訊和非相關性特徵向量的存在會使K近鄰演算法的准確性減小。近鄰演算法具有較強的一致性結果，隨著數據趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。
那麼KNN演算法的優點是什麼呢？KNN演算法的優點具體體現在六點，第一就是對數據沒有假設，准確度高，對outlier不敏感。第二就是KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練。第三就是KNN理論簡單，容易實現。第四就是理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。第五就是可用於非線性分類。第六就是訓練時間復雜度為O(n)。由此可見，KNN演算法的優點是有很多的。
那麼KNN演算法的缺點是什麼呢？這種演算法的缺點具體體現在六點，第一就是樣本不平衡時，預測偏差比較大。第二就是KNN每一次分類都會重新進行一次全局運算。第三就是k值大小的選擇沒有理論選擇最優，往往是結合K-折交叉驗證得到最優k值選擇。第四就是樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）效果差。第五就是需要大量內存。第六就是對於樣本容量大的數據集計算量比較大。
正是由於這些優點和缺點，KNN演算法應用領域比較廣泛，在文本分類、模式識別、聚類分析，多分類領域中處處有KNN演算法的身影。
在這篇文章中我們給大家介紹了很多關於KNN演算法的相關知識，通過對這些知識的理解相信大家已經知道該演算法的特點了吧，希望這篇文章能夠幫助大家更好的理解KNN演算法。

Ⅸ KNN庫簡介

機器學習經典庫scikit-learn中的sklearn.neighbors包集成了近鄰法相關的演算法，KNN分類樹演算法使用KNeighborsClassifier，回歸樹使用KNeighborsRegressor。除此之外，還有KNN的擴展，即限定半徑最近鄰分類樹RadiusNeighborsClassifier和限定半徑最近鄰回歸樹RadiusNeighborsRegressor，以及最近質心分類演算法NearestCentroid。

在這些演算法中，KNN分類和回歸的類參數完全一樣。限定半徑最近鄰法分類和回歸的類的主要參數也和KNN基本一樣。比較特別是的最近質心分類演算法，由於它是直接選擇最近質心來分類，所以僅有兩個參數，距離度量和特徵選擇距離閾值。

限定半徑最近鄰演算法，即樣本中某系類別的樣本非常的少，甚至少於K，這導致稀有類別樣本在找K個最近鄰的時候，會把距離其實較遠的其他樣本考慮進來，而導致預測不準確。為了解決這個問題，我們限定最近鄰的一個最大距離，也就是說，我們只在一個距離范圍內搜索所有的最近鄰，這避免了上述問題。這個距離我們一般稱為限定半徑。

最近質心演算法首先把樣本按輸出類別歸類。對於第 L類的Cl個樣本。它會對這Cl個樣本的n維特徵中每一維特徵求平均值，最終該類別所有維度的n個平均值形成所謂的質心點。對於樣本中的所有出現的類別，每個類別會最終得到一個質心點。當我們做預測時，僅僅需要比較預測樣本和這些質心的距離，最小的距離對於的質心類別即為預測的類別。這個演算法通常用在文本分類處理上。

KNN的主要優點有：

1） 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸

2） 可用於非線性分類

3） 訓練時間復雜度比支持向量機之類的演算法低，僅為O(n)

4） 和樸素貝葉斯之類的演算法比，對數據沒有假設，准確度高，對異常點不敏感

5） 由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合

6）該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分

KNN的主要缺點有：

1）計算量大，尤其是特徵數非常多的時候

2）樣本不平衡的時候，對稀有類別的預測准確率低

3）KD樹，球樹之類的模型建立需要大量的內存

4）使用懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的演算法慢

5）相比決策樹模型，KNN模型可解釋性不強