FPC: 大规模网页的快速增量聚类

余 钧，郭 岩，张 凯，刘 林，刘 悦，俞晓明，程学旗

(1. 中国科学院 计算技术研究所 中国科学院网络数据科学与技术重点实验室，北京 100190; 2. 中国科学院大学，北京 100190; 3. 中国信息安全评测中心，北京 100085)

FPC: 大规模网页的快速增量聚类

余 钧1,2，郭 岩1，张 凯1，刘 林3，刘 悦1，俞晓明1，程学旗1

(1. 中国科学院 计算技术研究所 中国科学院网络数据科学与技术重点实验室，北京 100190; 2. 中国科学院大学，北京 100190; 3. 中国信息安全评测中心，北京 100085)

面向结构相似的网页聚类是网络数据挖掘的一项重要技术。传统的网页聚类没有给出网页簇中心的表示方式，在计算点簇间和簇簇间相似度时需要计算多个点对的相似度，这种聚类算法一般比使用簇中心的聚类算法慢，难以满足大规模快速增量聚类的需求。针对此问题，该文提出一种快速增量网页聚类方法FPC(Fast Page Clustering)。在该方法中，先提出一种新的计算网页相似度的方法，其计算速度是简单树匹配算法的500倍；给出一种网页簇中心的表示方式，在此基础上使用Kmeans算法的一个变种MKmeans(Merge-Kmeans)进行聚类，在聚类算法层面上提高效率；使用局部敏感哈希技术，从数量庞大的网页类集中快速找出最相似的类，在增量合并层面上提高效率。

DOM树分层向量；网页簇中心；局部敏感哈希；快速增量聚类

1 引言

Web抽取是网络数据挖掘中的重要应用。针对海量网页的抽取，可以把结构相似的网页自动聚成一类，对聚类后的网页簇归纳出高效精确的抽取规则，从而提高抽取的准确率。传统的面向结构的网页聚类算法中，通常没有给出网页簇中心的表示方式。它们一般使用代表点的聚类算法，在计算点簇间距离和簇簇间距离时需要计算多个点对的距离，难以应用到大规模网页增量聚类中。

为了解决面向结构的大规模网页聚类问题，本文提出一种快速网页增量聚类方法FPC(Fast Page Clustering)。在该方法中，先提出DOM树分层向量，用多个DOM树分层向量的中心来近似反映多棵DOM树的中心。在此基础上，采用基于向量、集合相似度的方式来计算两个网页的相似度，其计算效率比传统的树编辑距离高；给出一种网页簇中心的表示方式，进而提出使用Kmeans算法的一个变种MKmeans(Merge-Kmeans)，实现网页的快速聚类；使用局部敏感哈希技术，从数量庞大的网页类集合中可以快速找出和给定类最相似的类，从而实现快速增量聚类。实验表明：(1)选用的网页特征确实有效合理，网页簇中心确实可以代表网页簇的一些公共结构中心，在网页聚类中很有效；(2)相似的网页类，使用局部敏感哈希技术计算得到的指纹也相似，可以用于快速查找近似最相似类；(3)FPC的速度远高于传统的网页聚类方法，且其准确率和回收率都非常高。

本文余下章节安排如下: 第二节介绍相关工作；第三节介绍快速网页增量聚类方法FPC；第四节是实验结果和分析；第五节是对本文的总结并讨论下一步的研究方向。

2 相关工作

计算两个网页的相似度有很多办法。文献[1]使用DOM树编辑距离来表示两个网页的相似度，这种方法计算代价较高。文献[2]使用局部标签树匹配的方法来进行聚类，将DOM 树的每一层节点的HTML标签连接成串，计算对应层字符串的编辑距离的加权和作为两个网页的距离，这种方法要求每层节点个数相差不大,对记录型网页效果不太好。文献[3]使用链路压缩树来定义网页的相似度，这种方法对高层节点很敏感。文献[4]使用自顶向下的树编辑距离来计算网页的相似度，这种方法对高层节点也很敏感，高层节点不匹配，则相似度非常小。

传统的网页聚类使用点代表的聚类方法，这些算法的执行效率较低，难以应用到大规模网页增量聚类中。文献[5]用的是自底向上的CURE算法，两个簇间的距离由这两个簇中距离最近的数据点的距离来确定。文献[6]用的是类CURE算法，两个簇间的距离由来自两簇的所有点对的距离的平均值来确定。

局部敏感哈希技术(Locality Sensitive Hash)主要用来解决高维空间中点的近似最近邻搜索问题。LSH将原始空间中的点嵌入到汉明(Hamming)空间中，原始空间中的度量变成Hamming空间中的度量。文献[7]使用局部哈希技术将一个网页映射到一个64位的二进制指纹上，通过查找相似的指纹可以快速检测出内容近似的网页。

3 快速增量聚类方法FPC

本文的FPC方法使用基于向量、集合的相似度来计算两个网页的相似度，比传统的基于树编辑距离和链路方法快得多；给出一种网页簇结构中心的表示方式，在这个基础上提出使用一种类似Kmeans的算法MKmeans(Merge Kmeans)实现网页的快速聚类；并使用局部敏感哈希技术从大规模的网页簇中快速找出近似最相似簇，实现快速增量聚类。

3.1 网页特征

网页是一种半结构化数据，同模板生成的网页，在结构上较相似，在内容上也相似，如广告链接、导航栏和版权信息等可能也会相似。FPC从网页中提取若干结构特征和内容特征，用来表示一个网页。

3.1.1 DOM树分层向量

DOM树是一个重要的网页结构特征，但是计算DOM树的编辑距离的代价太高。在HTML标记语言中，大部分标签是不能随意插入和删除的，标签的嵌套关系相对比较固定，同模板网页，语义相同的节点链路一般也会相同。

基于这个事实，给出下面的假设：

(1) 两个同模板网页，它们匹配上的节点大多处在树中同一层位置上；

(2) 在一个网页内，相同语义的迭代型节点(如帖子根节点)一般处在同一层位置上；

(3) 相同语义的迭代型节点，它们子树中每一层的节点分布相似，于是对同模板的网页，它们在迭代子树上标签的频率分布也相似。

由这些假设可以推出，同模板网页，它们在每层的标签分布向量也会相似。本文为此引入DOM树分层向量，该向量组是一个有序向量组，它的第i个向量表示树的第i层节点按标签名的频率分布。

定义1 DOM树分层向量，如式(1)所示。

(1)

图1的两个网页中，网页1的DOM树分层向量是： (html: 1), (head: 0.5,body: 0.5), (meta: 0.5,div: 0.25,a: 0.25) (p: 1)。网页2的DOM树分层向量是：(html:1), (head: 0.5,body: 0.5), (meta: 0.4,div: 0.4,a: 0.2)。

图1 样例页面

多个DOM树分层向量的中心也是一个分层向量，它的第i个向量是所有这些分层向量的第i个向量的中心。对DOM树，很难找出多棵DOM树的中心骨干。但对于多个DOM树分层向量，可以快速地计算出它们的中心。

定义2 DOM树分层向量的中心，如式(2)所示。

(2)

结构相似的网页，其DOM树分层向量相似，且它们的中心也和它们相似。对多个网页的中心向量，在相似层，它和各网页对应层向量的平均相似度较大；在不相似层，它和各网页对应层向量的平均相似度会较小。设置阈值，当中心的某层向量到各网页层的平均相似度较小时，则从中心去掉该层的向量，这样得到的中心分层向量将会保存这些网页中相似层部分，不相似层将会去掉。

如图1，网页1和网页2较相似，它们的DOM树分层向量的中心是：(html: 1), (head: 0.5,body: 0.5), (meta: 0.45,div: 0.325,a: 0.225) (p: 0.5)。

3.1.2 其他特征

同模板网页有一些属性值比较特殊的标签，如Discuz论坛软件生成的帖子页面中，会经常出现这种标签。本文用标签-属性特征来保存具有特定属性的标签的标识串，标识串的格式是“标签名+属性名+属性值”。

FPC选取部分内容作为网页的特征。这些内容特征包括：链接地址、CSS文件名、JS文件名、JS中出现的函数名、锚文本、短文本、图片名。

这些特征都是集合型的，每个特征包含多个字符串。多个网页，它们对应特征会有若干共同元素，这些共同元素是这些网页的公共固定部分。可以用集合中心来表示多个网页的集合型特征的公共固定部分。

定义3 多个集合的中心

多个集合的中心是一个集合，该中心集合中的元素是在这些集合中出现比例超过某个阈值的元素。

3.2 网页表示和网页簇中心表示

FPC选取九个网页特征，在这些基础上给出网页和网页簇的中心的表示方式，并给出相似度的计算方法。

3.2.1 网页表示

我们使用DOM树分层向量，以及3.1.2节中的八个特征来表示一个网页。从网页中计算出DOM树分层向量，找出标签-属性值、链接地址等内容特征，可以将网页映射到一个特征向量上。

定义 4 网页表示为式(3)。

(3)

其中，fi是网页的第i个特征，除了DOM树分层向量外，其他特征都是集合型的。

3.2.2 网页簇中心表示

许多聚类算法要求给出簇中心的表示方法。FPC将网页簇中心定义为一个隐藏网页，它包含网页的九个特征，其所反映的是簇中网页的公共固定部分。它的各个特征是簇中所有网页相应特征的中心。

定义5 网页簇中心，如式(4)所示。

(4)

其中P1,…,Pn表示n个网页，fi,Pk是网页Pk的第i个特征，i=1,..9,k=1,…,n。对DOM分层向量，按定义2的方式给出其中心，对其余八个集合型特征，按定义3的方式给出其中心。网页簇中心可以很好地反映簇中网页的共同稳定部分。如果簇中网页相似，则簇中心和它们也相似。

3.2.3 相似度计算

网页与网页、网页与网页簇的相似度，是各个特征相似度的加权和，计算公式如式(5)所示。

(5)

其中S1,S2是网页或网页簇中心，weightfi是特征fi的权重，Simfi是特征fi的相似度。

对两个DOM树分层向量，它们的相似度是各对应层向量的余弦相似度之和除以两者向量层数和的一半，计算公式如式(6)所示。

(6)

对集合型的特征，相似度计算采用不同的计算方式。

1. 两个网页，或者两个簇中心，它们的集合型特征的相似度使用Jaccard相似性度量，平滑后的公式为式(7)。

(7)

其中S1,S2都是网页或者都是簇中心的集合型特征，α是FPC中MKmeans算法合并簇的相似度阈值。

2. 网页和簇中心，它们的集合型特征的相似度稍有不同，平滑后的公式为式(8)。

(8)

其中S是网页的集合型特征，T是簇中心的集合型特征。

3.3 增量聚类

FPC使用Leader-Follower策略进行网页增量聚类，即将网页分批聚类，对每批聚类后的类，从已有类集中查找最相似的类，如果它们的相似度大于给定阈值，则将它们合并在一起，否则将该类作为新类并添加到类集中。

3.3.1 单批网页聚类算法MKmeans

Kmeans算法需要提前指定类别个数，但是网页类别的个数通常难以提前确定。为此，FPC提出使用一种类似Kmeans的算法MKmeans(Merge-Kmeans)，该算法不需要提前指定K值，聚类结果中类个数是由合并类的阈值间接决定。通过修改类合并阈值，可以使得聚类后每类网页的类内平均相似度都较高。MKmeans算法如下。

算法1 聚类算法MKmeans(Merge-Kmeans)

输入：网页集合S，初始类相异阈值d，类合并阈值α，类内平均相似度变化阈值e，最大迭代次数T

输出：网页类

1. 初始类中心：对S中的网页，逐个计算其与已有类中心的相似度，如果最大相似度小于阈值d，则该网页成为一个新的类中心；

2. 归入最近类：将S中的网页逐个归入最相近的类；

3. 更新类中心：计算每个类中心，它是类中所有网页的中心；

4. 合并相似类：计算各对类的相似度，不断合并最相似的类，直到所有类之间的相似度都小于阈值α；

5. 迭代步骤2,3,4，直到迭代次数超过T或类内平均相似度的变化已经小于阈值e。

3.3.2 增量合并

在增量聚类的过程中，如果类集中类的个数太多，则从中查找最相似类的时间开销将很大。FPC使用局部敏感哈希技术计算出类的指纹信息，用其来筛选出小部分备选类，再从备选类中找最相似类。FPC对一个网页类，可以计算得到一个指纹组，一个指纹组包含32个16位的二进制指纹。计算指纹组算法如下。

算法2 计算指纹组算法FingerPrints

输入： 一个网页类C，四个哈希函数Hi，i=1,2,3,4

输出：指纹组(32个16位的二进制指纹)

1. 对哈希函数Hi(i=1,2,3,4)，依次

1.1使用一个128位的二进制数X，将其清零；

1.2对网页类C的中心的标签-属性特征中的每个元素，分别用Hi计算其哈希结果hashvalue，将X的第hashvalue%128位置1；

1.3将X切分成八个16位的二进制数，得到八个指纹；

2. 每个哈希函数得到八个指纹，四个哈希函数共得到32个指纹，返回指纹组。

指纹组中的指纹是有序的，两个指纹组相似度等于两组对应序号且相等的指纹的个数除以指纹组长度32。计算公式如式(9)所示。

(9)

其中，F1,i是指纹组FS1的第i个指纹，F2,i是指纹组FS2的第i个指纹，

相似的网页类，它们的指纹组很可能也相似，利用指纹组，可以快速地找出近似最相似的类，从而实现快速增量聚类。FPC在增量聚类的过程中，保存已有类集中每个类的中心及其指纹组信息，同时保存32个指纹的倒排索引表，索引内容是类的标识。子类合并算法如下。

算法 3 子类合并到类集中算法 Merge-Cluster

输入：子类C，类库(S,F, IDX)，S是已有类集，F是类的指纹组表，IDX=(index1,…,index32)是32个指纹索引表，指纹相似阈值β

输出：合并C后的类库(S,F, IDX)

1. 计算C的指纹信息F1,…,F32；

2. 分别从index1,…,index32中找到F1,…,F32对应的索引列l1,…,l32；

3. 在索引列l1，…,l32中找出出现次数超过32*β的类，记这些类为备选类；

4. 从备选类中找出和子类C最近的类，如果相似度大于给定阈值，则将子类C和最相似的类进行合并；否则，子类C成为一个新的类，添其加到类集中。

5. 更新发生变化的类的指纹组表F和索引表IDX。

4 实验与分析

4.1 聚类实验

本实验是为了评测FPC中聚类方法的效果。对比实验使用STM计算相似度，用文献[6]中用于网页聚类的类CURE算法进行聚类，该类CURE算法用两个类之间所有的点对的平均相似度作为两个类的相似度，不断合并最相似的类，直到所有的类的相似度小于给定阈值。本文将该对比实验方法称为STM+CURE。

4.1.1 实验数据

数据集1：采集15个新闻网站，每个网站采集20个网页，共300个网页。我们认为，由相同软件生成的网页属于同一模板，于是将这300个网页分为15个模板类。

数据集2：采集100个论坛网站，每个网站采集10个网页，共1 000个网页，分为23个模板类。

4.1.2 评价指标

我们使用以下三种指标进行评价：

1. 准确率 Precision, 回收率Recall， F值。

2. 时间开销，评测两者的效率。

4.1.3 结果分析

考虑到对比实验中的类CURE算法时间复杂度较高，我们在实现类CURE算法时，做了很多优化。实验结果如表1所示。

表1 聚类测试结果

注：APS-Time(Average Page Similarity Time)：计算两个网页相似度的平均时间开销。

另外，在数据集2上，前者的回收率比后者高出62.5%。这是因为STM算法太过敏感，在计算树的相似度时，如果两棵子树的根节点不一样，则认为这两棵子树的匹配数为0，于是若两棵子树高层节点偏差稍大，则可能导致计算得到的相似度很小，从而使得同类网页被错误分开。而FPC是把各层的相似度类加起来，高层结点差异不影响计算低层的相似度。因此，FPC算法健壮性更好，适用范围更广，回收率也更高。

同时，FPC的准确率也很高。这表明FPC中所选用的网页特征确实很有效，网页簇中心能很好地反应多个网页的一些公共固定部分，将其用在簇中心代表的聚类算法中很有效。

4.2 指纹实验

本实验是为了验证两方面内容：(1)指纹相似，则类也较相似；(2)利用指纹可以有效筛选出类集中一小部分备选类，最相似的类落在备选集中的概率会很大。

4.2.1 实验数据

数据集3：采集1160个网站网页，每个网站采集5个网页，共5 800个网页。聚成302个类，记为类集3。

数据集4：采集855个网站网页，每个网站采集5个网页，共4 275个网页。聚成149个类，记为类集4。

数据集4所选的网站绝大部分是来自数据集3中所选的网站，但这两个数据集所用网页完全不一样。因此，类集3和类集4间虽然有许多类是相似的，但它们不会完全一样(这里指类中心的特征不会完全相同)。

4.2.2 结果分析

计算类集3和类集4之间所有类对的类相似度和指纹相似度，得到指纹相似度—类相似度曲线，如图2所示。

对类集4中的每一个类，计算其指纹，从类集3中筛选出和其指纹相似度超过阈值β的备选类，检测和其最相似的类是否落在备选类集中。表2给出不同指纹相似阈值β下的备选集大小，同时还给出最相似的类落在其中的概率。

图2 指纹相似度-类相似度曲线

表2 备选集测试结果

注：备选集大小是指，备选集在整个类集3中所占的比例。

从图2可以看出，指纹相似度和类相似度存在一种很好的正相关关系，两个类的指纹越相似，则这两个类也越可能相似。从表2可以看出，利用指纹可以筛选出一个很小的备选类集，而最相似类落在备选集中的概率会非常大。例如，当指纹相似阈值取0.05时，就可以筛选出一个6.9%大小的备选集，而最相似类落在该备选集中的概率是90.6%。

因此，在增量合并类的过程中，可以筛选出一小部分备选集，最相似的类落在备选集中的概率很大，即使最相似类没有落在备选集中，从备选集中仍然可以找出和其很相似的类。例如，从图2中可以看出，当指纹相似阈值取0.45时，备选集中的类和需合并的子类的平均相似度达到0.3。因此，利用局部敏感哈希，确实可以从很小的备选集中近似找到最相似的类，从而大大提高FPC在增量合并类的效率。

5 结论

本文先提出DOM树分层向量概念，给出一种新的计算网页相似度的方法，其速度是简单树匹配算法的500倍，并且适用范围更广。本文还提出一种网页簇中心的表示方式。在这些基础上用类Kmeans算法MKmeans实现网页的快速聚类，其正确率回收率都很高，这表明所选的网页特征和网页簇中心表示方式确实非常有效。最后，本文使用局部敏感哈希技术，可以在庞大的网页类集中快速找出近似最相似的类，从而提高增量合并中查找相似类的效率。

本文在使用公式(1)计算网页相似度时，各个特征权重是预先设定的，在接下来的工作中准备通过一些机器学习方法训练出更好的参数。另外，网页簇中心除了用在聚类上，还可以用在分类上。如何使用网页簇中心以用于分类当中，这是一个有待继续研究的问题。

[1] Reis D C,Golgher P B, Silva A S, et al. Automatic Web news extraction using tree edit distance[C]//Proceedings of the 13th International Conference on World Wide Web. New York: ACM.

[2] 李 睿, 曾俊瑀, 周四望. 基于局部标签树匹配的改进网页聚类算法[J]. 计算机应用, 2010，30(3)：818-820.

[3] 宋明秋, 张瑞雪. 基于链路压缩树的网页相似度研究[J]. 情报学报, 2012，31(1)：40-46.

[4] 何昕,谢志鹏. 基于简单树匹配算法的Web页面结构相似性度量[J]. 计算机研究与发展, 2007，44(23)：1-6.

[5] 邱韬奋,杨天奇,曾洪波. 基于网页聚类的Web 信息自动抽取[J]. 微型机与应用, 2011，31(4)：71-74.

[6] 赖春波. Web信息自动抽取技术研究[D]. 浙江:浙江大学, 2008.

[7] Gurmeet Singh Manku, Arvind Jain, Anish Das Sarma. Detecting near-duplicates for web crawling[C]//Proceedings of the 16th International Conference on World Wide Web, Banff, Alberta, Canada, 2007: 141-150.

FPC: Fast Incremental Clustering for Large Scale Web Pages

YU Jun1,2, GUO Yan1,ZHANG Kai1, LIU Lin3, LIU Yue1, YU Xiaoming1, CHENG Xueqi1

(1. CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China； 2. University of Chinese Academy of Sciences, Beijing 100190, China；3. China Information Technology Security Evaluation Center, Beijing 100085, China)

Structure-oriented web page clustering is one of the most important technique in web data mining. Previous traditional methods haven’t given a formal definition of the web page cluster center and have to calculate several point-wise similarities for the purpose of getting the similarity between a point and a cluster or the similarity between two clusters. The efficiency of these methods is much slower than the clustering algorithms using cluster center, especially they can’t satisfy the need of large scale clustering in fast incremental web pages clustering. To solve these issues, this paper proposes a fast incremental clustering method FPC (Fast Page Clustering). In our method, a new approach is given to calculat the similarity between two web pages which is 500 times faster than the Simple Tree Matching algorithm; then a formal representation of web page cluster center is described and a Kmeans-like MKmeans(Merge-Kmeans) clustering algorithm for fast clustering is applied; Moreover, we use local sensitive hashing technique to quickly find the most similar cluster in a large scale cluster set and improve the efficiency in terms of the incremental clustering.

DOM tree layered vectors; web page cluster center; local sensitive hashing; fast incremental clustering

余钧(1988—)，硕士，主要研究领域为网络信息处理。E⁃mail：yu．jun．reach@gmail．com郭岩(1974—)，博士，高级工程师，主要研究领域为网络信息处理。E⁃mail：guoy@ict．ac．cn张凯(1976—)，硕士，助理研究员，主要研究领域为网络数据采集。E⁃mail：zk@ict．ac．cn

1003-0077(2016)02-0182-07

2013-08-25 定稿日期： 2014-06-01

国家973计划(2012CB316303，2013CB329602)；国家863计划(2014AA015204)；国家自然科学基金(61232010，61425016，61572473，61572467)

TP391

A