本站原创为您写算法毕业论文和职称论文提供算法方面有关在职毕业论文范文,与基于结构挖掘的排序算法综述相关论文范文检索,包括关于算法及网络安全及计算机工程方面的论文题目、提纲、开题报告、文献综述、参考文献的大学硕士和本科毕业论文，是免费优秀的算法论文范文。
【 摘 要 】 随着Inter的迅猛发展,Web成为了人们获取信息的重要途径.但是,网页数量的与日剧增,信息量的爆炸式增长,也为人们的信息查询带来了不便.Web数据挖掘技术的引入提高了检索质量,特别是Web结构挖掘在搜索引擎中的应用,很好地帮助用户快速从搜索结果中锁定对自己真正有用的信息.本文对基于结构挖掘的排序算法进行了大量搜集分析,并进行了归纳总结.
【 关 键 词 】 结构挖掘；PageRank；HITS
【 中图分类号 】 TP3 【 文献标识码 】 A
1.引言
随着全球网络的迅猛发展,Web成为了人们获取信息的重要途径.网络上的页面与日俱增,截止2008年,网页数量已超过1万亿.要从如此巨大的网络资源中快速查找到所需的信息是一项具有挑战性的任务,它需要一个强大的搜索引擎.目前,网络上流行的搜索引擎有Google、Yahoo、搜狐、百度等.这些搜索引擎使用起来简单,并且还融入了高级检索、分类查找等功能,方便了用户搜索各种信息.但现有的搜索引擎技术有限,还不能抓取到网络的所有页面,例如,搜索引擎Google能检索到的最大网页数量仅为总网页的29.2%.即使这个范围内,网页的数量也是十分庞大的,用户要从中浏览到自己所需要的页面将花掉大量时间.因此,如何提供一种高效、准确的算法对搜索结果进行排序,使得最可能符合用户需求的页面排在搜索结果的最靠前的位置,是提高搜索引擎能力的重要研究内容,它可让用户更快捷地获取所需的检索信息.
传统的Web搜索引擎排序算法大多都是基于关键字匹配的,关键字出现频率高的页面往往在搜索结果中的排名靠前,这种方法简单、有效.但如果站点有意提高关键字出现的频率,将影响搜索结果的客观性和准确性.因此,如何将查询主题的相关性和搜索页面本身的权威性等重要指标引入Web挖掘及其结果的排序中是研究和改进搜索引擎排序算法的有效途径.
2.研究现状
如何利用Web结构挖掘理论和技术进行Web挖掘受到许多学者和研究机构的重视.近年来,利用超链接挖掘中的链接分析思想为搜索引擎结果进行排序的研究已有不少的算法研究成果,如PageRank, HITS（Hyperlink-Induced Topic Search）, SALSA（Stochastic Approach for Link-Structure Analysis）, PHITS , Bayesian等.利用这些研究成果进行搜索引擎结果排序已经收到很好的效果.其中,对PageRank和HITS的研究最为广泛,如H-PageRank （Hub-PageRank）, dPageRank （Distributed-PageRank）, V-HITS（Vecter Space Model-HITS）算法.事实上,PageRank和HITS及其各种变体算法已被各种搜索引擎系统所吸收（如Google）.
1998年提出的PageRank算法通过页面的入度（入链个数）和出度（出链个数）计算网络中各个页面的权威等级,以此为基础进行搜索结果的排序是一种独立于查询的排序.事实上它是Google的核心技术.1999年Kleinberg提出了HITS算法,算法引入权威度和中心度综合权衡页面的重要性,并用于搜索引擎结果的排序,它本质上是一种依赖于查询的算法.
国内外一些学者和研究机构从主题相似、算法收敛速度、算法运行的有效性和高效性等方面对传统的PageRank进行了各种改进.例如,文献[11]提出了主题敏感的PageRank算法,该算法根据Open Directory建立了16个基本主题向量,离线计算出每个网页对于这些基本主题向量的PageRank值.为了提高PageRank算法中稀疏矩阵的收敛速度,提出了艾特肯外推法和二次外推法、基于I/O的PageRank加速算法、降低冗余迭代次数的PageRank适应性算法.基于P2P网络的分布式PageRank算法,各结点采用异步方式进行通信,很好地解决了链接失效问题并且具有很好的收敛性.考虑到串行计算整个网络的PageRank值时不仅大量消耗系统资源而且很耗时,提出了并行计算PageRank值的算法.通过多台服务器同时运算,算法的收敛速度大大提高.
在对HITS的改进工作中, ARC（Automatic Resource Compilation）算法,它在赋予页面集对应的链接矩阵的初值时结合了锚（Anchor）文本,适应了不同的链接具有不同的权值的情形.Lemple和Moran利用马尔可夫链的概念提出了SALSA（Stochastic Approach for Link-Structure Analysis）算法,该算法弱化了权威页面和中心页面之间的关系.Saeko等提出的空间投影HITS算法,通过对各个社区的考察,进一步保证了结果的合理性.
3.PageRank算法分析
3.1 算法思想
PageRank基于链接分析计算页面的权威度,衡量网页的权威性,实现搜索结果的等级排序.但PageRank算法的有效工作需要两个假设前提,否则,PageRank的等级排序的意义将受到极大的约束.
3.2 算法的缺点
3.2.1 PageRank值计算的滞后特性
3.2.2基于PageRank值排序的主题漂移性
由于传统的PageRank算法在计算PageRank值时并不考虑页面的内容对权威度的影响,即它是脱离页面内容或独立于查询内容的,PageRank值的计算建立在链接结构上,它无法区分网页中的超链接是否和主题相关,也无法判断网页内容与查询主题的相似性,且网页对所引用页面的PageRank值的贡献均等,容易导致大量排在搜索结果前面的所谓“权威网页”与查询目标毫无关联或者关联度很小,形成主题漂移现象,影响搜索结果排序的客观性和准确性,给用户查询带来不便. 4 HITS算法分析
4.1 HITS算法的基本思想
4.2 HITS算法存在的主要问题
（1） 在实际应用中,由于根集S生成基集T的时间开销太大,需要下载和分析S中每个网页包含的所有链接.一般T比S要大得多,而由T生成有向图也很耗时.并且HITS算法需要计算Authority和Hub两个值,计算量也很大.
（2） 网页中一些无关的链接会影响HITS算法的精度,如站内的一些广告链接、导航链接、友情链接等.
（3） 用HITS进行窄主题查询时,可能产生主题泛化问题,即根集扩展成基集时,可能引入与查询主题无关的新主题.
（4） 不能很好地处理主题漂移问题,即所谓的紧密链接现象TKC.由于基集中包含了一些与查询主题无关、但又是紧密链接的网页,HITS算法会认为它们形成的区域更重要,而在结果中返回这些网页,从而偏离了原来的主题.
5.结束语
PageRank和HITS算法都是基于链接结构的,因此不可避免地存在主题漂移现象,虽然已经有不少改进算法的提出,但是由于现有技术的有限,还不能完全杜绝这个问题,因为Web挖掘涉及人工智能、语义学、统计学等多个领域,要把这些领域完美结合起来,还需要一定时间.