论文研究-一种多特征因子融合的PageRank算法研究.pdf

所需积分/C币:10 2019-09-10 09:03:41 657KB .PDF
46
收藏 收藏
举报

摘  要:针对PageRank算法完全依据链接结构排序,未考虑网页内容分析,造成平均分配PR值、主题漂移、偏重旧网页的现象,且已有改进算法存在单一性优化等问题,提出一种多特征因子融合的PageRank算法。该算法为使搜索结果更接近用户查询需求,同时兼顾搜索内容的相关度和查准率,通过添加链入链出权重因子、用户反馈因子、主题相关因子和时间因子,共同改善PageRank算法存在的不足。实验结果表明,所提算法在内容相关性和查准率方面,较其他网页排序算法有明显提高,达到优化PageRank算法的目的。
齐向明,孙文心:一种多特征因子融合的 PageRank算法研究 2017,53(7) 99 EKTR算法的核心思想是:网页链入关系越多,网 COlt2→= 页越重要;网页入链接点击量越多,则该网页越受到用 户关注,PR值越高排序越靠前;引入主题相关因子即式中,v表示从网页v指向网页u的链接点击量,即 关键词比,通过查询词中关键词数H和贞中关键词数V(a→l);TLa)表示与网页v相关的所有链接的点击 目之间的比,衡量搜索结果与询内容之间的相关性,量,即∑V→),Bd是网页v正向链接的网页集 优化主题漂移现象;添加时间因子,提升具有较少链入 合.公式(8)可以变换为如下公式(9): 链接和访问次数的网页排序位置。算法数学公式如下 V(v→l) EKTR(u=(l-d) ∑Vt→h) (V,0.7Wm+0.3 EKTR(u A∈B( 7(7) Vu→u)值越大表示网页v与网页u这两个网页越相 式中,W。和W分别表示链入权重因子、链出权重美,网页应该获得较高PR值。收进算法中加入用户 因子;E 访问网站的入链接点击量,根据用户浏览行为习惯将最 TLu) 表示用户反馈因子,V表示网页v到网页有价值的网页显示在搜索结果列表顶部缩小搜索范 a的链接点击量,TL(v)表示与网页v相关的链接点击围,提高搜索结果的相关性。为了验证用户反馈因子 量总科;表示主题相关因子;表示时间因子。 的作用,以下举例说明:A、B、C表示网络链接结构中 的三个网页,每条链接上对应的是用户对链接点山量 3.1链入链出权重因了 在网络中权威网页应具有较核心排序位置,起关键 引导作用,不仅要求该网页具有较多的入链接,而且出 链接数目也应该多。但是, PageRank算法公式中只依 据閃贞的正向链接数H平均分配页PR值,导致一些 B 垃圾网页分配较多的PR值,搜索结果中出现不相关的 图1含有VOL的Web图 网页,引起主题漂移。因此,在计算网页PR值时根据 网页入链接数目和出链接数目计算网页重要程度,并依 用公式(1) PageRank算法计算网页A、B、C的 PR值计算表达式如下 据重要程度分配PR值,使权威树贞拥有较好的排名 链入权重因子Wa、链出权重因子W计算公式分 PR(A)=1-a)+(PR()×3 別如下: PRB)=(1-+ /PR(A)×1 (以 PR(C)=(1-d)+a(PR(B)×为)+(P(A)×) PR(4)=1.10 (7 PR(B)=0.68 p=Biv PR(C)=121 公式(6)、(7)屮,L、O,分别表示网页u的入度、出度 用公式(5)EKTR算法计算得PR(A)=1.207 、O2分别表示网页v所指向网页的入度、出度,B()PR(B)=0.539,PR(C)=1.45,通过PR值计算结果对比 是网页v反向链接的网页集合 可知EKTR算法从用户度出发,加入用户反馈因子, 32用户反馈因了 提高了网页A和网页C的PR值。网页C包含 大多数网页排序改进算法根据链接结构或网页内A→C、B→C这两个链接且链接点击量较多,PR值 容提升排名很少考虑用户行为。用户反馈是使用者对增大;A包含C→A链接点击量为2,B包含 查询内容作出的一种反应,包括显式反馈和隐式反→B链接点击量为1,说明网页A比网页B重要,所 馈。显式反馈显而易见是用户主动参与,上传岗页以网页A的P值增大,网页B值减小。 URL和相应的关键词表示用户的认可。隐式反馈则与3.3主题相关因子 显式反馈相反,没有用户主动参与,利用用户浏览网页 主题相关因了基于Web内容挖掘,提取网页内容和 留下的痕迹信息得出查询结果的准确率。本文用户反查询词屮的关键词,根据关键词比提高查询內容的相关 馈因子(ωmt,a采用隐式反馈,通过网贝浏览者对链度,优化主题漂移。为了统计关键词数H,首先进行关 接的访问次数即点击量表示。用户反馈因子计算公式键词提取吗:采用TFDF统计方法,设N表示给定文档 如下: 集合D包含的全部文档数目.n表示文档集合中含有 1002017,53(7) Computer Engineering and4 pplications计算机工程与应用 词亲l的文档数目。对于给定文档,词条在该文档子d的影响,和搜索引擎的搜索周期相关。通过文献 中的权重1计算公式如下所示: [S]中实验证明,在算法中分别取e 0.015 n为网页总 ZE!= TFXIDF DF=lo (10)数)、e=915,e=0.015,c=011.c=1得到同一个网 式中,TF代表某个词条:出现在文档d的频率;DF页的PR值几相同,证明e的取值不影响网页最后PR 代表文档d的反转频率。如果某个词条t在给定文档值,但是在选代计算过程中,c的大小影响迭代收敛的 d中现次数多且在其他文档出现次数较少时,表明词速度。当e=1(n为网页总数)时收敛速度较快,排 条!的权重τ较高在文档中具有较高的重要性。根据 序效果达到最好。因此,本文实验中取e (n为 词条的权重值τ;,提取较大的词条为关键词。设查 询条件中关健词集为Q=<A,…kn>,网页中关键词网页总数)。T为个网页被搜索引擎访问的周期次 集为K=<K,K2…K>,则统计出查淘词中关键词数数,利用搜索引擎搜索周期来表示网页存在时间,如果 目n和网页中关链词总数N 某网页存在时间长在同一个周期内被频繁搜索到,都记 关键词比( KeyRatio)即杳询词所含关键词个数为一次来计算处理,这样页面存在时间与被搜索次数成 和网页屮关键词总数N之间的比。计算公式如下: 正比。 3.5算法合理性 KeyRato ne EKTR算法的合理性:改进算法弥补了 PageRank算 关健词比计算过程伪代码如下: 法中存在的主题漂移、偏重旧网页、平均分配网页PR值 Preprocess( Weh Graph G, Query Q 等不足,利用开源的搜索引擎utch比较公平的呈现出 IString WebPageContent-=null 网页应该其有的排名,提高搜索结果的相关性和查准 2. For each WebPage p inG dot 率。改进算法虽然运用了乘除计算,计算复杂度高,但 3.移除指向自身的链接; 由于离线计算PR值,不需要占用用户的杏询时间,因 4 WebPage Content-从网页p中提取文本内 此能够即时响应用户查询需求。 5移除 WebPageContent和查询词Q屮的停用词; 6对文本内容采用IK技术中文分词; 4实验仿真 7.利用 TF-IDF统计方法提取 WebPagecontent和查询诃 41实验条件 中的关键词 8.nk=查询词所含关键词个数; 为验证改进算法的正确性和合理性,对EKTR算法 9.Nk=网页中关键词总数 进行实验仿真。实验工具为win7系统, Cygwin软件, 10.} Tomcat服务器,开源搜索引擎 Nutch。 Nutch提供运行 由于 PageRank算法与ER算法这两种算法都是仅搜索引擎所需的全部工具,包括爬虫和查询。爬虫主要 依据链接结构排序,不能够准确判断网页内容相关性,负责从上爬取树页并建立索引。查询主要根据用户查 使得主题不相关树页与相关树贞获得同等的重要性,出询条件,利用索引技术检索已爬取的网页。实验数据来 现主题漂移。上KTR算法中加入主题相关因子即关键源于辽宁工程技术大学官网(mtp:www.intu.edu.cn) 词比,通过结合基于Web内容挖掘和基于b结构挖掘本文分别在7月2号和9月2号对该刚站进行爬取,并统 的方法,计算查询内容与网页主题之间的相关性,优化计从7月2号开始爬取到第二次爬取结束时的点击量 PageRank算法存在的主题漂移。 情况 34时间因子 42实验过程 贞 PageRank值大小主要由树贞链接数H决定, (1)揩建实验环境。在 Windows系统上利用Cyg 因此网页存在时间越长,被链接的网页越多,网页PR win模拟Unⅸx环境搭建实验平台,通过 Tomcat配置 值越大。但实际上对于新闻类和商务类网页来说,存Nuch运行环境,确保软件正常运行。 在时间长信息不与时俱进,失去其应有的价值,因此 (2)计算链入链出权重。利用 Nutch爬虫以htp: Pagerank算法不能很奷满足用户的实际查询需求。改 ww: hIndu. edu.cn为源地址抓取貞,并保存至本地, 进算法加入时间因子,使旧网页下沉新网页上浮,解决实验共采集约7000个网页。对网页进行预处理,删除 偏向旧网页问题。时间因子(Time)计算公式如下 无关网页,提取网页內容和网页的链入链出URL结构, 根据公式(6)、公式(7)分别计算链入链出权重,存储计 Time= (12 算结果 式中,e是一个实验常数,它的取值受公式(1)中阻尼因 (3)统计链接点击量。在网页v上点击链出网页 齐向明,孙文心:一种多特征因子融合的 PageRank算法研究 2017,53(7)101 a,网页的访问次数加1。现实中可能存在主观作弊 表2各算法对应PR值 提高点击量,策略是删除同一IP每天点击量超过300 ID ER EKTR 査询词为空或空格的网页信息,确保链接点击量真实 123 0.38640.16000.2300 有效。 17270.16380.5283 0.25810.41590.4471 (4)提取网页关键词。具体步骤如下:①对爬虫 03614 6(4532 L经抓取的网页进行颜处理,去除网页文本中存在的 50.36040.17860.4532 HIML格式,且对文本进行中文分词,实验中采用K中 60.36040.17860.4532 文分词技术。②权重计算,根据公式(10)计算文本中 0.36040.17860.4532 80.14290.27860.1135 每个词语的值。③输出结果,根据值大小进行排序,选 90.2535 0.40 择最优的关键词并输出结果。 100.34420.50560.5438 (5)计算爷网页PR值。编码实现PR、ER、EKTR 10.28730.32410.3922 算法,分别替换Nuch中原有网页排序算法,存储运行 120.28730.324 0.3922 13 28730.3241 3922 各算法后计算得到的各网页PR值。 140.14090.29320.3283 43实验结果及分析 0.29620.23850.3485 使用Nutch的爬虫功能,以http://www.intu.edu.cn 0.01720.1457 0.14D0 ().216 1.3269 为源地址根据深度优先策略爬取网页,在 Cygwin中输 180.14000.21160.3269 入命令: bin/nutch readdb crawl/crawldb-topN20,选取 190.14000.21160.3269 URL得分前20的网页并编号,如表1所示。使用PR、 200.14000.2160.3269 ER和EKTR算法分别计算20个页面PR值,计算结果 1EKIR算法与PR算法排序结果比较。表3(a) 如表2所示。 与表3(b)实验数据对比,EKTR算法中加入时间因子 表1各网页编号对应关系表 使旧网页4、5、6、7等下沉,而新网页2、3、9等上浮,优 URT 化了P算法偏重旧网页;加入用户反馈因子,提升编号 1http://localhost/webgraph/index.html 10、14排厅位置;加入锩入链出权重因子,根据链入链出 2http://localhost/webgraph/news.html 比例计算PR值,降低编号1排名,优化了PR算法平均 3http://localhost/webgraph/view.html 4http://localhost/webgraph/service.html 分配PR值;加入主题相关因子,提升编号14、17、20排 5http://localhost/wcbgraph/train.htmi 名,优化了由于包含较多与查询词相关的关键词导致主 6http:/localhost/webgraph/mail.html 题漂移问题 ttp st/webgraph/list.html (2)EKIR算法与ER算法排序结果比较。表3(a) 8http://localhost/webgraph/soft.html 与表3(c)实验数据对比,ER算法中加入链入链出权重 9http://localhost/webgraph/jichu.html 10http://localhost/webgraph/dianzi.html 因子和用户反馈因子,提高了编号11、12等排名,但仍 ttp //loca 存在主题漂移现象。EKTR算法屮加入主题相关因子 12http://localhost/webgraph/dianqi.html 和时间因子,提升了编号4、5、6、7排名,解决ER算法中 3http://localhost/wcbgraph/xrld.html 存在的主题漂移和偏向旧网页问题。 4http://localhost/webgraph/xg.html (3)查准率比较。查准率是根据川户主观判断,确 15http://localhost/webgraph/qy.htmi 16http://localhost/webgraph/ls.htm 定查询结果与用户需求相关度的一个衡量标准。查准 http:/localhost/webgraph/ky.html 率 Precision的计算公式如下 18http://localhost/webgraph/jxzy.html 19http://localhost/webgraph/zwhj.html 20http://localhost/webgraph/xsgl.html Precision= 分别按PR、ER和ER算法所得P值进行降序式中,sm表示查询出来的页面总数,m,表示查询结 排列结果如表3(a)、3(b)、3(c)所示,表中RANK表示果中用户满意的页面总数,n表示用户数。实验中取 网页排名,ID表示网页编号, Count表示用户访问网页=5,表示5名同专业的研究生作为用户体验者。根 点击量,Time表示网页发布日期。链入链出权重因子据不同用户查询类型组织查询关键词,查询类型包括信 和关键词比根据公式计算,不列入表中,但在各算法PR息型、事务型和导航型3种,主要是信息型。为使本文 值比较时也作为参考因素 更具说服力,实验过程由5名测试用户选取不同类型的 1022017,53(7) Computer Engineering and4 pplications计算机工程与应用 表3(a)EKTR算法排序表 表3(b)PR算法排序表 表3(c)ER算法排序表 RANK ID EKTR Time Count RANK ID PR Time RANK ID ER Time Count 100.54382011-05-2940 10.38642011-03-0725 1100.50562011-05-2940 0.52832014-12-2312 40.360420|-03-2433 230.41592014-091624 340.45322011-03-2433 2345 50.36042012-05-1618 3110.32412013-02-0716 5045322012-05-1618 60.36042012-08-155 4120.32412014-082720 560.4532201208-155 70.36042012-09-2614 5130.32412014-04-1817 670.45322012-09-2614 6100.34422011-05-2940 6 90.30172014-03-1814 30.44712014-019-1624 7150.29622013-06-1710 140.29322012-11-2812 890.4079201403-1822 8110.28732013-02-0716 80.27862013-11-113 9110.39222013-02-0716 9120.28732014-0 9150.23852013-06-1710 10120.3922201408-2720 0 30.28732014-04-1817 10170.2l162012-11-28 6 130.39222014-04-1817 30.25812014-09-1624 11180.21162012-11-2811 150.34852013-06-1710 90.25352014-03-1822 12190.21162012-11-2813 13140.32832012-11-2812 13160.22462014-04-164 200.21162012-11-28 170.32692012-11-286 1420.17272014-12-2 14 40.17862011-03-2433 180.32692012-11-2811 80.14292013-1l-113 l550.17862012-05-1618 16190.32692012-11-2813 16140.14092012-11-2812 1660.17862012-08-155 17200.32692012-11-2821 70.14 2012-11-286 1770.17862012-09-2614 0.23 20l-03-0 I8180.142012-11-2811 1820.16382014-12-2312 19160.14572014-04-164 19190.14 2012-11-2813 1910.16 2011-03-07 80.l1352013-11-11 200.14 2012-11-2821 20160.01722014-04-164 30个关键词共进行200次查询,并获取每个查询关键词 的前30条记录,将这些记录合并由测试者阅读网页内 ■PR■ER■EKTR 容,根据用户需求判断网页是否符合查询条件;若有3 人以上同意符合,则认为是相关网页,否则不相关。图2 给出了用户查询200次后,得到搜索结果的查准率。 研究生校园安全教师 查询关键词 图3各算法搜索结果和关性 从图3实验结果得出,通过不同的查询词,EKTR算 法搜索结果中满足用户需求的页面较多,具有较高的相 PR一 ER-EKtR 关性。改进算法考虑网页内容分析,加入主题相关因 20406080100120140160180200 查询次数 子,优化主题漂移,提高了搜索结果的相关性。 图2搜索结果的查准率 根据以上实验仿真结果的奁准率和相关性比较得 从图2实验结果看出,经过200次查询,EKTR算法出:本文提出的改进算法EKTR算法能有效结合网页内 的查准率平均值为53%左右,而ER算法的查准率平均容分析,优化了 PageRank算法屮存在的主题漂移现象 值大约为40%,PR算法的查准率平均值佔计为25%,根据网页间链接结构权重比,合理修正PR值分配;从 FKTR算法搜索结果的查准率明显高于PR和FR算法,用户角度出发,提高了搜索结果的相关性;一定程度上 表明EKTR算法可以更加准确的计算网页权威性,返回解决偏向旧网页问题,弥补了由于新网页时间短链接少 的搜索结果更符合用户搜索目标 的问题,实现了提高搜索引擎检索服务质量的目标 (4)相关性比较:为验证搜索结果的相关性,选取 若干关键词进行查询,在此选取4个关键词:k=“研究5结束语 生”,k2=“校园”,k3=“安全”,k4=“教师”。分別利用 对比分析了PR、ER算法中存在的不足,及已有解 PR、FR、FKTR算法对得判的查询结果进行相关性判决算法的单一性,提出一种有效结合链入链出权重因 断,图3给出不同关键词通过各算法得到搜索结果相子、用户反馈因子、主题相关因子和时间因子的EKTR 关性 算法,达到综合优化 PageRank算法的研究目标。本文 齐向明,孙文心:一种多特征因子融合的 PageRank算法研究 2017,53(7)103 算法通过加入链入链出权重因子,解决平均分配网页 的新方法小计算机研究与发展,2004,41(1):98-103 PR值问题;结合用户反馈因子,使返回结果更符合用户[7]曹珊珊,王冲基于网页链接与用户反馈的 PageRank算法 查询需求添加主题相关因子,提高查询结果的相关性, 改进研究门计算机科学,2014,41(12):179-182 避免主题漂移;引入时间因子,使旧网页下沉,新网页上L8 I Page L, Brin S, Motwani r, et al.The PageRank citation 浮,斛决了偏重旧网贞问题。实验结果表明,FKTR算 ranking: Bringing order to the Web, Tech Rep SIDL-WP 法提高了搜索结果查准率和内容相关性,对 PageRank 1999-0120[R]1998 改进算法中存在的单·性问题有较好改善。如果面对 19 Tyagi N, Sharma S Weighted PageRank algorithm based 互联网TB级海量数据采用串行计算,其复杂度高且效 un number of visits of links of Web page[J]. International Journal of Soft Computing and Engineerig(UISCE) 率低,下一步,计划对EKTR算法利用 SPARK框架技术 2012,2(3):441446 实施并行优化,减少空间复杂度,提高搜索结果的效率。 [10 Singhand R Sharma d K. RatioRank: Enhancing the of inlinks and outlinks[].Adv Compi 参考文献 Conference(IACC),2013,7903(21):794-799 [1 Xing W, Gorbani A Weighted PageRank agorithm[c]r [11 Singhand R, Sharma d K. Enhanced-RatioRank: Enhancing Proceedings of 2nd Annual Conference on Communication impact of inlinks and outlinks[J]. Information Com Networks and Services Research. 2004: 305-314 munication Technologies(ICT), 2013, 7903(21): 287-291 [2 Haveliwala T Hto nsitive PageRank[Cy/PI 土冲,曹珊珊.基于用户反馈与主题关联度的网页排序算 of the 11 th international con ference on world wide 法改进[]计算机应用,2014,34(12):3502-3506 Web. Hawaii USA 200 [13] Kumar G, Duhan N, Sharma A K Page ranking based [3]高琪,张永平超链接导向搜索算法中主题漂移的研究[J on number of visits of Web pages[C]/Proceedings of 计算机应用,2009,29(11):3100-3102 International Conference on Conputer Communica [4]Richardson M, Domingos P. The intelligent surfer: Proba tion Technology(ICCCT), 2011: 11-14 bilistic combination of link and content in formation[J.[14]杨颖,戴彬基于多特征的中文关键词抽取方法[J计算 PageRank Advances in Neural Information Processing 机应用与软件,2014,31(11):109-112 Systems,2002,14:673-680 「151郭庆宝,贾代平融合反馈信息与内容相关度的 PageRank [5]戚华春,黄德才,郑月锋.具有时间反馈的 PageRank改进 改进算法[计算机工程与设计.2011,32(12):4071-4074 算法[浙江工业大学学报,2005,33):272-275 [16]何国斌,赵晶璐.Web页面主题相关性排序算法的研究[J I6]张岭,马范援.加速评估算法:一种提高web结构挖掘质量 计算机工程与应用,2009,45(23):149-151 (上接48页) [12 Pant M, Thangaraj R, Abraham A Particle swarm opti 8 Clerc M, Kennedy J. The particle swar-explosion, sta mization using adaptive mutation[c]pRoceedings of bility, and convergence in a multidimensional complex 1%th International Workshop on Database and expert space[j] IEEE Transactions on Evolutionarycomputation systems Application, 2008: 519-523 2002,6(1):58-73 ]窦仝胜,周春光,马铭.粒子群优化的两种改进策咯[小计 r9]黄宇,刘玉峰,彭志敏,等.基于量子并行粒子群优化算法 算机研究与发展,2015,42(5):897904 的分数阶混沌系统参数估计物理学报,2015,64(3):[14]Iix, Tang k, Omidvar Mn, et albenchmark functions 228-235. for the CEC 2013 special session and competition on [10]胥小波,郑康锋,李丹等.新的混沌粒子群优化算法[J large-scale global optimization[J]. Gene, 2013, 7: 33 通信学报,2012,33(1):2430. [15 Yao X. Liu Y, Lin G Evolutionary progranming made []黄泽霞,俞攸红,黄德才惯性自适应调整的量子粒子群 faster[J].IEEE Transactions on Evolutionary Computa 优化算法[上海交通大学学报,2012,46(2):28-232 tion,I999,3(2):82-102

...展开详情
试读 7P 论文研究-一种多特征因子融合的PageRank算法研究.pdf
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-一种多特征因子融合的PageRank算法研究.pdf 10积分/C币 立即下载
1/7
论文研究-一种多特征因子融合的PageRank算法研究.pdf第1页
论文研究-一种多特征因子融合的PageRank算法研究.pdf第2页

试读结束, 可继续读1页

10积分/C币 立即下载