1.引言

頂級數據挖掘會議ICDM于2006年12月評選出了數據挖掘領域的十大經典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Na?ve Bayes與 CART。 以前看過關于這些數據挖掘算法，但對背后數學原理未做過多探究，因而借此整理以更深入地理解這些算法。

本文討論的kNN算法是監督學習中分類方法的一種。所謂監督學習與非監督學習，是指訓練數據是否有標注類別，若有則為監督學習，若否則為非監督學習。監督學習是根據輸入數據（訓練數據）學習一個模型，能對后來的輸入做預測。在監督學習中，輸入變量與輸出變量可以是連續的，也可以是離散的。若輸入變量與輸出變量均為連續變量，則稱為回歸；輸出變量為有限個離散變量，則稱為分類；輸入變量與輸出變量均為變量序列，則稱為標注[2]。

2.kNN算法

kNN算法的核心思想非常簡單：在訓練集中選取離輸入的數據點最近的k個鄰居，根據這個k個鄰居中出現次數最多的類別（最大表決規則），作為該數據點的類別。

算法描述

訓練，其類別，訓練集中樣本點數為N，類別數為K。輸入待預測數據，則預測類別

其中，涵蓋的k鄰域記作，當時指示函數，否則。

分類決策規則

kNN學習模型：輸入，通過學習得到決策函數：輸出類別。假設分類損失函數為0-1損失函數，即分類正確時損失函數值為0，分類錯誤時則為1。假如給預測類別為，即；同時由式子（1）可知k鄰域的樣本點對學習模型的貢獻度是均等的，則kNN學習模型誤分類率為

若要最小化誤分類率，則應

所以，最大表決規則等價于經驗風險最小化。

存在問題

k值得選取對kNN學習模型有著很大的影響。若k值過小，預測結果會對噪音樣本點顯得異常敏感。特別地，當k等于1時，kNN退化成最近鄰算法，沒有了顯式的學習過程。若k值過大，會有較大的鄰域訓練樣本進行預測，可以減小噪音樣本點的減少；但是距離較遠的訓練樣本點對預測結果會有貢獻，以至于造成預測結果錯誤。下圖給出k值的選取對于預測結果的影響：

前面提到過，k鄰域的樣本點對預測結果的貢獻度是相等的；但距離更近的樣本點應有更大的相似度，其貢獻度應比距離更遠的樣本點大?？梢约由蠙嘀?img src="http://file.elecfans.com/web1/M00/64/CE/pIYBAFuiGcSANSJCAAAHxdycjlU069.png" />進行修正，則最大表決原則變成：