北京SEO

随着Internet的迅速发展，Web信息的急速膨胀，在给人
们提供丰富信息的同时，在对它们的有效使用方面又给人们
带来了巨大的挑战[1]。面对信息的海洋，用户试图通过浏览
Web来发现信息已经变得非常困难。搜索引擎正是为解决这
一困难而出现的技术。搜索引擎以一定的策略在互联网中搜
集、发现信息，对信息进行理解、提取、组织和处理，并为用户
提供检索服务。搜索引擎虽然给人们带来了巨大便利，但其搜
索结果不能很好地满足用户的需求。如：搜索引擎返回的大量
结果没有很好的主题关联度[2]。
本文着眼于对Google搜索引擎返回的结果进行分析，将
同类主题的文档进行分类，达到方便用户的目的。主要采用聚
类分析方法，建立文档模型，进行不同文档的相似度计算，构
建符合Web文档的聚类算法，能在短时间内完成大量Web文
档的聚类工作。
1常用聚类算法
聚类的目标是将一组对象划分成若干组或类别,简单地说
就是相似元素同组、相异元素不同组的划分过程[3]。聚类算法
大致可以分为两种：层次化聚类算法和基于划分的聚类算法。
1.1层次化聚类算法[4]
层次化聚类算法可以产生一个生成树结构，这个结构可
以表示基于不同相似度模式的嵌套分组关系。这个生成树结
构可以根据不同的相似度分解为不同的模式聚集。在大多数
层次化聚类算法中，Single-link和Complete-link算法最为常
见，一些其它的层次化聚类算法大多从其发展而来。二者最大
的区别在于处理模式之间相似的特性方式。
1.2基于划分的聚类算法[5]
不同于层次化方法的构建生成树，基于划分的聚类算法
获得一个对数据集合的分割。基于划分的聚类算法的主要问
题是对输出聚类数目的选择。这个选择往往会影响聚类的效
果。因此，在实践中，基于划分的聚类算法常常在不同的初始
状态下运行多次，依据一个判别函数选择出聚类效果最好的
结果进行输出。划分聚类的一个典型算法是K-mean（sK均值
算法）。
2快速聚类算法
对于Web文档聚类要考虑Web文档区别于一般文档的
特点。现针对Google搜索引擎返回的查询结果进行算法设计
分为用于获取和分析搜索引擎返回页面的超文本分析器、文
档模型、索引模型、相似度计算模型、聚类器等五个部分。
2.1超文本分析器
超文本分析器是针对Google搜索引擎返回的查询结果页
面进行分析，抽取出结果中各个文档的标题、网摘及URL。它
分为两个部分：页面抓取器及页面分析器。
页面抓取器和页面分析器需协同工作，笔者设计了两种
数据结构：1）HTML页面池：用于保存页面抓取器抓到的页
面。2）URL地址池：用于保存后续查询结果页面的URL。这二
者都采用先进先出的队列结构。
2.2文档模型
该快速聚类系统建立的文档特征矢量模型为
D
i
=(Ki，1，Wi，
1
)，(K
i，2
，W
i，2
)，……，(K
i，j
，W
i，j
)，……，
其中D
i
表示第i个文档；
Ki
，j
表示第i个文档的第j个关键词；
Wi
，j
表示第i个文档的第j个关键词的权值。
在权值的计算上，选择从词出现的频率上着手，为了更好
的突出文档中的关键词，也为了计算方便，在文档特征矢量计
算完成后，将其转化为单位矢量。统计完每个词的出现次数后
做如下处理：
xi=1
∑
i=1
n
xi
2
姨
，

其中x
i
为文档中第i个词出现的次数。
2.3索引模型
索引模型主要解决在计算机中如何存储抽取的数据集特
征，使其既能保证数据的高效存储，又能方便数据之间的相似
性计算。笔者采用了具有表现方式直观、维护较容易，创建方
法效率高倒排文档模型。倒排表结构如图1所示。
2.4相似度计算模型
文档聚类的最终目标，就是将相似的文档归为一类。相似
度计算模型的选择，对于文档聚类系统的精度有着举足轻重
的作用。由于Web文档聚类系统中文档数目较多，因此聚类
算法中相似度计算算法的调用次数比较多，时空复杂度较高。
为此，设计了一种高效的、占用空间少且精度合适的改进相似
度计算算法。
相似度计算改进算法：
输入———文档特征矢量：x
→
i
，x
→
j
；
输出———相似度；
（1）初始化词权重矩阵；
（2）将x
→
i、x
→
j
各维中的词权重放到权重矩阵中；
（3）计算x
→
i
·x
→
j
（4）for(i=0;i<权重矩阵行数;i++)
TotalWeight=TotalWeight+wordiWeight；
if(word
i
是普通词)CommonWeight=CommonWeight+word
i
Weight；
（5）计算(x
→
i
·x
→
j
)C
ommonWeight
TotalWeight
2.5聚类器
层次化聚类方法直观，使用灵活，但它要求在聚类前完成
相似度的计算。它的时间复杂度为O(n2logn)，空间复杂度达到
O(n2)，这对于海量的Web文档而言，时空开销都是不可接受
的。另外它也不符合Web聚类所要求的渐进性[6]。
划分聚类算法中的K-均值算法，时间复杂度为O(kn1)，
空间复杂度为O(k)。单纯使用K-均值算法是不理想的。因为
K-均值算法中聚类结果中的很大一部份取决于聚类开始时
聚类个数和初始划分，对于大量的从搜索引擎返回的结果，确
定的聚类个数和划分是不可知的。
2.5.1快速聚类算法
结合二者的特点，提出了一种快速聚类算法，即采用层次
化算法解决K-均值算法中的聚类个数。聚类过程分为两个
阶段：
（1）第一个阶段，采用层次化聚类算法对一定数目的
Web文档进行聚类。根据Google中的PageRank算法，PageR-
ank值大的页面排在前边。所以首先选取搜索引擎返回的一定
数目的搜索结果，再用层次化方法进行聚类，得到一个初始聚
类结果作为“种子”聚类集合，然后计算每个聚类的中心。
（2）第二个阶段，采用K-均值算法对后续的大量Web文
档进行聚类。计算该条目与每个聚类中心的距离，将其归入离
聚类中心最近的聚类，然后重新计算该聚类的中心。同时设定
最大距离，如果该条目与所有聚类的距离均大于这个最大距
离，则将该条目作为一个新的聚类。
2.5.2两步迭代过程
聚类过程要不断计算聚类中心，即完成聚集中文档权重
和所含词权重的计算过程，需完成两步迭代过程:
（1）第一步，使用当前对词权重的估计值Wt改进对文本
权重的估计值Wf，找出当前比较重要的词,包含这些词的文
本就是比较重要的文本，因此相应地增加这些文本的权重。
（2）第二步，使用当前对文本权重的估计值Wf改进对词
权重的估计值Wt，找出当前比较重要的文本，经常在这些文
本中出现的词就是比较重要的词,因此相应地增加这些词的权
重。反复进行以上的两步迭代过程，文本权重向量Wf和词权
重向量Wt最终收敛。
2.5.3计算聚类中心算法
计算聚类中心算法：
输入———聚类簇；
输出———聚类中心；
（1）初始化Wf，Wt；
（2）while Wt，Wf未收敛
for(j=0;j<n;j++)
Wt
j
=∑
i=1
m
A
i，j
×Wf
i
转换Wt为单位向量；
for(i=0;i<m;i++)
Wfi=∑
j=1
n
Ai
，j×Wt
j
转换Wf为单位向量；
对于任意给定的初始值，这种迭代过程都是收敛的，并且
最后的值恰好分别是矩阵A×AT和AT×A的某个特征向量。
通过如表1的实验结果可知，文档矢量权值在第七次迭代后
就已收敛。
索引项1
索引项2
索引项3
SnipMeta1 Weight1 SnipMeta2Weight2
SnipMeta1
SnipMeta1
Weight1
Weight1
SnipMeta2
SnipMeta2
Weight2
Weight2 SnipMeta3 Weight3
图1倒排表结构
文档
迭代1
迭代2
迭代3
迭代4
迭代5
迭代6
迭代7
迭代8
迭代9
迭代10
文档1
0.5107747
0.5123394
0.5125684
0.5126019
0.5126067
0.5126075
0.5126076
0.5126076
0.5126075
0.5126075
文档2
0.512882
0.5145977
0.5148296
0.5148614
0.5148655
0.514866
0.5148662
0.5148662
0.5148662
0.5148662
文档3
0.4856193
0.4834808
0.4831637
0.4831163
0.4831093
0.4831083
0.483108
0.4831079
0.4831079
0.4831079
文档4
0.4901378
0.4888188
0.4886481
0.4886265
0.4886239
0.4886235
0.4886236
0.4886236
0.4886236
0.4886236
表1迭代实验数据

3多线程技术实现
由于Web文档数目相当大，采用单线程串行技术实现效
率很低。算法运行时，系统会占用大量CPU资源，使得用户的
请求长时间得不到响应。另外，算法执行过程中，大部分时间
是通过网络获取Google返回结果的页面，由于网络通信环境
不可知，采用单线程串行技术，在等待返回结果的过程中将会
使大量计算机资源处于闲置状态，因而，采用多线程并行技术
实现算法势在必行。采用多线程并行处理技术可以大幅度提
高系统的运行效率。
4实验
在同一网络环境下，对同一关键词，通过设定不同的聚类
文档数进行测试。
网络环境：使用Iperf软件进行网络带宽测试，带宽为
89.9Mbps，网络丢包率为0.035%。
计算机主要性能指标：CPU：Intel Pentium 1.4GHz；256MB
内存。
搜索引擎：Google。
实验数据：关键字为UCLA。
测试结果如表2所示。
实验结论：本系统有较好的聚类效率，可以在线性时间内
完成聚类，适用于对大规模数据进行聚类，文档数与聚类时间
的关系如图2所示。
5结束语
本文提出了一种基于Web文档的快速聚类算法，该算法
的主要特点：第一，它可以对搜索引擎的大量返回结果进行文
本主题的识别；第二，它综合了层次化聚类算法和基于划分的
聚类算法的优点。第三，应用了一种高效的、占用空间少并且
精度合适的相似度计算改进算法。实验证明,快速聚类算法提
高了文本聚类的速度，适用于对大规模数据进行聚类。
参考文献：
[1]王继成，萧嵘，孙正兴，等.Web信息检索研究进展[J].计算机研究
与发展，2001，38（2）：187-193.
[2]徐泽平.数据挖掘在Internet信息检索中的应用[D].北京：中科院计
算所，2001.
[3]吴斌.一种基于群体智能的Web文当聚类算法[J].计算机研究与
发展,2002,39(11):1429-1434
[4]Marques JP.Pattern Recognition Concepts,Methods and Applications.
2nd ed[M].Beijing:Tsinghua University Press,2002.
[5]Fred ALN,Leitao JMN.Partitional vs hierarchical clustering using a
minimum grammar complexity approach[EB].2000.http://www.sigmod.
org/dblp/db/conf/sspr/sspr2000.html.
[6]杨学明.Web中文文本聚类研究及实现[J].北京：现代图书情报技
术，2006，（12）：81-84.
文档数
100
150
200
250
300
350
400
450
500
用时（s）
7.85
8.73
11.62
14.3
17.62
21.30
24.26
28.61
31.51
得到聚类数（个）
86
114
142
179
203
230
259
287
321
表2测试结果
35
30
25
20
15
10
5
100 150 200 250 300 350 400 450 500
t/s
doc number
图2文档数—聚类时间关系