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