通常在分類任務中可以使用“投票法”，即選擇這k個示例中出現頻率最高的標簽類別作為預測結果；在回歸任務中，可以使用“平均法”，即使用這k個示例的真實值輸出標記的平均值作為預測結果；還可以根據距離進行加權平均或加權投票，距離越近，示例的權重越大。
k-最近鄰方法沒有顯式的學習過程。事實上，它是懶惰學習的著名代表。這種學習技術只在訓練階段保存樣本，訓練時間成本為零，收到測試樣本後再進行處理。
KNN壹般采用歐氏距離，也可以采用其他距離度量。壹般Lp距離為:
KNN中K值的選取對K最近鄰算法的結果有很大影響。如果選擇較小的k值，則相當於使用較小字段中的訓練示例進行預測。“學習”的近似誤差（近似誤差:可以理解為現有訓練集的訓練誤差）將減少，只有與輸入示例接近或相似的訓練示例才會對預測結果起作用。同時，問題是“學習”的估計誤差會增加。換句話說，k值的降低意味著整體模型變得復雜並且容易過擬合。
如果選擇較大的k值，則相當於使用較大領域中的訓練示例進行預測。它的優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增加。此時，遠離輸入示例的訓練示例也會作用於預測器，使預測錯誤，k值的增加意味著整體模型變得簡單。
在實際應用中，k的值通常是壹個相對較小的值，例如，交叉驗證方法用於選擇k的最佳值。經驗法則:k通常低於訓練樣本數的平方根
1.計算測試對象到訓練集中每個對象的距離。
2.按距離排序。
3.選擇與當前測試對象最近的K個訓練對象作為測試對象的鄰居。
4.統計這K個鄰居的類別頻率。
5.K個鄰居中出現頻率最高的類別是測試對象的類別。
輸入X可以采用兩種數據結構，BallTree或KDTree，以優化計算效率，並且可以在實例化KNeighborsClassifier時指定。
KDTree
基本思想是，如果A點離B點很遠，B點離C點很近，則可以知道A點和C點非常遠，並且不需要顯式計算它們的距離。這樣，最近鄰搜索的計算成本可以降低到O【dn log（N）】或更低。這是在大樣本數n中暴力搜索性能的顯著提高。KD樹的構建非常快，並且對於低維（D
KD樹是壹種二叉樹結構，它沿數據軸遞歸劃分參數空間，並將其劃分為嵌入數據點的嵌套各向異性區域。KD樹的構建非常快:因為它只需要沿著數據軸進行分區，所以不需要計算D維距離。壹旦構造完成，查詢點的最近鄰距離的計算復雜度僅為O【log（N）】。雖然KD樹方法適合於低維（D
KD樹的特性適合使用歐氏距離。
鮑爾樹公司
BallTree解決了KDTree在高維時效率低的問題。用這種方法構建的樹比KD樹消耗更多的時間，但這種數據結構對於高度結構化的數據非常有效，即使在高維空間中也是如此。
KD樹是通過用中位數依次劃分K維坐標軸而構建的樹。球樹以質心c和半徑r劃分樣本空間，每個節點是壹個超球。換句話說，對於目標空間（q，r），將遍歷和搜索被超球面截斷的所有子超球面中的所有子空間。
BallTree通過使用三角不等式減少最近鄰搜索的候選點:| x+y |《= | x |+| y |使用此設置，測試點和質心之間的單個距離的計算足以確定節點中所有點的距離的下限和上限。由於球樹節點的球形幾何形狀，其在高維度中的性能超過了KD-tree，盡管實際性能高度依賴於訓練數據的結構。
BallTree適用於更壹般的距離。
1優勢
沒有非常簡單的分類算法，人性化，易懂易實現。
適合處理多分類問題，如推薦用戶
它可用於數值數據和離散數據，並可用於分類和回歸。
對異常值不敏感
2.不足之處
這是壹種時間復雜度很高的懶惰算法，因為它需要計算未知樣本到所有已知樣本的距離。
樣品平衡高度依賴。當樣本在極端情況下不平衡時，分類肯定會有偏差，可以通過調整樣本權重來改善。
可解釋性差，無法給出決策樹這樣的規則。
向量的維數越高，歐氏距離的區分能力越弱。
樣本空間太大不適合，因為計算量太大，預測慢。
文本分類
用戶推薦
回歸問題
1）從所有觀察示例中隨機提取K個觀察點作為聚類中心點，然後遍歷剩余的觀察點以找到最近的聚類中心點並將其添加到聚類中。這樣，我們就有了壹個初步的聚類結果，這是壹個叠代的過程。
2）我們的每個聚類中心至少有壹個觀察實例，這樣我們可以找到每個聚類的中心點（均值）作為新的聚類中心，然後遍歷所有觀察點以找到最近的中心點並將其添加到聚類中。然後繼續運行2）。
3）重復這種方式，直到從前面兩次叠代中獲得的聚類中心點完全相同。
該算法的時間復雜度為O（tkmn），其中t為叠代次數，k為聚類數，m為記錄數，n為維數；
空間復雜度:O（（m+k）n），其中k是聚類數，m是記錄數，n是維度。
適用範圍:
K-menas算法試圖找到最小化微小誤差準則函數的聚類。當潛在聚類形狀為凸形，聚類之間差異明顯，且聚類大小相近時，聚類結果較為理想。如前所述，該算法的時間復雜度為O（tkmn），與樣本數呈線性關系。因此，該算法在處理大型數據集時非常高效且可擴展。然而，該算法不僅需要預先確定聚類數k並且對初始聚類中心敏感，而且經常以局部優化結束，並且對“噪聲”和孤立點敏感，並且該方法不適合尋找具有非凸形狀的聚類或大小差異較大的聚類。
1）首先，該算法只能找到局部最優聚類，而不能找到全局最優聚類。此外，該算法的結果非常依賴於初始隨機選擇的聚類中心的位置。我們多次運行該算法，使用不同的隨機生成的聚類中心，然後通過evaluate（C）函數評估它們各自的結果C，並在多個結果中選擇evaluate（C）值最小的壹個。k-means++算法在選擇初始種子時的基本思想是初始聚類中心之間的相互距離應盡可能遠。
2）初始k值的選擇。第壹個想法是從壹個初始值到壹個最大值，通過k-means算法對每個值進行聚類，並通過評估函數計算最佳聚類結果，這個K就是最優K .我們首先想到上面使用的evaluate（C）。但k越大，聚類中心越多，顯然每個觀測點與其中心的距離平方和會越小，這在實踐中也得到了驗證。這個問題將在第四節的實驗結果分析中詳細討論。
3）關於性能。在原始算法中，每個觀測點與所有聚類中心之間的距離是在每次叠代中計算的。有什麽方法可以提高效率？是的，妳可以使用k-d樹或球樹的數據結構來提高算法的效率。在壹定條件下，對於某個區域內的觀測點，可以將該區域內的所有點放入最近的簇中，而無需遍歷每個觀測點。這將在第三部分詳細介紹。
相似性:它們都包括在給定壹個點的數據集中找到最近的點的過程。也就是說，兩者都使用了NN（Nears Neighbor）算法，並且壹般使用KD樹來實現NN。
K-d樹和球樹
1）k-d樹【5】
將N維特征的觀察示例放入N維空間。k-d樹通過壹種算法壹次選擇壹個特征（坐標軸），並使用其值之壹作為邊界來制作超平面，將當前的所有觀察點分成兩部分，然後對每個部分使用相同的方法，直到達到某個條件。
在上面的陳述中，有幾個要點將在下面詳細解釋:（1）選擇特征（坐標軸）的方法（2）哪壹個特征是邊界（3）算法在什麽條件下結束。
（1）選擇特征的方法
計算當前觀測點集中每個特征的方差，選擇壹個方差最大的特征，然後繪制壹個垂直於該特征的超平面，將所有觀測點分成兩組。
（2）坐標軸超平面的具體位置是垂直選擇的，以特征值為邊界。
第壹個由每個點的中值方差限定。這將使構建的樹非常平衡，並將均勻地分開壹組。這樣做的問題是，如果點的分布非常嚴重傾斜，選擇中間值將導致同壹方向的連續分割，形成細長的超矩形。
另壹種方法是計算這些點和坐標軸的平均值，並選擇最接近該平均值的點作為超平面和坐標軸的交點。這樣，樹將不會完全平衡，但區域將傾向於積極劃分，並且連續劃分更有可能發生在不同的方向上。
（3）什麽條件下算法結束？
實際上，該算法直到葉節點僅包含兩個點時才結束。您可以設置壹個預設的最小值，並在達到該最小值時結束算法。
在圖6中，星號表示目標點。我們在k-d樹中找到該點所在的區域後，依次計算包含在該區域中的點的距離以找到最近的點（黑點）。如果在其他區域有更近的點，我們必須在壹個以這兩個點為半徑的圓中。假設這個圓包含如圖所示的其他區域。先看這個區域內兄弟節點對應的區域，不與圓重疊；然後查看其父節點的兄弟節點的相應區域。從其子節點的相應區域中找到它（該圖確實與該父節點的兄弟節點的子節點的相應區域重疊）。找出其中是否有更近的節點。
k-d樹的優點是可以增量更新。可以不斷增加新的觀察點。找到新觀察點所在的區域。如果是空的，添加它。否則，沿著最長的邊劃分區域，使其接近正方形。這將破壞樹的平衡，並使該區域不利於找到最近的鄰居。當樹的深度達到壹定值時，我們可以重建樹。
然而，k-d樹也有問題。矩形不是在這裏使用它們的最佳方式。傾斜的數據集導致了保持樹的平衡和保持區域的方形特征之間的沖突。此外，矩形甚至正方形都不是在這裏使用的完美形狀，因為它的角。如果圖6中的圓更大，即黑點離目標點更遠，則圓將與左上角的矩形相交，並且需要檢查多壹個區域中的點，並且該區域是當前區域中父節點的兄弟節點的子節點。
為了解決上述問題，我們引入了球樹。
2）球樹
解決上述問題的方法是使用超球面代替超矩形來劃分區域。球面的使用可能會導致球面之間的重疊，但這無關緊要。球樹是壹個k維超球來覆蓋這些觀察點並將它們放在樹中。圖7（a）示出了在二維平面中具有16個觀察示例的圖，圖7（b）示出了其對應的球樹，其中節點中的數字表示觀察點的數量。
不同層次的圓以不同的風格繪制。樹中的每個節點對應壹個圓，節點數表示該區域包含的觀測點數量，但不壹定是圖中該區域包含的點數，因為存在重疊，壹個觀測點只能屬於壹個區域。實際球樹的節點保持中心和半徑。葉節點存儲它包含的觀察點。
使用球樹時，首先從上到下找到包含目標的葉節點，並找到離該節點最近的觀察點。該距離是最近鄰距離的上限。檢查其兄弟節點是否包含小於此上限的觀測點。方法是:如果目標點與兄弟節點的中心之間的距離大於圓心加上先前上界的值，則兄弟節點不能包含所需的觀察點。（圖8）否則，檢查這個兄弟節點是否包含合格的觀察點。
那麽，球樹的分割算法是什麽？
選擇距離當前中心最遠的觀察點i1和距離i1最遠的觀察點i2，將圓中距離這兩個點最近的所有觀察點分配給這兩個聚類的中心，然後計算每個聚類的中心點以及包括其所屬所有觀察點的最小半徑。用n個觀察點分割超圓只需要線性時間。
和k-d樹壹樣，如果壹個節點包含的觀測點達到預設的最小值，那麽這個頂點就不能再被分割。