1、一種基于潛在語義結構的文本分類模型 (江西師范大學計算機信息工程學院 江西南昌 330027)摘要：潛在語義索引（lsi）模型，是一種已經成功地應用于文本分類等很多領域的算法。lsi模型能在一定程度上解決一詞多義和多詞一義問題，并能過濾一部分文檔噪音。然而在lsi模型中，對稀有類別很重要的分類特征，可能因為在整個文檔集中不重要而被濾掉。針對這一問題，本文提出了一種新穎的擴展lsi模型的文本分類模型。新模型在盡量保留文檔信息的同時，增加考慮了文檔的類別信息。這樣，新模型將能比lsi模型更好地表示原始文檔空間中的潛在語義結構。在實驗中，本分類模型也表現出了非常好的分類性能。關鍵詞：文本分類 潛在語

2、義索引 偏最小二乘分析中圖分類號：tp18文獻標識碼: a1 引言自動文本分類就是在給定的分類體系下，根據文本的內容自動地確定文本關聯的類別。如今，已經有很多基于統計和機器學習的文本分類算法，如：回歸模型、k近鄰、決策樹、樸素貝葉斯和支持向量機等1。其中，很多現有的分類算法都是基于從文本中抽取關鍵詞（經常是單獨的詞）的方法。在這種方法中，假定一個關鍵詞唯一地代表一個概念或語義單元；然而實際的情況是：一個詞往往有多個不同的含義，多個不同的詞也可以表示同一個語義。這就是所謂的一詞多義和多詞一義。比如：“馬上”可以有“立刻”的意思，也可以理解為“馬的上面”；“感冒”、“傷風”和“著涼”卻代表著同一種

3、疾病。像這樣的情況是很難由計算機自動判別的。一詞多義和多詞一義，是所有基于語義的算法必須解決的兩個主要問題。潛在語義索引（lsi: latent semantic indexing）2，是近年來比較有效的算法之一。lsi 把原始的向量空間轉換成潛在語義空間，文檔和查詢就在轉換后的語義空間上進行表示和比較。實驗表明這種方法可以在一定程度上解決一詞多義和多詞一義問題：新的語義空間是原始“文檔向量矩陣”的線性組合變換得到的，一般認為這個空間能捕捉文檔集中的潛在語義結構。由于lsi在信息檢索中的優異表現2，就有人開始嘗試將其應用于文本分類領域。其中，wiener的工作3是很有代表性的。wiener的實

4、驗中以兩種方式使用了lsi。（1）利用lsi對原始向量空間降維。把潛在語義空間中權重較低的維濾掉，這樣就可以得到原始空間的一個子集，并濾掉一些噪音；（2）將整個文檔集按類別進行劃分，為每個類別建立一個lsi表示。為每個類別構建一個單獨的lsi表示，很重要的一個原因是：有一些對特定類很重要的詞，由于詞義不確定的問題，在整體考慮所有類的時候，反而會變的不重要。如bank這個詞可能對財經類很重要，但如果把所有類放在一起考慮，這個詞就有可能因為它的多義性在語義空間中被濾掉（或變得不重要）。實際上，我們發現這種分立的lsi表示，確實可以分別為每個類找到重要的詞（或特征）。但在考慮整個文檔集的時候，情形就

5、會有所不同：對單個類重要的詞并不一定就對分類有大的貢獻。文本分類的關鍵是在整體考慮下，在所有的類別中，為文檔找到它最有可能屬于的類。這種類別之間的舍取，在每個類別都是單獨考慮情況下肯定不可能做到完全公平。在本文中，我們提出了一種對lsi擴展的算法。我們提取的語義特征不僅反映了文檔和詞的信息，也考慮了文檔的類別信息。不同于為每個類建立單獨的lsi表示，我們把所有的信息整合在一個lsi表示里。本文組織如下：第一部分是引言，第二部分介紹一些相關的基本概念，第三部分詳細闡述本文提出的模型，實驗結果和分析在第四部分中說明，最后是結束語。2 相關工作2.1 基于向量空間模型的文本分類在向量空間模型中，文檔

6、以由n個詞組成的向量表示（這些詞從文檔集中選取得到），詞也可以由m篇文檔組成的向量表示。在實際使用中，用“文檔向量矩陣”x能最好的代表這種對偶的信息表示，其中一列代表一個詞、一行代表一篇文檔：矩陣中的元素，一般表示詞j在文檔i中出現的頻數；也可以根據其他因素調整它的權重4。比如，以反向文檔頻率（idf: inverse document frequency）調整：其中，文檔頻數是出現詞j的文檔數量。說明一下，由于一個詞只會在很少的文檔中出現，因此矩陣x中的大多數元素都會是零。信息檢索的典型處理方式就是關鍵字匹配。用戶提出一個查詢q，然后用和文檔一樣的方式，把它看成一個由關鍵字組成的向量。通過計

7、算查詢向量和文檔向量之間的點積（對向量的規一化消除文檔長度的影響），可以得出兩者之間的相似度。所有m篇文檔的相似度可以構成一個向量s()，查詢q的相關文檔就可以根據這個指標排序并返回給用戶。文本分類，就是把新的文檔歸到已有的類別體系中去。有很多方法可以實現這個目的，一種簡單的分類方法是為每個類別計算一個中心向量（類中所有文檔向量的平均值）5。這些中心向量被認為是每個類別的代表。所有k個類別的k個中心向量，組成一個 的矩陣。判別文檔屬于某個類的標準是，該文檔距離哪個類別的中心向量更近。其他的方法6則是通過最小化誤差平方和c，來解決文本分類問題，c的定義如下：其中，b是保存訓練集文檔的正確類別信息

8、的矩陣。一篇新進文檔，要通過投影到變換向量上得到與每個類的相似度，并由具體的閾值，決定其到底屬于哪個類或哪幾個類。2.2 應用lsi模型的文本分類在原始的“文檔向量矩陣”中，存在著冗余、詞語多義和噪音問題。我們希望建立一個比原始矩陣小得多，并只包含有效語義的子空間。要達到這個目的，一般可以通過有效的維數約減。維數約減后，冗余的信息可以合并在一起，詞語多義可以通過考慮上下文相關信息解決，把相對不重要的一些特征約去則可以部分解決噪音問題。lsi就是這樣一種維數約減方法。它可以通過對“文檔向量矩陣”進行解奇異值分解（svd: singular value decomposition）運算，自動計算得

9、到一個比原始空間小得多的有效語義空間：其中，r是矩陣x的階，是由特征值構成的對角矩陣，和分別是左、右特征向量。一般r個特征值是按大小排序的，當要進行特征值截取的時候，比如只保留前k個最大的特征值，下面的矩陣就是原始矩陣的非常好的近似：在得到的k維子空間中，一篇文檔的投影是，而所有m篇文檔的投影就是。查詢q的變換方式也是如此。因此，查詢q和文檔之間的相似度計算在lsi的子空間中就變成了：維數的大量約減，既降低了計算的復雜度也濾去了一部分噪音。比如，求矩陣中心向量或作矩陣變換的計算量就從變成了 5。這樣的方法在樸素貝葉斯分類模型7、knn模型和svm模型8中都被證明是非常有效的，提高了分類模型的準

10、確度。lsi成功的原因在于，lsi得到的語義空間比原始特征空間更能表達分類必須的語義結構，部分地解決了信息檢索中的同義詞和文本分類中的信息冗余問題。在數學上，通過svd選取的矩陣是原始矩陣x在k階情況下的最佳近似。從統計觀點看，lsi和主成分分析類似，是一種非常有效的維數約減方法。即：認為特征值較小的維是噪音，并將其濾去。然而，lsi在降低維數的同時也會丟失結構信息。實際上，lsi基于文檔信息來建立語義空間（文檔的類別信息并未考慮），得到的空間會保留原始矩陣中最主要的全局信息。但有一種情況是：一些對特定類別分類貢獻很大的特征，放在全局下考慮卻會變得不重要了。這樣的特征在維數約減的過程中，就很容

11、易被濾掉，而如果這樣，特定類別的分類精度就會受影響。要解決這個問題，文檔的類別信息就應該也被考慮進來。以傳統方式使用lsi的另一個問題是：沒有理論說明，在得到的語義空間中到底應該保留多少維，而維數的變化對最后的結果又有很大的影響8。在實際使用中，人們一般中只能通過反復的實驗來確定這個值。3 應用于分類的一種潛在語義模型使用lsi方法的前提假設是，在由大量的詞和特征構成的“文檔向量矩陣”中隱含著有規律的潛在語義結構。如前所述，稀有類別的重要特征卻有可能被忽略掉。事實上也是，稀有類中出現的詞很可能是文檔集中的非常見詞，而非常見詞就很有可能被濾掉。于是對稀有類別很重要的分類特征，可能因為在文檔集中不

12、重要而被濾掉。為了解決這個問題，wiener9使用局部lsi模型代替全局lsi模型。他們為每個類別建立了一個獨立的lsi模型，在分類過程中，每個局部lsi模型都被單獨的使用。這樣的方法能局部解決前面提到的問題：對稀有類別很重要的特征可以在其局部lsi模型中保留下來。但這樣還有其他的問題：（1） 一篇新進文檔屬于哪些類別，各個局部lsi模型是分別單獨考慮的，那么不同的局部模型得到的相似度分值就很難相互比較。可能造成的情況是，應該屬于某個類的文檔卻被錯誤的分到了其他類中。（2） 無法很好的解決一詞多義的問題。比如，在某個特定類別（如：金融）中，一個多義詞（如：bank）就可能變得沒有歧義。局部ls

13、i模型會認為這種詞很重要，但如果放在文檔集中考慮，它對分類的貢獻卻不大。在分立的局部模型中，我們將無法考慮這種一詞多義的情況。為了解決這個問題，我們提出了一種同時考慮文檔信息和類別信息的分類模型。與lsi模型類似，我們也希望從原始空間中得到一個潛在語義空間；然而不同的是，我們要在盡量保留文檔信息的同時，通過對文檔信息和類別信息建模，把文檔和類別之間的關聯也考慮進來。從統計學的觀點來看，和偏最小二乘分析（partial least square analysis）有些類似。下面給出一些符號約定：x是mn維的“文檔向量矩陣”；是m維的類別信息向量，其中，；矩陣x和向量y都要先做規一化。向量分別是x

14、和y的潛在變量。現在我們所關注的就不是詞信息的協方差矩陣x，而是x和y的交叉協方差矩陣。我們希望通過一組一組的潛在變量對來表示這些交叉信息，就如：其中，代表矩陣x中的潛在語義信息，代表矩陣y中的潛在信息。按他們代表信息的重要程度降序排列，也就是代表最重要的信息，代表次重要的信息，依次類推。確定這些變量對的原則是：（1）變量對，是在對矩陣x和向量y的最佳近似；（2）變量對，是對除去已表示部分的x和y的最佳近似；（3）變量對，是對除去和已表示部分的x和y的最佳近似；具體的變量對（如），它要滿足如下條件：（a）變量，要盡可能好的表示矩陣x的信息；（b）變量，要盡可能好的表示矩陣y的信息；（c）變量對

15、，要盡可能好的表示矩陣x和y之間的聯系。從統計上來說，條件（a）等價于使變量滿足，即：要得到表示矩陣信息最多的變量，就是要使得該變量的方差最大；條件（b）等價于條件;條件（c）等價于要求 ，其中代表求兩個隨機變量之間的相關系數。把看成是由詞組成的，也就可以寫成：其中，u是一個待定的向量。即認為是詞的線形組合，不同的詞根據它對語義單元的重要性不同有不同的權重。類似的，我們也可以認為變量（v也是一個待定向量），是y中元素的線形組合。它也是一個非常重要的聯系矩陣x和y的中間變量。這樣，前面提到的三個條件就可以寫成：其中，|u| 和 |v| 代表向量 u 和 v長度。根據協方差的定義，我們有：于是，前

16、面的三個極值問題就可以整合成一個極值問題10：假定代表點積，因為， 確定的問題就可以轉成求解如下的極值問題：如果是這個極值問題的解，根據奇異值分解的原理，就是矩陣在一階情況下的最佳近似11；其中，是奇異值分解的奇異值，分別是左右特征向量。得到潛在變量對后，我們就能計算出在矩陣x和y中，和所能表示的部分：那么，減去這些信息的矩陣就是和；從新的x和y出發，就可以通過相同的過程依次得到和其他的變量對。上面的過程與wold10提出的偏最小二乘算法（pls : partial least square）是類似的。為了避免進行奇異值分解運算，tenenhaus12對該算法做了改進，修改后的算法如下：算法

17、(lsr/pls1): ; ; for k=1,s do ; ; ; ; endfor當所有的潛在變量對都計算出來后，我們就可以按如下方式對文檔進行分類：假設有一新進文檔，為了表示它與訓練集中心向量的差異，對做變換得到，其中；然后就可以按下面的公式，遞推出s個元素（其中k = 1, , s）：是一個中間變量；是規范化的主成分，在算法(lsr/pls1)中第k步確定；表示第k個主成分所代表的語義信息；因此，元素代表的是第k步時，矩陣中的剩余信息。最終，文檔的類別信息可以這樣計算出來：其中，的計算方式和類似。本算法既考慮了文檔信息（在公式中由e表示），也考慮了類別信息（在公式中由f表示）。算法中由

18、變量表示前者，變量表示后者，而由兩者同時表示。與全局lsi比較，我們的方法增加了類別信息；與局部lsi比較，我們沒有分別考慮不同類別的信息，而是整體考慮的；這樣在分類時，文檔屬于某個類別的相似度分數就易于比較了。另外，非常有意思的是當向量y的取值全是1的時候，上面的模型就變成了傳統的lsi模型。這也就是說，lsi模型是我們這個模型的一個特例。4 實驗結果和討論做文本分類實驗，語料庫的選擇是非常重要的；只有語料庫一致，不同作者之間的實驗結果的比較才有意義。英文文本分類方面，國外已經有了reuter，trec，ohsumed等一些標準權威的分類語料庫；而在中文文本分類方面，目前還沒有一個公認權威的

19、中文文本分類語料庫。一般國內的作者，都是自己收集文檔建立語料庫，并在上面做實驗；而這樣得到的結果很難與其他同行的結果做比較。經過選擇，我們選用了復旦大學中文文本分類語料庫。該語料庫總共有19637篇文檔，其中測試文檔9833篇，訓練文檔9804篇；訓練文檔和測試文檔基本按照1:1的比例來劃分。經分析發現語料庫存在大量重復文檔和少量損壞文檔，去除后這些文檔后，保留有14377篇文檔，其中訓練文檔8214篇和測試文檔6163篇?？珙悇e的重復文檔沒有考慮，即一篇文檔只屬于一個類別。所有文檔分為20個類別，但文檔的分布并非平均分布；其中訓練文檔最多的類economy有1369篇訓練文檔，而訓練文檔最少

20、的類communication只有25篇訓練文檔；整個語料庫中訓練文檔少于100篇的稀有類共有11個。在預處理階段，中文分詞部分，我們采用了中科院計算所開源項目“漢語詞法分析系統ictclas”系統，然后按詞性只保留了名詞和動詞；對文檔中出現的英文予以保留，全部轉為小寫形式，去除了英文停用詞，沒有做詞干化處理。特征提取算法采用了算法。詞的權重表示方式，采用了ltc權重：其中，是詞i出現在文檔k中的頻數，n是訓練集文檔的總數，m是訓練集中詞的總數，是出現了詞i的文檔數。文本分類系統中兩個常用的評價指標是準確率(precision = l/m)和召回率(recall= l/n)，其中l為分類正確的

21、文本數，m為確定了類別的文本數，n為待分類的總文本數。綜合考慮準確率和召回率，可以得到新的評估指標f1測試值，也稱為綜合分類率，計算公式如下： 為了評測系統整體的分類性能，我們還采用了微平均f1和宏平均f1兩種指標。其中宏平均f1平等對待每一個類別，因此它的得分主要受非常見類的影響；而微平均f1則平等考慮每一個文檔，因而它將主要受常見類的影響。在實驗中，我們用算法(lsr/pls1)建立了多二分分類器。循環次數s，由矩陣的值決定。當對矩陣x的估計（）近似于零的時候，那么我們就認為矩陣中剩余的信息已經很少了，而停止循環。閾值的確定，是另一個比較復雜的問題。在實驗中，我們把整個訓練集代回分類器，通

22、過最大化f1的方式確定閾值。為了檢測本算法在特征維數變化情況下的性能，我們對算法在不同維數下的微平均f1和宏平均f1作了比較。結果如下：表1 不同特征維數的情況下的微平均f1和宏平均f1特征維數1002005001,0002,0003,0004,0005,0006,0007,0008,000微平均f107720817085408740887088408820883088608830886宏平均f104850545063606990727072607340721074607300753從表1中可以看出，本算法在特征維數只有100的情況下，依然具有可接受的分類性能；而在特征維數大于1000以后，微

23、平均f1值就穩定在比較高的88左右。說明本算法相對于特征數量的魯棒性較好。下面我們進一步給出在2000維的情況下，各個類別具體的precision，recall和f1變化的情況：類別訓練文檔測試文檔precisionrecallf1economy136911270.894 0.917 0.905 sports12049800.968 0.927 0.947 computer10195910.974 0.953 0.963 politics10109890.915 0.915 0.915 agriculture8476350.904 0.945 0.924 environment8053710.

24、945 0.933 0.939 art5102860.733 0.815 0.772 space5062480.953 0.899 0.925 history4664680.774 0.763 0.769 military74750.576 0.507 0.539 education58580.646 0.534 0.585 transport57580.800 0.690 0.741 law51520.735 0.481 0.581 medical51520.926 0.481 0.633 philosophy40330.538 0.424 0.475 mine33290.762 0.552

25、 0.640 literature33320.667 0.063 0.114 energy30310.870 0.645 0.741 electronics26260.750 0.577 0.652 communication25220.773 0.773 0.773 表2 各個類別的precision，recall和f1從表2中可以看出，本算法對于訓練文檔數大于800的常見類的f1值均大于了90，對于大部分稀有類的分類性能也在可接受范圍內，只有個別類的分類性能較差（估計與語料庫有一定的關系）。說明本算法的整體性能較好，是一種非常有效的文本分類算法。5 結束語本文提出了一種新穎的擴展lsi模型

26、的文本分類模型。針對lsi模型中對稀有類別很重要的分類特征，可能因為在文檔集中不重要而被濾掉的問題，新模型在盡量保留文檔信息的同時，增加考慮了文檔的類別信息。這樣，新模型將能比lsi模型更好地表示原始文檔空間中地潛在語義結構。在實驗中，本分類模型也被證明是一種非常有效的文本分類算法。未來的工作是：進一步完善和優化算法，找到一種比較好的循環判停條件和一種更好的閾值判定算法；并與其他經典分類算法作一下比較。致謝：實驗用的“復旦大學中文文本分類語料庫”是由復旦大學李榮陸提供，中文分詞用的“漢語詞法分析系統ictclas”系統是由中科院計算所張華平提供。在此表示感謝！參考文獻1 sebastiani,

27、 f. (2002) machine learning in automated text categorization, acm computing survey, 34(1):1-47.2 deerwester, s., dumais, s.t., furnas, g.w., landauer, t.k., harshman, r. (1990) indexing by latent semantic analysis, journal of the american society of information science, 41(6): 391-407.3 wiener, e.,

28、pedersen, j.o., weigend, a.s. (1995) a neural network approach to topic spotting, proceedings of sdair-95, 4th annual symposium on document analysis and information retrieval, pp. 317332.4 salton, g. and buckley, c. (1988) term weighting approaches in automatic text retrieval, information processing

29、 and management, 24(5): 513-523.5 dumais, s.t. (1995) using lsi for information filtering, the third text retrieval conference (trec-3), d. harman, ed., national institute of standards and technology special publication.6 yang, y. (1995) noise, reduction in a statistical approach to text categorizat

30、ion, 18th acm international conference on research and development in information retrieval, pp. 256263.7 baker, l.d., mccallum, a.k. (1998) distributional clustering of words for text classification, proc. acm- sigir-98, pp. 96103.8 park, h., howland, p. and jeon, m (2003) cluster structure preserv

31、ing dimension reduction based on the generalized singular value decomposition, siam journal on matrix analysis and applications, 25(1):165-179.9 wiener, e., pedersen, j.o., weigend, a.s. (1995) a neural network approach to topic spotting, proceedings of sdair-95, 4th annual symposium on document ana

32、lysis and information retrieval, pp. 317332.10 wold, h. ( 1985) partial least squares, kotz, s. and johnson n.l., encyclopedia of statistical science. wiley, new york.11 harville, d.a. (1997) matrix algebra from a statisticians perspective. spinger.12 tenenhaus, m. (1998) la rgreesion pls. thorie et pratique. ditions technip, paris.a latent semantic structure model for text classificationz