一種基于類別分布的增量特征選擇算法

石 莉，李 敏，孫慧慧

淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮北，235000

一種基于類別分布的增量特征選擇算法

石 莉，李 敏，孫慧慧

淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮北，235000

樣本數(shù)量分布不平衡時(shí)，特征的分布同樣會(huì)不平衡。大類別中經(jīng)常出現(xiàn)的特征，在小類別中很少出現(xiàn)或者根本不出現(xiàn)，使得分類器被大類別所淹沒，小類別的識別率很低。為此，根據(jù)數(shù)據(jù)的類別分布提出一種基于差異系數(shù)的增量特征選擇算法CVIFS(Coefficient Variance-based Incremental Feature Selection)，選取最具有區(qū)分能力的特征，提高小類別的識別率，使用區(qū)間估計(jì)檢測概念漂移。經(jīng)實(shí)驗(yàn)驗(yàn)證，該算法處理偏斜數(shù)據(jù)流時(shí)優(yōu)于信息增益，具有較低的均衡誤差率(Balanced Error Rate BER)。

概念漂移；偏斜分布；差異系數(shù)；信息增益

數(shù)據(jù)流中的概念漂移以及偏斜分布，使其樣本無法準(zhǔn)確反映整個(gè)空間的數(shù)據(jù)分布，分類器容易被大類別淹沒而忽略小類。針對偏斜分布，目前主要采取抽樣、單類別學(xué)習(xí)和特征選擇的方法來處理[1]。數(shù)據(jù)的高維性會(huì)使偏斜分布問題更為嚴(yán)重，因此特征選擇相對分類算法更重要[2]。

根據(jù)不平衡分類問題的特點(diǎn)，選擇對小類別有較好指示作用的特征是提高小類別分類性能的關(guān)鍵，所以選擇有豐富類別信息的特征是解決非均衡問題的一條有效的途徑。本文提出一種不依賴于其他方法的特征選擇方法，稱為基于差異系數(shù)的增量特征選擇算法(CVIFS)。該方法根據(jù)特征的類別分布，選擇在類間分布差異較大的特征，并結(jié)合增量學(xué)習(xí)來處理概念漂移問題。

移動(dòng)超平面數(shù)據(jù)上的實(shí)驗(yàn)表明，處理偏斜數(shù)據(jù)流時(shí)優(yōu)于信息增益，CVIFS具有較低的均衡誤差率(Balanced Error Rate BER)。

1 相關(guān)工作

傳統(tǒng)的特征選擇方法在均衡數(shù)據(jù)上效果很好，但在非均衡數(shù)據(jù)上效果并不理想[3-4]。因?yàn)檫@些方法一般傾向于高頻詞，導(dǎo)致非平衡問題中的小類別被大類別所淹沒。信息增益(IG)和卡方統(tǒng)計(jì)量(CHI)是傳統(tǒng)的特征選擇算法中效果最好的度量指標(biāo)[5]。近年來，很多學(xué)者對不均衡問題的特征選擇進(jìn)行了深入研究。Zheng等人提出顯式的近似最優(yōu)組合正特征(指示文檔屬于某類別的特征)和負(fù)特征(指示文檔不屬于某類別的特征)[6-7]能夠提高特征選擇在非平衡數(shù)據(jù)上的效果，但是這種框架依賴于其他方法，只有當(dāng)所依據(jù)的方法能夠很好地選擇正負(fù)特征時(shí)，此方法才是有效的。Chen首次提出基于ROC曲線的FAST(Feature Selection Assessment by Sliding Thresholds)特征選擇方法[8]，采用滑動(dòng)閾值機(jī)制進(jìn)行特征選擇，在偏斜小樣本數(shù)據(jù)集上能夠取得較好的效果；但樣本較大時(shí)，閾值設(shè)置會(huì)遇到麻煩，不適用于數(shù)據(jù)流上的特征選擇。靖紅芳等人依據(jù)特征在類間的分布特點(diǎn)，提出了基于類別分布的特征選擇框架[9]，采用類間方差區(qū)分屬性；然而,不同特征間的水平差異較大，需要區(qū)別對待，類間方差不能兼顧這一點(diǎn)。Wang等人采用一個(gè)探索評價(jià)函數(shù)選擇一定數(shù)量的特征[10]，選擇那些特征與目標(biāo)類之間的相關(guān)性高而特征相互之間的關(guān)聯(lián)性低的特征；然而，他們同樣沒有注意到不同特征間的水平差異。劉智等人依據(jù)特征的重要程度，提出基于W分布和D分布的動(dòng)態(tài)特征選擇方法[11]，然而計(jì)算開銷過大。

2 信息增益(IG)

信息增益是按照能“最佳分類”的特征A進(jìn)行劃分，該特征使得完成元組分類所需的平均信息量最小。信息增益作為特征選擇的度量，選擇信息增益值最大的那些特征。對于數(shù)據(jù)集D，特征A的信息增益定義如下：

Gain(A)=Info(D)-InfoA(D)

(1)

(2)

從信息增益的定義及描述可以看出，信息增益沒有重視小類別的重要性，因此不適合作為偏斜分布的數(shù)據(jù)流分類中的特征選擇度量。

3 基于差異系數(shù)的增量特征選擇算法(CVIFS)

當(dāng)數(shù)據(jù)流逐步流入時(shí)，到來的數(shù)據(jù)被分成數(shù)據(jù)段S1,S2,…,Sn,…，對于每個(gè)數(shù)據(jù)段Sk，僅有少量的正實(shí)例，絕大部分為負(fù)實(shí)例。其中，Sn是最近時(shí)間步到來的數(shù)據(jù)段。數(shù)據(jù)段Sn中的每個(gè)實(shí)例X={A1,A2,…,An;C}，其中Ai為X的特征，假設(shè)其值為el，l=1,2,…,v， 類變量C=+1或-1。

θP={X∈Sn,C(X)=+1}；

θN={X∈Sn,C(X)=-1}；

Sn1={X∈Sn,Ai=ei}；

θP1={X∈Sn1,C(X)=+1}；

θN1={X∈Snl,C(X)=-1}。

3.1 差異系數(shù)

差異系數(shù)CV常用于同一總體中的不同樣本的離散程度的比較。對于水平相差較大，則是對同一種測量的不同樣本，進(jìn)行觀測值離散程度的比較。差異系數(shù)大時(shí)，表明分散程度大，反之，分散程度小。在沒有概念漂移的情況下，對數(shù)據(jù)塊Sn中實(shí)例的差異系數(shù)為：

(3)

其中，SAi、MAi分別為關(guān)于特征Ai的標(biāo)準(zhǔn)差和平均值。

(4)

(5)

(6)

利用差異系數(shù)公式計(jì)算出每個(gè)特征的CV(Ai,C)之后，選擇值最高的z個(gè)特征。

3.2 概念漂移發(fā)現(xiàn)

(7)

(8)

(9)

增量特征選擇算法具體描述如下：

輸入:偏斜數(shù)據(jù)流S1,S2,…,Sk,…；特征個(gè)數(shù)z；

輸出:特征子集Fs;

1.Fs←?;t=0

3.Fs←Ranker(CV(Ai,C),z)

6.returnFs

算法1：基于差異系數(shù)的增量特征選擇算法(CVIFS)

4 實(shí)驗(yàn)及實(shí)驗(yàn)結(jié)果

為了驗(yàn)證CVIFS對概念漂移的適應(yīng)性及其在不同偏斜率情況下的分類效果，在移動(dòng)超平面數(shù)據(jù)集上與基于信息增益進(jìn)行了比較。實(shí)驗(yàn)所采用的分類器為NaiveBayes(NB)，評價(jià)函數(shù)為均衡誤差率(BER)。

4.1 移動(dòng)超平面數(shù)據(jù)集

4.2 評價(jià)函數(shù)

在一般情況下，研究者采用全體實(shí)例的分類精度來評價(jià)分類器的分類性能。由于偏斜數(shù)據(jù)的分布特點(diǎn)，精度不能很好地反映分類器的分類情況。理想的分類算法不僅能在小類別上取得好的結(jié)果，而且在大類別上也能取得好的結(jié)果。這就需要一個(gè)能夠兼顧二者的評價(jià)指標(biāo)。均衡誤差率(Balanced Error Rate BER)常用來衡量不均衡數(shù)據(jù)的分類[8]。均衡誤差率是兩個(gè)類的錯(cuò)誤率的平均值，由下式給出：

(10)

其中FP(true positives)指分類器正確標(biāo)記的正實(shí)例，F(xiàn)N(true negatives)是分類器正確標(biāo)記的負(fù)實(shí)例。FP(false positives)是錯(cuò)誤標(biāo)記的負(fù)實(shí)例，F(xiàn)N(false negatives)是錯(cuò)誤標(biāo)記的正實(shí)例。

4.3 實(shí)驗(yàn)結(jié)果

下面給出當(dāng)數(shù)據(jù)流中數(shù)據(jù)段的大小為1 600，特征個(gè)數(shù)為50，偏斜率r=1%,5%,10%,15%時(shí)的實(shí)驗(yàn)結(jié)果，偏斜率即為正實(shí)例所占的比例。當(dāng)數(shù)據(jù)流中的數(shù)據(jù)段為2 000，3 000，4 000時(shí)得到了相似的結(jié)果。

圖1 r=1%時(shí)兩種算法在超平面數(shù)據(jù)集上的比較

圖2 r=5%時(shí)兩種算法在超平面數(shù)據(jù)集上的比較

圖1是在超平面數(shù)據(jù)集上，將基于CV的增量特征選擇算法與基于IG的增量特征選擇算法所預(yù)測的均衡誤差率的比較。其中，橫坐標(biāo)是時(shí)間步，縱坐標(biāo)是在檢測集合上的均衡誤差率。實(shí)驗(yàn)中，偏斜率r=1%，從圖1中可以看出，基于CV的特征選擇算法的均衡誤差率明顯低于基于IG的特征選擇算法。遇到概念漂移時(shí)，基于CV的增量特征選擇算法也能很快地收斂到目標(biāo)概念。

圖3 r=10%時(shí)兩種算法在超平面數(shù)據(jù)集上的比較

圖4 r=15%時(shí)兩種算法在超平面數(shù)據(jù)集上的比較

圖2、圖3、圖4分別是在偏斜率r為5%，10%，15%時(shí)的兩種算法在超平面數(shù)據(jù)集上的比較。從圖中可以看出，隨著偏斜率的升高，基于信息增益的增量特征選擇算法的均衡誤差率有一定的下降，但遇到概念漂移時(shí)還是不能很快地適應(yīng)概念漂移?；诓町愊禂?shù)的增量特征選擇算法不但能夠保持較低的均衡誤差率，而且能夠很快地適應(yīng)概念漂移。在移動(dòng)超平面數(shù)據(jù)集上的實(shí)驗(yàn)表明，當(dāng)偏斜率下降時(shí)，基于信息增益的增量特征選擇算法的誤差率很高，且不能很好地處理概念漂移。這與信息增益選擇的屬性是平均信息量高有關(guān)?；陬悇e分布的差異系數(shù)增量特征選擇不但能夠保持較低的均衡誤差率，而且能夠很快地適應(yīng)概念漂移。這是因?yàn)椴町愊禂?shù)選擇的是類間分布差異較大的特征，也就是類別指示性強(qiáng)的那些特征。

5 結(jié)束語

本文給出的基于類別分布的差異系數(shù)增量特征選擇算法，并用區(qū)間估計(jì)檢測概念漂移。移動(dòng)超平面數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，在處理偏斜數(shù)據(jù)流時(shí)，優(yōu)于信息增益。但是，目前的特征選擇函數(shù)性能的評估均是通過試驗(yàn)驗(yàn)證的方法，即完全基于經(jīng)驗(yàn)的方法。因此進(jìn)一步的理論分析非常重要。而且，目前討論的是二類偏斜數(shù)據(jù)流問題，多分類的偏斜數(shù)據(jù)流特征選擇問題也有待進(jìn)一步研究。

[1]NiteshV.Chawla,NathalieJapkowicz,AleksanderKolcz.Editorial:SpecialIssueonLearningfromImbalancedDataSets[J].ACMSIGKDDExplorationnewsletter,2004,6(1):1-6

[2]FormanG.Anextensiveempiricalstudyoffeatureselectionmetricsfortestclassification[J].JournalofMachineLearningResearch,2003(3):1289-1305

[3]MladenicD，GrobelnikM.FeatureselectionforunbalancedclassdistributionandNoveBayes[C]//ProceedingsofsixteenthInternationalConferenceonMachineLearning(ICML1999).BledSlovenia，1999:258-267

[5]YangY,PedersenJO.AComparativeStudyonFeatureSelectioninTextCategorization[C]//ProceedingsofthefourteenthInternationalConferenceonMachineLearning(ICML1997).MashvilleTennesseeUSA,1997:412-420

[6]ZhengZ,WuX,SrihariR.FeatureSelectionforTextCategorizationonImbalancedData[J].ACMSIGKDDExplorationsnewsletter,2004(1):80-89

[7]ZhengZ,SrihariR.OptimallyCombiningPositiveandNegativeFeaturesforTextCategorization[C]//ProceedingsoftheICML’03WorkshoponLearningfromImbalancedDataSets.WashingtonDCUSA,2003:1-8

[8]ChenX，MichaelWasikowski.FAST:AROC-basedFeatureSelectionMetricforSmallSamplesandImbalancedDataClassificationProblems[C]//KDD’08.NevadaUSA,2008:124-132

[9]靖紅芳,王斌,楊雅輝.基于類別分布的特征選擇框架[J].計(jì)算機(jī)研究與發(fā)展,2009(9):1586-1593

[10]WangK,BunjiraMakond,WangK.AnImprovedSurvivabilityPrognosisofBreastCancerbyUsingSamplingandFeatureSelectionTechniquetoSolveImbalancedPatientClassificationData[J].BMCMedicalInformaticsandDecisionMaking,2013:1-14

[11]劉智,楊宗凱.采用動(dòng)態(tài)特征選擇的中文情感識別研究[J].小型微型計(jì)算機(jī)系統(tǒng),2014,35(2):358-364

[12]王勇.WEB數(shù)據(jù)挖掘研究[D].西安：西北工業(yè)大學(xué)研究生院,2006:42-43

[13]YueX,MoH,ChiZ.Immune-inspiredincrementalfeatureselectiontechnologytodatastreams[J].AppliedsoftComputing.2008,8(2):1041-1049

(責(zé)任編輯：汪材印)

An Algorithm of Incremental Feature Selection Based on Category Distribution

SHI LI,LI Ming,SUN Hui-hui

School of Computer Science and Tecknnology,Huaibei Normal University，Huaibei Anhui,235000,China

The distribution of sample size is very uneven, and the feature distribution of sample will be uneven too. Classifier is submerged by the majority classes easily and the minority classes are hardly distinguished, because the features which often appear in the majority classes hardly appear in the minority classes or even do not occur. In this paper, the method for discovering concept drifting on imbalanced data streams and CVIFS(Coefficient Variance-based Incremental Feature Selection) algorithm are proposed according to the characteristics of imbalanced classification problems. The interval estimation is used to detect concept drifting. Experimental study on Moving Hyperplane dataset shows that the proposed algorithm has lower BER(Balanced Error Rate)than Information Gain on imbalanced data streams with concept drifting.

concept drifting;imbalanced distribution;coefficient variance;information gain

10.3969/j.issn.1673-2006.2014.11.022

2014-07-28

安徽省高校自然科學(xué)研究項(xiàng)目“云計(jì)算環(huán)境下信息服務(wù)交互信任管理的關(guān)鍵問題研究”(KJ2013Z281)；淮北師范大學(xué)青年科研項(xiàng)目“基于類別分布的增量特征選擇算法研究”(2014xq012)；淮北師范大學(xué)青年自然科學(xué)研究項(xiàng)目“面向云服務(wù)的交互信任模型構(gòu)建與信任實(shí)體評價(jià)研究”(700693)。

石莉(1978-)，女，安徽淮北人，博士，講師，主要研究方向：評價(jià)方法與應(yīng)用，算法理論。

TP181

A

1673-2006(2014)11-0075-04