介紹

定義

　　在模式識(shí)別領(lǐng)域中，最近鄰居法（k-Nearest Neighbors algorithm，KNN算法，又譯K-近鄰算法）是一種用于分類和回歸的非參數(shù)統(tǒng)計(jì)方法。

• k-NN分類
  輸入：包含特征空間中的 k 個(gè)最接近的訓(xùn)練樣本。
  輸出：一個(gè)分類族群。

• k-NN回歸
  輸入：包含特征空間中的 k 個(gè)最接近的訓(xùn)練樣本。
  輸出：該對象的屬性值。該值是其 k 個(gè)最近鄰居的值的平均值。

起源

　　TODO

優(yōu)點(diǎn)

1. 簡單，易于理解，易于實(shí)現(xiàn)，無需估計(jì)參數(shù)，無需訓(xùn)練；
2. 適合對稀有事件進(jìn)行分類；
3. 特別適合于多分類問題（multi-modal，對象具有多個(gè)類別標(biāo)簽）。

缺點(diǎn)

1. 主要的不足：當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。 該算法只計(jì)算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無論怎樣，數(shù)量并不能影響運(yùn)行結(jié)果。
2. 計(jì)算量較大，因?yàn)閷γ恳粋€(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。
3. 可理解性差，無法給出像決策樹那樣的規(guī)則。

應(yīng)用領(lǐng)域

　　文本分類，聚類分析，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)，預(yù)測分析，減少維度，模式識(shí)別，圖像處理

相關(guān)

　　然而k最近鄰居法因?yàn)橛?jì)算量相當(dāng)?shù)拇?，所以相?dāng)?shù)暮臅r(shí)，Ko與Seo提出一算法TCFP（text categorization using feature projection），嘗試?yán)锰卣魍队胺▉斫档团c分類無關(guān)的特征對于系統(tǒng)的影響，并借此提升系統(tǒng)效能，其實(shí)實(shí)驗(yàn)結(jié)果顯示其分類效果與k最近鄰居法相近，但其運(yùn)算所需時(shí)間僅需k最近鄰居法運(yùn)算時(shí)間的五十分之一。
　　除了針對文件分類的效率，尚有研究針對如何促進(jìn)k最近鄰居法在文件分類方面的效果，如Han等人于2002年嘗試?yán)秘澬姆?，針對文件分類?shí)做可調(diào)整權(quán)重的k最近鄰居法WAkNN（weighted adjusted k nearest neighbor），以促進(jìn)分類效果；而Li等人于2004年提出由于不同分類的文件本身有數(shù)量上有差異，因此也應(yīng)該依照訓(xùn)練集合中各種分類的文件數(shù)量，選取不同數(shù)目的最近鄰居，來參與分類。

解法

• 思路
  如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

• 步驟

  1. 準(zhǔn)備數(shù)據(jù)，對數(shù)據(jù)進(jìn)行預(yù)處理
  2. 選用合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)和測試元組
  3. 設(shè)定參數(shù)，如k
     4.維護(hù)一個(gè)大小為k的的按距離由大到小的優(yōu)先級隊(duì)列，用于存儲(chǔ)最近鄰訓(xùn)練元組。隨機(jī)從訓(xùn)練元組中選取k個(gè)元組作為初始的最近鄰元組，分別計(jì)算測試元組到這k個(gè)元組的距離，將訓(xùn)練元組標(biāo)號和距離存入優(yōu)先級隊(duì)列
  4. 遍歷訓(xùn)練元組集，計(jì)算當(dāng)前訓(xùn)練元組與測試元組的距離，將所得距離L 與優(yōu)先級隊(duì)列中的最大距離Lmax
  5. 進(jìn)行比較。若L>=Lmax，則舍棄該元組，遍歷下一個(gè)元組。若L < Lmax，刪除優(yōu)先級隊(duì)列中最大距離的元組，將當(dāng)前訓(xùn)練元組存入優(yōu)先級隊(duì)列。
  6. 遍歷完畢，計(jì)算優(yōu)先級隊(duì)列中k 個(gè)元組的多數(shù)類，并將其作為測試元組的類別。
  7. 測試元組集測試完畢后計(jì)算誤差率，繼續(xù)設(shè)定不同的k值重新進(jìn)行訓(xùn)練，最后取誤差率最小的k 值。

實(shí)現(xiàn)

Python

• Scikit-Learn
  http:///stable/modules/neighbors.html

  KNN分類器使用sklearn.neighbors.KNeighborsClassifier，參數(shù)設(shè)置參考 http:///stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

  • knn_classification_example.py
    python
X = [[0, 100], [1, 99], [99, 1], [100, 0]]
y = [0, 0, 1, 1]
from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=3)
classifier.fit(X, y)
print(classifier.predict([[10, 90], [90, 10]]))
print(classifier.predict_proba([[10, 90], [90, 10]]))
print(classifier.kneighbors([[10, 90], [90, 10]], return_distance=False))

    
    • output
      text
>>> print(classifier.predict([[10, 90], [90, 10]]))
[0 1]
>>> print(classifier.predict_proba([[10, 90], [90, 10]]))
[[ 0.66666667 0.33333333]
[ 0.33333333 0.66666667]]
>>> print(classifier.kneighbors([[10, 90], [90, 10]], return_distance=False))
[[1 0 2]
[2 3 1]]


  KNN回歸器使用sklearn.neighbors.KNeighborsRegressor，參數(shù)設(shè)置參考 http:///stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html

  • knn_regression_example.py
    python
X = [[0], [1], [2], [3]]
y = [0, 0, 1, 1]
from sklearn.neighbors import KNeighborsRegressor
regressor = KNeighborsRegressor(n_neighbors=2)
regressor.fit(X, y)
print(regressor.predict([[1.5]]))

    
    • output
      text
[ 0.5]


應(yīng)用

　　TODO

參考

1. https://zh./wiki/最近鄰居法
2. http://baike.baidu.com/view/1485833.htm
3. http://blog.sina.com.cn/s/blog_7fc305440101d0vr.html