梁伍七， 李 斌， 許 磊

（安徽廣播電視大學(xué)信息與工程學(xué)院，合肥 230022）

基于類別的CHI特征選擇方法

梁伍七， 李 斌， 許 磊

（安徽廣播電視大學(xué)信息與工程學(xué)院，合肥 230022）

文本分類問題中，卡方特征選擇是一種效果較好的特征選擇方法。計(jì)算單詞的卡方值時(shí)，先計(jì)算單詞針對(duì)每個(gè)類別的卡方值，再通過類別概率將卡方值調(diào)和平均，作為單詞相對(duì)于整個(gè)訓(xùn)練集合的卡方值，這種全局方法忽視了單詞和類別間的相關(guān)性。針對(duì)這一問題，提出基于類別的卡方特征選擇方法?；陬悇e的方法針對(duì)每個(gè)類別遴選特征詞，特征詞數(shù)量根據(jù)事先設(shè)定的閾值、類別的文檔數(shù)和整個(gè)訓(xùn)練集合文檔數(shù)計(jì)算得到，不同類別的特征空間可能包含相同的特征詞。采用KNN分類方法，將基于類別的方法與全局方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，基于類別的方法能夠提高分類器的總體性能。

文本分類；卡方；特征選擇；特征詞；KNN分類

一、引 言

互聯(lián)網(wǎng)的發(fā)展導(dǎo)致了網(wǎng)絡(luò)信息的爆炸式增長(zhǎng)，網(wǎng)絡(luò)信息大部分是文本格式的，如何有效組織和管理這些文本信息，對(duì)這些信息進(jìn)行高效地過濾、分類和檢索，從中找到用戶感興趣的信息，是信息過濾、信息檢索和搜索引擎等領(lǐng)域面臨的課題，自動(dòng)文本分類技術(shù)在這些領(lǐng)域有廣泛應(yīng)用。分類系統(tǒng)主要包括文本表示、分類器選擇和訓(xùn)練以及分類結(jié)果評(píng)價(jià)和反饋等過程。1975年Salton提出用向量空間模型（Vector Space Model，VSM）描述文本［1］。文本用特征向量描述時(shí)，向量維數(shù)過高會(huì)提高分類時(shí)間代價(jià)，降低分類精度，因此特征降維是分類系統(tǒng)預(yù)處理過程中的關(guān)鍵步驟。

傳統(tǒng)的特征選擇方法有:信息增益（Information Gain，IG）、期望交叉熵（Expected Cross Entropy，ECE）、互信息（Mutual Information，MI）、文本證據(jù)權(quán)（the Weight of Evidence of Text，WET）、文檔頻率（Document Frequency，DF）、卡方統(tǒng)計(jì)（Chi-Square，CHI）等。在特征選擇方面，美國卡內(nèi)基梅隆大學(xué)的Yang教授針對(duì)文本分類問題，對(duì)IG、DF、MI和CHI等特征選擇方法進(jìn)行了比較，得出IG和CHI方法分類效果相對(duì)較好的結(jié)論［2］。熊忠陽等人［3］分析了CHI統(tǒng)計(jì)方法的不足，將頻度、集中度和分散度指標(biāo)應(yīng)用到CHI統(tǒng)計(jì)方法上，對(duì)CHI統(tǒng)計(jì)進(jìn)行改進(jìn)；肖婷等人［4］通過引入文檔內(nèi)頻度和類內(nèi)正確度指標(biāo)對(duì)CHI統(tǒng)計(jì)進(jìn)行改進(jìn)；劉海峰等人［5］通過特征項(xiàng)的類內(nèi)分布、類間分布以及類內(nèi)不同文本之間分布等角度，對(duì)CHI模型進(jìn)行逐步優(yōu)化。CHI算法是有監(jiān)督的特征選擇算法，它和IG特征選擇算法在文本分類的性能表現(xiàn)上不相上下，有時(shí)候甚至比IG特征選擇算法更為出色，所以更多地應(yīng)用于文本分類［6］。但對(duì)于多類問題來說，上面的這些改進(jìn)措施先計(jì)算單詞針對(duì)每個(gè)類別的卡方值，再針對(duì)類別求最大值，作為單詞相對(duì)于整個(gè)訓(xùn)練集合的卡方值，這種全局方法忽視了單詞和類別間的相關(guān)性［3-5］。

針對(duì)這一問題，提出基于類別的卡方特征選擇方法。基于類別的方法針對(duì)每個(gè)類別遴選特征詞，特征詞數(shù)量根據(jù)事先設(shè)定的閾值、類別的文檔數(shù)和整個(gè)訓(xùn)練集合文檔數(shù)計(jì)算得到，不同類別的特征空間可能包含相同的特征詞。采用KNN分類方法，將基于類別的方法與全局方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，基于類別的方法能夠提高分類器的總體性能。

二、CHI特征選擇算法

設(shè)有單詞w與類別c，假設(shè)w和c之間符合具有一階自由度的卡方分布，則可用卡方統(tǒng)計(jì)量度量單詞w與類別c之間的相關(guān)程度［7］。CHI算法衡量的是單詞w與類c之間的相關(guān)程度，單詞對(duì)于某類的χ2統(tǒng)計(jì)值越高，它與該類之間的相關(guān)性越大。單詞w針對(duì)類c的CHI算法公式如下:

其中，N11為訓(xùn)練集合中包含單詞w的c類文本數(shù)，N10為訓(xùn)練集合中包含單詞w的非c類文本數(shù)，N01為訓(xùn)練集合中不包含單詞w的c類文本數(shù)，N00為訓(xùn)練集合中不包含單詞w的非c類文本數(shù)，|D|為訓(xùn)練集合中總文本數(shù)，具體含義用表1表示。

表1　公式（1）中的記號(hào)含義

單詞w相對(duì)于整個(gè)訓(xùn)練集合的CHI值計(jì)算方式通常有如下兩種，|C|為類別數(shù)，我們采用以下公式計(jì)算:

CHI算法基于Pearsonχ2檢驗(yàn)用于變量的獨(dú)立性檢驗(yàn)，即檢驗(yàn)兩個(gè)隨機(jī)變量（X，Y）是否互相獨(dú)立。設(shè)隨機(jī)變量X取值為xi（i=1，2，…，r），Y取值為yj（j=1，2，…，c），觀察值記為Oi，j，在變量獨(dú)立的假設(shè)下，觀察值的期望次數(shù)為:

其中N是樣本大小，則用于校驗(yàn)的χ2統(tǒng)計(jì)值公式如下:

對(duì)于特征選擇問題來說，兩個(gè)事件分別是指單詞w在文檔中是否出現(xiàn)和這個(gè)文檔是否屬于類c，X是一個(gè)二值隨機(jī)變量，當(dāng)文檔包含單詞w時(shí)，它取值為1，否則取值為0；而Y也是個(gè)二值隨機(jī)變量，當(dāng)文檔屬于類別c時(shí)，它取值為1，否則取值為0，此時(shí)公式（5）可化簡(jiǎn)為公式（1）。公式（2）計(jì)算單詞的卡方值時(shí)，先計(jì)算單詞針對(duì)每個(gè)類別的卡方值，再通過類別概率將卡方值調(diào)和平均，作為單詞相對(duì)于整個(gè)訓(xùn)練集合的卡方值，這種全局方法（以下稱為Global CHI）忽視了單詞和類別間的相關(guān)性。

三、基于類別的CHI特征選擇算法

針對(duì)全局方法忽視了單詞和類別間的相關(guān)性這一不足，提出基于類別的卡方特征選擇方法（以下稱為L(zhǎng)ocal CHI）?；陬悇e的方法針對(duì)每個(gè)類別遴選特征詞，特征詞數(shù)量根據(jù)事先設(shè)定的閾值、類別的文檔數(shù)和整個(gè)訓(xùn)練集合文檔數(shù)計(jì)算得到，不同類別的特征空間可能包含相同的特征詞。

Global CHI特征選擇算法具體描述如下:

算法1Global CHI特征選擇算法

輸入 類別集合C，詞典集合W，鄰接表T，特征選擇維度N，訓(xùn)練語料庫文檔D

輸出 特征詞集合K

（1）計(jì)算訓(xùn)練語料庫文檔總數(shù)|D|；

（2）計(jì)算類別ci的文檔在語料中出現(xiàn)的概率P（ci）（ci∈C）；

（3）計(jì)算單詞w相對(duì)于整個(gè)訓(xùn)練集合的

CHI值；

針對(duì)詞典集合W中每個(gè)單詞w（w∈W）；

針對(duì)類別集合C中的每個(gè)類別ci（ci∈C）；

利用鄰接表T信息計(jì)算N11，N10，N01，N00；

利用公示（1）計(jì)算χ2（w，ci）；

利用公示（2）計(jì)算χ2（w）；

將單詞w及其CHI值保存到向量集合中；

（4）按照單詞w的CHI值降序排序向量集合；

（5）根據(jù)特征選擇維度取前N個(gè)單詞w加入到特征詞集合K中。

Local CHI特征選擇算法具體描述如下:

算法2 Local CHI特征選擇算法

輸入 類別集合C，詞典集合W，鄰接表T，閾值N，訓(xùn)練語料庫文檔D

輸出 特征詞集合K

（1）計(jì)算訓(xùn)練語料庫文檔總數(shù)|D|；

（2）為類別ci生成特征詞集合Ki；

針對(duì)類別集合C中的每個(gè)類別ci（ci∈C）；

計(jì)算類別ci中的文檔數(shù)目|Di|；

計(jì)算類別ci中遴選的特征詞數(shù)目Ni←|Di|× N/|D|；

針對(duì)詞典集合W中每個(gè)單詞w（w∈W）；

利用鄰接表T信息計(jì)算N11，N10，N01，N00；

利用公示（1）計(jì)算χ2（w，ci）；

將單詞w及其CHI值保存到向量集合中；

按照單詞w的CHI值降序排序向量集合；

根據(jù)特征選擇維度取前Ni個(gè)單詞w加入到特征詞集合Ki中。

（5）特征詞集合K←UKi。

由算法2可以看出，基于類別的方法針對(duì)每個(gè)類別遴選特征詞，特征詞數(shù)量根據(jù)事先設(shè)定的閾值、類別的文檔數(shù)和整個(gè)訓(xùn)練集合文檔數(shù)計(jì)算得到，不同類別的特征空間可能包含相同的特征詞，導(dǎo)致最終生成的特征詞集合的大小可能小于最初設(shè)定的閾值。

四、實(shí)驗(yàn)過程和結(jié)果分析

（一）評(píng)價(jià)指標(biāo)

為評(píng)價(jià)分類系統(tǒng)的性能，采用通用的性能評(píng)估指標(biāo)，包括查準(zhǔn)率（Precision，簡(jiǎn)記為P）、查全率（Recall，簡(jiǎn)記為R）和F1測(cè)試值［8］。

如果將屬于該類別的文章定義為“正例”，不屬于該類別的文章定義為“負(fù)例”，定義分類器混合矩陣如表2所示:

表2　分類器混合矩陣

查準(zhǔn)率P=TP/（TP+FP），查準(zhǔn)率又叫準(zhǔn)確率；查全率R=TP/（TP+FN），查全率又叫召回率；F1=2PR/（P+R），它是查準(zhǔn)率和查全率的調(diào)和平均值。

（二）實(shí)驗(yàn)過程

文本分類一般由預(yù)處理、特征選擇、向量空間模型建立和分類算法等部分組成。

預(yù)處理模塊主要包括中文分詞和停用詞過濾等，中文分詞使用中國科學(xué)院的漢語詞法分析系統(tǒng)ICTCLAS對(duì)文本進(jìn)行分詞處理。預(yù)處理結(jié)束后，得到詞典文件。特征選擇模塊使用文中介紹的CHI特征選擇算法對(duì)詞典文件中的每個(gè)詞計(jì)算對(duì)分類的貢獻(xiàn)分值，從而對(duì)高維特征空間進(jìn)行降維，構(gòu)成用于分類所使用的特征空間。

向量空間模型建立部分將訓(xùn)練語料庫中的文檔抽象成以特征項(xiàng)的權(quán)重為分量的特征向量，特征項(xiàng)的權(quán)重計(jì)算采用目前最流行的TF-IDF算法。TF-IDF算法基本思想是:特征項(xiàng)的重要性正比于特征項(xiàng)的詞頻，反比于訓(xùn)練文檔內(nèi)出現(xiàn)此特征項(xiàng)的文檔頻率。訓(xùn)練文檔根據(jù)TF-IDF算法抽象成以特征項(xiàng)的權(quán)重為分量的特征向量后，將其歸一化處理。然后對(duì)需要分類的文檔建立向量空間模型。

分類算法模塊采用K最近鄰算法（K-Nearest Neighbor algorithm）［9］。對(duì)于某個(gè)待分類文檔，KNN分類算法在訓(xùn)練語料庫中找離它最近的K個(gè)樣本點(diǎn)，并計(jì)算這K個(gè)樣本點(diǎn)所屬類別?？催@K個(gè)樣本點(diǎn)中，那個(gè)類別出現(xiàn)的次數(shù)多，則將該類別標(biāo)簽賦予待分類文檔。分類結(jié)束后，就可以對(duì)分類結(jié)果進(jìn)行評(píng)估。

（三）實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用的語料庫源于搜狗新聞分類語料庫［10］。通過整理，訓(xùn)練語料庫中文檔總數(shù)為3 6041篇，測(cè)試集合中待分類文檔總數(shù)6 000篇，一共分為9個(gè)類別，包括商業(yè)、新聞、房產(chǎn)、奧運(yùn)、女性、體育、娛樂、教育和旅游。訓(xùn)練語料庫新聞?lì)悇e的文檔總數(shù)最多，為7 819篇，旅游類別的文檔總數(shù)最少，為829篇。

預(yù)處理模塊經(jīng)過分詞和停用詞過濾后得到的單詞總數(shù)為122 347個(gè)，特征選擇分別選用Global CHI和Local CHI特征選擇算法進(jìn)行。特征選擇維度和閾值分別取50、100、200、400、600和800，分別計(jì)算準(zhǔn)確率、召回率和F1值。KNN分類算法中K取100，僅僅保留相似度最大的100篇訓(xùn)練樣本，分類后得到的具體結(jié)果如表3至表5以及圖l至圖3所示。

表3　2種算法分類準(zhǔn)確率結(jié)果對(duì)比（百分比）

表4　2種算法分類召回率結(jié)果對(duì)比（百分比）

表5　2種算法分類F1值結(jié)果對(duì)比（百分比）

從表4至表6以及圖l至圖5可以看出:

（1）對(duì)于分類準(zhǔn)確率來說，Local方法比Global方法要高，維度或閾值越低，二者的差距越大，維度或閾值為400時(shí)，二者的準(zhǔn)確率接近。但隨著維度或閾值的增加，Local方法的準(zhǔn)確率逐漸變好，而Global方法的準(zhǔn)確率有下降的趨勢(shì)。

（2）對(duì)于分類召回率來說，Local方法比Global方法要高，維度或閾值越低，二者的差距越大。但隨著維度或閾值的增加，二者的召回率有逐漸接近的趨勢(shì)。

（3）對(duì)于分類F1值來說，Local方法比Global方法要好，維度或閾值越低，二者的差距越大。維度或閾值超過200時(shí)，二者的差距基本穩(wěn)定在10個(gè)百分點(diǎn)左右。

總之，無論特征選擇維度或閾值如何變化，Local方法分類結(jié)果保持穩(wěn)定，準(zhǔn)確率、召回率和F1測(cè)試值都比Global方法要高。且隨著維度或閾值的增加，Local方法的準(zhǔn)確率有進(jìn)一步變好的趨勢(shì)。

五、結(jié)束語

全局卡方特征選擇忽視單詞和類別間的相關(guān)性，針對(duì)這一問題，提出基于類別的卡方特征選擇方法?；陬悇e的方法針對(duì)每個(gè)類別遴選特征詞，特征詞數(shù)量根據(jù)事先設(shè)定的閾值、類別的文檔數(shù)和整個(gè)訓(xùn)練集合文檔數(shù)計(jì)算得到，不同類別的特征空間可能包含相同的特征詞。采用KNN分類方法，將基于類別的方法與全局方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，基于類別的方法能夠提高分類器的總體性能。

［1］ SALTON G，WONG A，YANG C S.A Vector Space Model for Automatic Indexing［J］.Communications of the ACM，1975，18（11）:613-620.

［2］ YANG Y M，PEDERSEN J O.A Comparative Study on Feature Selection in Text Categorization［C］//Proceeding of the Fourteenth International Conference on Machine Learning（ICML97）.San Francisco，USA:Morgan Kaufmann Publishers，1997:412-420.

［3］ 熊忘陽，張鵬招，張玉芳.基于χ2統(tǒng)計(jì)的文本分類特征選擇方法的研究［J］.計(jì)算機(jī)應(yīng)用，2008，28（2）:513-518.

［4］ 肖婷，唐雁.改進(jìn)的χ2統(tǒng)計(jì)文本特征選擇方法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（14）:136-137.

［5］ 劉海峰，蘇展，劉守生.一種基于詞頻信息的改進(jìn)CHI文本特征選擇［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（22）:110-114.

［6］ 尚文倩.文本分類及其相關(guān)技術(shù)研究［D］.北京:北京交通大學(xué)，2007.

［7］ SCHUTZE H，HULL D A，PEDERSEN J O.A Comparison of Classifiers and Document Representations for the Routing Problem［C］//Proceedings of 18th ACM International Conference on Research and Development in Information Retrieval. New York，USA:ACM Press，1995:229-237.

［8］ LIU TAO，LIU S，CHEN Z.An Evaluation on Feature Selection for Text Clustering［C］//Proceedings of the 20th International Conference on Machine Learning.Washington D.C.，USA:［s.n.］，2003:488-495.

［9］ COVER T M，HART P E.Nearest Neighbor Pattern Classification［J］.IEEE Transactions on Information Theory，1967，13（1）:21-27.

［10］ 中文分類語料庫［EB/OL］.（2012-03-21）［2015-01-30］.http://www.sogou.com/labs/dl/tce.html.

CHI Feature Selection Method Based on Category

LIANG Wu-qi， LI Bin， XU Lei
（College of Information Science and Engineering，Anhui Radio and TV University，Hefei 230022，China）

In text categorization，chi-square feature selection is a better feature selection method.While the chi-square value of a word being calculated，the chi-square value for each category is calculated first，and then the harmonic mean is calculated by the category probability and the chi-square value，which serves as the chisquare value of the word for the entire training set.This global approach ignores the correlation between words and categories.Aiming at this problem，a chi-square feature selection method based on category is proposed，which chooses feature words for each category.The number of feature words is calculated by pre-set threshold，the number of documents in the category and the number of documents in the entire training set. The feature space of different categories may contain the same feature words.Using K Nearest Neighbor（KNN）method，it is compared with the global feature selection approach.Experimental results show the chisquare feature selection method based on category can improve the overall performance of the classifier.

text categorization；Chi-square；feature selection；feature word；KNN categorization

TP391

A

1008-6021（2015）03-0124-05

［責(zé)任編輯 李潛生］

2015-01-30

梁伍七（1969-），男，安徽懷寧人，碩士，副教授。研究方向:網(wǎng)絡(luò)信息安全和數(shù)據(jù)挖掘。