不均衡大數據集下的文本特征基因提取方法

孫晶濤，張秋余

(1. 西安郵電大學計算機學院 西安 710121；2. 蘭州理工大學計算機與通信學院 蘭州 730050)

當前社會正在逐漸步入大數據時代，文本內容分析業已成為實現大數據理解與價值發現的有效手段，文本分類作為大數據內容挖掘的關鍵技術，廣泛應用于互聯網輿情監測與預警、網絡有害信息過濾以及情感分析等多個領域。而特征選擇作為文本分類中至關重要的一環，也直接影響到模型構建及分類效率和準確性。

目前在文本分類中，特征選擇方法多采用基于向量空間模型(vector space model)[1-2]的統計方法，但這類方法在實際應用中會出現兩方面的問題：1)集內樣本的類別分布不均衡，傳統特征選擇函數如文檔頻率(ocument frequency, DF)、信息增益(information gain, IG)、互信息(mutual information,MI)等方法[3-5]，往往假定數據集內樣本的類別分布相同或相近，使得所確定的特征項大多來自類別數量占優的大類，導致選出的最具區分度的特征子集無法準確反映整個樣本空間的真實分布；2)“大數據”[6-7]使得數據維數呈現爆炸性增長，面對超高維度的數據集，不僅意味著巨大的內存需求，而且意味著高昂的計算成本投入。在這些高維數據的特征空間中，繁多的特征點之間存在著很強的相關性，使得采用傳統方法選取的特征項泛化能力急劇惡化。如何從紛繁復雜的表象信息中提取出事物的本質特征、提高特征項的泛化能力就愈顯重要。

如同生物基因是生命體最小的功能單位一樣，文本特征基因也是文本最小的結構單位，其儲存著文本深層次的語義結構以及潛在的語義聯系，是全部文本信息的基本載體。本文正是研究如何在文本特征集中提取出穩定、泛化能力強的特征基因子集，從而降低向量空間的特征維數，提高分類識別效果。將信息熵引入特征點類別權重定義中，構造特征點對文本類別的區分度矩陣，消除傳統方法對不均衡樣本集進行特征提取時的缺陷，提高分類識別的正確性。采用獨立成分分析方法(independent component analysis, ICA)[8]，通過分析多維統計數據間的高階相關性，找出相互獨立的隱含信息成分，以此提取文本特征基因，減少特征采樣點數量，實現在不均衡大數據集中，較準確提取全面、真實反映文本內容信息的最優特征基因子集，提升文本分類識別的性能。通過在搜狐新聞數據(SogouCS)20151022語料庫上的實驗表明，文本特征基因提取方法(text feature gene extraction, TFGE)能夠使采用SVM(support vector machine)分類算法構造的文本分類器識別性能顯著提升。

1 相關工作

目前，國內外學者針對不均衡數據集下的數據分析進行了相關的研究。文獻[9]提出了基于逐級優化的逆隨機欠抽樣算法，該算法在去除訓練樣本中噪聲和重復信息的同時，使獲得的分類器更傾向于小類樣本，而采用Bagging方法進行多分類器集成，能夠盡可能保留有用信息，提高有效數據的利用率。文獻[10]提出了基于核聚類欠抽樣集成不均衡SVM分類算法，該算法首先在核空間中對大類樣本集進行聚類，然后隨機選擇出具有代表意義的聚類信息點，在減少大類樣本的同時，將SVM算法的分類界面向小類樣本方向偏移，并利用集成手段對基于核聚類的欠抽樣SVM算法進行集成，最終實現提高不均衡數據SVM算法泛化性能的目的。文獻[11]提出了改進的基于核密度估計的數據分類算法。該方法通過引入空間信息以及平滑參數，改善了原有核密度估計的分類方法在處理不均衡問題時所存在的缺陷。但該方法將空間信息仍定義為檢測點到類中心的距離，這必然導致方法的魯棒性較差。還有一些文獻提出了分類算法的改進，如boosting[12]、FCM-KFDA[13]、AdaBoost-SVM[14]、代價敏感學習算法[15]，這些方法所選特征子集通常較為優化，但面對“大數據”普遍存在運行效率低的問題。

然而現有處理手段大多集中在對樣本類別分布再平衡及分類算法改進等方面，對特征選擇、特征提取的研究尚不多見。文獻[16]提出了一種迭代的特征選擇模型，利用迭代過程中的聚類結果進行數據特征采樣排名，以此選取最優特征子集。但該模型中迭代函數以及迭代次數的選擇對問題求解影響因素很大，模型性能受到了一定制約。文獻[17]提出了一種應用于不均衡數據集下的無監督特征選擇方法，該方法在無監督環境下，對不同特征空間利用概率密度分析各特征數據的分布狀況，通過特征之間的數據分布關系來進行特征選擇。但該方法沒有考慮到數據分布的特點，對分類性能的影響較大。

本文研究擬以CHI統計選擇方法(χ2統計)為基礎，通過引入信息熵以及文本特征分布矩陣，克服χ2統計量在處理不均衡數據集上的不足，并采用ICA方法分析原本隱藏在大量數據集中的內在因子或成分信息，利用這些信息描述數據的本質結構，實現降維去噪，提高文本分類的識別率。

2 相關理論

2.1 CHI統計選擇方法

CHI統計選擇方法是假定在特征與類別之間，具有一階自由度χ2分布基礎上提出的一種FS方法。χ2值大小與特征和類別的相關性成正比[18-19]。特征t與類別ci的χ2值定義為：

式中，N表示樣本集中樣本的總數；A表示包含特征t并且類別為ci的樣本數；B表示包含特征t并且類別不為ci的樣本數；C表示不包含特征t，但類別為ci的樣本數；D表示既不包含特征t，類別也不為ci的樣本數。

可以看出，χ2值越大，特征t與類別ci越相關。當類別數較多時，可以分別計算特征t與不同類別的χ2值，選取其中最大的χ2值作為特征t的所屬類別，即

文獻[20]的實驗證明，CHI統計選擇方法具有較好的特征選擇性能。但從式(1)能夠看出，χ2值僅體現特征在樣本集中的文檔頻率，并沒有考慮特征的詞頻，導致CHI方法在處理低頻詞時具有較大誤差，使一部分噪聲詞被“優選”出來，降低了分類精度。

2.2 信息熵

1948年美國數學家香農(Claude Elwood Shannon)借鑒熱力學中熵的概念，系統性提出了信息的度量方法，并定義了信息熵[21]。

定義 1假設離散隨機變量X，其取值R={x1,x2,…,xn}為有限可數，取值隨機出現的概率分別為p(x1),p(x2),…,p(xn)，且則X的信息熵H(X)為：

2.3 獨立成分分析

ICA是從多元(多維)統計數據中尋找內在因子或成分的一種方法，有別于其他統計方法的特點在于：不僅能夠去除數據中各分量間的一、二階相關性，還具有發掘并去除數據間高階相關性的能力，使輸出分量不僅相互獨立，而且是非高斯分布[21]。

ICA基本模型[22]：假設存在n個隨機變量x1,x2,…,xn，而這些變量是由另外n個隨機變量s1,s2,…,sn的線性組合得到：

式中，aij(i,j=1,2,…,n)為實系數，在模型中，假設si在統計上彼此獨立。

為方便表示，通常選用向量-矩陣形式，即用隨機向量x來表示混合向量，其元素分別為x1,x2,…,xn，同樣地用s來表示元素s1,s2,…,sn。用矩陣A表示混合系數aij，由此混合模型可以寫為：

或寫為：

ICA的目的就是計算分離矩陣W，并得到一組相互獨立的隨機變量y1,y2,…,yn，使隨機向量y：

3 不均衡大數據集下的文本特征基因提取方法

3.1 不均衡數據集合上的特征選擇方法

3.1.1 基于χ2統計量的文本特征分布矩陣

CHI方法認為，特征的重要性主要由其χ2的大小決定，低于某一χ2值的特征一般不含或較少含有類別區分信息。但這一認知建立在數據集合類別分布處于平衡或準平衡狀態的條件下，并沒考慮類別分布處于不均衡狀態時，文檔類別分布對分類的影響，也沒有考慮特征詞頻對分類的影響。因此，在不均衡數據集條件下，傳統CHI方法存在明顯的缺陷。為了避免χ2統計量的不足，綜合考慮特征在每一個類別中的具體分布，需要對數據類別分布不均衡及特征選擇兩類問題進行處理。本文在現有χ2統計量中融入信息熵，以此建立新的加權χ2統計量矩陣，較好地解決了不均衡數據集條件下的特征選擇問題。通過對特征的類別分布進行一定程度的修正，不僅能夠清楚地反映特征項的實際分布情況，而且能極大地改善CHI統計選擇方法的性能。

為了解決不同特征類別之間存在的差異性，本文同時對特征t與類別ci進行加權，加權后的χ2統計量可定義為Wχ2(t,ci)。傳統特征選擇方法中W=1，如果小類別被分配較大權重，則小類別中χ2會增大，這些特征被選擇的機會也就會增大，從而提高小類別的分類精度，但如果分配給小類別χ2統計量的權重值過大，則會影響大類別中特征的選擇，因此如何設置權重顯得尤為重要，本文將權重定義為特征t與類別ci的信息熵值，即：

式中，p(t|ci)為特征t在類別ci中的出現概率；p(ci)為類別ci出現的概率；p(t,ci)為類別ci中特征t出現的概率。式(7)充分利用信息熵的反增長性，綜合H(t|ci)、H(ci)，一方面通過對類別權重的調節，賦予小類別較大的權重，使χ2統計量能夠客觀地反映類別分布對特征選擇的影響，有利于小類別特征的選擇，另一方面，通過控制特征的權重，有效防止噪聲詞被選中，確保整體的分類性能。

利用加權后的χ2統計量建立統計矩陣K：

式中，行與列分別表示特征在不同類別和相同類別中的加權概率分布。在此基礎上進行特征選擇操作，將避免過多考慮特征或過多考慮分類類別的缺陷。

3.1.2 算法描述

輸入：加權后的文本χ2統計量矩陣K。

輸出：文本特征子集T

算法步驟：

1)T=?;//T為特征集，初始化操作

2)依次選擇K中每一行ti，進行如下處理：

⑥φ≥0.85時，得到特征子集T。

算法的時間復雜度主要由步驟2)決定。算法的時間復雜度為O(nm)(n為特征個數，m為類別數)。此外，由算法的具體步驟可知，算法的空間復雜度為O(n)。

3.2 文本特征基因提取模式

ICA的目的就是計算出分離矩陣，并得到一組相互獨立的隨機變量。本文采用基于負熵的快速固定點算法(FastICA)[21,23]，通過分析多維數據間的高階統計相關性，找出相互獨立的隱含信息成分，以此提取獨立特征基因并完成分量間高階冗余的去除。

3.2.1 基于負熵的快速不動點算法

定義 2若隨機變量y的密度函數為py(x)，那么其微分熵的定義為：

定義 3負熵J的定義為：

式中，y?是與y具有相同相關(和協方差)矩陣的高斯隨機向量。

負熵很難直接計算，需要用近似的方法。負熵近似的經典方法是使用高階積累量及密度多項式方法。它相應的近似為：

式中，kurt(y)為y的峭度。但是這種估計方法存在非魯棒性問題，所以在實際問題中，一般使用非二次函數G的期望形式，相應的近似形式為：

式中，函數G可以選擇或通常取1。

FastICA算法即找到一個單位(長度)向量w，使得對應的投影wTz的非高斯性達到極大化，非高斯性利用式(11)定義的負熵近似J(wTz)來度量。

算法的基本形式描述為：

1)對數據進行中心化使其均值為0；

2)然后對數據進行白化得到z；

3)選擇要估計的獨立成分個數m，令i=1；

4)選擇一個具有單位范數的初始化(可隨機選取)向量wi；

6)標準化wi，wi←wi/||wi|| ；

7)如果尚未收斂，返回步驟5)；

8)令i←i+1，如果i≤m，返回步驟4)。

3.2.2 文本特征基因提取算法描述

在前面的內容中，分別介紹了加權χ2統計量的文本特征分布矩陣和獨立成分分析的文本特征基因提取方法，本文將這兩種方法結合來進行文本特征基因提取。具體算法描述：

1)中心化特征子集

計算文本特征子集X=(x1,x2,…,xp)的平均向量：

2)白化

式中，E為Cx的特征向量矩陣，且為正交矩陣；D為Cx的特征值矩陣，且為對角矩陣。

線性白化變換為：

白化后的數據為：

3)利用3.2.1節中的算法計算得到各獨立成分。

4 實驗與結果分析

4.1 實驗設計

本文實驗中所有代碼均在Matlab R2015a平臺上編寫，編譯運行的PC機參數為：HP Pavilion 15，Intel i7-6500U、8 GB內存、Win10 64位操作系統。

為驗證該文所提方法的合理性，選用搜狐新聞數據(SogouCS)20151022語料庫作為實驗數據集，語料庫包含12個大類，共10 902個文本，其類間分布并不均衡，其中，最大類中包含2 254個文本，最小類中只包含130個文本。為了檢驗各方法的實際處理效果，對語料庫進行了一定程度的補充和優化，如：補充了部分類型的文本、去除了一些數據不完整的文本，并從處理后的語料庫中選取7個類別：農林漁畜、醫學、娛樂、電子游戲、自然科學、藝術、運動休閑，類別選擇為有目的的隨機，選取類別中文本分布呈現較大的差異性，其中數據集中訓練集包含4 360個文本，測試集包含1 336個文本，訓練集的文本分布如圖1所示。文本預處理階段采用中國科學院的中文分詞工具ICTCLAS對數據進行處理。分類算法采用性能較優的SVM，具體實現利用臺灣大學LIBSVM工具包。

圖1 訓練集各類別文本數量

目前對分類器性能的評價通常選取查全率、準確率、F1三項指標。由于在不均衡數據集的分類中，分類結果極易偏向大類，如果仍采用這類傳統指標，則無法真實評價分類器的實際性能。本文采用宏平均查全率、宏平均準確率、宏平均F1以及混合矩陣下的真正類率(true positive rate, TPR)、負正類率(false positive rate, FPR)、精確度(accuracy rate, ACC)及AUC(area under the ROC curve)等指標對分類結果進行評價。

1)宏平均查全率為：

式中，ri表示第i個類別的查全率；|C|表示類別數。

2)宏平均準確率為：

式中，pi表示第i個類別的準確率。

3)宏平均F1為：

式中，F1i表示第i個類別的F1值。

4)TPR、FPR、ACC分別為：

式中，TP和TN表示實際正類和負類被正確判定的數目；FP表示將負類判定為正類的數目；FN表示將正類判定為負類的數目。

5)AUC表示ROC曲線下的面積。當ROC曲線不能很好地說明分類器效果時，通過該數值，能夠更清晰的說明分類器效果。

4.2 實驗測試與分析

為了得到更具統計意義的實驗結果，本文采用5折交叉檢驗方法，對DF、IG、MI以及新提出的文本特征基因提取方法(text feature gene extraction,TFGE)在SVM分類器上進行有效性評估。

表1列出了DF、IG、MI以及加權χ2統計量矩陣特征選擇方法在搜狐新聞數據(SogouCS)20151022語料庫上用LIBSVM分類器的實驗結果(采用徑向基核函數)。可以看出，在選取特征數量較少時，采用加權χ2統計量矩陣特征選擇方法優勢比較明顯，表明加權方法能夠更早地獲得較好的分類效果。

表1 不同特征選擇方法的性能比較

表2表示經過FastICA提取后的特征子集在LIBSVM分類器上的正確率變化情況(采用徑向基核函數)。可以看出，雖然分類識別準確率有小幅度下降，但特征子集規模減少約41%，實現了在大數據集高維特征空間中高階冗余的去除，所提取出的特征基因數據泛化能力顯著增強。

表2 加權χ2統計量矩陣特征選擇與特征基因提取方法的性能比較

表3列出了DF、IG、MI以及新提出的TFGE在搜狐新聞數據(SogouCS)20151022語料庫上用LIBSVM分類器的實驗結果(采用徑向基核函數，特征空間向量維數設置成4 000)。可以看出，TFGE的效果優于DF、IG和MI，宏平均F1值提高顯著，且該方法相較DF、IG和MI方法，SVM分類器的運算時間縮短了計算復雜度大大降低。

表3 4種方法的總體性能比較

圖2 4種方法的分類效果比較

從圖2中可以明顯看出，TFGE在特征數量為500時，就可以使SVM分類器的宏平均準確率達到85.04%，在特征數量為3 000時，SVM分類器的宏平均準確率達到最高89.47%，之后趨于穩定。由此可以看出，文本特征基因提取方法TFGE所選特征子集泛化性能優于DF、IG和MI。

在搜狐新聞數據(SogouCS)20151022語料庫上，采用將運動休閑類的230個樣本作為正例，其余為負例的方式，構造不均衡二分問題。表4列出了DF、IG、MI以及TFGE采用LIBSVM分類器的實驗結果。可以看出，DF與IG方法在解決不均衡問題時，兩者差異不大，MI方法則相對性能較差，TFGE各項指標均優于其他3種方法，表現出較優的分類性能。

表4 4種方法在二分問題上的性能比較

5 結 束 語

本文對傳統特征降維方法及不均衡數據集下的數據分析進行了深入研究，結合χ2統計分布矩陣及獨立成分分析思想，提出了一種新穎的文本特征基因子集提取方法，實現了多維統計數據中隱含信息成分的提取，克服了傳統分類器因類別分布不均衡導致的性能不佳問題。文中重點介紹了CHI統計選擇方法，利用信息熵構建了加權χ2統計量的文本特征分布矩陣，避免采用過抽樣或欠抽樣方法對原始不均衡數據集的類別分布所做出的改變，通過特征類別分布的修正，極大改善CHI統計選擇方法的性能。在不均衡數據集特征選擇過程中優先去除冗余和噪聲樣本，使得在減少數據的同時保留更多的有用信息。最后采用基于負熵的FastICA進行多維數據間的獨立隱含信息成分提取，獲取文本特征基因用于分類器集成，進一步提高對訓練樣本中有效信息的利用率。實驗結果表明，本文提出的不均衡大數據集下的TFGE使文本分類求解效率和準確率得到一定的提高，新方法有效且實用。另外，特征基因提取選擇僅僅是數據預處理的一個步驟，將文本特征基因提取思想用于實際應用，更好地適應其他領域的分類需求，是今后要進行的研究工作。

[1]馬力, 劉惠福. 一種改進的文本特征提取算法[J]. 西安郵電大學學報, 2015, 20(6)： 79-81.MA Li, LIU Hui-fu. Study on the extraction of characteristics of chinese text based on the LDA model[J].Journal of Xi'an University of Posts and Telecommunications, 2015, 20(6)： 79-81.

[2]曾琦, 周剛, 蘭明敬, 等. 一種多義詞詞向量計算方法[J].小型微型計算機系統, 2016(7)： 1417-1421.ZENG Qi, ZHOU Gang, LAN Ming-jing, et al. Polysemous word multi-embedding calculation[J]. Journal of Chinese Computer Systems, 2016(7)： 1417-1421.

[3]LI A, ZANG Q, SUN D, et al. A text feature-based approach for literature mining of lncRNA-protein interactions[J].Neurocomputing, 2016, 206： 73-80.

[4]YUAN M. Feature extension for short text categorization using frequent term sets[J]. Procedia Computer Science,2014, 31： 663-670.

[5]PEREZ-TELLEZ F, CARDIFF J, ROSSO P, et al. Weblog and short text feature extraction and impact on categorisation[J]. Journal of Intelligent & Fuzzy Systems,2014, 27(5)： 2529-2544.

[6]MORENO A, REDONDO T. Text analytics： the convergence of big data and artificial intelligence[J].International Journal of Interactive Multimedia and Artificial Intelligence, 2016, 3： 57-64.

[7]YUAN S, XIANG Y, SHI J E. Text big data content understanding and development trend based on feature learning[J]. Big Data Research, 2015(3)： 1-10

[8]BOUZALMAT A, KHARROUBI J, ZARGHILI A.Comparative study of PCA, ICA, LDA using SVM classifier[J]. Journal of Emerging Technologies in Web Intelligence, 2014, 6(1)： 64-68.

[9]陳睿, 張亮, 楊靜, 等. 基于BSMOTE和逆轉欠抽樣的不均衡數據分類算法[J]. 計算機應用研究, 2014(11)：3299-3303.CHEN Rui, ZHANG Liang, YANG Jing, et al.Classification algorithm for imbalanced data sets based on combination of BSMOTE and inverse under sampling[J].Application Research of Computers, 2014(11)： 3299-3303.

[10]陶新民. 不均衡數據SVM分類算法及其應用[M]. 哈爾濱：黑龍江科學技術出版社, 2011.TAO Xing-ming. Imbalance data SVM classification algorithm and its application[M]. Harbin： Heilongjiang Science and Technology Press, 2011.

[11]李俊林, 符紅光. 改進的基于核密度估計的數據分類算法[J]. 控制與決策, 2010, 25(4)： 507-514.LI JUN-lin, FU Hong-guang. Improved KDE-based data classification algorithm[J]. Control and Decision, 2010,25(4)： 507-514.

[12]LI Q J, MAO Y B, WANG Z Q. An imbalanced data classification algorithm based on boosting[C]//Proceedings of the 30th Chinese Control Conference. [S.l.]：IEEE, 2011.

[13]YIN S. A classification method for imbalanced data sets based on FCM-KFDA discriminant[J]. Journal of Huazhong Normal University, 2013, 47(6)： 776-780.

[14]LI P, BI T T, YU X Y, et al. Imbalanced data classification based on AdaBoost-SVM[J]. International Journal of Database Theory & Application, 2014, 7(5)： 85-94.

[15]QIONG G U, YUAN L, XIONG Q J, et al. A comparative study of cost-sensitive learning algorithm based on imbalanced data sets[J]. Microelectronics & Computer,2011, 28(8)： 145-146.

[16]KHOSHGOFTAAR T M, GAO K, NAPOLITANO A.Exploring an iterative feature selection technique for highly imbalanced data sets[C]//International Conference on Information Reuse and Integration. [S.l.]： IEEE, 2012.

[17]ALIBEIGI M, HASHEMI S, HAMZEH A. Unsupervised feature selection based on the distribution of features attributed to imbalanced data sets[J]. International Journal of Artificial Intelligence & Expert Systems, 2011, 2(1)：2011-2014.

[18]CHEN G, CHEN L. Augmenting service recommender systems by incorporating contextual opinions from user reviews[J]. User Modeling and User-Adapted Interaction,2015, 25(3)： 295-329.

[19]BULATOV A, BULATOVA N, LOGINOVICH Y, et al.Illusion of extent evoked by closed two-dimensional shapes[J]. Biological Cybernetics, 2014, 109(2)： 163-178.

[20]QIU Y F, WANG W, LIU D Y. Research on an improved CHI feature selection method[J]. Applied Mechanics &Materials, 2012 (241-244)： 2841-2844.

[21]芬海韋里恩. 獨立成分分析[M]. 北京： 電子工業出版社,2007.AAPO H. Independent component analysis[M]. Beijing：Publishing House of Electronics Industry, 2007.

[22]ROUIGUEB A, CHITROUB S, BOURIDANE A. Density estimation of high dimensional data using ICA and Bayesian networks[J]. Intelligent Data Analysis, 2014,18(2)： 157-179.

[23]吳微, 彭華, 張帆. FastICA和RobustICA算法在盲源分離中的性能分析[J]. 計算機應用研究, 2014, 31(1)：95-98.WU Wei, PENG Hua, ZHANG Fan. Performance analysis of FastICA and RobustICA on blind sources separation[J].Application Research of Computers, 2014, 31(1)： 95-98.