淺談基于特征選擇的文本聚類方法.doc

淺談基于特征選擇的文本聚類方法以Text Clustering with Feature Selection by Using Statistical Data為例摘 要: 基于特征選擇的文本聚類方法不僅能夠降低文本數(shù)據(jù)空間的維度，而且能夠顯著提高文本聚類的性能。以Text Clustering with Feature Selection by Using Statistical Data為例，對基于特征選擇的文本聚類方法進(jìn)行典型分析，并在此基礎(chǔ)上，對Text Clustering with Feature Selection by Using Statistical Data進(jìn)行簡要評價，認(rèn)為如何在實際應(yīng)用中更好地引入學(xué)習(xí)機(jī)制，將特征選擇融入到文本聚類中，從而提高文本聚類效率是一個好的研究方向。關(guān)鍵詞: 特征選擇；文本聚類；K-means算法1引言文本聚類是文本挖掘和信息檢索領(lǐng)域的核心問題之一。它完全根據(jù)文本文檔的內(nèi)容相關(guān)性來組織文檔集合，將整個集合聚集成若干個類，并使得屬于同一類的文檔盡量相似，屬于不同類的文檔差別明顯。文本聚類方法可以分為等級聚類法和動態(tài)聚類法，主要應(yīng)用于自動摘要、文本的自動組織、搜索結(jié)果聚類等方面1。文本聚類是一種無監(jiān)督的學(xué)習(xí)方法，文本缺少有監(jiān)督特征選擇所必須的類別信息。因此，有監(jiān)督的特征選擇方法在文本分類上取得了成功，但是卻很少用于文本聚類中。然而，若能夠有效將有監(jiān)督的特征選擇方法應(yīng)用在文本聚類上，則能夠顯著提高文本聚類的性能。因此，如何將有監(jiān)督的特征選擇方法應(yīng)用于文本聚類成為了一個新的研究熱點。目前，國外學(xué)者在此方面進(jìn)行了大量研究，并取得了較為豐厚的結(jié)果。如Jos Martnez Sotoca2，Yanjun Li3，P.Santhi4等。相較而言，國內(nèi)學(xué)者的研究熱點還主要集中在單獨對特征選擇方法改進(jìn)或聚類算法改進(jìn)上。如樊東輝，王治和5等提出了一種利用特征詞的熵函數(shù)加權(quán)的權(quán)值的計算方法，考察特征詞的文檔頻數(shù)和在文檔中出現(xiàn)的次數(shù)，使選出的特征子集更具有較好的代表性，從而改善聚類結(jié)果。胡玉嫻6則提出基于知網(wǎng)特征詞合并算法，通過合并具有高度相似性的特征詞，有效降低特征向量維度，使得聚類結(jié)果較為穩(wěn)定。誠然，國內(nèi)也有少數(shù)學(xué)者對基于特征選擇的文本聚類進(jìn)行研究，比較具有代表性的有劉濤、吳功宜和陳正7的一種高效的用于文本聚類的無監(jiān)督特征選擇算法。 下面，筆者以國外學(xué)者Yanjun Li，Congnan Luo，Chung, S.M的Text Clustering with Feature Selection by Using Statistical Data為代表，進(jìn)行典型分析，并在此基礎(chǔ)上進(jìn)行簡評，以期為今后學(xué)術(shù)界在文本聚類上的研究提供一定的參考。2典型分析從文本數(shù)據(jù)收集與處理、特征項選擇、聚類算法實現(xiàn)、聚類結(jié)果分析等四個方面對Yanjun Li，Congnan Luo，Chung, S.M所寫的Text Clustering with Feature Selection by Using Statistical Data進(jìn)行分析。2.1文本數(shù)據(jù)收集、處理與表示2.11文本數(shù)據(jù)收集與處理Yanjun Li等從CACM and MEDLINE 摘要文本和Reuters-21578 Distribution 1.0兩個不同類型的數(shù)據(jù)庫中提取了5個用于測試的數(shù)據(jù)集，其中2個數(shù)據(jù)集來自于前者，另外三個數(shù)據(jù)集來自Reuters-21578 Distribution 1.0中的EXCHANGE、PEOPLE、TOPIC分類集。在進(jìn)行聚類實驗之前，利用停用詞表刪除了文本數(shù)據(jù)集中出現(xiàn)的停用詞。各文本數(shù)據(jù)集中的文檔都已經(jīng)提前被分類到了某一個唯一類中，但是，在聚類的過程中，這些信息是被隱藏的，提前分類的結(jié)果僅僅用于后面對聚類結(jié)果準(zhǔn)確度的評價。2.12文本數(shù)據(jù)的表示 文本聚類面臨的首要問題是如何將文本內(nèi)容表示為使用計算機(jī)可以分析處理的形式，即文本數(shù)據(jù)的表示方法。目前國內(nèi)外學(xué)者通常采用的是向量空間模型，從文本中提取特征詞構(gòu)成特征向量，并計算出每個特征詞在各個文檔中的權(quán)重。如果把特征列表看作一個 維的坐標(biāo)系，那么坐標(biāo)值就對應(yīng)為各維的權(quán)重，文本集中的每一個文檔就可以看作是 維空間中的一個向量，這樣就把文檔表示成為計算機(jī)可以處理的形式了。Yanjun Li等采用的正是向量空間模型。2.2特征項選擇常用的特征選擇方法有信息增益、互信息、x2 統(tǒng)計量、期望交叉熵、單詞權(quán)、單詞貢獻(xiàn)度1。但是在眾多的特征選擇方法中，有學(xué)者指出IG（信息增益）和CHI（x2 統(tǒng)計量）的效果最好8，而IG計算量相對其它幾種方法較大，因此Yanjun Li等針對目前特征選擇方法中效果最好2統(tǒng)計方法進(jìn)行研究和改進(jìn)。他們在研究中發(fā)現(xiàn)了以下兩個問題：其一，CHI降低了低頻詞的權(quán)重。2統(tǒng)計方法不能準(zhǔn)確地保留往往是某類特有的，具有很強代表性的低頻詞。這里的低頻詞是指文檔頻數(shù)，但某些低頻詞往往是某類特有的特征詞，這些特征詞具有很強的代表性，雖然只出現(xiàn)在指定類的少量文章中，但在這少量文章中頻繁的出現(xiàn)，因此對分類的貢獻(xiàn)很大，需要被保留下來；其二，提高了很少在指定類中出現(xiàn)但普遍存在于其他類的特征在該類中的權(quán)重。在整個訓(xùn)練集語料庫中一些出現(xiàn)頻率較高的詞，而這些詞語在指定類中出現(xiàn)得很少甚至幾乎是不出現(xiàn)的，顯然這些詞是不能很好地代表該指定類，應(yīng)該被過濾掉。針對以上兩個缺陷，Yanjun Li等對CHI方法進(jìn)行了改進(jìn)，提出了一種新的分類方法CHIR。針對缺陷一，把特征項在具體的文檔中出現(xiàn)的頻度作為權(quán)重值考慮進(jìn)2統(tǒng)計的計算公式。因此，某一特征向量與類的關(guān)系計算公式為：其中：p(RW, Cj)是 的權(quán)重： 針對缺陷二，改進(jìn)的方法主要體現(xiàn)在對Rw,c的判斷上。Rw,c=(a*d-b*c)/(a+b)(a+c) +1，當(dāng) Rw,c小于1時，即在整個語料庫出現(xiàn)頻繁，而在指定類出現(xiàn)較少。當(dāng) 大于 1 時，即在指定類出現(xiàn)較多。2.3聚類算法實現(xiàn) Yanjun Li等基于EM算法，將有監(jiān)督的特征選擇方法CHIR與K-means算法進(jìn)行結(jié)合，形成了一種新的聚類算法TCFS。TCFS算法的詳細(xì)步驟如下：1執(zhí)行第一遍K-means算法，獲得初始聚類和各類的聚類中心；2對步驟1生成的數(shù)據(jù)集，利用CHIR，進(jìn)行特征選擇。被選擇的特征將繼續(xù)保持在表示文本集的向量空間中，而沒有被選擇的那些特征，其乘以一個特定的權(quán)重值f，f為提前設(shè)定的一個因子，取值范圍為（0,1），從而減少他們對于文本聚類的影響力。緊接著，在新的向量空間中，重新計算K個類的聚類中心。3文檔集中的每一篇文檔都要利用聚類標(biāo)準(zhǔn)函數(shù)來與新的向量空間中各個類的中心進(jìn)行比較，從而將每一篇文檔劃分到與其最為相似的類別中。4反復(fù)迭代步驟2和步驟3，直到簇中心不發(fā)生改變。2.4聚類結(jié)果分析2.41特征選擇的評價Yanjun Li等利用凝聚度對CHIR、CHI、CC、SCHI等四個特征選擇方法進(jìn)行比較，使用的數(shù)據(jù)庫為CACM數(shù)據(jù)庫。研究結(jié)果顯示，當(dāng)選擇前20%的詞作為特征量時，CHIR能夠比CHI、CC、SCHI更有效刪除非相關(guān)特征。通過比較各凝聚度值的大小，可以知道，在同一百分比的特征選擇下，CHIR的凝聚度值均大于其他三個的凝聚度值，且特征選擇的百分比越小，即選擇的特征越少，CHIR的凝聚度與其他三個的凝聚度值相差越大，CHIR在特征選擇上的表現(xiàn)越優(yōu)異。2.42聚類方法的評價Yanjun Li等利用純度和F-Measure來評價聚類算法的準(zhǔn)確性。純度是度量類簇在多大程度上包含單個類的成員的另一種度量。類簇 i的純度通過式Purity = Max(Pij )求得 ，聚類的總純度通過式計算得到?？偧兌仍礁撸垲愋阅芫驮胶?。F-Measure是將準(zhǔn)確率（Precision）與召全率（Recall）綜合起來的另外一個常用指標(biāo)。對于每一個主題類別T和對應(yīng)的聚類C中，統(tǒng)計出:N1:在聚類C中且主題類別為T的文檔數(shù)；N2:在聚類C中但不屬于主題類別T的文檔數(shù)；N3:屬于主題類別T但沒有分到聚類C中的文檔數(shù)；Precision(C,T)=N1/(N1+N2); Recall(C,T)=N1/(N1+N3); F-measure=2PR/(P+R)10。 Yanjun Li等將聚類方法的評價實驗分成兩個部分。一方面，他們比較了K-means算法、基于TS的K-means算法、基于CHIR的TCFS算法、基于CC的TCFS算法和基于CHI的TCFS算法等5個算法的準(zhǔn)確性。將這五種算放運行與EXE數(shù)據(jù)庫，運行結(jié)果顯示：由于特征選擇方法能夠有效移除非相關(guān)或冗余特征，因此，將特征選擇的方法溶于文本聚類中，能夠有效改善文本聚類的結(jié)果；將有監(jiān)督的特征選擇方法運用于TCFS算法中（如基于CHIR的TCFS算法、基于CC的TCFS算法和基于CHI的TCFS算法），得到的F-measure值比基于TS的K-means算法要更好，可見，若將有監(jiān)督的特征選擇方法運用于聚類過程中，更夠提高聚類的準(zhǔn)確性；當(dāng)特征向量的選擇百分比發(fā)生變化時，基于TS的K-means算法所得到的聚類結(jié)果并不是一直都比K-means算法要優(yōu)異，基于TS的K-means算法并不能夠一直選出最合適的特征集，在某些時候，TS會移除一些相關(guān)特征而保留一些非相關(guān)特征；在不同的測試數(shù)據(jù)集中，基于CHIR的TCFS算法得到的F-measure值和純度值都要高于其他算法，基于CHIR的TCFS算法優(yōu)于其他四個算法。另一方面，他們對TCFS與IF（迭代特征選擇算法）進(jìn)行了比較。IF算法與TCFS算法的主要區(qū)別在于以下兩點，其一，在IF中，一旦某一個特征沒有被選擇，這個特征將立即被移除，從而不會出現(xiàn)在接下來的聚類中；其二，在IF中，特征選擇的過程時獨立與K-means算法的。實驗結(jié)果顯示：在大多數(shù)情況下，TCFS的聚類結(jié)果優(yōu)于IF的聚類結(jié)果；隨著迭代次數(shù)的增加，IF算法并不能夠一直提高其聚類效果。究其原因，Yanjun Li等認(rèn)為，在初始時期，通過有監(jiān)督特征選擇方法得到的特征向量并不一定是真正能夠代表各類的特征向量，有些沒有被選擇的向量很有可能才是真正能夠代表某類的特征向量，但是，這些向量需要在接下來的運行過程凸顯出來。因此，如果在初始時期就將沒有被選擇的向量移除，將對接下來的特征選擇結(jié)果和聚類結(jié)果產(chǎn)生不好的影響。由此可見，降低將未被選中的特征在向量空間中的權(quán)重而非直接將其刪除的TCFS算法能夠?qū)υ缙鹚赶碌腻e誤進(jìn)行糾正，從而獲得一個更好的聚類結(jié)果。3簡評接下來，筆者將從兩個層面對Yanjun Li，Congnan Luo，Chung S.M的Text Clustering with Feature Selection by Using Statistical Data進(jìn)行簡單評論。這兩個層面分別是自身層面和比較層面。3.1自身層面Yanjun Li，Congnan Luo，Chung S.M的Text Clustering with Feature Selection by Using Statistical Data闡述了有監(jiān)督的特征選擇方法在文本聚類中的研究與應(yīng)用過程。新特征選擇方法和聚類算法的提出為今后在特征選擇方法和有監(jiān)督的文本聚類算法等多個方面的研究奠定較好的基礎(chǔ)。但是，筆者認(rèn)為，Text Clustering with Feature Selection by Using Statistical Data也存在一些不足之處：其一，評價指標(biāo)的客觀性不強。對于同一種算法，不同的評價指標(biāo)，得到的評價結(jié)果是具有差異性的。在Text Clustering with Feature Selection by Using Statistical Data中，筆者僅僅通過凝聚度一個指標(biāo)對特征選擇方法進(jìn)行了評價，而在算法的評價中，同一種算法在F-measure和純度兩個指標(biāo)中表現(xiàn)的結(jié)果也不盡相同。由此可見，是否僅僅用一個或兩個評價指標(biāo)就能夠很好地說明問題還有待探究；其二，存在算法對數(shù)據(jù)庫的依賴性問題。同一算法運行與不同數(shù)據(jù)庫中，產(chǎn)生的結(jié)果不盡相同，甚至差異性極大。在Text Clustering with Feature Selection by Using Statistical Data中，作者并非將各個算法在五個數(shù)據(jù)庫中運行的結(jié)果都展現(xiàn)出來了，而是選擇了其中的兩個數(shù)據(jù)庫運行結(jié)果進(jìn)行展示，剩余的三個數(shù)據(jù)庫的運行結(jié)果無從得知。有理由懷疑TCFS在未展示的數(shù)據(jù)庫中運行得到的結(jié)果并不盡如人意；其三，f值的取值問題。在聚類算法中，未被選中的特征向量將乘以f來降低其在向量空間中所占有的權(quán)重。不可否認(rèn)的是，相較于直接刪除未被選擇的特征向量，這確實是一個好的想法，但是，在Text Clustering with Feature Selection by Using Statistical Data中，作者并沒有指出f值究竟應(yīng)該取多少為合適。在實驗中，作者選取的f值為0.5，而其選取的原因無從而知。會不會有可能存在，當(dāng)f值取其他值時，得到的實驗結(jié)果與現(xiàn)有的實驗結(jié)果差別較大呢？其四，新的聚類算法并沒有改進(jìn)K-means算法固有的缺陷?，F(xiàn)有的研究成果顯示，K-means算法具有初始聚類中心不確定、初始類數(shù)量自定義、只能發(fā)現(xiàn)球狀簇等缺陷。但是，對于這些缺陷，新的聚類算法TCFS并沒有提出有效的改進(jìn)方法，改進(jìn)K-means算法固有的缺陷依舊任重而道遠(yuǎn)。3.2比較層面以劉濤、吳功宜和陳正的一種高效的用于文本聚類的無監(jiān)督特征選擇算法為比較對象，對這兩種基于特征選擇的文本聚類算法進(jìn)行比較研究。劉濤、吳功宜和陳正的一種高效的用于文本聚類的無監(jiān)督特征選擇算法中描述的文本聚類算法如下：從最大聚類數(shù)和最小聚類數(shù)的集合中，隨機(jī)選擇一個數(shù)K為聚類個數(shù)并隨機(jī)選擇K個初始中心點；利用K-means聚類得到聚類結(jié)果P；在P的結(jié)果上使用特征選擇算法如CHI、IG等為每一個單詞求得重要性值；更新每一個單詞的重要性，即每一個單詞新的重要性等于本次聚類前的重要性加上此次聚類后得到的新的重要性；按照重要性對單詞數(shù)組進(jìn)行排序，在此基礎(chǔ)上，開始新一輪的聚類；在聚類開始前就設(shè)置好聚類次數(shù)M，重復(fù)執(zhí)行步驟-M次，聚類結(jié)束。通過比較兩種算法，可以兩種之間既有共同點又有差異性。共同點體現(xiàn)在：兩種聚類算法都是在聚類結(jié)果上使用特征選擇方法，改變單詞權(quán)重（重要性）；在計算單詞權(quán)重時，不是僅根據(jù)一次聚類結(jié)果就將某些單詞刪除（權(quán)重為零），而是，采用累積的方法，結(jié)合多次聚類結(jié)果，逐漸改變單詞權(quán)重；兩種聚類算法都沒有改進(jìn)K-means算法固有的缺陷。差異性體現(xiàn)在：一套完整的K-means算法的執(zhí)行次數(shù)不同，Yanjun Li等設(shè)計的聚類算法在時間和空間上優(yōu)于劉濤等設(shè)計的聚類算法。Yanjun Li等設(shè)計的文本聚類算法只進(jìn)行一輪的完整K-means算法，而劉濤等設(shè)計的聚類算法則要根據(jù)最初設(shè)置的參數(shù)M，進(jìn)行M輪完整的K-means算法；特征選擇發(fā)生的時間不同。在Yanjun Li等設(shè)計的文本聚類算法中，特征選擇是在每一次聚類結(jié)果上進(jìn)行的，而在劉濤等設(shè)計的聚類算法中，特征選擇是在每一輪聚類結(jié)果上進(jìn)行的；需要人為設(shè)置的參數(shù)不同。在Yanjun Li等設(shè)計的文本聚類算法中，需要人為設(shè)置參數(shù)f為控制單詞權(quán)重的變化，而在劉濤等設(shè)計的聚類算法中，需要人為設(shè)置的參數(shù)是完整的K-means算法執(zhí)行次數(shù)M；單詞權(quán)重改變的方法不同。Yanjun Li等是根據(jù)單詞的選擇情況，用小于零的參數(shù)f乘以未被選擇的單詞，以此來實現(xiàn)單詞權(quán)重的改變，而劉濤等則是采用逐輪累加的方法來實現(xiàn)單詞權(quán)重的改變。采用的特征選擇方法不同。Yanjun Li等提出了一種新的特征選擇方法CHIR，而劉濤等采用的是那些常規(guī)的特征選擇方法，如CHI、IG等。通過以上比較可知，特征選擇與文本聚類的融合形式雖然是不盡相同的，但是，卻是萬變不離其宗。它們都是在聚類結(jié)果上使用特征選擇的思想，將那些非常有效但無法直接應(yīng)用到文本聚類上的有監(jiān)督的特征選擇方法成功地應(yīng)用到文本聚類上?，F(xiàn)有的研究成果也一再說明，基于特征選擇的文本聚類方法不僅能夠極大地降低文本數(shù)據(jù)空間的維度，而且使文本聚類的性能有了顯著的提高。因此，筆者相信，如何在實際應(yīng)用中更好地引入學(xué)習(xí)機(jī)制，將特征選擇融入到文本聚類中，從而提高文本聚類效率是一個好的研究方向。同時，探索新的特征選擇方法和聚類算法，改進(jìn)現(xiàn)有算法的缺陷仍然是學(xué)術(shù)界在文本聚類分類上的研究熱點之一。參考文獻(xiàn)：1蘇新寧.信息檢索理論與技術(shù)，2004，北京：科學(xué)技術(shù)文獻(xiàn)出版社.2Jos Martnez Sotoca,Filiberto Pla.Supervised featureselection by clustering using conditional mutual information-based distancesJ.Pattern Recognition,2010,43(6):20682081.3Yanju