基于小波分析的特征提取文本分類方法研究

朱 晉,懷麗波,崔榮一,尹 慧

(1. 延邊大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 智能信息處理研究室，吉林 延吉 133002) (2. 延邊大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 延吉 133002)

0 引言

文本分類是分析待定文本的特征,并與已知類別中文本所具有的共同特征進(jìn)行比較,然后將待定文本劃歸為特征最接近的一類并賦予相應(yīng)的分類號(hào)[1-2]。通常用一組詞條作為屬性向量構(gòu)成特征向量空間。文本的原始特征向量空間包含全部的詞條屬性，具有高維、稀疏的特點(diǎn)，但并不是所有屬性對(duì)分類決策都有貢獻(xiàn)，冗余的屬性不但對(duì)決策無(wú)任何貢獻(xiàn)，反而會(huì)降低決策的執(zhí)行效率。因此需要在不降低系統(tǒng)性能的前提下，對(duì)高維文本特征空間進(jìn)行有效地降維，提取出最佳分類特征屬性集合[3]。

數(shù)據(jù)壓縮一直是小波分析的重要應(yīng)用領(lǐng)域之一，并由此帶來(lái)了巨大的社會(huì)效益和經(jīng)濟(jì)效益[4]。本文對(duì)向量空間模型下的特征向量進(jìn)行了本文的小波變換、逆小波變換，使文本特征空間維度有所減小，期望達(dá)到提取文本特征、進(jìn)行有效文本分類的目的。

1 相關(guān)工作

1.1 文本特征處理

文本表示一般采用向量空間模型，該模型是由G.Salton提出的[5]。該模型不考慮詞的順序，將文本簡(jiǎn)化為一個(gè)BOW(Bag-of-Words)，并表示為特征權(quán)重的向量。除此之外的文本表示有基于高階詞統(tǒng)計(jì)、基于特征概率分布、將文本理解為信號(hào)序列、二維視圖等模型，但應(yīng)用都十分局限[6]。向量空間模型主要以詞作為特征，以詞頻矩陣為基礎(chǔ)計(jì)算權(quán)重。常用的特征提取方法有文檔頻率、信息增益、互信息、卡方檢驗(yàn)、期望交叉熵、TF-IDF方法和特征降維[7]等。

現(xiàn)有的特征降維技術(shù)很多: 停用詞表，停用詞的區(qū)別作用不大，從詞典里去掉停用詞可以達(dá)到降維目的，但現(xiàn)今停用詞表依舊不夠健全完善且特殊情況下停用詞對(duì)提取一篇文檔的特征還是有作用的；獨(dú)立成分分析(ICA)，用ICA將輸入文本空間映射到相應(yīng)的獨(dú)立成分空間，這種方法產(chǎn)生的計(jì)算空間小[2]；主成分分析(PCA)，將高維的詞語(yǔ)特征—文檔空間轉(zhuǎn)換為一個(gè)低維度的正交矩陣，從中選擇最有辨別能力的特征，最終得到最佳的分類特征子集[3]；奇異值分解(SVD),使用 SVD 對(duì)特征文本矩陣進(jìn)行降維，解決了同義詞和多義詞問(wèn)題，降低了文本分類的計(jì)算量[8]。

1.2 小波分析

小波分析能有效地從非平穩(wěn)信號(hào)中提取出有用信息，從根本上克服了傅立葉分析只能以單個(gè)變量描述信號(hào)的缺點(diǎn)[9]。小波分析在信號(hào)分析、神經(jīng)網(wǎng)絡(luò)、模式識(shí)別、語(yǔ)音合成、方程求解等方面取得了重要成果。小波變換可以起到壓縮數(shù)字信號(hào)的作用: 小波變換后數(shù)據(jù)可以截?cái)?，僅存放小部分最強(qiáng)的小波系數(shù)，就能保留近似的壓縮數(shù)據(jù)[10]。常見(jiàn)小波函數(shù)有Haar小波，Mexican hat小波，Morelet小波，Daubechies小波等[11]。

1.3 文本分類

自從20世紀(jì)90年代開(kāi)始，文本分類主要為基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方法，這種方法相對(duì)于知識(shí)工程方法，在準(zhǔn)確率和穩(wěn)定性方面都有明顯的優(yōu)勢(shì)。在構(gòu)建分類器過(guò)程中，分類器是自動(dòng)建立的，分為學(xué)習(xí)過(guò)程和分類過(guò)程，學(xué)習(xí)過(guò)程是基于訓(xùn)練集學(xué)習(xí)到一個(gè)分類器，而分類過(guò)程則是利用學(xué)習(xí)到的分類器預(yù)測(cè)新數(shù)據(jù)的類別。整個(gè)過(guò)程不需要專家參與，分類的時(shí)間開(kāi)銷和人力投入都很少，準(zhǔn)確率卻得到了提高。研究人員嘗試了大量的機(jī)器學(xué)習(xí)算法，包括: 支持向量機(jī)、樸素貝葉斯、KNN、決策樹、Rocchio、最大熵模型[12]等。

1.4 壓縮感知

壓縮感知理論首先由Candès、Romberg、Tao和Donoho等人在2004年提出,文獻(xiàn)直到2006年才發(fā)表。Candès證明了只要信號(hào)在某一個(gè)正交空間具有稀疏性,就能以較低的頻率采樣信號(hào),而且能以高概率重構(gòu)該信號(hào)[13]。壓縮感知理論可以高效地采集稀疏信號(hào)的信息,通過(guò)非相關(guān)性感知測(cè)量值,此特性使得壓縮感知廣泛地應(yīng)用于現(xiàn)實(shí)生活中。壓縮感知理論解決了信息采集和處理技術(shù)目前遇到的瓶頸,帶來(lái)了革命性的突破,受到各國(guó)學(xué)者的廣泛關(guān)注,從醫(yī)學(xué)成像和信號(hào)編碼到天文學(xué)和地球物理學(xué)均有應(yīng)用[14]。

2 基本理論

2.1 TF-IDF特征提取方法

單詞權(quán)重計(jì)算最為有效的實(shí)現(xiàn)方法是TF-IDF，它是Salton在1988年提出的。它的計(jì)算如式(1)所示。

W(ti,dj)=tf(ti,dj)×idf(ti,d)

(1)

其中,W(ti,dj)是特征項(xiàng)ti在文本dj的權(quán)重取值;tf(ti,dj)是特征項(xiàng)ti在文本dj中出現(xiàn)的頻率，用于計(jì)算該詞描述文檔內(nèi)容的能力;idf(ti,d)是特征項(xiàng)ti在文本集d中出現(xiàn)文本頻率數(shù)的反比，稱為反文檔頻率，用于計(jì)算該詞區(qū)分文檔的能力。TF-IDF法認(rèn)為一個(gè)單詞出現(xiàn)的文本頻率越小，它區(qū)別不同類別的能力就越大，所以引入了反文本頻度IDF的概念，以TF和IDF的乘積作為特征空間坐標(biāo)系的取值測(cè)度[3]。

2.2 Mallat算法

Mallat于1987年把多分辨率思想引入小波分析中，提出了塔式分解算法，即Mallat算法,該算法在實(shí)際應(yīng)用中減少了小波變換的復(fù)雜度。分解式子可表示為式(2):

(2)

重構(gòu)式子表示為式(3):

(3)

信號(hào)的小波分解和重建可通過(guò)子帶濾波的形式來(lái)實(shí)現(xiàn)[15]。

2.3 KNN法

KNN分類算法能夠確定待分類樣本與訓(xùn)練樣本之間的相似程度，從而確定與待分類樣本距離最近的 K個(gè)訓(xùn)練樣本。其最關(guān)鍵的因素是相似性度量方法，最常用的相似性度量方法是余弦相似度，如式(4)所示。

(4)

其中，X,Y代表兩個(gè)文檔表示向量。對(duì)于一個(gè)待分類文本x,根據(jù)相似性度量函數(shù)從整個(gè)訓(xùn)練集中找到與文本x最相似的K(K是預(yù)先設(shè)定的一個(gè)整數(shù))個(gè)文本，然后根據(jù)K個(gè)近鄰文本所屬的類別給x的候選類別評(píng)分[16]。

2.4 基于小波分析的文本特征提取方法

2.4.1 相關(guān)理論分析

向量空間模型簡(jiǎn)化了文本處理，不同詞語(yǔ)之間的組合可能會(huì)達(dá)到它們排列的效果。但其缺點(diǎn)是隨著文本集擴(kuò)充、詞典單詞增多，向量維度會(huì)迅速增加。單個(gè)文本向量很難占有詞典里的大部分詞，故有很多維度權(quán)重值為0，產(chǎn)生了向量的高維度、稀疏性現(xiàn)象。因此我們需要對(duì)傳統(tǒng)向量空間模型中的向量進(jìn)行降維處理，可以把文本向量看成數(shù)字信號(hào)。而小波分析理論對(duì)數(shù)字信號(hào)處理具有很強(qiáng)的優(yōu)勢(shì)?，F(xiàn)有的理論和實(shí)踐表明，變換后的數(shù)字信號(hào)能高度還原到原始信號(hào)，且小波分析能獨(dú)到地捕捉到局部化細(xì)節(jié)，這就使在小波變換空間進(jìn)行本文操作變成了可能。

本文的小波變換是將一維離散小波變換產(chǎn)生的低頻向量和高頻向量進(jìn)行了對(duì)應(yīng)分量的簡(jiǎn)性相加。一維離散小波變換后的低頻和高頻向量維度相同且約為原始向量的一半，因此達(dá)到了降維目的。這可解釋為我們?cè)诜治稣Z(yǔ)言內(nèi)容時(shí)會(huì)從正向和反向進(jìn)行理解。低頻信息類比于我們的正向理解，這在整體理解上確實(shí)占了很大比重；高頻信息類比于我們對(duì)語(yǔ)言內(nèi)容的反向理解，相應(yīng)地所占比重小。正向加反向理解便是我們對(duì)語(yǔ)言內(nèi)容的整體把握。在小波空間比重不同，但是實(shí)際上比例應(yīng)該一致，故本文進(jìn)行的逆小波變換是采用尺度函數(shù)對(duì)高頻信息和低頻信息進(jìn)行變換再進(jìn)行簡(jiǎn)性相加。更進(jìn)一步解釋，信號(hào)一般都符合高斯分布，所以本文的逆小波變換提取了上述變換的中間若干維，從而達(dá)到降維的目的。

2.4.2 小波分析法對(duì)特定分類類別的優(yōu)勢(shì)

本文對(duì)特定訓(xùn)練集進(jìn)行了相關(guān)統(tǒng)計(jì):

4) 某類別綜合因子Si, 自定義表達(dá)式如式(5)所示。

(5)

其中，n為訓(xùn)練集的文本類別總數(shù)，T為訓(xùn)練集總文本數(shù)，D是詞典中單詞數(shù)。

根據(jù)壓縮感知理論，正交、高稀疏空間的信號(hào)進(jìn)行變換會(huì)以高概率還原到原始信號(hào)。本文中DWT空間符合初始條件: 1)正交的DBN小波； 2)高稀疏: 后期測(cè)得小波空間低頻部分、高頻部分的零值過(guò)半的向量均占了各自總向量的90%以上，某類別的稀疏程度可由上文提到的類別綜合因子描述。所以在做本文提出的逆變換后有機(jī)會(huì)還原出原始信號(hào)的重要部分。類綜合因子作為本文逆小波變換特定分類優(yōu)勢(shì)的判斷標(biāo)準(zhǔn)。

通過(guò)以上分析，本文對(duì)向量空間模型進(jìn)行了本文采用的DWT、IDWT方法，用文本分類的準(zhǔn)確程度檢驗(yàn)該文本特征提取方法的有效性。以下是算法步驟:

Step1對(duì)數(shù)據(jù)集進(jìn)行分詞，構(gòu)建出詞典，獲得TF-IDF特征空間向量;

Step2利用式(2)等對(duì)已獲得的TF-IDF向量進(jìn)行一維離散小波變換，得到尺度系數(shù)和小波系數(shù)；

Step3對(duì)尺度系數(shù)和小波系數(shù)進(jìn)行對(duì)應(yīng)分量相加，得到本文提出的小波空間各向量；

Step4對(duì)Step 3得到的尺度系數(shù)和小波系數(shù)均利用式(3)進(jìn)行對(duì)應(yīng)的尺度函數(shù)還原再相加，對(duì)得到的向量提取其中間若干維度，獲得本文提出的逆小波空間各向量；

Step5利用測(cè)試文本計(jì)算在兩類空間下進(jìn)行KNN分類的相似性；

Step6比較所有測(cè)試向量判定標(biāo)簽和其真實(shí)所屬標(biāo)簽，計(jì)算準(zhǔn)確率。

3 實(shí)驗(yàn)部分

本文分類實(shí)驗(yàn)是為了驗(yàn)證特定分類組的實(shí)驗(yàn)準(zhǔn)確率，故對(duì)于每個(gè)特定分類組的實(shí)驗(yàn)沒(méi)有摻雜負(fù)樣本。

3.1 實(shí)驗(yàn)過(guò)程

采用中國(guó)科學(xué)院NLPIR分詞系統(tǒng)對(duì)數(shù)據(jù)集進(jìn)行分詞。使用SVD方法、ICA方法、PCA方法、本文DWT小波變換方法、本文IDWT逆小波變換方法對(duì)向量空間VSM下的特征向量(TF-IDF)分別進(jìn)行降維特征提取。再使用KNN方法(余弦距離作為相似性度量標(biāo)準(zhǔn))對(duì)各個(gè)空間進(jìn)行分類，測(cè)得各空間的分類準(zhǔn)確率。由于前期所做文本實(shí)驗(yàn)發(fā)現(xiàn)選用DB20小波、K=8時(shí)優(yōu)于同水平實(shí)驗(yàn)結(jié)果，故本文實(shí)驗(yàn)參數(shù)亦如此設(shè)定。SVD空間、ICA空間、PCA空間、IDWT空間的維度一致。

本文共進(jìn)行兩大組實(shí)驗(yàn)。第一組實(shí)驗(yàn)測(cè)試各訓(xùn)練空間針對(duì)內(nèi)部樣本時(shí)的分類性能(測(cè)試集和訓(xùn)練集來(lái)自同一樣本集)；選用復(fù)旦大學(xué)新聞組語(yǔ)料庫(kù)，該語(yǔ)料庫(kù)包含20個(gè)類別、9 804篇文本。舍去英文單詞、標(biāo)點(diǎn)符號(hào)、數(shù)字、部分停用詞、極低頻詞，獲得特征詞共計(jì)27 950個(gè)。每類中的文本數(shù)如表1所示。

表1 各類別文本數(shù)

分別隨機(jī)抽取樣本集的13/19、11/17、7/13、1/2、1/3、1/5、1/7作為測(cè)試集，剩余作為訓(xùn)練集，先進(jìn)行各類空間的轉(zhuǎn)化(每組SVD、ICA、PCA、IDWT降維尺度由每個(gè)ICA訓(xùn)練集的最多有效主元個(gè)數(shù)決定)，再進(jìn)行共計(jì)7次各空間分類實(shí)驗(yàn)。

第二組實(shí)驗(yàn)驗(yàn)證本文提出的小波分析法在外來(lái)樣本中的優(yōu)越性: 選用數(shù)據(jù)堂網(wǎng)站新聞組語(yǔ)料庫(kù)，該語(yǔ)料庫(kù)包含10個(gè)類別、2 815篇文本。在每個(gè)類別中隨機(jī)抽出10篇，其余作為訓(xùn)練集。在訓(xùn)練集中舍去英文單詞、標(biāo)點(diǎn)符號(hào)、數(shù)字、部分停用詞、極低頻詞，獲得特征詞即詞典單詞數(shù)D共計(jì)9 700個(gè)。SVD、ICA、PCA、IDWT空間的維度為2 000。表2是統(tǒng)計(jì)出的具體信息。

表2 訓(xùn)練集的統(tǒng)計(jì)信息

該組實(shí)驗(yàn)選取復(fù)旦新聞組語(yǔ)料庫(kù)中的對(duì)應(yīng)新聞?lì)?，進(jìn)行各空間中各類別的分類實(shí)驗(yàn)。

3.2 實(shí)驗(yàn)結(jié)果及分析

以第一組實(shí)驗(yàn)的實(shí)驗(yàn)條件和實(shí)驗(yàn)結(jié)果形成表3。橫向表頭代表各個(gè)訓(xùn)練空間，縱向表頭代表上文所隨機(jī)抽取的VSM向量的在每組SVD、ICA、PCA、IDWT空間降維后的維度數(shù)。分類準(zhǔn)確率(單位: %)相關(guān)結(jié)果如下。

表3 內(nèi)部樣本下各類特征提取方法的文本分類

續(xù)表

當(dāng)測(cè)試集減少到一定階段之前(本組實(shí)驗(yàn)中是原始數(shù)據(jù)集的1/5)，訓(xùn)練集會(huì)增長(zhǎng)到一定程度，測(cè)試樣本能充分利用訓(xùn)練集，多個(gè)空間的分類準(zhǔn)確率整體呈增長(zhǎng)趨勢(shì)；當(dāng)減少到某一閾值后，訓(xùn)練集的類別多樣性趨于穩(wěn)定、可利用率變低，導(dǎo)致分類誤差越來(lái)越大?？傮w來(lái)看,傳統(tǒng)的VSM空間分類準(zhǔn)確率已有一個(gè)很高的水平；DWT空間在維度降為VSM空間維度的一半后仍能和VSM空間的分類準(zhǔn)確率保持一致(平均分類誤差0.2%)；IDWT空間在從原始29 750維降到相應(yīng)低維度，有效避免了維度災(zāi)難的發(fā)生，卻也付出了分類準(zhǔn)確率降低的代價(jià)，同時(shí)可以看出，隨著本文訓(xùn)練集的增加，IDWT空間的分類準(zhǔn)確率呈直線增長(zhǎng)，這說(shuō)明該空間前文所提閾值上限要高于其他空間；SVD、ICA、PCA空間不但在維度上銳減，而且在分類準(zhǔn)確率上亦有個(gè)好的效果，和VSM空間的平均分類誤差為0.30%、-0.02%、-0.001%。

值得一提的是，SVD、ICA、PCA方法能有效提取訓(xùn)練樣本最具有分類效果的特征(去除冗余特征)。但這些降維特征提取方法嚴(yán)重依賴于訓(xùn)練集的特性，所以會(huì)有偏差: 如某特征在訓(xùn)練集中是重要分類特征，但隨著樣本的增多，可能就發(fā)現(xiàn)是冗余特征。而小波分析空間先于訓(xùn)練集的存在，故魯棒性較強(qiáng)。這在下組實(shí)驗(yàn)中有所體現(xiàn)。

以第二組實(shí)驗(yàn)條件和實(shí)驗(yàn)結(jié)果形成表4。分類準(zhǔn)確率(單位: %)結(jié)果如下所示。

表4 外來(lái)大樣本下各類特征提取方法的文本分類

續(xù)表

該表是在大樣本測(cè)試集下進(jìn)行分類所得結(jié)果。綜合分類準(zhǔn)確率規(guī)律基本沿襲之前實(shí)驗(yàn)體現(xiàn)出的結(jié)果。但在交通類新聞中VSM空間分類準(zhǔn)確率最高，SVD空間、ICA空間、PCA空間低于VSM空間的分類準(zhǔn)確率，這也驗(yàn)證了SVD、ICA、PCA方法依賴于訓(xùn)練集的特性；體育類、政治類新聞的分類準(zhǔn)確率IDWT空間最高，由表2發(fā)現(xiàn)這兩類的類綜合因子都很高(均大于等于0.005 5);IDWT空間分類準(zhǔn)確率較低的其他新聞?lì)惖念惥C合因子也都很低。在SVD、ICA、VSM、PCA、DWT空間中具有特征不足、特征值小的政治類向量(參考表2)會(huì)在這幾個(gè)空間的分類準(zhǔn)確率低。政治類和體育類平均能提高VSM空間的約8.5%準(zhǔn)確率。

綜上發(fā)現(xiàn): (1) DWT空間能降低高稀疏、高維的VSM空間近一半的維度，且分類準(zhǔn)確率在各個(gè)實(shí)驗(yàn)環(huán)境下基本與VSM空間保持一致，這是因?yàn)楸疚牡男〔ㄗ儞Q能保留下VSM空間的重要分類特征，故其與VSM空間的分類誤差較小，但其降維尺度固定，基本為VSM空間的一半；

(2) IDWT空間在類綜合因子大的條件下具有明顯的分類優(yōu)勢(shì)，能在很低維度下超越實(shí)驗(yàn)中其他典型空間特定類別的分類準(zhǔn)確率。

此外，同多數(shù)特征降維方法相比，小波分析方法不嚴(yán)重依賴于樣本的統(tǒng)計(jì)特征，尤其是本文的逆小波變換方法，且小波分析方法只涉及卷積運(yùn)算(如SVD、ICA、PCA方法需要矩陣運(yùn)算)，所以在實(shí)現(xiàn)難易程度上亦有所區(qū)別。

4 結(jié)束語(yǔ)

本文提出了一種基于小波分析的特征提取文本分類方法。實(shí)驗(yàn)表明本文提出的小波空間在各個(gè)環(huán)境中同傳統(tǒng)向量空間下的分類誤差基本一致，且能減少向量空間近一半的維度；本文提出的逆小波空間在特定條件下能對(duì)特定分類類別有更高的準(zhǔn)確率，低維下很多特征提取方法會(huì)丟失掉分類重要特征，而根據(jù)壓縮感知理論可知，高稀疏正交的本文小波空間向量能有高概率還原出最原始特征向量的重要特征部分。接下來(lái)的工作有檢驗(yàn)小波分析法的特征提取效率是否在實(shí)驗(yàn)中具有一定優(yōu)勢(shì)，如何擴(kuò)大本文逆小波空間的特定條件使其特定優(yōu)勢(shì)更大化。