knn鄰近演算法

Ⅰ knn演算法是什麼

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

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

介紹

KNN演算法本身簡單有效，它是一種lazy-learning演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為n，那麼KNN的分類時間復雜度為O(n)。

KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

Ⅱ knn是什麼意思

knn是鄰近演算法，或者說K最鄰近分類演算法，全稱為K-NearestNeighbor，是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，是K個最近的鄰居的意思，說的是每個樣本都可以用最接近的K個鄰近值來代表。近鄰演算法是將數據集合中每一個記錄進行分類的方法。

knn演算法的核心思想：

如果一個樣本在特徵空間中的K個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

Ⅲ 01 KNN演算法 - 概述

KNN演算法 全稱是K近鄰演算法 （K-nearst neighbors，KNN）

KNN是一種基本的機器學習演算法，所謂K近鄰，就是k個最近的鄰居。即每個樣本都可以用和它 最接近的k個鄰近位置的樣本 來代替。

KNN是個相對比較簡單的演算法，比起之前提過的回歸演算法和分類演算法更容易。如果一個人從來沒有接觸過機器學習的演算法，拿到數據後最容易想到的分類方式就是K近鄰。打個比方：你們想了解我是個怎樣的人，然後你們發現我的身邊關系最密切的朋友是一群逗逼，所以你們可以默認我也是一個逗逼。

KNN演算法即可以應用於 分類演算法 中，也可以應用於 回歸演算法 中。

KNN在做回歸和分類的主要區別，在於最後做預測時候的決策不同。在分類預測時，一般採用 多數表決法 。在做回歸預測時，一般使用 平均值法 。

多數表決法： 分類時，哪些樣本離我的目標樣本比較近，即目標樣本離哪個分類的樣本更接近。

平均值法： 預測一個樣本的平均身高，觀察目標樣本周圍的其他樣本的平均身高，我們認為平均身高是目標樣本的身高。

再舉個例子：
分別根據甜度和脆度兩個特徵來判斷食物的種類。
根據樣本我們普遍發現：
比較甜，比較脆的食物都是水果。
不甜，不太脆的食物是蛋白質。
不甜，比較脆的食物是蔬菜。
於是根據目標的樣本甜度和脆度兩個特徵，我們可以對其進行分類了。

k值的選擇:
先選一個較小的值，然後通過交叉驗證選擇一個合適的最終值。
k越小，即使用較小的領域中的樣本進行預測，訓練誤差會減小，但模型會很復雜，以至於過擬合。
k越大，即使用交大的領域中的樣本進行預測，訓練誤差會增大，模型會變得簡單，容易導致欠擬合。

距離的度量:
使用歐幾里得距離：歐幾里得度量（euclidean metric）（也稱歐氏距離）是一個通常採用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。

決策規劃:
分類：多數表決法、加權多數表決法。
回歸：平均值法、加權平均值法。

加權多數表決法：

平均值法和加權平均值法：
同樣看上面的圖，上方的三個樣本值為3，下面兩個樣本值為2，預測？的值。
如果不考慮加權，直接計算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6

加權平均值：權重分別為1/7和2/7。計算加權平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43

1、蠻力實現(brute)：
計算預測樣本到所有訓練集樣本的距離，然後選擇最小的k個距離，即可得到k個最鄰近點。
缺點：當特徵數多、樣本數多時，演算法的效率比較低。

2、KD樹 (kd_tree)：
首先對訓練數據進行建模，構建KD樹，然後根據建好的模型來獲取鄰近樣本數據。
後續內容會介紹KD樹搜索最小值的方式，讓大家直觀感受到KD樹比蠻力實現要少檢索多少數據。

Ⅳ K-近鄰演算法（KNN）

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

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

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

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

獲取訓練樣本 datasets.load_iris()

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

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

生成預測數據

對數據進行預測

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

Ⅳ 什麼是knn演算法

作為一種非參數的分類演算法，K-近鄰（KNN）演算法是非常有效和容易實現的。它已經廣泛應用於分類、回歸和模式識別等。在應用KNN演算法解決問題的時候，要注意兩個方面的問題——樣本權重和特徵權重。利用SVM來確定特徵的權重，提出了基於SVM的特徵加權演算法（FWKNN,feature
weighted
KNN）。實驗表明，在一定的條件下，FWKNN能夠極大地提高分類准確率。

Ⅵ 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-近鄰演算法簡介

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