论文部分内容阅读
面对规模庞大并且每天都在飞速增长的互联网,Web挖掘技术的研究和探索变得越来越重要。Web挖掘一般分为Web内容挖掘、Web结构挖掘和Web使用记录挖掘三个研究方向。在Web结构挖掘领域,Web社区发现技术主要是研究如何从Web数据集中抽取出同主题的页面集合(称为Web社区)。Web社区发现具有非常重要的意义,它可以帮助用户更快更准确地找到最感兴趣的信息;可以帮助Internet/Intranet门户有效地组织目录结构;可以帮助厂商快速准确地定位客户等等。在Web社区发现领域应用较早且较广泛的技术是Kleinberg算法。在该算法基础上衍生了很多Web社区发现技术,比如HITS算法,Clever系统,Companion算法等等。同时不少新的Web社区发现技术不断地被提出来,如拖网算法,基于流的社区发现算法等等。除了计算机科学领域外,社会网络领域也对社区发现做了不少研究,如Girvan和Newman提出的基于边的betweenness值的社区发现算法等等。 本文主要研究如何根据纯链接结构从主题数据集中发现Web社区。主题数据集指的是利用传统搜索引擎返回的某个查询主题下的根页面集通过链接关系扩充得来的基本页面集。 Kleinberg算法利用权威页面与中枢页面的相互加强关系来发现主题数据集中的Web社区。然而Kleinberg算法在面对存在TKC(Tightly Knit Community)的主题数据集时容易发生主题漂移问题,把主题不相关的页面当成社区内的权威页面。不少研究人员提出其他算法试图绕过TKC以避免发生主题漂移,然而效果并不理想。本文对Kleinberg算法进行了深入探讨和理论分析,揭示了其面对存在TKC的数据集发生主题漂移的本质原因,在此基础上提出了一种改进算法EAA,有效地解决了由于TKC带来的主题漂移问题。 在很多情况下主题数据集中不只存在一个Web社区,比如一个有争议的查询主题“abortion”对应的主题数据集中存在至少两个Web社区,一个关于“Pro-Choice”,另一个则关于“Pro-Life”。面对这样的主题数据集,Kleinberg算法及其改进算法、拖网算法、基于流量的算法等都不能有效地进行处理。本文在研究社会网络领域社区发现技术基础上,引入了Girvan和Newman的社区发现算法。同时本文在研究图聚类领域MCL算法的基础上,提出一种基于MCL的Web社区发现算法MWCFA。相比Girvan和Newman的算法,MWCFA算法具有更好的效果。 本文的主要贡献概括如下: ①对Kleinberg算法进行了深入探讨和理论分析,揭示了其面对存在TKC的主题数据集时发生主题漂移的本质原因。 ②在①的基础上对Kleinberg算法进行了改进,提出了平等授权算法EAA,成功地绕过TKC,避免主题漂移现象。 ③为了从主题数据集中发现多个Web社区,在对前人的算法进行了分析总结的基础上,引入了社会网络领域Girvan和Newman提出的社区发现算法。 ④在研究分析图聚类领域提出的MCL算法以及Web独特的超链接关系基础上,提出了一种基于MCL的Web社区发现算法MWCFA,有效地从主题数据集中发现多个Web社区。