多層概圖文檔聚類方法中精化算法的研究

1,、引言
聚類分析是數(shù)據(jù)挖掘的重要手段之一,，在文本挖掘中也占據(jù)重要地位。在各種聚類方法中,，圖論法是一種較為靈活有效的方法,。其前提是把需要聚類的數(shù)據(jù)表示成無向圖G=(V,E)的形式，V是圖的頂點集,，E是圖的邊集,。所有數(shù)據(jù)點構(gòu)成頂點集，如果兩個頂點符合一定的鄰域規(guī)則,，那么它們之間有邊,。
基于圖的聚類操作，一般是應(yīng)用圖分割算法,，把圖分割為互不連通的分支，再把分支中的頂點集映射到數(shù)據(jù)集合,，得到最后的聚類結(jié)果,。在圖的分割和映射過程中，要能對邊和點的權(quán)重進(jìn)行處理,，并研究根據(jù)一定的目標(biāo)函數(shù),，求取最優(yōu)分割的算法。本文研究了高維特征空間下的文本聚類方法,，提出了一種基于多層粗圖模型的聚類算法,，對反概化操作中的精化算法進(jìn)行了深入探討。
2,、相關(guān)工作
文獻(xiàn)[1]提出了一種基于超圖（hypergraph）模型,、對高維空間數(shù)據(jù)進(jìn)行聚類的方法，并應(yīng)用于Web文檔聚類,。其中的HEMTIS是一種應(yīng)用于VLSI設(shè)計的多層超圖二分算法,。超圖的最優(yōu)二分計算是一個NP問題，但由于該問題在許多應(yīng)用領(lǐng)域的重要性,，學(xué)者們已經(jīng)提出很多啟發(fā)式算法用于近似解決二分圖的問題,。
超圖二分模型一般有三種。第一種為單階段型,，其一般的過程是,，從一個初始分割（隨機獲得）開始，通過應(yīng)用精化算法進(jìn)行迭代,，頂點在爐分割的兩部分之間動態(tài)移動,，使分割質(zhì)量不斷提高,。第二種是兩階段型，包括：①把原始圖聚集為一個較小型的圖,，并應(yīng)用FM算法進(jìn)行二分,；②把該聚集超圖的二分映射回原始超圖，獲得原始超圖的二分,。該類型的分割質(zhì)量主要取決于第一階段超圖聚集操作,。第三種是三階段型，包括：①概化過程,；②初始分割過程,；③反概化和精化過程。在概化過程中,，從原始圖通過概化操作,，產(chǎn)生一系列逐步縮小的概圖；在初始分割過程,，應(yīng)用超圖分割算法對最小的概圖進(jìn)行分割,；在反概化和精化過程，最小概圖的二分反向逐層映射回較細(xì)的概圖,，并在每一層應(yīng)用KL或FM算法進(jìn)行精化操作,，不斷提高超圖的分割質(zhì)量。
無論是何種超圖分割模型,，均需要應(yīng)用精化算法在不同階段進(jìn)行局部點的移動,，以改善分割質(zhì)量。在這些分割模型中,，應(yīng)用到的精化算法一般有三種,，分別為Kernighan-Lin算法、KL的擴展Schweikert-Kernighan算法和計算速度較快的Fiduccia-Mattheyses算法,。但是,，應(yīng)用這些算法產(chǎn)生的分割質(zhì)量有時仍難令人滿意，尤其是對于頂點較多的大型超圖,。究其原因主要有：1,、對移動點的選擇僅僅依賴于局部信息，沒有考慮全局信息,；2,、當(dāng)頂點的“增益”相等時，無法給出正確選擇移動點的方法,；3,、當(dāng)含有多個頂點的超邊跨越分割時，這些頂點的“增益”計算無法準(zhǔn)確進(jìn)行,。
METIS是一種多層圖分割算法,，對概化操作進(jìn)行了改進(jìn),，但不能直接應(yīng)用于超圖分割；hMETIS則在此基礎(chǔ)做了進(jìn)一步改進(jìn),，使其能應(yīng)用于超圖分割,。文獻(xiàn)[]在圖的二分基礎(chǔ)上進(jìn)行了擴展，能同時把圖劃分為二,、四或八個分割,，稱為k-way算法。
本文針對web文檔聚類的數(shù)據(jù)高維,、稀疏的特點,，提出一種基于多層概圖模型的文檔聚類算法，首先創(chuàng)建文檔的向量空間,，運用向量內(nèi)積定義數(shù)據(jù)點的相似性,；然后建立圖模型反映數(shù)據(jù)點之間的聯(lián)系程度，對此原始圖進(jìn)行不斷的概化操作,，形成一系列逐層縮小的概圖序列,，對最小的概圖運用分割算法劃分為k個分支；最后把此分割再逐層映射回較細(xì)圖,，根據(jù)需要運用改進(jìn)的FM精化算法對分割進(jìn)行局部調(diào)整,，不斷改善分割質(zhì)量，最終原始圖的分割映射到文檔數(shù)據(jù)集,，就是我們需要的聚類結(jié)果。本文主要介紹了多層概圖聚類算法中的精化算法,。
3,、基于多層概圖模型的文檔聚類算法
3.1、文檔向量空間模型
Web文檔經(jīng)過預(yù)處理[]后,，產(chǎn)生一系列原始數(shù)據(jù),，如特征詞j在文檔i中出現(xiàn)的次數(shù)fji ，包含特征詞j的文檔數(shù)dj 等,。利用這些計數(shù),，在Rd空間建立n個文檔向量 x1,x2,……,xn，文檔向量xi的第j分量為
xji=tji×gj×si (1≤j≤d,1≤i≤n) （1）
其中,，tji 是依賴于fji的特征詞權(quán)重分量,；gj是依賴于dj的全局權(quán)重分量；si是xi的范化分量,。也就是說,，tji 反映特征詞在一篇文檔中的相對重要性，而gj反映詞在整個文檔集中的全局重要性,。該文檔向量的權(quán)重模型,，加強了不同文檔向量的識別,，從而加強了信息獲取效力。
對于特征詞權(quán)重分量,、全局權(quán)重分量和范化分量的取值方法有多種,，我們采用較為通用的TF和IDF模型取值，即tji= fji, gj=1(TF模型)或gj=log(n/dj)(IDF模型),，范化分量的取值采用L2范式,，即
sj= （2）
一般來說，范化的目的是只獲得文檔向量模型的方,，這保證了擁有相同主題（即使用了相似的特征詞）的文檔不會因為文檔長度的不同而使其相似度減小,。
3.2、向量相似度計算
根據(jù)（1）,、（2）式,，文檔向量x1,x2,……,xn可以看作Rd空間單位球表面上的n個點。對多數(shù)權(quán)重模型來說,，向量的各個分量均是非負(fù)的,，因此文檔向量在Rd空間處于非負(fù)方向，即 ,。對于向量模型,，內(nèi)積是一種自然的相似性度量準(zhǔn)則。
給定 空間任意兩個單位向量x和y,，兩者之間的角度可以表示為0≤θ（x,y）≤π/2,，那么

因此，內(nèi)積 常被稱為”余弦相似度（cosine similarity）”,。由于余弦相似度容易解釋,，對稀疏向量來說計算簡單，因此在文本挖掘和信息抽取領(lǐng)域得到了廣泛應(yīng)用,。
3.3,、多層概圖模型
在定義了文檔向量的相似度以后，將n個文檔向量映射為n個圖的頂點,，建立圖模型H=(V,，E)，其中,，V={v1,v2,…,vn}是圖的頂點集合,，E={e1,e2,…,em}是圖的邊集合。
圖中,，頂點的權(quán)重等于其連接的邊數(shù),，邊的權(quán)重等于所連接點的相似度，即余弦相似度,。我們把原始數(shù)據(jù)集對應(yīng)的圖G0稱為基圖,。從基圖,，G1=G0出發(fā)，經(jīng)過不斷的概化操作,，得到一系列概化程度逐步提高,、點和邊的規(guī)模逐步縮小的多層概圖Gi（i=1…l）。我們稱Gi是相對于Gi-1的概圖,，Gi-1是相對于Gi的細(xì)圖,，Gl是最小概圖。概化過程中,，邊和點的權(quán)重依據(jù)一定的規(guī)則得以在層間保留,，并在反概化過程中又逐步映射回原始數(shù)據(jù)集，對最小概圖應(yīng)用k-way分割算法,，形成圖的劃分,，通過反向映射和周期性局部調(diào)整，在原始數(shù)據(jù)集中形成的劃分就是聚類結(jié)果,。
4,、精化算法
由于隨著圖的頂點數(shù)增多，可能存在的分割數(shù)將呈指數(shù)增長,，因此建立逐層概圖模型,、縮小分割對象的規(guī)模的主要目的是減小圖分割的復(fù)雜度。但是,，由于概化算法的不足,，概圖的優(yōu)化分割并不直接對應(yīng)于較細(xì)圖的優(yōu)化分割，因此必須在從概圖向細(xì)圖映射的過程中應(yīng)用精化算法,，對細(xì)圖的分割進(jìn)行精化,，以提高分割質(zhì)量；然后再向下一層細(xì)圖映射,，直到映射回基圖。為此,，我們總結(jié)Kernighan-Lin算法和Fiduccia-Mattheyses算法,，對圖的二分精化算法進(jìn)行推廣，提出一種快而有效的精化算法,。
4.1精化算法概述
我們的算法在FM算法的基礎(chǔ)上,，有以下幾點改進(jìn)：①可以優(yōu)化任意數(shù)目的分割，而不局限于二分,；②FM算法僅能處理頂點有權(quán)重的圖,，我們的算法能同時處理帶有頂點權(quán)重和邊權(quán)重的圖；③能進(jìn)行任意整數(shù)個集合間的割集的消耗度量,；④算法中采用一種隨機機制以增強算法魯棒性,；⑤當(dāng)只有少數(shù)點需要移動時,，利用重用計算（reuse computation）大幅減少運行時間。
與頂點在不同集合之間移動相聯(lián)系的“增益（gain）”概念是KL之后精化算法的基本出發(fā)點,。“增益”是指由于頂點在不同集合之間交換引起的割集權(quán)重的凈減少,。即，如果頂點i從集合l移動到集合K,，相應(yīng)的增益可以表示為：

其中P（j）是頂點j的當(dāng)前所在集合,，wij是頂點i和j之間邊的權(quán)重，clk是連接集合l和k的邊的對稱集合間消耗度量,，一般可取為1,。
上式表明，如果一個頂點的增益是正的,，那么移動該點會減少割集的總消耗或稱為權(quán)重,，無疑對優(yōu)化分割是有利的。但是是否移動,，必須考慮兩個因素,，一是分割的規(guī)模約束，即考慮分割頂點集合的平衡性,。如果要求最后的分割集合規(guī)模大致相當(dāng),，在考察頂點移動時就要考慮相應(yīng)的兩個集合的規(guī)模因素；二是局部和全局的因素,，也許某個頂點的移動從當(dāng)前來看是不利的,，但從全局看也許由此引發(fā)的一系列頂點移動會使分割性能更為優(yōu)化。
精化算法的基本結(jié)構(gòu)如圖1所示：
Until No better partition is discovered
Best Partition:=Current Partition
Compute all initial gains
Until Termination criteria reached
Select vertex to move
Perform move
Update gains of all neighbors of moved vertex
If Current Partition balanced and better than Best Partition Then
Best Partition:=Current Partition
End Until
Current Partition:=Best Partition
End Until
圖1. 圖分割精化算法
該算法包括含兩個嵌套的循環(huán),。內(nèi)循環(huán)完成一系列集合間點的移動,，外循環(huán)持續(xù)探測改善分割的可能性。我們稱外循環(huán)一次為一個輪次,，每次內(nèi)循環(huán)完成一個頂點的移動,，每個頂點在一輪次內(nèi)只允許移動一次。點移動完成后,，所有它的鄰點的增益更新,，然后進(jìn)入下一個選擇和移動的循環(huán)。為了突破局域限制,，內(nèi)循環(huán)中的最好分割配置被記錄下來,，并進(jìn)行更多點的移動和探索，直到滿足終止條件跳出內(nèi)循環(huán),；在進(jìn)入下一輪次（外循環(huán)）時,，數(shù)據(jù)按最優(yōu)分割進(jìn)行配置。
4.2精化算法的數(shù)據(jù)結(jié)構(gòu)
FM算法使用一種相對復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，采用一種抽象的“桶”的概念存儲所有可能移動的頂點增益,。由于其針對二分圖進(jìn)行精化,，假定頂點集合為A、B,，所有從A到B的可能移動點及其增益值存入一“桶”,，從B到A的存入另一“桶”，并由大到小排序,，具體可由雙鏈列表實現(xiàn),。選擇具有最高增益值的點，只需簡單地尋找最高的非空桶,，然后把相應(yīng)的點的序號從一個桶移到另一個桶,，并更新所有相鄰點的增益值。
我們的算法對FM作了擴展,，使之能處理任意數(shù)目的集合,。假定有s個集合，每次移動一個點,，可能有s(s-1)個不同移動,，我們?yōu)槊總€移動維持一個排序的桶結(jié)構(gòu)，則有s(s-1)個桶,。共n個點,，每個點可能移動到其它s-1個集合中，所以需要的存儲空間是O(n(s-1)),。也就是說,，共有n(s-1)個候選移動分布在s(s-1)個桶中，每個桶有中的候選移動由增益值自大到小排序,。此種結(jié)構(gòu)可以由經(jīng)過排序的雙鏈表實現(xiàn),，每個存儲單元有兩個指針，一個指針指示其在桶中的位置,，另一指針指示其所屬的頂點,，即每個增益值既可以按桶索引，也可按點索引,。在進(jìn)入最里層循環(huán)之前,，計算所有的增益值并存儲在相應(yīng)的桶中，計算復(fù)雜度為O((s-1)m),。進(jìn)入內(nèi)層循環(huán)之后，移動點的選擇需要O(s(s-1)m)的時間,，其余需要O(sm)的時間,。
4.3循環(huán)的終止條件
循環(huán)的終止條件有兩種，一種是從大集合到小集合的移動不再可能；另一種是無法改善分割質(zhì)量而提前終止循環(huán),。實際上,，第二種終止條件是有利的，雖然我們設(shè)計了多層概圖模型中的精化算法,，但實際上希望盡量少地使用到,，或即使用到，其做的改變也盡量小,。對于第二種條件,，我們比較遇到的最好分割和當(dāng)前分割之間的質(zhì)量差異，如果這種差異越來越大,，表明發(fā)現(xiàn)更好分割的可能性很小,，內(nèi)部循環(huán)隨即終止。
4.4隨機機制
當(dāng)出現(xiàn)頂點的增益值相等時,，如何處理將直接影響分割的結(jié)果,。我們采用了隨機選擇的機制，初始增益值的計算是按隨機順序進(jìn)行的,，當(dāng)增益值得到更新時,，相應(yīng)的頂點及其增益值放在列表的最前端，然后其鄰集的增益值逐步計算,。另外,，為了克服局域優(yōu)化的問題，在外循環(huán)尋求更好的分割配置時失敗時仍使算法繼續(xù)循環(huán)三次,，以增加分割優(yōu)化的可能性,。
5、實驗結(jié)果
為了評價多層概圖文檔聚類算法和傳統(tǒng)聚類算法的性能,，我們從網(wǎng)上收集了有關(guān)商業(yè),、娛樂、健康,、政治,、運動、技術(shù),、文學(xué),、農(nóng)業(yè)等的文檔874篇，進(jìn)行文檔預(yù)處理后,，保留了1653個特征詞,。形成874×1653的數(shù)據(jù)表，表中第I行第j列表示文檔I中出現(xiàn)的j特征詞的次數(shù),。
運用本文算法,，定義了數(shù)據(jù)對象之間的余弦相似度,，并對相似度大于0.05的數(shù)據(jù)對象之間建立邊，形成頂點數(shù)n=768（其余文檔由于其與任何文檔的相似度均低于0.05,，視為孤立點）,，邊m=81253的基圖。設(shè)k=8,，我們應(yīng)用多層概圖算法對文檔進(jìn)行了聚類,。由于類別之間文檔數(shù)相差較大，我們對算法進(jìn)行了設(shè)置,，對圖進(jìn)行分割時沒有要求平衡性,。作為對比，我們還應(yīng)用autoclass對同一數(shù)據(jù)集進(jìn)行聚類操作,。分析聚類結(jié)果,，多層概圖方法的聚類結(jié)果，其8個簇的文檔數(shù)分別為c1=116,，c2=108,，c3=74，c4=85,，c5=132,，c6=94，c7=124,，c8=35,。其中，有關(guān)商業(yè),、娛樂,、健康、運動,、農(nóng)業(yè),、技術(shù)的文章聚集相關(guān)性較強，能較好的聚為一類,，屬于政治,、文學(xué)的文檔，大部分聚為相應(yīng)的兩個簇,，有少部分被聚集到其它類中,。以autoclass方法進(jìn)行文檔的自動聚類，結(jié)果聚集為12個簇,，具體分析時發(fā)現(xiàn)簇內(nèi)文檔有些混亂,，許多相似性不大的、明顯處于不同類的文檔被劃分到一簇,，總體聚類質(zhì)量低于多層概圖模型的質(zhì)量,。
6,、結(jié)論與未來工作
文檔聚類是高維聚類的重要應(yīng)用領(lǐng)域。我們應(yīng)用多層概圖模型進(jìn)行文檔聚類,，把文檔對象作為圖的頂點，以對象間的相似性建邊,，在對最小概圖進(jìn)行初始分割后,，應(yīng)用精化算法對劃分進(jìn)行逐層優(yōu)化，取得了較好的效果,。
本文應(yīng)用的精化算法仍需要繼續(xù)改進(jìn),。精化操作，可以在多層概圖算法的概化過程中應(yīng)用,，也可以設(shè)計在反概化過程中應(yīng)用,。作者將進(jìn)一步深入精化算法的研究，進(jìn)一步提高多層概圖模型的性能,。