面向維吾爾文不平衡數(shù)據(jù)分類的特征選擇方法

董 瑞，周 喜

（1.中國科學(xué)院研究生院，北京100080；2.中科院新疆理化技術(shù)研究所，新疆 烏魯木齊830011）

0 引 言

由少數(shù)民族語言信息技術(shù)在不斷發(fā)展，維吾爾文網(wǎng)頁數(shù)目也隨之飛速增長，相應(yīng)的電子文本數(shù)目也越來越多，維吾爾文自動文本分類也越發(fā)受到重視。在文本分類中，特征空間維數(shù)過高是影響最終分類結(jié)果的重要因素。漢語大辭典中中文詞條超過37萬，維吾爾文詞典詞條超過100萬，若以詞為特征，將是一個非常高的特征空間。有效的特征選擇算法可以很大程度上降低特征空間維數(shù)?，F(xiàn)有的特征選擇函數(shù)主要有文檔頻數(shù)（document frequency，DF），卡方檢驗(yàn)（chi－square，CHI），互 信 息（mutual information，MI）等。目前，維吾爾文文本分類的研究尚少，且主要的維吾爾文自動文本分類研究都是基于平衡數(shù)據(jù)的，如文獻(xiàn)［1－2］所述搭建了維吾爾文文本分類平臺，卻未考慮到維吾爾文不平衡數(shù)據(jù)問題。不平衡數(shù)據(jù)問題是指在某個分類問題中，有一些類的文本數(shù)目比另外一些多［3］，通常的分類算法中都會忽略了正類（文本數(shù)目較少的類），而偏向負(fù)類（文本數(shù)目多的類）。正類和負(fù)類的不平衡比可能從1∶1到1∶100，甚至?xí)摺Ｓ捎诿總€類別文檔的數(shù)目不平衡，傳統(tǒng)特征選擇方法可能會導(dǎo)致正類被淹沒，從而影響最終的分類精度，甚至導(dǎo)致分類器不可用。不平衡數(shù)據(jù)問題是普遍存在的，經(jīng)常出現(xiàn)在如垃圾郵件過濾，文本過濾等自動文本分類的現(xiàn)實(shí)應(yīng)用中。因此，維吾爾文不平衡數(shù)據(jù)集的研究非常必要且意義重大。研究表明，可以通過調(diào)整訓(xùn)練數(shù)據(jù)分布，改進(jìn)特征選擇算法，調(diào)整每個特征的權(quán)值表示方法，修改分類算法等方面來改善不平衡數(shù)據(jù)給最終分類結(jié)果帶來的影響［4］，本文試圖從改進(jìn)特征選擇算法方面來解決該問題。

1 維吾爾文特性與預(yù)處理

正如中文不同于英文，需要分詞處理一樣，維吾爾文也有自身的語言特性。維吾爾文屬于阿爾泰語系突厥語族，在結(jié)構(gòu)語法上屬于粘著語類型。現(xiàn)代維吾爾文是以阿拉伯文字為基礎(chǔ)的拼音文字，字母共有32個，其中8個元音字母，24個輔音字母。維吾爾文字母形體因單獨(dú)書寫，或者在詞首、詞中、詞尾的位置不同，而略有不同，32個字母共有126種書寫形體。

維吾爾文中詞與詞之間采用空格隔開，不同于中文，需要進(jìn)行分詞。維吾爾文詞通常是由詞根或者詞干添加詞綴來構(gòu)成的，詞根和詞干的區(qū)別在于詞根可以結(jié)合構(gòu)詞附加成分構(gòu)成新詞，而詞干只能和構(gòu)形附加成分結(jié)合表示各種語法意義。詞綴可以加在詞根、詞干之前，也可以加在之后。由于詞綴的不同，包含相同詞干的維吾爾文單詞可以表示多種意思相同，但是形態(tài)、詞性不同的表示方法。

這種豐富的形態(tài)變化方式使得維吾爾文的詞匯量變的非常巨大，目前收集到的維吾爾文詞干的數(shù)目大約為4萬個，而維吾爾文詞典收集到的單詞數(shù)目超過100萬。目前沒有哪個文本分類方法可以在百萬這個數(shù)量級的特征空間上表現(xiàn)良好，因此需要對維吾爾文文本特征空間進(jìn)行降維處理。由于維吾爾文附加成分—詞綴本身沒有詞義，可以對維吾爾文單詞進(jìn)行切分［5］，去除不表示詞義的詞綴，僅使用詞干和詞根作為特征進(jìn)行文本分類。

維吾爾文也有一些表示語氣，量詞等詞語，對表示文本的意義沒有幫助，而且出現(xiàn)頻率較高會給分類帶來噪音，因而可以去掉這些詞條來降低特征維數(shù)。本文使用的停用詞表是由人工收集的，共516個單詞。

2 現(xiàn)有的特征選擇方法

在統(tǒng)計(jì)機(jī)器學(xué)習(xí)中，特征選擇就是通過選擇特征空間的一個子集來構(gòu)建一個好的學(xué)習(xí)模型。目前，有以下比較成熟的特征選擇方法：卡方檢驗(yàn)（chi－squared，CHI），信息增益（information gain，IG），讓步比（odds ratio，Odds），文檔頻數(shù)（document frequency，DF）等。其中，CHI和IG在中文和英文文本分類中，分類效果要更好［6］。這些特征選擇方法都是從全局的角度來度量特征，而沒有考慮到不平衡數(shù)據(jù)集問題。

2.1 CHI（Chi－Squared）

CHI［7］，其思想是通過觀測實(shí)際值與理論值之間的偏差來確定假設(shè)理論是否成立。CHI值越大，表明相關(guān)度越高，反之相關(guān)度越小。CHI的公式如下

式中：E——期望，即理論值。xi——觀測樣本值。

設(shè)詞條ti與類別Cj，那么可以按照含有詞條ti的文檔是否屬于類別Cj的關(guān)系，得到如下關(guān)系表（見表1）。

表1 詞條與類別關(guān)系

其中：A指包含詞條ti且屬于Cj類的文檔數(shù)；B指包含詞條ti屬于Cj類的文檔數(shù)；C指不包含詞條ti屬于Cj類的文檔數(shù)；D指不含有詞條ti不屬于Cj類的文檔數(shù)；

CHI的化簡公式為

式中：n指樣本集中所有的文檔總數(shù)；

2.2 IG（Information Gain）

IG，IG經(jīng)常被用在機(jī)器學(xué)習(xí)中，它是通過度量一個特征是否在某個文檔中，看能夠給分類系統(tǒng)帶來多少信息，得到特征與類別之間的關(guān)聯(lián)［8］。信息增益的公式如下

式中：t——詞條，Ci——類別，P（t）——t出現(xiàn)的概率，m——類別數(shù)目。

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

CHI和IG在英文文本分類中相對于DF，MI來說，有更好的分類精度。但是這兩種特征選擇方法都有其缺點(diǎn)。CHI只考慮一個詞特征是否出現(xiàn)在文檔中，而忽略了詞頻信息，這就可能偏袒低頻詞，即 “低頻缺陷”；IG考慮了一個詞特征是否出現(xiàn)在某個文檔中，但是IG只是從全局的角度出發(fā)，度量所有的特征詞進(jìn)行選擇，沒有考慮每一類中具有代表性的特征詞。

由于不平衡數(shù)據(jù)集中正類的數(shù)目會遠(yuǎn)遠(yuǎn)少于負(fù)類，從而被負(fù)類淹沒，而CHI和IG都是通過對比訓(xùn)練樣本中所有的詞，挑選相關(guān)度最高的特征，而忽視了那些能夠更好的表示某一類別的特征詞。試想一個極端的例子，如果正類中只有一篇文章，負(fù)類中含有無窮多的文檔數(shù)，那么即使正類中的特征對于區(qū)分正類負(fù)類有著非常重要的作用，最終也會被忽略。

造成這一結(jié)果的原因在于正負(fù)兩類文檔數(shù)目偏差過大，使得正類被淹沒，因此試圖找到一個合適的方法，用來抑制負(fù)類文檔數(shù)目過多這一問題。考慮idf（inverse document frequency）逆文檔頻數(shù)，即文檔頻數(shù)的倒數(shù)。由于負(fù)類的文檔數(shù)目很多，那么能夠很好的表示負(fù)類的詞的文檔頻數(shù)也會較高，從而其idf值就會較?。粚τ谀軌蚝芎玫谋硎菊惖奶卣髟~，由于正類的總文檔數(shù)目較少，該特征詞的idf值就會較大；對于在所有類別集合中都多次出現(xiàn)的特征詞，這類特征詞可能對分類沒有特別大的幫助，如停用詞等，其idf值也會較小。如上文所說，idf可以平衡出現(xiàn)在負(fù)類中文檔頻數(shù)較高、在正類中文檔頻數(shù)較低、以及整體數(shù)據(jù)集中文檔頻數(shù)較高的問題，從而使得所選擇的特征更加合理。單一的使用idf進(jìn)行特征選擇效果并不理想［9］，而多種特征選擇方法想結(jié)合可能會得到更好的分類精度［10－11］?？紤]將現(xiàn)有的特征選擇方法和idf相結(jié)合，以提高維吾爾文不平衡數(shù)據(jù)集文本分類的分類精度。

綜上所述提出一種改進(jìn)的特征選擇方法，CIDF——卡方檢驗(yàn)和逆文檔頻數(shù)相結(jié)合的方法。

平滑后的idf公式為

式中：n——訓(xùn)練集中總得文檔數(shù)，df——文檔頻數(shù)。

CIDF公式如下

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

4.1 分類器

式中：C——類別集合，Cj——類別，P（Cj）——類別Cj出現(xiàn)的概率，P（ωi｜Cj）——詞條ωi出現(xiàn)在Cj中的概率。

4.2 數(shù)據(jù)集

由于維吾爾文文本分類的研究還處于初級階段，沒有一個統(tǒng)一的語料庫，因而首先建立維吾爾文語料庫。由于人民網(wǎng)維吾爾文版塊的內(nèi)容較為正規(guī)，方便整理，本文爬取了人民網(wǎng)維吾爾文新聞版塊的內(nèi)容，作為語料庫。選取兩類新聞網(wǎng)頁作為不平衡數(shù)據(jù)集，類別信息表見表2。

表2 類別信息

實(shí)驗(yàn)數(shù)據(jù)共分9組，按照正類和負(fù)類的文檔數(shù)目比例從1：10到9：10分組，其中負(fù)類的訓(xùn)練樣本數(shù)目為948篇，正類的數(shù)目按照比例設(shè)定。測試樣本，正類626篇，負(fù)類608篇，每組的測試樣本都相同。

4.3 評價方法

目前主要的文本分類評價方法有3個［12］，如下

式中：li——分類的結(jié)果中被標(biāo)記為第i個類別且標(biāo)記正確的文本個數(shù)，mi——結(jié)果中表示被標(biāo)記成第i個類的文本個數(shù)，ni——被分類的文本中實(shí)際屬于第i個類別的樣本個數(shù)。

由于不平衡數(shù)據(jù)集中正類的數(shù)目遠(yuǎn)遠(yuǎn)少于負(fù)類，選擇準(zhǔn)確率或者召回率作為評價標(biāo)準(zhǔn)容易忽視正類的性能，從而無法很好的表示不同特征選擇算法對不平衡數(shù)據(jù)的影響。而F1值綜合考慮的準(zhǔn)確率和召回率，只有兩個值都比較高的時候才能取得較好的F1值，F(xiàn)1值越高說明分類結(jié)果越好。本文選擇宏平均F1作為評價公式

式中：F1i——第i類的F1值，m——總的類別數(shù)。

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

為了能夠更加直觀的了解分類性能，分別從不同平衡比和不同特征維數(shù)兩個方面描述實(shí)驗(yàn)結(jié)果。

圖1是當(dāng)特征維數(shù)為1000時，正類和負(fù)類不同比值的F1值圖。對于CHI和IG來說，在高不平衡比的訓(xùn)練中，由于正類被負(fù)類淹沒，使得正類的F1值趨近于0，這樣使得整體的宏F1值變小，而文本提出的CIDF方法，由于使用idf抑制了負(fù)類的高文檔頻數(shù)，使得分類結(jié)果明顯高于其它兩種特征選擇方法。當(dāng)正類和負(fù)類的比值接近1：1時，3種特征選擇方法的分類結(jié)果變得非常相似，這是因?yàn)橛捎趦深惖奈臋n數(shù)目接近，使得idf失去作用，進(jìn)而還可能使得分類精度下降。

圖1 特征維數(shù)為1000時的不同平衡比的F1值圖

圖2是正類和負(fù)類的文檔數(shù)目比在3：10時的不同特征維數(shù)的F1值圖。CIDF特征選擇方法在不同維數(shù)都優(yōu)于CHI方法。在低維空間時IG的分類結(jié)果高于CIDF，從400維開始，CIDF特征選擇方法的結(jié)果開始高于IG方法，并且分類結(jié)果較為穩(wěn)定，可以看出IG方法在特征維數(shù)增加的情況，下降很快。從上圖得知，CIDF總體要優(yōu)于CHI和IG方法。

圖2 不平衡比為3∶10時的不同維數(shù)F1值圖

5 結(jié)束語

本文論述了維吾爾文的語言特征和不平衡數(shù)據(jù)集特有的問題，將CHI和IDF相結(jié)合，提出一種針對維吾爾文不平衡數(shù)據(jù)集的特征選擇方法CIDF。使用宏平均F1值作為評價標(biāo)準(zhǔn)。實(shí)驗(yàn)證明該方法在維吾爾文不平衡數(shù)據(jù)集文本分類問題上優(yōu)于CHI和IG這兩種特征選擇方法。在后續(xù)研究中，會繼續(xù)完善維吾爾文語料庫，尋找新的針對維吾爾文不平衡數(shù)據(jù)集的權(quán)重計(jì)算方法，通過分析和改進(jìn)維吾爾文文本分類的各個環(huán)節(jié)，提供其在不平衡數(shù)據(jù)集上的分類精度。

［1］Alimjan AYSA，Turgun IBRAHIM.Machine learning based Uyghur language text categorization［J／OL］.Computer Engineering and Applications，2012，48（5）：110－112（in CHinese）.［2011－07－14］.http：／／www.cnki.net／kcms／detail／11.2127.TP.20110714.1549.012.html（in Chinese）.［阿里木江·艾沙，吐爾根·伊布拉音.基于機(jī)器學(xué)習(xí)的維吾爾文文本分類研究［J／OL］.計(jì)算機(jī)工程與應(yīng)用，2012，48（5）：110－112.［2011－07－14］.http：／／www.cnki.net／kcms／detail／11.2127.TP.20110714.1549.012.html.］

［2］Halqam Aisa，Winira Musajan.Study on web document classification of Uyghur，Kazak，Kirgiz multi－lingual search engine［J］.Journal of Xinjiang University（Natural Science Edition），2010，28（3）：362－365（in Chinese）.［海麗且木·艾莎，維尼拉·木沙江.維、哈、柯多文種搜索引擎中web文本分類的研究［J］.新疆大學(xué)學(xué)報（自然科學(xué)版），2010，28（3）：362－365.］

［3］Nitesh V Chawla.Data mining for imbalanced datasets：An overview［M］.Springer，2010：875－886.

［4］LI Jun.Research on the imbalanced data learning［D］.Changchun：Jilin University，2011（in Chinese）.［李軍.不平衡數(shù)據(jù)學(xué)習(xí)的研究［D］.長春：吉林大學(xué)，2011.］

［5］XUE Huajian，DONG Xinghua，WANG Lei，et al.Unsupervised Uyghur word segmentation method based on affix corpus［J］.Computer Engineering and Design，2011，32（9）：3191－3194（in Chinese）.［薛化建，董興華，王磊，等.基于詞綴庫的非監(jiān)督維吾爾語詞切分方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（9）：3191－3194.］

［6］YANG Fenqiang，LIU Yugui.A new feature selection method based on class－concept in text categorization［J］.Computer Systems ＆ Applications，2009，18（10）：93－96（in Chinese）.［楊奮強(qiáng)，劉玉貴.文本分類中基于類別概念的特征選擇方法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，18（10）：93－96.］

［7］PEI Yingbo，LIU Xiaoxia.Study on improved CHI for feature selection in Chinese text categorization［J］.Computer Engineering and Applications，2011，47（4）：128－130（in Chinese）.［裴英博，劉曉霞.文本分類中改進(jìn)型CHI特征選擇方法的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（4）：128－130.］

［8］LIU Ting，QIN Bing，ZHANG Yu，et al.Information retrieval system introduction［M］.Beijing：China Machine Press，2008：186－204（in Chinese）.［劉挺，秦兵，張宇，等.信息檢索系統(tǒng)導(dǎo)論［M］.北京：機(jī)械工業(yè)出版社，2008：186－204.］

［9］Pui Cheong Gabriel Fung，F(xiàn)red Morstatter，Huan Liu.Feature selection strategy in text classification［C］／／Shenzhen：The 15th Pacific－Asia Conference on Knowledge Discovery and Data Mining，2011.

［10］Scott Olsson J，Douglas W Oard.Combining feature selectors for text classification［C］／／Virginia：Proceedings of the 15th ACM International Conference on Information and Knowledge Management，2006.

［11］Robert Neumayer，Rudolf Mayer，KjetilCombination of feature selection methods for text categorization［C］／／Berlin，Heidelberg：Proceedings of the 33rd European Conference on Advances in Information Retrieval，2011.

［12］YANG Ming，YIN Junmei，JI Genlin.Classification methods on imbalanced data：A survey［J］.Journal of Nanjing Normal University（Engineering and Technology Edition），2008，8（4）：7－12（in Chinese）.［楊明，尹軍梅，吉根林.不平衡數(shù)據(jù)分類方法綜述［J］.南京師范大學(xué)學(xué)報（工程技術(shù)版），2008，8（4）：7－12.］