基于页面相似度的链接分析算法研究

论文摘要

Web为人们提供了丰富的信息资源的同时,它所具有的海量数据、复杂性、极强的动态性和用户的多态性等特点也给Web资源的挖掘造成了相当的难度。由于Web信息是自组织和半结构化的,经典的信息检索和数据库技术很难得到有效的应用。超链接是Web特有的组成部分,是联系Web上数据资源的纽带。链接分析是提高Web资源挖掘质量的重要途径。本文详细分析了Web数据挖掘方法及Web搜索引擎的结构,分析了Web链接结构的特征及主流的链接分析算法的特点及存在的问题。Pagerank算法和HITS算法是两种典型的基于链接分析的页面排序算法。但是PageRank算法同等对待网页间的链接,没有考虑网页更新时间的重要性、导航网页的影响等;HITS算法忽略了主机之间的多重加强关系,容易发生主题偏移产生不合理结果以及不能满足用户站点粒度的信息需求等。根据Web链接特征以及网络冲浪者的浏览过程,可以发现网络冲浪者的随机游走过程受当前页面内容的影响,通常会跳转到与当前页面内容相关性很大页面,而不是等概率地沿着出链跳转。在此基础上,本文引入了SimRank算法来定义网页之间的相似性,从而给出了一种基于网页间相似度权值分配模式,对相关性大的页面间的链接赋予较大的跳转概率。利用此分配模式我们提出了一种基于分配因子排序算法RAD(Ranking Algorithm Basedon Distributed Factor)。本文阐述了PAD算法平台设计,包括实验数据集的获取、数据库设计、剪枝处理、SimRank算法实现及RAD算法实现。实验结果表明,该算法在获得相关性网页以及宏平均准确率方面比标准的PageRank算法更加有效。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 论文研究背景
• 1.2 论文研究内容以及组织结构
• 2 Web数据挖掘及其链接分析研究
• 2.1 Web数据挖掘
• 2.1.1 Web数据挖掘概述
• 2.1.2 Web数据挖掘分类
• 2.2 Web搜索引擎
• 2.2.1 搜索引擎介绍
• 2.2.2 搜索引擎中的相关度排序
• 2.2.3 数据挖掘在搜索引擎中的应用
• 2.3 超链接的结构特征
• 2.3.1 链接的URL属性
• 2.3.2 网页的链入链出分布
• 2.4 链接分析模型
• 2.5 链接分析算法
• 2.5.1 PageRank算法
• 2.5.2 HITS算法
• 2.5.3 SALSA算法
• 2.5.4 HITS、PageRank和SALSA算法存在的问题以及比较
• 3 RAD:基于分布因子的链接分析算法
• 3.1 超链接相似度的计算
• 3.2 Markov随机游走过程
• 3.3 RAD算法描述
• 3.4 矩阵处理以及算法框架
• 4 RAD算法平台设计与实验分析评价
• 4.1 RAD算法平台设计
• 4.1.1 实验数据集概述
• 4.1.2 数据库设计
• 4.2 RAD算法平台核心模块介绍与实现
• 4.2.1 剪枝处理
• 4.2.2 SimRank算法的实现
• 4.2.3 RAD算法实现
• 4.3 实验评价以及数据分析
• 4.3.1 实验数据集
• 4.3.2 查询结果的权威性评价
• 4.3.3 RAD算法优越性分析
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢