论文研究-基于网络的空间矢量信息渐进传输的研究.pdf

所需积分/C币:5 2019-09-07 20:41:35 1.34MB .PDF

结合网页链接分析和网页内容相关性分析提出一种改进的PageRank算法EPR(Extended PageRank),从分析网页内容相似性的角度解决相关性需求,从网页链接分析的角度解决权威性需求。算法为扩展PageRank提供了广阔的空间,并且实验证明,通过选择合适的参数EPR算法可以获得优于传统PageRank算法的排序结果。
1622007,43(21 Computer Engineering and Applications计算机工程与应用 获取网页集 数据入库EPR离线计算 链接。 网络蜘蛛模块 网页预处理模块 模块 (2)网页内容分析,构建文档的ⅤSM模型 数据入库 首先对文本进行中文分词并去除停用词汇。统计词语的词 频,并根据词语在HTML标签中的不同位置赋予相应的权重因 索引模块 查询模块 子。实验屮分词部分采用屮科院计算所研制的汉语词法分析系 Lucene 统 ICTCLAS,系统的分词正确率高达97%以上。 显示排序结果 (3)后向链接和反词频统计 图1系统结构图 根据数据库存储的网页前向链接和词频信息进行后向链 等。网页之间相互链接构成本文实验的Wcb图,比如说新闻网接和反词频的统计,反词频即出现某个词语的文档数。使用文 页通常会链接内容相关的以及热点推荐的新闻网页等。本实验 档中词语的词频和反词频以及权重因子信息计算文档VSM模 型向量 的网络蜘蛛系统结构如图2所示 (4)计算网页相似度 获取链接 链接抽取链接过滤 有网页的前向链接和网页文档的ⅤSM模型向量,就可以计 载 特HTP协议模块→网页数据 重复性链接检测 算当前网页和所有前向链接的网页的相似度。对于出度为0的 网页不用计算网页相似度,在实际算法迭代中将进行特殊处理 网页存储入库 链接存储入库 4.3算法的迭代 图2网络蜘蛛系统结构图 釆用迭代方法四进行EPR计算。假设 Source和Dest分别 HTP协议的处理细节,通过它来下载网页,模块的初始URL法如下伪码所述,第j次迭代的结果保存在Sore6 其中HTTP协议模块是整个系统的驱动模块,封装了对表示网页集的EPR向量,向量长度为N即网页数量15396,算 为htpr:/news.163com,以后的网页URL由链接抽取模块解析 Source=1/M 下载的网页得到。链接过滤模块处理从网页中抽取的URL,根 While(residual>t 据本实验要求滤除非htp:/news.163.com站内的链接和非 html网页链接(如图片等非html文档的URL)。重复性链接检 While (not Links eof()) 测模块通过比较入库的已下载URL来避免重复下载。网络蜘 蛛采用广度优先规则爬取,即首先爬取完当前网页的前向链 Links. read (_id, _outdegree, _outlinks, _ similarity 接,即按FIFO的队列来存储链接。实验证明此规则易于获得优 -outdegree-1 质的网页集 Links. read(_outlinks[i], indegree[i], outdegree[i]); 4.2网页数据集的预处理 indegree Sum=sum (indegree) 实验的Web图是由htt:/news.163com一个站点的网页 outdegree Sum=sum(outdegree 构成,因此在进行EPR计算之前首先去除网页中其它站点的 similarity Sum=sum(_similarity); 链接以及广告等噪声信息。本文算法将用到网页链接和网页内 if(_ outdegree=0)∥出度为0,则将权值平均分配到每个网 容两部分信息,因此预处理的第二部分工作就是统计网页的前页上 向和后向链接,以及对网页内容进行抽取、中文分词、建立 for i=0. 1 VSM模型和计算构成链接的两个网页的相似度。此类信息按 Desti+=Source_idN 表1的表结构存储在 MySQL数据库中。 网页预处理步骤: fori=0,1,…, outdegree (1)网页链接和文本内容的抽取 式(3)的迭代算法 通过构建HTML文档解析模块进行,将HTML文档按DOM Destl_outlink:s团引+= Source_id)*(a* Indegree 模型分解为DOM树结构,然后删除DOM树中表示外部链接、 outdegree[i /(indegree Sum*outdegree Sum)+ 广告等链接的节点。然后按需要抽取节点中的文本内容和前向 (1-a)*_similarity[i similarity Sum) 表1网页统计信息表结构 网页标识(id) 每张网页用一个唯一的id标识 01 网页URL(url) 当前网页的在因特网上的URL A,http://news.163.com/focus/index.html 网页路径(path) 当前网页在本地磁盘中的路径 AH. F: news. 163. com\\index. html 人度( indegree) 链接当前网页的网页数量 如,402 出度( outdegree) 当前网页的对外链接数量 如,4 前向链接( out links) 当前网页链出的网页ID 如,1,487,488,998 分词信息(词频,反词频,权重等)当前网页经分词,词频统计后的信息 如,美国,1,613,1.0#大使,1,58,1.0# 0.008532808127447906,0.02043722679022451, 前向链接相似度( similarity) 根据分词信息计算的与链出网页的相似度0.07244786315704187, 0.006370426355507406 PgRa值( pagerank)根据PgeR算法计算的权值001389020593 MyPageRank ffi( mypagerank 根据本文算法计算的权值 0.0041832548405717 钱功伟,倪林, MIAO Yuan,等:基于网页链接和内容分析的改进 Page Rank算法2007,43(21)163 置,从0开始,n;为相关度,分为四个等级,分别为(1)非常相 关,网页正文中含有关于查询非常重要的信息;(2)相关,网页 Dest=c*Dest+(1-c)/N;∥应用衰减因子 正文中含有查询的信息;(3)稍微相关,网页正文中仅仅含有很 Residual=ll source-Destll 少查询信息;(4)不相关,仅仅在网页不重要的地方含有查询关 Sourece=Dest 键宇。实验中四个等级对应的r值分别为1.0、0.5、0.1和0.0 其中c为衰减因子,取c=0.15,a为调整权威性和相关性比例 本实验由5名不同专业背景的测试人员进行网页相关性的评 估,然后按照少数服从多数的原则最终确定网页与查询的相关 的比重因子。 Links相当于数据库中的记录集( Resultset或 Recordset),通过遍历数据库的所有记录进行迭代,上述迭代算 等级,最后对不同的排序结果计算得分值。表2结果是式(6)中 比重因子取0.5时的排序结果得分比较。 法的终止条件是残差小于某个设定的阈值,实际实现中可以通 过设置迭代次数来终止算法。本文算法采用的依然是平均分布 因 Pagerank 的跳转概率分布函数。 mW Page Rank ITCPageran 4.4索引查询模块 EPR(a=0.5) 大规模文档的査询需要对文档进行索引,如简单的基于关 键词的倒排索引等。通过索引将大大提高査询的效率 中美关系 旅游 试 非典 是一款优秀的开源全文搜索引擎框架,提供了完整的查询和索 图4各种排序结果得分的直方图比较 引引擎。因此利用 Lucene框架,按照它提供的接∏构造网页文 从表2和图4的实验结果中可以看出,EPR算法在α=0.5 档的处理模块就可实现完整的索引和查询模块。 Lucene的模块时,均能获得高于传统 PageRank算法的排序结果,四个关键词 结构如下: 用户满意度分别提高14.5%、52.7%、15.5%和17.7%,平均提高 被索引文件 25.1%。 PAgerAnk由于存在比较严重的主题漂移往往会将高 询语命 g. apache lucene query Parser 对了权值的弱相关排在靠前的位置,排序结果有时会比 Pagerank 外 差。 TCPagerank算法的性能仅次于本文的算法,因为在小网页 查询结果 apachelucene searc org.apachelucene.analysIs 集中对相关性的需求要大于权威性需求。在实验中α越大(接 L org. apache luceneindex」索 brg apache lucene. documen 近1)实验结果越接近 PAgerAnk,α越小(接近0)结果越接近 org. apache lucene util TCPageRank。对于小的网页数据集,往往对相关性的需求较 索引文件 org.apache lucene.sore」心 基础结构,≌.-……一 大,取较小的α可以获得较好的结果,对于大的网页数据集,对 图3 Lucene索引查询引擎的模块结构 权威性的需求较大,取较大的α可以获得较好的结果。 实验中发现 TCPageran同样也存在一类主题漂移现象, 实验中的网页文档处理模块就是从上图中的 org. apache.假设某类相关的网页相互链接,由于网页内容的相似性,这些 lucene. analysis接口派生。基于 Lucene的索引查询模块同样采 网页获得较高的权值,查询某个关键词时,即使这些网页与查 用ⅤSM模型,即用向量空间来表示查询和文档,根据查询和文询微弱相关,它们也会放到结果集中参与排序,由于它们的权 档的向量空间相似性进行排序。为使用 Pagerank算法和本文的 值较高,往往排在靠前的位置。可以从两个方面削弱主题漂移 算法进行排序,在做索引过程中会将离线计算好的 Pagerank值现象,第一个是在建立网页文档的ⅤSM向量时设定阈值,去除 和本文算法计算的网页权值,作为一部分信息写进索引,然后对 权值低于阈值的词语。第二个是查询时设定阈值,将结果集中 查询结果按这两个值分别排序,并进行排序结果评估 与查询相似度低于阈值的文档去除,然后进行排序。实际的实 4.5实验结果分析 验中还依赖于网页噪声信息的进一步过滤。实验采用第二种方 通过查询若干个关键词如“中美关系”、考试”、“非典”和法,具体是将查询结果集中相关度较低的20%网页去除后进行 旅游”,根据相关性和权威性对不同的排序结果进行比较。其排序。由于“考试”和“中美关系”查询的相关网页不足50,因此 中相关性由测试人员阅读网页内容主观判断,权威性由网页在这里仅采用“旅游”和“非典”两个关键词为例。结果如表3和图 排序结果中的位置决定。假设用 Score表示排序结果的得分 5所示,各种排序算法的得分都有提高,其中 TCPagerank和 它是所有结果网页得分的总和,网页的得分受相关性和权威性EPR提高尤为明显。 两个因素的影响,网页内容越相关、排序位置越靠前得分越高 反之网页越不相关、排序位置越靠后得分越低。同样大小的结 果集中 Score越高说眀排序结果整体性能越好。偎设单个网页 mWPage Rank 因 TCPageRankl 的得分是 Score,则定义 曰EPR(a=0.5) (n-L Score=ri , Score=∑S (9) 旅游 非典 其中n为结果网页的总数,如果m>50则取n=50,为排序的位 15裁减20%低相关度的网页之后结果集得分比较 表2不同算法的排序结果得分比较 查询关键词结果网页数量 Pagerank排序的得分 PAgerank排序的得分 TCPagerank排序的得分EPR(a=0.5)排序的得分 中美关系 7.8105263157894748.1684210526315879631578947368418.942105263157895 旅游 5.2020000000000014.808 8.1680000000000017930000000000001 考试 296.3689655172413795.8206896551724136.031034482758627.355172413793103 非典 115 16.672 17.114 18.77200000000000219626 1642007,43(21 Computer Engineering and Applications计算机工程与应用 表3裁减20%低相关度的网页之后结果集得分表 查询关键词结果网页数量 Pagerank排序的得分 PAgerank排序的得分 PAGerank排序的得分EPR(a=0.5)排序的得分 旅游 110 6.022 5.762 11.15599999999999810.984000000000001 非典 92 23.52800000000000223.26 24.92 25.222 i÷,罪 HI.t:h」 已上二 L,:-: ”手1 二:卜平淫壮屮卞 二}:「"P:LEk「TF二L:1k:EPE 图6本文实验系统用户界面 图7 PageRank和EPR(α=0.5)排序算法关于“非典”的结果集 --- ,种,把,贴,理 aMIP 如出”!,L a 二 “" !D是M 甲L ,:,L… 主, 品,二 国,4一■ E:5 )翻 图8 PAgerank和 TCPagerank关手 图9 Pagerank和EPR(α=0.5)排序算 图10 PAgerank和 TCPage rank “非典”结果集 法关于“旅游”的结果集 关于“旅游”的结果集 本实验在CPUP41.6G,内存128M的机器上进行,使用 Bringing order to the web[R].Stanford Digital Libraries SIDL-WP Java语言在 Windows XP Professional+J Creato2.5平台上开发 1999-0120.1999 用到JDK1.5、 Lucene l.9、 Httpclient3.09和 iDyll等库。系统界21 Kleinberg J Authoritative sources in a hyperlinked environment[Cpr 面和部分实验结果见图6-图10。 Proceedings of the Ninth Annual ACMSIAM Sy ymposium on Di crete Algorithms. San Francisco. California. 1998. 668-677 3 Xing Wenpu, Ghorbani A Weighted Page Rank Algorithm[C)/Com- 5总结和展望 munication Networks and Services Research, Proceedings of Second 本文结合网页链接分析和网页内容相关性分析两个方面 Annual Conference on 19-21 May 2004: 305-314 提出一种改进 Pagerank的EPR算法,从挖掘网页内容的角度4 Havelieala t htopic- -sensitive PageRank [Cy/Proceedings of the 解决排序中的相关性需求,从网页链接分析的角度解决排序中 1 1th International World Wide Web Conference. Hawaii. 2002 的权威性效果。实验证明,通过合适的调整两者比重,可以获得 517-526. 优于传统算法的排序结果。在此算法框架下各种链接分析算法5 I Heydon A, Najork M. Mercator- a scalable, extensible web crawler[ 和文档和相关度计算模型都可以进行应用,为扩展 Pagerank World Wide Web Journal, 1999: 219-229 算法提供了广阔的空间。本文仅仅使用了Web链接和内容信6计算所汉语词法分析系统 ICTCLASJEB/OLht:/wtcn 息,进一步应用用户的使用信息,将有助于提供个性化的排序 freeware/003_ictclas. asp 结果,这也将是作者进一步研究的方向。 [7] Haveliwala T Efficient computation of pagerank[R]. Stanford Univer- sity, Stanford, CA, 1999 收稿日期:2007年2月) [8] Gospodnetic O, Hatcher E Lucene in action[M]. Greenwich: Mannin Publications. 2005 参考文献: 19HttpclientEb/ol].http:jakartaapacheorg/commons/httpclient/ [1] Page L, Brin S, Motwani R, et al.the pagerank citation ranking [10] JtiDy[eb/ol].htTp:/jtidy.sourceforge.net/

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐