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

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

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

0 引言

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

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

1 相關工作

1.1 文本特征處理

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

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

1.2 小波分析

小波分析能有效地從非平穩信號中提取出有用信息，從根本上克服了傅立葉分析只能以單個變量描述信號的缺點[9]。小波分析在信號分析、神經網絡、模式識別、語音合成、方程求解等方面取得了重要成果。小波變換可以起到壓縮數字信號的作用: 小波變換后數據可以截斷，僅存放小部分最強的小波系數，就能保留近似的壓縮數據[10]。常見小波函數有Haar小波，Mexican hat小波，Morelet小波，Daubechies小波等[11]。

1.3 文本分類

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

1.4 壓縮感知

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

2 基本理論

2.1 TF-IDF特征提取方法

單詞權重計算最為有效的實現方法是TF-IDF，它是Salton在1988年提出的。它的計算如式(1)所示。

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

(1)

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

2.2 Mallat算法

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

(2)

重構式子表示為式(3):

(3)

信號的小波分解和重建可通過子帶濾波的形式來實現[15]。

2.3 KNN法

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

(4)

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

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

2.4.1 相關理論分析

向量空間模型簡化了文本處理，不同詞語之間的組合可能會達到它們排列的效果。但其缺點是隨著文本集擴充、詞典單詞增多，向量維度會迅速增加。單個文本向量很難占有詞典里的大部分詞，故有很多維度權重值為0，產生了向量的高維度、稀疏性現象。因此我們需要對傳統向量空間模型中的向量進行降維處理，可以把文本向量看成數字信號。而小波分析理論對數字信號處理具有很強的優勢。現有的理論和實踐表明，變換后的數字信號能高度還原到原始信號，且小波分析能獨到地捕捉到局部化細節，這就使在小波變換空間進行本文操作變成了可能。

本文的小波變換是將一維離散小波變換產生的低頻向量和高頻向量進行了對應分量的簡性相加。一維離散小波變換后的低頻和高頻向量維度相同且約為原始向量的一半，因此達到了降維目的。這可解釋為我們在分析語言內容時會從正向和反向進行理解。低頻信息類比于我們的正向理解，這在整體理解上確實占了很大比重；高頻信息類比于我們對語言內容的反向理解，相應地所占比重小。正向加反向理解便是我們對語言內容的整體把握。在小波空間比重不同，但是實際上比例應該一致，故本文進行的逆小波變換是采用尺度函數對高頻信息和低頻信息進行變換再進行簡性相加。更進一步解釋，信號一般都符合高斯分布，所以本文的逆小波變換提取了上述變換的中間若干維，從而達到降維的目的。

2.4.2 小波分析法對特定分類類別的優勢

本文對特定訓練集進行了相關統計:

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

(5)

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

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

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

Step1對數據集進行分詞，構建出詞典，獲得TF-IDF特征空間向量;

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

Step3對尺度系數和小波系數進行對應分量相加，得到本文提出的小波空間各向量；

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

Step5利用測試文本計算在兩類空間下進行KNN分類的相似性；

Step6比較所有測試向量判定標簽和其真實所屬標簽，計算準確率。

3 實驗部分

本文分類實驗是為了驗證特定分類組的實驗準確率，故對于每個特定分類組的實驗沒有摻雜負樣本。

3.1 實驗過程

采用中國科學院NLPIR分詞系統對數據集進行分詞。使用SVD方法、ICA方法、PCA方法、本文DWT小波變換方法、本文IDWT逆小波變換方法對向量空間VSM下的特征向量(TF-IDF)分別進行降維特征提取。再使用KNN方法(余弦距離作為相似性度量標準)對各個空間進行分類，測得各空間的分類準確率。由于前期所做文本實驗發現選用DB20小波、K=8時優于同水平實驗結果，故本文實驗參數亦如此設定。SVD空間、ICA空間、PCA空間、IDWT空間的維度一致。

本文共進行兩大組實驗。第一組實驗測試各訓練空間針對內部樣本時的分類性能(測試集和訓練集來自同一樣本集)；選用復旦大學新聞組語料庫，該語料庫包含20個類別、9 804篇文本。舍去英文單詞、標點符號、數字、部分停用詞、極低頻詞，獲得特征詞共計27 950個。每類中的文本數如表1所示。

表1 各類別文本數

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

第二組實驗驗證本文提出的小波分析法在外來樣本中的優越性: 選用數據堂網站新聞組語料庫，該語料庫包含10個類別、2 815篇文本。在每個類別中隨機抽出10篇，其余作為訓練集。在訓練集中舍去英文單詞、標點符號、數字、部分停用詞、極低頻詞，獲得特征詞即詞典單詞數D共計9 700個。SVD、ICA、PCA、IDWT空間的維度為2 000。表2是統計出的具體信息。

表2 訓練集的統計信息

該組實驗選取復旦新聞組語料庫中的對應新聞類，進行各空間中各類別的分類實驗。

3.2 實驗結果及分析

以第一組實驗的實驗條件和實驗結果形成表3。橫向表頭代表各個訓練空間，縱向表頭代表上文所隨機抽取的VSM向量的在每組SVD、ICA、PCA、IDWT空間降維后的維度數。分類準確率(單位: %)相關結果如下。

表3 內部樣本下各類特征提取方法的文本分類

續表

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

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

以第二組實驗條件和實驗結果形成表4。分類準確率(單位: %)結果如下所示。

表4 外來大樣本下各類特征提取方法的文本分類

續表

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

綜上發現: (1) DWT空間能降低高稀疏、高維的VSM空間近一半的維度，且分類準確率在各個實驗環境下基本與VSM空間保持一致，這是因為本文的小波變換能保留下VSM空間的重要分類特征，故其與VSM空間的分類誤差較小，但其降維尺度固定，基本為VSM空間的一半；

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

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

4 結束語

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