基于KL距離的不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法研究

趙向兵，周建慧，楊澤民

(山西大同大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)工程學(xué)院，山西 大同 037009)

1 引言

伴隨科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)量呈爆發(fā)式激增，其中蘊(yùn)含大量有價(jià)值的信息，對人們生產(chǎn)生活、科技研發(fā)等方面具有關(guān)鍵作用，因此將有意義的隱藏信息從海量數(shù)據(jù)中挖掘出來具有極高的應(yīng)用前景。學(xué)習(xí)算法是數(shù)據(jù)挖掘中普及最廣泛的技術(shù)之一，分類問題作為其中的重要分支，能根據(jù)已知數(shù)據(jù)創(chuàng)建具有辨識(shí)不同類別樣本數(shù)據(jù)能力的訓(xùn)練模型，以實(shí)現(xiàn)未知數(shù)據(jù)預(yù)測[1，2]。該算法通常以平衡數(shù)據(jù)集作為基礎(chǔ)，若數(shù)據(jù)集包含的各類樣本數(shù)不同，分類邊界會(huì)向樣本數(shù)少的類別(弱勢類)傾斜，易造成樣本數(shù)多的類別(強(qiáng)勢類)存在分類空間擴(kuò)大的問題，從而難以辨識(shí)弱勢類樣本，影響數(shù)據(jù)集分類效果。通常情況下，包含不同類別樣本數(shù)的不平衡數(shù)據(jù)集更具有研究價(jià)值，其中弱勢類樣本更能為人們提供有效的信息，例如網(wǎng)絡(luò)入侵檢測、垃圾短信過濾、森林火災(zāi)預(yù)警等，相對于含有大量數(shù)據(jù)的樣本，人們更關(guān)注含有少量數(shù)據(jù)的異常樣本，因此，精準(zhǔn)地辨識(shí)出不平衡數(shù)據(jù)中的弱勢類樣本尤為關(guān)鍵。

KL距離也稱相對熵，可對兩個(gè)概率在同一時(shí)間空間中的分布差異狀況進(jìn)行度量[3]。半監(jiān)督學(xué)習(xí)方法是采用漸進(jìn)模式，將有標(biāo)簽數(shù)據(jù)與無標(biāo)簽數(shù)據(jù)相結(jié)合，挖掘不平衡數(shù)據(jù)中有效信息的漸進(jìn)學(xué)習(xí)算法。本文研究基于KL距離的不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法，通過欠抽樣法使不平衡數(shù)據(jù)達(dá)到均衡狀態(tài)，運(yùn)用基于KL距離的不平衡數(shù)據(jù)半監(jiān)督學(xué)習(xí)算法實(shí)現(xiàn)處理后數(shù)據(jù)的漸進(jìn)學(xué)習(xí)，獲取精準(zhǔn)、可靠的不平衡數(shù)據(jù)分類結(jié)果。

2 基于KL距離的不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法研究

2.1 KL距離

體系的混亂水平可以用熵進(jìn)行表示，熵在概率論、生命科學(xué)等領(lǐng)域應(yīng)用非常廣泛。

概率空間用(Ω，F(xiàn)，P)描述，其中值為S(?RD)的D維離散隨機(jī)向量用X描述，在X分布律為{p(x)：x∈S}的條件下，X的熵采用式(1)進(jìn)行定義

(1)

如果信源用離散隨機(jī)向量表示，那么熵可以在平均意義上對信源整體特征進(jìn)行描述，同時(shí)能夠衡量信源的平均不確定性[4]。

F1(x)的同維分布函數(shù)用F1描述；F2(x)：RD→[0，1]的同維分布函數(shù)用F2描述；F1相對于F2的相對熵定義如式(2)所示

(2)

相對熵即KL距離，不僅能對兩個(gè)分布函數(shù)之間的距離進(jìn)行描述，還能對兩個(gè)分布函數(shù)之間轉(zhuǎn)化所需信息量進(jìn)行描述[5，6]。

(3)

下述為KL距離包含的性質(zhì)

(4)

3)可加性：邊緣分布函數(shù)用F1i(xi)，i=1，2，…，D、F2i(xi)，i=1，2，…，D描述，聯(lián)合分布函數(shù)用F1(x)=F1(x1，x2，…，xD)、F2(x)=F2(x1，x2，…，xD)描述，如果其分別與兩個(gè)邊緣分布函數(shù)的乘積相等，則可獲得式(5)

(5)

4)坐標(biāo)變換不變性：設(shè)定ρ1(x)、ρ2(x)描述概率密度，線性變換用y=f(x)描述，則可獲得式(6)

(6)

使用積分符號(hào)替換式(1)、式(2)中的求和符號(hào)，能分別得到連續(xù)隨機(jī)向量的熵與KL距離。連續(xù)隨機(jī)向量用X、Y描述，兩者的分布相似度可通過KL距離進(jìn)行度量[7，8]。在相同空間定義的密度函數(shù)用fX(x)、fY(x)描述，分別與D維高斯隨機(jī)向量X、Y相匹配。協(xié)方差矩陣等于Σ1，均值向量等于μ1，同時(shí)滿足這兩個(gè)條件的D維密度函數(shù)用fX(x)描述，表示為fX(x)～N(μ1，Σ1)；協(xié)方差矩陣等于Σ2，均值向量等于μ2，同時(shí)滿足這兩個(gè)條件的D維密度函數(shù)用fY(x)描述，表示為fY(x)～N(μ2，Σ2)，X和Y的KL距離用式(7)描述

(7)

KLmax的數(shù)學(xué)形式用式(8)描述

(8)

2.2 欠抽樣法

為防止產(chǎn)生不平衡數(shù)據(jù)樣本的盲目性，提升后續(xù)漸進(jìn)學(xué)習(xí)算法的分類效果，使用欠抽樣法對不平衡數(shù)據(jù)進(jìn)行處理。欠抽樣法操作簡單，可行性高，主要是將一些多數(shù)類樣本移除，以實(shí)現(xiàn)類別的平衡，能夠使少數(shù)類樣本全部留存[9]。抽樣程度用?描述，其計(jì)算過程如下所示

(9)

2.3 基于KL距離的不平衡數(shù)據(jù)半監(jiān)督學(xué)習(xí)算法

分類器能利用訓(xùn)練集P學(xué)習(xí)得到，未標(biāo)識(shí)數(shù)據(jù)集用U描述，其內(nèi)各實(shí)例的正負(fù)性需使用KL距離進(jìn)行判定，若實(shí)例為負(fù)類的可能性較大，KL距離應(yīng)越??；若實(shí)例為正類的可能性較大，KL距離應(yīng)越大。

使用KL距離完成不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)的過程如下所述：

1)使用P學(xué)習(xí)得到分類器，用于分類U。計(jì)算U內(nèi)各實(shí)例di的類別后驗(yàn)概率與P內(nèi)正類先驗(yàn)概率間的KL距離，根據(jù)KL距離，采用降序形式排列U內(nèi)全部隸屬某正類k的實(shí)例，將排在前面的幾個(gè)實(shí)例分配至P內(nèi)當(dāng)作k的實(shí)例，且將包含于U中的實(shí)例清除[10]，具體過程用算法1描述。

算法1：尋找可靠正例。

將P、U作為該算法的輸入，輸出為可能的正類實(shí)例集合，用Sp描述。P內(nèi)類標(biāo)簽集合用C={c1，c2，…，cn}描述；閾值用λ描述；U內(nèi)有幾率隸屬類k的實(shí)例集合用Bk描述，將其設(shè)定為空集。

(a)Sp=?；

(b)for each setBk，1≤k≤n

(c)Bk=?；

(d)根據(jù)P學(xué)習(xí)得到分類器，用于分類U；

(e)for (each instancedi∈U)

(h)Bk=Bk∪{di}

(j)關(guān)于各集合Bk，僅將KL距離最高的topk個(gè)實(shí)例留存，且清除U內(nèi)該實(shí)例；

(k)for (each setBk，1≤k≤n)

(l)Sp=Sp∪Bk

(m)returnSp；

(n)end

2)修正的訓(xùn)練集用P∪Sp描述，修正的未標(biāo)識(shí)集用U-Sp描述，使用P∪Sp學(xué)習(xí)得到新的分類器，用于分類U-Sp，獲取其內(nèi)各實(shí)例的KL距離。采用升序形式，并根據(jù)KL距離排列所有實(shí)例，清除U-Sp內(nèi)前μ個(gè)實(shí)例，并將其分配至P∪Sp內(nèi)當(dāng)作負(fù)類實(shí)例以對學(xué)習(xí)進(jìn)行輔助。具體過程用算法2描述。

算法2：尋找可靠反例。

將P、U作為該算法的輸入，輸出為可能的負(fù)類實(shí)例集合，用Sn描述，閾值用μ描述。

(a)Sn=?；

(b)根據(jù)P學(xué)習(xí)得到分類器，用于分類U；

(c)for (each instancedi∈U)

(f)Sn=Sn∪{di}；

(g)returnSn；

(h)end

3)修正的訓(xùn)練集用P∪Sp∪Sn描述，其內(nèi)存在可以對學(xué)習(xí)進(jìn)行輔助的正類實(shí)例與負(fù)類實(shí)例，修正的未標(biāo)識(shí)集用U-Sp-Sn描述，根據(jù)P∪Sp∪Sn學(xué)習(xí)得到logistic回歸分類器，用于分類U-Sp-Sn，以獲取全部負(fù)類實(shí)例，并通過欠抽樣法使得訓(xùn)練數(shù)據(jù)集達(dá)到平衡狀態(tài)，具體過程用算法3描述。

算法3：基于KL距離的不平衡數(shù)據(jù)半監(jiān)督分類。

將P、U作為該算法的輸入，輸出為負(fù)類實(shí)例集合，用Un描述。

(a)Un=?；

(b)if (P和U為文本數(shù)據(jù))

(c)使用TF-IDF方法操作P、U；

(d)if (P為非平衡數(shù)據(jù))

(e)使用欠抽樣法操作P；

(f)P=P∪Positive-Find(P，U)；

(g)U=U-Positive-Find(P，U)；

(h)P=P∪Negative-Find(P，U)；

(i)U=U-Negative-Find(P，U)；

(j)兼并P內(nèi)全部正類實(shí)例，使其歸為一類；

(k)if(P為非平衡數(shù)據(jù))

(l)使用欠抽樣法操作P；

(m)根據(jù)P學(xué)習(xí)得到分類器，用于分類U；

(n)for (each instancedi∈U)

(o)if(p(“-”|di)>p(“+”|di))

(p)Un=Un∪{di}；

(q)returnUn；

(r)end

根據(jù)上述步驟可知，通過尋找可靠正例、可靠反例，可以實(shí)現(xiàn)對處理后數(shù)據(jù)集的最終分類。

3 結(jié)果分析

從UCI數(shù)據(jù)庫中選擇Churn、UCIsubject兩個(gè)不平衡數(shù)據(jù)集作為實(shí)驗(yàn)對象，有效樣本數(shù)分別為3500、4528，使用本文算法對數(shù)據(jù)集進(jìn)行漸進(jìn)學(xué)習(xí)，以驗(yàn)證該學(xué)習(xí)算法的分類性能，該算法可通過Java編程語言實(shí)現(xiàn)，所用分類器均利用API完成。引入G-mean度量本文算法的整體分類性能，該指標(biāo)能保證當(dāng)正、負(fù)類分類精度均衡時(shí)，使兩類的分類精度達(dá)到最大，G-mean值越高，算法的分類性能越優(yōu)異。定義非平衡因子imbf以對各類之間的非平衡性進(jìn)行度量，imbf值越大，非平衡性越高。

以Churn不平衡數(shù)據(jù)集作為測試對象，數(shù)據(jù)集中正例數(shù)量與反例數(shù)量的比用a描述。當(dāng)imbf為0.3時(shí)，使用欠抽樣法與未使用欠抽樣法的G-mean隨a的變化情況用圖1描述。

圖1 使用與未使用欠抽樣法的G-mean結(jié)果

從圖1可以看出，在a值小于0.8的條件下，使用與未使用欠抽樣法的G-mean均處于較高數(shù)值，當(dāng)a值大于等于0.8時(shí)，兩者均有輕微下降趨勢；使用欠抽樣法的G-mean值始終高于未使用欠抽樣法的G-mean值，且均保持在0.8以上，最大G-mean值高達(dá)0.91，而未使用欠抽樣法的最大G-mean值約為0.7。對比實(shí)驗(yàn)結(jié)果表明，使用欠抽樣法對不平衡數(shù)據(jù)進(jìn)行均衡化處理可極大地提升本文算法的分類性能。

選擇UCIsubject不平衡數(shù)據(jù)集中的10組數(shù)據(jù)進(jìn)行測試，將a的值設(shè)定為0.1，將imbf的值設(shè)定為0.2，將本文算法使用前后各組數(shù)據(jù)的G-mean結(jié)果進(jìn)行對比，詳情用表1描述。

表1 本文算法使用前后各組數(shù)據(jù)的G-mean結(jié)果

分析表1可以發(fā)現(xiàn)，本文算法使用前，僅有數(shù)據(jù)組7的G-mean值超出0.8，其它數(shù)據(jù)組的G-mean值均處于較低數(shù)值，特別是數(shù)據(jù)組4和數(shù)據(jù)組9的G-mean值低于0.5；本文算法使用后，各組數(shù)據(jù)的G-mean值有顯著提升，且均保持在0.8以上，尤其是數(shù)據(jù)組2、5、6、7、9的G-mean值已達(dá)0.9以上，最高G-mean值為0.95。對比這些數(shù)據(jù)可表明，本文算法具有較優(yōu)異的不平衡數(shù)據(jù)整體分類性能，漸進(jìn)學(xué)習(xí)效果優(yōu)勢明顯。

使用F-measure(查全率與查準(zhǔn)率的調(diào)和均值)指標(biāo)度量本文算法對于不平衡數(shù)據(jù)集中弱勢類樣本的分類性能，F(xiàn)-measure值越大，分類性能越理想。以Churn不平衡數(shù)據(jù)集作為測試對象，不同抽樣比例下，本文算法使用前后的F-measure結(jié)果用圖2描述。

圖2 本文算法使用前后的F-measure結(jié)果

分析圖2可以看出，隨著抽樣比例持續(xù)增加，本文算法使用前后的F-measure值均呈現(xiàn)波動(dòng)式變化；當(dāng)抽樣比例小于40%時(shí)，兩者的F-measure值較為接近，波動(dòng)趨勢基本一致；當(dāng)抽樣比例大于40%時(shí)，兩者的F-measure值差距增大；相對于本文算法使用前的F-measure值，本文算法使用后的F-measure值在任何抽樣比例下都保持最高，且在抽樣比例較大時(shí)，F(xiàn)-measure值存在緩慢上升趨勢。由實(shí)驗(yàn)結(jié)果可得，本文算法能很好地分類出不平衡數(shù)據(jù)集中的弱勢類樣本，學(xué)習(xí)效果符合預(yù)期。

4 結(jié)論

伴隨各行各業(yè)發(fā)展的逐漸成熟，大量數(shù)據(jù)呈爆發(fā)式增長，為從海量數(shù)據(jù)中提取隱藏的有效信息，研究基于KL距離的不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法，通過KL距離與欠抽樣法相結(jié)合，使用半監(jiān)督學(xué)習(xí)算法實(shí)現(xiàn)不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)。由實(shí)驗(yàn)結(jié)果可知，該算法具有極好的分類性能，且適用性較強(qiáng)，在各類檢測、辨識(shí)、預(yù)警等技術(shù)領(lǐng)域中發(fā)展前景廣闊。