文本分類(lèi)的特征選取方法

文本分類(lèi)的特征選取方法

高維特征集不一定對(duì)高維特征集的分類(lèi)學(xué)習(xí)產(chǎn)生重要和有用的影響。另外,高維的特征集還會(huì)加劇機(jī)器學(xué)習(xí)的負(fù)擔(dān),使用較多的時(shí)間但卻得到較少的相關(guān)特征,這樣的分類(lèi)結(jié)果不能令人滿意。針對(duì)這樣高維的特征集,在機(jī)器學(xué)習(xí)中的許多特征子集的選取方法都不再適用,因而我們采用評(píng)估函數(shù)的方法,對(duì)特征集中的所有特征進(jìn)行評(píng)估,然后將得到的評(píng)估分?jǐn)?shù)進(jìn)行有序排列,取閾值范圍內(nèi)的特征形成特征子集,而閾值的選取要根據(jù)具體問(wèn)題的實(shí)驗(yàn)來(lái)確定。我們常采用的評(píng)估方法有文檔頻次(DF)、信息增益(IG)、互信息(MI)、x2統(tǒng)計(jì)(CHI)、期望交叉熵(ECE)和幾率比(OR)等。其中文檔頻次、信息增益、互信息和x2統(tǒng)計(jì)在實(shí)際應(yīng)用中都是非常有效的評(píng)估函數(shù)。用這幾種評(píng)估方法進(jìn)行特征選取后,再用K-最近鄰、貝葉斯等分類(lèi)法分類(lèi)文本,會(huì)得到一個(gè)平均精確度較滿意的結(jié)果。1分類(lèi)方法的選取文本分類(lèi)是文本挖掘的一種方法,主要是將每個(gè)文本自動(dòng)分配到預(yù)先定義好的類(lèi)中。具體的做法是:通過(guò)選擇每個(gè)類(lèi)的特征詞或特征詞組進(jìn)行類(lèi)別分析,通過(guò)訓(xùn)練,形成將來(lái)可用于新文本分類(lèi)的特殊用表。在分類(lèi)時(shí),將被分類(lèi)文本的特征選取出來(lái),和已經(jīng)形成的特殊用表中的一套特征進(jìn)行比較,相匹配的劃歸為一類(lèi)。近幾年來(lái),許多的統(tǒng)計(jì)分類(lèi)方法和機(jī)器學(xué)習(xí)技術(shù)都用在了文本分類(lèi)方面,包括線性回歸模型、K-最近鄰分類(lèi)、貝葉斯概率方法、決策樹(shù)、支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)等。文本分類(lèi)的一個(gè)主要的問(wèn)題就是高維的特征空間。這些特征空間是由文檔中的詞或詞組構(gòu)成的,對(duì)于一個(gè)中等程度的文檔集可能就會(huì)形成成百上千萬(wàn)的特征項(xiàng)。對(duì)于許多的學(xué)習(xí)算法來(lái)說(shuō)這么高維的特征項(xiàng)是無(wú)法處理的。比如貝葉斯無(wú)法實(shí)現(xiàn)龐大的計(jì)算模型。而神經(jīng)網(wǎng)絡(luò)也幾乎無(wú)法處理這樣巨大數(shù)據(jù)量的輸入節(jié)點(diǎn)。因而在不影響特征準(zhǔn)確度的情況下減少原來(lái)的文本描述空間是很有必要的,同時(shí)也希望能夠去掉一些不表示任何信息的詞,最終建立特征子集。本文主要討論在文本分類(lèi)問(wèn)題中縮減高維特征向量空間的評(píng)估方法,好的特征選取方法在某種程度上能提高分類(lèi)的精確度。通常我們使用信息增益的方法迅速減少文檔詞匯,也可以使用互信息和x2統(tǒng)計(jì)去選取特征,然后作為分類(lèi)系統(tǒng)的輸入。2篩選特征選擇向量降維以及對(duì)文本向量權(quán)值的調(diào)整,通常是通過(guò)在訓(xùn)練數(shù)據(jù)集上的統(tǒng)計(jì)來(lái)計(jì)算每一維的某種特征值,根據(jù)指標(biāo)值的高低決定是否保留相應(yīng)的字或詞,或者對(duì)對(duì)應(yīng)維的權(quán)值進(jìn)行加權(quán),從而實(shí)現(xiàn)特征選擇和提取。存在多種篩選特征項(xiàng)的算法,如根據(jù)詞和類(lèi)別的互信息量判斷,根據(jù)詞熵判斷,根據(jù)距離判斷等不純度度量。在實(shí)際應(yīng)用中常采用的評(píng)估方法都有一個(gè)選詞標(biāo)準(zhǔn),從文本集的所有詞匯中選取出一個(gè)希望得到有某個(gè)限定范圍的特征詞。2.1特征詞頻率變化文檔頻次是指有該詞條出現(xiàn)的文檔數(shù)量。在訓(xùn)練文本集中對(duì)每個(gè)詞條計(jì)算它的文檔頻次,并且剔除在特征空間中文檔頻次小于預(yù)先定義的閾值的詞條。文檔詞頻是縮減詞條的最簡(jiǎn)單的方法。它通過(guò)在訓(xùn)練文檔數(shù)量中計(jì)算線性近似復(fù)雜度來(lái)衡量巨大的文檔集,該方法通常被認(rèn)為是一個(gè)提高效率的特別方法,而不僅僅是一個(gè)選擇特征詞的規(guī)則標(biāo)準(zhǔn),因?yàn)樵谛畔⑻崛≈杏幸粋€(gè)廣泛承認(rèn)的規(guī)則標(biāo)準(zhǔn)。低的文檔頻次被認(rèn)為和文本分類(lèi)任務(wù)不相關(guān)。2.2信息增益評(píng)估函數(shù)信息增益在機(jī)器學(xué)習(xí)中經(jīng)常被用作特征詞評(píng)判的標(biāo)準(zhǔn),它是一個(gè)基于熵的評(píng)估方法,涉及較多的數(shù)學(xué)理論和復(fù)雜的熵理論公式,定義為某特征在文檔中出現(xiàn)前后的信息熵之差。根據(jù)訓(xùn)練數(shù)據(jù),計(jì)算出各個(gè)特征詞的信息增益,刪除信息增益很小的詞,其余的按照信息增益從大到小排序。如果以信息增益最大者為根結(jié)點(diǎn),建立一棵決策樹(shù),就可以進(jìn)行決策數(shù)的分類(lèi)挖掘。信息增益評(píng)估函數(shù)被定義為表示目標(biāo)空間的類(lèi)集c,w為特征詞條,其中p(w)為詞條出現(xiàn)的概率,表示詞條w不出現(xiàn),p(ci)為i類(lèi)值的出現(xiàn)概率,p(ci∧w)為詞條出現(xiàn)時(shí)屬于第i類(lèi)的條件概率。這個(gè)定義比較綜合地應(yīng)用在二元分類(lèi)模型中,這種計(jì)算包括估算給定詞條類(lèi)的條件概率和在這個(gè)定義中的熵計(jì)算。概率估計(jì)有時(shí)間復(fù)雜度O(N)和空間復(fù)雜度O(N),其中N是訓(xùn)練文檔的數(shù)量,L是詞條的長(zhǎng)度,熵計(jì)算有時(shí)間復(fù)雜度O(Lm)。2.3對(duì)于概率的預(yù)測(cè)互信息是普遍應(yīng)用在相關(guān)詞統(tǒng)計(jì)語(yǔ)言建模中,假設(shè)有詞條w和類(lèi)c,X是w出現(xiàn)時(shí)屬于類(lèi)c的次數(shù),Y是w出現(xiàn)時(shí)不屬于類(lèi)c的次數(shù),Z是類(lèi)c中不出現(xiàn)w的次數(shù),N是總的文檔數(shù),w和c互信息定義為其中p(w∧c)定義為w和c的同現(xiàn)概率,p(w)定義為w出現(xiàn)的概率,p(c)定義為c出現(xiàn)的概率。從概率上說(shuō),如果某個(gè)詞和某一類(lèi)別在分布上統(tǒng)計(jì)獨(dú)立,那么p(w∧c)=p(w)×p(c),從而有MI(w,c)=0,也就是說(shuō)詞w的出現(xiàn)對(duì)于預(yù)測(cè)類(lèi)別c沒(méi)有什么信息量。在實(shí)際計(jì)算中,這些概率可以用訓(xùn)練集中相應(yīng)的出現(xiàn)頻率予以近似。評(píng)價(jià)函數(shù)為假如w始終沒(méi)在c中出現(xiàn),則MI(w,c)=0,為了評(píng)價(jià)一個(gè)特征選取詞的好壞,我們結(jié)合詞條在不同類(lèi)中的得分和兩種交替的方法:互信息計(jì)算有一個(gè)時(shí)間復(fù)雜度,類(lèi)似于信息增益?；バ畔⒌牟蛔阒幵谟诘梅址浅Ｊ茉~條的邊緣概率的影響,就像在這個(gè)式子中看到的。對(duì)于有相等條件概率的一些詞,稀有詞比常用詞的得分還要高,因此對(duì)于頻率相差很大的詞,得分是不具備可比性的。2.4創(chuàng)建使用x統(tǒng)計(jì)的規(guī)范x2統(tǒng)計(jì)評(píng)估定義如下:其中概率是指對(duì)于文本x,特征詞條w不存在其中,但x屬于類(lèi)c中,r是訓(xùn)練集的勢(shì)。直觀地看,x2(w,c)的值越小,說(shuō)明特征詞條w關(guān)于類(lèi)c的獨(dú)立程度越高,因此我們選擇那些x2(w,c)值最大的特征詞條。假設(shè)X是詞條w出現(xiàn)在類(lèi)c中的次數(shù),Y是w出現(xiàn)但不在類(lèi)c中的次數(shù),Z是w不出現(xiàn)的次數(shù),Q是w和c都不出現(xiàn)的次數(shù),N是文檔的總數(shù),詞條好壞的評(píng)估定義為如果詞條w和類(lèi)c是相互獨(dú)立的,x2統(tǒng)計(jì)為零。我們?cè)谟?xùn)練集中的每個(gè)詞條和類(lèi)之間計(jì)算每個(gè)類(lèi)的x2統(tǒng)計(jì),然后結(jié)合每個(gè)詞條的針對(duì)某個(gè)類(lèi)的得分,得到如下的分?jǐn)?shù)x2統(tǒng)計(jì)得分的計(jì)算有二次復(fù)雜度,相似于互信息和信息增益。在x2統(tǒng)計(jì)和互信息之間主要的不同是x2是規(guī)格化評(píng)價(jià),因而x2評(píng)估對(duì)在同類(lèi)中的詞是可比的。但是x2統(tǒng)計(jì)對(duì)于低頻詞來(lái)說(shuō)是不可靠的。如果對(duì)以上的公式做個(gè)改進(jìn),將其求平方根,進(jìn)一步強(qiáng)調(diào)特征詞條和類(lèi)wc之間的相關(guān)性,其中在修改以后的公式中幾乎不強(qiáng)調(diào)什么特征,因?yàn)閷?duì)于類(lèi)而言這些因素的值很小,只起到一個(gè)極小的微調(diào)作用,而在分子中的作用可以忽略。將以上3個(gè)因素從x2(w,c)的平方根中去掉,我們將得到簡(jiǎn)化的x2統(tǒng)計(jì)方法:通過(guò)一些實(shí)驗(yàn)證明了簡(jiǎn)化后的x2方法比原來(lái)的x2方法要好,大幅度地減少了特征,同時(shí)也縮小了計(jì)算的工作量,因而簡(jiǎn)化的x2方法是一個(gè)從根本上降低了特征空間維數(shù)的好方法。3線性回歸模型在研究了以上特征選取評(píng)估方法以后,進(jìn)一步探討在此基礎(chǔ)上的分類(lèi)方法,因?yàn)樘卣鬟x取是分類(lèi)方法的預(yù)處理,所以在得到較滿意的特征子集后,就可以開(kāi)始分類(lèi)挖掘了。常使用的分類(lèi)方法有:K-最近鄰分類(lèi)法(K_Nearest_Neighbor)、線性回歸模型(LinearRegressionMethod)、樸素貝葉斯分類(lèi)(NaiveBayes)、決策樹(shù)(DecisionTree)、支持向量機(jī)(SupportVectorMachines)和神經(jīng)網(wǎng)絡(luò)(NeuralNetwork)等。這些系統(tǒng)的輸入是將要被分類(lèi)的文檔集,該文檔集是由特征詞權(quán)重構(gòu)成的稀疏矩陣,系統(tǒng)的輸出是由每個(gè)類(lèi)的信任度的評(píng)分組成的有序列表。在k-最近鄰方法中類(lèi)隊(duì)列表是根據(jù)分配給最近鄰訓(xùn)練集輸入的類(lèi),其相似度由它們的夾角余弦得出。假如一個(gè)類(lèi)屬于多個(gè)鄰居,那么這些鄰居的相似度分?jǐn)?shù)的總和就是這個(gè)類(lèi)在輸出時(shí)的權(quán)值。所以說(shuō)k_最近鄰算法是將一個(gè)文檔的所屬類(lèi)別范疇的預(yù)測(cè)建立在與之最為相似的k個(gè)文檔所屬類(lèi)別的概率分布上。文檔x屬于類(lèi)c的概率表達(dá)式為其中xi是文檔x的k個(gè)最近鄰,它可以按不同的概率屬于不同的類(lèi)也可以屬于唯一的類(lèi)當(dāng)且僅當(dāng)j≠k;文檔的相似度計(jì)算公式為決策樹(shù)方法是以信息增益(IG)的標(biāo)準(zhǔn)來(lái)選擇信息詞的,它根據(jù)文檔中詞組合的出現(xiàn)概率預(yù)測(cè)所屬的類(lèi)別;支持向量機(jī)不僅能處理線性情況,對(duì)于非線性的問(wèn)題也可以通過(guò)非線性變換轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題,其算法復(fù)雜度與樣本維數(shù)無(wú)關(guān);神經(jīng)網(wǎng)絡(luò)能較容易地預(yù)測(cè)非線性系統(tǒng),包容噪音和錯(cuò)誤數(shù)據(jù);基于線性回歸模型的方法,是用文檔中的詞去預(yù)測(cè)類(lèi)的權(quán)值,回歸系數(shù)是由從訓(xùn)練文檔到訓(xùn)練類(lèi)的映射來(lái)決定的,它提供了完整的給定文檔的分類(lèi)排列,根據(jù)上下文相關(guān),并假設(shè)輸入詞條和輸出類(lèi)都是不獨(dú)立的,直接評(píng)估每個(gè)文檔的分類(lèi)。應(yīng)用文本特征選取在分類(lèi)方法的預(yù)處理中,特征選取方法效率的評(píng)估是根據(jù)分類(lèi)方法在預(yù)處理的文本上的執(zhí)行情況來(lái)考慮的。以上的分類(lèi)方法對(duì)每個(gè)文檔給出一個(gè)