基于鏈接聚類算法分析Blog網頁

劉 葵

LIU Kui

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

基于鏈接聚類算法分析Blog網頁

Blog link clustering algorithm based on analysis of web page

劉 葵

LIU Kui

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

Blog是隨著科技的發展興起的一種是一種新型的網絡表現形式，如今已成為互聯網的又一主體。本文主要是基于鏈接聚類算法來分析Blog網頁，Blog頁面具有不穩定性、即時更新性，以常用圖聚類算法為基礎，根據GMC算法來進行聚類，在此基礎上提Blog聚類的圖聚類算法。并且本文還對GMC算法制定相應的數學解決方案，以得到較高的算法運行效率。

Blog網頁；聚類算法；GMC

0 引言

隨著科技的發展，網絡中出現了一種新的表現形式Blog。本文主要是基于鏈接聚類算法來分析Blog網頁，Blog頁面具有不穩定性、即時更新性，以常用圖聚類算法為基礎，根據GMC算法來進行聚類，在此基礎上提Blog聚類的圖聚類算法。本文還對GMC算法制定相應的數學解決方案，以得到較高的算法運行效率。

1 對鏈接的分析

進行聚類是要在頁面上尋找Blog相似內容討論的社區，這些社區具有一定的談論話題，有很多成員參與。本文進行鏈接聚類算法分析，就需要對Blog內鏈接的類型進行詳細的分析，去掉對聚類結果分析沒有意義的、會造成干擾的鏈接。

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

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

2 對聚類算法的分析

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

2.1 MCL（Markov Cluster）

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

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

2.2 ICC（Iterative Conductance Cutting）

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

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

2.3 GMC（Geometric MST Cluster）

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

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

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

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

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

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

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

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

3 詳細算法實現

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

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

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

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

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

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

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

N=D-1*A

假設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是對稱矩陣，并且它的特征對可以很容易地轉換成N的特征對，問題得以解決。

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

4 對實驗作出分析

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

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

5 結束語

綜上所述，在Blog的特性基礎上，提出了Blog聚類的圖聚類算法，聚類的結果體現出了內容的相關性，也取得了不錯的效果。但從實驗結果中也可以看出，由于鏈接的稀疏性，在Blog上產生了大量的孤立節點，這些節點對于聚類來說是毫無意義的。單純地采用鏈接分析的方法還是存在很大的缺陷，可以綜合其他的算法來加強聚類分析，在一些文獻中已經有了這方面的描述。

[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 - ），男，廣西忻城人，講師，計算機工程碩士，研究方向為計算機網絡技術和嵌入式系統。