多層概圖文檔聚類方法中精化算法的研究
1、引言 聚類分析是數(shù)據(jù)挖掘的重要手段之一，在文本挖掘中也占據(jù)重要地位。在各種聚類方法中，圖論法是一種較為靈活有效的方法。其前提是把需要聚類的數(shù)據(jù)表示成無(wú) 向圖G=(V,E)的形式，V是圖的頂點(diǎn)集，E是圖的邊集。所有數(shù)據(jù)點(diǎn)構(gòu)成頂點(diǎn)集，如果兩個(gè)頂點(diǎn)符合一定的鄰域規(guī)則，那么它們之間有邊。 基于圖的聚類操作，一般是應(yīng)用圖分割算法，把圖分割為互不連通的分支，再把分支中的頂點(diǎn)集映射到數(shù)據(jù)集合，得到最后的聚類結(jié)果。在圖的分割和映射過(guò)程中， 要能對(duì)邊和點(diǎn)的權(quán)重進(jìn)行處理，并研究根據(jù)一定的目標(biāo)函數(shù)，求取最優(yōu)分割的算法。本文研究了高維特征空間下的文本聚類方法，提出了一種基于多層粗圖模型的聚 類算法，對(duì)反概化操作中的精化算法進(jìn)行了深入探討。 2、相關(guān)工作 文獻(xiàn)[1]提出了一種基于超圖（hypergraph）模型、對(duì)高維空間數(shù)據(jù)進(jìn)行聚類的方法，并應(yīng)用于Web文檔聚類。其中的HEMTIS是一種應(yīng)用于 VLSI設(shè)計(jì)的多層超圖二分算法。超圖的最優(yōu)二分計(jì)算是一個(gè)NP問(wèn)題，但由于該問(wèn)題在許多應(yīng)用領(lǐng)域的重要性，學(xué)者們已經(jīng)提出很多啟發(fā)式算法用于近似解決二 分圖的問(wèn)題。 超圖二分模型一般有三種。第一種為單階段型，其一般的過(guò)程是，從一個(gè)初始分割（隨機(jī)獲得）開(kāi)始，通過(guò)應(yīng)用精化算法進(jìn)行迭代，頂點(diǎn)在爐分割的兩部分之間動(dòng)態(tài) 移動(dòng)，使分割質(zhì)量不斷提高。第二種是兩階段型，包括：①把原始圖聚集為一個(gè)較小型的圖，并應(yīng)用FM算法進(jìn)行二分；②把該聚集超圖的二分映射回原始超圖，獲 得原始超圖的二分。該類型的分割質(zhì)量主要取決于第一階段超圖聚集操作。第三種是三階段型，包括：①概化過(guò)程；②初始分割過(guò)程；③反概化和精化過(guò)程。在概化 過(guò)程中，從原始圖通過(guò)概化操作，產(chǎn)生一系列逐步縮小的概圖；在初始分割過(guò)程，應(yīng)用超圖分割算法對(duì)最小的概圖進(jìn)行分割；在反概化和精化過(guò)程，最小概圖的二分 反向逐層映射回較細(xì)的概圖，并在每一層應(yīng)用KL或FM算法進(jìn)行精化操作，不斷提高超圖的分割質(zhì)量。 無(wú)論是何種超圖分割模型，均需要應(yīng)用精化算法在不同階段進(jìn)行局部點(diǎn)的移動(dòng)，以改善分割質(zhì)量。在這些分割模型中，應(yīng)用到的精化算法一般有三種，分別為 Kernighan-Lin算法、KL的擴(kuò)展Schweikert-Kernighan算法和計(jì)算速度較快的Fiduccia-Mattheyses算 法。但是，應(yīng)用這些算法產(chǎn)生的分割質(zhì)量有時(shí)仍難令人滿意，尤其是對(duì)于頂點(diǎn)較多的大型超圖。究其原因主要有：1、對(duì)移動(dòng)點(diǎn)的選擇僅僅依賴于局部信息，沒(méi)有考 慮全局信息；2、當(dāng)頂點(diǎn)的“增益”相等時(shí)，無(wú)法給出正確選擇移動(dòng)點(diǎn)的方法；3、當(dāng)含有多個(gè)頂點(diǎn)的超邊跨越分割時(shí)，這些頂點(diǎn)的“增益”計(jì)算無(wú)法準(zhǔn)確進(jìn)行。 METIS是一種多層圖分割算法，對(duì)概化操作進(jìn)行了改進(jìn)，但不能直接應(yīng)用于超圖分割；hMETIS則在此基礎(chǔ)做了進(jìn)一步改進(jìn)，使其能應(yīng)用于超圖分割。文獻(xiàn)[]在圖的二分基礎(chǔ)上進(jìn)行了擴(kuò)展，能同時(shí)把圖劃分為二、四或八個(gè)分割，稱為k-way算法。 本文針對(duì)web文檔聚類的數(shù)據(jù)高維、稀疏的特點(diǎn)，提出一種基于多層概圖模型的文檔聚類算法，首先創(chuàng)建文檔的向量空間，運(yùn)用向量?jī)?nèi)積定義數(shù)據(jù)點(diǎn)的相似性；然 后建立圖模型反映數(shù)據(jù)點(diǎn)之間的聯(lián)系程度，對(duì)此原始圖進(jìn)行不斷的概化操作，形成一系列逐層縮小的概圖序列，對(duì)最小的概圖運(yùn)用分割算法劃分為k個(gè)分支；最后把 此分割再逐層映射回較細(xì)圖，根據(jù)需要運(yùn)用改進(jìn)的FM精化算法對(duì)分割進(jìn)行局部調(diào)整，不斷改善分割質(zhì)量，最終原始圖的分割映射到文檔數(shù)據(jù)集，就是我們需要的聚 類結(jié)果。本文主要介紹了多層概圖聚類算法中的精化算法。 3、基于多層概圖模型的文檔聚類算法 3.1、文檔向量空間模型 Web文檔經(jīng)過(guò)預(yù)處理[]后，產(chǎn)生一系列原始數(shù)據(jù)，如特征詞j在文檔i中出現(xiàn)的次數(shù)fji ，包含特征詞j的文檔數(shù)dj 等。利用這些計(jì)數(shù)，在Rd空間建立n個(gè)文檔向量 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的范化分量。也就是說(shuō)，tji 反映特征詞在一篇文檔中的相對(duì)重要性，而gj反映詞在整個(gè)文檔集中的全局重要性。該文檔向量的權(quán)重模型，加強(qiáng)了不同文檔向量的識(shí)別，從而加強(qiáng)了信息獲取效 力。 對(duì)于特征詞權(quán)重分量、全局權(quán)重分量和范化分量的取值方法有多種，我們采用較為通用的TF和IDF模型取值，即tji= fji, gj=1(TF模型)或gj=log(n/dj)(IDF模型)，范化分量的取值采用L2范式，即 sj= （2） 一般來(lái)說(shuō)，范化的目的是只獲得文檔向量模型的方，這保證了擁有相同主題（即使用了相似的特征詞）的文檔不會(huì)因?yàn)槲臋n長(zhǎng)度的不同而使其相似度減小。 3.2、向量相似度計(jì)算 根據(jù)（1）、（2）式，文檔向量x1,x2,……,xn可以看作Rd空間單位球表面上的n個(gè)點(diǎn)。對(duì)多數(shù)權(quán)重模型來(lái)說(shuō)，向量的各個(gè)分量均是非負(fù)的，因此文檔向量在Rd空間處于非負(fù)方向，即 。對(duì)于向量模型，內(nèi)積是一種自然的相似性度量準(zhǔn)則。 給定 空間任意兩個(gè)單位向量x和y，兩者之間的角度可以表示為0≤θ（x,y）≤π/2，那么 因此，內(nèi)積 常被稱為”余弦相似度（cosine similarity）”。由于余弦相似度容易解釋，對(duì)稀疏向量來(lái)說(shuō)計(jì)算簡(jiǎn)單，因此在文本挖掘和信息抽取領(lǐng)域得到了廣泛應(yīng)用。 3.3、多層概圖模型 在定義了文檔向量的相似度以后，將n個(gè)文檔向量映射為n個(gè)圖的頂點(diǎn)，建立圖模型H=(V，E)，其中，V={v1,v2,…,vn}是圖的頂點(diǎn)集合，E={e1,e2,…,em}是圖的邊集合。 圖中，頂點(diǎn)的權(quán)重等于其連接的邊數(shù)，邊的權(quán)重等于所連接點(diǎn)的相似度，即余弦相似度。我們把原始數(shù)據(jù)集對(duì)應(yīng)的圖G0稱為基圖。從基圖，G1=G0出發(fā)，經(jīng)過(guò) 不斷的概化操作，得到一系列概化程度逐步提高、點(diǎn)和邊的規(guī)模逐步縮小的多層概圖Gi（i=1…l）。我們稱Gi是相對(duì)于Gi-1的概圖，Gi-1是相對(duì)于 Gi的細(xì)圖，Gl是最小概圖。概化過(guò)程中，邊和點(diǎn)的權(quán)重依據(jù)一定的規(guī)則得以在層間保留，并在反概化過(guò)程中又逐步映射回原始數(shù)據(jù)集，對(duì)最小概圖應(yīng)用k- way分割算法，形成圖的劃分，通過(guò)反向映射和周期性局部調(diào)整，在原始數(shù)據(jù)集中形成的劃分就是聚類結(jié)果。 4、精化算法 由于隨著圖的頂點(diǎn)數(shù)增多，可能存在的分割數(shù)將呈指數(shù)增長(zhǎng)，因此建立逐層概圖模型、縮小分割對(duì)象的規(guī)模的主要目的是減小圖分割的復(fù)雜度。但是，由于概化算法 的不足，概圖的優(yōu)化分割并不直接對(duì)應(yīng)于較細(xì)圖的優(yōu)化分割，因此必須在從概圖向細(xì)圖映射的過(guò)程中應(yīng)用精化算法，對(duì)細(xì)圖的分割進(jìn)行精化，以提高分割質(zhì)量；然后 再向下一層細(xì)圖映射，直到映射回基圖。為此，我們總結(jié)Kernighan-Lin算法和Fiduccia-Mattheyses算法，對(duì)圖的二分精化算法 進(jìn)行推廣，提出一種快而有效的精化算法。 4.1精化算法概述 我們的算法在FM算法的基礎(chǔ)上，有以下幾點(diǎn)改進(jìn)：①可以優(yōu)化任意數(shù)目的分割，而不局限于二分；②FM算法僅能處理頂點(diǎn)有權(quán)重的圖，我們的算法能同時(shí)處理帶 有頂點(diǎn)權(quán)重和邊權(quán)重的圖；③能進(jìn)行任意整數(shù)個(gè)集合間的割集的消耗度量；④算法中采用一種隨機(jī)機(jī)制以增強(qiáng)算法魯棒性；⑤當(dāng)只有少數(shù)點(diǎn)需要移動(dòng)時(shí)，利用重用計(jì) 算（reuse computation）大幅減少運(yùn)行時(shí)間。 與頂點(diǎn)在不同集合之間移動(dòng)相聯(lián)系的“增益（gain）”概念是KL之后精化算法的基本出發(fā)點(diǎn)。“增益”是指由于頂點(diǎn)在不同集合之間交換引起的割集權(quán)重的凈減少。即，如果頂點(diǎn)i從集合l移動(dòng)到集合K，相應(yīng)的增益可以表示為： 其中P（j）是頂點(diǎn)j的當(dāng)前所在集合，wij是頂點(diǎn)i和j之間邊的權(quán)重，clk是連接集合l和k的邊的對(duì)稱集合間消耗度量，一般可取為1。 上式表明，如果一個(gè)頂點(diǎn)的增益是正的，那么移動(dòng)該點(diǎn)會(huì)減少割集的總消耗或稱為權(quán)重，無(wú)疑對(duì)優(yōu)化分割是有利的。但是是否移動(dòng)，必須考慮兩個(gè)因素，一是分割的 規(guī)模約束，即考慮分割頂點(diǎn)集合的平衡性。如果要求最后的分割集合規(guī)模大致相當(dāng)，在考察頂點(diǎn)移動(dòng)時(shí)就要考慮相應(yīng)的兩個(gè)集合的規(guī)模因素；二是局部和全局的因 素，也許某個(gè)頂點(diǎn)的移動(dòng)從當(dāng)前來(lái)看是不利的，但從全局看也許由此引發(fā)的一系列頂點(diǎn)移動(dòng)會(huì)使分割性能更為優(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. 圖分割精化算法 該算法包括含兩個(gè)嵌套的循環(huán)。內(nèi)循環(huán)完成一系列集合間點(diǎn)的移動(dòng)，外循環(huán)持續(xù)探測(cè)改善分割的可能性。我們稱外循環(huán)一次為一個(gè)輪次，每次內(nèi)循環(huán)完成一個(gè)頂點(diǎn)的 移動(dòng)，每個(gè)頂點(diǎn)在一輪次內(nèi)只允許移動(dòng)一次。點(diǎn)移動(dòng)完成后，所有它的鄰點(diǎn)的增益更新，然后進(jìn)入下一個(gè)選擇和移動(dòng)的循環(huán)。為了突破局域限制，內(nèi)循環(huán)中的最好分 割配置被記錄下來(lái)，并進(jìn)行更多點(diǎn)的移動(dòng)和探索，直到滿足終止條件跳出內(nèi)循環(huán)；在進(jìn)入下一輪次（外循環(huán)）時(shí)，數(shù)據(jù)按最優(yōu)分割進(jìn)行配置。 4.2精化算法的數(shù)據(jù)結(jié)構(gòu) FM算法使用一種相對(duì)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，采用一種抽象的“桶”的概念存儲(chǔ)所有可能移動(dòng)的頂點(diǎn)增益。由于其針對(duì)二分圖進(jìn)行精化，假定頂點(diǎn)集合為A、B，所有從 A到B的可能移動(dòng)點(diǎn)及其增益值存入一“桶”，從B到A的存入另一“桶”，并由大到小排序，具體可由雙鏈列表實(shí)現(xiàn)。選擇具有最高增益值的點(diǎn)，只需簡(jiǎn)單地尋找 最高的非空桶，然后把相應(yīng)的點(diǎn)的序號(hào)從一個(gè)桶移到另一個(gè)桶，并更新所有相鄰點(diǎn)的增益值。 我們的算法對(duì)FM作了擴(kuò)展，使之能處理任意數(shù)目的集合。假定有s個(gè)集合，每次移動(dòng)一個(gè)點(diǎn)，可能有s(s-1)個(gè)不同移動(dòng)，我們?yōu)槊總€(gè)移動(dòng)維持一個(gè)排序的桶 結(jié)構(gòu)，則有s(s-1)個(gè)桶。共n個(gè)點(diǎn)，每個(gè)點(diǎn)可能移動(dòng)到其它s-1個(gè)集合中，所以需要的存儲(chǔ)空間是O(n(s-1))。也就是說(shuō)，共有n(s-1)個(gè)候 選移動(dòng)分布在s(s-1)個(gè)桶中，每個(gè)桶有中的候選移動(dòng)由增益值自大到小排序。此種結(jié)構(gòu)可以由經(jīng)過(guò)排序的雙鏈表實(shí)現(xiàn)，每個(gè)存儲(chǔ)單元有兩個(gè)指針，一個(gè)指針指 示其在桶中的位置，另一指針指示其所屬的頂點(diǎn)，即每個(gè)增益值既可以按桶索引，也可按點(diǎn)索引。在進(jìn)入最里層循環(huán)之前，計(jì)算所有的增益值并存儲(chǔ)在相應(yīng)的桶中， 計(jì)算復(fù)雜度為O((s-1)m)。進(jìn)入內(nèi)層循環(huán)之后，移動(dòng)點(diǎn)的選擇需要O(s(s-1)m)的時(shí)間，其余需要O(sm)的時(shí)間。 4.3循環(huán)的終止條件 循環(huán)的終止條件有兩種，一種是從大集合到小集合的移動(dòng)不再可能；另一種是無(wú)法改善分割質(zhì)量而提前終止循環(huán)。實(shí)際上，第二種終止條件是有利的，雖然我們?cè)O(shè)計(jì) 了多層概圖模型中的精化算法，但實(shí)際上希望盡量少地使用到，或即使用到，其做的改變也盡量小。對(duì)于第二種條件，我們比較遇到的最好分割和當(dāng)前分割之間的質(zhì) 量差異，如果這種差異越來(lái)越大，表明發(fā)現(xiàn)更好分割的可能性很小，內(nèi)部循環(huán)隨即終止。 4.4隨機(jī)機(jī)制 當(dāng)出現(xiàn)頂點(diǎn)的增益值相等時(shí)，如何處理將直接影響分割的結(jié)果。我們采用了隨機(jī)選擇的機(jī)制，初始增益值的計(jì)算是按隨機(jī)順序進(jìn)行的，當(dāng)增益值得到更新時(shí)，相應(yīng)的 頂點(diǎn)及其增益值放在列表的最前端，然后其鄰集的增益值逐步計(jì)算。另外，為了克服局域優(yōu)化的問(wèn)題，在外循環(huán)尋求更好的分割配置時(shí)失敗時(shí)仍使算法繼續(xù)循環(huán)三 次，以增加分割優(yōu)化的可能性。 5、實(shí)驗(yàn)結(jié)果 為了評(píng)價(jià)多層概圖文檔聚類算法和傳統(tǒng)聚類算法的性能，我們從網(wǎng)上收集了有關(guān)商業(yè)、娛樂(lè)、健康、政治、運(yùn)動(dòng)、技術(shù)、文學(xué)、農(nóng)業(yè)等的文檔874篇，進(jìn)行文檔預(yù)處理后，保留了1653個(gè)特征詞。形成874×1653的數(shù)據(jù)表，表中第I行第j列表示文檔I中出現(xiàn)的j特征詞的次數(shù)。 運(yùn)用本文算法，定義了數(shù)據(jù)對(duì)象之間的余弦相似度，并對(duì)相似度大于0.05的數(shù)據(jù)對(duì)象之間建立邊，形成頂點(diǎn)數(shù)n=768（其余文檔由于其與任何文檔的相似度 均低于0.05，視為孤立點(diǎn)），邊m=81253的基圖。設(shè)k=8，我們應(yīng)用多層概圖算法對(duì)文檔進(jìn)行了聚類。由于類別之間文檔數(shù)相差較大，我們對(duì)算法進(jìn)行 了設(shè)置，對(duì)圖進(jìn)行分割時(shí)沒(méi)有要求平衡性。作為對(duì)比，我們還應(yīng)用autoclass對(duì)同一數(shù)據(jù)集進(jìn)行聚類操作。分析聚類結(jié)果，多層概圖方法的聚類結(jié)果，其8 個(gè)簇的文檔數(shù)分別為c1=116，c2=108，c3=74，c4=85，c5=132，c6=94，c7=124，c8=35。其中，有關(guān)商業(yè)、娛樂(lè)、 健康、運(yùn)動(dòng)、農(nóng)業(yè)、技術(shù)的文章聚集相關(guān)性較強(qiáng)，能較好的聚為一類，屬于政治、文學(xué)的文檔，大部分聚為相應(yīng)的兩個(gè)簇，有少部分被聚集到其它類中。以 autoclass方法進(jìn)行文檔的自動(dòng)聚類，結(jié)果聚集為12個(gè)簇，具體分析時(shí)發(fā)現(xiàn)簇內(nèi)文檔有些混亂，許多相似性不大的、明顯處于不同類的文檔被劃分到一 簇，總體聚類質(zhì)量低于多層概圖模型的質(zhì)量。 6、結(jié)論與未來(lái)工作 文檔聚類是高維聚類的重要應(yīng)用領(lǐng)域。我們應(yīng)用多層概圖模型進(jìn)行文檔聚類，把文檔對(duì)象作為圖的頂點(diǎn)，以對(duì)象間的相似性建邊，在對(duì)最小概圖進(jìn)行初始分割后，應(yīng)用精化算法對(duì)劃分進(jìn)行逐層優(yōu)化，取得了較好的效果。 本文應(yīng)用的精化算法仍需要繼續(xù)改進(jìn)。精化操作，可以在多層概圖算法的概化過(guò)程中應(yīng)用，也可以設(shè)計(jì)在反概化過(guò)程中應(yīng)用。作者將進(jìn)一步深入精化算法的研究，進(jìn)一步提高多層概圖模型的性能。 |
|
|
來(lái)自： 123#￥ > 《我的圖書(shū)館》
