基于異構(gòu)距離的集成分類算法研究

張燕，杜紅樂

（商洛學院 數(shù)學與計算機應(yīng)用學院，陜西 商洛 726000）

傳統(tǒng)的算法多是面向均衡數(shù)據(jù)集，有較好的分類性能，而實際應(yīng)用中的數(shù)據(jù)集多是不均衡、異構(gòu)的。面向不均衡數(shù)據(jù)分類的研究是數(shù)據(jù)挖掘、機器學習等領(lǐng)域當前的研究熱點之一[1-16]，主要集中在數(shù)據(jù)層面[1-8]和算法層面[9-16]。

數(shù)據(jù)層面的方法[1-5]，又稱為重采樣法，多采用減少多數(shù)類樣本或增加少數(shù)類樣本，使得數(shù)據(jù)集均衡化，過采樣[1-3]是依據(jù)少數(shù)類樣本的空間特征，通過一定的方法增加少數(shù)類樣本數(shù)量，該方法容易導(dǎo)致過擬合，為此許多研究者提出了解決方法，例如合成少數(shù)類樣本過采樣技術(shù)(synthetic minority oversampling technique,SMOTE)及對SMOTE的改進算法；欠采樣[5-6]則是通過一定的方法刪除多數(shù)類樣本中信息重復(fù)或者包含信息量較少的樣本，但由于計算方法的不同，會刪除包含豐富信息的樣本，導(dǎo)致欠學習，為此研究者結(jié)合集成學習和重采樣思想，不刪除樣本，而是對多數(shù)類樣本按照一定策略進行抽取，然后與少數(shù)類樣本一起構(gòu)成訓(xùn)練子集[7]。

算法層面的方法則是提出新方法或者改進已有算法，減少數(shù)據(jù)不均衡對分類性能的影響，主要包括代價敏感學習[8-9]、單類學習、集成學習[10-14]等。其中集成學習方法是通過迭代逐步把弱分類器提升為強分類器，能夠較好的提高分類器的性能，也是解決不均衡分類問題的常用方法，在一些領(lǐng)域得到應(yīng)用[15-16]。文獻[11]首先將數(shù)據(jù)集劃分為多個均衡的子集，訓(xùn)練各個子集獲得多個分類器，然后把多個分類器按照一定的規(guī)則(文中給出5種集成規(guī)則)進行集成，從而提高分類性能，該方法中對數(shù)據(jù)集的劃分方法對最終的分類器性能有較大的影響，為此，文獻[5]中通過聚類對多數(shù)類樣本進行欠取樣，獲得與少數(shù)類樣本數(shù)量相同的樣本，然后采用Adaboost算法獲得最終分類器，該方法保證所選樣本的空間分布，但不能對分類錯誤樣本和正確樣本進行區(qū)別對待，而文獻[6]利用抽樣概率進行抽樣，通過迭代不斷修正抽樣概率，對于分類錯誤的樣本加大抽樣概率，而分類正確的樣本減小抽樣概率，目的是爭取下輪迭代中能選中進行學習。因此，本文方法既要充分考慮樣本的空間分布，又要考慮到正確分類和錯誤分類樣本之間的區(qū)別，采用聚類和抽樣概率的方式進行數(shù)據(jù)集的劃分，獲得多個均衡的數(shù)據(jù)子集。

KNN算法是一種簡單而有效的分類算法，通過計算與樣本最近的K個樣本的類別來判斷樣本的類別，計算樣本的K近鄰經(jīng)常采用歐氏距離、相關(guān)距離等，而對于異構(gòu)數(shù)據(jù)集下，這些距離不能準確的表達樣本的相似程度，針對此問題，Wilson等[18]提出了異構(gòu)距離，可以更準確的度量異構(gòu)數(shù)據(jù)下2個樣本之間的相似度，因此，本文采用基于異構(gòu)距離的KNN算法作為弱分類器。

基于以上分析，本文提出一種面向不均衡異構(gòu)數(shù)據(jù)的集成學習算法(imbalanced heterogeneous data ensemble classification based on HVDM-KNN,HK-Adaboost算法)，提高異構(gòu)不均衡數(shù)據(jù)下的分類性能。該算法首先用聚類算法把數(shù)據(jù)集劃分為多個均衡的數(shù)據(jù)子集，對于每個子集采用基于異構(gòu)距離的KNN算法，然后用Adaboost算法對弱分類器進行訓(xùn)練，然后依據(jù)一定的評價指標進行調(diào)整，獲得最終的強分類器。

1 相關(guān)概念

1.1 異構(gòu)距離

定義1異構(gòu)不均衡數(shù)據(jù)(heterogeneous data)：設(shè)數(shù)據(jù)集X上的每條記錄共有m個屬性，k(0＜k＜m)個屬性取值為連續(xù)值，其余m-k個屬性取值為離散值，則稱該數(shù)據(jù)集為異構(gòu)數(shù)據(jù)集，若該數(shù)據(jù)集中類樣本數(shù)量有較大差異，則稱數(shù)據(jù)集為異構(gòu)不均衡數(shù)據(jù)集。

根據(jù)樣本到類中心的距離判斷樣本的類別，其實質(zhì)就是計算樣本與類的相似度，然而歐氏距離以及其它距離都不能準確度量異構(gòu)數(shù)據(jù)集中記錄的相似度。為了有效度量異構(gòu)數(shù)據(jù)之間的相似度，實現(xiàn)數(shù)據(jù)分類，Wilson等[18]提出HVDM(heterogeneous value difference metric)距離函數(shù)，能夠反映出不同屬性對相似度的影響，有效度量數(shù)據(jù)之間的差異，其定義如下：

定義2異構(gòu)距離：設(shè)，則x，y之間的異構(gòu)距離H(x,y)定義為

式中：

1.2 KNN算法

K-近鄰算法通過取測試樣本的K個近鄰，然后依據(jù)K個近鄰的類別進行投票，確定測試樣本的類別，由于算法簡單、易于實現(xiàn)等特點，被廣泛應(yīng)用。KNN是依據(jù)K個近鄰的類別決定測試樣本的類別，因此K個近鄰的選取將影響算法的性能，與測試樣本越相近實質(zhì)就是與測試樣本越相似，而計算相似度可以采用距離、夾角余弦等方法，基于距離相似度中常采用歐氏距離，尤其是對連續(xù)屬性的向量之間，能較好的度量2個向量間的相似程度。而對于既有數(shù)值屬性又有字符屬性的異構(gòu)數(shù)據(jù)，采用歐氏距離不能準確描述2個向量間的相似程度，而實際應(yīng)用中的數(shù)據(jù)有相當部分屬于這樣的異構(gòu)數(shù)據(jù)集，進行訓(xùn)練、分類時多是采用簡單的數(shù)字替換，把數(shù)據(jù)集轉(zhuǎn)換為數(shù)值型的向量，例如red、blue、yellow 3種顏色，若用1、2、3進行代替，原來red與blue之間的差別與red與yellow之間的差別是相同的，但是用數(shù)字替換后的距離計算中，(1-2)2與(1-3)2間的差別是不相同的，因此本文的KNN算法中采用文獻[18]給出的異構(gòu)距離作為度量選擇K個近鄰樣本。

1.3 數(shù)據(jù)均衡化

在集成學習中，對多個訓(xùn)練集進行訓(xùn)練獲得分類器，然后把分類器進行集成，Adaboost算法是通過修改每個樣本的權(quán)重，改變原有的數(shù)據(jù)分布從而得到新的訓(xùn)練集，但是該方法無法改變2類樣本數(shù)量不成比例的問題，為此，文獻[11]提出一種新的面向不均衡數(shù)據(jù)的集成方法，把多數(shù)類樣本劃分為多個與少數(shù)類樣本規(guī)模相當?shù)淖蛹?，然后與少數(shù)類樣本一起構(gòu)成多個均衡的子集，該方法的關(guān)鍵是如何對多數(shù)類樣本進行劃分；文獻[5]采用K均值聚類，產(chǎn)生與少數(shù)類樣本數(shù)量相同的簇數(shù)，用簇代表原來的多數(shù)類樣本，從而對數(shù)據(jù)進行均衡化，該方法會導(dǎo)致丟掉較多的樣本，進而導(dǎo)致出現(xiàn)欠學習現(xiàn)象；文獻[6]中依據(jù)抽樣概率從多數(shù)類樣本中隨機抽取與少數(shù)類樣本數(shù)量相等的樣本，與少數(shù)類一起構(gòu)成訓(xùn)練集，這樣同樣會導(dǎo)致丟掉較多的樣本，為此，文中采用迭代的方式多次抽取，每次抽取都會修改樣本的抽樣概率，一方面該方法仍然會有部分樣本不被選中，另一方面，抽取的樣本無法保持原有數(shù)據(jù)的空間分布，為此本文采用先聚類再抽取的方式對多數(shù)類樣本進行劃分，劃分方法如算法1。

該方法抽取的樣本包含有對應(yīng)簇的空間信息，使得針對每個子集獲得的分類器有較好的分類性能，另外選取合理的m值，幾乎不會有樣本不被抽取，并且抽取的樣本與多數(shù)類樣本有相似的空間分布。

算法1數(shù)據(jù)劃分

輸入數(shù)據(jù)集

輸出獲得m個均衡的子集。

2 HK-Adaboost算法

算法需要依據(jù)每個子分類器的分類性能計算每個子分類器的權(quán)重，這里采用子分類器的分類錯誤率描述子分類器的權(quán)重，子分類器的權(quán)重表示為

在第t輪迭代中需要更新樣本的權(quán)重，改變子分類器的分類性能，新樣本的權(quán)重依據(jù)式(6)進行更新：

每輪迭代結(jié)束，對分類器進行集成時，要考慮上輪所獲得的分類器和本輪分類器進行集成，集成方法如下：

計算每輪迭代結(jié)束所獲得分類器的分類性能提升情況，并獲得該輪迭代后的分類器：

對的分類性能表示為

迭代結(jié)束后獲得最終分類器為

算法2的詳細過程如下：算法2HK-Adaboost算法

輸入數(shù)據(jù)集，迭代次數(shù)T，基礎(chǔ)分類器C。

1)用K均值聚類算法對數(shù)據(jù)集進行劃分，獲得m個均衡的子集；

for t=1：T

3) for i=1：M

利用式(5)計算每個分類器權(quán)重；

利用式(6)對各子集中樣本進行權(quán)重更新；

end for i

若分類效果沒有提升，則結(jié)束該子集上的迭代，若有提升，則依據(jù)公式(8)選擇提升效果最好的分類器作為第t次迭代后的分類器；

end for t

1)中，利用K均值聚類算法對多數(shù)類樣本進行聚類，K值為少數(shù)類樣本數(shù)，得到K個簇，然后采用有放回抽樣，從每個簇中隨機取出一個樣本，與少數(shù)量樣本一起構(gòu)成一個均衡的訓(xùn)練子集，然后重復(fù)該步驟，產(chǎn)生m個均衡的訓(xùn)練子集。

2)是對每個訓(xùn)練子集中的每個樣本賦予權(quán)值，初始權(quán)值都相等。

3)是第t次迭代時，每個訓(xùn)練子集上的訓(xùn)練過程，依據(jù)Adaboost算法思想，對每個子集上的每個樣本的權(quán)重進行更新，當?shù)趖次迭代結(jié)束后獲得的分類器為第t-1次迭代獲得分類器與第i個子集上前t-1次迭代獲得的分類器的加權(quán)和。每個分類器的分類性能評價指標可以是F1值、G-mean、AUC等，本文算法中采用與Adaboost一致的評價方式-分類錯誤率。

式(5)是依據(jù)分類器對樣本的分類錯誤樣本的權(quán)重之和計算分類器的權(quán)重，然后依據(jù)Adaboost算法中更新樣本權(quán)重的思想，應(yīng)用式(6)更新每個樣本的權(quán)重，第t輪迭代結(jié)束。

4)是計算第t次迭代結(jié)束后獲得的分類器，如果分類效果比上次迭代好，則進行后面步驟，否則丟棄該次迭代產(chǎn)生分類器。這里從m個子分類器中選擇提升效果最好的分類器作為第t次迭代后的分類器，提升效果的評價仍然可以采用F1值、G-mean、AUC等評價指標進行評價，本文為簡化算法，仍采用準確率作為評價指標，獲得本輪迭代的分類器。然后計算本輪所得分類器的分類性能，并計算本輪迭代所得分類器在最終分類器中的權(quán)重。

3 實驗分析

本文選擇8組不同的數(shù)據(jù)集進行實驗，8組數(shù)據(jù)集來自UCI數(shù)據(jù)庫，Car Evaluation、TICTAC-Toe Endgame、Liver Disorders、Breast Cancer、Haberman's Survival、Blood transfusion、Contraceptive Method Choice和Teaching Assistant Evaluation，所選實驗數(shù)據(jù)集的詳細信息如表1所示，可以看到數(shù)據(jù)集在一定程度上都是不均衡的，并且數(shù)據(jù)集的各個屬性是不連續(xù)的，另外本文算法是針對2類分類的，因此把數(shù)據(jù)集都轉(zhuǎn)化為2類的數(shù)據(jù)集[17,19]。

表 1 實驗數(shù)據(jù)集Table 1 dataset

3.1 實驗評價指標

針對均衡數(shù)據(jù)的分類多采用分類精度作為評價指標，而對于不均衡數(shù)據(jù)，更多關(guān)注的是少數(shù)類樣本的分類情況，這種基于相同錯分代價的評價指標不能很好描述分類性能。針對不均衡數(shù)據(jù)分類的評價指標多采用Recall、Precision、F-mean、G-mean、ROC曲線和AUC等，這些性能指標是基于混淆矩陣來計算的，對于二分類問題的混淆矩陣如表2所示。

表 2 混淆矩陣Table 2 Obfuscation matrix

依據(jù)混淆矩陣可以計算上面評價指標的計算公式：

Recall表示正類的查全率；Precision表示正類的查準率；F-mean同時考慮查全率和查準率，只有當兩個都大時F-mean的值才較大，可以較好的描述不均衡數(shù)據(jù)集下的分類性能；G-mean綜合考慮2類的準確率，任何一類準確率較低時，G-mean的值都會較小，因此能夠較好評價不均衡數(shù)據(jù)集下的分類性能。

ROC曲線則是以正負類的召回率為坐標軸，通過調(diào)整分類器的閾值而獲得一系列值對應(yīng)的曲線，由于ROC曲線不能定量評價分類器的分類性能，因此常采用ROC曲線下的面積AUC來評價分類器的分類性能，AUC值越大代表分類器的分類性能越好，本文實驗主要從上面所列評價指標來對比算法的性能。

3.2 異構(gòu)距離有效性驗證

表3中HDVM_KNN是指采用HDVM距離的K近鄰算法，KNN指采用歐氏距離的K近鄰算法，其中K取值為5的實驗結(jié)果，SVM是依據(jù)動態(tài)錯分代價的支持向量機算法，SVM和KNN是對數(shù)據(jù)進行歸一化操作后采用matlab中自帶的支持向量機算法進行實驗的結(jié)果，Car數(shù)據(jù)集的實驗是從數(shù)據(jù)集中隔一條記錄取一條的方式選取訓(xùn)練集，用全部樣本作為測試集的結(jié)果，其他數(shù)據(jù)集均是全部數(shù)據(jù)既是訓(xùn)練集又是測試集的結(jié)果。實驗結(jié)果主要依據(jù)常見的性能指標樣本準確率ACC、Recall、Precision、F-mean、G-mean和 AUC驗證算法的性能，實驗更加關(guān)注少數(shù)類樣本的分類性能。

表 3 實驗結(jié)果Table 3 Experimental result

由表3的實驗結(jié)果可以看出，基于異構(gòu)距離的KNN實驗結(jié)果除了Breast數(shù)據(jù)集的準確率和Contraceptive數(shù)據(jù)集的AUC、F1值外，其他指標都優(yōu)于采用歐氏距離的KNN算法的實驗結(jié)果，說明對于異構(gòu)數(shù)據(jù)集，異構(gòu)距離比歐氏距離能更準確的描述2個樣本之間的相似度。

3.3 與其他算法的性能對比

用每個數(shù)據(jù)集的全部數(shù)據(jù)作為訓(xùn)練集，同時用該數(shù)據(jù)作為測試集的實驗結(jié)果，詳細實驗數(shù)據(jù)如表4所示，其中KNN是K近鄰算法、Adaboost用的是matlab中自帶的算法、OK-Adaboost是本文所提算法(K近鄰算法采用歐氏距離進行計算)、HK-Adaboost是本文所提算法(K近鄰算法采用異構(gòu)距離進行計算)，實驗中中K近鄰算法的K取值為5，劃分子集數(shù)m取值為5，Adaboost算法迭代100次、OK-Adaboost和HK-Adaboost算法迭代20次。

表 4 算法性能對比1Table 4 Algorithm performance comparison 1

由于訓(xùn)練集和測試集相同，各個算法的各項指標都比較好，但是每項指標本文算法的性能都優(yōu)于其他算法，KNN算法和Adaboost算法沒有考慮數(shù)據(jù)集不均衡的問題，算法OK-Adaboost中若分離器采用的是歐氏距離，不能準確描述樣本間的相似程度。

表5給出的是各個數(shù)據(jù)集，取一半作為訓(xùn)練集、一半作為測試集。從第一條開始隔一條去一條作為訓(xùn)練集，剩余為測試集，實驗中取m＝5，K＝5，T＝20，詳細的實驗結(jié)果如表5所示。由于采用一半作為訓(xùn)練集，一半作為測試集，實驗所得各項性能指標明顯比表4要差，尤其是在Car和Contraceptive數(shù)據(jù)集上的分類性能，可以看到基于歐氏距離的算法要比基于異構(gòu)距離的算法效果要好，查看樣本之間的異構(gòu)距離，發(fā)現(xiàn)他們之間的差異遠遠小于歐氏距離之間的差異。分析數(shù)據(jù)發(fā)現(xiàn)計算樣本的值之間差異很小，即屬性值在各個類中出現(xiàn)的頻率相近，導(dǎo)致值接近0，即任意2個樣本之間的相似度都很高，也就不能很好區(qū)分2個樣本之間的差異。由此可以看到，異構(gòu)距離在這樣的數(shù)據(jù)集中，同樣不能很好的計算2個樣本的相似度。圖1和圖2是Haberman和Blood2個數(shù)據(jù)集下采用本文算法和Adaboost算法下的ROC曲線。

表 5 算法性能對比 2Table 5 Algorithm performance comparison 2

圖 1 Haberman數(shù)據(jù)集的ROC曲線對比Fig. 1 RCO figure of Haberman dataset

圖 2 Blood數(shù)據(jù)集ROC曲線對比Fig. 2 RCO figure of Blood dataset

4 結(jié)束語

針對異構(gòu)不均衡數(shù)據(jù)集下的分類問題，本文提出一種面向不均衡異構(gòu)數(shù)據(jù)的集成學習算法-HK-Adaboost算法，該算法從數(shù)據(jù)劃分、基于異構(gòu)距離的KNN及多個分類器的迭代集成等方面進行改進，可以提高分類器在異構(gòu)不均衡數(shù)據(jù)集下的分類性能，通過在8組UCI異構(gòu)數(shù)據(jù)集上進行實驗，驗證了算法在異構(gòu)不均衡數(shù)據(jù)上的分類性能。但實驗中遇到一些問題，如Adaboost算法對數(shù)據(jù)進行歸一化后的分類性能會更差、異構(gòu)距離計算時間復(fù)雜度高、數(shù)據(jù)劃分子集的個數(shù)如何最優(yōu)、如何擴展到多類問題等問題將是下階段的主要工作。