王秀慧，王麗珍，麻淑芳

（山西大同大學 教育科學與技術學院，山西 大同037009）

0 引 言

文本聚類是數(shù)據(jù)挖掘領域研究的一個熱點。傳統(tǒng)聚類算法像基于劃分的K－MEANS、K－MEDOIDS，基于層次的CURE等可以實現(xiàn)文本聚類，但是這些算法大多采用向量空間模型表示文本，容易產(chǎn)生“高維效應”，直接導致聚類算法效率低下且聚類結(jié)果不準確。針對這樣的問題，Bei和Xu在論文frequent term－based text clustering中提出了一種基于頻繁項集的文本聚類方法FTC （frequent term－based clustering）。

FTC算法保證了高維度數(shù)據(jù)聚類的效率，有效地降低了時間開銷，可伸縮性良好。但是，由于直接在文本的關鍵詞集上挖掘頻繁項集而未考慮詞語間的語義聯(lián)系，因此聚類質(zhì)量并沒有得到明顯提高。另外，具有多個主題是文本的一個自然屬性，而FTC把一個文本硬性地劃分到唯一結(jié)果簇中，不能獲取最優(yōu)聚類結(jié)果。針對FTC 算法存在的不足，本文進行了有效改進。首先，借助某種中文語料庫把文本的關鍵詞集映射到概念集合，在更高更抽象的級別挖掘滿足最小支持度的頻繁項集并獲取聚類候選簇。由于充分考慮了關鍵詞間的語義聯(lián)系，相似文本將會更好的聚集。其次，定義了簇間相似度度量公式，以決定簇間是否應該存在重疊，合理實現(xiàn)了對候選簇的軟分離，保證了聚類結(jié)果全局最優(yōu)。實驗結(jié)果表明，改進后的FTC 算法聚類準確度更高。

1 FTC算法介紹

FTC算法是一種基于頻繁項集的文本聚類算法，它由Bei和Xu提出。該算法的基本思想是：從文本集合中挖掘所有滿足最小支持度的頻繁項集，并把包含頻繁項集的文本集合看成一個候選簇，然后通過一種貪心策略，重復選擇與其它候選簇重疊度最小的作為結(jié)果簇，直到結(jié)果簇集合覆蓋到所有文本為止［1］。

在FTC中，假定文本數(shù)據(jù)庫D 包含D1，D2…Dm文本，每一個文本Di由包含在該文本的關鍵詞集合Ti表示。在T＝｛T1，T2，…，Tm｝上挖掘滿足最小支持度minsup的頻繁項集，得到頻繁項集集合F＝ ｛F1，F(xiàn)2，…，F(xiàn)n｝。對于任一Fi，如果包含k個頻繁詞，則稱之為頻繁k項集，相應的候選簇稱之為k階簇。k個頻繁詞包含在該簇的所有文本內(nèi)，反應了文本集的共性，可作為該簇的類別標簽。

由于一個文本通常包含多個頻繁項集，因此候選簇之間會存在重疊現(xiàn)象。定義熵重疊度 （entropy overlap）E O（Ci）來衡量Ci與其它候選簇的重疊情況

其中，fj為Dj所支持的頻繁項集個數(shù)。

E O（Ci）反映了Ci所支持的頻繁項集在其它候選簇中的分布情況。顯然，值越大，Ci與其它簇的重疊度越高。當值為0時，Ci所包含的文檔都不支持其它頻繁項集，此時Ci與其它簇無重疊。

在對文本進行分詞、停用詞過濾等預處理后，去除大部分噪聲詞，得到關鍵詞集合T＝ ｛T1，T2，…，Tm｝，F(xiàn)TC在此基礎上再進行聚類，該算法詳細步驟描述如下：

輸入：文本數(shù)據(jù)庫D 的關鍵詞集T

輸出：結(jié)果簇集C

（1）從T 中挖掘滿足最小支持度minsup 的頻繁項集F＝ ｛F1，F(xiàn)2，…，F(xiàn)n｝，每個頻繁項集Fi對應的文本集合構(gòu)成候選簇Ci。

（2）聚類結(jié)果簇集C＝ ｛｝。

（3）計算每個候選簇Ci的熵重疊度。

（4）把熵重疊度最小的Ci加入結(jié)果簇集C中。

（5）對于包含在Ci中的任一文本Dj，如果Dj屬于其它候選簇Cj則從Cj中刪除Dj。

（6）從候選簇中刪除Ci。

（7）判斷聚類結(jié)果簇是否覆蓋所有文本，如果沒有返回 （3）繼續(xù)執(zhí)行，否則算法終止。

Bei和Xu通過實驗驗證，F(xiàn)TC 算法的聚類質(zhì)量比bisecting k－means更高，同時時間花銷較少，具有處理大型數(shù)據(jù)集的能力。但是，考慮到兩個文本對象的相似度并不是單純的由文本內(nèi)出現(xiàn)相同的詞語決定，比如 “土豆”和“馬鈴薯”，這兩個詞詞形不同，但語義是完全相同的。如果聚類簡單的只考慮詞形，而忽略了詞語之間語義聯(lián)系的話，包含 “土豆”和 “馬鈴薯”的兩個文本將被劃分到不同的簇中，顯然會影響聚類準確性。另外，文本具有多個主題是其一個自然屬性，例如一段關于醫(yī)藥的價格報道文本，就應該歸入醫(yī)藥和財經(jīng)兩個類別中。而FTC 聚類是一種硬劃分，即每個文本被唯一的劃分到一個簇中，未能體現(xiàn)出文本的多主題性。針對FTC 算法存在的兩點不足，本文進行了有效改進，如2所述。

2 FTC算法改進

對FTC算法的改進體現(xiàn)在兩個方面：一方面，把文本的關鍵詞集映射成概念集合，以概念集合作為挖掘頻繁項集的基礎；另一方面，定義簇間相似度度量公式，以便于把多主題文本劃分到不同結(jié)果簇中，實現(xiàn)聚類軟劃分。改進后的FTC 算法稱為基于語義的FTC 算法 （semanticsbased FTC，SFTC）。

2.1 關鍵詞概念獲取

為了準確有效的挖掘文本關鍵詞之間的潛在語義關系，需借助某種中文語料庫來獲取關鍵詞所代表的概念。目前，知網(wǎng)作為一個知識系統(tǒng)，在中文信息處理領域發(fā)揮的作用越來越大，因此，本文選定知網(wǎng)［2］作為概念獲取的語料庫。

知網(wǎng)有兩個非常重要的概念：義項和義原。其中義項是對詞的一個描述，主要用DEF來描述。義原是不可分割的最小語義單位，沒有歧義。DEF 由多個義原組合而成，知網(wǎng)用有限的義原去定義無限的義項［3］。根據(jù)義原的這些特點，本文采用義原作為文本中關鍵詞在語義上的概念。為了把文本集的關鍵詞映射成知網(wǎng)中的某個義原，需先處理未登錄詞、多義詞。

2.1.1 處理未登錄詞

考慮到知網(wǎng)收錄詞條的有限性，文本中的有些詞在知網(wǎng)中查不到，把這些詞稱為未登錄詞。對于未登錄詞，如果出現(xiàn)頻率很低，直接過濾掉，如果出現(xiàn)頻率較高，則直接把它歸入文本的概念集合中。

2.1.2 處理多義詞

由于中文詞語的多義性，文本中的一個關鍵詞可能存在多個義項，如 “出口”一詞，可以是名詞，也可以是動詞。對應到知網(wǎng)中有兩個義項，其中名詞 “出口”的DEF為 ｛location｜位置：PartPosition＝ ｛mouth｜口｝，belong＝｛building｜建筑物｝， ｛GoInto｜進入：location＝ ｛～｝｝，｛GoOut｜出去：location＝ ｛～｝｝｝，動詞 “出口”的DEF為 ｛transport｜運 送：LocationFin ＝ ｛place ｜地 方：PlaceSect＝ ｛country｜國家｝，domain＝ ｛politics｜政｝，modifier＝ ｛foreign｜外國｝｝，domain＝ ｛commerce｜商業(yè)｝｝。對于有多個義項的關鍵詞，需要首先為其選擇合適的義項，即詞義排岐。由于義原的組合說明了知網(wǎng)中各個義項的含義，因此描述義項的義原在某文本中出現(xiàn)次數(shù)越多，表明該義項更符合原文本的語義環(huán)境。定義了義項對原文的重要程度公式

式中：tf（tj）——多義詞w 的第i個DEF中的第j個義原tj在文本中出現(xiàn)的頻率，sumtf（wi）——w 的第i個DEF中所有義原在文本中出現(xiàn)的頻次之和。顯然，sumtf（wi）值越大，表明該DEF更符合原文本的上下文環(huán)境。因此從w 的若干義項中選擇sumtf 值最大的作為該關鍵詞的最終義項。

2.1.3 概念獲取

知網(wǎng)中的單義登錄詞只有一個義項，可以直接獲得其DEF。多義登錄詞有多個義項，通過2.1.2 描述的方法可以唯一確定該詞的DEF。為了獲取關鍵詞所對應的概念，需從DEF所包含的多個義原中選擇主題描述能力最強的作為該詞的最終概念。

DEF中各個義原的語義描述能力不同。比如 “長跑”一詞，其DEF＝ ｛fact｜事情：CoEvent＝ ｛exercise｜鍛煉｝，domain＝ ｛sport｜體育｝｝。顯然 “事情”這個義原所含的語義信息很少，查詢義原概念樹可知其位于第二層，層次越低，則語義描述能力越弱。對于這類義原，本文稱之為弱義原，應該過濾掉。像 “人”、“地方”、“萬物”、“屬性”等，都屬于弱義原。為了實現(xiàn)義原過濾，本文首先從知網(wǎng)中把所有的弱義原提取出來并存放在一個數(shù)據(jù)庫表中，在進行義原抽取時，碰到此類義原，直接過濾即可。

過濾掉弱義原后，DEF 里還可能包含多個義原，為了選擇DEF中的某個義原作為最終概念，本文借鑒了文獻［4］的方法。即：計算出各個義原的權(quán)值，然后選擇權(quán)值最大的作為最終義原。

由知網(wǎng)的結(jié)構(gòu)特點可知，義原之間存在8 種關系，但最重要的是上下位關系。本文只考慮上下位關系，則知網(wǎng)系統(tǒng)對應9個義原概念樹，每個義原是概念樹中的一個節(jié)點。顯然，影響義原權(quán)重的因素有二，一是義原所在的概念樹，一是義原在概念樹中的層次。

由于一篇文本中能表達文本主題的大多是名詞和動詞，因此9棵概念樹中最重要的是實體樹和事件樹。文獻 ［4］簡單的將義原所處的實體樹或事件樹的權(quán)重設為1.0 和0.25而未考慮義項的詞性，實際上義原的重要程度跟義項的詞性也有關。如 “出口”作動詞使用時其DEF＝ ｛transport｜運送：LocationFin＝ ｛place｜地方：PlaceSect＝｛country｜國 家｝，domain＝ ｛politics｜政｝，modifier＝｛foreign｜外國｝｝，domain＝ ｛commerce｜商業(yè)｝｝。在它的若干義原中，“運送”的語義描述能力更強，更具代表性。而如果采用文獻 ［4］的方法， “地方”的權(quán)值要更大，顯然計算結(jié)果不準確。為使權(quán)重計算更準確，本文根據(jù)義項的詞性來給義原概念樹賦予不同權(quán)值，當義項為名詞時，實體樹權(quán)重要偏大，而當義項為動詞時，事件樹權(quán)重偏大。其它概念樹如專有名詞樹、屬性樹等對一個義項的描述能力較弱，本文簡單將權(quán)重都設置為一個比較小的值。

義原作為概念樹中的一個節(jié)點，所處位置不同，義原的語義描述能力也不同。由知網(wǎng)結(jié)構(gòu)特點可知，義原在概念樹中層次越深，且下位義原越少，則描述能力越強。綜合義原所處的概念樹以及在概念樹中的層次情況，可得義原的權(quán)值計算式

式中：w（DEFi）——DEF中第i個義原的權(quán)值，wtree是根據(jù)義項的詞性所確定的義原所在的概念樹的權(quán)重，droot——該義原在概念樹中的層次，n——下位義原數(shù)。參數(shù)a、b、c為可調(diào)節(jié)參數(shù)，用來控制義原權(quán)值的取值范圍。采用式（3）計算出DEF中每個義原的權(quán)值，選擇權(quán)值最大的義原作為關鍵詞的最終概念，完成了關鍵詞的概念獲取。

2.2 候選簇的生成與簇相似度

2.2.1 生成候選簇

FTC在文本集合的關鍵詞集中直接挖掘頻繁項集，然后以每個頻繁項集所支持的文本集合作為候選簇或初始簇，由于未考慮關鍵詞間的語義聯(lián)系，會導致最終聚類結(jié)果質(zhì)量不高。本文依據(jù)2.1中的方法，把文本的關鍵詞集映射到知網(wǎng)中的概念集合，在更高更抽象的概念集合中挖掘頻繁項集。由于事先考慮了關鍵詞間的語義聯(lián)系，聚類結(jié)果將會更準確。

挖掘頻繁項集的算法很多，具有代表性的有自底向上遍歷的Aprior 算法、自頂向下遍歷的Max－Miner 算法等［5］。而最近提出的FP－Growth算法不產(chǎn)生候選項集，直接產(chǎn)生頻繁模式項集，且對數(shù)據(jù)庫的掃描限制在兩遍，有效地提高了挖掘效率［6，7］。因此，本 文采用FP－Growth 算法從文本的概念集合中挖掘頻繁項集。把每個頻繁項集看做一個候選簇，所有支持該頻繁項集的文本被劃分到該簇中。頻繁項集中的詞語反映了該候選簇的共性，可作為簇標簽使用。

2.2.2 定義簇相似度

對于候選簇Ci和Cj，如果兩者所支持的頻繁項集存在交集，包含在兩簇內(nèi)的文本存在重疊，則兩簇存在一定的相似性。定義簇間相似度度量公式見式 （4）

式中：Fi——描述簇Ci的頻繁項集，doc（Ci）——簇Ci包含的文本集。即簇間相似度定義為兩個簇所對應的頻繁項集相交個數(shù)占所有頻繁項集的百分比與簇間相交文本占數(shù)所有文本的百分比的疊乘。Sim（Ci，Cj）的取值范圍為 ［0，1］，值越大，相似度越高，當兩簇完全相同時，Sim（Ci，Cj）＝1。

在FTC算法的步驟 （5）中，如果選定候選簇Ci為結(jié)果簇，則包含在Ci中的任一文本Di，如果存在于剩余候選簇Cj，則直接從Cj中刪除Di，根本沒有考慮文本具有多主題性的特點。鑒于此，本文首先計算出Sim（Ci，Cj），如果Sim（Ci，Cj）小于閾值α，表明兩簇所表達的主題不一致，此時應保留Cj中的文本Di；反之，Sim（Ci，Cj）大于閾值α，表名兩簇主題相似，此時應刪除Cj中的文本Di，這樣合理的實現(xiàn)了聚類結(jié)果的軟劃分。

2.3 SFTC算法描述

在把文本的關鍵詞集映射成概念集合后，結(jié)合式 （4）得到SFTC算法，詳細步驟描述如下：

輸入：文本數(shù)據(jù)庫D 的概念集合S

輸出：聚類結(jié)果簇集C

（1）利用FP－Growth從概念集合S中挖掘滿足最小支持度minsup 的頻繁項集F＝ ｛F1，F(xiàn)2，…，F(xiàn)n｝，根據(jù)頻繁項集構(gòu)造候選簇集 ｛C1，C2，…，Cn｝。

（2）置聚類結(jié)果簇集C＝ ｛｝。

（3）計算每個候選簇Ci的熵重疊度。

（4）把熵重疊度最小的Ci加入結(jié)果簇集C 中。

（5）對于包含在Ci中的任一文本Dj，如果Dj屬于其它候選簇Cj，根據(jù)式 （4）計算簇間相似度Sim（Ci，Cj）。

（6）如果Sim（Ci，Cj）＞α，刪除Cj中的Dj，否則保留。

（7）刪除候選簇中的Ci。

（8）判斷聚類結(jié)果簇是否覆蓋所有文本，如果沒有返回 （4）繼續(xù)執(zhí)行，否則算法終止。

3 實驗結(jié)果與分析

為了測試SFTC 算法的性能，本文采用了兩組數(shù)據(jù)，文本集一選自大同地區(qū)科學數(shù)據(jù)共享平臺中的8000條科學數(shù)據(jù)，文本集二選自搜狗實驗室的全網(wǎng)新聞數(shù)據(jù)－sougou－CA［8］，從中隨機選擇了5000 篇文本，并使用目前比較常用的F－measure方法進行結(jié)果評價。

3.1 F－measure

F－measure是一種基于人工標注的外部評價標準，它綜合了召回率和準確率兩種評價指標［9，10］。對于類Ki和簇Cj，召回率和準確率的公式定義見式 （5）和式 （6）

其中，nij表示簇Cj中屬于類Ki中的文本數(shù)。由召回率和準確率可得到表示簇Cj描述類Ki能力的計算公式

對于每一個Ki，都對應一個最能描述它的結(jié)果簇Cj，即maxCj∈C｛F （Ki，Cj）｝。據(jù)此定義F（C），它表示所有類的maxCj∈C｛F （Ki，Cj）｝加權(quán)之和。其定義見式 （8）

F（C）的取值范圍 ［0，1］，值越大表示聚類質(zhì)量越好。

3.2 聚類質(zhì)量評價

為了測試SFTC 算法的聚類質(zhì)量，選取bisecting kmeans和FTC 與本文算法進行比較。其中，bisecting kmeans隨機選擇初始聚類中心，F(xiàn)TC 和SFTC 的最小支持度相同，取5%。Bisecting k－means和FTC 在文本的關鍵詞集上實現(xiàn)聚類，SFTC 在關鍵詞集所對應的概念集合中完成聚類。3種算法在兩個文本集合上的聚類結(jié)果見表1。

表1 3種算法F值比較

從表1可以看出，SFTC 在兩個文本集上的F 值比bisecting k－means和FTC都要高，表明SFTC 算法確實提高了聚類質(zhì)量。究其原因，主要有兩個方面：一是因為用知網(wǎng)中的概念代替文本的關鍵詞，使得聚類在更抽象的概念集合上完成，確保了同類文本更好的聚集；二是把多主題文本劃分到不同的相關簇中，使得聚類結(jié)果更符合人的思維。

3.3 性能分析

一個聚類算法只有當執(zhí)行效率得到保證時才是可行的。為了測試SFTC算法的運行效率，本文采用大同大區(qū)科學數(shù)據(jù)共享平臺中的8000條科學數(shù)據(jù)作為測試對象。3種算法在科學數(shù)據(jù)集上的運行時間如圖1所示。

圖1 3種算法在同一數(shù)據(jù)集上的時間開銷比較

從圖1可以看出，隨著文本數(shù)的逐漸增大，3種算法的運行時間也在不斷增加。但是SFTC 比其它兩種算法的運行時間都要低，而且當文本數(shù)增加到一定程度時，SFTC運行時間增加比較平緩。這主要是因為SFTC 在文本的概念集合上進行聚類。由于概念集合建立在知網(wǎng)的有限義原基礎之上，因此維度得到明顯的降低。在一個維數(shù)較低的空間實現(xiàn)聚類，SFTC運行時間相對于其它算法肯定會減少。

從上述實驗結(jié)果可以看出，SFTC 算法無論是在聚類質(zhì)量上還是在算法性能上都有了一定的提高。

4 結(jié)束語

本文主要針對FTC算法在實現(xiàn)文本聚類時未考慮詞語之間語義聯(lián)系以及文本集硬劃分聚類的問題，提出了一種結(jié)合語義的改進FTC文本聚類算法。通過引入知網(wǎng)把文本的關鍵詞集映射到更抽象的概念集合，以概念集合作為發(fā)現(xiàn)頻繁項集的基礎，有效實現(xiàn)了相關文本在語義層面的更好聚集。通過定義簇間相似度度量公式合理實現(xiàn)了對聚類結(jié)果簇的軟分離，使得最終聚類結(jié)果更符合人的思維。實驗結(jié)果表明，改進后的算法在保證性能的前提下有效提高了聚類的質(zhì)量。

［1］ZHOU Chong.Document clustering in search engine ［D］.Wuhan：Huazhong University of Science and Technology，2009 （in Chinese）. ［周翀.搜索引擎中文檔聚類方法研究［D］.武漢：華中科技大學，2009.］

［2］DONG Zhendong，DONG Qiang.HowNet［OL］. ［2013－05－01］.http：／／www.keenage.com／zhiwang／c＿zhiwang.html（in Chinese）.［董振東，董強.知網(wǎng) ［OL］. ［2013－05－01］.http：／／www.keenage.com／zhiwang／c＿zhiwang.html.］

［3］GUO Chong，ZHANG Yangsen.Study of semantic automatic error－detecting for Chinese text based on sememe matching of HowNet［J］.Computer Engineering and Design，2010，31（17）：3924－3928 （in Chinese）. ［郭充，張仰森.基于 《知網(wǎng)》義原搭配的中文文本語義級自動查錯研究 ［J］.計算機工程與設計，2010，31 （17）：3924－3928.］

［4］BAI Qiuchan，JIN Chunxia，ZHOU Haiyan.Text clustering algorithm based on concept vector［J］.Computer Engineering and Applications，2011，47 （35）：155－157 （in Chinese）.［白秋產(chǎn)，金春霞，周海巖.概念向量文本聚類算法 ［J］.計算機工程與應用，2011，47 （35）：155－157.］

［5］YAO Xiaoling.Research on fast mining frequent itemsets algorithm ［D］.Changsha：Hunan University，2010 （in Chinese）. ［姚曉玲.快速頻繁項集挖掘算法研究 ［D］.長沙：湖南大學，2010.］

［6］HE Zhongsheng，ZHUANG Yanbin.Algorithm of mining frequent itemset based on Apriori ＆Fp－growth［J］.Computer Technology and Development，2008，18 （7）：45－47（in Chinese）.［何中勝，莊燕濱.基于Apriori ＆Fp－growth的頻繁項集發(fā)現(xiàn)算法 ［J］.計算機技術與發(fā)展，2008，18 （7）：45－47.］

［7］XIAO Jie.Research on text clustering based on frequent item set［D］.Changsha：Central South University，2009 （in Chinese）.［肖杰.基于頻繁項集的文本聚類方法研究 ［D］.長沙：中南大學，2009.］

［8］Sogou Labs.The news network ［DB／OL］.［2013－04－10］.http：／／www.sogou.com／labs／dl／ca.html（in Chinese）.［搜 狗語實驗室.全網(wǎng)新聞數(shù)據(jù) ［DB／OL］.［2013－04－10］.http：／／www.sogou.com／labs／dl／ca.html.］

［9］SUN Aixiang，YANG Xinhua.Evaluation of text clustering effect［J］.Journal of Shandong University of Technology，2007，21 （5）：65－68 （in Chinese）.［孫愛香，楊鑫華.關于文本聚類有效性評價的研究 ［J］.山東理工大學學報，2007，21 （5）：65－68.］

［10］WANG Xinbo.Research and application of metadata clustering algorithm based on OAI－PMH ［D］.Taiyuan：Taiyuan University of Science ＆Technology，2009 （in Chinese）.［王新波.基于OAI－PMH 協(xié)議的元數(shù)據(jù)聚類算法及應用研究［D］.太原：太原科技大學，2009.］