近鄰檢索演算法

❶ 什麼叫做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值的方法是自助法。

❷ KNN 演算法-理論篇-如何給電影進行分類

KNN 演算法 的全稱是 K-Nearest Neighbor ，中文為 K 近鄰 演算法，它是基於 距離 的一種演算法，簡單有效。

KNN 演算法 即可用於分類問題，也可用於回歸問題。

假如我們統計了一些 電影數據，包括電影名稱，打鬥次數，接吻次數，電影類型 ，如下：

可以看到，電影分成了兩類，分別是動作片和愛情片。

如果現在有一部新的電影A，它的打鬥和接吻次數分別是80 和7，那如何用KNN 演算法對齊進行分類呢？

我們可以將打鬥次數作為 X 軸 ，接吻次數作為 Y 軸 ，將上述電影數據畫在一個坐標系中，如下：

通過上圖可以直觀的看出，動作電影與愛情電影的分布范圍是不同的。

KNN 演算法 基於距離，它的原理是： 選擇與待分類數據最近的K 個點，這K 個點屬於哪個分類最多，那麼待分類數據就屬於哪個分類 。

所以，要判斷電影A 屬於哪一類電影，就要從已知的電影樣本中，選出距離電影A 最近的K 個點：

比如，我們從樣本中選出三個點（即 K 為 3），那麼距離電影A 最近的三個點是《功夫》，《黑客帝國》和《戰狼》，而這三部電影都是動作電影。因此，可以判斷電影A 也是動作電影。

另外，我們還要處理兩個問題：

關於點之間的距離判斷，可以參考文章 《計算機如何理解事物的相關性》 。

至於K 值的選擇，K 值較大或者較小都會對模型的訓練造成負面影響，K 值較小會造成 過擬合 ，K 值較大 欠擬合 。

因此，K 值的選擇，一般採用 交叉驗證 的方式。

交叉驗證的思路是，把樣本集中的大部分樣本作為訓練集，剩餘部分用於預測，來驗證分類模型的准確度。一般會把 K 值選取在較小范圍內，逐一嘗試K 的值，當模型准確度最高時，就是最合適的K 值。

可以總結出， KNN 演算法 用於分類問題時，一般的步驟是：

如果，我們現在有一部電影B，知道該電影屬於動作電影，並且知道該電影的接吻次數是 7 ，現在想預測該電影的打鬥次數是多少？

這個問題就屬於 回歸問題 。

首先看下，根據已知數據，如何判斷出距離電影B 最近的K 個點。

我們依然設置K 為3，已知數據為：

根據已知數據可以畫出下圖：

圖中我畫出了一條水平線，這條線代表所有接吻次數是7 的電影，接下來就是要找到距離 這條線 最近的三部（K 為 3）動作電影。

可以看到，距離這條水平線最近的三部動作電影是《功夫》，《黑客帝國》和《戰狼》，那麼這三部電影的打鬥次數的平均值，就是我們預測的電影B 的打鬥次數。

所以，電影B 的打鬥次數是：

本篇文章主要介紹了 KNN 演算法 的基本原理，它簡單易懂，即可處理分類問題，又可處理回歸問題。

KNN 演算法 是基於 距離 的一種機器學習演算法，需要計算測試點與樣本點之間的距離。因此，當數據量大的時候，計算量就會非常龐大，需要大量的存儲空間和計算時間。

另外，如果樣本數據分類不均衡，比如有些分類的樣本非常少，那麼該類別的分類准確率就會很低。因此，在實際應用中，要特別注意這一點。

（本節完。）

推薦閱讀：

決策樹演算法-理論篇-如何計算信息純度

決策樹演算法-實戰篇-鳶尾花及波士頓房價預測

樸素貝葉斯分類-理論篇-如何通過概率解決分類問題

樸素貝葉斯分類-實戰篇-如何進行文本分類

計算機如何理解事物的相關性-文檔的相似度判斷

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

❹ k近鄰演算法中關鍵的要素是

k近鄰演算法中關鍵的要素是：k值的選取、鄰居距離的度量和分類決策的制訂。

1.k值的選取：

k近鄰演算法優點很明顯，簡單易用，可解釋性強，但也有其不足之處。例如，「多數表決」會在類別分布偏斜時浮現缺陷。也就是說，k值的選取非常重要，出現頻率較多的樣本將會主導測試點的預測結果。

3.分類決策的制訂：

本質上，分類器就是一個由特徵向量，到預測類別的映射函數。k近鄰演算法的分類流程大致如下三步走：（1）計算待測試樣本與訓練集合中每一個樣本的歐式距離；（2）對每一個距離從小到大排序；（3）選擇前k個距離最短的樣本，分類任務採用「少數服從多數」的表決規則。回歸任務則可採用k個近鄰的平均值舉茄作為預測值。

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

❻ k近鄰演算法特徵值非數字

k-近鄰演算法採用測量不同特徵值之間的距離來進行分類。
優點：精度高，對異常值不敏感，無數據輸入假定。缺點：計算復雜度高、空間復雜度高。適用數據范圍：數值型和分類型。原理：首先，我們必須得有一份含有分類標簽的數據集，為訓練數據集。比如我們要預測用戶是否會流失，那麼分類標簽就是流失和未流失。然後有一份新的數據集，這份數據集並沒有分類標簽，k-近鄰演算法就會將新的數據集和訓練數據集進行比較，從訓練數據集中選出與新數據集每個數據最相近的K個數據，查看這K個數據所屬標簽哪類最多，比如流失，就把新數據集中的那個數據分類為流失。怎麼判斷是否相近呢？K-近鄰是計算不同數據的距離。k-近鄰演算法的原理偽代碼。
對未知類別屬性的數據集中的每個數據點依次執行以下操作：(1)計算已知類別數據集中的點與當前點之間的距離。(2)按照距離遞增次序排序。(3)選出與當前距離最近的K個點。(4)統計出K個點所屬類別的頻率。(5)返回K個點出現頻率最高的的類別作為當前點的預測類別