ISSN 1 009-3044 E~mail:info@cccc.net.CB ComputerKnowledgeAnd Technology电脑知识与技术 http://www.dnzs.net.cn Vo1.4,No.7,December 2008,PP.1619-1620,1629 Tel:+86~55 1—5690963 5690964 基于Web结构挖掘算法的网站构建 叶琳莉 ,林嵩凯 (1.福建农林大学计算与信息学院,福建福州350002;2.福建省邮电学校,福建福州350008) 摘要:Web结构挖掘是对web的链接结构进行分析。该文概述Web结构挖掘技术,列举其常见算法。并对PageRank和HITS这两 种最重要的Web结构挖掘算法分析比较。通过对算法规律的研究,指出在网站设计规划时的策略以提高网站的价值 关键词:Web结构挖掘;PageRank:HITS:算法 中图分类号:TP311 文献标识码:A 文章编号:1009—3044(2oo8)34—1619—02 Building the Web Site Based Web Structure Mining Arithmetic YE Lin—li ,LIN Song—kai (1.Computer and Information CoUege,Fujian Agriculture and Forest University,Fuzhou 350002,China;2.School of Post and Telecom— munications of Fujian Province,Fuzhou 350008,China) Abstract:This paper introduces the conception of web structure mining,and analyses the authoritative algorithms based on Web hyper- link structure.At the end,correlative application on increasing the rank of the website by Web structure mining algorithms. key words:web sturcture mining;pagerank;hyperlink—induced topic search(HITS);agorithm 1引言 数据挖掘是将人工智能技术和数据库技术紧密结合发展出的一门新的技术,利用计算机从庞大的数据中智能地、自动地抽取 有价值的知识模式,以满足人们不同应用的需要。随着互联网的普及和迅猛发展、Web上信息量的爆炸式增长.网上的资源得到极 大丰富,但也充斥着大量的垃圾信息,人们迫切需要能从这些纷繁芜杂的信息中找到有用知识的工具。鉴于数据挖掘工具的日益成 熟完善,人们自然而然想到了要把数据挖掘技术应用到Web上来。 Web挖掘指在www上挖掘潜在的、有用的模式及隐藏的信息过程。根据对Web数据的感兴趣程度不同,Web挖掘一般可以 分为三类:Web内容挖掘(Web Content mining)、Web结构挖掘(Web structure mining)、Web用法挖掘(Web usage Mining) 其中Web结构挖掘是对Web的链接结构进行分析,以对超链接分析来评估基础Web资源,从而发现有用模式,提高搜索质量。 2 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等算法。这些算法有的已经在实际的系统中实现和使 用,并且取得了良好的效果 。 3 WEB结构挖掘常见算法 3.1 PageRank算法 PageRank的具体算法是,将某个页面的PageRank除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页 面的PageRank相加.即得到了被链接的页面的PageRank。 算法基于“从许多优质的网页链接过来的网页,必定还是优质网页”的回归关系,来判定所有网页的重要性。Google认为当某个 网页有链接到另一个网页时,它就对该网“投了一票”。一个网页的得票越多,则认为它的重要性也就越高。进一步说,投票网页的重 要性也决定着票本身的重要程度.Google通过计算网页得票来得到页面重要性。计算PageRank值时每票的重要性都要考虑在内。 简单将PageRank算法描述如下:将网络看作一个有向图:G=(V,E),其中V是节点[网页)集,E是边(当且仅当存在从页面i到 页面i的链接时存在从节点i到节点i的边)集。 收稿日期:2008—09-16 本栏目责任编辑:冯蕾 - 一 网络矗讯及安全・-1619 Compu ̄rKnowledgeAnd Technology电脑知识与技术 2008年第4卷第7期(总第34期) PageRank的基本思想在于一个页面重要或者有链接指向它的页面多,或者有链接指向它的页面重要或者二者兼而有之。其初 始定义如下: PR(q): p磊 ∈占 L( ) 其中:PR(q):页面q的网页级别,PR(p):页面P的网页级别,页面P链向页面q,N(p):页面P链出的链接数量。 PageRank在具体实现时会忽略掉Web页面上的文本和其它内容,只考虑页面间的超链接,将网页的URL对应成唯一的整数, 把每一个超链接用其整数ID存放到索引数据库中,经过预处理(如去除数据库中的悬摆指针)之后,设每个网页的初始PR值为l, 通过以上的递归算法计算每一个网页的PageRank值,反复进行迭代,直至结果收敛。 3.2HITS算法 Hill ToD算法的指导思想和PageRank是一致的,即都通过反相链接的数量和质量来确定搜索结果的排序权重。但超链接的应 用存在着许多的潜在的问题,如大量的链接是为了导航(如“点击此按钮返回主页”)或付费广告而创建的。而出于商业竞争的原因, 尽管内容相关.有些网站又不会把超链接指向他们的竞争对手。 HITS首先利用一个传统的文本搜索引擎获取一个与主题相关的网页根集合,然后向根集合中扩充那些指向根集合中网页的网 页和根集合中网页所指向的网页,这样就获得了一个更大的基础集合。假设最终基础集合中包含N个网页,那么对于HrPS算法来 说,输入数据就是一个NxN的相邻矩阵A,其中如果网页i存在一个链接到网页j,则A。 =1,否则A。,=0。 HITS算法为每个网页i分配两个度量值:中心度h 和权威度a。。设向量a=(d.1,a …,a 代表所有基础集合中网页的权威度,而向 量h=(h ,h ,…,l )则代表所有的中心度.最初,将这两个向量均置为u=(1,1,…,1)。操作In(a)使向量a=ATh,而操作Out(h)使向量h=Aa. 反复迭代上述两个操作,每次迭代后对向量a和h范化,以保证其数值不会使计算溢出.Kleinberg证明经过足够的迭代次数,向量a 和h将分别收敛于矩阵AlrA和AA 的主特征向量。通过以上过程可以看出,基础集合巾网页的中心度和权威度从根本上是由基础 集合中的链接关系所决定的,更具体地说,是由矩阵A 和AAT所决定 3.3其它算法及归类 链接分析算法可以用来提高搜索引擎的查询效果,可以发现www上的重要的社区,可以分析某个网站的拓扑结构,声望,分 类等,可以用来实现文档的自动分类等。归根结底,能够帮助用户在www海量的信息里面准确找到需要的信息。这是一个正在迅 速发展的研究领域。 PageRank和HITS是算法中应用最广的两种,而其它一些类似的算法有的处于研究阶段,有的已经在具体的系统实现了。这些算 法大体可以分为3类:基于随机漫游模型的,比如PageRank,Repution算法;基于Hub和Authority相互加强模型的,如HIS及其变 T种;基于概率模型的,如SALSA,PHITS,基于贝叶斯模型的,如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容 分析技术进行了优化。一些实际的系统实现了某些算法,并且获得了很好的效果,Googte实现了PageRank算法,IBM Almaden Re. search Center的Clever Project实现了ARC算法,多伦多大学计算机系实现了一个原型系统TOPIC,来计算指定网页有声望的主题。 4 PageRank与HITS算法比较 显而易见,两者均是基于链接分析的搜索引擎排序算法,并且在算法中二者均利用了特征向量作为理论基础和收敛性依据.但 两种算法的不同点也非常明显 。 PageRank是对www的整体分析,通过模拟在WWW上的随机游动对每一个网页计算其PageRank值。因此该算法是独立于 用户查询的,可以对用户要求产生快速的响应。HITS算法是对WWW的局部分析,是根据特定的查询产生不同的根集.然后计算网 页的Authority值和Hub值。该算法是依赖于用户查询的,实时性差。 HITS算法存在“主题漂移’’的现象,如用户在查询“量子物理学”时,由于算法中需要对初次检索结果的根集扩充成基集,最终的 检索结果中会包含大量的有关“物理学”的站点。因此,HITS适合与宽主题的查询,而PageRank则较好地克服了“主题漂移”的现象。 5应用WEB结构挖掘算法提高网站价值 5.1选择链接策略 在互联网的海洋中,最重要的就是互联互通,不被其他网站引用的网站就是“信息孤岛”。WEB结构挖掘引擎所有算法都将网页 中的链接作为主要挖掘的对象,特别是实际应用中,大多数用户都是使用基于PageRank算法的Google,Yahoo,Baidu都搜索引擎, 因此可以采取以下几种策略,提高网站的排名。 1)广泛链接策略。来自其他网站的任何反相链接都是有用的。当前常见的新搜索引擎已经不再只是网站目录的索引.而是更全 面的网页索引,所以无论来自其他网站任何地方的反相链接都是非常有价值的 同时如果一个网页只有大量的进入链接,而缺乏导出链接,也会被搜索引擎认为是没有价值的站点。保证你的网站能够帮助搜 索引擎更准确地判断哪些是对用户最有价值的信息,也就是说如果你的网站只有外部反向链接而没有导出链接的话.也会对你的 网站在搜索结果中的表现带来负面影响。 2)高质量链接策略。被PageRank高的网站引用能更快地提高PageRank数量只是关键因素之一,来自PageRank高的页面的链 接还能更快的提高被链接目标的PageRank 3)无空链接策略。应当保持网站自身的健康,经常利用坏链检查工具检查网站中是否有死链。同时保持网页内容/链接的稳定性 和持久性:在搜索引擎索引中网页存在的历史也是一个比较重要的因素,而且历史比较久的网页被链接的几率越高。为了保证自己 网页能够被比较持久的被其他网站的页面引用,如果自己网页中有链接更新时,最好能保留旧的页面并做好链接转向,以保持内容 的连续性。 5.2构建友好的网站结构 有了合适的链接,就可以在算法中取得一个比较理想的分值,但由于数据的挖掘过程中由机器Spider自动完成。因此还必须考 虑让引擎能完整的采集到所设计的链接,这就需要按照下面方式构建友好的网站结构: 1620 网络通讯趸安全 ;* (下转第1629页) 本栏目责任编辑:冯蕾 周新:.NET平台下移动Agent系统开发技术研究 当运行TestApp.exe时,.NET CLR(通用语言运行环境)会首 先创建一个应用程序域(AppDomain)来容纳TestApp.exe 接着,CLR 将引用的程序集加载到该应用程序域中 MSCorLib.dll是一个基 本的程序集,该程序集会自动被加载到每个应用程序域中。然后, CLR加载应用程序(即TestApp.exe)所属以及引用的程序集。程序 集的加载一般在应用程序启动时通过CLR自动加载完毕。然而,. NET平台也提供了一种应用程序运行后动态加载程序集的方法, 即文章前面提到的反射技术.通过该技术动态加载程序集、获取 类类型、创建该类实例、调用实例中的方法.使得动态执行移动A— gent代码成为可能。 在移动Agent系统开发实例中,对程序集加载运行的设计思 路如下: 首先,在Agent基类的Move方法中加入TransferAgentAssem— bliesToHost方法,将程序集传送至服务端。 其次.在AgentHost远程对象类巾.增加IsAssemb1vInstalled (程序集安装判定)和SaveAssemblvBits(按位存储程序集)。方法 图3应用程序域中的组件及相互关系 IsAssemblvInstalled使用参数提供的名称和路径来调用程序集,如 果失败,即程序集没有安装。SaveAssemblvBits方法也是使用程序 集的全名,将其按二进制方式存放到指定的路径。 最后,在AgentHost类中,增强HostAgent方法的功能,利用反射机制,根据路径调用存储的程序集,取得移动Agent的类,并执 行Agent的Run方法。 其中有些细节需要说明,在Agent基类传递程序集前,需要调用AgentHost中的IsAssemblyInsta1led来判断相关的程序集是否已 经安装,在没有安装的情况下才发送,当然还需要通过递归的方法将与 亥程序集有依赖关系的程序集一并发送。为提高程序集的管 理效率,可以将程序集获取、解析、存储、查找等方法统一归属至一个辅助类如AssemblyManagert31。 5结束语 移动Agent系统开发面临着信道建立、代码移动、程序集加载运行等主要难题,微软.NET平台中的Remoting和反射技术,为系 统开发提供了很好的环境支撑。大大简化了开发过程。.NET平台的强大功能有助于推动移动Agent系统的普及,发挥移动Agent系 统在数据采集、网络管理、科学计算等领域的突出优势。 参考文献: 【1]李朝纯,郭颂.移动Agent系统的研究【JJ.武汉理工大学学报,2004,26(1):38-41. f2]Chen X.应用框架的设计与实现——.NET平台【M】.温昱,靳向阳,译.北京:电子工业出版社,2005. [3]Neely M.Write Mobile Agents In.NET To Roam And Interact On Your Network[EB/OL].http://msdn.microsoft.com]en—us/magazine/ CC 1 63649.aspx. (上接第1620页) 11网站结构扁平化。网站目录结构要扁平,因为每深一级目录,PAGERANK降低1—2个档次。假设首页是3,其子可能目录就是 1了,更深可能就无法列入评级范围了。 21表现和内容的分离。遵循w3c的规范,使用更规范的XHTML和XML作为显示格式,JavaScript和CSS尽可能和网页分离,一 方面提高代码重用度(也方便页面缓存),另外一方面,由于有效内容占网页长度的百分比高,也能提高相关关键词在页面中的比重 也增加了。因为挖掘引擎会更倾向于<title><h1><h2>……之间的内容,而不是正文。 31建立站点地图。让所有的贞面都有能够快速人E1:站点地图,方便网页爬虫(spider)快速遍历网站所有需要发布的内容。如果 首页就是用F1ash或图片进入的话,无异于将搜索引擎拒之门外,除了UI设计的用户友好外,spider友好也是非常重要的。 5结束语 网络的结构挖掘技术已经是比较成熟的技术,特别是PageRank算法已经应用到各大搜索网站中。所有的结构挖掘算法都是基 于网页结构中超链接的分析。所不同的仅仅只是分析的效率改进和一些附加的分析条件。通过网站结构算法的研究,可以有效地采 取应对措施,提高网站在搜索引擎中的排名。从而能网站可以有效的被客户搜索。随着电子商务的迅猛发展,企业应当尽早地重视 这种被挖掘的技术应用,提高自身网站的价值。 参考文献: f11何晓阳,吴强,吴治蓉.HIIS算法与PageRank算法比较分析【J].情报杂志,2004(2). f21王晓宇,周傲.万维网的链接结构分析及其应用综述[J].软件学报,2003(10). 【3]杨炳儒,李岩,陈新中,等.Web结构挖掘【J].计算机工程,2003(11). 『41杨沅钊,吴薇,喻晓莉,等.搜索引擎排名改进算法分析『j].农业网络信息,2005(2). 本栏目责任编辑:冯蕾