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

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