基于Web信息检索的链接分析算法研究

摘要

随着Internet技术的高速发展，Web已经成为人们获取信息的一个重要途径，由于Web上的文本信息日益增长，如何有效地检索用户所需的信息成为一个非常重要的研究课题。 万维网WWW(World Wide Web)是一个巨大的、分布全球的信息服务中心，正在以飞快的速度扩展，这就对传统信息检索技术提出了新的挑战。在传统的信息检索技术没有突破性进展的现状下，从Web数据本身的特点出发，充分挖掘Web上最充分的超链接资源，通过超链接进行搜索，建立有效的Web信息检索模型，从而找到我们需要的信息。因此，链接结构分析在万维网的很多研究领域起着越来越重要的作用，本文将介绍链接结构在Web信息检索中的应用。 近年来，许多研究者发现WWW上超链结构是个非常丰富和重要的资源，如果能够充分利用这些资源，可以极大地提高检索结果的质量。基于这种超链分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法[1]。Google搜索引擎依靠其PageRank机制及收敛算法一直处于该领域的领先地位，而收敛算法的好坏尤其重要，它直接决定了得到最终PageRank向量的时空开销，一个好的收敛算法可以使系统在较小的时空开销下得到最终向量值，从而使整个搜索的效率得到提高。在当前情况下，PageRank要处理的矩阵是巨大的，传统的矩阵理论不能直接应用于PageRank的计算。因此迫切需要利用。PageRank转移矩阵特征值的特殊性，找到一个比较高效的计算方法来提高迭代法的收敛速度，以便提高PageRank的计算效率。 本文首先分析由链接生成的万维网网络结构在Web信息检索中的应用，然后介绍PageRank算法的模型建立与主要性质。随后，在现有PageRank计算方法的研究基础上，作者推导加速PageRank计算的一般性公式，设计产生满足Web链接结构特征的高维随机矩阵的算法。本文提出General Extrapolation和Acceleration Extrapolation两种有效的加速收敛方法。最后，我们分别在高维随机矩阵数据和四个数据集上进行数值实验，实验结果证实加速PageRank计算的理论分析和算法的有效性。从实验结果可以看出，计算速度得到明显加快。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2研究现状和主要内容

1.3本文组织结构

第二章超链分析与Web信息检索

2.1超链分析概述

2.1.1超链接分析的提出

2.1.2常用超链分析方法

2.2 Web信息检索技术

2.2.1 Web信息的特征

2.2.2主要信息检索模型

2.2.3 Google搜索引擎

2.3超链接分析的主要应用领域

2.4超链分析在Web信息检索中的应用

2.5本章小结

第三章PageRank算法基础

3.1 PageRank算法原理

3.2 PageRank算法模型

3.2.1马尔可夫链模型

3.2.2声望模型

3.2.3 PageRank随机冲浪模型

3.3 PageRank算法与HITS算法比较

3.4本章小结

第四章加速PageRank收敛算法

4.1 PageRank向量计算现状

4.1.1幂法

4.1.2 Aitken Extrapolation算法

4.1.3 Quadratic Extrapolation算法

4.2 General Extrapolation法

4.2.1 General Extrapolation公式

4.2.2 General Extrapolation算法

4.2.3生成高维随机矩阵

4.2.4实验结果与分析

4.3 Acceleration Extrapolation算法

4.3.1 Acceleration Extrapolation原理

4.3.2 Acceleration Extrapolation实现

4.3.3实验结果与分析

4.4本章小结

第五章总结与展望

5.1总结

5.2展望

参考文献

致谢

在学期间公开发表论文情况