一種基于卡方檢驗的不平衡數(shù)據(jù)分類方法

浮盼盼，潘正高，王 勝，高亞蘭

宿州學(xué)院信息工程學(xué)院，宿州，234000

在知識發(fā)現(xiàn)與數(shù)據(jù)挖掘領(lǐng)域中，數(shù)據(jù)分布不平衡是數(shù)據(jù)分類所面臨的一個極具挑戰(zhàn)性問題。大多數(shù)分類算法在設(shè)計時，都是基于數(shù)據(jù)均衡分布、誤分代價相等的條件下，將最大化總體精度作為其目標(biāo)。然而，在許多關(guān)鍵領(lǐng)域，如信用卡欺詐行為檢測、衛(wèi)星雷達(dá)影像圖片中的石油泄漏檢測、罕見疾病的醫(yī)學(xué)診斷、國防安全系統(tǒng)的入侵檢測以及災(zāi)害報警系統(tǒng)的實時監(jiān)測等，這些領(lǐng)域往往由于某一類或者某些類數(shù)據(jù)樣本在采集過程中，因為代價昂貴或者數(shù)據(jù)采集過程不統(tǒng)一而造成訓(xùn)練樣本遠(yuǎn)遠(yuǎn)少于其他類。此時，傳統(tǒng)分類器在訓(xùn)練過程中就會由于缺乏足夠的樣本而使訓(xùn)練過程出現(xiàn)嚴(yán)重偏差，造成算法性能的下降。

為解決數(shù)據(jù)分布不平衡所造成的算法性能下降問題，國內(nèi)外學(xué)者先后從以下兩個方面進(jìn)行了研究：

(1)在數(shù)據(jù)層面上對偏斜的數(shù)據(jù)分布進(jìn)行修正，采用重采樣或構(gòu)建新樣本的思想來實現(xiàn)數(shù)據(jù)集的均衡化處理。如：文獻(xiàn)[1]針對數(shù)據(jù)重采樣過程中有用樣本信息丟失的問題，首先對數(shù)據(jù)樣本進(jìn)行聚類，提取多數(shù)類的聚類邊界，然后利用支持向量機(jī)(Support Vector Machine，SVM)進(jìn)行分類學(xué)習(xí)，該方法即保留了多數(shù)類中的有用樣本信息，又均衡了數(shù)據(jù)的分布，提高了SVM對稀有類樣本的識別能力；文獻(xiàn)[2]針對樣本構(gòu)建所引入的數(shù)據(jù)噪聲干擾與模型做過擬合現(xiàn)象，提出了一種單邊選擇鏈與樣本分布密度融合的分類算法，有效解決了合成少數(shù)類過采樣技術(shù)(Synthetic Minority Over-sampling Technique，SMOTE)的模型過擬合問題；文獻(xiàn)[3]基于錯分理論提出了一種混合采樣算法，有效解決了樣本構(gòu)建中所引入的數(shù)據(jù)噪聲干擾問題，提高了分類模型對稀有類的分類性能。

(2)在算法層面上對分類模型進(jìn)行改進(jìn)。這類研究往往采用組合分類或者代價敏感分析等方法對傳統(tǒng)分類算法進(jìn)行改進(jìn)，如：文獻(xiàn)[4]將代價敏感學(xué)習(xí)理論應(yīng)用于隨機(jī)森林分類算法中，提出了一種適用于不均衡數(shù)據(jù)的加權(quán)隨機(jī)森林分類方法；文獻(xiàn)[5]采用一種核校對的方法來調(diào)整類邊界面，這種通過更新核來構(gòu)建偏斜的算法被稱為類邊界校準(zhǔn)算法；文獻(xiàn)[6-8]基于統(tǒng)計學(xué)習(xí)理論為基礎(chǔ)的SVM，結(jié)合代價敏感學(xué)習(xí)、組合分類等技術(shù)對SVM進(jìn)行改進(jìn)，修正分類超平面，提高分類性能；文獻(xiàn)[9]通過對比分析Boosting算法的類間隔理論與SVM的最大間隔準(zhǔn)則，建立起二者之間的關(guān)聯(lián)關(guān)系，提出了LDM(Large Margin Distribution Learning)學(xué)習(xí)算法，算法在最大化類間隔平均值的同時最小化類間隔方差，即最大化類間隔分布，以此來優(yōu)化樣本集的類間隔分布，提高分類機(jī)的抗擬合性與泛化性能。

雖然上述研究對不均衡數(shù)據(jù)的分類都取得了良好的效果，但或多或少都隱含了一定的風(fēng)險因素，如模型中參數(shù)選取的盲目性、數(shù)據(jù)重采樣的隨機(jī)性等。本文針對文獻(xiàn)[9]中核函數(shù)的定義進(jìn)行優(yōu)化，提出了一種基于卡方檢驗的不均衡數(shù)據(jù)分類方法，以期解決參數(shù)選取的盲目性。該方法以復(fù)分析中的保形變換與統(tǒng)計分析中的卡方檢驗為基礎(chǔ)，結(jié)合基于核校對的類邊界校準(zhǔn)算法，對LDM中的核函數(shù)進(jìn)行修正定義，實現(xiàn)對邊界周圍空間分辨率的不對稱改變，補(bǔ)償數(shù)據(jù)偏斜對分類超平面的影響。通過對UCI標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實驗測試，發(fā)現(xiàn)該算法能夠很好地解決數(shù)據(jù)分布傾斜性所導(dǎo)致的分類器性能下降問題，提高了分類模型對不均衡數(shù)據(jù)集中稀有類的識別能力。

1 相關(guān)工作

核方法(Kernel Method，KM)，即基于核的機(jī)器學(xué)習(xí)方法，在機(jī)器學(xué)習(xí)領(lǐng)域里一度受到廣泛關(guān)注。在機(jī)器學(xué)習(xí)方法中，用核函數(shù)代替內(nèi)積運算，就得到了該方法所對應(yīng)的核方法，而用核函數(shù)代替內(nèi)積運算的技巧則被稱之為“核技術(shù)”，因其在SVM中的成功應(yīng)用，促進(jìn)了采用該技術(shù)改進(jìn)傳統(tǒng)數(shù)據(jù)處理算法的研究，并由此產(chǎn)生了多種基于核函數(shù)的方法，文獻(xiàn)[9]中的LDM算法同樣也運用了核技術(shù)。本文將采用卡方檢驗與保形核變換對其核函數(shù)的定義進(jìn)行優(yōu)化。

1.1 卡方檢驗

卡方檢驗是統(tǒng)計分析中專門用于計數(shù)數(shù)據(jù)的一種統(tǒng)計分析方法，主要用于檢驗由樣本得到的實際頻數(shù)與理論頻數(shù)的分布是否有顯著性差異，如果將由樣本得到的實際頻數(shù)記為f0，數(shù)據(jù)集的理論頻數(shù)記為fe，則卡方檢驗的計算公式為：

(1)

卡方值的大小會隨實際頻數(shù)與理論頻數(shù)差的大小而變化，兩者差越小，卡方值也越小，說明樣本分布與假設(shè)的理論分布越一致，反之，則說明樣本分布與假設(shè)的理論分布越不一致。

1.2 保形核變換

保形變換是復(fù)分析中的一個重要定理，因其優(yōu)異的保角不變性等特性被廣泛應(yīng)用于諸多領(lǐng)域。文獻(xiàn)[10]針對SVM對不均衡數(shù)據(jù)分類性能不高的問題提出了一種基于核函數(shù)的保形變換策略，利用該策略很好地提高了SVM對邊界附件樣本的解析度。核變換的一般形式為：

K′(x,x′)=D(x)K(x,x′)D(x′)

(2)

其中，D(x)是一個恰當(dāng)定義的正函數(shù)，如果D(x)和原核函數(shù)K均為高斯函數(shù)，則經(jīng)該變換后的函數(shù)K′也是一個高斯函數(shù)，且K′滿足Mercer條件，成為一個新的核函數(shù)。

對于D(x)的定義，隨后又有許多學(xué)者對其進(jìn)行研究，其中，文獻(xiàn)[11]將其擴(kuò)展到二分類問題中樣本數(shù)明顯不同的情況，提出了不對稱內(nèi)核擴(kuò)展(AKS)，其基本思想是對邊界面兩邊的區(qū)域范圍進(jìn)行不同程度上的擴(kuò)大，以便補(bǔ)償對少數(shù)類樣本的傾斜。它采用的D(x)定義形式為：

(3)

其中，S+與S-是由第一步標(biāo)準(zhǔn)SVM預(yù)測所得到的正負(fù)類樣本集，k1、k2是待尋優(yōu)的自由變量，算法通過尋找恰當(dāng)?shù)膋1、k2值來得到最佳核變換，從而在邊界面兩邊進(jìn)行不同的空間擴(kuò)展，以補(bǔ)償數(shù)據(jù)不平衡造成的偏斜。該算法具有較好的健壯性，但是額外增加了算法參數(shù)，文章采用網(wǎng)格搜索與交叉驗證的方法進(jìn)行尋優(yōu)，無疑增加了算法的計算開銷，文中指出，該參數(shù)值與每一類的樣本數(shù)均有關(guān)系，但并未找到明確的對應(yīng)關(guān)系。

1.3 大間隔分布學(xué)習(xí)算法

大間隔分布學(xué)習(xí)算法(LDM)是2014年南京大學(xué)計算機(jī)科學(xué)與技術(shù)系的周志華教授等通過對比分析Boosting算法的類間隔理論與SVM的最大間隔準(zhǔn)則而提出的一種學(xué)習(xí)算法[9]。該算法在最大化類間隔平均值的同時最小化類間隔方差，從而最大化樣本集的類間隔分布，優(yōu)化其類間隔分布。該模型類似于SVM，相當(dāng)于是對SVM的一種改進(jìn)，其模型方程如下：

s.t.yiωTφ(xi)≥1-ξi,

ξi≥0,i=1,…,m

(4)

其中，假設(shè)模型樣本集含有m個樣本點，記為：S={(x1,y1),…,(xm,ym)}，式(4)中X=[φ(xi),…,φ(xm)]，這里φ(x)是核函數(shù)引入地對樣本x的一個特征映射，即：k(xi,xj)=φ(xi)Tφ(xj)，式中y=[y1,…,ym]T，其余變量則同于軟間隔SVM，如下式(5)所示。

(5)

2 算法設(shè)計與描述

本文基于文獻(xiàn)[11]所提出的不對稱內(nèi)核擴(kuò)展思想，利用卡方檢驗與保形核變換的優(yōu)異特性，提出了一種基于卡方檢驗不均衡數(shù)據(jù)分類算法，算法利用公式(1)(2)(3)對模型(4)中的核函數(shù)進(jìn)行優(yōu)化改進(jìn)。

2.1 權(quán)重因子計算

加權(quán)是一種處理類不均衡問題的常用方法，該方法中權(quán)值的設(shè)置是關(guān)鍵。為平衡樣本分布，提高稀有類樣本的識別率，本文設(shè)置權(quán)值如下：

(6)

2.2 參數(shù)因子計算

對于上述數(shù)據(jù)集，其實際頻數(shù)與均衡分布情況下頻數(shù)的分布差異，可由卡方檢驗公式(1)計算而得：

(7)

(8)

2.3 算法描述

基于前文思想，本文算法的實現(xiàn)流程如圖1所示。算法首先利用標(biāo)準(zhǔn)分類器對訓(xùn)練集進(jìn)行初始訓(xùn)練，然后迭代式地對模型進(jìn)行更新。在每次迭代中，算法首先計算出加權(quán)因子wi與參數(shù)因子ki，然后按照公式(3)計算出矩陣D(x)，并按照公式(2)更新核矩陣K，最后利用更新后的核矩陣對模型進(jìn)行重新訓(xùn)練。具體描述如算法2.1所示。

按0.01 mm/min的位移速度施加軸向應(yīng)力，直至相似試件充分破壞，如圖1所示，記錄應(yīng)力-應(yīng)變曲線和試驗力-變形曲線，對相似試件單軸壓縮曲線進(jìn)行分析。

圖1 算法流程圖

算法2.1

Input:

訓(xùn)練集Xtrain，初始核函數(shù)K，最大迭代次數(shù)T

Output:

分類器LDMt

Begin

1：利用分類器LDM對初始訓(xùn)練集Xtrain進(jìn)行初始訓(xùn)練，得到初始分類器LDM0，其中核函數(shù)選用初始核函數(shù)K0=K；

2：t← 1

3：while (t<=T) {

5：利用公式(3)，結(jié)合分類器LDMt-1計算出的各樣本x∈Xtrain到近似超平面的距離f(x)，得出核變換中的矩陣Dt-1(x)；

6：結(jié)合舊核矩陣Kt-1，由公式(2)計算得到新核矩陣Kt；

7：使用新核矩陣重新訓(xùn)練得到新的分類模型LDMt；

8：t←t+1 }

9：返回 LDMt

End

3 實驗分析

3.1 實驗設(shè)置與數(shù)據(jù)集描述

為驗證文中算法性能，通過對比實驗將文中算法與其他經(jīng)典的不均衡數(shù)據(jù)分類算法進(jìn)行對比分析。其中對比算法選取利用不平衡率進(jìn)行加權(quán)的SVM、結(jié)合重采樣技術(shù)的SVM-SMOTE以及標(biāo)準(zhǔn)LDM算法。算法性能評價指標(biāo)采用經(jīng)典性能評價指標(biāo)F指標(biāo)、G指標(biāo)。實驗在Matlab編程環(huán)境下，利用Libsvm與LDM工具箱完成。各算法均采用交叉驗證思想運行3次，將實驗結(jié)果的平均值作為最后結(jié)果。實驗數(shù)據(jù)集采用UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的真實數(shù)據(jù)集，其描述如表1所示。

表1 原始數(shù)據(jù)集描述

注：“各類樣本數(shù)”按類標(biāo)號遞增的順序排列；“不平衡率”是各類所含樣本數(shù)中最大值與最小值的比值。

實驗采取十折交叉驗證法，一次選取各數(shù)據(jù)集的10%(向上取整)作為測試集，其余作為訓(xùn)練集。為測試不同不平衡率下的算法性能，對于多類數(shù)據(jù)集cmc以第2類為正類構(gòu)成兩類數(shù)據(jù)集cmc-1，glass數(shù)據(jù)集以第4、5、6類為正類構(gòu)成兩類數(shù)據(jù)集glass-1，yeast數(shù)據(jù)集以第4類為正類構(gòu)成兩類數(shù)據(jù)集yeast-1，以第5、6類為正類構(gòu)成兩類數(shù)據(jù)集yeast-2，以第7、8類為正類構(gòu)成兩類數(shù)據(jù)集yeast-3，以第9類為正類構(gòu)成兩類數(shù)據(jù)集yeast-4，最終得到訓(xùn)練集,如表2所示。

表2 對比實驗所采用的訓(xùn)練集描述

3.2 評價指標(biāo)

對不均衡數(shù)據(jù)分類算法性能評價的指標(biāo)大都基于混淆矩陣得來(表3)。在混淆矩陣中，TP(true positives)表示被正確分為正類的正類樣本數(shù)，F(xiàn)P(false positives)表示被錯分為正類的負(fù)類樣本數(shù)，F(xiàn)N(false negatives)表示被錯分為負(fù)類的正類樣本數(shù)，TN(true negatives)表示被正確劃分為負(fù)類的負(fù)

表3 混淆矩陣

類樣本數(shù)，本文基于此采用廣為使用的G-mean和F-measure作為算法的性能評價指標(biāo)，具體計算如下：

(1)G-mean值：

(9)

(2)F-measure值：

(10)

3.3 實驗結(jié)果與分析

利用上述訓(xùn)練集與相應(yīng)測試集，采用本文算法與實驗設(shè)置中的各對比算法分別進(jìn)行訓(xùn)練，在測試集上所得到的預(yù)測結(jié)果如圖2、圖3及表4所示。

圖2 各算法對不同測試集預(yù)測的F-measure 圖3 各算法對不同測試集預(yù)測的G-mean

數(shù)據(jù)集加權(quán)SVMSVM-SMOTELDM本文算法F-measureG-meanF-measureG-meanF-measureG-meanF-measureG-meanpima0.6890.760.3410.4720.7330.7970.8230.843haberman0.3480.5010.3330.4610.6880.6950.8540.867glass-10.780.8390.8450.9130.9230.950.9630.982cmc-10.3810.5720.2890.4860.4690.5970.6070.612yeast-10.7810.8410.80.8940.8570.9280.9270.981yeast-20.4740.7130.4620.7150.7380.8450.8480.889yeast-30.2110.6270.2730.6530.7150.7080.8270.753yeast-40.0470.6060.1110.6710.8070.8160.9230.986

由上述實驗結(jié)果可以看出，本文所提出的算法在不同不平衡率下均表現(xiàn)出良好的性能，尤其在數(shù)據(jù)集發(fā)生嚴(yán)重不平衡的情況下，如yeast-4數(shù)據(jù)集，其不平衡率達(dá)到了73，但其分類性能優(yōu)于對比算法，由圖2可以看出，該數(shù)據(jù)集的F-measure指標(biāo)表現(xiàn)最為明顯，由表4可以看出，在該數(shù)據(jù)集上，文中算法的F-measure指標(biāo)要高出SVM-SMOTE算法0.812，高出簡單加權(quán)SVM算法0.876，高出LDM算法0.116。由圖3可知，本文算法在不同數(shù)據(jù)集上的G-mean指標(biāo)也均優(yōu)于對比算法。

4 結(jié) 語

本文針對傳統(tǒng)分類器處理不均衡數(shù)據(jù)分類時性能下降的問題，提出了一種基于大間隔分類學(xué)習(xí)器的改進(jìn)算法，該算法利用卡方檢驗與保形核變換優(yōu)化了其核函數(shù)的定義。通過在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上的實驗測試表明，該算法對于具有不同特征的、不同不均衡率的數(shù)據(jù)分類，均表現(xiàn)出了較高的分類精度，有效解決了數(shù)據(jù)分布偏斜所造成的分類器性能下降問題。