結(jié)合語(yǔ)義的改進(jìn)FTC文本聚類(lèi)算法

王秀慧，王麗珍，麻淑芳

（山西大同大學(xué) 教育科學(xué)與技術(shù)學(xué)院，山西 大同037009）

0 引 言

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

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

1 FTC算法介紹

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

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

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

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

E O（Ci）反映了Ci所支持的頻繁項(xiàng)集在其它候選簇中的分布情況。顯然，值越大，Ci與其它簇的重疊度越高。當(dāng)值為0時(shí)，Ci所包含的文檔都不支持其它頻繁項(xiàng)集，此時(shí)Ci與其它簇?zé)o重疊。

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

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

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

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

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

（3）計(jì)算每個(gè)候選簇Ci的熵重疊度。

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

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

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

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

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

2 FTC算法改進(jìn)

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

2.1 關(guān)鍵詞概念獲取

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

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

2.1.1 處理未登錄詞

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

2.1.2 處理多義詞

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

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

2.1.3 概念獲取

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

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

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

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

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

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

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

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

2.2.1 生成候選簇

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

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

2.2.2 定義簇相似度

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

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

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

2.3 SFTC算法描述

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

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

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

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

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

（3）計(jì)算每個(gè)候選簇Ci的熵重疊度。

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 F－measure

F－measure是一種基于人工標(biāo)注的外部評(píng)價(jià)標(biāo)準(zhǔn)，它綜合了召回率和準(zhǔn)確率兩種評(píng)價(jià)指標(biāo)［9，10］。對(duì)于類(lèi)Ki和簇Cj，召回率和準(zhǔn)確率的公式定義見(jiàn)式 （5）和式 （6）

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

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

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

3.2 聚類(lèi)質(zhì)量評(píng)價(jià)

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

表1 3種算法F值比較

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

3.3 性能分析

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

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

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

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

4 結(jié)束語(yǔ)

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

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

［2］DONG Zhendong，DONG Qiang.HowNet［OL］. ［2013－05－01］.http：／／www.keenage.com／zhiwang／c＿zhiwang.html（in Chinese）.［董振東，董強(qiáng).知網(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)》義原搭配的中文文本語(yǔ)義級(jí)自動(dòng)查錯(cuò)研究 ［J］.計(jì)算機(jī)工程與設(shè)計(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)，金春霞，周海巖.概念向量文本聚類(lèi)算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47 （35）：155－157.］

［5］YAO Xiaoling.Research on fast mining frequent itemsets algorithm ［D］.Changsha：Hunan University，2010 （in Chinese）. ［姚曉玲.快速頻繁項(xiàng)集挖掘算法研究 ［D］.長(zhǎng)沙：湖南大學(xué)，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的頻繁項(xiàng)集發(fā)現(xiàn)算法 ［J］.計(jì)算機(jī)技術(shù)與發(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）.［肖杰.基于頻繁項(xiàng)集的文本聚類(lèi)方法研究 ［D］.長(zhǎng)沙：中南大學(xué)，2009.］

［8］Sogou Labs.The news network ［DB／OL］.［2013－04－10］.http：／／www.sogou.com／labs／dl／ca.html（in Chinese）.［搜 狗語(yǔ)實(shí)驗(yàn)室.全網(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）.［孫愛(ài)香，楊鑫華.關(guān)于文本聚類(lèi)有效性評(píng)價(jià)的研究 ［J］.山東理工大學(xué)學(xué)報(bào)，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ù)聚類(lèi)算法及應(yīng)用研究［D］.太原：太原科技大學(xué)，2009.］