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

董 瑞，周 喜

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

0 引 言

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

1 維吾爾文特性與預處理

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

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

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

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

2 現有的特征選擇方法

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

2.1 CHI（Chi－Squared）

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

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

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

表1 詞條與類別關系

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

CHI的化簡公式為

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

2.2 IG（Information Gain）

IG，IG經常被用在機器學習中，它是通過度量一個特征是否在某個文檔中，看能夠給分類系統帶來多少信息，得到特征與類別之間的關聯［8］。信息增益的公式如下

式中：t——詞條，Ci——類別，P（t）——t出現的概率，m——類別數目。

3 改進的特征選擇方法

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

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

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

綜上所述提出一種改進的特征選擇方法，CIDF——卡方檢驗和逆文檔頻數相結合的方法。

平滑后的idf公式為

式中：n——訓練集中總得文檔數，df——文檔頻數。

CIDF公式如下

4 實驗與分析

4.1 分類器

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

4.2 數據集

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

表2 類別信息

實驗數據共分9組，按照正類和負類的文檔數目比例從1：10到9：10分組，其中負類的訓練樣本數目為948篇，正類的數目按照比例設定。測試樣本，正類626篇，負類608篇，每組的測試樣本都相同。

4.3 評價方法

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

式中：li——分類的結果中被標記為第i個類別且標記正確的文本個數，mi——結果中表示被標記成第i個類的文本個數，ni——被分類的文本中實際屬于第i個類別的樣本個數。

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

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

4.4 實驗結果

為了能夠更加直觀的了解分類性能，分別從不同平衡比和不同特征維數兩個方面描述實驗結果。

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

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

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

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

5 結束語

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

［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／OL］.計算機工程與應用，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］.新疆大學學報（自然科學版），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）.［李軍.不平衡數據學習的研究［D］.長春：吉林大學，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）.［薛化建，董興華，王磊，等.基于詞綴庫的非監督維吾爾語詞切分方法［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）.［楊奮強，劉玉貴.文本分類中基于類別概念的特征選擇方法［J］.計算機系統應用，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）.［裴英博，劉曉霞.文本分類中改進型CHI特征選擇方法的研究［J］.計算機工程與應用，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）.［劉挺，秦兵，張宇，等.信息檢索系統導論［M］.北京：機械工業出版社，2008：186－204.］

［9］Pui Cheong Gabriel Fung，Fred 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）.［楊明，尹軍梅，吉根林.不平衡數據分類方法綜述［J］.南京師范大學學報（工程技術版），2008，8（4）：7－12.］