基于KL距離的不平衡數據漸進學習算法研究

趙向兵，周建慧，楊澤民

(山西大同大學計算機與網絡工程學院，山西 大同 037009)

1 引言

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

KL距離也稱相對熵，可對兩個概率在同一時間空間中的分布差異狀況進行度量[3]。半監督學習方法是采用漸進模式，將有標簽數據與無標簽數據相結合，挖掘不平衡數據中有效信息的漸進學習算法。本文研究基于KL距離的不平衡數據漸進學習算法，通過欠抽樣法使不平衡數據達到均衡狀態，運用基于KL距離的不平衡數據半監督學習算法實現處理后數據的漸進學習，獲取精準、可靠的不平衡數據分類結果。

2 基于KL距離的不平衡數據漸進學習算法研究

2.1 KL距離

體系的混亂水平可以用熵進行表示，熵在概率論、生命科學等領域應用非常廣泛。

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

(1)

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

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

(2)

相對熵即KL距離，不僅能對兩個分布函數之間的距離進行描述，還能對兩個分布函數之間轉化所需信息量進行描述[5，6]。

(3)

下述為KL距離包含的性質

(4)

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

(5)

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

(6)

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

(7)

KLmax的數學形式用式(8)描述

(8)

2.2 欠抽樣法

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

(9)

2.3 基于KL距離的不平衡數據半監督學習算法

分類器能利用訓練集P學習得到，未標識數據集用U描述，其內各實例的正負性需使用KL距離進行判定，若實例為負類的可能性較大，KL距離應越小；若實例為正類的可能性較大，KL距離應越大。

使用KL距離完成不平衡數據漸進學習的過程如下所述：

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

算法1：尋找可靠正例。

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

(a)Sp=?；

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

(c)Bk=?；

(d)根據P學習得到分類器，用于分類U；

(e)for (each instancedi∈U)

(h)Bk=Bk∪{di}

(j)關于各集合Bk，僅將KL距離最高的topk個實例留存，且清除U內該實例；

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

(l)Sp=Sp∪Bk

(m)returnSp；

(n)end

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

算法2：尋找可靠反例。

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

(a)Sn=?；

(b)根據P學習得到分類器，用于分類U；

(c)for (each instancedi∈U)

(f)Sn=Sn∪{di}；

(g)returnSn；

(h)end

3)修正的訓練集用P∪Sp∪Sn描述，其內存在可以對學習進行輔助的正類實例與負類實例，修正的未標識集用U-Sp-Sn描述，根據P∪Sp∪Sn學習得到logistic回歸分類器，用于分類U-Sp-Sn，以獲取全部負類實例，并通過欠抽樣法使得訓練數據集達到平衡狀態，具體過程用算法3描述。

算法3：基于KL距離的不平衡數據半監督分類。

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

(a)Un=?；

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

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

(d)if (P為非平衡數據)

(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內全部正類實例，使其歸為一類；

(k)if(P為非平衡數據)

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

(m)根據P學習得到分類器，用于分類U；

(n)for (each instancedi∈U)

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

(p)Un=Un∪{di}；

(q)returnUn；

(r)end

根據上述步驟可知，通過尋找可靠正例、可靠反例，可以實現對處理后數據集的最終分類。

3 結果分析

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

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

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

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

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

表1 本文算法使用前后各組數據的G-mean結果

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

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

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

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

4 結論

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