1.引言

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

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

2.kNN算法

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

算法描述

訓(xùn)練，其類別，訓(xùn)練集中樣本點數(shù)為N，類別數(shù)為K。輸入待預(yù)測數(shù)據(jù)，則預(yù)測類別

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

分類決策規(guī)則

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

若要最小化誤分類率，則應(yīng)

所以，最大表決規(guī)則等價于經(jīng)驗風(fēng)險最小化。

存在問題

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

前面提到過，k鄰域的樣本點對預(yù)測結(jié)果的貢獻度是相等的；但距離更近的樣本點應(yīng)有更大的相似度，其貢獻度應(yīng)比距離更遠的樣本點大。可以加上權(quán)值進行修正，則最大表決原則變成：