一種基于潛在語義結(jié)構(gòu)的文本分類模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、平均f1值就穩(wěn)定在比較高的88左右。說明本算法相對于特征數(shù)量的魯棒性較好。下面我們進一步給出在2000維的情況下，各個類別具體的precision，recall和f1變化的情況：類別訓(xùn)練文檔測試文檔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中可以看出，本算法對于訓(xùn)練文檔數(shù)大于800的常見類的f1值均大于了90，對于大部分稀有類的分類性能也在可接受范圍內(nèi)，只有個別類的分類性能較差（估計與語料庫有一定的關(guān)系）。說明本算法的整體性能較好，是一種非常有效的文本分類算法。5 結(jié)束語本文提出了一種新穎的擴展lsi模型

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