基于潜在语义索引的超链接分析模型

《基于潜在语义索引的超链接分析模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cn基于潜在语义索引的超链接分析模型刘华生，刘刚，吕玉琴北京邮电大学电子工程学院，北京(100876)E-mail：liuhuasheng@sohu.com摘要：为了更合理的排名Web文档本文提出了一个新的链接分析模型。该模型结合了基[1,2]于马尔科夫链的链接分析技术和基于潜在语义索引以及文档聚类分析的内容分析技术，能很好的适应新增Web页面，并且能用来解决基于链接和基于内容的搜索引擎作弊以及上下文搜索和主题相关搜索问题。关键词：链接分析模型；潜在语义索引；搜索

2、引擎中图分类号：TP1．引言信息检索理论在搜索引擎中的应用并没有达到预期的效果，主要是因为以下原因：（1）Web文档量非常大而用户输入的查询通常是很短的几个关键词，因此检索到的文档太多以至于很难满足用户的需求；（2）Web文档的质量参差不齐并且变化频繁，有的Web文档作者为了提升自己网页在检索结果中的位置故意重复与文档内容无关但是用户普遍查询的关键字，这也就是搜索引擎作弊（spamming）的一个方面。因此仅仅基于关键字的文本检索技术不能很好的应用于Web搜索。随着Web链接分析技术的出现情况有所改观，尤

3、其是PageRank算法给商业搜索引擎Google带来巨大的成功更直接说明超链接分析技术能有效地给Web页面带来权威的评价以满足用户的信息需求。[3,4]比较成功的链接分析算法主要是PageRank和HITS，他们的基本思想都是如果一个页面被引用的越多说明其价值越高，因此被检索到的时候应该排在前面。自从PageRank算法被提出之后，有很多文章提出了不少的改进方法，而且实验也表明这些改进算法较之PageRank算法非常有效。尤其是内容分析与链接分析的结合，机器学习算法在链接分析中的应用，主题相关的动态权重

4、计算方法等更为有效的改善页面权重的准确度和可靠度。本文主要从这些方面出发提出一种新的页面质量评测模型——基于潜在语义索引的链接分析模型。2．PageRank算法和存在的问题[3,4]PageRank链接分析算法基于以下事实：（1）链接意味着文档的权值从源页面转移到目的页面，因此如果一个页面被很多页面链接则其权重就很高；（2）如果一个页面有很高的权重，则被它链接的页面相应的权重也应该很高；（3）一个页面有很多指向其它页面的链接，该页面的权重应该被这些北至想的页面所共享。如果O表示指向页面i的链接数，(i,)

5、jEÎ表示页面j有指向页面i的链接，pi()表j示页面i的PageRank权值，则可表示为：pj()pi()=å（1）(i,)jEÎOj可以用矩阵形式来表示所有页面的权值，假设共有n个页面，n维列向量P表示所有页T面的权值，即P=(p(1),p(2),...,pn())，-1-http://www.paper.edu.cn矩阵A表示页面间归一化的邻接矩阵：ì1ï,ifi(,)jEÎAij=íOi（2）ïî0,if(i,)jEÏT则整个系统可表示为：P=AP。该公式是循环定义的，因此可以用迭代的办法求解。但

6、这里有几个问题，首先Web的有向图表示并不一定是连同的，其次有很多的页面没有向外的链接，因此矩阵A中有很多行值是全零。为了使其适应Web随机冲浪模型，做出了如下的修改：ETP=((1-+d))dAP（3）n1其中，E为全1的n维方阵，表示页面间随机跳转的概率，d为衰减因子取值在0和1之n间，即dÎ[0,1]，经验值为d=0.85。矩阵的求解可以用迭代的方式求解：PageRank-Iterate(G)P¬en/0k¬1RepeatTP¬(1)-+dedAPk1k-kk¬+1Until

7、

8、PP-<

9、

10、ekk-

11、1ReturnPk从增强的PageRank计算公式可以看出，方阵E为全1矩阵，意味着所有页面之间的跳转是完全随机的，这与事实不符，实际上网上冲浪者在获取信息时更关注内容相关的页面，因此等概率模型不准确。另外，矩阵A中每一行表示所有被链接的页面共享原页面的所有权重分值，并且也是均分，这也是不合理的。本文主要从这两方面改进PageRank算法，提出基于内容的潜在语义索引的链接分析模型，该模型的主要思想仍然是社会网络分析的应用。3．基于内容的链接分析模型T根据马尔科夫链模型P=AP，A表示从状态i跳转到状态j的

12、概率，可以得到描kk-1ij述页面之间链接关系的模型：TP=((1-+d))EdAP（4）kk-1TP=(p,pp,...,)表示在状态k时所有页面的权重，n表示页面集合的大小，矩阵A中kk12kkn的元素A表示页面i和页面j间的链接关系。避免没有向外的链接的页面影响随机矩阵A，ij1对A进行特殊处理，如果页面i没有向外的链接，则有A=。为了使P能收敛，结合ijijkn-2-http://www.paper.edu.cnWeb