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

(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抽取是网络数据挖掘中的重要应用。针对海量网页的抽取，可以把结构相似的网页自动聚成一类，对聚类后的网页簇归纳出高效精确的抽取规则，从而提高抽取的准确率。传统的面向结构的网页聚类算法中，通常没有给出网页簇中心的表示方式。……