基于链接聚类算法分析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的实时的收集。我们要建立一种比较适用于我们应用的图形聚类算法。现在对于邻接关系的图形聚类算法有好多种形式，一般在聚类算法中都是针对的无向图，在处理的过程中，一些有向图也被当作无向图了，文献[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 - ），男，广西忻城人，讲师，计算机工程硕士，研究方向为计算机网络技术和嵌入式系统。