《基于改进的PageRank算法的网页主题相关度分析研究》由会员分享,可在线阅读,更多相关《基于改进的PageRank算法的网页主题相关度分析研究(7页珍藏版)》请在金锄头文库上搜索。
1、 基于改进的PageRank算法的网页主题相关度分析研究 普措才仁 齐爱琴摘要 基于链接分析的经典算法Page Rank,其页面转移概率被平均分配到链出页面,新页面链接较少,所以PR值较低,出现在最后反馈结果中的排序靠后,影响用户信息获取效率和准确度,而冗余信息对用户的干扰使用是信息检索领域探究的焦点。文章分析经典算法Page Rank的优缺点,并提出基于主题相关性的PageRank算法改进策略,实施重新排序,结果证明改进后的算法提高查询效率和质量,具有良好的稳定性,具备可拓展性。【关键词】改进PageRank 算法 网页主题相关度 主题漂移信息技术的发展使网络搜索引擎呈几何式增长,而人们的搜
2、索习惯还是喜欢依靠排名筛选有用的信息。利用超链接结构对网页进行分析提出的Page Rank算法,是目前最权威的网页排序算法,发展也最成熟,但应用缺陷也十分明显,主要存在链出权重平均,没有将链接的重要性考虑在内。忽略检索词和网页主题的相关性,导致主体漂移。不能根据网络动态及时更新,面对网络提供的丰富资源,高质量的服务能提高用户满意度。在此基礎上进行改进,帮助用户提高获取信息的准确率成为搜索引擎的重要工作。1 基于传统Page Rank算法的改进由于人们总是检索新页面而传统计算算法提供的反馈结果不能满足用户需求,因此,浙江大学的黄教授提出基于时间反馈的PageRank改进算法。用户对某类网页进行检
3、索,如文献检索,由于互联网上存在的时间越久,重要性信息的在结果中的排序也会不断下降,在基础网页排序算法中考虑时间影响因素,最终反馈网页的PR值也会结合信息发布时间长短动态浮动。但改进后的算法缺乏对网页权威性的考虑,导致PR值分配不合理。反馈结果中链接的质量也是影响网页排名和使用满意度的重要因素,实时上链入或链出界面中链接的网页越多越能吸引访问者点击页面,因此,有学者基于网页的结构提出网页权重排序算法(WPR),分析网页的重要性,然后给予不同权重,最终反馈的结果就会使重要性更高的网页获得较高的排序,但该算法没有考虑信息更新的时间和网页排名,因此,反馈结果多存在旧网页,网页时效性不高。学者黄德才提
4、出基于主题相似度模型和虚拟文档的主题相似度模拟的算法,极大的提高主题拟合度,确保用户使用结果效率提高,减少主题漂移现象,且该算法不需要添加额外的文信息,基于时间复杂度的运算也不须考虑,就能提高服务质量和效率。2 改进的网页主题相关度算法网页排序算法的指导思想是,当用户随机检索的网页T中存在链出链接指向网页A,将页面T的重要性赋予网页A。该算法将定向连接的网络定义为设有向图G=(1)式中d为衰减系数,取值为O,1,一般衰减系数设定为0.85。基于用户随机冲浪模型分析,假设用户的网页浏览行为随机,则不断随机点击某链接的概率为d,由于链出网页的概率相同,所以该模式下用户随机冲浪至另一页面的概率为l-
5、d,概率也相同。页面i指向的其它页面用Fi表示,网页Fi链出的数目用C(Fi)表示。2.1 改进主题权重PageRank算法在经典网页排序算法的基础上提两点改进,同时引入主题相关度和权重影响因子提高网页排序质量,改进后依据主题相关度和链接权重的算法( Topic WeightedPagerRank,TEPR),描述如下。网页超链接用Link(i,j)描述,表示网页i与网页j的超链接关系。链出度用Out(i)描述,指页面i指向的超链接总数,链入度In(i)描述,表示其他页面指向网页节点i的超链接总数。其中页面i指向所有页面的集合为Fi,Fi=pl,p2.,pn),n=Out (i);集合Bi表示
6、所有页面指向页面i,Bi=pl,p2.,pmm=ln (i)。可以假设某个用户不关心页面内容,在某一时刻h,随机访问某页面i,则停止浏览该页面并通过页面i链接至页面j的概率为2.2 基于网页主题相关度和权重的算法步骤算法计算步骤简述如下:首先,借用网络蜘蛛获取测试页面的信息;其次,对干扰链接进行过滤,排除干扰,对不参与计算的页面进行预处理;然后,在概率e情况下,计算任一页面的链入和链出数量,获取页面的修改时间;接着,在计算基于主题相关度因素的概率转移矩阵,运用公式(3)进行主题相关性评价。与主题相关度较小或者无关的网页获得的PR值较小,因此在反馈结果中的排序靠后;最后,计算改进后的PR值,根据
7、PR值对结果进行重新排序,获得最终PR值,并将最终搜索结果反馈给客户。3 实验测试与结果分析为了验证主题相关度和权重因素对改进后算法服务质量的影响,进行了实验测试,以新闻中心,腾讯网的网站进行测试,测试中采用爬虫采集软件进行爬行,一共获得13296张有效的新闻图片,并根据网站主页的分类包括国内外新闻、社会、军事、历史、文化、旅游、公益等键入关键词:微博、财经、考研、十九大、天坛、大学生、论语、孟子、姚明、体育。将经典网页排序算法与改进后的主题权重网页排序算法分别对上述10个主题进行检索,并将最终检索结果的前100项作为测试样本。测试结果显示,在网页数量不断增加时,改进后的主题权重算法耗时不断减
8、少,而反馈结果的准确率逐渐提高,并且基于网页主题权重的排序算法具有较好的稳定性,具有拓展空间。传统的PageRank算法主要存在主题漂移、网页权值平均以及新网页更新较少的问题,改进后的算法加入主题相关限度因子和重要性权重,提出一种基于主题相关性权重的改进算法,并将其应用在新闻用户主题词搜索的排序中,文章根据主题爬虫采集软件进行测试,并对结果进行分析。测验结果表明改进后的算法具有较好的排序效果,并可以应用在跟大规模的数据集上。4 结束语本文主要在传统超链接网页排序算法的基础上既考虑关键词和网页的主题相关度也考虑网页链接重要性,从网页链接权重和主题相关度提出改进的排序算法,测试结果表明,质量较高网
9、页排序提前,改进后算法在应用中缩短搜索时间,提高搜索准确率。实际网页排名的影响因素很多,今后将会对其他影响因素进行改进,为用户提供更高质的搜索服务。参考文献1周秋丽,基于改进PageRank算法的网页排序问题研究D.哈尔滨理工大学,2016.2杨格兰,涂立.基于主题相关性和链接权重的PageRank算法J.华中科技大学学报(自然科学版),2012,40 (Sl): 300-303.3王旭阳,任国盛,基于用户行为与页面分析的改进PageRank算法J,计算机工程,2016 (02):164-168.4朱颢东,丁温雪,杨立志等,微博环境下基于用户行为与主题相似度的改进PageRank算法J.计算机工程,2017 (05):179-184. -全文完-