何　燕，哈力旦·阿布都熱依木，阿麗亞·艾爾肯，吳冰冰

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830047)

?

一種新的維吾爾文文本分類特征選擇方法

何燕，哈力旦·阿布都熱依木，阿麗亞·艾爾肯，吳冰冰

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830047)

摘要：針對(duì)傳統(tǒng)卡方統(tǒng)計(jì)量方法對(duì)特征項(xiàng)的頻數(shù)和類別分布考慮不足的缺陷，提出了一種結(jié)合余弦相似度的卡方統(tǒng)計(jì)量特征選擇方法。該方法首先使用均值詞頻-逆文檔頻率表示特征項(xiàng)，通過引入一個(gè)調(diào)整公式來平衡類間選取的特征項(xiàng)數(shù)，從而對(duì)傳統(tǒng)卡方統(tǒng)計(jì)量方法進(jìn)行修正，然后結(jié)合余弦相似度進(jìn)一步消除噪聲文本。在收集的維吾爾文數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)論證。實(shí)驗(yàn)結(jié)果表明：改進(jìn)的卡方統(tǒng)計(jì)量方法具有較好的魯棒性，且分類性能優(yōu)于傳統(tǒng)的卡方統(tǒng)計(jì)量方法。

關(guān)鍵詞：維吾爾文；卡方統(tǒng)計(jì)量；余弦相似度；特征選擇

0引言

文本分類是從一系列數(shù)字文檔中找到相關(guān)和及時(shí)信息的關(guān)鍵技術(shù)。隨著新疆地區(qū)信息化建設(shè)的飛速發(fā)展，網(wǎng)絡(luò)上包括維吾爾文等少數(shù)民族語種的大量數(shù)字化信息呈現(xiàn)指數(shù)級(jí)增長(zhǎng)趨勢(shì)。如何有效管理和利用這些紛繁雜蕪的海量信息，并對(duì)大量少數(shù)民族語種文本數(shù)據(jù)進(jìn)行自動(dòng)歸類，是當(dāng)前重要的研究課題之一[1]。

特征選擇是將能夠有效表達(dá)文本內(nèi)容的特征挑選出來建立學(xué)習(xí)樣本，保留重要的信息，去除冗余信息，以降低特征空間維度的過程。一個(gè)好的學(xué)習(xí)樣本是訓(xùn)練分類器的關(guān)鍵，樣本中是否含有不相關(guān)或冗余信息直接影響著分類器的分類精度和泛化性能[2]。因此，尋求一種好的特征選擇方法是提高文本分類性能的有效途徑。

卡方統(tǒng)計(jì)量(chi-square statistic,CHI)方法以其時(shí)間復(fù)雜度低、便于理解和應(yīng)用方便等優(yōu)點(diǎn)已經(jīng)成為文本分類中常用的特征選擇模型。目前，針對(duì)CHI模型進(jìn)行的改進(jìn)研究受到了越來越多的關(guān)注[3-4]。文獻(xiàn)[5]通過引入最大詞頻和采樣方差對(duì)傳統(tǒng)CHI方法進(jìn)行修正，針對(duì)特征數(shù)目的不同，提出了兩種基于詞頻和特征項(xiàng)分布的CHI特征選擇方法。文獻(xiàn)[6]通過設(shè)置最低詞頻閾值去除部分低頻詞對(duì)CHI的干擾，并將改進(jìn)后的CHI特征選擇公式引入特征權(quán)重計(jì)算中，不僅使文本表示更合理，而且有效提高了文本分類的準(zhǔn)確率。文獻(xiàn)[7]在不平衡的維吾爾文數(shù)據(jù)集上，提出了一種結(jié)合逆文檔頻率的改進(jìn)卡方統(tǒng)計(jì)量方法。這些改進(jìn)方法在中英文的文本分類中取得了很好的效果，但維吾爾文的語種特點(diǎn)[8]與中英文不同，采用該類方法不能達(dá)到很好的分類效果。因此，針對(duì)CHI的優(yōu)缺點(diǎn)和維吾爾文語種特點(diǎn)進(jìn)行深入研究，建立針對(duì)維吾爾文文本分類的新模型具有重要意義。本文通過分析傳統(tǒng)CHI的優(yōu)缺點(diǎn)，提出了一種新的結(jié)合余弦相似度的CHI特征選擇方法，不僅克服了傳統(tǒng)算法對(duì)低頻詞的偏袒以及特征項(xiàng)的類別分布不均勻問題，而且提高了分類性能。

1卡方統(tǒng)計(jì)量方法

卡方統(tǒng)計(jì)量(CHI)方法就是通過觀察實(shí)際值與理論值的偏差來確定理論的正確與否。假設(shè)詞條tk與類ci之間的獨(dú)立關(guān)系服從具有一個(gè)自由度的χ2分布[9]。

假定T={tk|k=1,2,…,m}為訓(xùn)練樣本集的特征集；ci為第i類訓(xùn)練樣本，i=1,2,…,n。tk對(duì)于類ci的卡方統(tǒng)計(jì)量可表示為：

(1)

當(dāng)特征項(xiàng)tk與類ci越相關(guān)時(shí)，其對(duì)應(yīng)的CHI(tk,ci)值越大，代表特征項(xiàng)tk對(duì)分類的貢獻(xiàn)越大；反之，特征項(xiàng)tk與類ci相互獨(dú)立時(shí)，其對(duì)應(yīng)的CHI(tk,ci)=0，代表特征項(xiàng)tk不包含任何有關(guān)類ci的信息。

對(duì)于多個(gè)類別的問題，應(yīng)分別計(jì)算特征項(xiàng)tk對(duì)于每個(gè)類別的CHI(tk,ci)，再對(duì)計(jì)算結(jié)果進(jìn)行綜合。綜合的方式一般有兩種：一種是加權(quán)平均，另一種是取最大值。本文選擇取最大值的方式進(jìn)行綜合。

由式(1)可知CHI方法是基于文檔頻率(document frequency,DF)的特征選擇方法，只考慮特征項(xiàng)在文檔中是否出現(xiàn)，會(huì)更加偏向于將DF值高的詞作為特征。

同時(shí)，在對(duì)多個(gè)類別進(jìn)行分類時(shí)，若設(shè)定的閾值不合適，CHI容易選擇對(duì)某特定類別區(qū)分度低而對(duì)其他類別具有強(qiáng)區(qū)分度的特征項(xiàng)，會(huì)導(dǎo)致某些類別選擇的特征項(xiàng)過多或過少。

2改進(jìn)的CHI特征選擇方法

2.1特征項(xiàng)頻數(shù)的改進(jìn)

為解決傳統(tǒng)卡方統(tǒng)計(jì)量容易忽略文檔頻數(shù)低而詞頻高的缺陷，在傳統(tǒng)的CHI特征選擇的基礎(chǔ)上，引入均值詞頻-逆文檔頻率(term frequency-inverse document frequency,TF-IDF)特征權(quán)重計(jì)算來進(jìn)行調(diào)節(jié)。

TF×IDF(k,j)=tfkj×idfj=tfkj×log(N/nj) ，

(2)

其中：tfkj為特征項(xiàng)tk在文檔dj中出現(xiàn)的次數(shù)；idfj為包含特征項(xiàng)tk的逆文檔頻率；N為總文檔數(shù)；nj為出現(xiàn)特征項(xiàng)tk的文檔數(shù)。

本文采用均值TF-IDF來表征每個(gè)特征項(xiàng)，如下所示：

(3)

其中：Count(j)為數(shù)據(jù)集中文檔的總數(shù)目。此時(shí)，可將式(1)改進(jìn)為式(4)：

(4)

2.2特征項(xiàng)類別分布的改進(jìn)

一般而言，具有較強(qiáng)類別表現(xiàn)能力的特征項(xiàng)在該類別內(nèi)的頻數(shù)不僅應(yīng)該較大，而且這些特征項(xiàng)的數(shù)目在其相應(yīng)的類內(nèi)應(yīng)保持均衡，這樣不會(huì)使得某一個(gè)類別中最終保留的特征項(xiàng)過多或者過少。

引入以下公式，使得各個(gè)類中選取的特征項(xiàng)數(shù)均等，以保留更多的具有強(qiáng)區(qū)分度的特征項(xiàng)。

(5)

(6)

其中：CHIL(tk)為最終保留的特征項(xiàng)；CHI↓(tk)為文檔集中降序排列的卡方值；N(ci)為ci類中包含保留的特征項(xiàng)tk的個(gè)數(shù)；FC為每個(gè)類中預(yù)選擇的特征個(gè)數(shù)；R為整個(gè)語料庫中縮減的特征項(xiàng)數(shù)目；C為類別的數(shù)目。

文獻(xiàn)[10]提出使用CHI方法去權(quán)衡相似度，以及使用CHI測(cè)試來確定文本分類中兩個(gè)隨機(jī)樣本中詞向量的同質(zhì)性，發(fā)現(xiàn)CHI和余弦相似性相結(jié)合可以提供更加可靠和有效的分類機(jī)制。文獻(xiàn)[11]在改進(jìn)的CHI的基礎(chǔ)上采用余弦相似度計(jì)算阿拉伯文本間相似度，分類準(zhǔn)確率明顯提高。

因此，為了進(jìn)一步消除文本噪聲，引入余弦(Cosine)相似定理來計(jì)算文本間的相似度。計(jì)算公式如下：

(7)

其中：Di=(wi1,wi2,…，wiN)；Dk=(wk1,wk2,…，wkN)；wij，wkj分別為文本Di，Dk中的第j個(gè)特征詞的TF-IDF權(quán)值;N為特征向量的維數(shù)。每篇文檔作為一個(gè)向量，向量中的每一維就是文本中每個(gè)特征詞的權(quán)重。計(jì)算兩篇文檔的相似度，當(dāng)向量夾角的余弦值越接近于1，表明兩篇文檔越相似；反之，兩篇文檔越不相關(guān)。

為了解決個(gè)別噪聲文檔對(duì)分類準(zhǔn)確率的影響，引入以下公式：

(8)

(9)

(10)

其中：S1為類內(nèi)文檔余弦相似度的平均值，這里忽略文檔Di的自身余弦相似度值；Ncj為類Cj中包含的文檔數(shù)；S2為文檔Di與其他類中文檔余弦相似度平均值。假設(shè)S1低于閾值α并且S2高于閾值β，那么文檔Di不能有效表達(dá)所屬類的信息，卻與其他類相關(guān)，即認(rèn)為該文檔不適合用來表征所屬類別的信息，應(yīng)刪除以減小帶給分類器的噪聲。

3實(shí)驗(yàn)與分析

圖1　改進(jìn)的CHI方法的具體實(shí)現(xiàn)流程圖

實(shí)驗(yàn)是在Intel(R) Core(TM) i5-4200U處理器、4 GB內(nèi)存，操作系統(tǒng)為Windows 7的PC機(jī)上進(jìn)行的，使用eclipse作為開發(fā)環(huán)境。

為了考察CHI的改進(jìn)效果，在相同的實(shí)驗(yàn)條件下，將改進(jìn)的CHI(CHI+Cosine)方法與傳統(tǒng)卡方統(tǒng)計(jì)量(CHI)方法進(jìn)行實(shí)驗(yàn)對(duì)比。改進(jìn)的CHI方法的具體實(shí)現(xiàn)流程如圖1所示。

3.1實(shí)驗(yàn)數(shù)據(jù)集

目前,針對(duì)中英文的文本分類研究，國(guó)內(nèi)外已經(jīng)有相對(duì)標(biāo)準(zhǔn)的、開放的文本分類語料庫作為參考，可以在相同的數(shù)據(jù)集上比較不同的特征選擇和分類方法的性能。由于維吾爾語文本分類的研究仍然處于起步階段，因而目前并沒有標(biāo)準(zhǔn)的、開放的維吾爾語文本集作為統(tǒng)一的參考。實(shí)驗(yàn)中所使用的維吾爾文文本數(shù)據(jù)為本實(shí)驗(yàn)室采集，數(shù)據(jù)來源于新疆政府網(wǎng)、天山網(wǎng)和Ulinix等主要維吾爾語門戶網(wǎng)站[12]。實(shí)驗(yàn)數(shù)據(jù)描述見表1。

表1　維吾爾文文本數(shù)據(jù)集信息描述

3.2分類性能評(píng)估

本文選取常用的準(zhǔn)確率、召回率和F1值作為實(shí)驗(yàn)評(píng)價(jià)指標(biāo)[13]。這里假設(shè)a為屬于類Ci而被分至類Ci的文檔數(shù)；b為屬于類Ci而被分至非類Ci的文檔數(shù)；c為不屬于類Ci而被分至類Ci的文檔數(shù)；d為不屬于類Ci而被分至非類Ci的文檔數(shù)。那么，準(zhǔn)確率p和召回率r定義為：

(11)

F1值為關(guān)于r和p的函數(shù)，是兩者的調(diào)和平均值，具體計(jì)算公式為：

(12)

宏平均F1值 (Macro-F1)是每個(gè)類別性能指標(biāo)F1值的算術(shù)平均值，計(jì)算公式為：

(13)

本文采用宏平均F1值來綜合衡量分類效果。

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

維吾爾文與中文不同，卻相似于英文。對(duì)于維吾爾文來說，不存在分詞的問題，因?yàn)樵~語之間已經(jīng)自然地用空格隔開。通過去除非維吾爾語文本以及停用詞等預(yù)處理之后，建立了由77 591個(gè)特征項(xiàng)組成的候選特征項(xiàng)集合。分別采用兩種算法(CHI方法和CHI+Cosine方法)對(duì)預(yù)處理后的數(shù)據(jù)集進(jìn)行特征選擇，最后采用開放數(shù)據(jù)挖掘WEKA平臺(tái)的LibSVM分類算法進(jìn)行分類。其中，α取值為0.2，β取值為0.7。為測(cè)試算法的準(zhǔn)確性，這里采用十折交叉驗(yàn)證方法。

特征維數(shù)為3 000的情況下，CHI方法以及CHI+Cosine方法在每個(gè)類別中的分類準(zhǔn)確率，如表2所示。

表2　兩種方法的分類準(zhǔn)確率對(duì)比　%

在表2的4類實(shí)例數(shù)據(jù)中，CHI+Cosine方法與CHI方法相比，除了社會(huì)時(shí)事類別，其他類別維吾爾文文本分類的準(zhǔn)確率均有不同程度的提高，尤其是體育類和生活與健康類提高效果顯著。由表2數(shù)據(jù)可知：CHI方法在特征項(xiàng)數(shù)目保留過低時(shí)，如體育類和生活與健康類的特征包含較少，因而導(dǎo)致其分類準(zhǔn)確率過低，而CHI+Cosine方法剛好克服了這一缺點(diǎn)。

圖2是支持向量機(jī)(support vector machine,SVM)分類器采用CHI和CHI+Cosine兩種特征選擇方法，在實(shí)驗(yàn)數(shù)據(jù)集上的Macro-F1曲線。從圖2a中可以看出：在特征數(shù)低于4 000時(shí)，CHI+Cosine方法的分類性能已經(jīng)遠(yuǎn)遠(yuǎn)高于CHI方法。這是因?yàn)楦倪M(jìn)的CHI+Cosine方法在選取的特征數(shù)目較低時(shí)，明顯克服了傳統(tǒng)CHI方法選擇的特征項(xiàng)在某些類別中過多，而在其他類別的特征項(xiàng)數(shù)目過少的不足。從圖2b中可以看出：CHI+Cosine方法在特征數(shù)為45 000時(shí)，使分類器的性能達(dá)到最優(yōu)并趨于穩(wěn)定；CHI方法在選取35 000個(gè)特征時(shí)，分類器的Macro-F1值達(dá)到最高(0.930)。而且隨著特征數(shù)目的變化，CHI+Cosine方法使得分類器的性能始終優(yōu)于CHI方法。

圖2　采用兩種不同特征選擇方法的SVM分類器性能比較

4結(jié)束語

本文提出了一種結(jié)合余弦相似度的卡方統(tǒng)計(jì)量方法，分別從特征項(xiàng)出現(xiàn)的頻數(shù)以及類別分布對(duì)CHI算法進(jìn)行修正。通過引入一個(gè)調(diào)整公式來平衡類間選擇的特征數(shù)目，避免某一個(gè)類別中最終保留的特征項(xiàng)過多或者過少，解決了傳統(tǒng)CHI方法對(duì)低頻詞的偏倚以及特征項(xiàng)的類別分布的問題。在開放數(shù)據(jù)挖掘平臺(tái)WEKA中，使用LibSVM對(duì)收集的維吾爾文數(shù)據(jù)集進(jìn)行分類，改進(jìn)的CHI+Cosine方法使得分類器性能優(yōu)于傳統(tǒng)的CHI方法，具有很好的魯棒性，有效地克服了傳統(tǒng)CHI方法在選擇較少特征數(shù)目時(shí)分類性能過低的問題。

參考文獻(xiàn)：

[1]艾海麥提江·阿布來提,吐爾地·托合提,艾斯卡爾·艾木都拉.基于Naive Bayes的維吾爾文文本分類算法及其性能分析[J].計(jì)算機(jī)應(yīng)用與軟件,2012,29(12):27-29.

[2]姚旭,王曉丹,張玉璽,等.特征選擇方法綜述[J].控制與決策,2012,27(2):161-166,192.

[3]邱云飛,王威,劉大有,等.基于方差的CHI特征選擇方法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1304-1306.

[4]王光,邱云飛,史慶偉.集合CHI與IG的特征選擇方法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(7):2454-2456.

[5]JIN C,MA T,HOU R,et al.Chi-square statistics feature selection based on term frequency and distribution for text categorization[J].IETE journal of research,2015,61(4):1-12.

[6]肖雪,盧建云,余磊,等.基于最低詞頻CHI的特征選擇算法研究[J].西南大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,37(6):137-142.

[7]董瑞,周喜.面向維吾爾文不平衡數(shù)據(jù)分類的特征選擇方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(1):349-352.

[8]李敏強(qiáng),哈力旦·阿布都熱依木,閆軻.一種改進(jìn)型局部二值模式的維吾爾文定位算法[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,36(3):43-47.

[9]李明江.結(jié)合類詞頻的文本特征選擇方法的研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(7):2024-2026.

[10]CHEN Y T,CHEN M C.Using chi-square statistics to measure similarities for text categorization[J].Expert systems with applications,2011,38(4):3085-3090.

[11]HAEASHIN B,MANSOUR A M,ALJAWARNEH S.An efficient feature selection method for Arabic text classification[J].International journal of computer applications,2013,83(17):1-6.

[12]陳洋,哈力旦·阿布都熱依木,伊力亞爾·達(dá)吾提,等.基于加權(quán)改進(jìn)貝葉斯算法的維吾爾文文本分類[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(6):1999-2003.

[13]伍洋,鐘鳴,姜艷,等.面向?qū)徲?jì)領(lǐng)域的短文本分類技術(shù)研究[J].微電子學(xué)與計(jì)算機(jī),2015,32(1):5-10.

中圖分類號(hào)：TP391.1

文獻(xiàn)標(biāo)志碼：A

收稿日期：2015-09-02

作者簡(jiǎn)介：何燕(1991-)，女，新疆塔城人，碩士生；哈力旦·阿布都熱依木(1959-)，女，維吾爾族，新疆烏魯木齊人，教授，碩士生導(dǎo)師，主要從事圖像處理、數(shù)據(jù)挖掘等方面的研究.

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61163026，60865001)

文章編號(hào)：1672-6871(2016)03-0042-05

DOI:10.15926/j.cnki.issn1672-6871.2016.03.010