李國和，岳 翔，吳衛(wèi)江，洪云峰 ，劉智淵 ，程 遠(yuǎn)

(1. 中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102249;2. 中國石油大學(xué)(北京) 油氣數(shù)據(jù)挖掘北京市重點實驗室，北京 102249；3. 石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院，北京 100029)

?

面向文本分類的特征詞選取方法研究與改進(jìn)

李國和1,2,3，岳 翔1,2，吳衛(wèi)江1,2,3，洪云峰3，劉智淵3，程 遠(yuǎn)3

(1. 中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102249;2. 中國石油大學(xué)(北京) 油氣數(shù)據(jù)挖掘北京市重點實驗室，北京 102249；3. 石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院，北京 100029)

中文特征詞的選取是中文信息預(yù)處理內(nèi)容之一，對文檔分類有重要影響。中文分詞處理后，采用特征詞構(gòu)建的向量模型表示文檔時，導(dǎo)致特征詞的稀疏性和高維性，從而影響文檔分類的性能和精度。在分析、總結(jié)多種經(jīng)典文本特征選取方法基礎(chǔ)上，以文檔頻為主，實現(xiàn)文檔集中的特征詞頻及其分布為修正的特征詞選取方法(DC)。采用宏F值和微F值為評價指標(biāo)，通過實驗對比證明，該方法的特征選取效果好于經(jīng)典文本特征選取方法。

文本文檔；特征詞；特征選??；文本分類

1 引言

文本分類的目的是將未知類別的文本劃歸到具體的類別中，其在文檔信息處理中主要具有信息過濾、內(nèi)容查重、組織管理等功能，成為信息檢索領(lǐng)域的重要應(yīng)用之一[1]。由于文檔的非結(jié)構(gòu)化或半結(jié)構(gòu)化特點，其中所隱含的信息難于直接進(jìn)行比較，因此采用結(jié)構(gòu)化的向量空間模型進(jìn)行文本表示[2-3]。在該模型中，特征由文本中具有語義的詞、短語等構(gòu)成，統(tǒng)稱特征詞。這使得文檔分類過程主要包括文本分詞、特征詞提取與優(yōu)化、特征加權(quán)和分類器構(gòu)建等階段[1]。特征詞的提取，除了可以去除停用詞(如標(biāo)點符號等)外，還可以完成文檔的特征向量表示的結(jié)構(gòu)化過程。由于采用統(tǒng)一特征向量形式表示所有文檔，導(dǎo)致針對每一文檔的特征向量具有高維性和稀疏性[4]。這不僅降低分類器的學(xué)習(xí)效率，而且影響甚至降低分類器的分類效果(包括精確率和召回率)。因此，通過特征選取方法，優(yōu)化特征維數(shù)，選取確保分類效果不變或改善的特征詞子集，成為文檔分類的重要研究內(nèi)容之一[5-6]。目前，特征詞的選取方法主要采用統(tǒng)計學(xué)的方法[1，7]，但是沒有考慮到特征詞在文檔中的分布特性。針對這一不足，本文提出特征詞分布的修正方法，完善特征詞選取的功能。

2 相關(guān)研究工作

先簡介一些相關(guān)基本概念，給出規(guī)范化的定義。

2.1 基本概念

D={di|i=1,2,…,n}為n個文檔的文檔集；T={ti|i=1,2,…,k}為k個特征詞的特征集；C={ci|i=1,2,…,m}為文檔的類別集；W={Wi|i=1,2,…,k}為所有特征值域的集合(即ω： D×T→Wi，對于?d∈D，ω(d, ti)∈Wi為文檔d的特征詞ti的特征值，也稱特征詞加權(quán)的權(quán)值)；D(t)?D為含有特征詞t∈T的文檔集，D(c)?D為屬于類別c∈C的文檔集，D(t,c)?D為屬于類別c∈C并且含有特征詞t∈T的文檔集，DF(t)=|D(t)|為含有特征詞t∈T的文檔頻(即文檔集D(t)中的文檔數(shù))，DF(c)=|D(c)|為屬于類別c∈C的文檔頻(即文檔集D(c)中的文檔數(shù))，DF(t,c)=|D(t,c)|為屬于類別c并且含有特征詞t∈T的文檔頻(即文檔集D(c)中含有特征詞t的文檔數(shù))，TF(t, D′)為文檔集D′ ?D中出現(xiàn)特征詞t∈T的詞頻(即文檔集D′中出現(xiàn)特征詞t的次數(shù))。定義c類別概率、t詞頻概率、t詞頻與c類別關(guān)系的聯(lián)合概率和條件概率，如下所示。

(1)

(2)

(3)

(4)

(5)

t、c分別為非特征詞t和非類別c，也可定義有關(guān)概率。實際上，這些概率均為關(guān)于文檔頻的頻率。

文本分類就是構(gòu)造分類器函數(shù)φ:D×T→C，即φ(d,ω1(d,t1),ω2(d,t2),...,ωk(d,tk))∈C。特征詞選取就是選取特征詞子集SubT?T，并使分類器函數(shù)η:D×SubT→C滿足η(d,SubT)=φ(d,T)，即特征子集與原有特征集具有相同的分類能力。

2.2 經(jīng)典文本特征選取方法

經(jīng)典文本特征選取有信息增益IG[8]、互信息熵MI[8]、卡方χ2[8]、文檔證據(jù)權(quán)WET[9]、期望交叉熵EC[9]、相對熵H[5]等，還有與文本類別無關(guān)的文檔頻DF[8]等，它們均為基于統(tǒng)計學(xué)的方法。各種特征詞的選取方法是定義特征詞t∈T對文檔所有類別c∈C的分類能力評估函數(shù)。這些函數(shù)涉及如2.1所述的概率。通過特征詞分類評估函數(shù)評價每個特征詞t的分類能力，選取分類能力強(qiáng)的若干個特征詞構(gòu)成特征詞子集SubT。

這些評估函數(shù)(DF方法除外)都體現(xiàn)出特征詞t與文檔類別c之間統(tǒng)計意義下的關(guān)聯(lián)關(guān)系，如信息增益IG：

(6)

其強(qiáng)調(diào)特征詞t對文本分類的影響，即特征詞t決策類別c的能力，而互信息MI：

(8)

其強(qiáng)調(diào)特征詞t與類別c之間的相互關(guān)聯(lián)性，即特征詞t決策類別c并且類別c也決策特征詞t的能力。又如相對熵RE是文檔類別c概率分布{P(ci)|i=1,2,...,m}，與t∧c概率分布{P(t∧ci)|i=1,2,...,m}的相似性比較，表達(dá)形式如式(9)所示。

(9)

2.3 存在問題

經(jīng)典特征選取方法只是涉及到文檔頻DF，并不涉及到詞頻TF。實際上，詞頻TF對文檔分類具有很大的影響。一般情況下，文檔d∈D中某一特征詞t的詞頻TF(t,j5i0abt0b)越高，文檔內(nèi)涵越明確，文檔的類別就越清晰，所以該特征詞對文檔的分類能力也越強(qiáng)。鑒于此，文獻(xiàn)[10]提出了基于TFIDF的文檔特征選取方法，其核心思想是用屬于ci類且含有特征詞t的文檔數(shù)來刻畫特征詞t對ci類文檔的分類能力，即

(10)

還結(jié)合詞頻TF，定義特征詞t對ci類文檔的分類能力

(11)

3 基于文檔詞頻分布修正的特征詞選取方法

基于文檔詞頻分布修正的特征詞選取方法(DC)以文檔頻DF為主，兼顧文檔集中詞頻的分布對文檔分類的影響，涉及以下基本算子：

綜合上述四個基本算子，特征詞t的文檔分類能力評估函數(shù)定義如下：

(12)

表明了特征詞t在ci類文檔集中詞頻較大，而且分布比較均勻(即類中每個文檔的詞頻大小相當(dāng))，而在其他類詞頻較小，而且分布不均勻(即類中每個文檔的詞頻不相當(dāng))，則表示此特征詞的分類能力較強(qiáng)，因此該方法充分體現(xiàn)了類內(nèi)文檔相似性高、類間文檔差異性大的特點。

4 實驗結(jié)果對比

4.1 實驗基礎(chǔ)

實驗數(shù)據(jù)采用復(fù)旦大學(xué)計算機(jī)學(xué)院提供的文檔集，其類別數(shù)|C|=20，文檔數(shù)|D|=19 637。采用ICTCLAS分詞系統(tǒng)進(jìn)行分詞，得到特征詞數(shù)|T|約為13萬。采用TFIDF對所有文檔進(jìn)行加權(quán)[7]：

(11)

表示文檔d的特征詞t的權(quán)值。

分類器選用KNN[11]，并取K值為15。對文檔集D中的所有文檔進(jìn)行統(tǒng)一加權(quán)后，采用5-交叉驗證實驗，即所有文檔隨機(jī)均分成五組，一組為測試集，其他四組為訓(xùn)練集，共進(jìn)行五次實驗，最后評價指標(biāo)的平均值作為特征詞選取的依據(jù)。

4.2 效果評價標(biāo)準(zhǔn)

4.3 特征詞分類能力有效性實驗

根據(jù)式(10)對每一特征詞的分類能力進(jìn)行評估，并根據(jù)評估值從大到小對所有特征詞進(jìn)行排序。為了證明此特征選取方法的有效性，從有序的特征集中分別“從前到后”(即正向選取)、“從后到前”(即反向選取)和“隨機(jī)”(即隨機(jī)選取)選取特征詞n個，構(gòu)成三個n維特征向量，分別進(jìn)行文檔分類效果實驗。特征向量維數(shù)n的范圍為100到4 000。每隔100個特征詞做一次5-交叉實驗。實驗結(jié)果如圖1和圖2所示。從實驗結(jié)果可看出： ①正向選取的特征詞集分類效果好于反向選取特征詞集的分類效果，而隨機(jī)選取特征詞集的分類效果介于正向選取和反向選取的分類效果之間。②隨著特征詞數(shù)的增加，正向選取特征詞的文檔分類效果逐漸變好，而反向選取特征詞的分類效果基本不變。說明反向選取的特征詞分類能力特別弱。③特征詞數(shù)目大于4 000以后，正向選取特征集的分類效果基本保持不變，隨機(jī)選取特征集和反向選取特征集的分類效果在緩慢逐漸增大，但最大值也難于接近正向選取特征集的分類效果。其他特征詞分類能力的評價實驗結(jié)果與宏F值和微F值測試結(jié)果具有相似的變化趨勢。說明有序特征集中靠前的特征詞分類能力比較強(qiáng)，特征選取方法DC能夠?qū)μ卣髟~分類能力進(jìn)行有效評估，成為特征詞選取的依據(jù)。

圖1 宏F反映特征集分類能力

圖2 微F反映特征集分類能力

4.4 文本特征選取方法對比實驗

對文檔集進(jìn)行TFIDF加權(quán)后，分別采用詞頻修正DC、文檔頻DF、信息增益IG、互信息熵MI、統(tǒng)計量χ2(CHI)、文檔證據(jù)權(quán)WET、期望交叉熵ECE和DIS以及相對熵RE進(jìn)行文檔分類效果對比實驗，實驗結(jié)果如圖3和圖4所示。

圖3 不同特征詞選取方法比較(微F)

圖4 不同特征詞選取方法比較(宏F)

由圖3所示，所有特征選取方法的微F值隨著特征詞的增多都能達(dá)到一個比較穩(wěn)定的效果，其中DC方法優(yōu)于其他方法，最快達(dá)到的穩(wěn)定值和最大值。由圖4可知，上述所有方法的宏F值隨著特征詞的增多都呈現(xiàn)明顯的上升趨勢，但是DC方法上升趨勢更明顯，且達(dá)到的極值最大。當(dāng)特征詞大于4 000個以后，微F值和宏F值就沒有明顯增大趨勢，文檔分類效果基本達(dá)到極值。其他特征詞分類效果評價的變化趨勢與微F值和宏F值實驗結(jié)果變化趨勢相似。

5 結(jié)束語

通過分析現(xiàn)有多種基于統(tǒng)計學(xué)的文本特征詞選取方法，其實質(zhì)上是利用某個特征詞在一個文檔中是否出現(xiàn)對文檔類別的概率分布的影響來刻畫特征詞對文檔分類能力，只是應(yīng)用到文檔頻的信息。而這些特征選取方法缺乏考慮文檔詞頻和文檔詞頻分布對文檔分類的影響。針對這個缺陷，以文檔頻為主，結(jié)合文檔詞頻和文檔詞頻分布為修正，重新定義文本特征詞分類能力的評估函數(shù)。在此基礎(chǔ)上完成特征詞的分類能力排序，形成基于詞頻分布修正的文本特征詞選取方法DC。目前，文本特征詞選取方法主要是構(gòu)造特征詞分類能力評估函數(shù)，實現(xiàn)特征詞分類能力排序。以特征詞分類能力為啟發(fā)信息，采用分類能力強(qiáng)的特征詞組合(即特征詞分類能力的強(qiáng)強(qiáng)聯(lián)合)，逐一測試每一組合的分類效果(即精確率、召回率、F值)，人工選取認(rèn)可的特征詞子集集，但還缺少特征詞自動選取方法。另一方面，特征詞選取后采用其他方法(主要是TFIDF方法)對特征詞加權(quán)，即特征詞選取和特征詞加權(quán)是分離的。因此，下一步工作是實現(xiàn)自動特征選取方法和特征加權(quán)后再進(jìn)行特征詞選取的研究。

[1] 苗奪謙，衛(wèi)志華.中文文本信息處理的原理與應(yīng)用[M].北京： 清華大學(xué)出版社，2007

[2] 劉銘.大規(guī)模文檔聚類中若干關(guān)鍵問題的研究[D].哈爾濱工業(yè)大學(xué)博士學(xué)位論文. 2010.

[3] 熊忠陽，張鵬招，張玉芳.基于χ2統(tǒng)計的文本分類特征選擇方法的研究[J]，計算機(jī)應(yīng)用，2008,28(2)： 513-514

[4] 熊云波.文本信息處理的若干關(guān)鍵技術(shù)研究[D].復(fù)旦大學(xué)博士學(xué)位論文. 2006.

[5] 王 輝，張成鎖，卓呈祥.一種改進(jìn)的相對熵特征選擇方法[J].計算機(jī)工程，2011,37(10):167-169.

[6] 柴玉梅，王宇.基于TFIDF的文本特征選擇方法[J].微計算機(jī)信息，2006,22(8-3)： 24-26

[7] 蘇丹.一種基于最少出現(xiàn)文檔頻的文本特征提取方法[J].計算機(jī)工程與應(yīng)用，2012,48(10):164-166+178.

[8]BongCh,K.Narayanan.Anempiricalstudyoffeatureselectionfortextcategorizationbasedontermweightage[C]//ProceedingsoftheInternationalConferenceonWebIntelligence, 2004:599-602.

[9] 代六玲，黃河燕，陳肇雄.中文文本分類中特征抽取方法的比較研究[J].中文信息學(xué)報，2004,18(1)： 26-32.

[10]Saltong,Clementty.Ontheconstructionofeffectivevocabulariesforinformationretrieval[C]//Proceedingsofthe1973Meet-ingonProgrammingLanguagesandInformationRetrieva.lNewYork:ACM, 1973: 11.

[11] 宗成慶.統(tǒng)計自然語言處理[M].北京： 清華大學(xué)出版社，2011.

[12] 陳鍵.面向文本分類的特征詞選取方法研究[D]. 合肥工業(yè)大學(xué)碩士學(xué)位論文. 2009.

[13] 余俊英.文本分類中特征選擇方法的研究[D]. 江西師范大學(xué)碩士學(xué)位論文. 2007.

[14] 周茜，趙明生等. 中文文本分類中的特征選擇研究[J].中文信息學(xué)報，2003 ,18 (3):17- 23.

[15] 單松巍，馮是聰，李曉明.幾種典型特征選取方法在中文網(wǎng)頁分類上的效果比較[J].計算機(jī)工程與應(yīng)用，2003,39(22):146-148

[16]YangYiming，PedersenJO.Acomparativestudyonfeatureselectionintextcategorization[C]//ProceedingsoftheFourteenthInternationalConferenceonMachineLearning.SanFrancisco，CA，USA：ICML97MorganKaufmannPublishersInc，1997.

Feature Word Selection for Document Classification

LI Guohe1,2,3，YUE Xiang1,2，WU Weijiang1,2,3，HONG Yunfeng3，LIU Zhiyuan3，CHEN Yuan3

(1. College of Geophysics and Information Engineering, China University of Petroleum, Beijing 102249, China；2. Beijing Key Lab of Data Mining for Petroleum Data, China University of Petroleum, Beijing 102249, China；3. PanPass Institute of Digital Identification Management and Internet of Things, Beijing 100029, China)

Feature words selection from texts is a significant step in Chinese text information pre-processing. After the segmentation of Chinese texts, a Vector Model constructed by feature words representing the Chinese text documents cannot avoid low accuracy of document classification (or document retrieval) due to the sparseness and high-dimension of feature words. On the basis of an analysis of several classical text feature selection methods, a new method of text feature selection(DC) is presented, which is based on a modified document frequency. Experiments prove the performance of DC, is better than that of typical other methods according to macro-F values and micro-F values.

Text document; Feature word; Feature selection; Text classification

李國和(1965—),博士,教授,博士生導(dǎo)師,主要研究領(lǐng)域為智能信息處理,知識發(fā)現(xiàn),數(shù)據(jù)可視化等。E-mail:ligh@cup.edu.cn岳翔(1988—),碩士研究生,主要研究領(lǐng)域為智能信息處理,知識發(fā)現(xiàn)等。E-mail:yuexiang19881@126.com吳衛(wèi)江(1971—),在職博士研究生,副教授,主要研究領(lǐng)域為智能信息處理,知識發(fā)現(xiàn),數(shù)據(jù)可視化等。E-mail:allan1226@163.com

1003-0077(2015)04-0120-06

2013-07-14 定稿日期： 2013-11-12

國家高新技術(shù)研究發(fā)展計劃(2009AA062802)；國家自然科學(xué)基金(60473125)；中國石油(CNPC)石油科技中青年創(chuàng)新基金(05E7013)；國家重大專項子課題(G5800-08-ZS-WX)

TP391

A