孫 傲，趙禮峰

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

1 概 述

分類是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重點(diǎn)和熱點(diǎn)方向。分類的方法眾多，如決策樹(shù)、K近鄰算法、遺傳算法、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)等。其中K近鄰算法以其理論簡(jiǎn)單有效，且易于實(shí)現(xiàn)等優(yōu)點(diǎn)在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域被廣泛應(yīng)用。

K近鄰算法的直觀思想就是給定訓(xùn)練數(shù)據(jù)集，選擇恰當(dāng)?shù)木嚯x函數(shù)，通過(guò)已選的距離函數(shù)計(jì)算待分類樣本和訓(xùn)練集中每個(gè)樣本之間的距離，選取與待分類樣本距離最小的k個(gè)樣本作為待分類樣本的k個(gè)最近鄰，將待分類樣本歸為k個(gè)最近鄰所屬類別中的多數(shù)類。

K近鄰算法雖然算法直觀、簡(jiǎn)單有效，但是也存在著比較明顯的缺點(diǎn)。首先k值的選擇會(huì)直接影響分類的效果，k值較小易導(dǎo)致過(guò)擬合，此時(shí)待分類樣本的類別判斷只受與待分類樣本較近的實(shí)例影響；k值較大易導(dǎo)致學(xué)習(xí)的近似誤差增大，距離待分類樣本較遠(yuǎn)的實(shí)例也會(huì)對(duì)分類結(jié)果產(chǎn)生影響。其次，K近鄰算法在解決大規(guī)模數(shù)據(jù)分類時(shí)，分類速度較慢，其需要存儲(chǔ)數(shù)據(jù)集中所有數(shù)據(jù)樣本，計(jì)算待分類樣本與數(shù)據(jù)集中所有樣本之間的距離。另外，將每個(gè)屬性等同看待，賦予相同權(quán)重，忽略了每個(gè)屬性對(duì)分類的不同重要程度，影響了分類結(jié)果的準(zhǔn)確性。

針對(duì)K近鄰算法的不足，許多學(xué)者對(duì)其進(jìn)行了研究和改進(jìn)，逐漸完善了K近鄰算法體系。針對(duì)k值選擇影響分類結(jié)果的問(wèn)題，路敦利等[1]將BP神經(jīng)網(wǎng)絡(luò)與kNN相結(jié)合，通過(guò)對(duì)訓(xùn)練樣本使用k值不同的K近鄰算法進(jìn)行初步分類,同一數(shù)據(jù)會(huì)得到多個(gè)不同的初步分類結(jié)果集;然后將初步分類結(jié)果集作為BP神經(jīng)網(wǎng)絡(luò)的輸入,再對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練分類。優(yōu)化了傳統(tǒng)K近鄰算法精度受k值影響的問(wèn)題，提高了分類準(zhǔn)確率。孫可等[2]提出SA-KNN算法，優(yōu)化傳統(tǒng)K近鄰k值選擇問(wèn)題，引入系數(shù)學(xué)習(xí)理論，通過(guò)局部保持投影LPP重構(gòu)測(cè)試樣本，利用l2,1范數(shù)去除噪聲樣本，尋找投影變換矩陣進(jìn)而確定k值。豆增發(fā)等[3]提出一種根據(jù)最小距離個(gè)數(shù)來(lái)增長(zhǎng)式地確定k值的方法，將待分類樣本與所有訓(xùn)練樣本的歐氏距離按大小排序，從最小距離開(kāi)始，按距離大小等級(jí)得到m個(gè)k值選擇序列，選擇使樣本正確分類的最小k值，作為K近鄰的k值；同時(shí)運(yùn)用信息增益確定屬性重要程度，計(jì)算加權(quán)距離進(jìn)行K近鄰分類。

屬性等同看待忽視了屬性對(duì)分類的重要性，王增民等[4]根據(jù)信息熵理論，計(jì)算各分類屬性與分類的相關(guān)性，剔除相關(guān)度低的樣本，并依據(jù)保留特征的相關(guān)性作為權(quán)重，計(jì)算加權(quán)歐氏距離，選擇K近鄰，優(yōu)化了距離度量。陳振洲等[5]提出FWKNN算法，將SVM算法應(yīng)用到K近鄰特征權(quán)重的度量中，以SVM算法中參數(shù)w作為特征的權(quán)重，并以此計(jì)算加權(quán)歐氏距離，選取k個(gè)近鄰。

合適的距離度量函數(shù)影響分類效果，周靖等[6]將樣本特征參數(shù)的熵值與樣本分布概率的乘積作為特征對(duì)分類的相關(guān)度,并根據(jù)相關(guān)度值衡量特征對(duì)分類影響程度的強(qiáng)弱以定義樣本間的距離函數(shù)，優(yōu)化了在進(jìn)行近鄰選擇時(shí)多數(shù)類別和高密度樣本占優(yōu)的情況。楊立等[7]提出SDKNN算法，分析屬性內(nèi)取值的語(yǔ)義差異，定義語(yǔ)義距離構(gòu)成距離函數(shù)，優(yōu)化了同一屬性取值的語(yǔ)義差異所帶來(lái)的影響。

分類速度隨數(shù)據(jù)維度和樣本量的增加急劇下降，余小鵬等[8]針對(duì)K近鄰算法搜索慢的缺陷，提出自適應(yīng)K最近鄰算法，建立半徑生長(zhǎng)的BP神經(jīng)網(wǎng)絡(luò)模型，在以測(cè)試點(diǎn)為中心的超球內(nèi)搜索，縮小了搜索范圍，提高了搜索效率。江昆等[9]提出運(yùn)用隨機(jī)森林算法對(duì)變量進(jìn)行排序，剔除不重要的變量，降低數(shù)據(jù)維數(shù)，提高K近鄰算法在處理高維數(shù)據(jù)集的性能。Chen Yewang等[10]針對(duì)K近鄰分類速度慢的問(wèn)題，提出一種改進(jìn)基于緩沖區(qū)的K最近鄰查詢算法，有效減少搜索待分類樣本的時(shí)間復(fù)雜度。

不同的決策方式使k個(gè)近鄰對(duì)待分類樣本有不同的分類，楊金福等[11]在模板約簡(jiǎn)K近鄰算法的基礎(chǔ)上提出TWKNN算法，利用模板約簡(jiǎn)技術(shù)，將訓(xùn)練集中遠(yuǎn)離分類邊界的樣本去掉,同時(shí)按照各個(gè)近鄰與待測(cè)樣本的距離為k個(gè)近鄰賦予不同的權(quán)值,增強(qiáng)了算法的魯棒性。肖輝輝等[12]提出一種FCD-KNN算法，首先通過(guò)距離度量函數(shù)計(jì)算待分類樣本與訓(xùn)練樣本的距離值，通過(guò)距離值選擇k個(gè)樣本，定義類可信度函數(shù)，根據(jù)各類近鄰樣本點(diǎn)的平均距離及個(gè)數(shù)判斷待測(cè)試樣本的類別，優(yōu)化了K近鄰決策的方式。

但是，目前對(duì)于K近鄰算法的改進(jìn)和應(yīng)用[13-17]，大多使用不加權(quán)的歐氏距離或單一指標(biāo)的加權(quán)歐氏距離，無(wú)法全面準(zhǔn)確地度量分類特征對(duì)分類的重要程度。針對(duì)這一問(wèn)題，利用信息增益和基尼不純度的綜合指標(biāo)確定分類屬性的重要程度，只有信息增益足夠大且基尼不純度足夠小的特征才是真正重要的特征，即用信息增益和基尼不純度的差值作為衡量特征重要程度的依據(jù)，并根據(jù)此綜合指標(biāo)構(gòu)造權(quán)重，計(jì)算加權(quán)歐氏距離，進(jìn)行K近鄰分類。

2 相關(guān)知識(shí)

2.1 K近鄰算法

K近鄰算法是一種基于實(shí)例的懶散算法，其思想就是選擇距離度量函數(shù)，根據(jù)距離度量，找出與待分類樣本距離最小的k個(gè)最近鄰，通過(guò)多數(shù)表決等方式進(jìn)行類別預(yù)測(cè)。

算法流程如下：

(1)選擇距離度量函數(shù)，計(jì)算待分類樣本與數(shù)據(jù)集中所有實(shí)例的距離值；

(2)在數(shù)據(jù)集實(shí)例中，找出與待分類樣本距離度量值最小的k個(gè)實(shí)例點(diǎn)；

(3)根據(jù)與待分類樣本距離度量值最小的k個(gè)實(shí)例點(diǎn)所屬的類別，通過(guò)分類決策規(guī)則(如多數(shù)表決)，決定待分類樣本的類別。

不同的距離度量方式，所選取的k個(gè)最近鄰不同，從而最終待分類樣本的類別判斷也會(huì)不同。因此選取合適的距離度量方式，對(duì)提高K近鄰分類的性能尤為重要。

2.2 信息增益及算法

信息增益表示在已知某特征的信息而使得類別的信息的不確定性減小的程度。若特征為A，訓(xùn)練數(shù)據(jù)集為D，則特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益為g(D,A)。

g(D,A)=H(D)-H(D|A)

(1)

其中，H(D)為集合D的經(jīng)驗(yàn)熵，表示對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性；H(D|A)為在特征A給定條件下數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵，表示在給定特征A給定條件下對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性。

因此信息增益就表示在給定特征A而使得對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性減少的程度，所以信息增益大的特征具有更強(qiáng)的分類能力，該特征對(duì)分類的重要程度更大。

信息增益的算法流程如下:

(1)計(jì)算數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)。

(2)

其中，|Ck|為屬于類Ck的樣本個(gè)數(shù)；|D|為樣本容量。

(2)計(jì)算特征A對(duì)數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵H(D|A)。

(3)

其中，|Di|為根據(jù)特征A的取值將D劃分的第i個(gè)子集的樣本個(gè)數(shù)；|Dik|為子集Di中屬于類Ck的樣本個(gè)數(shù)。

(3)計(jì)算信息增益。

2.3 基尼不純度

基尼不純度表示集合的不確定性，基尼不純度越大，集合的不確定性也就越大。若經(jīng)過(guò)某特征對(duì)集合進(jìn)行劃分，使得劃分后集合的不確定性減小，則該特征較重要。

在分類問(wèn)題中，假設(shè)集合D有k個(gè)類，則集合D的基尼不純度為：

(4)

其中，Ck是D中屬于第k個(gè)類的樣本子集；k是類的個(gè)數(shù)。

經(jīng)過(guò)特征A劃分后，集合D的基尼不純度為：

(5)

其中，Di為集合D中屬性A取值為i的樣本子集。

3 基于信息增益和基尼不純度綜合指標(biāo)的加權(quán)K近鄰分類器構(gòu)造方法

基于信息增益和基尼不純度綜合指標(biāo)的加權(quán)K近鄰分類器將信息增益和基尼不純度兩個(gè)指標(biāo)結(jié)合起來(lái)評(píng)價(jià)屬性的重要性，綜合利用了信息增益和基尼指數(shù)的兩個(gè)評(píng)價(jià)指標(biāo)的優(yōu)點(diǎn)，對(duì)屬性重要性的評(píng)價(jià)更加全面。信息增益越大的特征重要程度越高，基尼不純度越小的特征重要程度越高。由此出發(fā)，若一個(gè)特征基尼不純度足夠小且信息增益足夠大即信息增益和基尼不純度的差值越大，則表示該特征對(duì)分類越重要。

構(gòu)造流程如下：

(1)將信息增益和基尼不純度綜合指標(biāo)定義為GaGi，屬性A的GaGi指標(biāo)的計(jì)算公式為：

GaGi(A)=g(D,A)-Gini(D,A)

(6)

計(jì)算數(shù)據(jù)集每個(gè)屬性的GaGi指標(biāo)，信息增益越大，屬性越重要；基尼不純度越小，屬性越重要。所以屬性的綜合指標(biāo)GaGi的數(shù)值越大，該屬性的重要程度越大。

(2)根據(jù)屬性的GaGi指標(biāo)值構(gòu)造屬性權(quán)重，訓(xùn)練數(shù)據(jù)集D共有n個(gè)屬性，其中屬性A的權(quán)重構(gòu)造公式為：

(7)

(3)根據(jù)每個(gè)屬性的權(quán)重，建立加權(quán)歐氏距離d，樣本點(diǎn)x1,x2之間的加權(quán)歐氏距離為：

(8)

(4)計(jì)算待分類樣本與所有訓(xùn)練樣本的加權(quán)歐氏距離，對(duì)距離值進(jìn)行排序。

(5)指定k值，選取與待分類樣本最近鄰的k個(gè)訓(xùn)練樣本。

(6)依據(jù)多數(shù)表決決策規(guī)則，將k個(gè)最近鄰樣本所屬類別中的多數(shù)類別作為待分類樣本的類別。

4 仿真實(shí)驗(yàn)

4.1 實(shí)值仿真

利用Python3編程環(huán)境構(gòu)造分類器，分別采用UCI數(shù)據(jù)庫(kù)中的Iris和Wine兩個(gè)數(shù)據(jù)集驗(yàn)證該算法的有效性。為保證有充足的數(shù)據(jù)集用于訓(xùn)練，采用留存交叉驗(yàn)證的方法對(duì)每個(gè)數(shù)據(jù)集隨機(jī)選擇20%的數(shù)據(jù)作為測(cè)試集，剩下的作為訓(xùn)練集。為更加準(zhǔn)確地估計(jì)分類器的錯(cuò)誤率，進(jìn)行多次迭代求出平均錯(cuò)誤率作為分類器的最終錯(cuò)誤率。

數(shù)據(jù)集信息如表1所示。

表1 數(shù)據(jù)集信息

4.1.1 Iris數(shù)據(jù)集仿真效果

該數(shù)據(jù)集包含150個(gè)實(shí)例和4個(gè)特征變量，特征變量分別為：花萼長(zhǎng)度sepal length、花萼寬度sepal width、花瓣長(zhǎng)度petal length、花瓣寬度petal width。

選取30個(gè)數(shù)據(jù)實(shí)例作為測(cè)試集，剩下120個(gè)數(shù)據(jù)實(shí)例作為訓(xùn)練集，用于構(gòu)造加權(quán)分類器，同時(shí)為避免特征的數(shù)量值大小對(duì)樣本間距離的影響，消除特征間數(shù)量值等級(jí)的差別，對(duì)數(shù)據(jù)集進(jìn)行歸一化處理。最后采用10次留存交叉驗(yàn)證法得到最終分類器錯(cuò)誤率。

在不同k值下算法實(shí)現(xiàn)的平均錯(cuò)誤率如表2所示。

表2 不同k值下的三種算法錯(cuò)誤率對(duì)比(Iris)

通過(guò)對(duì)比可以發(fā)現(xiàn)，加權(quán)K近鄰算法總體優(yōu)于傳統(tǒng)K近鄰算法，屬性權(quán)重的度量方式和k值的選擇不同也會(huì)影響分類精度，在此數(shù)據(jù)下，總的來(lái)說(shuō)基于信息增益和基尼不純度綜合指標(biāo)的加權(quán)K近鄰法更優(yōu)。

4.1.2 Wine數(shù)據(jù)集仿真效果

UCI數(shù)據(jù)庫(kù)中Wine數(shù)據(jù)集包含178個(gè)數(shù)據(jù)實(shí)例，有13個(gè)紅酒理化元素特征變量，對(duì)數(shù)據(jù)集進(jìn)行歸一化，隨機(jī)選擇35個(gè)數(shù)據(jù)實(shí)例作為測(cè)試集，剩下143個(gè)數(shù)據(jù)作為訓(xùn)練集，最后采用10次留存交叉驗(yàn)證法得到最終分類器錯(cuò)誤率。

k值取1到5時(shí)，三種K近鄰算法的平均錯(cuò)誤率如表3所示。

通過(guò)對(duì)Wine數(shù)據(jù)集的算法仿真可以看出，基于信息增益和基尼不純度綜合指標(biāo)的加權(quán)K近鄰法最優(yōu)，加權(quán)K近鄰算法始終優(yōu)于傳統(tǒng)K近鄰算法，在k等于1和5時(shí)分類器的準(zhǔn)確度最高，分類效果最好。

表3 不同k值下的三種算法錯(cuò)誤率對(duì)比(Wine)

4.2 方法評(píng)價(jià)與不足

通過(guò)對(duì)兩個(gè)真實(shí)數(shù)據(jù)集的仿真實(shí)驗(yàn)，可以得出區(qū)別對(duì)待屬性特征，進(jìn)行加權(quán)K近鄰算法明顯優(yōu)于傳統(tǒng)的K近鄰方法；同時(shí)權(quán)重的構(gòu)造指標(biāo)也會(huì)對(duì)分類結(jié)果產(chǎn)生影響。實(shí)驗(yàn)證明，采用信息增益與基尼不純度的綜合指標(biāo)比采用單一的信息增益指標(biāo)劃分屬性重要程度更加合理，分類精度略優(yōu)于采用單一的信息增益指標(biāo)的K近鄰法。

該算法也存在一定的不足，信息增益和基尼不純度偏向于取值較多的特征。在特征取值較均衡時(shí)，算法具有很好的分類性能，在特征取值嚴(yán)重不均衡時(shí)，算法分類性能有所下降。

5 結(jié)束語(yǔ)

合理劃分分類屬性的重要程度，是數(shù)據(jù)挖掘分類問(wèn)題和特征選取的重點(diǎn)方向。面對(duì)數(shù)據(jù)集的眾多分類特征，如何選擇合適指標(biāo)評(píng)價(jià)特征變量的重要程度至關(guān)重要。針對(duì)傳統(tǒng)K近鄰算法將特征變量等同權(quán)重影響分類準(zhǔn)確性和單一指標(biāo)度量特征變量重要程度的不全面性的問(wèn)題，提出一種基于信息增益和基尼不純度的加權(quán)K近鄰算法。該算法通過(guò)定義的GaGi指標(biāo)對(duì)分類特征的重要程度進(jìn)行度量，并以此為權(quán)重，計(jì)算加權(quán)歐氏距離，進(jìn)行K近鄰分類。對(duì)UCI數(shù)據(jù)庫(kù)中Wine和Iris兩個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，該方法分類錯(cuò)誤率比傳統(tǒng)K近鄰算法和基于信息增益的加權(quán)K近鄰算法的錯(cuò)誤率更低，分類性能更好。