文本分類中基于綜合度量的特征選擇方法

楊杰明,劉元寧,曲朝陽,劉志穎

(1.東北電力大學 信息工程學院,吉林 吉林 132012；2.吉林大學 計算機科學與技術學院,長春 130012)

隨著IT應用的不斷增長,人工管理文本數字信息已成為一項不可能完成的任務.自動文本分類技術是處理海量文本信息的有效方法,近年來已在許多領域得到廣泛應用.目前,已有很多成熟算法應用于文本分類中,如Bayes分類器、支持向量機、決策樹、K-近鄰方法等.然而,文本分類中最大的特點是高維性,即使是一個并不太大的語料集,它的維度也能達到上萬維甚至十幾萬維.在機器學習過程中,高維度會帶來兩方面的問題：1) 在高維環境中,大部分成熟算法不能得到高效的應用;2) 在高維環境中訓練分類器時,不可避免地會產生過擬合現象[1].因此,降維成為文本分類中的一個重要研究方向.目前,降維主要有兩種實現方式,即特征選擇和特征提取.特征提取是在原有特征的基礎上,通過組合、轉換生成一組全新特征集合的技術,如特征項聚類、隱含語義索引[2]和獨立分量分析[3]等.特征提取方式能捕獲特征間的語義關系,但表示文本的特征不易理解、計算成本較高.特征選擇算法是根據某種特征度量函數,衡量一個特征在分類中所起作用的重要度,并按重要度排序,然后根據排序結果從原有的特征集合中選擇重要度最高的少數特征組成一個特征子集,最終實現文本的表示和分類器的訓練.特征選擇算法運算效率高、實現方便快捷,是當前文本分類中最常使用的降維方法[4-5].目前已有很多特征選擇方法應用在文本分類的降維過程中,如文檔頻率(DF)、信息增益(IG)、卡方檢驗(CHI)[6-7]、正交質心(OCFS)[8]和特征質心(FCFS)特征選擇算法[9]等.

本文提出一種新的特征選擇算法,該算法從兩方面綜合度量一個特征對于分類的重要性,并在20-Newgroups,Reuters和WebKB這3個數據集上與文檔頻率、信息增益、卡方檢驗、正交質心和FCFS特征選擇算法進行了對比.實驗結果表明,該算法能有效提高文本分類性能.

1 問題描述及相關技術

1.1 問題描述

預先給定一個整數K,在盡可能保證文本分類性能不受影響的前提下,特征選擇算法從原始的特征集合T中選擇一個子集T′(|T′|?|T|).Yang等[6]指出最佳的特征選擇算法和合適的特征子集數量不但不損害分類器的性能,反而能提高分類效果.目前,應用在文本分類中的特征選擇方法可分為3類,即嵌入式特征選擇(embed)、融合式特征選擇(wrapper)和過濾式特征選擇(filtering).嵌入式的特征選擇方法是將特征選擇的過程直接嵌入到分類器的學習過程中,而融合特征選擇方法是利用某個分類器學習算法作為特征的評價標準去選擇特征子集,再利用該特征子集訓練分類器.過濾式特征選擇方法先利用一個獨立的評價函數去度量一個特征對分類的重要程度,然后根據度量值對所有的特征進行排序,最后選擇K個度量值最高的特征構成特征子集.由于易于操作、計算成本低、分類效果好等特點,因此過濾式特征選擇方法應用廣泛.本文提出的算法也是過濾式特征選擇方法.

1.2 相關技術

1.2.1 文檔頻率 文檔頻率是一個簡單而有效的特征選擇算法,它計算包含某個特征的文檔數量.主要思想是如果一個特征出現在很少的文本中,則該特征對分類沒有用,甚至可能降低分類性能,所以該特征選擇算法保留那些具有高文檔頻率的特征.該算法可表示為

DF(tk,ci)=P(tk|ci).

1.2.2 信息增益 信息增益是機器學習領域常用的算法.如果一個特征的信息增益值越大,則表明該特征對分類越有用.特征tk相對于類別ci的信息增益可表示為

1.2.3 卡方檢驗 卡方檢驗是數理統計學中用于度量兩個變量獨立性的方法.在文本分類中,卡方檢驗被用于確定特征tk與類別ci的獨立性程度.如果χ2(tk,ci)=0,則表示特征tk和類別ci是相互獨立的,即特征tk對類別ci不具有任何代表性;反之,卡方檢驗值越大,該特征對分類越有用.卡方檢驗公式定義為

1.2.4 正交質心 正交質心先計算一個特征在每個類別和在整個訓練集中的質心,然后根據每個類質心與整個訓練集質心計算出該特征的分值.特征的分值越大,該特征包含越多的分類信息.一個特征的正交質心公式定義為

1.2.5 FCFS特征選擇算法 FCFS算法先計算特征tk出現在所有類別中的質心tck,然后將特征tk在類別ci中的特征頻率與tck的偏差作為該特征度量,值越大則越具有類別代表性.FCFS算法可描述為

FCFS(tk,ci)=tf(tk,ci)-tf(tk)/|C|.

2 算法設計

目前,大多數特征選擇算法都是在特征×類別矩陣的基礎上進行的.在特征×類別矩陣中,行表示出現在訓練集中的每個特征,列表示預定義的類別,矩陣中的元素表示某個特征出現在某一類別中的特征頻率,見表1.

表1 特征×類別矩陣Table 1 Feature×category matrix

2.1 算法思想

FCFS算法根據一個特征在不同類別中出現的特征頻率計算該特征在不同類別中的質心,然后計算該特征在某一類別中偏離該質心的距離.如果特征tk在類別ci中偏離質心的距離最大,則表明該特征tk擁有最多的類別ci信息.FCFS算法即為通過一個特征偏離類別質心的程度度量該特征在某一類別中相對于在其他類別中的重要程度.

正交質心特征選擇算法首先計算所有特征在整個訓練集中的質心及在每個類別中的質心,然后利用每個類別的質心和整個訓練集質心計算出所有特征對分類的重要程度.正交執行特征選擇算法主要是計算類別內部一個特征相對其他特征對分類的重要程度.

事實上,FCFS算法只關注了一個特征出現在某一類別中相對于出現在其他類別中的重要程度,而正交質心算法只考慮了某一類別中一個特征相對于其他特征的重要程度.上述兩種算法都只分別考慮了特征×類別矩陣中的一方面,即FCFS算法只關注特征×類別矩陣的行,而正交質心只關注特征×類別矩陣的列.如表1中的特征,按照FCFS算法特征project包含類別1的信息最多,而從正交質心算法的角度看則是特征design最能代表類別1.基于上述原因,本文提出一種新的特征選擇算法,該算法彌補了上述兩種算法的不足,同時考慮特征×類別矩陣的行和列,綜合度量一個特征對分類的重要程度.

2.2 算法描述

輸入：V,D,K.其中:V表示特征×類別矩陣,包含T個特征,C個類別,矩陣中元素tf(i,j),1≤i≤T,1≤j≤C,表示第i個特征在第j類別中的特征頻率;D表示類別中文本數量向量{d1,d2,…,dj},1≤j≤C,dj表示第j個類別中的文本數量;K表示要選擇的特征數量.

輸出：特征子集Vs.

算法如下:

1) 計算整個訓練集中的特征質心向量,M={m1,m2,…,mi},其中mi表示第i個特征的質心,

3) for每個特征ti∈V;

4) for每個類別ci∈C

計算特征ti在類別cj中相對于類間質心tci的偏移量,cp(i,j)=tf(i,j)-tci;

計算特征ti的總體重要性,ICFS(i,j)=tp(i,j)*cp(i,j);

end

end

5) 按照ICFS(i,j)對所有的特征進行排序;

6) 選擇ICFS(i,j)值最高的K個特征構成一個新的特征集合Vs.

3 實驗環境與結果

3.1 數據集

為了驗證算法的有效性,本文在3個不同的數據集上進行實驗驗證.其中,20-Newgroups是文本分類中常采用的語料集,共包含19 997個文本,且所有的文本被平均劃分到20個不同的類別中；Reuters-21578語料集中共包含21 578個路透社新聞報道,所有的新聞報道被不均勻的劃分到135個類別中,本文采用文本數量最多的10個類別；WebKB語料集中包含4個不同大學網站的網頁集合,8 282個網頁被劃分到7個不同的類別中.本文采用“course”,“faculty”,“project”和“student”4個類別作為訓練集.

3.2 分類器

在實驗過程中,本文使用兩個不同的分類器.其中,Bayes分類器是建立在出現于一個文本中的特征與其他特征無關的假設基礎上的分類算法.目前,Bayes分類器有兩種常用模型: 多項式模型和多元Bernoulli模型[10].本文采用多項式模型.支持向量機是一個高效的文本分類器.本文采用libsvm工具包[11],并選擇缺省參數和線性核.

3.3 評價準則

采用Micro-F1和準確率[12-14]度量本文提出特征選擇算法的性能：

其中:P表示查準率;R表示查全率;TP表示正確劃分為正類的數量;TN表示正確劃分為負類的數量;FP表示錯誤劃分為正類的數量;FN表示錯誤劃分為負類的數量.

3.4 實驗結果

3.4.1 Micro-F1性能比較 表2～表4分別列出了6個不同特征選擇算法應用在20-Newgroups,Reuters-21578和WebKB語料集上時,Bayes分類器和支持向量機分類器的Micro-F1性能比較結果.由表2可見,當ICFS特征選擇算法應用在20-Newgroups語料集時,Bayes和支持向量機的分類性能優于信息增益、文檔頻率和正交質心,次于卡方檢驗和FCFS算法.由表3可見,當ICFS算法應用在Reuters-21578語料集上時,Bayes和支持向量機分類器的性能均優于其他5個特征選擇算法.由表4可見,ICFS算法應用在WebKB語料集上時,分類器的性能優于其他特征選擇算法,特別是采用支持向量機分類器時.

表2 6種不同特征選擇算法應用在20-Newgroups語料集時Bayes分類器和支持向量機分類器的Micro-F1性能比較Table 2 Micro-F1 measure result by Na?ve Bayes and SVM classifiers for 6 feature selection algorithms on 20-Newsgroups

表3 6種不同特征選擇算法應用在Reuters-21578語料集時Bayes分類器和支持向量機分類器的Micro-F1性能比較Table 3 Micro-F1 measure result by Na?ve Bayes and SVM classifiers for 6 feature selection algorithms on Reuters-21578

表4 6種不同特征選擇算法應用在WebKB語料集時Bayes分類器和支持向量機分類器的Micro-F1性能比較Table 4 Micro-F1 measure result using Na?ve Bayes and SVM classifiers for 6 feature selection algorithms on WebKB

3.4.2 分類準確率性能比較 圖1～圖6為6種特征選擇算法應用在3個不同語料集上時Bayes和支持向量機分類器的分類準確率性能曲線.由圖1和圖2可見,應用ICFS特征選擇算法時的Bayes分類器和支持向量機分類器的準確率曲線高于信息增益、文檔頻率和正交質心算法,而低于卡方檢驗和FCFS算法.由圖3可見,ICFS算法應用在Retuers-21578語料集上時,Bayes分類器的準確率曲線除了當特征數量為800～1 600時僅次于FCFS外,高于其他特征選擇算法,特別是當特征數量較少時,性能的增加較明顯.由圖4可見,應用ICFS算法時,支持向量機分類器的分類準確率遠高于其他特征選擇算法,性能增加的幅度最高達到了1.6%.由圖5可見,ICFS算法應用在WebKB語料集上時,Bayes分類器的分類準確率曲線整體上高于其他特征選擇算法,但性能增加的幅度不大,低于0.6%.由圖6可見,ICFS算法與支持向量機分類器配合應用在WebKB語料集上時,分類準確率遠高于其他特征選擇算法.

圖1 6個特征選擇算法應用在20-Newgroups 語料集時Bayes分類器的準確率曲線 Fig.1 Accuracy performance curves of Na?ve Bayes combined with 6 feature selection algorithm on 20-Newsgroups

圖2 6個特征選擇算法應用在20-Newgroups語料 集時支持向量機分類器的準確率曲線 Fig.2 Accuracy performance curves of SVM combined with 6 feature selection algorithm on 20-newsgroups

圖3 6個特征選擇算法應用在Reuters-21578語料 集時Bayes分類器的準確率曲線 Fig.3 Accuracy performance curves of Na?ve Bayes combined with 6 feature selection algorithm on Reuters-21578

圖4 6個特征選擇算法應用在Reuters-21578語料 集上時的支持向量機分類器的準確率曲線 Fig.4 Accuracy performance curves of SVM combined with 6 feature selection algorithm on Reuters-21578

圖5 6個特征選擇算法應用在WebKB語料 集上時Bayes分類器的準確率曲線Fig.5 Accuracy performance curves of Na?ve Bayes combined with 6 feature selection algorithm on WebKB

圖6 6個特征選擇算法應用在WebKB語料集 上時支持向量機分類器的準確率曲線 Fig.6 Accuracy performance curves of SVM combined with 6 feature selection algorithm on WebKB

由實驗結果可見,本文提出的新的特征選擇算法在20-Newgroups語料集上并未獲得最優效果.主要是因為20-Newgroups語料集是一個平衡的語料集,而Reuters-21578和WebKB語料集都存在不同程度的不平衡性問題,所以本文提出的特征選擇算法在不平衡的環境下能較好地發揮作用.

綜上所述,本文提出的特征選擇算法由兩方面綜合地度量了一個特征對分類的重要程度.實驗結果表明,該特征選擇算法能有效提高分類器的分類性能,特別在不平衡數據集上能產生較大幅度的性能提升.

[1] Sebastiani F.Machine Learning in Automated Text Categorization [J].ACM Computing Surveys,2002,34(1): 1-47.

[2] Deerwester S,Dumail S T,Furnas G W,et al.Indexing by Latent Semantic Analysis [J].Journal of the American Society of Information Science,1990,41(6): 391-407.

[3] TANG Lei,LIU Huan.Bias Analysis in Text Classification for Highly Skewed Data [C]//Proceedings of the 5th IEEE International Conference on Data Mining (ICDM-05).Washington: IEEE Computer Society,2005: 781-784.

[4] YANG Jie-ming,LIU Yuan-ning,LIU Zhen,et al.A New Feature Selection Algorithm Based on Binomial Hypothesis Testing for Spam Filtering [J].Knowledge-Based Systems,2011,24(6): 904-914.

[5] YANG Jie-ming,LIU Yuan-ning,ZHU Xiao-dong,et al.A New Feature Selection Based on Comprehensive Measurement Both in Inter-Category and Intra-Category for Text Categorization [J].Information Processing and Management,2012,48(4): 741-754.

[6] YANG Yi-ming,Pedersen J O.A Comparative Study on Feature Selection in Text Categorization [C]//Proceedings of the 14th International Conference on Machine Learning.San Francisco: Morgan Kaufmann Publishers Inc,1997: 412-420.

[7] Ogura H,Amano H,Kondo M.Feature Selection with a Measure of Deviations from Poisson in Text Categorization [J].Expert Systems with Applications: An International Journal,2009,36(3): 6826-6832.

[8] YAN Jun,LIU Ning,ZHANG Ben-yu,et al.OCFS: Optimal Orthogonal Centroid Feature Selection for Text Categorization [C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York: ACM Press,2005: 122-129.

[9] YANG Jie-ming,LIU Zhi-ying.A Feature Selection Based on Deviation from Feature Centroid for Text Categorization [C]//Proceedings of the Intelligent Control and Information Processing (ICICIP).Piscataway: IEEE Press,2011: 180-184.

[10] McCallum A,Nigam K.A Comparison of Event Models for Na?ve Bayes Text Classification [C]//AAAI-98 Workshop on Learning for Text Categorization.[S.l.]: AAAI Press,1998.

[11] Chang C C,Lin C J.LIBSVM: A Library for Support Vector Machines [EB/OL].2011-09-03.http://www.csie.ntu.edu.tw/～cjlin/libsvm.

[12] Forman G.An Extensive Empirical Study of Feature Selection Metrics for Text Classification [J].Journal of Machine Learning Research,2003,3: 1289-1305.

[13] WANG Gang,LIU Yuan-ning,ZHANG Xiao-xu,et al.Novel Spam Filtering Method Based on Fuzzy Adaptive Particle Swarm Optimization [J].Journal of Jilin University: Engineering and Technology Edition,2011,41(3): 716-720.(王剛,劉元寧,張曉旭,等.基于模糊自適應粒子群的垃圾郵件過濾新方法 [J].吉林大學學報: 工學版,2011,41(3): 716-720.)

[14] LIU Jie,JIN Di,DU Hui-jun,et al.New Hybrid Feature Selection Method RRK [J].Journal of Jilin University: Engineering and Technology Edition,2009,39(2): 419-423.(劉杰,金弟,杜惠君,等.一種新的混合特征選擇方法RRK [J].吉林大學學報: 工學版,2009,39(2): 419-423.)