孫 傲，趙禮峰

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

1 概 述

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

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

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

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

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

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

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

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

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

2 相關(guān)知識

2.1 K近鄰算法

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

算法流程如下：

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

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

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

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

2.2 信息增益及算法

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

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

(1)

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

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

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

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

(2)

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

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

(3)

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

(3)計算信息增益。

2.3 基尼不純度

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

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

(4)

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

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

(5)

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

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

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

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

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

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

(6)

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

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

(7)

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

(8)

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

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

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

4 仿真實驗

4.1 實值仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 方法評價與不足

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

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

5 結(jié)束語

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