论文部分内容阅读
Web的永久保存具有重要意义，国际范围内许多组织和政府机构相继建立了大型的历史网页存档系统来永久保存网页，如Internet Archive和Web InfoMal。而如何对蕴含在海量网页存档系统中的信息进行有效的挖掘和利用是一个尚待解决的问题。对网页按照其主题进行聚类是解决此问题的一项基础性工作，对于主题的自动发现机制、信息提取、主题检索及建模等具有重要意义；同时主题发现与追踪(TDT)也是较长时间以来的研究热点之一。大规模网页的主题聚类在效率和精度等方面面临诸多挑战。本文在此问题上贡献如下：
1.参与设计和实现了一种基于文档最长公共子序列(LCS)的大规模相似文档检测算法(LCS算法)。该算法用于在主题聚类之前对网页进行消重，并在构建文章链接图(本文主题聚类算法赖以实施的基础)的过程中起关键的作用。算法利用文档间的LCS作为文档相似性的衡量标准，以提高检测精度和召回率；利用分治策略设计算法框架以解决LCS用于相似文档检测的效率问题。在本文的对比实验中，LCS算法在精度和召回率上优于Simhash算法和cosine算法：LCS算法的全局精度是0.95，Simhash和cosine分别是0.71和0.82；同时，LCS算法的召回率是Simhash的1.86倍，是Cosine的1.56倍。
2.设计并实现了一种大规模网页主题聚类算法(LCA算法)。通过分治策略提供了一种对大规模网页聚类效率瓶颈的解决方案，并利用主题相关性的局部性来进一步提高效率；通过链接分析和内容分析两阶段的处理充分挖掘网页间的主题相关性来保证算法精度。在链接分析阶段利用时间距离、链接强度和出链数量挖掘主题关联性，在内容分析阶段利用基于topics向量空间的Cosin距离挖掘主题关联性。在本文的对比实验中，LCA算法在精度和召回率上优于层次聚类算法和K-Means算法：LCA算法在F-值为0.94时精度和相对召回率分别是0.92和1；层次聚类算法的最优F-值为0.86，精度和相对召回率分别是0.87和0.91；K-Means算法的最优F值为0.71，精度和相对召回率分别是0.83和0.77；在效率方面，LCA算法对从Web InfoMall中提取的5500万文章的主题聚类可在439小时内完成，而另两种算法通常需要数年完成此过程。
3.基于上述的LCA算法开发了主题聚类系统。在Web InfoMall的数据集合上部署该系统，将其中的4.3亿主题型网页进行消重得到约5500万文章，然后将这些文章进行主题聚类获得约46万个主题，覆盖中的约3300万文章。作为对主题聚类结果的应用示例，在历史网页搜索引擎Histrace的基础上开发了针对主题的检索系统，提供对搜索结果的按主题排序和展示。