基于鏈接聚類算法分析Blog網(wǎng)頁(yè)

劉 葵

LIU Kui

（浙江紡織服裝學(xué)院 機(jī)電與信息工程分院， 寧波 315211）

基于鏈接聚類算法分析Blog網(wǎng)頁(yè)

Blog link clustering algorithm based on analysis of web page

劉 葵

LIU Kui

（浙江紡織服裝學(xué)院 機(jī)電與信息工程分院， 寧波 315211）

Blog是隨著科技的發(fā)展興起的一種是一種新型的網(wǎng)絡(luò)表現(xiàn)形式，如今已成為互聯(lián)網(wǎng)的又一主體。本文主要是基于鏈接聚類算法來(lái)分析Blog網(wǎng)頁(yè)，Blog頁(yè)面具有不穩(wěn)定性、即時(shí)更新性，以常用圖聚類算法為基礎(chǔ)，根據(jù)GMC算法來(lái)進(jìn)行聚類，在此基礎(chǔ)上提Blog聚類的圖聚類算法。并且本文還對(duì)GMC算法制定相應(yīng)的數(shù)學(xué)解決方案，以得到較高的算法運(yùn)行效率。

Blog網(wǎng)頁(yè)；聚類算法；GMC

0 引言

隨著科技的發(fā)展，網(wǎng)絡(luò)中出現(xiàn)了一種新的表現(xiàn)形式Blog。本文主要是基于鏈接聚類算法來(lái)分析Blog網(wǎng)頁(yè)，Blog頁(yè)面具有不穩(wěn)定性、即時(shí)更新性，以常用圖聚類算法為基礎(chǔ)，根據(jù)GMC算法來(lái)進(jìn)行聚類，在此基礎(chǔ)上提Blog聚類的圖聚類算法。本文還對(duì)GMC算法制定相應(yīng)的數(shù)學(xué)解決方案，以得到較高的算法運(yùn)行效率。

1 對(duì)鏈接的分析

進(jìn)行聚類是要在頁(yè)面上尋找Blog相似內(nèi)容討論的社區(qū)，這些社區(qū)具有一定的談?wù)撛掝}，有很多成員參與。本文進(jìn)行鏈接聚類算法分析，就需要對(duì)Blog內(nèi)鏈接的類型進(jìn)行詳細(xì)的分析，去掉對(duì)聚類結(jié)果分析沒有意義的、會(huì)造成干擾的鏈接。

對(duì)于典型的Blog，對(duì)于一些鏈接，首先要剔除。一般Blog，除了日志內(nèi)容外，還會(huì)有很多的鏈接，主要是為了進(jìn)行用戶本身的Blog內(nèi)、日志作者所在的Blog站內(nèi)、站外還有廣告的跳轉(zhuǎn)，這樣的鏈接對(duì)于聚類分析是沒有任何意義的。

對(duì)于正文內(nèi)的Blog鏈接，則要分成兩部分來(lái)考慮，一是和正文內(nèi)容確實(shí)有關(guān)聯(lián)的，二是一些Blog作者想擴(kuò)大自己網(wǎng)頁(yè)的影響面，會(huì)在文章的結(jié)尾用廣告的方式插進(jìn)去，這種鏈接，我們需要篩選出來(lái)剔除，但是這種鏈接比較難以識(shí)別，為保證聚類主題的核心，只好采用所有和Blog用戶同一主域名的鏈接，全部忽略這在一定程度上會(huì)對(duì)合格的日志作者造成影響。

2 對(duì)聚類算法的分析

從廣義上講，Blog可以看作是一種類型的Web頁(yè)面，但從現(xiàn)行的Blog頁(yè)面形式來(lái)看，Blog網(wǎng)頁(yè)中已經(jīng)不存在傳統(tǒng)意義上的中樞頁(yè)面概念，作為Blog用戶可以根據(jù)自己的需要隨時(shí)增刪自己的日志。而且，Blog也很少能成為比較權(quán)威的頁(yè)面，主要是因?yàn)锽log日志更多記錄的是個(gè)人生活化的隨筆，因此，限制了Blog日志向權(quán)威方面的發(fā)展。我們用到的數(shù)據(jù)都是源自于網(wǎng)上的Blog的實(shí)時(shí)的收集。我們要建立一種比較適用于我們應(yīng)用的圖形聚類算法?，F(xiàn)在對(duì)于鄰接關(guān)系的圖形聚類算法有好多種形式，一般在聚類算法中都是針對(duì)的無(wú)向圖，在處理的過程中，一些有向圖也被當(dāng)作無(wú)向圖了，文獻(xiàn)[2]中對(duì)此作了比較詳細(xì)的介紹。在這里介紹幾種比較重要的常用的算法。

2.1 MCL（Markov Cluster）

這種聚類算法是以隨機(jī)游走為基礎(chǔ)的[3]。它的基本思想是，對(duì)于和每個(gè)節(jié)點(diǎn)相連的邊，根據(jù)權(quán)重比較賦予游走的概率。比如節(jié)點(diǎn)有權(quán)重為0.5 1.5 3 4 5的四條邊，則從該節(jié)點(diǎn)沿著這幾條邊走出去的概率分別為1/28，3/28，3/14，2/7，5/14，假如我們記k步以前從節(jié)點(diǎn)i走到節(jié)點(diǎn)j的概率聚陣為N(k)，那么讓k趨向于無(wú)窮大，我們就可以得到從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的概率矩陣N。取定適當(dāng)?shù)拈撝担蕹齆中的小概率元素，然后確定連通分支，得出最后的聚類結(jié)果。

MCL算法的實(shí)驗(yàn)結(jié)果，是比較理想的，但是它的致命缺點(diǎn)在于，對(duì)于規(guī)模比較大的圖，中間求冪循環(huán)復(fù)雜度較高，尤其對(duì)于大規(guī)模的稀疏矩陣，計(jì)算出的中間結(jié)果N將很快變得稠密，導(dǎo)致無(wú)法充分利用圖的邊稀疏性這一特點(diǎn)。

2.2 ICC（Iterative Conductance Cutting）

這種聚類算法的基本思想和二分法比較相似，就是要對(duì)圖不斷地使用最小割算法進(jìn)行二分，直至得到滿意的結(jié)果。計(jì)算最小割NP-hard的，通常采用的是一種近似的poly-logarithmic的算法：

ICC算法的計(jì)算結(jié)果缺陷，就是它的聚類最重類的大小需要人工操作進(jìn)行控制，這與我們Blog聚類開始的目標(biāo)有一定的差距，我們的目的是緊密聯(lián)系在一起的Blog頁(yè)面，都可以作為一類，不用管這個(gè)類的規(guī)模大小。由于Blog的社會(huì)性或者說不確定性，我們面對(duì)如此龐雜的數(shù)據(jù)無(wú)法得出最終聚類的規(guī)模，而且也不適宜一刀切的模式來(lái)規(guī)劃所有類，所以ICC并不適用于我們的應(yīng)用。

2.3 GMC（Geometric MST Cluster）

GMC算法與前兩個(gè)算法相比并不是那么直觀和容易理解。它是從一類稱作譜方法（Spectral Method）的算法中推演而來(lái)的。這類方法的一般過程可以總結(jié)如下：

1）對(duì)于給定的加權(quán)圖G，計(jì)算它的鄰接矩陣M；

2）計(jì)算M的特征向量x1，x2，…，xk；

3）利用x1，x2，…，xk生成聚類（該步通稱為Interpretation）。

這類算法，第1）步基本上都是一樣的。對(duì)于GMC，第2）3）步中的k通常設(shè)為2或者3。第3）步interpretation是最重要的，它決定著整個(gè)聚類的質(zhì)量。GMC的第3）步可具體描述如下：（1）計(jì)算特征向量x1，x2，…，xk的一個(gè)加權(quán)和v；（2）利用v重新定義圖中所有邊的權(quán)重wi,j=|vivj|；（3）對(duì)新的權(quán)重計(jì)算該圖的一個(gè)最小生成樹（Minimum Spanning Tree，MST）；（4）給定一個(gè)閾值，將（3）中得到的MST中所有權(quán)重小于該閾值的邊砍掉；（5）計(jì)算各連通分支，即是最后的聚類結(jié)果。

綜合起來(lái)，GMC算法可以描述如下：

1）計(jì)算鄰接矩陣M并規(guī)一化為矩陣N（所謂規(guī)一化，即將每行的元素除以該行元素的和以使得每行元素和均為1）；2）計(jì)算N的除1之外的最大的k個(gè)正特征值對(duì)應(yīng)的特征向量（通常k取2，3）；3）根據(jù)特征向量計(jì)算邊的新權(quán)值；4）根據(jù)新權(quán)值生成MST；5）分別計(jì)算原圖以及MST的平均權(quán)重和最大權(quán)重；6）根據(jù)平均權(quán)重和最大權(quán)重確定閾值；7）根據(jù)閾值刪除MST中的相應(yīng)邊；8）求MST的連通分支，即是聚類結(jié)果。

GMC相對(duì)前兩個(gè)算法來(lái)說，相對(duì)簡(jiǎn)單，且可充分地利用生成的鄰接矩陣的稀疏性，最終聚類的效果也很不錯(cuò)[2]。

3 詳細(xì)算法實(shí)現(xiàn)

我們的算法可以綜述如下：

1）處理過濾Blog數(shù)據(jù)的鏈接，生成以頁(yè)面（URL）為頂點(diǎn)，鏈接為邊的圖；2）處理圖的鄰接關(guān)系，產(chǎn)生鄰接矩陣；3）使用GMC算法聚類。

其中第一步由于把圖看作無(wú)向的來(lái)處理，因此對(duì)于兩個(gè)頁(yè)面相互鏈接的情況，可認(rèn)為它們之間的邊的權(quán)重為2，因此生成的是一個(gè)邊權(quán)重可取1，2的無(wú)向圖。

算法的第三步GMC算法的具體實(shí)現(xiàn)可參考3.3節(jié)中GMC算法的步驟，可以看到，GMC算法中除了第二步之外，其余的七步都很容易實(shí)現(xiàn)。對(duì)于第二步計(jì)算特征向量，注意到我們只需要求兩到三個(gè)極端的特征對(duì)，因此我們采用了冪迭代的方法。但是通常來(lái)說，冪迭代只能求一個(gè)極端特征對(duì)，而我們要求的是多個(gè)。對(duì)于對(duì)稱矩陣，有比較簡(jiǎn)單的方法：

對(duì)于n階對(duì)稱矩陣A，假設(shè)c1，c2，…，cn是它的特征值，v1，v2，…，vn是對(duì)應(yīng)的正交單位特征向量，那么就有：

即對(duì)于對(duì)稱陣，可采用從原矩陣中減掉極端特征對(duì)的方法來(lái)求第二極端的特征對(duì)。

但是，注意到要求特征對(duì)的矩陣N是規(guī)一化之后的，盡管規(guī)一化之前的鄰接矩陣M是對(duì)稱陣，但是不能保證N也是對(duì)稱的。所以，還需要一點(diǎn)小技巧來(lái)求N的特征對(duì)。假設(shè)A是對(duì)稱陣，D是以A的每行元素之和為對(duì)角元素的對(duì)角陣，N是A的規(guī)一化之后的矩陣，那么：

N=D-1*A

假設(shè)c,v是N的一個(gè)特征對(duì)，則：

Nv=cv

D-1Av=cv

D-1/2Av=cD1/2v

D-1/2AD-1/2D1/2v = cD1/2v

這里D-1/2AD-1/2是對(duì)稱矩陣，并且它的特征對(duì)可以很容易地轉(zhuǎn)換成N的特征對(duì)，問題得以解決。

由于建立的圖是一個(gè)規(guī)模較大的邊稀疏的圖，對(duì)應(yīng)到鄰接矩陣就是一個(gè)大規(guī)模的稀疏對(duì)稱矩陣，需要充分地利用而不要破壞這一特性。GMC算法中，對(duì)稱性雖然被破壞，但通過一個(gè)簡(jiǎn)單的變換來(lái)加以恢復(fù)，且這種變換后的矩陣稀疏性和原矩陣相同，從而稀疏性得以保留。冪迭代算法同樣不會(huì)改變?cè)仃嚨南∈栊?，這樣就可充分地利用稀疏矩陣的數(shù)值算法。

4 對(duì)實(shí)驗(yàn)作出分析

我們的實(shí)驗(yàn)數(shù)據(jù)是大約3千萬(wàn)個(gè)從網(wǎng)上隨機(jī)抓取的Blog，運(yùn)行平臺(tái)是志強(qiáng)雙核CPU（1.8GHz）+UNIX，每運(yùn)行一次聚類算法，大約需要十五分鐘，該時(shí)間說明程序的運(yùn)行效率還是比較高的。

程序運(yùn)行的結(jié)果大約產(chǎn)生了一百多萬(wàn)個(gè)聚類，其中絕大部分都是單個(gè)的頁(yè)面作為一類，有大概一千個(gè)聚類是規(guī)模比較大的，這是有意義的結(jié)果，通過對(duì)其中網(wǎng)頁(yè)內(nèi)容的分析，基本上都是內(nèi)容相關(guān)的，與我們目標(biāo)相一致。至于單個(gè)頁(yè)面作為一類的情況，是因?yàn)轫?yè)面正文中沒有有意義的鏈接，因此成為單獨(dú)的一類。

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

綜上所述，在Blog的特性基礎(chǔ)上，提出了Blog聚類的圖聚類算法，聚類的結(jié)果體現(xiàn)出了內(nèi)容的相關(guān)性，也取得了不錯(cuò)的效果。但從實(shí)驗(yàn)結(jié)果中也可以看出，由于鏈接的稀疏性，在Blog上產(chǎn)生了大量的孤立節(jié)點(diǎn)，這些節(jié)點(diǎn)對(duì)于聚類來(lái)說是毫無(wú)意義的。單純地采用鏈接分析的方法還是存在很大的缺陷，可以綜合其他的算法來(lái)加強(qiáng)聚類分析，在一些文獻(xiàn)中已經(jīng)有了這方面的描述。

[1] K.Bhatart,M.Henzinger.Improved Algorithms for Topic Distillation in Hyperlink Environments.The 21st ACM SIGIR Conf.on Research and Development in Information Retrieval,Melbourne,Australia,1998.

[2] U.Brandes,M.Gaertler,and D.Wagner."Experiments on graph clustering algorithms.",Proceedings of the ESA 2003 Eleventh European Symposium on Algorithms,pp.568-579,LNCS 2832, Berlin：Springer-Verlag,2003.

[3] Van Dongen S.M.：Graph Clustering by Flow Simulation.PhD thesis,University of Utrecht (2000).

TP301.6

B

1009-0134(2010)09-0215-03

10.3969/j.issn.1009-0134.2010.09.66

2010-05-20

劉葵（1970 - ），男，廣西忻城人，講師，計(jì)算機(jī)工程碩士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)和嵌入式系統(tǒng)。