一種高性能的文本特征自動(dòng)提取算法

一種高性能的文本特征自動(dòng)提取算法

自動(dòng)文本分類(lèi)是檢索和挖掘領(lǐng)域的研究熱點(diǎn)和關(guān)鍵技術(shù)。近年來(lái)，它引起了人們的廣泛關(guān)注和迅速發(fā)展。它在檢索、新聞推薦、含義差異、文本識(shí)別、網(wǎng)絡(luò)分類(lèi)等領(lǐng)域發(fā)揮著廣泛的作用。文本自動(dòng)分類(lèi)的主要難題之一是特征空間維數(shù)過(guò)高,如何降低特征空間維數(shù)成為文本自動(dòng)分類(lèi)中需要首先解決的問(wèn)題。特征選擇是文本特征降維的一種有效方法,很多學(xué)者對(duì)此進(jìn)行了深入的研究,并提出了很多有效的方法,比較經(jīng)典的有文檔頻率DF、信息增益IG、χ2統(tǒng)計(jì)量CHI、互信息MI和多種方法組合等。這些方法按其特征選擇函數(shù)計(jì)算函數(shù)值,然后以降序選擇靠前的特征集。在選擇過(guò)程中,選擇尺度是一個(gè)重要指標(biāo),直接影響著文本分類(lèi)的性能。實(shí)驗(yàn)證明:多數(shù)分類(lèi)器呈現(xiàn)出隨特征數(shù)量增加,效果快速提高并能迅速接近平穩(wěn)的特點(diǎn);但若特征數(shù)過(guò)大,性能反而可能降低。這表明合理的特征選擇尺度不僅能大量降低處理開(kāi)銷(xiāo),而且在很多情況下可以改善分類(lèi)器的效果。在確定特征選擇尺度時(shí),現(xiàn)有特征選擇方法通常采用經(jīng)驗(yàn)估算方法:如給定特征數(shù)的經(jīng)驗(yàn)值(PFC)或比例(THR)、考慮統(tǒng)計(jì)量閾值(MVS)或向量空間稀疏性(SPA)、特征數(shù)與文本數(shù)成比例(PCS)等一些選擇方法。這些方法在某些特定語(yǔ)料庫(kù)上取得比較好的效果,但通常為觀察所得或經(jīng)驗(yàn)推斷,理論基礎(chǔ)不充分,不便于文本自動(dòng)分類(lèi)的進(jìn)一步推廣研究;因此,研究能適應(yīng)文本特性的特征自動(dòng)提取方法是非常必要的。云模型是一種定性定量轉(zhuǎn)換模型,由于其具有良好的數(shù)學(xué)性質(zhì),可以表示自然科學(xué)、社會(huì)科學(xué)中大量的不確定現(xiàn)象。云模型不需要先驗(yàn)知識(shí),它可以從大量的原始數(shù)據(jù)中分析其統(tǒng)計(jì)規(guī)律,實(shí)現(xiàn)從定量向定性的轉(zhuǎn)化。本文作者結(jié)合特征在整體與局部上的χ2分布情況,利用云模型在定性知識(shí)表示以及定性、定量知識(shí)轉(zhuǎn)換時(shí)的橋梁作用,引入云隸屬度概念對(duì)特征分布加以修正,并且構(gòu)建了一種逐級(jí)動(dòng)態(tài)聚類(lèi)算法來(lái)獲取特征集,在此基礎(chǔ)上提出一種高性能文本特征自動(dòng)提取算法。該算法不需要指定聚類(lèi)數(shù)目,能根據(jù)特征分布特點(diǎn)自動(dòng)獲取隸屬度高的特征集。分析和開(kāi)放性實(shí)驗(yàn)結(jié)果表明:該特征集具有特征個(gè)數(shù)少、分類(lèi)精度高的特點(diǎn),性能明顯比當(dāng)前主要的特征選擇方法的優(yōu)。1于詞頻的特征選擇特征選擇是通過(guò)構(gòu)造一個(gè)特征評(píng)分函數(shù),把測(cè)量空間的數(shù)據(jù)投影到特征空間,得到在特征空間的值,然后,根據(jù)特征空間中的值對(duì)每個(gè)特征進(jìn)行評(píng)估。特征選擇并沒(méi)有改變?cè)继卣骺臻g的性質(zhì),只是從原始特征空間中選擇了一部分重要的特征,組成一個(gè)新的低維空間。特征選擇是文本特征降維的一種有效方法。目前已有的特征選擇方法主要分為2類(lèi):(1)傾向于詞頻的特征選擇方法,如DF,IG,χ2統(tǒng)計(jì)量CHI和MI等;(2)傾向于類(lèi)別的特征選擇方法,如CTD特征選擇方法和帶有強(qiáng)類(lèi)別信息詞SCIW特征選擇方法等。第1類(lèi)方法強(qiáng)調(diào)詞頻在所有類(lèi)別上的整體分布;第2類(lèi)方法強(qiáng)調(diào)類(lèi)別信息,而對(duì)詞頻在所有類(lèi)別上的整體分布考慮不充分。如果能有效地結(jié)合詞頻在所有類(lèi)別的整體分布和在單個(gè)類(lèi)別上的分布情況,將會(huì)明顯改善特征選擇性能。此外,還有期望交叉熵(ECE)、文本證據(jù)權(quán)(WET)、優(yōu)勢(shì)率(OR)等一些特征選擇方法,文獻(xiàn)對(duì)DF,IG,MI,CHI,ECE,WET和OR這些特征選擇方法進(jìn)行了比較,結(jié)果表明:OR方法的效果最好,IG,CHI和ECE的效果次之,WET和DF的效果再次之,MI的效果最差。而Yang等認(rèn)為IG是最好的測(cè)度之一。Forman等分別從有效性、區(qū)分能力及獲得最好效果的機(jī)會(huì)等方面對(duì)不同特征選擇方法進(jìn)行了廣泛比較,結(jié)果表明:CHI和IG等統(tǒng)計(jì)量及組合方法具有一定的優(yōu)勢(shì)。從上述分析看,這些方法對(duì)提高文本分類(lèi)的效果都沒(méi)有絕對(duì)優(yōu)勢(shì)。這是因?yàn)槲谋痉诸?lèi)本身涉及訓(xùn)練數(shù)據(jù)集合本身的特點(diǎn),同時(shí),不同分類(lèi)器的分類(lèi)效果也不盡相同。2類(lèi)別特征的統(tǒng)計(jì)方法χ2統(tǒng)計(jì)量的概念來(lái)自列聯(lián)表檢驗(yàn),用來(lái)衡量特征ti和類(lèi)別Cj之間的統(tǒng)計(jì)相關(guān)性。實(shí)驗(yàn)證明是一種比較好的特征選擇方法,它基于ti和Cj之間符合具有一階自由度的χ2分布假設(shè)。ti關(guān)于Cj的χ2可由下式計(jì)算:式中:N為訓(xùn)練語(yǔ)料中文檔總數(shù);A為屬于類(lèi)Cj的文檔頻數(shù);B為不屬于Cj類(lèi)但包含ti的文檔頻數(shù);C為屬于Cj類(lèi)但不包含ti的文檔頻數(shù);D是既不屬于Cj也不包含ti的文檔頻數(shù)?？芍?dāng)特征ti與類(lèi)別Cj相互獨(dú)立時(shí),χ2(ti,Cj)=0,此時(shí)特征ti不包含任何與類(lèi)別Cj有關(guān)的信息。特征ti與類(lèi)別Cj的統(tǒng)計(jì)相關(guān)性越強(qiáng),χ2(ti,Cj)越大,此時(shí),特征ti包含的與類(lèi)別Cj有關(guān)的信息就越多。由χ2計(jì)算公式可以看出:χ2統(tǒng)計(jì)方法作為特征選擇方法時(shí),只考慮了特征在所有文檔出現(xiàn)的文檔頻數(shù)。若某一特征只在一類(lèi)文檔的少量文檔中頻繁出現(xiàn),則通過(guò)χ2計(jì)算公式計(jì)算的χ2統(tǒng)計(jì)值很低,在特征選擇時(shí),這種特征詞就會(huì)被排除,但這種在少量文檔中頻繁出現(xiàn)的特征詞很有可能對(duì)分類(lèi)的貢獻(xiàn)很大,如專(zhuān)指概念。這是χ2統(tǒng)計(jì)的不足之處,它對(duì)低文檔頻的特征項(xiàng)不可靠?；谝陨戏治?考慮特征在各個(gè)類(lèi)別之間的分布情況,建立特征關(guān)于類(lèi)別的χ2分布矩陣。定義如下:從F的構(gòu)造可以看出:F中的每一行反映了特征在不同類(lèi)別中的分布情況,每一列反映了在同一類(lèi)別中不同特征的分布情況。將二者結(jié)合起來(lái),能夠完整反映整個(gè)特征集的分布,而且客觀上彌補(bǔ)了χ2統(tǒng)計(jì)量作為特征選擇方法上的缺點(diǎn)。3類(lèi)別中出現(xiàn)比較頻繁的特征通過(guò)分析每一類(lèi)別上不同特征的χ2分布情況可見(jiàn):一些χ2較大的特征在類(lèi)別中出現(xiàn)頻率極低,而另一些在類(lèi)別中出現(xiàn)比較頻繁的特征χ2反而很小。這種異常的出現(xiàn)正是由于這些特征打破了χ2統(tǒng)計(jì)量基于ti和Cj之間符合具有一階自由度的χ2分布,受整體分布影響較大,需要加以修正。由此,本文為每個(gè)特征引入一個(gè)模糊概念,用云模型對(duì)其在類(lèi)別上的分布進(jìn)行定量描述,將特征對(duì)于類(lèi)別的χ2用相應(yīng)的隸屬度加以修正。3.1云域和云圖中的概念云模型用語(yǔ)言值表示某個(gè)定性概念與其定量表示之間的不確定性,已經(jīng)在智能控制、模糊評(píng)測(cè)等多個(gè)領(lǐng)域得到應(yīng)用。定義1設(shè)U是一個(gè)用數(shù)值表示的定量論域,C是U上定性概念。若定量值x∈U是定性概念C的一次隨機(jī)實(shí)現(xiàn),x對(duì)C的確定度μ(x)∈[,0]1是有穩(wěn)定傾向的隨機(jī)數(shù),μ:U→,?x∈U,x→μ(x),則x在論域U上的分布稱(chēng)為云,記為云C(X)。每一個(gè)x稱(chēng)為一個(gè)云滴。如果概念對(duì)應(yīng)的論域是n維空間,那么可以拓廣至n維云。定義2設(shè)X是一個(gè)普通集合X={x},稱(chēng)為論域。隸屬度在基礎(chǔ)變量上的分布稱(chēng)為云。在對(duì)模糊集的處理過(guò)程中,論域中某一點(diǎn)到它的隸屬度之間的映射是一對(duì)多的轉(zhuǎn)換,不是一條明晰的隸屬曲線,從而產(chǎn)生了云的概念。云用期望Ex(Expectedvalue)、熵En(Entropy)、超熵He(Hyperentropy)這3個(gè)數(shù)字特征來(lái)整體表征一個(gè)概念。期望Ex是云滴在論域空間分布的期望,是最能夠代表定性概念的點(diǎn);熵En代表定性概念的可度量粒度,熵越大,通常概念越宏觀,也是定性概念不確定性的度量,由概念的隨機(jī)性和模糊性共同決定。超熵He是熵的不確定性度量,即熵的熵,由熵的隨機(jī)性和模糊性共同決定。用3個(gè)數(shù)字特征表示的定性概念的整體特征記作C(Ex,En,He),稱(chēng)為云的特征向量。正向云算法和逆向云算法是云模型中2個(gè)最基本、最關(guān)鍵的算法。前者把定性概念的整體特征變換為定量數(shù)值表示,實(shí)現(xiàn)概念空間到數(shù)值空間的轉(zhuǎn)換;后者實(shí)現(xiàn)從定量值到定性概念的轉(zhuǎn)換,將一組定量數(shù)據(jù)轉(zhuǎn)換為以數(shù)字特征{Ex,En,He}來(lái)表示的定性概念。3.2動(dòng)態(tài)聚類(lèi)算法通過(guò)特征χ2分布矩陣,特征的取值不僅反映了特征對(duì)整個(gè)分類(lèi)作用大小,也反映了該特征對(duì)于每一類(lèi)別的貢獻(xiàn)程度。通過(guò)云模型隸屬度函數(shù)的引入,更修正了特征在類(lèi)別中的分布情況。通過(guò)提取每一類(lèi)別隸屬度最高的特征集,合并而成最終的分類(lèi)特征集合,不僅可以保留對(duì)整個(gè)分類(lèi)貢獻(xiàn)最大的特征集,同時(shí)兼顧某些特征集較少(或者在某一類(lèi)中出現(xiàn)頻率大,但總體出現(xiàn)概率低的特征)的類(lèi)別。在對(duì)特征取值進(jìn)行隸屬度表示后,特征在類(lèi)別上的取值表示成了區(qū)間上的連續(xù)值。特征對(duì)類(lèi)別的相關(guān)性越大,其隸屬度越高。但每一類(lèi)別仍包含大量特征,其中很大一部分特征對(duì)于類(lèi)別的隸屬度極低,需要對(duì)特征集進(jìn)行初步篩選,減少特征提取計(jì)算量。定義3一維論域中U中,任一小區(qū)間上的云滴群?x對(duì)定性概念A(yù)的貢獻(xiàn)?C為:由定義3,可以計(jì)算得到U上所有元素對(duì)概念A(yù)的總貢獻(xiàn)C為:基于以上分析,通過(guò)計(jì)算可以得到位于區(qū)間[Ex-0.67En,Ex+0.67En]的特征,占特征總量的22.33%,但它們對(duì)類(lèi)別的貢獻(xiàn)占50%,能夠滿足特征提取需要,故將在此區(qū)間的特征篩選為初選特征集。在特征的提取上,可以采用動(dòng)態(tài)聚類(lèi)方法進(jìn)行處理。但是,在聚類(lèi)過(guò)程中,類(lèi)別個(gè)數(shù)應(yīng)該是與數(shù)據(jù)本身特性有關(guān),而不是一個(gè)經(jīng)驗(yàn)值。因此,采用逐步試探聚類(lèi)類(lèi)別個(gè)數(shù)直至最終滿足聚類(lèi)要求的思路,提出了逐級(jí)動(dòng)態(tài)聚類(lèi)算法。算法1:逐級(jí)動(dòng)態(tài)聚類(lèi)算法。輸入:類(lèi)別向量Ci//即第2節(jié)中χ2分布矩陣F中的列向量。輸出:特征集合Ti。算法步驟:(1)提取Ci中所有不重復(fù)的特征隸屬度以升序構(gòu)成新類(lèi)別向量Ci′={dij,Clusterid},其中Clusterid為聚類(lèi)類(lèi)別編號(hào)。(3)初始類(lèi)別K=1,v=e+1//v為循環(huán)控制變量。(4)WHILE(v>e)DO//當(dāng)v≤e時(shí),各類(lèi)的聚合程度已經(jīng)比較好,聚類(lèi)結(jié)束。1)構(gòu)建中心類(lèi)別表TC:將Ci′平均分成K+1份,取區(qū)間右端點(diǎn)加入TC,作為C′在K情況下的初始類(lèi)別,同時(shí)將Ci′各元素Clusterid置為0;2)設(shè)定臨時(shí)循環(huán)控制變量e1=0;3)當(dāng)e1≠v時(shí),執(zhí)行以下循環(huán)://聚類(lèi)穩(wěn)定后,各類(lèi)的標(biāo)準(zhǔn)差將收斂為穩(wěn)定值。(2)計(jì)算Ci′中每個(gè)值與TC中各類(lèi)別距離,將其歸并到距離最小的類(lèi)別中;(3)根據(jù)加權(quán)平均修正TC中各類(lèi)別的中心距離;(4)計(jì)算TC中各類(lèi)別的標(biāo)準(zhǔn)差Si,令4)K=K+1//聚類(lèi)類(lèi)別數(shù)加1,進(jìn)行下一輪的聚類(lèi)處理。(5)聚類(lèi)結(jié)束,K′=K-1即為聚類(lèi)類(lèi)別數(shù)。編號(hào)為K′的特征為類(lèi)別Ci隸屬度最大的特征集,(6)RETURNTi。算法1的復(fù)雜度分析:設(shè)類(lèi)別Ci上特征的平均個(gè)數(shù)為n,算法時(shí)間復(fù)雜度主要由步驟(4)決定。步驟(4)是一個(gè)典型的k均值聚類(lèi),其時(shí)間復(fù)雜度為O(k×n),因此,步驟(4)的時(shí)間復(fù)雜度為O(k2×n)(其中,k為平均聚類(lèi)個(gè)數(shù))。故算法1的時(shí)間復(fù)雜度為O(k2×n),空間復(fù)雜度為O(n)。在算法1的基礎(chǔ)上,提出了一種云隸屬度下的文本特征自動(dòng)提取算法。該算法不需要指定聚類(lèi)數(shù)目,能根據(jù)特征分布特點(diǎn)自動(dòng)獲取隸屬度高的特征集,具體見(jiàn)算法2。算法2:基于云隸屬度的文本特征自動(dòng)提取算法(FAS)。輸入:特征χ2分布矩陣F,訓(xùn)練集TR。輸出:經(jīng)過(guò)特征選擇后的訓(xùn)練集TR′。算法步驟:初始化特征集T=φ;依次選擇F中每一列Ci,進(jìn)行以下步驟處理:1)運(yùn)用逆向云算法計(jì)算Ci的數(shù)字特征C(Ex,En,He);2)運(yùn)用正向云算法將Ci特征值轉(zhuǎn)化成對(duì)應(yīng)隸屬度;3)將Ci中區(qū)間[Ex-0.67En,Ex+0.67En]外的特征刪除,得到初次約簡(jiǎn)類(lèi)別向量Ci′;4)在Ci′基礎(chǔ)上調(diào)用逐級(jí)動(dòng)態(tài)聚類(lèi)算法(算法1)得到選擇后特征集Ti;6)刪除TR中不屬于T的所有特征項(xiàng),得到選擇處理后訓(xùn)練集TR′。算法2的復(fù)雜度分析:設(shè)訓(xùn)練集類(lèi)別平均特征數(shù)為n,類(lèi)別數(shù)為m,則算法2的時(shí)間復(fù)雜度為O(k2×n×m)(k為平均聚類(lèi)個(gè)數(shù)),空間復(fù)雜度為O(n)。4文本分類(lèi)測(cè)試為了測(cè)試本文算法的有效性,對(duì)FAS算法進(jìn)行橫向?qū)Ρ葴y(cè)試。實(shí)驗(yàn)中,采用性能較好的kNN分類(lèi)器算法(k=30)進(jìn)行文本分類(lèi)測(cè)試。測(cè)試結(jié)果用準(zhǔn)確率(即分類(lèi)正確數(shù)/實(shí)際分類(lèi)數(shù))、查全率(即分類(lèi)正確數(shù)/應(yīng)有數(shù))和宏平均(P為準(zhǔn)確率;R為召回率)進(jìn)行評(píng)測(cè)。4.1pv.0訓(xùn)練集、測(cè)試集的構(gòu)建實(shí)驗(yàn)選用中文語(yǔ)料庫(kù)TanCorpV1.0與英文語(yǔ)料庫(kù)Reuters-21578。TanCorpV1.0包含文本14150篇,共分為12類(lèi)。經(jīng)過(guò)停用詞移除、詞干還原等處理后,得到詞條72584個(gè)。對(duì)于Reuters-21578,使用只有1個(gè)類(lèi)別且每個(gè)類(lèi)別至少包含5個(gè)以上的文檔。這樣,得到訓(xùn)練集5273篇、測(cè)試集1767篇。經(jīng)過(guò)停用詞移除、詞干還原等處理后,得到13961個(gè)詞條。4.2fp3算法在reunths-1263-2000上的分類(lèi)性能比較現(xiàn)有特征選擇方法通常采用經(jīng)驗(yàn)方式來(lái)確定特征數(shù)目,為了得到各特征選擇方法在達(dá)到最佳分類(lèi)性能時(shí)的特征數(shù),采用了逐步增加特征數(shù)的方法來(lái)確定。測(cè)試結(jié)果如表1和2所示。從表1和2可以看出:IG和CHI方法隨著特征數(shù)的增加,分類(lèi)性能提升較快,而MI方法需要的特征數(shù)則較多,性能提升緩慢。同時(shí),當(dāng)特征數(shù)達(dá)到某個(gè)閾值時(shí),各特征選擇方法性能均會(huì)達(dá)到最佳狀態(tài)。但此閾值的獲取因特征選擇方法的不同、語(yǔ)料庫(kù)的差異而各有不同,需要大量實(shí)驗(yàn)才能得到。而使用FAS算法在TanCorpV1.0上自動(dòng)提取的特征數(shù)平均為1380個(gè),在Reuters-21578上自動(dòng)提取的特征數(shù)平均為239個(gè),不僅不需要任何經(jīng)驗(yàn)知識(shí),而且特征數(shù)明顯少于已有特征選擇方法的特征數(shù)。將FAS算法選擇的特征集進(jìn)行分類(lèi)測(cè)試,性能比較結(jié)果見(jiàn)表3和4。從表3和4可以看出:與IG,CHI和MI這3種算法相比,FAS算法提取的特征集具有個(gè)數(shù)少、分類(lèi)精度高的特點(diǎn)。kNN方法在TanCorpV1.0上的最好宏平均(F1=84.78%)與Reuters-21578上的最好宏平均(F1=86.1%)相比,基于FAS算法提取特征集上,kNN方法宏平均提高了5%~6%,說(shuō)明該算法提取的特征集具有比較高的類(lèi)別描述能力。從分類(lèi)的時(shí)間開(kāi)銷(xiāo)來(lái)看