K-近鄰演算法

在圖型識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和迴歸的無母數統計方法^[1]，由美國統計學家伊芙琳·費克斯和小約瑟夫·霍奇斯於1951年首次提出，後來由托馬斯·寇弗（英語：Thomas M. Cover）擴充。在這兩種情況下，輸入包含特徵空間中的k個最接近的訓練樣本。

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

在k-NN迴歸中，輸出是該物件的屬性值。該值是其k個最近鄰居的值的平均值。

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

K-NN是一種循例學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習（英語：lazy learning）。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

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

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

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

K-平均演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關係。資料標準化可以大大提高該演算法的準確性^[2]^[3]。

演算法

k近鄰演算法例子。測試樣本（綠色圓形）應歸入要麼是第一類的藍色方形或是第二類的紅色三角形。如果k=3（實線圓圈）它被分配給第二類，因為有2個三角形和只有1個正方形在內側圓圈之內。如果k=5（虛線圓圈）它被分配到第一類（3個正方形與2個三角形在外側圓圈之內）。

訓練樣本是多維特徵空間向量，其中每個訓練樣本帶有一個類別標籤。演算法的訓練階段只包含儲存的特徵向量和訓練樣本的標籤。

在分類階段，k是一個使用者定義的常數。一個沒有類別標籤的向量（查詢或測試點）將被歸類為最接近該點的k個樣本點中最頻繁使用的一類。

一般情況下，將歐氏距離作為距離度量，但是這是只適用於連續變數。在文字分類這種離散變數情況下，另一個度量——「重疊度量」（或海明距離）可以用來作為度量。例如對於基因表達微陣列資料，k-NN也與Pearson和Spearman相關係數結合起來使用。^[4]通常情況下，如果運用一些特殊的演算法來計算度量的話，k近鄰分類精度可顯著提高，如運用大間隔最近鄰居或者鄰里成分分析法。

「多數表決」分類會在類別分布偏斜時出現缺陷。也就是說，出現頻率較多的樣本將會主導測試點的預測結果，因為他們比較大可能出現在測試點的K鄰域而測試點的屬性又是通過k鄰域內的樣本計算出來的。^[5]解決這個缺點的方法之一是在進行分類時將樣本到k個近鄰點的距離考慮進去。k近鄰點中每一個的分類（對於迴歸問題來說，是數值）都乘以與測試點之間距離的成反比的權重。另一種克服偏斜的方式是通過資料表示形式的抽象。例如，在自組織對映（SOM）中，每個節點是相似的點的一個叢集的代表（中心），而與它們在原始訓練資料的密度無關。K-NN可以應用到SOM中。

參數選擇

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

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

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

加權最近鄰分類器

$k$ - 最近鄰分類器可以被視為為 $k$ 最近鄰居分配權重 $1/k$ 以及為所有其他鄰居分配 $0$ 權重。這可以推廣到加權最近鄰分類器。也就是說，第 $i$ 近的鄰居被賦予權重 $w_{ni}$ ，其中 $\sum _{i=1}^{n}w_{ni}=1$ 。關於加權最近鄰分類器的強一致性的類似結果也成立。^[9]

設 $C_{n}^{wnn}$ 表示權重為 $\{w_{ni}\}_{i=1}^{n}$ 的加權最近鄰分類器。根據類別分布的規律性條件，超額風險具有以下漸近展開^[10]

{\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{Bayes})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},

對常數 $B_{1}$ and $B_{2}$ 當 $s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}$ 並且 $t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\{i^{1+2/d}-(i-1)^{1+2/d}\}$ 。

最佳加權方案 $\{w_{ni}^{*}\}_{i=1}^{n}$ 用於平衡上面顯示中的兩個項，如下所示：令 $k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor$ ，

w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]

對

i=1,2,\dots ,k^{*}

並且

w_{ni}^{*}=0

對

i=k^{*}+1,\dots ,n

.

利用最佳權重，超額風險的漸近展開中的主項是 ${\mathcal {O}}(n^{-{\frac {4}{d+4}}})$ 。當使用bagged 最近鄰分類器（英語：bootstrap aggregating）時，類似的結果也是如此。

屬性

原始樸素的演算法通過計算測試點到儲存樣本點的距離是比較容易實現的，但它屬於計算密集型的，特別是當訓練樣本集變大時，計算量也會跟著增大。多年來，許多用來減少不必要距離評價的近鄰搜尋演算法已經被提出來。使用一種合適的近鄰搜尋演算法能使K近鄰演算法的計算變得簡單許多。

近鄰演算法具有較強的一致性結果。隨著資料趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍^[11]。對於一些K值，K近鄰保證錯誤率不會超過貝葉斯的。

決策邊界

近鄰演算法能用一種有效的方式隱含的計算決策邊界。另外，它也可以顯式的計算決策邊界，以及有效率的這樣做計算，使得計算複雜度是邊界複雜度的函數。^[12]

連續變數估計

K近鄰演算法也適用於連續變數估計，比如適用反距離加權平均多個K近鄰點確定測試點的值。該演算法的功能有：

從目標區域抽樣計算歐式或馬氏距離；
在交叉驗證後的RMSE基礎上選擇啟發式最佳的K鄰域；
計算多元k-最近鄰居的距離倒數加權平均。

發展

然而k最近鄰居法因為計算量相當的大，所以相當的耗時，Ko與Seo提出一演算法TCFP（text categorization using feature projection），嘗試利用特徵投影法（英語：feature projection）來降低與分類無關的特徵對於系統的影響，並藉此提昇系統效能，其實驗結果顯示其分類效果與k最近鄰居法相近，但其運算所需時間僅需k最近鄰居法運算時間的五十分之一。

除了針對檔案分類的效率，尚有研究針對如何促進k最近鄰居法在檔案分類方面的效果，如Han等人於2002年嘗試利用貪婪法，針對檔案分類實做可調整權重的k最近鄰居法WAkNN（weighted adjusted k nearest neighbor），以促進分類效果；而Li等人於2004年提出由於不同分類的檔案本身有數量上有差異，因此也應該依照訓練集合中各種分類的檔案數量，選取不同數目的最近鄰居，來參與分類。

參見

注釋

^ 這個方案是一個線性插值的推廣。

參考文獻

參照

^ Altman, N. S. An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879.
^ Piryonesi S. Madeh; El-Diraby Tamer E. Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems. Journal of Transportation Engineering, Part B: Pavements. 2020-06-01, 146 (2): 04020022. doi:10.1061/JPEODX.0000175.
^ Hastie, Trevor. The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Tibshirani, Robert., Friedman, J. H. (Jerome H.). New York: Springer. 2001. ISBN 0-387-95284-5. OCLC 46809224.
^ Jaskowiak, P. A.; Campello, R. J. G. B. Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data. Brazilian Symposium on Bioinformatics (BSB 2011): 1–8. CiteSeerX 10.1.1.208.993  .
^ D. Coomans; D.L. Massart. Alternative k-nearest neighbour rules in supervised pattern recognition: Part 1. k-Nearest neighbour classification by using alternative voting rules. Analytica Chimica Acta. 1982, 136: 15–27. doi:10.1016/S0003-2670(01)95359-0.
^ Everitt, B. S., Landau, S., Leese, M. and Stahl, D.（2011）Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK.
^ Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). "Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization". Journal of Chemical Information and Modeling 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183.
^ Hall P, Park BU, Samworth RJ. Choice of neighbor order in nearest-neighbor classification. Annals of Statistics. 2008, 36 (5): 2135–2152. doi:10.1214/07-AOS537.
^ Stone C. J. Consistent nonparametric regression. Annals of Statistics. 1977, 5 (4): 595–620. doi:10.1214/aos/1176343886.
^ Samworth R. J. Optimal weighted nearest neighbour classifiers. Annals of Statistics. 2012, 40 (5): 2733–2763. arXiv:1101.5783  . doi:10.1214/12-AOS1049.
^ Cover TM, Hart PE (1967). "Nearest neighbor pattern classification". IEEE Transactions on Information Theory 13 (1): 21–27. doi:10.1109/TIT.1967.1053964.
^ Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). "Output-sensitive algorithms for computing nearest-neighbor decision boundaries". Discrete and Computational Geometry 33 (4): 593–604. doi:10.1007/s00454-004-1152-0

來源

E. H. Han, G. Karypis and V. Kumar, Text categorization using weight adjusted k-Nearest Neighbor classification, Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 53–65, 2001.
Y. J. Ko and Y. J. Seo, Text categorization using feature projections, Proceedings of the Nineteenth international conference on Computational linguistics, Volume 1, pp. 1–7, 2002.
B. L. Li, Q. Lu and S. W. Yu, An adaptive k-nearest neighbor text categorization strategy, ACM Transactions on Asian Language Information Processing, Volume 3 , Issue 4, pp. 215–226, 2004.

}}

拓展閱讀

When Is "Nearest Neighbor" Meaningful?（頁面存檔備份，存於網際網路檔案館）
Belur V. Dasarathy (編). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. 1991. ISBN 0-8186-8930-7.
Shakhnarovish, Darrell, and Indyk (編). Nearest-Neighbor Methods in Learning and Vision. MIT Press. 2005. ISBN 0-262-19547-X.
Mäkelä H Pekkarinen A. Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data. Forest Ecology and Management. 2004-07-26, 196 (2–3): 245–255. doi:10.1016/j.foreco.2004.02.049.
Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
Scholarpedia article on k-NN （頁面存檔備份，存於網際網路檔案館）
google-all-pairs-similarity-search （頁面存檔備份，存於網際網路檔案館）

[2] 這個方案是一個線性插值的推廣。

[1] Altman, N. S. An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879.

[:0-3] Piryonesi S. Madeh; El-Diraby Tamer E. Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems. Journal of Transportation Engineering, Part B: Pavements. 2020-06-01, 146 (2): 04020022. doi:10.1061/JPEODX.0000175.

[4] Hastie, Trevor. The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Tibshirani, Robert., Friedman, J. H. (Jerome H.). New York: Springer. 2001. ISBN 0-387-95284-5. OCLC 46809224.

[5] Jaskowiak, P. A.; Campello, R. J. G. B. Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data. Brazilian Symposium on Bioinformatics (BSB 2011): 1–8. CiteSeerX 10.1.1.208.993  .

[Coomans_Massart1982-6] D. Coomans; D.L. Massart. Alternative k-nearest neighbour rules in supervised pattern recognition: Part 1. k-Nearest neighbour classification by using alternative voting rules. Analytica Chimica Acta. 1982, 136: 15–27. doi:10.1016/S0003-2670(01)95359-0.

[7] Everitt, B. S., Landau, S., Leese, M. and Stahl, D.（2011）Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK.

[8] Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). "Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization". Journal of Chemical Information and Modeling 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183.

[HPS2008-9] Hall P, Park BU, Samworth RJ. Choice of neighbor order in nearest-neighbor classification. Annals of Statistics. 2008, 36 (5): 2135–2152. doi:10.1214/07-AOS537.

[Stone-10] Stone C. J. Consistent nonparametric regression. Annals of Statistics. 1977, 5 (4): 595–620. doi:10.1214/aos/1176343886.

[Samworth12-11] Samworth R. J. Optimal weighted nearest neighbour classifiers. Annals of Statistics. 2012, 40 (5): 2733–2763. arXiv:1101.5783  . doi:10.1214/12-AOS1049.

[12] Cover TM, Hart PE (1967). "Nearest neighbor pattern classification". IEEE Transactions on Information Theory 13 (1): 21–27. doi:10.1109/TIT.1967.1053964.

[13] Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). "Output-sensitive algorithms for computing nearest-neighbor decision boundaries". Discrete and Computational Geometry 33 (4): 593–604. doi:10.1007/s00454-004-1152-0

[1]

[註 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]