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

石 莉，李 敏，孫慧慧

淮北師范大學計算機科學與技術學院，安徽淮北，235000

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

石 莉，李 敏，孫慧慧

淮北師范大學計算機科學與技術學院，安徽淮北，235000

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

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

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

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

移動超平面數據上的實驗表明，處理偏斜數據流時優于信息增益，CVIFS具有較低的均衡誤差率(Balanced Error Rate BER)。

1 相關工作

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

2 信息增益(IG)

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

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

(1)

(2)

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

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

當數據流逐步流入時，到來的數據被分成數據段S1,S2,…,Sn,…，對于每個數據段Sk，僅有少量的正實例，絕大部分為負實例。其中，Sn是最近時間步到來的數據段。數據段Sn中的每個實例X={A1,A2,…,An;C}，其中Ai為X的特征，假設其值為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 差異系數

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

(3)

其中，SAi、MAi分別為關于特征Ai的標準差和平均值。

(4)

(5)

(6)

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

3.2 概念漂移發現

(7)

(8)

(9)

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

輸入:偏斜數據流S1,S2,…,Sk,…；特征個數z；

輸出:特征子集Fs;

1.Fs←?;t=0

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

6.returnFs

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

4 實驗及實驗結果

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

4.1 移動超平面數據集

4.2 評價函數

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

(10)

其中FP(true positives)指分類器正確標記的正實例，FN(true negatives)是分類器正確標記的負實例。FP(false positives)是錯誤標記的負實例，FN(false negatives)是錯誤標記的正實例。

4.3 實驗結果

下面給出當數據流中數據段的大小為1 600，特征個數為50，偏斜率r=1%,5%,10%,15%時的實驗結果，偏斜率即為正實例所占的比例。當數據流中的數據段為2 000，3 000，4 000時得到了相似的結果。

圖1 r=1%時兩種算法在超平面數據集上的比較

圖2 r=5%時兩種算法在超平面數據集上的比較

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

圖3 r=10%時兩種算法在超平面數據集上的比較

圖4 r=15%時兩種算法在超平面數據集上的比較

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

5 結束語

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

[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].計算機研究與發展,2009(9):1586-1593

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

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

[12]王勇.WEB數據挖掘研究[D].西安：西北工業大學研究生院,2006:42-43

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

(責任編輯：汪材印)

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

安徽省高校自然科學研究項目“云計算環境下信息服務交互信任管理的關鍵問題研究”(KJ2013Z281)；淮北師范大學青年科研項目“基于類別分布的增量特征選擇算法研究”(2014xq012)；淮北師范大學青年自然科學研究項目“面向云服務的交互信任模型構建與信任實體評價研究”(700693)。

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

TP181

A

1673-2006(2014)11-0075-04