以文本方式查看主题 - W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL (http://bbs.xml.org.cn/index.asp) -- 『 Web挖掘技术 』 (http://bbs.xml.org.cn/list.asp?boardid=69) ---- Web结构挖掘算法概述及应用 (http://bbs.xml.org.cn/dispbbs.asp?boardid=69&rootid=&id=48601) |
-- 作者:DMman -- 发布时间:6/16/2007 9:29:00 PM -- Web结构挖掘算法概述及应用 转自 http://blog.csdn.net/zhanghefu/archive/2007/03/25/1540495.aspx [内容提要] Web 结构挖掘是对Web 的链接结构进行分析。本文概述Web结构挖掘技术,列举其常见算法。并对PageRank和HITS这两种最重要的Web结构挖掘算法分析比较。通过对算法规律的研究,指出在网站设计规划时的策略以提高网站的价值。 [关键词]Web结构挖掘 PageRank HITS Summarization and application of Web Structure Mining arithmetic Abstract: This paper introduces the conception of Web structure mining, and analyses the authoritative algorithms based on Web hyperlink structure. At the end, correlative application on increasing the rank of the website by Web structure mining algorithms. Key words: Web Structure Mining ; PageRank;Hyperlink-Induced Topic Search (HITS); 一、 引言 数据挖掘是将人工智能技术和数据库技术紧密结合发展出的一门新的技术,利用计算机从庞大的数据中智能地、自动地抽取有价值的知识模式,以满足人们不同应用的需要。随着互联网的普及和迅猛发展、Web上信息量的爆炸式增长, 网上的资源得到极大丰富, 但也充斥着大量的垃圾信息, 人们迫切需要能从这些纷繁芜杂的信息中找到有用知识的工具。鉴于数据挖掘工具的日益成熟完善, 人们自然而然想到了要把数据挖掘技术应用到Web上来。 Web挖掘指在WWW 上挖掘潜在的、有用的模式及隐藏的信息过程。根据对Web数据的感兴趣程度不同,Web挖掘一般可以分为三类:Web内容挖掘(Web Content mining)、 Web结构挖掘( Web structure mining)、 Web 用法挖掘(Web usage Mining) 其中Web 结构挖掘是对Web 的链接结构进行分析, 以对超链接分析来评估基础Web 资源, 从而发现有用模式, 提高搜索质量。 二、 Web结构挖掘综述 传统的WEB搜索引擎大多数是基于关键字匹配的,返回的结果是包含查询项的文档,也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性,破坏搜索引擎结果的客观性和准确性。另外,有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面,并且目录大多靠人工维护,主观性强,费用高,更新速度慢。 Web结构包括不同网页之间的超链接结构和一个网页内部的可以用HTML,XML表示成的树开结构,以及文档URL中的目录路径结构等。Web页之间的超链接结构中包含了许多有用的信息,当网页A到网页B存在一个超链接时,则说明网页A的作者认为网页B的内容非常重要,且两个网页的内容具有相似的主题。因此,指向一个文档的超链接体现了该文档的被引用情况。如果大量的链接都指向了同一个网页,我们就认为它是一个权威页。这就类似于论文对参考文献的引用,如果某一篇文章经常被引用,就说明它非常重要。这种思想有助于对搜索引擎的返回结果进行相关度排序。从WWW的组织结构和链接关系中推导知识。通过对Web站点的结构进行分析、变形和归纳,将Web页面进行分类,分析一个网页链接和被链接数量以及对象来建立Web自身的链接结构模式,确定不同页面间的相似度和关联度信息。定位相关主题的权威站点,可以极大的提高检索结果的质量。 基于这种超链分析的思想,Sergey Brin和Lawrence Page在1998年提出了PageRank算法,同年J. Kleinberg提出了HITS算法,其它一些学者也相继提出了另外的链接分析算法,如SALSA,PHITS,Bayesian等算法。这些算法有的已经在实际的系统中实现和使用,并且取得了良好的效果。 三、 WEB结构挖掘常见算法 1、 PageRank算法 PageRank算法是Web超链接结构分析中最成功的代表之一。该算法由Stanford大学的Brin和Page提出,是评价网页权威性的一种重要工具。搜索引擎Google、Yahoo、Baidu都是利用该算法和anchor text标记、词频统计等因素相结合的方法对检索出的大量结果进行相关度排序,将最权威的网页尽量排在前面。 1) PageRank基本原理 传统情报检索理论中的引文分析方法是确定学术文献权威性的重要方法之一,即根据引文的数量来确定文献的权威性。PageRank 的发明者对网络超链接结构和文献引文机制的相似性进行了研究,把引文分析思想借鉴到网络文档重要性的计算中来,利用网络自身的超链接结构给所有的网页确定一个重要性的等级数,当从网页A 链接到网页B 时,就认为”网页A 投了网页B 一票”,增加了网页B 的重要性。最后根据网页的得票数评定其重要性,以此来帮助实现排序算法的优化,而这个重要性的量化指标就是PageRank 值。 但是网页和学术上的出版文献的差别是很大的。首先学术论文的出版发表非常的严格,而网页的出版非常自由、成本很低并缺乏控制,用一个简单的程序就可以产生大量的网页和很多链接。另外学术出版物的引文一般和文章的领域有关系,而网页的链接范围领域却很广。可见简单的链接数量计算并不能客观真实地反映网页的重要性,所以PageRank 除了考虑网页得票数(即链接) 的纯数量之外,还要分析为其投票的网页的重要性,重要的网页所投之票有助于增强其他网页的“重要性”。简单地说,PageRank 就是要从链接结构中获取网页的重要性,而网页的重要 2) PageRank的实现 PageRank在具体实现时会忽略掉Web页面上的文本和其它内容,只考虑页面间的超链接,把Web看成是一个巨大的有向图G =(V,E),结点vÎ V代表一个Web页面,有向边(p, q )Î E代表从结点p指向结点q的超链接,结点p的出度是指从页面p出发的超链接(outlink)的总数,而入度是指所有指向结点p的超链接(inlink)的总数。 PageRank的具体定义如下:将Web对应成有向图,设W为该有向图结点的集合,N=|W|, Fi是页面i指向的所有页面的集合,Bi是指向页面i的所有页面的集合。对每个出度为0的结点S,设FS ={有向图中全部N个结点},则所有其他结点的Bi={B È i S},这样可以将结点S所具有的PageRank值均匀地传递给其他所有页面。PageRank的具体迭代公式为 。 其中,参数 d是 取值0到1之间的衰减因子,因为任何一个网页的作者都认为其它的网页不如自己的重要。d通常被置为0.85。 PageRank的实现过程为:将网页的URL对应成唯一的整数,把每一个超链接用其整数ID存放到索引数据库中,经过预处理(如去除数据库中的悬摆指针)之后,设每个网页的初 始PR值为1,通过以上的递归算法计算每一个网页的PageRank值,反复进行迭代,直至结果收敛。 2、 HITS算法 1) HITS基本原理 Hill Top 算法的指导思想和PageRank 是一致的,即都通过反相链接的数量和质量来确定搜索结果的排序权重。但超链接的应用存在着许多的潜在的问题,如大量的链接是为了导航(如“点击此按钮返回主页”)或付费广告而创建的。而出于商业竞争的原因,尽管内容相关,有些网站又不会把超链接指向他们的竞争对手(如:Cisco公司不会将超链接指向Sun公司的主页)。 HITS算法他认为网页的重要性应该依赖于用户提出的查询请求。而且对每一个网页应该将其authority权重(由网页的outlink决定)和hub权重(由网页的inlink决定)分开来考虑,通过分析页面之间的超链接结构,可以发现以下两种类型的页面: 中心网页(hub):一个指向权威页的超链接集合的Web页 权威网页(authority):一个被多个Hub页指向的权威的Web页 中心网页(hub) 权威网页(authority)
参考文献
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
46.875ms |