（计算机应用技术专业论文）基于web结构挖掘的hits算法研究.pdf

摘要 w e b 是一个巨大的信息资源库，提供了各种各样的信息服务，随 着网络的普及和网络信息的迅速膨胀，如何有效的从w e b 获取所需信 息变得越来越重要。为此，在w e b 这样的分布式环境中找到有价值的 信息，并从中提取出知识内容已经成为目前信息检索、数据挖掘重要 课题。用户不仅希望得到相关的w e b 页面外，还希望检索到的页面具 有高质量，即找到权威页面。网页的超链接是一个重要的研究途径， 链接分析( 即w e b 结构挖掘) 的引入和应用为这些问题的解决提供了 一条崭新的思路。h i t s 算法是一种应用广泛的基于链接分析的权威 资源提取算法，具有很高的研究价值。 w e b 结构挖掘是w e b 数据挖掘的一个重要方面，其重点在于信息 检索，链接分析技术在该领域中扮演着极为重要的角色，并已经被成 功的用于分析w e b 超链接数据来确定权威的信息源。在各种对网页进 行链接分析并提取分组的算法中，h i t s ( h y p e r - t e x t i n d u c e d t o p i cs e a r c h ) 算法是应用的最为广泛的。 本文对h i t s 算法进行了重点研究，对传统h i t s 算法易产生主题 偏移问题这一缺点进行了分析，并针对这一问题，使用根集向量投影 法和基本集缩减法对h i t s 算法加以改进，接着在根集向量投影法的 基础上，提出了根集向量加权投影法和基本集向量加权投影法，以更 好的实现权威网页搜索。对改进后的h i t s 算法与传统h i t s 算法进行 了实验比较，发现根集向量投影法可以有效的避免主题偏移现象，基 本集缩减法可以大大的缩减算法运算量，而根集向量加权投影法和基 本集向量加权投影法则可以在使权威网页的提取结果更为合理的基 础上，有效提高算法的灵活性。 关键词w e b 结构挖掘；h i t s 算法；向量投影法；缩减法；加权投影 法 a b s t r a c t w e bi sa ne n o r m o u si n f o r m a t i o nr e s o u r c e sb a n k ，w h i c hp r o v i d e sv a r i o u sk i n d so fi n f o r m a t i o ns e r v i c e s a st h e p r e v a l e n c eo fw e ba n dt h eq u i c ke x p a n s i o no fw e bi n f o r m a t i o n ，h o wt o a c q u i r ei n f o r m a t i o nt h a tw en e e df r o mw e bb e c o m e sm o r ea n dm o r ei m p o r t a n t t h e r e f o r e ，d i s c o v e r i n gv a l u a b l ei n f o r m a t i o nf r o md i s t r i b u t i v ew e be n v i r o n m e n ta n da c q u i r ek n o w l e d g ef r o mi th a sb e c a m ei m p o r t a n tt a s ko ft h ei n f o r m a t i o nr e s e a r c ha n dd a t am i n i n gf i e l da tp r e s e n t u s e r sh o p et og e tn o to n l yt h er e l e v a n tw e bp a g e s ，b u ta l s op a g e ss e a r c h e d w i t hh i g hq u a l i t y , t h a t st o s a yt o f i n do u ta u t h o r i t yp a g e s p a g e sh y p e r l i n ki sa ni m p o r t a n tm e t h o df o ri t ，a n dt h ei n t r o d u c t i o na n da p p l i c a t i o no fh y p e r l i n ka n a l y s i sp r o v i d eaw h o l l yn e wa p p r o a c ht os o u t et h o s ep r o b l e m s t h eh i t s ( h y p e r - t e x t i n d u c e d t o p i c s e a r c h ) a l g o r i t h mi saw i d e l yu s e da u t h o r i t ys o u r c e d i s t i l l i n ga l g o r i t h mw h i c hb a s e dh y p e r l i n ka n a l y s i sa n dh a sh i g hv a l u ef o r s t u d y i nw e bs t r u c t u r em i n i n g ，h y p e r l i n ka n a l y s i sh a sb e e ns u c c e s s f u l l y u s e di na n a l y z i n gt h eh y p e r l i n kd a t ao fw e b p a g e st oe x t r a c ta u t h o r i t a t i v e i n f o r m a t i o ns o u r c e s a m o n gv a r i o u sh y p e r l i n ka n a l y s i sm e t h o d s ，h i t s a l g o r i t h mi su s e dt h em o s tw i d e l y i nt h ef o l l o w i n gp a r to ft h i st h e s i s ，h i t sa l g o r i t h mi sd i s c u s s e da n d t h et o p i cd r i f tp r o b l e mo fh i t sa l g o r i t h mi sa l s oa n a l y z e d t h e nr o o t s e t e i g e n v e c t o rp r o je c t i o nm e t h o da n db a s e s e t d o w n s i z i n gm e t h o da r e i m p l e m e n t e dt oi m p r o v et h eh i t sa l g o r i t h m b a s e do np r o je c t i o nm e t h o d ， w e i g h e dr o o t s e te i g e n v e c t o rp r o j e c t i o nm e t h o da n dw e i g h e db a s e s e t e i g e n v e c t o rp r o j e c t i o nm e t h o da r ea l s op r o p o s e di n t h i st h e s i st om a k e d e e p e ri m p r o v e m e n t s ot h a tt h es e a r c ho fa u t h o r i t a t i v ew 曲p a g c sc a nb e m o r ee f f e c t i v e l y k e y w o r d sw e bd a t am i n i n g ；h i t sa l g o r i t h m ；e i g e n v e c t o rp r o j e c t i o n m e t h o d ；d o w n s i z i n gm e t h o d ；w e i g h e de i g e n v e c t o rp r o j e c t i o nm e t h o d 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：堑i 生 日期： 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 储签名：译翩签名五也期：堕年月旦日 硕上学位论文第一章绪论 第一章绪论 知识是当今世界一种最重要的财富。数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，即k d d ) 方法和数据挖掘技术【l 】【2 】【3 】【4 】，近几年受到人们的 高度重视，并对其进行了深入的研究，取得了不少成果，产生了许多有效的方法 和技术。 1 1 研究背景及意义 随着i n t e m e t 技术的迅猛发展，w w w ( w o r l dw i d ew e b ) 已发展成为拥有3 亿 页面的分布式信息空间，而且这个数字仍以每4 至6 个月翻一番的速度增加着。 面对这海量的数据和信息，人们却感知识的匮乏。现代社会的竞争趋势要求必须 对w e b 大量复杂的信息进行实时的和深层次的分析，从中找出真正有价值的信 息知识，用于科学研究、决策支持、过程控制、趋势预测、偏差预防等，但是， 现有的k d d 方法和技术已不能满足人们从w e b 获取知识的需要，这是因为： ( 1 ) w e b 数据是异质、异构、动态、模糊的半结构化、非结构化或数据库 信息； ( 2 ) 异质、异构以及动态性给数据仓储带来极大困难； ( 3 ) 语义理解难度加大，造成基于内容的信息检索难以实现； ( 4 ) 挖掘算法、信息模型的动态性以及大样本空间搜索能力要求很高； ( 5 ) 现有的k d d 方法和m d 技术不能直接运用于w e b 挖掘。 因此，人们迫切感到需要一种新的技术一基于w e b 的数据挖掘技术，以便 从w e b 海量的数据中自动地，智能地抽取隐藏于这些数据中的知识。w e b 数据 挖掘是一种新兴的边缘科学技术，它涉及到机器学习、数据挖掘、信息检索、自 然语言处理、数据库以及人工智能等技术，可用于网络检索、网站建设以及电子 商务等方面。 w e b 挖掘是一项涉及w e b 技术、数据库、机器学习、数据挖掘、统计学、 计算机语言学等多学科的综合技术，不同的研究者从不同的角度出发，对w e b 挖掘有着不同的理解。研究搜索引擎的人着重于w e b 页面上文本数据的分析； 而设计w e b 站点结构的入，则着重于用户对w e b 站点访问模式的研究。我们从 更为一般的角度出发，对w e b 挖掘作如下定义：w e b 挖掘是指从大量的w e b 硕： = 学位论文第一章绪论 文档的集合c 中发现隐含模式p 的过程。如果将c 看作输入，将p 看作输出， 那么w e b 的过程就是从输入到输出的一个映射己：c p 。 当前w e b 上的信息主要分为三类： ( 1 ) w e b 页面中的内容，包括文本信息和各种媒体信息； ( 2 ) w e b 服务器上的用户登陆网站的访问日志数据； ( 3 ) w r e b 页面中超链之间相互引用的数据。 对三种数据采用的处理算法有很大的差异，由此w e b 挖掘主要分类三类： w e b 内容挖掘、w e b 访问同志挖掘( 也叫w e b 使用挖掘) 和w e b 结构挖掘。 传统的w e b 搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询 项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。 有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜 索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引 擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观 性强，费用高，更新速度慢。 最近几年，许多研究者发现，w w w 上超链结构是个非常丰富和重要的资源， 如果能够充分利用的话，可以极大的提高检索结果的质量。基于这种超链分析的 思想，s e r g e yb r i n 和l a w r e n c ep a g e 在1 9 9 8 年提出了p a g e r a n k 算法【5 】f 6 】，同年 j k l e i n b e r g 提出了h i t s 算法，其它一些学者也相继提出了另外的链接分析算 法，如s a l s a ，p h i t s ，b a y e s i a n 等算法。这些算法有的已经在实际的系统中 实现和使用，并且取得了良好的效果。 1 2 研究内容及组织 在广泛参考和整理相关资料的基础上，本文采取理论分析，算法实现和仿真 试验相结合的方法，首先对国内外w e b 结构挖掘的现状进行了概述，接着分别 对w e b 结构挖掘中的两个重要算法p a g e r a n k 算法和h i t s 进行了详细的描述， 比较两种算法之间的优越点以及各自存在的问题。探讨了对h i t s 算法进行改进 的方法，提出了自己的改进h i t s 思想，并应用改进的方法构建w e b 结构挖掘 平台，进行了相关的实验。 本文总共分六章，各章内容分别如下： 第一章介绍了国内外w e b 结构挖掘研究的现状和发展趋势，并指出本文研 究的主要工作既课题研究的目的和课题研究的意义： 第二章对数据挖掘技术以及w e b 结构挖掘技术进行了总体的了解，包括基 2 硕士学位论文 第一章绪论 本概念、主要的方法技术、研究现状及存在的问题，为在这一领域进行跟深入的 研究打下初步基础； 第三章对w e b 结构挖掘进行了全面深入的分析，包括主要的算法、算法的 相关原理、主要应用和当前研究热点等； 第四章对h i t s 算法进行深入剖析，并针对当前h i t s 算法存在的问题，提 出一些改进思想： 第五章对改进h i t s 后的算法进行实验及数据分析； 第六章主要是对本文工作的总结，给出对本文研究工作的结论，并指出当前 存在的问题及后续研究工作的方向和工作重心。 硕： ：学位论文 第二章w e b 数据挖掘的基本理论 第二章w e b 数据挖掘的基本理论 现代的人类己经处于一个信息极度丰富的时代，人们可以从各种各样的传播 媒体获得信息，如报纸、电视、杂志、万维网等，近几年万维网己经成为一个巨 大的、分布广泛的全球性的信息服务中心并逐渐渗透到人们的日常生活，它为用 户提供了所能想到的各种信息资源。然而，面对复杂而庞大的万维网，多数用户 往往觉得力不从心。如何有效的满足用户的需求，依据用户的需求帮助用户从因 特网的信息海洋中发现他们所要寻找或者感兴趣的资源，己经成为一项迫切而重 要的课题。 2 1w e b 数据挖掘的产生与发展 由于互联网是一个高速增长、完全不受控制的异构信息集合，因而无论是 w e b 信息资源的利用，还是w e b 拓扑建模，经典的信息挖掘技术和数据建模方 法都很难得到有效应用，而超链分析的引入和应用为这些问题的解决提供了一条 崭新的思路。大量研究表明，w e b 的链接结构具有自组织性，w e b 的这种自组 织性为链接分析提供了依据。所有对链接分析的研究基于以下两个假设： ( 1 ) 链接表达了作者的荐举性，如果a 网页链接到b 网页，且a ，b 两网 页的作者不同，那么说明a 网页认为b 网页对其有价值； ( 2 ) 被同一网页指向的不同网页往往是主题相关的。 在全局上，页面间通过超链接将相同或相关的内容主题自然地聚合 ( c l u s t e r i n g ) 在起，形成一个个社区( c o m m u n i t y ) ，社区内部的页面之间链接密集， 而不同社区之问链接稀疏、甚至根本不链接。在一个社区内部，页面之间的链接 结构也有规律的特征模式：一个社区主要由两类页面所组成，一类主要被别的页 面所链接，另一类则主要链接到别的页面。前者被k l e i n b e r g 称为权威( a u t h o r i t y ) 即包含高质量主题内容的页面；后者称为中心( h u b ) 即提供对高质量主题内容链 接的页面，它们均是用户想要的好的结果。 大多数像g o o g l e 这样的第二代搜索引擎已在其文档数据库中维护了页面 问的链接信息( 链接分析在w e b 信息检索中己普遍运用) ，它主要有两个用途： 一是抓取( c r a w l i n g ) 高质量的页面；二是对检索结果使用质量评分排序( r a n k i n g ) 即基于链接的排序。基于链接的排序有两种方案： ( 1 ) 独立于查询( q u e r y i n d e p e n d e n t ) 4 颂上学位论文第二章w 幽数据挖掘的基本理论 这是一种用户检索静处理，链接分析算法计算页面“固有的 质量值，在用 户查询时，质量值与姻关度等线性组合后对结果进行排序。典型的算法有g o o g l e 中采用的p a g e r a n k 算法。 ( 2 ) 依赖于查询( ( q u e r y - d e p e n d e n t ) 这是一种用户检索后处理，检索系统响应用户查询后返回结果集，链接分析 算法依此为起点获得一组与用户查询主题相关的页面、计算各页面的质量值，并 据此精选出少量高质量的信息源。因此，这种方案也称主题提取。典型的算法有 i b mc l e v e 项目中提出的h i t s 算法。 搜索弓l 擎的发展经过了几个阶段，起初一味地遥求收集网页的多少。后来发 现对同一用户提问，搜索引擎返回的信息太多，用户感到无所适从。1 9 9 6 年起， 搜索引擎技术开始注重网页质量与相关性的结合，这主要是通过对网上的超文本 和链接结构进行分耩，一个网页的重要性取决于它被其他网页链接的数量，特别 是一些已经被认定是“重要”的网页的链接数量。每一个链接都是一张价值相等 “选票”，所获选票的总价值将决定谁是这场比赛的优胜者，谁将被安置在最重 要、最显赫的位置上。事实证明，这一技术是非常有效的，尤其是网络资源的膨 胀毖然产生更多的链接，从焉为评价网页重要性提供了更多的证据。我们根据霹 页的得票数评定其重要性。然而，除了考虑网页褥票数( 即链接) 的数量之外， 还要分析为其投票的网页。“重要”网页所投的票份量自然较重，有助于增强其 他网页的“重要性对。重要的、高质量的网页可获得较高的网页级别，从而在搜 索结果中可以获得较高的排位。这代表了该蹰页本身的特性，是根据网络数据、 采用评定链接结构的综合运算法则进行分析的结果。 2 2w e b 数据挖掘概述 因特网是到目前为止世界上最丰富和最密集的信息来源，在海量的、异构的 w e b 信怠资源中，蕴藏着具有巨大潜在价值的知识。所以人们追切需要找到这样 的工具，能够从w e b 上快速、有效的发现资源，发现隐含的规律性内容，提高 w e b 信息的利用效率，解决数据的应用质量问题。w e b 数据挖掘就是为顺应这 种需要而发展起来的数据处理技术。 w e b 数据挖掘是指在v c w w 上挖掘有趣蛉、潜在的、蕴藏的信息以及有用的 模式这样一个过程【7 】【8 1 。原始数据可以是结构化的，如关系数据库中的数据；也 可以是半结构化的，如文本、图形、图像数据；甚至是分布在网络上的异构型数 据。w e b 上的数据不同于传统的数据库的数据，它具有半结构化等特点。因此， 5 硕： 学位论文第二章w e b 数据挖掘的基本理论 面向w e b 的数据挖掘比面向单个数据仓库的数据挖掘要复杂的多，w e b 数据挖 掘有自身的特点，主要体现在以下几个方面： ( 1 ) 异构数据库环境 从数据库研究的角度出发，w e b 网站上的信息也可以看作一个数据库，一个 更大、更复杂的数据库。w e b 上的每一个站点就是一个数据源，每个数据源都是 异构的，因而每一站点之间的信息和组织都不一样，这就构成了一个巨大的异构 数据库环境。如果想要利用这些数据进行数据挖掘，首先，必须研究站点之间异 构数据的集成问题，只有将这些站点的数据都集成起来，提供给用户一个统一的 视图，才有可能从巨大的数据资源中获取所需的东西。其次，还要解决w e b 上 的数据查询问题，因为如果所需的数据不能很有效地得到，对这些数据进行分析、 集成、处理就无从谈起。 ( 2 ) 半结构化的数据结构 w - e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据 模型，可以根据此模型来具体描述特定的数据，而w e b 上的数据非常复杂，没 有特定的模型描述，每一站点的数据都各自独立设计，并且数据本身具有自述性 和动态可变性。因而w e b 上的数据具有一定的结构性，但因自述层次的存在， 从而是一种非完全结构化的数据，这也被称之为半结构化数据。半结构化是w 曲 上数据的最大特点。 ( 3 ) 解决半结构化的数据源问题 w e b 数据挖掘技术首要解决半结构化数据源模型和半结构化数据模型的查 询与集成问题。解决w e b 上的异构数据的集成与查询问题，就必须要有一个模 型来清晰的描述w e b 上的数据，针对w e b 上的数据半结构化的特点，寻找一个 半结构化的数据模型是解决问题的关键所在。除了要定义一个半结构化数据模型 外，还需要一种半结构化模型抽取技术，即自动地从现有数据中抽取半结构化模 型的技术。面向w e b 的数据挖掘要以半结构化模型和半结构化数据模型抽取技 术为前提。 w e b 挖掘( w e bm i n i n g ) 是数据挖掘在w e b 上的应用，是一项综合技术，涉及 网络、数据挖掘、计算机语言学、信息学等多个领域。w e b 挖掘是针对w e b 页 面内容，站点拓扑结构，用户访问信息，用户注册信息及电子商务交易信息等在 内的各种数据，应用数据挖掘方法以发现有用的知识的过程。它可以帮助人们从 w w w 中发现知识，改进站点设计，提供个性化服务。 现今最流行的w e b 数据挖掘根据挖掘的对象不同可分为：w e b 内容挖掘、w e b 结构挖掘、w e b 使用记录挖掘，其分类如图2 1 所示。 6 硕十学位论文第一二章w e b 数据挖掘的基本理论 图2 1w e b 数据挖掘分类图 ( 1 ) w r e b 内容挖掘 w e b 内容挖掘是指从w e b 网页内容( 包括文本、超文本、图像、音视频、元 数据等多媒体信息) 中白动发现和获取知识，特点是数据是无结构或半结构化的。 w e b 内容挖掘可用于协助用户搜集信息或根据用户的目标过滤无用的信息。目前 的主要成果是在w e b 文本挖掘上。它和通常的平面文本挖掘的功能和方法比较 类似，但由于w e b 文档中存在标签，因此可以利用这些标签来提高w e b 文本挖 掘的性能。一些研究工作还结合了文档之间的超链结构【9 j 。 w e b 内容挖掘可分为两类：一类是面向信皂, ( i n f o n n a t i o nr e s e a r c h ) 的w 曲内 容挖掘，目的是从用户的角度出发，改善信息检索质量或者信息过滤的性能；另 一类是面向数据建模的w e b 内容挖掘，通过挖掘数据模式，实现数据集成和像 关系数据库那样对w e b 数据执行一些复杂的查询。常见的方法是将文档内容抽 取到某个数据模型。 与数据库中的结构化数据相比，w e b 文档具有有限的结构，或者根本就没有 结构。即使具有一些结构，也是着重于格式，而非文档内容。文档的结构不一致， 文档的内容是自然语言，计算机很难处理其语义。文本信息源的这些特殊性使得 现有的数据挖掘技术无法直接应用于其上，需要对文本进行预处理，抽取代表其 特征的元数据，作为文档的中间表示形式。文本特征分为描述性特征，例如文本 的名称、日期、大小、类型等，以及语义性特征，例如文本的作者、机构、标题、 内容等。描述性特征易于获得，而语义性特征则较难得到。在此基础上，可以从 半结构化的w 曲文档中抽取作者、机构等特征。 w r e b 内容的表示是w e b 挖掘中的基本问题，w 曲挖掘中的很多课题( 如分 类、聚类、网页问关系的学习、规则或模式的抽取等) 均与此相关。经典的文本 表示采用了向量空间的表示法，在该方法中，文档空间被表示成一组正交词条矢 量所构成的矢量空间，而忽略词的出现顺序。特征的取值可以是布尔值( 根据词 条是否出现分别取1 或o ) ，或基于词频的函数值。同时要进行特征选择，如基 于信息增益、互信息、墒、概率比率、隐形语义索引等实现向量的降维。 w e b 内容挖掘常用的领域有分类、聚类、关联分析、w e b 主题发现与跟踪、 7 硕：七学位论文 第二章w e b 数据挖掘的基本理论 预测分析、提取规则发现、w e b 内容变化规律检测、用户模型、频繁子结构发现、 站点数据模式挖掘、数据集成等。 ( 2 ) w e b 结构挖掘 由于w e b 网页具有比纯文本更为丰富的结构，不仅具有文本信息，而且具 有表示网页之间关系的链接。所以在w e b 结构挖掘中主要目标是利用w e b 文档 之间的超链结构进行分析。主要的研究起源于社会网络的引述分析。w e b 页面包 含了从一个页面指向另一个页面的超链接，而超链接信息包含了人类潜在的注 释。大量的w e b 超链接信息提供了关于w e b 页面内容相关性、质量和结构方面 的信息，反映了文档之间的包含、引用或者从属关系。引用文档对被引用文档的 说明往往更客观、更概括、更准确。它有助于自动推断出页面的权威性。所谓权 威页面是在一个主题内被高度引用或参考的网页。与其相关的另一个概念是中心 页面，既那些指向许多权威页面的页面。权威页面和中心页面展示了强烈的互增 强关系；一个好的中心指向了许多好的权威；一个好的权威被许多好的中心所指。 在信息检索中可以将高权威值和高中心值的网页视为高质量的网页，优先提供给 用户。这样就可以通过分析超链拓扑结构发现w w w 上超链社区。对于检索结 果或指定的网页集合，可以构建一个有向图；每个结点表示一个网页，超链表示 结点间的有向边。h i t s ，p a g e r a n k 等给出了模型化w e b 拓扑结构的算法。这些 算法主要用作计算每个网页的质量和相关性的手段。关于h i t s 和p a g e r a n k 的 算法思想我们在以下章节中有详细描述。 ( 3 ) w e b 使用挖掘 w e b 使用挖掘即w e b 使用一记录挖掘，在新兴的电子商务领域有重要意义， 它通过挖掘相关的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析 日志记录中的规律，可以识别用户的忠实度、喜好、满意度，可以发现潜在用户， 增强站点的服务竞争力。w r e b 使用记录数据除了服务器的日志记录外还包括代 理服务器日志、浏览器端同志、注册信息、用户会话信息、交易信息、c o o k i e 中的信息、用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见 w e b 使用记录的数据量是非常巨大的，而且数据类型也相当丰富。w e b 使用挖 掘可以从w e b 服务器那里自动发现用户存取w e b 页面的模式，得出群体用户或 单个用户的访问模式和兴趣，目前已成功应用到个性化推荐、系统改进以及商业 智能等方面。 根据对数据源的不同处理方法，w e b 使用挖掘可以分为两类，一类是将w e b 使用记录的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系表中 的数据进行常规挖掘；另一类是将w e b 使用记录的数据直接预处理再进行挖掘。 w e b 使用挖掘基本过程分为两步：第一步，进行数据预处理，对w e bl o g 8 硕上学位论文 第二章w e b 数据挖掘的基本理论 进行清洗、过滤和转换，从中抽取感兴趣的数据；第二步，用数据挖掘技术进行 挖掘，包括建立数据立方体、进行路径分析、关联规则和分类聚类、序列模式发 现以及最终的挖掘结果可视化等等，从而实现w e b 流量分析、典型的时间序列 和用户行为模式分析、事物分析。 三种挖掘类型之问的区别比较可以清楚的通过如下表2 1 可以有所了解： 表2 1 三种挖掘类型之间的区别比较 挖掘方法数据来源数据形成数据对象搜索 结构挖掘拓扑结构超链接有向图超链集 内容挖掘页面挖掘文本索引页面集 使用挖掘 访问形式点击流 用户行为 日志数据 2 3w e b 结构挖掘概述 传统的w - e b 搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询 项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。 有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜 索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引 擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观 性强，费用高，更新速度慢。 w e b 结构包括不同网页之间的超链接结构和一个网页内部的可以用h t m l ， x m l 表示成的树开结构，以及文档u r l 中的目录路径结构等。w e b 页之间的超 链接结构中包含了许多有用的信息，当网页a 到网页b 存在一个超链接时，则 说明网页a 的作者认为网页b 的内容非常重要，且两个网页的内容具有相似的 主题。因此，指向一个文档的超链接体现了该文档的被引用情况。如果大量的链 接都指向了同一个网页，就认为它是一个权威页。这就类似于论文对参考文献的 引用，如果某一篇文章经常被引用，就说明它非常重要。这种思想有助于对搜索 引擎的返回结果进行相关度排序。从w w w 的组织结构和链接关系中推导知识。 通过对w e b 站点的结构进行分析、变形和归纳，将w e b 页面进行分类，分析一 个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式，确定不同 页面问的相似度和关联度信息。定位相关主题的权威站点，可以极大的提高检索 结果的质量。 基于这种超链分析的思想，s e r g e yb r i n 和l a w r e n c ep a g e 在1 9 9 8 年提出了 9 硕上学位论文 第二章w e b 数据挖掘的基本理论 p a g e r a n k 算法，同年j k l e i n b e r g 提出了h i t s 算法，其它一些学者也相继提 出了另外的链接分析算法，如s a l s a ，p h i t s ，b a y e s i a n 等算法。这些算法有 的已经在实际的系统中实现和使用，并且取得了良好的效果。 l o 硕士学位论文第三章w e b 结构挖掘的相关算法理论 第三章w e b 结构挖掘的相关算法理论 每个w e b 页面并不完全是平面结构，而是有自己的特定结构。w e b 结构挖 掘的目的是发现页面的结构( 文档内部结构) 和w e b 的结构( 文档间超链结构) ， 利用这些结构所蕴涵的信息可以帮助我们发现很多有用的模式或知识。文档内部 结构挖掘( 有人将其划人到w e b 内容挖掘里面) 。本文主要论述的是如何利用超 链来对w e b 结构进行挖掘。 3 1 文档超链结构 文档间超链结构挖掘主要基于s c i 的科学引文分析理论，如果两篇文献具有 同被弓l ( c o - c i t a t i o n ) 和耦合( c o u p l i n g ) 等关系，则这两篇文献具有相互关系或相互 联系。充分利用这些关系，能够客观地反映科学活动中许多隐蔽的和深层次的相 关关系，显示出有用的结构。 m r h e n z i n g e r 认为目前的w e b 超链接分析大多基于以下两条基本假设： 假设l ：从w e b 网页a 指向网页b 的超链接是网页a 作者对网页b 的推荐。 假设2 ：如果一条超链接将网页a 和网页b 相互链接起来，则网页a 和网 页b 可能有共同的主题( t o p i c ) 。 基于上面的两个基本假设，我们还可以引申出以下几个假设： 假设3 ：一个页面被多次引用，即很多页面有指向它的链接，则这个页面很 重要。 假设4 ：一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页 面也可能很重要。 假设5 ：个页面的重要性被均匀分布并传递到它所引用的页面。 假设6 ：如果页面p 和q 同被引，则它们可能是相关的， 同被引度越大， 相关度越大。 假设7 ：如果页面p 和q 耦合，则它们可能是相关的，耦合度越大，相关度 越大。 硕士学位论文第三章w e b 结构挖掘的相关算法理论 3 2p a g e r a n k 算法 基于假设3 5 ，s b r i n 和l p a g e 提出了计算页面权威性的算法【1 0 1 。计算 如公式( 3 一1 ) ： 盼( 1 _ c ) ，轳 ( 3 一1 ) p a g e 和b r i n 认为c 的最佳值为0 8 5 。其中b ( i ) 代表指向页面i 的页面集合。 n ( j ) 表示页面i 中指向其他页面的超链数目。r ( i ) 表示为页面i 的权威度。 p a g e 和b r i n 就根据这个原理，与关键词检索以及其他基于文本的技术一起 来提高查询质量。 3 3 t s 算法 h i t s 最早是在h i t s 算法是由康奈尔大学( c o m e l lu n i v e r s i t y ) 的j o n k l e i n b e r g 博士于1 9 9 8 年首先提出的【】。目前，它为i b m 公司阿尔马登研究中 心( i b ma l m a d e nr e s e a r c hc e n t e r ) 的名为“c le v e r ”的研究项目中的一部分。 j o nk l e i n b e r g 认为每个网页有两个级另t j ( r a n k i n g ) ：权威级别( 依赖于指向它的页 面) 、中心级别( 依赖于它指向别人的页面) 。工作过程如下：用基于文本的搜 索引擎得到某一查寻的结果集合r ( 称为r o o ts e t ) ；将r 所指向的页面集合以 及其他指向r 的页面集合包含进来形成集合s ；将所有页面的权威级别、中心 级别全部置初始值为1 ，再按照如下算法计算： r e p e a tu n t i lc o n v e r g e n c e ( 收敛) 口f = 乃；= a j f o ra l lp a g eii ns ： j e b ( i )j e f ( ，) ( 3 - 2 ) n o r m a l i z e ： ，口；= l ；，砰= 1 ( 3 3 ) e n d 其中b ( i ) 代表指向页面i 的所有页面集合；f ( i ) 代表页面i 所指向的页面集合。 最后根据权威级别的大小返回给用户。 其他类似的算法还有s a l s a 、p s a l s a 、p h i t s 等，基本原理与h i t s 相同。 1 2 硕十学位论文 第三章w e b 结构挖掘的相关算法理论 3 4p a g e r a n k 算法与h it s 算法的比较分析 显而易见，两者均是基于链接分析的搜索引擎排序算法，并且在算法中二者 均利用了特征向量作为理论基础和收敛性依据。但两种算法的不同点也非常明 显，下面就主要谈谈其不同点： ( 1 ) 从算法思想上看，虽然均同为链接分析算法，但二者之间还是有一定 的区别【1 2 1 。h i t s 的原理如前所述，其a u t h o r i t y 值只是相对于某个检索主题的 权重，因此h i t s 算法也常被称为q u e r y d e p e n d e n t 算法【1 3 l 。而p a g e r a n k 算 法独立于检索主题，因此也常被称为q u e r y i n d e p e n d e n t 算法。p a g e r a n k 的发 明者( p a g e & b r i n ) 把引文分析思想借鉴到网络文档重要性的计算中来，利用网络 自身的超链接结构给所有的网页确定一个重要性的等级数【l4 1 。当然p a g e r a n k 并 不是引文分析的完全翻版，根据因特网自身的性质等，它不仅考虑了网页引用数 量，还特别考虑了网页本身的重要性。简单地说，重要网页所指向的链接将大大 增加被指向网页的重要性l ”j 。 ( 2 ) 从权重的传播模型来看，h i t s 是首先通过基于文本的搜索引擎来获得 最初的处理数据，网页重要性的传播是通过h u b 页向a u t h o r i t y 页传递，而且 k l e i n b e r g 认为，h u b 与a u t h o r i t y 之间是相互增强的关系【l6 j ；而p a g e r a n k 基于 随机冲浪( r a n d o ms u r f e o 模型，可以认为它将网页的重要性从一个a u t h o r i t y 页 传递给另一个a u t h o r i t y 页【1 7 j 。 ( 3 ) 从处理的数据量及用户端等待时间来分析。表面上看，h i t s 算法对 需排序的网页数量较小，所计算的网页数量一般为1 0 0 0 至5 0 0 0 个，但由于需 要从基于内容分析的搜索引擎中提取根集并扩充基本集，这个过程需要耗费相当 的时间【1 8 】，而p a g e r a n k 算法表面上看，处理的数据数量上远远超过了h i t s 算法 1 1 9 。据g o o g l e 介绍【2 0 1 ，目前已收录的中文网页已达3 3 亿以上，但由于其计算量 在用户查询时已由服务器端独立完成，不需要用户端等待，基于该原因，从用户 端等待时间来看，p a g e r a n k 算法应该比h i t s 要短【2 。 基于链接分析的网页排序算法，目前的研究都还很不成熟，无论是p a g e r a n k 算法，还是h i t s 算法，已有众多的国内外学者在算法的改进方面做出了努力。 值得关注的是，目前已有学者对这两种算法相结合的可能性作了理论上的探讨。 3 5w e b 结构挖掘算法的主要应用 w e b 结构挖掘的主要应用有以下几个方面： 硕上学位论文第三章w e b 结构挖掘的相关算法理论 ( 1 ) 指导网页采集 网页采集【2 2 】【2 3 】【2 4 1 是搜索引擎机器人爬行网页的过程。它一般是根据网页之 间的链接信息来采集网页，采集效率低。为了采集“高质量 的网页，就应按照 网页质量的高低依次来进行采集，使得采集少量的网页而获得最好的网页。网页 链接分析为判断网页的质量提供了一种方式。 ( 2 ) 帮助结果查询 因为网页数量巨大，不可能对全部的页面进行链接分析。所以实际的工作过 程如下：先用基于关键词的搜索引擎得到一个集合( 取前面n 个) 。然后对这n 个页面应用p a g e r a n k 或h i t s 算法，得到最终的排序结果f 2 2 】【2 5 】【2 6 1 。对该算法的 评价可以参考文献【2 7 】 ( 3 ) 检索结构聚类 目前搜索引擎结果还不是令人满意。与基于词或短语的文本聚类算法不同， 有学者使用超链分析来对结果进行聚类【2 7 1 。它是基于c o c i t a t i o n 和c o u p l i n g 分 析来过滤无关文档，将质量高的文档进行聚类，提供给用户进行浏览和访问。例 如用户检索“j a g u a r ”，将结果聚类如下：j a g u a r c a r 、j a g u a rc l u b 、eo nj a g u a r c a r 、j a g u a rg a m e 等，从而方便用户浏览。 ( 4 ) 查找相关网页 根据实例查找，或称之为找相关网页( f i n dr e l a t e d p a g e s ) 2 2 1 2 9 1 。根据用户需 要查找的某一实例，例如一个网页，找出与之相关类似的网页。在g o o s e 和 n e t s c a p e 中支持这种服务。传统的信息检索技术是采用文本相似度，而在w r e b 环境中，可以充分挖掘链接结构来实现。k l e i n b e r g 声称将h i t s 算法稍加修改 也可以用来实现实例查找。d e a n 和h e n z i n g e r 提出了两种算法：c o m p a n i o n 算法、 c o c i t a t i o n 算法。基于链接分析的算法总体上优于基于文本相似度算法。 ( 5 ) 消除重复网页 网页路径是u r l 的一部分。例如：u r l ：h t t p ：g o o g l e c o r n a b o u t h t m l ， w v c w g o o g l e c o m 就是主机地址，a b o u t h t m l 是路径。两台主机h 2 和h 1 是镜像网站，当且仅当h 2 中的文档，在h 1 中具有相同路径的相似文档，反之 亦然。镜像网站具有相似的超链结构。通过超链分析可以检测出近似的镜像网站， 从而节省索引空间和存储空剐2 2 】【3 0 】。 ( 6 ) 确定地理区域 给定的w e b 网页是局部地区的还是全国的，抑或是全世界范围内的人对其 感兴趣。通过对超链分析可以得出该网页的兴趣覆盖范围1 2 2 1 。这个信息可以帮 助搜索引擎根据用户所在地区来裁减检索结果。 ( 7 ) 识别社区 1 4 硕士学位论文第三章w e b 结构挖掘的相关算法理论 在网络上有许多在线的由某些有共同兴趣的人创建、维护、使用的网页，这 些网页