k近鄰演算法java

A. k近鄰&kd樹

k近鄰演算法是懶惰學習的代表演算法。之所以說k近鄰懶惰，是因為它沒有顯示的訓練過程。它的思路很簡單， 手頭有一些帶標簽的樣本，現在給定一個新的樣本，找出已有樣本中距離新樣本最近的k個樣本點，然後取這k個樣本點標簽的投票結果。

k近鄰演算法本身並不復雜，但有幾個細節需要注意：

（1）距離度量

不同的距離度量可能產生不同的k近鄰，從而直接影響預測結果。至於度量的選取要結合應用場景， 關鍵在於我們需要知道在特定場景中如何量化兩樣本之間的相似度。

（2）k值選擇

k值的選擇沒有經驗性的方法，一般只能通過交叉驗證來選取合適的k值。

如果k值選擇較小，就相當於用較小的鄰域中的訓練實例進行預測，「學習」的近似誤差會減小，只有與輸入實例較近的訓練實例才會對預測起作用，但估計誤差會增大，預測結果會對近鄰的實例點非常敏感，如果近鄰的實例點恰巧是雜訊，預測就會出錯。相反如果k值選擇較大，就相當於用較大的領域中的訓練實例進行預測，近似誤差會增大，但估計誤差會減小。

對於k近鄰法來說，k越大模型越簡單，這一點乍一看不容易理解，但其實我們可以考慮極端情況k=N（N為樣本數），此時任何新樣本都會被歸入當前樣本集中實例最多的類別，從而丟失大量信息。反之，k越小模型越復雜，模型將面臨過擬合風險。

（3）投票法

k近鄰使用多數表決亮鬧的投票法看起來十分自然，但我們也可以從 最小化經驗誤差 的角度來理解，如果分類的損失函數為0-1損失函數，則誤分類概率為：

對於給定實例 ，其最近鄰的k個訓練實例構成集合 ，若涵蓋 的區域的類別是 ，則誤分類概率為：

要使誤分類率最小即經驗風險最小，就要使 最大，這正是投票法（多數表決）所做的事情。

kd樹是一種對k維空間中的實例點進行儲存以便對其進行快速檢索的樹形數據結構。 kd樹是二叉樹，表示對k維空間的一個劃分。構造kd樹相當於不斷用垂直於坐標軸的超平面將k維空間切分，構成一系列k維超矩形區域。

構造平衡kd樹的流程 如下：

輸入：k維空間數據集

（1）構造根結點，根結點對應於包含 的k維空間的超矩形區域。

（2）對深度為 的結點，選擇 為切分的坐標軸（ ），以該結點區域中所有實例的 坐標的中位數為切分點，將該結點對應的超矩形區域劃分為兩個子區域，切分由通過切分點並與坐標軸 垂直的超平面實現。

（3）重復（2）直至劃分得到的兩個子區域中沒有實例存在為止。

用kd樹進行最近鄰搜索的流程 如下：

輸入：構造好的kd樹，目標節點x

（1）在kd樹中找到包含目標節點 的葉結點：從根結點出發，遞歸地向下訪問kd樹。若目標 當前維的坐標小於切分點坐標則移動敬物罩到左子結點，否則移動到右子結點，直至子結點為葉結點為止。

（2）以此葉結點為「當前最近點」。

（3）遞歸地向上回退：

（4）當回退到根結點，搜索結束，此時的「當前最近點」即為 的最近鄰點。螞檔

以上就是利用kd樹進行最近鄰搜索的過程，同樣的方法可以推廣到k近鄰。現在我們來思考一下這個演算法的本質。

其實我個人理解的是， kd樹的構造就是二分法在k維的應用。 但是不太相同的是，kd樹演算法並不是選定一個軸後不斷二分直至結束，而是做一次二分換一個軸，這是因為如果我們只選定一個軸做二分得到的結果並不能反映各樣本之間距離的遠近，而兼顧各個軸則能一定程度上度量樣本之間的距離。

我們可以想像3維的情況，kd樹最終會形成一系列的小正方體，我們要想找距離一個新樣本點最近的樣本點，只需要找到新樣本點所在的小正方體，然後check這個小正方體中的樣本以及和這個小正方體 相鄰 的小正方體中的樣本哪個距離新樣本最近即可（相鄰這個概念是很重要的，為便於理解，考慮在一維的情況下，此過程為找到新樣本所在區間，然後檢查此區間以及左右相鄰區間中的樣本點即可）。而 相鄰 這個概念剛好和kd樹的構造過程相符，我們不斷回退的過程其實就是檢查 各個不同方向上 的相鄰超矩形的過程。這個過程十分高效，不難看出，平衡kd樹尋找最近鄰的復雜度是 。

B. K-近鄰演算法（K-NN）

給定一個訓練數據集，對於新的輸入實例， 根據這個實例最近的 k 個實例所屬的類別來決定其屬於哪一類 。所以相對於其它機器學習模型和演算法，k 近鄰總體上而言是一種非常簡單的方法。

找到與該實例最近鄰的實例，這里就涉及到如何找到，即在特徵向量空間中，我們要採取 何種方式來對距離進行度量 。

距離的度量用在 k 近鄰中我們也可以稱之為 相似性度量 ，即特徵空間中兩個實例點相似程度的反映。在機器學習中，常用的距離度量方式包括歐式距離、曼哈頓距離、餘弦距離以及切比雪夫距離等。 在 k 近鄰演算法中常用的距離度量方式是歐式距離，也即 L2 距離， L2 距離計算公式如下：

一般而言，k 值的大小對分類結果有著重大的影響。 當選擇的 k 值較小的情況下，就相當於用較小的鄰域中的訓練實例進行預測，只有當與輸入實例較近的訓練實例才會對預測結果起作用。但與此同時預測結果會對實例點非常敏感，分類器抗噪能力較差，因而容易產生過擬合 ，所以一般而言，k 值的選擇不宜過小。但如果選擇較大的 k 值，就相當於在用較大鄰域中的悶鄭握訓練實例進行預測，但相應的分類誤差也會增大，模型整體變得簡單，會產生一定程度的欠擬合。所以一般而言，我們需要 採用交叉驗證的方式來選擇合適的 k 值 。

k 個實例的多數屬於哪叢褲個類，明顯是多數表決的歸類規則。當然還可能使用其他規則，所以第三個關鍵就是 分類決策規則。

回歸：k個實例該屬性值的平均值

它是一個二叉樹的數據結構，方便存儲 K 維空間的數據

KNN 的計算過程是大量計算樣本點之間的距離。為了減少計算距離次數，提升 KNN 的搜索效率，人們提出了 KD 樹（K-Dimensional 的縮寫）。KD 樹是對數據點在 K 維空間中劃分的一種數據結構。在 KD 樹的構造中，每個節點都是 k 維數值點的二叉樹。螞慶既然是二叉樹，就可以採用二叉樹的增刪改查操作，這樣就大大提升了搜索效率。

如果是做分類，你需要引用：from sklearn.neihbors import KNeighborsClassifier
如果是回歸， 需要引用：from sklearn.neighbors import KNeighborsRegressor

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5, weights='uniform', algorithm='auto', leaf_size=30, p=2, metric='minkowski', metric_params=None, n_jobs=None, **kwargs)

C. K-近鄰演算法（KNN）

簡單地說，K-近鄰演算法採用測量不同特徵值之間的距離方法進行分類。

歐氏距離是最常見的距離度量，衡量的是多維空間中各個點之間的絕對距離。公式如下：

身高、體重、鞋子尺碼數據對應性別

導包，機器學習的演算法KNN、數據鳶尾花

獲取訓練樣本 datasets.load_iris()

畫圖研究前兩個特徵和分類之間的關系（二維散點圖只能展示兩個維度）

第二步預測數據：所預測的數據，自己創造，就是上面所顯示圖片的背景點

生成預測數據

對數據進行預測

ocr 光學字元識別（Optical Character Recognition） 我們先做一個基礎班：識別數字

D. 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 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

E. 什麼叫做knn演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的非參數統計方法。

在這兩種情況下，輸入包含特徵空間（Feature Space）中的k個最接近的訓練樣本。

1、在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k=1，則該對象的類別直接由最近的一個節點賦予。

2、在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-均值演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關系。數據標准化可以大大提高該演算法的准確性。

參數選擇

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一個較好的K值能通過各種啟發式技術（見超參數優化）來獲取。

雜訊和非相關性特徵的存在，或特徵尺度與它們的重要性不一致會使K近鄰演算法的准確性嚴重降低。對於選取和縮放特徵來改善分類已經作了很多研究。一個普遍的做法是利用進化演算法優化功能擴展，還有一種較普遍的方法是利用訓練樣本的互信息進行選擇特徵。

在二元（兩類）分類問題中，選取k為奇數有助於避免兩個分類平票的情形。在此問題下，選取最佳經驗k值的方法是自助法。

F. K-近鄰演算法簡介

1.K-近鄰(KNearestNeighbor,KNN)演算法簡介 ：對於一個未知的樣本，我們可以根據離它最近的k個樣本的類別來判斷它的類別。

以下圖為例，對於一個未知樣本綠色小圓，我們可以選取離它最近的3的樣本，其中包含了2個紅色三角形，1個藍色正方形，那麼我們可以判斷綠色小圓屬於紅色三角形這一類。
我們也可以選取離它最近的5個樣本，其中包含了3個藍色正方形，2個紅色三角形，那麼我們可以判斷綠色小圓屬於藍色正方形這一類。

3.API文檔

下面我們來對KNN演算法中的參數項做一個解釋說明：

'n_neighbors'：選取的參考對象的個數（鄰居個數），默認值為5，也可以自己指定數值，但不是n_neighbors的值越大分類效果越好，最佳值需要我們做一個驗證。
'weights': 距離的權重參數，默認uniform。
'uniform': 均勻的權重，所有的點在每一個類別中的權重是一樣的。簡單的說，就是每個點的重要性都是一樣的。
'distance'：權重與距離的倒數成正比，距離近的點重要性更高，對於結果的影響也更大。
'algorithm':運算方法，默認auto。
'auto'：根絕模型fit的數據自動選擇最合適的運算方法。
'ball_tree'：樹模型演算法BallTree
'kd_tree'：樹模型演算法KDTree
'brute'：暴力演算法
'leaf_size'：葉子的尺寸，默認30。只有當algorithm = 'ball_tree' or 'kd_tree'，這個參數需要設定。
'p'：閔可斯基距離，當p = 1時，選擇曼哈頓距離；當p = 2時，選擇歐式距離。
n_jobs：使用計算機處理器數目，默認為1。當n=-1時，使用所有的處理器進行運算。

4.應用案例演示
下面以Sklearn庫中自帶的數據集--手寫數字識別數據集為例，來測試下kNN演算法。上一章，我們簡單的介紹了機器學習的一般步驟：載入數據集 - 訓練模型 - 結果預測 - 保存模型。這一章我們還是按照這個步驟來執行。
[手寫數字識別數據集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

5.模型的方法
每一種模型都有一些它獨有的屬性方法（模型的技能，能做些什麼事），下面我們來了解下knn演算法常用的的屬性方法。

6.knn演算法的優缺點
優點：
簡單，效果還不錯，適合多分類問題
缺點：
效率低（因為要計算預測樣本距離每個樣本點的距離，然後排序），效率會隨著樣本量的增加而降低。

G. 實驗二 K-近鄰演算法及應用

（1）簡單，易於理解，易於實現，無需估計參數。

（2）訓練時間為零。它沒有顯示的訓練，不像其它有監督的演算法會用訓練集train一個模型（也就是擬合一個函數），然後驗證集或測試集用該模型分類。KNN只是把樣本保存起來，收到測試數據時再處理，所以KNN訓練時間為零。

（3）KNN可以處理分類問題，同時天然可以處理多分類問題，適合對稀有事件進行分類。

（4）特別適合於多分類問題(multi-modal,對象具有多個類別標簽)， KNN比SVM的表現要好。

（5）KNN還可以處理回歸問題，也就是預測。

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

（1）計算量太大，尤其是特徵數非常多的時候。每一個待分類文本都要計算它到全體已知樣本的距離，才能得到它的第K個最近鄰點。

（2）可理解性差，無法給出像決策樹那樣的規則。

（3）是慵懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的演算法慢。

（4）樣本不平衡的時候，對稀有類別的預測准確率低。當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。

（5）對訓練數據依賴度特別大，對訓練數據的容錯性太差。如果訓練數據集中，有一兩個數據是錯誤的，剛剛好又在需要分類的數值的旁邊，這樣就會直接導致預測的數據的不準確。

需要一個特別容易解釋的模型的時候。
比如需要向用戶解釋原因的推薦演算法。

通過此次實驗我了解了K近鄰演算法及其思路，該方法的思路是：如果一個樣本在特徵空間中的k個最相似的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
所謂k近鄰演算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的k個實例。

H. 常見的監督學習演算法

一. K-近鄰演算法（k-Nearest Neighbors，KNN）

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

二、決策樹（Decision Trees）

決策樹是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特徵屬性上的測試，每個分支代表這個特徵屬性在某個值域上的輸出，而每個葉節點存放一個類別。

使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。

三、樸素貝葉斯（Naive Bayesian）

貝葉斯分類是一系列分類演算法的總稱，這類演算法均以貝葉斯定理為基礎，故統稱為貝葉斯分類。樸素貝葉斯演算法（Naive Bayesian) 是其中應用最為廣泛的分類演算法之一。樸素貝葉斯分類器基於一個簡單的假定：給定目標值時屬性之間相互條件獨立。

四、邏輯回歸（Logistic Regression）

線性回歸就是根據已知數據集求一線性悔攜函數，使其盡可能擬合數據，讓損失函數最小，常用的拿棚線性碧敏伏回歸最優法有最小二乘法和梯度下降法。而邏輯回歸是一種非線性回歸模型，相比於線性回歸，它多了一個sigmoid函數（或稱為Logistic函數）。

五、AdaBoost

AdaBoost目的就是從訓練數據中學習一系列的弱分類器或基本分類器，然後將這些弱分類器組合成一個強分類器。AdaBoost有一個很突出的特點就是精度很高。

六、神經網路

神經網路從信息處理角度對人腦神經元網路進行抽象，建立某種簡單模型，按不同的連接方式組成不同的網路。

I. KNN演算法，k近鄰

K最近鄰(k-Nearest Neighbour，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。