1.引言

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

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

2.kNN算法

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

算法描述

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

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

分類決策規(guī)則

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

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

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

存在問題

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

前面提到過，k鄰域的樣本點(diǎn)對(duì)預(yù)測(cè)結(jié)果的貢獻(xiàn)度是相等的；但距離更近的樣本點(diǎn)應(yīng)有更大的相似度，其貢獻(xiàn)度應(yīng)比距離更遠(yuǎn)的樣本點(diǎn)大?？梢约由蠙?quán)值進(jìn)行修正，則最大表決原則變成：