劉 葵

LIU Kui

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

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

Blog link clustering algorithm based on analysis of web page

劉 葵

LIU Kui

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

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

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

0 引言

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

1 對鏈接的分析

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

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

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

2 對聚類算法的分析

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

2.1 MCL（Markov Cluster）

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

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

2.2 ICC（Iterative Conductance Cutting）

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

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

2.3 GMC（Geometric MST Cluster）

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

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

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

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

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

綜合起來，GMC算法可以描述如下：

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

GMC相對前兩個算法來說，相對簡單，且可充分地利用生成的鄰接矩陣的稀疏性，最終聚類的效果也很不錯[2]。

3 詳細算法實現(xiàn)

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

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

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

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

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

即對于對稱陣，可采用從原矩陣中減掉極端特征對的方法來求第二極端的特征對。

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

N=D-1*A

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

Nv=cv

D-1Av=cv

D-1/2Av=cD1/2v

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

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

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

4 對實驗作出分析

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

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

5 結(jié)束語

綜上所述，在Blog的特性基礎(chǔ)上，提出了Blog聚類的圖聚類算法，聚類的結(jié)果體現(xiàn)出了內(nèi)容的相關(guān)性，也取得了不錯的效果。但從實驗結(jié)果中也可以看出，由于鏈接的稀疏性，在Blog上產(chǎn)生了大量的孤立節(jié)點，這些節(jié)點對于聚類來說是毫無意義的。單純地采用鏈接分析的方法還是存在很大的缺陷，可以綜合其他的算法來加強聚類分析，在一些文獻中已經(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 - ），男，廣西忻城人，講師，計算機工程碩士，研究方向為計算機網(wǎng)絡(luò)技術(shù)和嵌入式系統(tǒng)。