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

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

(2)

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

本文采用均值TF-IDF來表征每個特征項，如下所示：

(3)

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

(4)

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

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

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

(5)

(6)

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

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

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

(7)

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

為了解決個別噪聲文檔對分類準(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實驗與分析

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

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

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

3.1實驗數(shù)據(jù)集

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

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

3.2分類性能評估

本文選取常用的準(zhǔn)確率、召回率和F1值作為實驗評價指標(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)和平均值，具體計算公式為：

(12)

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

(13)

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

3.3實驗結(jié)果

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

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)：

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

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

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

[4]王光,邱云飛,史慶偉.集合CHI與IG的特征選擇方法[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é)報(自然科學(xué)版),2015,37(6):137-142.

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

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

[9]李明江.結(jié)合類詞頻的文本特征選擇方法的研究[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].計算機工程與設(shè)計,2014,35(6):1999-2003.

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

中圖分類號：TP391.1

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

收稿日期：2015-09-02

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

基金項目：國家自然科學(xué)基金項目(61163026，60865001)

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

DOI:10.15926/j.cnki.issn1672-6871.2016.03.010