一种基于分配因子的链接分析算法

《一种基于分配因子的链接分析算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn1一种基于分配因子的链接分析算法范鑫鑫大连理工大学软件学院，大连(116621)E-mail:xinxinfan_1984@163.com摘要：随着整个万维网的迅速发展，很难为用户提供相关而准确的查询信息。Web结构挖掘在数据挖掘领域起着很重要的角色，PageRank和HITS是Web结构挖掘里面两种较为经典的排序算法，这两种算法在分配权值的时候都是平均分配的，没有考虑各链接的重要性。后来有些研究者通过入链、出链以及文本信息等对其进行了改进。本文提出了一种新的通过改变马尔科夫概率分布矩阵(MarkovProbabil

2、ityDistributionMatrix)排序算法，实验结果表明该排序算法比标准的PageRank算法更加有效。关键词：链接分析，Markov模型，分配因子，概率矩阵中图分类号：TP391.引言[1,2]Web是一个由复杂超文本所组成的巨大的信息源，每天以超过700万页面的速度增长,如何从这样一个不断变化的信息源中提取有用的信息是一个难题。由于web信息的自组织和[1]半结构化，现有的搜索引擎技术远不能让客户满意，经典的信息检索和数据库技术很难得[2]到有效的应用。Web中含有丰富的超链接，超链接是联系整个信息源的纽带，因此链接分析便成为提取有用信息的重要手段

3、。[3][4]PageRank和HITS算法是web结构挖掘中两个较为经典的链接分析算法，它们和其它大部分算法一样都是基于Markov模型的随机游动过程(RandomWalk)，即跳向一个新网页或者跟随链接到一个网页。这些算法能够很好的应用到web结构挖掘里面，但是这些算法在分配权值的时候都平均的分配给所指向的网页，忽视了各链接权重不同问题。针对此问题，[5][6]Bharat和Henzinge、Chakrabarti等提出了启发式方法来计算各链接权重值。Rafiei和[7][8]Mendelzon's算法则偏重于那些含有一些特殊词的网页。Haveliwala则

4、采用了包含查询词的网页子集方法。随机游走受当前页面内容的影响，通常会跳转到与当前页面内容相关性很大页面，所以链接权重应该是不一样的，鉴于此，本文提出了一种新的基于网页间相似度权值分配模式，利用此分配模式我们提出了一种新的基于分配因子排序算法RADF(RankingAlgorithmBasedonDistributedFactor)。实验结果表明，该算法在获得相关性网页以及宏平均准确率方面比标准的PageRank算法更加有效。文章结构组织如下：第2部分介绍一下相关的链接分析算法，第3部分详细说明本文提出的基于分配因子的链接分析算法RADF，第4部分通过实验将RAD

5、F算法与标准的PagesRank算法进行比较与分析，第5部分总结全文。2.相关链接分析算法Web的不断增大以及web用户特殊的性质使得整个网络结构更为复杂，检索出相关有用[9]的信息也变得更为困难。很多研究者也提出了不同的链接分析算法，例如：InDegree算法，该算法可以认为是所有基于流行度排序算法的前驱。Brin和Page通过扩展InDegree算法提出1本课题得到国家自然科学基金的资助（项目编号：60503003）。-1-http://www.paper.edu.cn[3][4]了PageRank算法。Kleinberg考虑到两种权值传递模式于1998年提

6、出了HITS算法。PageRank和HITS作为web结构挖掘里面较为经典的两种排序算法，很多研究者也对这两种算[10]法进行了改进。Mendelzon和Rafiei利用随机跳转对HITS进行了改进，与SALSA算法相似。[11][12-15]Tomlin提出了PageRank算法的一般化。文献对PageRank个性化向量处理方面也进行了改进。[16]沿着不同的研究路线，有些研究者利用概率与统计技术来计算权值。Cohn和Chang提出了PHITS算法，该算法假设了一个概率模型，该模型中的链接由潜在的“因素”或“主[17]题”引起，他们利用期望最大值化算法(Expe

7、ctationMaximizationAlgorithm)来计算网页的[18]权威权值。他们的工作是基于Hofmann提出的概率潜在语义分析(ProbabilisticLatentSemanticAnalysis)框架。3.基于分布因子的排序算法(RADF)传统的链接分析算法可能会带来不好的排序结果。首先，有些网页不是自描述性的，链接的存在完全是为了导航目的；其次，排在后面的返回网页是没有价值的，即使是相关的网[19-21]页，因为大部分用户不会浏览第一页以后的返回结果。在分析超链接结构的时候，通常把web用户看做是一个“随机冲浪者(RandomSurfer)”

8、。“冲浪者”会依不同的概