基于散度差準則的文本特征降維研究

摘 要：研究了一種基于散度差準則的文本特征抽取方法。首先討論了文本分類中特征降維的主要方法及其特點，然后分析了一種基于散度差的準則用于特征降維的原理和方法，從理論上對該方法的相關步驟進行了數學論證。在中文文本分類實驗中，對KNN分類器進行了基于密度的改進，消除了由于文本分布傾斜對分類器產生的影響。實驗結果表明，這種方法在文本分類的準確性方面效果較為理想。

關鍵詞：文本分類；特征選擇；特征抽取；特征降維；散度差；KNN分類器

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695(2008)07-1971-03



Research of reducing text feature based on scatter difference criterion

LIU Haifenga，b，WANG Yuanyuana，ZHANG Xuerenb ，LIU Shoushengb(a.Institute of Command Automation，b.Institute of Sciences， PLA University of Science Technology， Nanjing 210007， China)

Abstract:The paper studied a method of extracting text feature based on scatter difference.Firstly，analyzed the primary feature reduction means and their characteristic in text classification. Secondly，analyzed the principle and its method that based on scatter difference criterion. And more，the paperdemonstrated the validity about the main approaches of this method. Lastly，had a test about Chinese text categorization with this way.It improved the KNN classifier in the density factor to eliminate thedata incline disadvantage. The result shows that this method has a better precision.

Key words:text classification;feature selection;feature extraction;feature reduction;scatter difference;KNN classifier



文本自動分類是指在給定的分類體系下，對未知類別的文本根據其特征自動判斷類別歸屬的過程。作為機器學習技術與信息處理技術相互滲透、彼此交融的研究領域，文本自動分類技術在自然語言處理及模式識別等領域的應用日益廣泛，在提高信息利用的有效性和準確性上具有重要的現實意義。基于機器學習的中文文本分類方法相比早期的基于知識工程或專家系統的文本分類模式在分類效果、方法靈活性、擴展性等方面均有所突破^[1]；在特征選擇、文本表示、分類器性能評價、自反饋系統設計以及分類效果評估等方面均不同程度地得到發展。文本分類過程主要分為三個步驟，即文本的表示、特征降維和文本分類器構造。文本的表示是指使用恰當的文本表示模型將以字符串形式出現的文本轉換為分類算法能夠處理的形式，向量空間模型是主要的表現模式。訓練集樣本量大、類別分布不均以及文本特征的高維性是文本分類的顯著特點。尋找有效的特征降維方法是提高文本分類效率的關鍵因素之一。針對不同的文本分布情況選擇合適的分類器可以提高分類效率。

1 文本分類中特征降維的主要方法

總的說來，特征降維的目的是收集或提取原始特征集中的統計信息，以提煉后的信息表示文本。特征降維方法主要可分為特征選擇和特征抽取兩種途徑，從兩個不同的角度對文本特征維數進行壓縮，兩種方法在降維效果上各有特點，同時也有各自的不足。

1．1 特征選擇模式及其相關方法

特征選擇是使用某個評價標準獨立對原始特征項逐一評分，然后從中選出分值最高的前k個特征項，其結果是得到原始特征集的一個子集，本質上是對特征集合的約簡。常用于特征選擇的方法主要有文本頻度(document frequency， DF)、信息增益(information gain， IG)、互信息(multiinformation， MI)、χ2(Chisquare)統計、期望交叉熵(expected cross entropy， ECE)、特征熵(term entropy， TE)、特征權(term strength， TS)、幾率比(odds ratio， OR)等模型^[2]。特征選擇方法因為評分模型構造相對簡單、易于理解而得到廣泛應用。但是該方法存在一些不足：a)該模型沒有或是很少考慮特征項之間的相關性信息；b)對一些特征項賦予的權值大小與其對文本分類作用未必有相應的同步關系，對于數據偏斜嚴重的樣本集這個問題尤為突出^[3]。也就是說，特征選擇方法確定的高權特征在不同類別文本的類屬判定上未必體現出相應的重要性。Cover指出^[4]，即使假定各個原始特征之間相互獨立，利用一定的最優準則得到的各個最優特征構成的特征子集未必就是最優特征子集。在這個方面特征抽取模式彌補了特征選擇方法在特征間相關性度量方面的不足。

1．2 特征抽取模式的主要思想及相關方法

特征抽取實際是尋找一個合適的映射，將高維的原始特征空間數據投影到低維的像特征空間φ:x→y，Rn→Rd。其中：d＜n；x為原始向量；y為x在φ下的像。

以此獲得原始特征集相應的像集，借助低維的像特征對文本進行表示。其本質是完成Rn到Rd之間的變換^[5]。常用的特征抽取方法有基于線性的Fisher鑒別準則^[6，7]、主成分分析(principal component analysis， PCA)^[8]、因子分析(factor analysis，FA)、潛在語義分析（latent semantic analysis，LSA）等^[9]。而非線性的特征抽取主要有基于自組織映射(self organizing maps，SOM)、基于核的主成分分析和鑒別分析等。特征抽取得到的特征含有特征項之間的語義信息、相關性信息，是對原始特征集在特征相關性層面的壓縮。

1．3 基于散度差準則的特征抽取原理與方法

設Ci(i=1，2，…，r)表示訓練文本集中的文本類別，Ci內的文本數為ni（i=1，2，…，r）；N=rk=1ni為訓練集中的文本數，xij=(wij，1，wij，2，…，wij，n)表示類Ci中第j個文本（i=1，2…，r；j=1，2，…，nj；wij，p表示特征項Tp在文本xij中的權重）。

定義訓練集的類內散布矩陣Sw、類間散布矩陣分別為相應樣本的協方差矩陣^[6]：

其中:i=(1/ni)nij=1xij為第i類樣本均值；=(1/N)ri=1nij=1xij為總體樣本均值；p(Ci)為第i類樣本出現的概率。這里以該類文本的頻率計算p(Ci)=ni/N，因此式（1）（2）改寫為

由定義知，上述矩陣均為半正定矩陣。

訓練文本類間散度反映了類別樣本之間差異的平均，類間散度大說明不同類別樣本之間平均間距大；而類內散度反映了類內樣本之間密集程度，類內散度小意味著同一類別的樣本之間密集程度高。類間散度和類內散度從兩個側面反映了樣本的可分性。因此對文本進行分類應遵循的原則是應使得類內樣本的分散程度最小而類間樣本的分散程度最大，為此取函數

φ(y)=(yTSby)/(yTSwy)（5）

達到最大值時相應的方向y作為樣本的投影方向。這就是著名的Fisher鑒別準則。

其思想是使得xij在y方向上投影后的類間離散度最大而類內離散度最小。但是，當類內散布矩陣Sw奇異時，式（5）無法使用。為此，借鑒Fisher準則的分類思想，可以考慮使用散度差^[11，12]作為特征抽取的準則：

這里取y為單位向量是為了消除向量長度不同對最佳投影方向判定的影響。參數β1、β2的作用是用來調節類間散度和類內散度在不同類別分布情況下對特征抽取的影響力。

當訓練文本集的類別樣本分布比較平均時，相對于類內散度而言，應加大類間散度對特征抽取效率影響程度，此時應該調大β1；而當訓練文本集的類別樣本分布不均即出現數據傾斜時，應該加大類內散布矩陣Sw對式（6）的影響，故此時可調高β2。本文實驗中取β1=10，β2=3。式（6）這一準則實質上是一種根據樣本分布的不同情況而對類間散度和類內散度在文本分類作用的一種平衡。

通常情況下，由于訓練集的文本數以及文本類別數目均較大，單一的最優投影方向很難滿足大樣本分類要求，為此可以尋找一組正交的單位投影向量q1，q2，…，qt構成最優投影矩陣Q，使得相應準則函數J=QT(β1Sb-β2Sw)Q取最大值。

首先研究矩陣的一些性質。

由于A為實對稱的Hermite陣，故有^[13]：

性質1 A的特征值均為實數。記λ1≥λ2≥…≥λn為A的n個特征值。

性質2 A的相異特征值對應的特征向量必定正交。

引理1^[14] 設σ為對稱變換，V是σ的不變子空間，則V的正交補V⊥也是σ的不變子空間。

關于矩陣A的特征值與特征向量，有如下聯系：

定理 對于實對稱的Hermite矩陣A，存在n階正交矩陣T，使得

其中：T為由特征值λ1，λ2，…，λn相應的單位特征向量α1，α2，…，αn構成。

證明 根據實對稱矩陣A與對稱變換σ的關系，只須證明σ有個n特征向量構成Rn的一組標準正交基。現對維數n作歸納法。

a）顯然n=1時結論成立。

b）假設n-1時結論成立。

c）對于Rn，σ必有一單位特征向量α1，使得σ(α1)=λ1α1。以L(α1)表示α1生成的子空間。由引理1，L⊥(α1)必為σ的n-1維不變子空間，且在L⊥(α1)上σ仍為對稱變換，故由歸納假設，在L⊥(α1)上σ有n-1個特征向量α2，α3，…，αn構成L⊥(α1)的標準正交基，從而σ的n個單位特征向量α1，α2，…，αn構成了Rn的一組標準正交基。

證畢。

考慮到式（6）實質上是單位特征向量下的Rayleigh商：

其中：Sk-1=L[y1，y2，…，yk-1]，Tn-k=L[yk+1，…，yn]分別為相應向量生成的子空間；S⊥k-1為Sk-1的正交補。分析式（8）（10）可以看出，矩陣A=β1Sb-β2Sw前n個特征值λ1≥λ2≥…≥λn相應的單位特征向量依次為投影變換的最佳投影方向，且這組特征向量對準則函數式（6）的貢獻程度單調下降，從而可以取其前s個最大特征值λ1，λ2，…，λs所對應的s個標準正交特征向量α1，α2，…，αs組成式（6）的最優投影矩陣：

Q=(α1，α2，…，αs)∈Rn×s（11）

此時，對于訓練文本xij=(wij，1，wij，2，…，wij，n)，以式（11）作為投影變換矩陣，得xij的投影向量:

這里yij為s維向量。由于參數s＜n，可以達到特征降維目的。

2 實驗結果及其分析

2．1 分類器選取： KNN分類器的一種基于密度的改進

首先對分類器進行改進。KNN方法是一種簡單有效的非參數方法，在準確率和召回率方面表現出眾成為文本分類中常用的分類器之一。KNN^[16]方法的具體步驟如下：

a）將待分類文本d表示成與訓練文本構成的維數一致的特征向量。

b）根據距離函數計算待分類文本向量d和訓練文本向量dj的相似度sim(d，dj)，使用兩向量之間的歐氏距離|d-dj|進行計算：sim(d，dj)=1/|d-dj|;選擇與d相似度最大（距離最小）的k個文本作為d的k個最近鄰。

c）根據d的k個最近鄰依次計算文本類別c1，c2，…，cr對文本d相應的權重，賦權計算公式為

其中:sim(dj，d)表示文本dj與文本d之間的相似度：

δ(dj，d)=1 dj是屬于ci的文本

0 dj不屬于ci（14）

為類別示性函數。

d）將待分類文本d歸入權重最大的類別。

考慮到當文本類別分布出現數據傾斜時，KNN分類器對訓練集數據分布不均具有敏感性：當選取d的最相近的k個文本時，分布密度高的文本簇可能被選中的文本數與分布密度比較稀疏的文本簇可能被選中的文本數相比占有優勢^[17]，從而對式（13）的類別判定產生影響。為了消除這種敏感性，記

作為文本dj與其相應的k個文本的平均相似度，則類內文本密度大的文本平均相似度大，而類內文本密度小的文本平均相似度小。為此將式（14）進行改進：

0dj不屬于ci（15）

從而將式（13）改為

式（16）使得樣本分布密集區域的樣本與待分類文本相似度被降低，而稀疏區域的樣本與待分類文本之間相似度被放大，從而有效降低了由于樣本點分布不均而對分類器的影響。

2．2 實驗結果及其分析

本文對上述方法的分類效果進行了實驗。實驗數據為新浪網上下載的2 450篇文本。其中分為文學（430篇）、政治（379篇）、體育（451篇）、計算機（370篇）、新聞（425篇）以及軍事（395篇）。實驗時采用4分交叉實驗法，將2 450篇文本平均分為四份(保持各類別文檔數的比例)，三份為訓練集，一份為測試集；每份輪流作為測試集循環測試四次，取平均值為測試結果。經過分詞、過濾停用詞、人工刪除冷僻的特低頻詞等預處理后，文本的原始特征集特征維數為1 423，使用式（6）進行特征抽取；使用式（12）進行投影變換，取投影空間維數S=70，效果評估函數使用常用的查準率、查全率和F1測試值：

查準率=分類的正確文本數/實際分類文本數

查全率=分類的正確文本數/應有文本數

F1=(查準率×查全率×2)/(查準率+查全率)

與未改進的KNN方法^[16]進行比較，分類結果統計如表1所示。

表1 實驗結果統計

類別文學/%政治/%體育/%計算機/%新聞/%軍事/%

查準率80.279.191.382.386.584.2

查全率77.3 83.292.586.488.283.6

F1測試值78.181.1 91.984.387.383.9

KNN^[16]F1值76.283.2 84.382.786.581.6

這里，文學與政治的F1測試值略低，可能是相對于其他類別來說，這兩類文本之間本身界限不太明顯的原因。平均查準率83.9%，查全率為85.2%;F1測試值為84.4 %，相比較與常用的KNN方法，改進的方法總體來看F1值有所提高。這說明本文提出的基于散度差的加權特征抽取方法與改進的KNN方法相結合模型，其分類效果還是令人滿意的。

3 結束語

特征降維問題是文本處理必須面對的主要問題之一，是制約提高文本分類效率的瓶頸。本文討論了一種基于散度差準則的特征抽取在文本分類中的應用。特征選擇和特征抽取從不同的立足點出發對文本特征進行壓縮，兩種模式各有其優點和不足。如何將兩種模型進行合理的結合，構造組合型的特征降維模型應該是提高特征降維效率的思路之一，這也是今后要進行的研究工作。

參考文獻：

［1］SEBASTIANI F.Machine learning in automated text categorization[J].ACM Computing Surveys，2002，34(1):1-47. 

[2]陳濤，謝陽群.文本分類中的特征降維方法綜述[J].情報學報，2005，24(6):690-694.

[3]蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報，2006，17(9):18481859.

[4]COVER T M.The best two independent measurements are not the two best[J].IEEE Trans on Systems， Man， and Cybernetics，1974，6(4):116117.

[5]宋楓溪，高秀梅，劉樹海，等.統計模式識別中的維數削減與低損降維[J].計算機學報，2005，28（11）:19151922.

[6]陳伏兵，張生亮，高秀梅，等.小樣本情況下Fisher線性鑒別分析的理論及其驗證[J].中國圖象圖形學報，2005，10(8):984-991.

[7]張生亮，陳伏兵，謝永華，等.基于類間散布矩陣的二維主分量分析[J].計算機工程，2006，32(11):44-46.

[8]張志佳，黃莎白，史澤林，等.基于線性投影的代數空間降維分析[J].計算機工程，2005，31（21）:25-27.

[9]吳春國，梁艷春，孫延風，等.關于SVD與PCA等價性研究[J].計算機學報，2004，27（2）：286-288.

[10]DEERWESTER S，DUMAIS S T，FURNAS G W，et al.Indexing by latent semantic analysis[J].Journal of the American Society of Information Science，1990，41(6):391-407.

[11]宋楓溪，劉樹海，楊靜宇，等.最大散度差分類器及其在文本分類中的應用[J].計算機工程，2005，31(5):8-50.[12]宋楓溪，張大鵬，楊靜宇，等.基于最大散度差鑒別準則的自適應分類算法[J].自動化學報，2006，32(4):541-549.

[13]陳大新.矩陣理論[M].上海:上海交通大學出版社，1997.

[14]王萼芳，石生明.高等代數[M].北京:高等教育出版社，2003.

[15]張明淳.工程矩陣理論[M].南京:東南大學出版社，1995.

[16]張寧，賈自艷，史忠植.使用KNN算法的文本分類[J].計算機工程，2005，31(8)：171172.

[17]鞏軍，劉魯.一種KNN文本分類器的改進方法[J].情報學報，2007，26(1):56-59.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”