一種基于頻繁詞集表示的新文本聚類方法

張雪松 賈彩燕

(交通數(shù)據(jù)分析與數(shù)據(jù)挖掘北京市重點實驗室(北京交通大學(xué)) 北京 100044)

(北京交通大學(xué)計算機與信息技術(shù)學(xué)院 北京 100044)

(15120467@bjtu.edu.cn)

文本聚類是文本挖掘中的一個重要課題，是指在沒有人工干預(yù)的情況下，將大量無標(biāo)注的數(shù)據(jù)集根據(jù)文本間相似性劃分成若干個類，使得同類內(nèi)的文本相似度較大而類間的文本相似度較低.在文本聚類中要解決三大問題:1)數(shù)據(jù)的高維問題，解決此問題需要處理稀疏的數(shù)據(jù)空間或引用數(shù)據(jù)降維的方法；2)聚類算法在大規(guī)模文本集上聚類效果的問題，即聚類算法要有很好的精度和可擴展性；3)對類簇的主題描述，一個好的主題描述方法能夠讓人們直觀地了解每個類簇所代表的主題.在文本聚類中,向量空間模型 (vector space model, VSM)[1]是常用的模型，在VSM模型中，每個文本集中的詞作為空間坐標(biāo)系中的一個維度，每個文本是特征空間中的1個向量.盡管基于VSM的K-means聚類方法在文本聚類中被廣泛應(yīng)用，但這種文本表示的方法存在高維問題，向量空間中的特征維度過高導(dǎo)致文本向量過于稀疏，影響聚類的效果，并且VSM模型使用單個詞匯作為特征，忽略了詞之間的語義關(guān)系.

基于頻繁詞集的文本聚類方法，可以解決傳統(tǒng)文本表示的高維和語義缺失問題.頻繁詞集是指同時出現(xiàn)在一定比例的文本中的詞的集合，這些集合在某種程度上能夠反映出一些關(guān)于主題的語義.基于頻繁詞集的文本聚類首先挖掘出文本集中的頻繁詞集，將文本指派到與其具有相同主題的頻繁詞集中[2].Beil等人[3]提出FTC(frequent term-based clustering)算法和HFTC(hierarchical frequent term-based clu-stering)算法，該算法將挖掘出的頻繁詞集當(dāng)作聚類初始簇，采用貪婪策略優(yōu)先選擇簇重疊度最小的頻繁詞集進行聚類，該算法采用一種局部最優(yōu)策略，對項集的選擇順序過于依賴，算法效率較低.Fung等人[4]提出一種層次聚類方法，該算法同樣將挖掘出的頻繁詞集當(dāng)作初始簇，為解決類重疊問題，將每個文本通過打分函數(shù)劃分到最適合的簇中，然后構(gòu)建樹，運用剪枝策略進行聚類.Zhang等人[5]提出的MC(maximum capturing)算法將挖掘出的頻繁詞集當(dāng)作特征來表示文本，通過計算文本間共有的詞集個數(shù)來度量文本間相似性并直接對文本進行聚類.為了充分挖掘語義關(guān)系，Hernández-Reyes 等人[6]考慮了文本中詞集的語序，提出了基于最大頻繁序列(maximal frequent sequence, MFS)的文本聚類方法.

除了基于頻繁詞集的文本聚類方法，基于LDA(latent Dirichlet allocation)的文本聚類算法[7]、SPK-means(spherical-K-means)算法[8]和GNMF(graph regularized nonnegative matrix factorization)算法[9]也是較流行的文本聚類方法.其中，基于LDA的文本聚類方法基于這樣一個假設(shè)：一個文本中會包含多個主題，每個主題生成各種詞語的概率服從多項分布，通過該聚類方法會得到一個文本在不同主題下的分布情況，即文本在各主題下的概率，最后將文本指派到隸屬度最高的主題中.并且，通過統(tǒng)計出各個主題下詞的概率分布，那些在該主題上概率高的詞能夠非常好地描述該主題的語義.GNMF是一種基于非負(fù)矩陣分解(nonnegative matrix factorization, NMF)[10]的方法，該方法基于這樣的假設(shè)：如果2個數(shù)據(jù)點在高維空間具有相近的幾何分布，則在降維后的空間中2個數(shù)據(jù)點應(yīng)該也相近.而NMF方法是近年來興起的無監(jiān)督聚類方法，其本身也是一種很有效的數(shù)據(jù)降維的方法，因此GNMF在文本聚類中可以解決文本維度過高的問題.SPK-means算法運用余弦相似度作為衡量文本間相似度的指標(biāo)，將文本與初始中心間的相似度總和作為待優(yōu)化的代價函數(shù)，在迭代過程中最大化全局代價函數(shù)并更新聚類中心.SPK-means運行速度快、內(nèi)存消耗較小，因為采用余弦相似度，能夠有效地處理大文本數(shù)據(jù)集[11].

本文引用頻繁詞集理論，提出了一種基于頻繁詞集的文本聚類方法(frequent itemsets based document clustering method, FIC).該方法首先挖掘出頻繁詞集，運用頻繁詞集來構(gòu)建文本表示模型.將每個文本看作網(wǎng)絡(luò)中的節(jié)點，通過度量2個文本間的相似性來構(gòu)建邊，從而構(gòu)建成一個文本網(wǎng)絡(luò)，運用社區(qū)劃分的方法來實現(xiàn)文本的聚類.該方法不僅有效地降低了文本表示的維度，而且文本社區(qū)的引入建立了文本之間的關(guān)聯(lián)關(guān)系，使得聚類效果得到了有效提升.

1 相關(guān)算法介紹

基于頻繁詞集的文本聚類方法是解決數(shù)據(jù)高維問題的一個重要方法，對于聚類精度也比傳統(tǒng)模型有了進一步提高，同時能夠更加具體地描述數(shù)據(jù)集中的每個主題.

1.1 FTC算法

FTC算法首先從文本集中挖掘出所有滿足最小支持度的頻繁詞集，將每個頻繁詞集當(dāng)作聚類的候選簇，然后通過一種貪心策略，從中選擇與其他候選簇重疊度最小的作為結(jié)果簇，直到文本全部被指派到相應(yīng)簇中為止.

由于一個文本通常會包含多個頻繁詞集，因此候選簇之間會出現(xiàn)重疊的現(xiàn)象，即一個文本可能會屬于不同的候選簇，為了消除類間重疊，定義熵重疊度(entropy overlap)EO(Ci)來衡量候選簇Ci與其他候選簇的重疊情況：

(1)

其中，Dj表示文本，fj表示文本Dj所支持的頻繁詞集的個數(shù).式(1)反映了Ci所支持的頻繁詞集在其他候選簇中的分布情況，值越大，Ci與其他簇的重疊度越高.

算法1. FTC算法.

1) 從文本集中挖掘滿足最小支持度(minsup)的頻繁詞集F={F1,F2,…,Fn},每個頻繁詞集Fi對應(yīng)的文本集合構(gòu)成候選簇;

2) 計算每個候選簇Ci的熵重疊度;

3) 把熵重疊度最小的Ci加入結(jié)果簇集C中;

4) 若文本Dj包含在Ci中，則將其在其他候選簇中刪除;

5) 刪除候選簇Ci;

6)判斷文本是否全部包含在結(jié)果簇中，如果沒有則返回3)續(xù)執(zhí)行，否則結(jié)束.

FTC算法雖然在降低文本維度和效率上較傳統(tǒng)基于VSM模型的聚類方法提高了效率，但使用貪心策略選擇結(jié)果簇?zé)o法達(dá)到全局最優(yōu)，且對候選簇的選擇順序有依賴，在選擇結(jié)果簇中會消耗大量時間.

1.2 FIHC算法

FIHC算法由Fung等人[4]提出.步驟分為頻繁詞集挖掘、構(gòu)建初始簇、建樹、剪枝，最后得到樹形結(jié)構(gòu)的結(jié)果簇.此方法基于層次聚類，將文本集中挖掘出的頻繁詞集當(dāng)作初始簇，在解決類重疊問題中，采用一種打分函數(shù)將文本歸到最適合的類簇中，將初始簇構(gòu)建成樹結(jié)構(gòu)，運用剪枝策略來實現(xiàn)聚類.其中的文本歸檔打分函數(shù)為

(2)

其中，Score(Ci←Dj)表示文本Dj屬于類簇Ci的分?jǐn)?shù);global_support代表全局頻繁詞集集合，指的是在所有文本集中滿足最小支持度的所有頻繁詞集;cluster_support表示簇頻繁詞集集合，它指的是將文本指派到其含有的初始簇之后，根據(jù)每個簇內(nèi)的文本中頻繁詞集的出現(xiàn)頻率篩選出大于某一最小支持度的頻繁詞集，并將其作為簇頻繁詞集,簇頻繁詞集是全局頻繁詞集的一個子集;x表示Dj中出現(xiàn)的既屬于全局頻繁詞集集合又屬于簇頻繁詞集集合的詞集;x′表示只屬于全局頻繁詞集集合而不屬于簇頻繁詞集集合的詞集;n(·)是用來統(tǒng)計項集個數(shù)的函數(shù).通過式(2)即可將文本對歸到其最適合的初始簇中.

在樹形結(jié)構(gòu)中，每個節(jié)點代表1個類簇，為了得到指定數(shù)量的類簇或避免類簇描述過于具體，需要對樹進行剪枝.其策略是：通過計算簇之間的相似度，將相似度大于相應(yīng)閾值的2簇合并.公式如下：

(3)

式(3)中通過計算Cb到Ca和Ca到Cb的相似度并取幾何平均來得到2簇間的相似度.式(4)為計算單向相似度的公式.簇間相似度閾值為1，即將相似度大于1的2簇合并.通過這種方法實現(xiàn)對父子節(jié)點和兄弟節(jié)點的剪枝.FIHC算法在聚類效果和時間效率方面均優(yōu)于FTC算法.

1.3 MC算法

MC算法是一種直接對文本進行聚類的方法，利用文本中包含的頻繁詞集來度量文本之間的相似性.此方法運用頻繁詞集來表示每個文本，構(gòu)建成文本相似矩陣A，其中A[i][j]=MC_Sim(Di,Dj).MC聚類的基本思想是：如果2個文本有最高的相似度，則這對文本應(yīng)歸入同一類簇中.例如：如果文本Di和Dj在同一簇中，若文本Dk和Dj有最高的相似度，則Dk將與Di和Dj歸入同一簇中.

算法2. MC算法.

輸入：待聚類的文本集合；

輸出：不同簇下的文本集合.

1) 根據(jù)相似度構(gòu)建相似矩陣A;

2) 尋找A中除0之外的最小相似度值;

3) 尋找具有最大相似度的未被歸類的文本對;

4) 如果步驟3中尋找的最大相似度值與步驟2中的最小相似度值相等，則相應(yīng)的節(jié)點對組成一個新的類簇，否則執(zhí)行下列步驟：①如果文本對中的2個文本中任何一個都未被歸類，則將2個文本對構(gòu)成一個新的類簇;②若文本對中1個文本已被歸類，則另1個文本也同樣歸于此類;③將矩陣A中文本對所對應(yīng)的值置0，返回到步驟3;

5) 如果存在還未被歸類的文本，則將其組成一個新的類簇.

由于在文本聚類中文本的類數(shù)大部分是預(yù)先設(shè)定好的，因此需要對MC算法聚成的類簇進行合并，將不同簇中文本間的相似度值的總和作為簇間的相似度然后進行合并：

(5)

2 FIC算法

FIC算法框架圖如圖1所示.該算法運用頻繁詞集來表示文本和衡量文本間的相似度，這些頻繁詞集同時可以反映出一定的語義關(guān)系，使得相同主題下的文本間相似度較之不同主題下的文本相似度更高，運用頻繁詞集表示的文本相較于傳統(tǒng)的VSM模型能夠有效地降低維度，減小數(shù)據(jù)稀疏的問題.在構(gòu)建文本網(wǎng)絡(luò)后，可以引用社區(qū)劃分或譜聚類的方法進行文本聚類，使得聚類方法更加靈活.

Fig. 1 Procedure of FIC圖1 FIC算法流程圖

圖1中的主要步驟為：數(shù)據(jù)預(yù)處理、頻繁詞集挖掘、文本表示、構(gòu)建文本網(wǎng)絡(luò)、社區(qū)劃分和主題描述.數(shù)據(jù)預(yù)處理對原始數(shù)據(jù)進行分詞和去掉停用詞；然后對處理完的數(shù)據(jù)進行頻繁詞集挖掘，將用頻繁詞集表示的文本構(gòu)建成文本網(wǎng)絡(luò)之后進行社區(qū)劃分，每個社區(qū)即為文本聚類中的一個類簇，簇中的節(jié)點即為文本；再對劃分好的簇進行主題描述.下面將具體介紹算法中的關(guān)鍵步驟.

2.1 頻繁詞集挖掘

本文采用FP-Growth[12]算法來挖掘頻繁詞集，在進行頻繁詞集挖掘時，根據(jù)文本的數(shù)量來設(shè)置最小支持度，對進行特征選擇之后的文本直接進行頻繁詞集挖掘.下面給出定義：

定義1. 文本數(shù)據(jù)庫.將對文本進行分詞、去停用詞之后的文本組成文本數(shù)據(jù)庫D={D1,D2,…,Dn}.

定義2. 頻繁詞集.通過頻繁詞集挖掘，得到頻率大于最小支持度的頻繁詞集集合F={F1,F2,…,Fm},其中Fi表示1個頻繁詞集，1個頻繁詞集中包含1個或多個詞語Fi={w1,w2,…,wt}.

2.2 文本表示模型

較之傳統(tǒng)的VSM模型，本文采用基于頻繁詞集的文本表示模型.即用挖掘出的頻繁詞集來表示每個文本，構(gòu)建文本-頻繁詞矩陣M.其中矩陣M為0-1矩陣，通過衡量文本中是否含有頻繁詞集來賦值：

(6)

其中，M[i][j]表示矩陣M中文本Di對于頻繁詞集Fj的值，若文本Di中含有頻繁詞集Fj，則M[i][j]=1，否則M[i][j]=0.對于一個具體的文本可以直接將其中的特征單詞用頻繁詞集來代替.通過這種方法可以有效降低文本特征維度，解決了文本稀疏的問題.頻繁詞集本身可以在某些程度上反映出文本的主題，它基于這樣的假設(shè)：若某些詞匯經(jīng)常同時出現(xiàn)在同一文本中，則它們能夠呈現(xiàn)出一定的語義關(guān)系，例如：{apple}表示水果類，{window}表示裝飾類，若兩詞經(jīng)常出現(xiàn)在同一文本，則作為頻繁詞集{apple,window}可以表示出計算機類.因此以頻繁詞集作為特征在度量文本間相似度時可以避免不同類別間的文本產(chǎn)生過大的相似度而影響聚類效果.

2.3 構(gòu)建文本網(wǎng)絡(luò)

FIC算法將文本集中的每個文本當(dāng)作文本網(wǎng)絡(luò)中的節(jié)點，根據(jù)2文本之間的關(guān)聯(lián)程度來建立邊.文本間的關(guān)聯(lián)程度常常用它們之間的相似度來度量，已有的相似度量方法有很多，例如余弦相似度和歐氏距離.本文采用Jaccard相似度來度量：

(7)

其中,Jaccard_Sim(Di,Dj)表示文檔之間的相似度，分子表示2個文檔之間共有的頻繁詞集的個數(shù)，分母表示2個文檔一共含有的頻繁詞集的個數(shù).通過此方法可以得到文本集中兩兩文本間的相似度權(quán)值，設(shè)置閾值θ，若2邊相似度大于θ則在2個文本間建立1條邊，構(gòu)建成1個文本網(wǎng)絡(luò)G={V,E},其中V為節(jié)點的集合，E為網(wǎng)絡(luò)中邊的集合.文本網(wǎng)絡(luò)的構(gòu)建，不僅使相似的文本間有邊相連，而且也建立了文本與其他文本間的關(guān)聯(lián)關(guān)系.

2.4 社區(qū)劃分

對于上述構(gòu)建的文本網(wǎng)絡(luò)，我們需要對其進行社區(qū)劃分，得到網(wǎng)絡(luò)中不同的社團，通過文本與節(jié)點的對應(yīng)關(guān)系可以將文本直接匹配到對應(yīng)的社區(qū)，即類簇.我們使用硬劃分的社區(qū)劃分方法，每個文本只能被指派到唯一的社區(qū)中，解決了類間重疊的問題.本文中選用K-rank-D[13]與譜聚類[14](spectral clustering)對網(wǎng)絡(luò)進行劃分.

K-rank-D算法是一種網(wǎng)絡(luò)社區(qū)劃分算法，此算法在基于K-means的基礎(chǔ)上，通過計算節(jié)點的pagerank中心性來進行初始中心的選擇，解決了傳統(tǒng)K-means算法中隨機選取初始中心對聚類結(jié)果的影響.此算法具有精度高的優(yōu)點.

譜聚類是一種經(jīng)典的圖切割聚類方法，從圖論的角度來說，聚類問題就相當(dāng)于一個圖的分割問題.即給定一個圖G=(V,E)，頂點V表示各樣本，帶權(quán)的邊表示各樣本之間的相似度，譜聚類的目的是要找到一種合理的分割圖的方法，使得分割后形成若干子圖，連接不同子圖的邊的權(quán)重(相似度)盡可能低，同子圖內(nèi)的邊的權(quán)重(相似度)盡可能高.

算法3. 譜聚類算法.

輸入：待聚類的文本集合；

輸出：不同簇下的文本集合.

1) 根據(jù)數(shù)據(jù)生成圖的鄰接矩陣;

2) 根據(jù)鄰接矩陣生成拉普拉斯矩陣并進行歸一化;

3) 求最小的前K個特征值和對應(yīng)的特征向量，其中K為聚類的類簇個數(shù);

4) 將特征向量用K-means進行聚類.

因此，F(xiàn)IC算法采用以上2種聚類方法，組成FIC-S和FIC-K這2種算法進行文本聚類.

2.5 主題描述

為了能夠更加直觀地了解每個類簇下的主題，我們需要對主題進行描述.對于每一個類簇內(nèi)的文本，統(tǒng)計其中頻繁詞集的出現(xiàn)頻率，將出現(xiàn)頻率較大的頻繁詞集作為主題的描述詞.

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

為了驗證本文提出的文本聚類方法，我們選用3個文本聚類中標(biāo)準(zhǔn)的數(shù)據(jù)集來進行實驗，對照實驗選用常用的基于K-means文本聚類方法[15]、SPK-means、MC、LDA、FIHC、GNMF算法.其中在MC算法中，根據(jù)不同的文本相似度量方案分成MC-1，MC-2，MC-3.這里我們選擇精度較高的MC-1作為對照，在MC-1中2個文本間相似度的值為2個文本含有的共同頻繁詞集的個數(shù).

3.1 數(shù)據(jù)集

本次實驗采用文本聚類常用的標(biāo)準(zhǔn)數(shù)據(jù)集20-Newsgroup*http://kdd.ics.uci.edu/databases/20newsgroups/和Reuters-21578*http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.html，對于中文數(shù)據(jù)，選擇文本分類語料庫搜狗新聞數(shù)據(jù)*http://www.sougou.com/labs/resources/list_yuliao.php.其中，20-newsgroup數(shù)據(jù)包括近20 000篇新聞報道，分為20個不同的新聞組，除了小部分文檔，每個文檔都只屬于一個新聞組；Reuters-21578是文本分類的測試集，其中包含的文檔來自于路透社1987年的新聞，搜狗新聞數(shù)據(jù)包括9個新聞類，共有17 910個文本.

由于FIC算法與MC同樣采用頻繁詞集表示的策略，我們選擇抽取和MC算法同樣量級的數(shù)據(jù)，從以上數(shù)據(jù)集中隨機抽取文檔組成了5組測試集，測試集的詳細(xì)信息如表1～6所示，其中R12,R5，R8來自數(shù)據(jù)集Reuters-21578,N4來自20News-group，C6來自搜狗新聞數(shù)據(jù).

Table 1 Dataset in the Experiment表1 實驗中的數(shù)據(jù)集

Table 2 Description of N4表2 N4數(shù)據(jù)描述

Table 3 Description of R5表3 R5數(shù)據(jù)描述

Table 4 Description of R12表4 R12數(shù)據(jù)描述

Table 5 Description of R8表5 R8數(shù)據(jù)描述

Table 6 Description of C6表6 C6數(shù)據(jù)描述

3.2 聚類評價指標(biāo)

為了測試FIC算法的性能，我們采用文本聚類中常用的外部評價標(biāo)準(zhǔn)F-measure.它經(jīng)常被用作衡量聚類方法的精度，是一種平面和層次聚類結(jié)構(gòu)都適用的評價標(biāo)準(zhǔn).F-measure綜合了召回率和準(zhǔn)確率2種評價指標(biāo)：

(8)

(9)

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

(10)

聚類的總體F-measure值則可用每個類簇的最大F-measure值并采用該類簇的大小加權(quán)之后的總和:

(11)

F-measure值的取值范圍在[0,1]，值越大表示聚類效果越好.

3.3 實驗設(shè)計方案

在進行數(shù)據(jù)的預(yù)處理時，我們運用特征選擇[16]的方法.文本經(jīng)過分詞和去停用詞之后，依然會保留大量與主題不相關(guān)或無意義的單詞，例如Reuters數(shù)據(jù)中的Reuter，write等和一些未過濾的作者姓名單詞.為了只保留那些對劃分文本更有利的特征單詞，本文采用文檔-反文檔頻率(term frequency-inverse document frequency, TF-IDF)方法對文本中的單詞進行進一步過濾.TF-IDF用以評估1個單詞對于1個文件或1個語料庫的其中1份文件的重要程度.詞的重要度隨著它在1個文本中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在文本集中出現(xiàn)的頻率成反比下降：

tfidfi,j=tfi,j×idfi，

(12)

(13)

其中，tfi,j表示單詞i在文本dj中的詞頻，分子是該詞在文本dj中出現(xiàn)的次數(shù)，分母則是在文本dj中所有詞的出現(xiàn)次數(shù)之和.

(14)

其中，idfi表示該詞的反文檔頻率，分子表示語料庫中的文本總數(shù)，分母表示含詞語ti的文本數(shù)目.實驗中我們根據(jù)每個詞的重要度分?jǐn)?shù)進行排序，只保留前3/4的詞.通過此方法可以有效地過濾文本中大量無意義的詞.

3.4 實驗分析

我們在不同的算法上對5組數(shù)據(jù)進行聚類，其中對于K-means，SPK-means，LDA，GNMF，F(xiàn)IC-S這5種不確定型算法分別運行10次取平均值作為最后聚類的精度結(jié)果，每個算法的聚類結(jié)果如表7所示.

從表7中可以看出，F(xiàn)IC算法較之其他方法在精度上有明顯的優(yōu)勢.究其原因主要有3個方面：

1) 在數(shù)據(jù)處理上，我們并不只是分詞和去掉停用詞，為了保留那些更有代表性的詞匯，采用了通過TF-IDF值來篩選特征詞.

2) 運用頻繁詞集來構(gòu)建文本表示模型，文本集中挖掘出的頻繁詞集都在千量集以內(nèi)，較之傳統(tǒng)的VSM模型可將維數(shù)從上萬維度降到只有幾千維，另外，從文本集中挖掘的頻繁詞集本身帶有一定的語義，在衡量文本間相似度時，相較單個特征詞的衡量方法，能夠考慮到頻繁詞中的語義關(guān)系，使得相同主題下的文本相似度更高且降低了不同主題下文本間的相似度.相比于直接用2文本間共有的頻繁詞集的數(shù)量來衡量文本間的相似度，式(7)可以有效地避免類不平衡問題帶來的影響.當(dāng)測試數(shù)據(jù)集中不同類間文本數(shù)量差距較大時，挖掘出的頻繁詞集集合中關(guān)于大類主題的頻繁詞集會比較多，而關(guān)于小類主題的頻繁詞集較少，因此在用頻繁詞集表示每個文本時會出現(xiàn)小類文本中所具有的頻繁詞集較少的情況，若直接按照共有頻繁詞集的數(shù)量來衡量相似度則會出現(xiàn)小類間文本連接不緊密的情況，在社區(qū)劃分中會出現(xiàn)小類被大類吞并的問題.為了更加準(zhǔn)確地衡量文本間相似性，式(7)考慮到文本內(nèi)頻繁詞集的數(shù)量，將相似度看做文本間共有的頻繁詞集個數(shù)在2文本中所有頻繁詞集里所占的權(quán)重比例.通過這種方法使得小類間的文本連接更加緊密，減小被大類吞并的風(fēng)險.

3) 引用網(wǎng)絡(luò)和圖論的思想，將文本當(dāng)作網(wǎng)絡(luò)中的節(jié)點，建立文本建的關(guān)聯(lián)關(guān)系，使文本與文本之間不再是獨立的兩兩關(guān)系，并且使用文本網(wǎng)絡(luò)的分析方法可以更加直觀地分析文本集中的類結(jié)構(gòu).同時可以引入更多基于網(wǎng)絡(luò)社區(qū)劃分和圖切割的聚類算法，使得FIC算法更加靈活.

Table 7 Result of Algorithms表7 算法精度

3.5 實驗中的閾值調(diào)整

本文算法中主要涉及到3個參數(shù)，包括在篩選特征詞時的閾值、挖掘頻繁詞集中的最小支持度和計算文本間相似性的相似度閾值.本文通過采用手動調(diào)整、多次實驗的方式，獲得了聚類的最佳效果.其中對于最小支持度的選擇要盡量保證每個文本能夠至少有5個頻繁詞集來表示，相似度閾值則通過文本網(wǎng)絡(luò)中的邊數(shù)來衡量，避免文本網(wǎng)絡(luò)過于密集或稀疏，在最佳效果下各個閾值的取值如表8所示.下面我們將以對聚類精度影響最高的相似性閾值為例，介紹本次實驗過程.在英文數(shù)據(jù)集中，我們選取相似度閾值的步長為0.005，由于中文數(shù)據(jù)中的停用詞較多以及每個文檔中詞數(shù)量較少，因此采用與英文數(shù)據(jù)不同的閾值選擇方式，采用0.01的步長進行實驗.其中FIC-K算法在處理無權(quán)網(wǎng)絡(luò)時精度較之帶權(quán)網(wǎng)絡(luò)高，因此我們將閾值篩選后的文本網(wǎng)絡(luò)構(gòu)成一個無權(quán)網(wǎng)絡(luò)作為輸入數(shù)據(jù)，即將權(quán)值大于θ的權(quán)值置1，小于θ的權(quán)值置0.對于FIC-S算法使用帶權(quán)網(wǎng)絡(luò),權(quán)重為文本間的相似度.圖2和圖3為在固定最佳最小支持度閾值和特征篩選閾值后FIC-K算法在不同相似度閾值下的精度情況.

Table 8 Thresholds in the Data表8 數(shù)據(jù)中的閾值

Fig. 2 Accuracy of FIC-K for Chinese data on C6圖2 FIC-K算法在C6數(shù)據(jù)集的中文數(shù)據(jù)下的精度

Fig. 3 Accuracy of FIC-K for English data圖3 FIC-K算法在英文數(shù)據(jù)集上的精度

3.6 實驗中對文本主題的描述

對于本次實驗選取的5組數(shù)據(jù)，我們采用相同的主題描述方案.對每個類簇內(nèi)的文本，統(tǒng)計所有文本內(nèi)的頻繁詞集的出現(xiàn)頻率，并選擇按頻率排名前10的頻繁詞集來描述每個主題.這里主要展示由FIC-K算法所聚成類簇的主題描述情況，同時與LDA算法得到的主題描述詞進行對比，結(jié)果如表9所示.從表9中可看出，F(xiàn)IC算法得到的主題描述詞大多圍繞主題，用頻繁詞集合的形式來描述，在一定程度上比起LDA的單個詞描述可以將類簇表述的更加詳細(xì)具體.

Table 9 Topic Description表9 主題描述

Continued (Table 9)

Continued (Table 9)

4 結(jié)束語

本文提出一種新的文本聚類方法FIC，該方法運用基于頻繁詞集的文本表示模型，解決了傳統(tǒng)的VSM模型的高維和數(shù)據(jù)稀疏的問題，采用基于網(wǎng)絡(luò)的社區(qū)劃分聚類方法和譜聚類算法，由于考慮了多個文本間的關(guān)系，聚類性能相比于之前的方法有了一定程度的提升.至今文檔聚類一直是一個值得深入研究的課題，其中面臨著兩大問題：1)數(shù)據(jù)集規(guī)模海量增長；2)文本越來越趨向于短文本的形式.如何在這類數(shù)據(jù)集上進行有效的文本聚類是我們未來工作的挑戰(zhàn).

[1] Lu Yuchang, Lu Mingyu, Li Fan, et al. Analysis and construction of word weighting function in VSM[J]. Journal of Computer Research and Development, 2002, 39(10): 1205-1210 (in Chinese)

(陸玉昌, 魯明羽, 李凡, 等. 向量空間法中單詞權(quán)重函數(shù)的分析與構(gòu)造[J]. 計算機研究與發(fā)展, 2002, 39(10): 1205-1210)

[2] Peng Min, Huang Jiajia, Zhu Jiahui, et al. Mass of short texts clustering and topic extraction based on frequent itemsets[J]. Journal of Computer Research and Development, 2015, 52(9): 1941-1953 (in Chinese)

(彭敏, 黃佳佳, 朱佳暉, 等. 基于頻繁詞集的海量短文本聚類與主題抽取[J]. 計算機研究與發(fā)展, 2015, 52(9): 1941-1953)

[3] Beil F, Ester M, Xu Xiaowei. Frequent term-based text clustering[C] //Proc of the 8th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 436-442

[4] Fung M, Wang Ke, Ester M. Hierarchical document clustering using frequent itemsets[C] //Proc of the 3rd SIAM Int Conf on Data Mining. San Francisco, CA: SIAM, 2003: 59-70

[5] Zhang Wen, Yoshida T, Tang Xijin, et al. Text clustering using frequent itemsets[J]. Konwledge-Based Systems, 2010, 23(5): 379-388

[6] Hernández-Reyes E, García-Hernández R A, Carrasco-Ochoa J A, et al. Document clustering based on maximal frequent sequences[G] //Advances in Natural Language Processing. Berlin: Springer, 2006: 257-267

[7] Masada T, Kiyasu S, Miyahara S. Comparing LDA with pLSI as a dimensionality reduction method in document clustering[G] //Large-Scale Knowledge Resource. Berlin: Springer, 2008: 13-16

[8] Hornik K, Feinerer I, Kober M, et al. Spherical k-means clustering[J]. Journal of Statistical Software, 2012, 50(10): 1-22

[9] Cai Deng, He Xiaofei, Han Jiawei, et al. Graph regularized bonnegative matrix factorization for data representation[J]. IEEE Trans on Pattern Analysis & Machine Intelligence, 2011, 33(8): 1548-1560

[10] Hoyer P O. Non-negative matrix factorization with sparseness constraints[J]. Journal of Machine Learning Research, 2004, 5(1): 1457-1469

[11] Xiu Yu, Wang Shitong, Zhu Lin,et al. Maximum-entropy sphereK-means document clusterinf analysis[J]. Frontiers of Computer Science and Technology, 2007, 1(3): 331-339 (in Chinese)

(修宇, 王士同, 朱林, 等. 極大熵球面K均值文本聚類分析[J]. 計算機科學(xué)與探索, 2007, 1(3): 331-339)

[12] Han Jiawei, Pei Jian,Yin Yiwen. Mining frequent pattern without candidate generation: A frequent-pattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8(53): 53-87

[13] Li Yafang, Jia Caiyan, Yu Jian. A parameter-free community detection method based on centrality and dispersion of nodes in complex networks[J]. Physica A Statistical Mechanics & Its Applications, 2015, 438(43): 321-334

[14] Luxburg U V. A tutorial on spectral clustering[J]. Statistics & Computing, 2007, 17(17): 395-416

[15] Steinbach M, Karypis G, Kumar V. A comparison of document clustering techniques[C] //Proc of the 2nd KDD Workshop on Text Mining. New York: ACM, 2000: 525-526

[16] Huang Yuyan. Research and application of text clustering method based on maximal frequent itemsetsK-means[D]. Harbin: Harbin Institute of Technology, 2011 (in Chinese)

(黃玉燕. 基于最大頻繁詞集K-means的文本聚類算法研究及應(yīng)用[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2011)