（计算机软件与理论专业论文）基于超链接的web结构挖掘算法的研究.pdf

摘要 近年米，随着i n t e m e “、e b 技术的快速普及和迅猛发展，其为人们提供了丰富的信息资源 的同时，它所具有的海量数据、复杂性、极强的动态性和州户的多态性等特点也给w e b 资源 的发 6 | 造成了相当的难度。因此将数据挖掘技术和w e b 结合起来，进行w 曲数据挖掘也就 随之成为了解决w 曲挖掘问题的重要途径。 本文通过对经典的、b 结构挖掘算法h j t s 和p a 譬e r a n k 的研究学习，针对h i t s 算法中 完全只考虑w e b 页面之间的超链接分析而忽略的w e b 页面的内容，从而导致分析结果出现主 题偏移平种种的不足，提出了一种结合超链接分析和内容相关性分析的关丁h i t s 的改进算法， 该算法通过对不同w e b 页面进行内容分析并赋予链接之间不同的权重来实现对h i t s 的故进， 并最终通过实验证明该新算法的有效性。最后我们还针对h i t s 算法和p a g e r a n k 算法中住对 页面1 了点进行排序时存在将页面权威性与枢纽性完全分开或忽视了页面的枢纽性，造成信息 的丢失等问题，通过重新殴定p a g e r k 算法中的个性化矢耸冈子e ，探讨建立住此基础上的 h u b r a n k 算法并通过实验验证了该算法对该问题的有效性。 关键宇：w e b 结构挖掘 超链接h sp a g e r a k a b s t r a c t r e c e n t l xa l o n gw i t h t h eq u i c kp o p u i a r i z a t i o na n dd e v e l o p m e n to ft h ei n t e m e ta n dw e b t e c h n o i o g y ，i ts u p p l i e sp e o p l ew i t ha b u n d a n ti n f o r m a t i o n b u tt h ev a s tc o m p l j c a 靶da n dd y n a m i c i n t e r n e ti n f o r m a t i o na l s om a k ei tv e r yd i f f j c u l tf o rp e o p l et om i n et h ew 曲r e s o u r c e s oi tj sav e r y i m p o n a n tm e t h o d 协j m p l e m e n tw e bd a t am i n i n gb yc o m b j n i n gt r a d i t i o n a id a t am i n i n gt e c h n o i o g y a n d w 曲 b ys t u d y n gt h ec l a s s i c a lw e bs t r u c t u r em i n i n ga l g o r i t h mh i t sa n dp a g e r a n ka n dc o n s i d e r i n g t h a tt h eh i t so n l yc a l c u i a l e st h eh y p e r l j n ka m o n gt h ew e ba n dj g n o r e st h ec o n i e n to fw e br e s u l t i n t h ed r a w b a c ko ft o p i cd “凡w ep r o p o s ea ni m p r o v e dh 1 t sa i g o r i t h mt h a tc o m b i n e sh y p e r l i n k a n a l y s i sa n dc o n t e n ta n a l y s i s t h en e wa l g o r i t h mi m p r o v e st h eh i t sb ya n a i y z i n gt h ec o n t e n to ft h e w e ba n dg i v i n gt h eh y p e i n k sw i t hd f e r e n tw e i g h t a n de x p e m e n tp r o v e st h en e wa i g o r i t h m e 何色c “v e f i n a y f o rt 1 ea i g o r i t h mh i t sa n dp a g e r a l l kw i l is e p a r a t et h ep a g e l sa u t h o t yf 如mi h e p a g e sh u bo re v e ni g n o r et h ep a g e sh u b ，w ed l s c u s s 也ep e r s o n a l i z e dp a g e r a n kv e c t o ra n dt h e a i g o r i t h mh u b r a n kb a s e do np a g e r a n k a n di h ee x p e r i m e n tn n a l l yp m v et h eh u b r a n ki se h b c t i v e t ol h eo r o b l e m k e y w o r d ： w e bs t r u c t u r em i n i n g h y p e r h n k h i t s p a g e r a n k 创新性声明 y 8 5 8 9 7 9 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保管的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：扫盔签型 导师签名：! 霾丛生 日期加耐( 灯 日期垫! 垒【堕 第一章绪论 第一章绪论 1 1 研究背景 1 9 9 1 年，c e r n ( 欧洲粒子物理研究所) 的科学家提姆伯纳斯李( t i m b e m e r s - l e e ) 开发了万维网( w o r l d w i d e w e b ，简记w w w 或w e b ) ，全面启动了今同 的互联网浪潮。由于它的开放性和其上信息广泛的可访问性极大鼓励了人们创作 的积极性，并迅速在社会大众中得到普及。作为一个信息源，w e b 和传统的全文 检索系统工作对象( 一般为图书和文献) 相比，具有许多不同的特征【1 7 】： 规模大。在短短的十多年左右的时间，人类至少产生了8 0 亿网页 ( g o o g i e ，2 0 0 5 ) ，而人类有文字以来的上万年里产生了大约1 亿本书；中国互联网上 到2 0 0 5 年初大致有1 0 亿网页( 天网，2 0 0 5 ) ，而中华民族有史以来出版的书籍大约 不过2 7 5 万种。尽管书籍的内容和质量是一般网页不可比的，但在对应的时间背 景上考察其文字的总体数量，我们不能不为人类在w e b 上创造文字的激情惊叹。 内容不稳定。除了不断有新的网页出现外，旧的网页也可能会因为各种原因 删除( 有研究指出：5 0 网页的平均生命周期大约为5 0 天) 。 从原则上讲，读者数和作者数在同一个量级，形式和内容的随意性很强，权 威性也相对不高，也不大可能进行人工筛选和预处理。 与生俱来的数字化，网络化。传统载体上的信息，人们目前正在忙于将它们 数字化、上网( 花费极高) ，而网络信息天生如此。这个特性是一把双刃剑：一 方面便于我们搜集和处理，另一方面也会使我们感到太多，蜂拥而至，鱼目混珠。 随着万维网的飞速发展，w e b 的数量正在一直以指数的速度在增长，加上 w e b 具有的上述特征，要想在这数量庞大的w e b 中快速提取出各自需要的信息 成为人们面临的大难题，也给信息检索领域带来了新的发展机遇和技术挑战。 信息检索界开发了许多搜索引擎，但其覆盖率有限，因此查全率低。传统的w e b 搜索引擎大多是采用基于关键字文本匹配算法，返回的结果是查询项的文档，也 有基于目录分类的搜索弓l 擎。这些搜索引擎的结果并不令人满意。有的站点还可 以在页面中隐性的提高关键字出现的频率来提高自身在搜索引擎中的重要性，破 坏了搜索结果的客观性和准确性。另外不能针对特定的用户给出特殊的服务，因 为每个人感兴趣的东西是不一样的，因此不具有个性化。 而近些年来兴起与发展的数据挖掘技术为以上问题的解决带来了契机。数据 挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者。尤其是数据库、人工 智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。根掘 w j f r a w i e y 和g p s h 印i r o 等人的定义，数据挖掘是指从大型数据库的数据中提 取人们感兴趣的知识，而这些知识是隐含的、事先未知的、潜在的有用信息。原 始数据可以是结构化的，如关系型数据库中的数据；也可以是半结构化的，如文 本、图形、图像数据；甚至是分布在网络上的异构型数据。数据挖掘的方法可以 是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。挖掘出来的信 息可以被用于信息管理、决策支持、过程控制等，还可用于数据自身的维护。因 此，将传统的数据挖掘技术跟w e b 结合起来，进行w e b 数据挖掘成为了网络信 息挖掘问题的重要途径。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信 息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计 学、人工智能中的机器学习和神经网络等。 出于w w w 的迅猛发展和快速普及，w e b 上蕴藏的海量信息位数据挖掘提供 了无比丰富的资源，然而从以下的分析可以看出，对w e b 信息进行有效的知识发 现具有极大的挑战性。”j 1 对有效的数据仓库和数据挖掘而言，w e b 似乎太庞大了。w e b 的数据量目 前以兆兆字节( t e r a b ”e s ) 计算，而且仍然在迅速地增长。许多机构和社团都在把 各自大量的可访问信息置于网上。这使得几乎不可能去构造一个数据仓库来复制、 存储或集成w e b 上的所有数据。 2 w e b 页面的复杂性高于任何传统的文本文档。w e b 页面缺乏统一的结构， 它包含了远比任何一组书籍或其它文本文档多的多的风格和内容。w 曲可以看作 一个巨大的数字图书馆。然而，这一图书馆中的大量文档并不是根据任何有关的 排列次序加以组织的。它没有分类索引，更没有按标题、作者、扉页、且次等的 索引。在这样一个图书馆中搜索希望得到的信息是极具挑战性的。 3 w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信 息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务中心都在不断 的更新着自己的页面。链接信息和访问纪录也在不断频繁的更新当中。 4 w e b 面对的是一个广泛的形形色色的用户群体。目前因特网上连接约有 5 0 0 0 万台工作站，其用户群仍在不断地扩展当中。各个用户可以有不同的背景、 兴趣和使用目的。大部分用户并不了解信息网络结构，不清楚搜索的高昂代价， 极容易在“黑暗”的网络中迷失方向，也极容易在“跳跃式”访问中烦乱不已和 在等待信息中失去耐心。 5 w e b 上的信息只有很小的一部分是相关的或有用的。据说9 9 的w e b 信 息相对9 9 的用户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上的很小一部分信息确实是事实，w e b 所包含的其余信息对用户来说是不感兴趣 的，而且会淹没所希望得到的搜索结果。 第一章绪论 这些挑战已经推动了如何高效且有效地发现和利用因特网上资源的研究工 作。w e b 挖掘是一个更具挑战性的课题，它能实现对、v e b 存取模式、w e b 结构、 规则和动态的w e b 内容的查找。 1 2 研究内容及国内外研究现状 w e b 结构挖掘是w e b 数据挖掘的一个重要方面，其重点在于信息检索。虽 然随着万维网规模上的迅速增长，其复杂性也大大的增加，以致于我们己经无法 继续掌握其全貌。然而，在一些较小的、本地的领域里，w e b 表现的仍然是有序 的、结构化的，因为网页间的超链接结构是建立在人们努力进行注释的基础上的。 w e b 网页的作者往往会在其网页中添加指向相关主题网页的链接。通过利用这些 链接信息，就可以针对某一主题对网页进行提取和分组。搜索引擎可以帮助人们 尽快地找到所需要的信息，但是目前多数搜索引擎是基于分类或关键词逻辑组配 的检索方式，用户的一个查询请求往往会检索出庞大的结果集，而用户所需要的 信息却只是其中一小部分，面对如此多的结果，用户仍然不知所措，因此，如何 提供一些有效的工具和方法，帮助人们高效地获取所需信息，搜索所需领域的权 威网页成为研究者们所面临的重大课题。 为了迅速自动检索出对用户有价值的权威w e b 页面，首先必须对网页价值进 行合理的评估。研究发现，w e b 页面之间的超链接对于w e b 信息检索来说是一个 可利用的重要资源，如能充分利用，可以大大提高、e b 搜索的结果。目前根据这 种超链接分析的思想，对网络的组织结构和链接关系进行挖掘的主要算法有两种： 一是由l a r r y p a g e 和s e r g e y b f i n 于1 9 9 8 年提出的p a g e r a i l k 【l 】算法；二是在1 9 9 8 年由j 烈e i n b e 娼提出的经典的主题提取算法h i t s 团( h y p e r l i n k i n d u c e dt 0 p i c s e a r c h ) 。这两种算法目前研究最为广泛，并在实践中得到良好应用。其中p a g e r a n k 成为g o o g l e 搜索引擎的重要部分，取得了重大的成功，h i t s 算法也成功应用于 i b m 的c l e v e r 系统。世界上还有许多的科研团体和个人在这领域进行广泛的研究 和新的尝试，【3 】中作者将w e b 结构分析与随机取样的方法结合起来挖掘、e b 信息， 【4 】中作者则侧重于从、e b 的童曲值挖掘入手来搜索人们需要的w e b 信息，【5 ，6 】 都更多的通过发掘w e b 之间的链接关系来提高搜索精度。t 。 本文的研究都是在p a g e 胁k 算法和h i t s 算法的基础上进行的。 1 在 t s 算法中，e 曲e r g 认为页面的重要性应该建立在用户查询条件的基 础上，每一页面都分别有a u t h o 曲值和h u b 值。通常h u b 值好的页面是指向许多好 的权威页面；：好的权威是指由许多好的h u b 所指向的页面。这种h u b 和a u t l l o r i 够之 间的相互作用可用于权威页面的挖掘和高质量w e b 结构和资源的自动发现，这就是 h i t s 算法的基本思想。由于h i t s 完全建立在分析超链接的基础上，忽视了文档内 容的相关性，往往会导致主题偏移( t o p i c 出j 聊7 1 。本文在h i t s 的基础上对该算法 作出了改进，提出了w 瑚t s 算法。新算法通过对网页( 特别是h t m l 文档) 内容和 结构的分析和计算，给每个网页赋予一定的权值，再将其综合应用到超链接的迭 代运算中，以获得更好的返回结果。 2 p a g e r a n k 算法是最早利用页面间的链接信息来进行w e b 结构挖掘的算法， 其基本思想如下：一个页面被多次引用则这个页面很可能是重要的；一个页面 尽管没有被别的页面多次引用，但被一个重要页面引用，则这个页面很可能是重 要的：一个页面的重要性被均分并被传递到它所引用的页面。设页面f 的链入集 合为( t 1 ，t 2 ，t n ，c ( i ) 为f 的链出页面数，则页面f 的p a g e r a n k 值p r ( i ) 可以 通过以下的计算可以得出： p r ( i ) = 1 - d + d + ( p r ( t 1 ) c ( t 1 ) + 十p r ( t n ) c ( t n ) ) ) 显然p r ( i ) 值越大，页面i 的权威性就越高。该算法与用户查询条件无关，只是给 出每个页面的等级值( p a g e r a l l k 值) ，等级值越高，页面的排序就越靠前。在我们 的研究实验中，我们将借鉴h i t s 算法中h u b 页面的概念，在p a g e r 丑i l k 算法的基 础上，将每个页面的p a g e k 值不但考虑到页面的a i i _ m o r i t y 值，还考虑到页面 的h u b 值。我们将这个修改后的算法称为h u b m m k 【4 】算法。 1 3 本文组织结构 本文的研究工作都是围绕着h i t s 算法和p a g e r a n k 算法来进行的，这两个算 法都是属于w e b 数据挖掘中的w 曲结构挖掘，具体组织结构如下： 第一章绪论，介绍本文的研究背景，关于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 结构挖掘中的两个主要算法 h f t s 和p a g e r a n k 进行详细的描述。首先我们介绍了这两种算法的发展历史，应 用背景及研究现状，然后对这两种算法进行具体的描述，并分别分析和比较了这 两种算法各自的特点。 第四章w e b 结构挖掘算法的改进，从h i t s 算法存在的优缺点出发。我们作 出对h i t s 算法的改进，提出w e i g h t e d h i t s 算法，并对修改后的算法进行实验验 证，并对实验结果进行分析总结；并根据对p a g e r a i l l ( 算法的特点，对其进行修 改，形成p a g e r a t l k 的另外一个版本h u b r a n k 。 第五章总结，对本文所做的工作进行总结，分析了工作中存在的不足和问题， 第一章绪论 并提出下一步的研究和工作方向。 第二章w e b 数据挖掘概述 第二章w e b 数据挖掘概述 2 1w 曲数据挖掘概述 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的应 用使海量数据不断产生。随之而来的问题是如此多的数据让人难以消化，无法 从表面上看出他们所蕴涵的有用信息，更不用说有效地指导进一步的工作。如何 从大量的数据中找到真i e 有用的信息成为人们关注的焦点，数据挖掘技术也正是 伴随着这种需求从研究走向应用。 近年来，随着i n t e m e t w e b 技术的快速普及和迅猛发展，使各种信息可以以 非常低的成本在网络上获得，由于i m e m e t w w w 在全球互连互通，可以从中取 得的数据量难以计算，而且i m e m e 侧w w 的发展趋势继续看好，特别是电子商 务的蓬勃发展为网络应用提供了强大支持，如何在w w w 这个全球最大的数据集 合中发现有用信息无疑将成为数据挖掘研究的热点。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信 息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计 学、人工智能中的机器学习和神经网络等。 2 2 w 曲数据挖掘的分类 w e b 数据挖掘一般指的是三种完全不同的行为，所有的这些行为都有数据挖 掘的特性并且都被包括在网络中，但是就像数据挖掘的动机不同一样，实际被挖 掘的数据也是不同的。根据挖掘对象的不同，我们将w e b 数据挖掘分为w e b 内 容挖掘( w e bc o n t c mm i n i n g ) 、w e b 结构挖掘( w e bs t m c t u r em i i l i n g ) 、w e b 使用挖掘 ( w e b 、l s a g em i n i n g ) 三大类【1 4 j 。图2 1 给出了w e b 数据挖掘的分类图。 一、w e b 内容挖掘 即从网络的内容数据文档中发现有用信息的过程。网络信息资源类型众多， 从网络信息源的角度看，大量的网络信息资源可以直接从网上抓取、建立索引、 实现检索服务，但是还有一些网络信息是“隐藏”的，如由用户的提问而动态生成 的结果，或是存在d b m s 中的数据，或是那些私人数据，它们无法被索引，从而 无法提供对它们有效的检索方式；从资源形式看，网络信息内容是由文本、图像、 音频、视频、元数据等形式的数据组成的，因此网络内容挖掘是一种多媒体数据 挖掘形式。 ! 基于超链接的w e b 结构挖掘算法的研究 。可 匝圃 幽2 1w e b 数据挖掘分类圈 二、w e b 结构挖掘 即挖掘w e b 潜在的链接结构模式。这种思想源于引文分析，即通过分析一个 网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。可以用于网页 归类，并且可以由此获得有关不同网页间相似度及关联度的信息，有助于用户找 到相关主题的权威站点。 三、w e b 使用挖掘 通过网络用法挖掘，可以了解用户的网络行为数据所具有的意义。网络内容 挖掘、网络结构挖掘的对象是网上的原始数据，而网络用法挖掘则面对的是在用 户和网络交互的过程中抽取出来的第二手数据。这些数据包括：网络服务器访问 记录、代理服务器日志记录、浏览器日志记录、用户简介、注册信息、用户对话 或交易信息、用户提问式等等。分析这些数据可以帮助理解用户的行为，从而改 进站点的结构，或为用户提供个性化的服务。 2 3w 曲内容挖掘 指从w e b 内容，数据文档中发现有用信息，w e b 上的信息五花八门，传统的 i n t e m e t 由各种类型的服务和数据源组成，包括w w w 、f t p 、t e l n e t 等，现在有 更多的数据和端口可以使用，比如政府信息服务、数字图书馆、电子商务数据， 以及其他各种通过w e b 可以访问的数据库。w e b 内容挖掘的对象包括文本、图 像、音频、视频、多媒体和其他各种类型的数据。其中针对无结构化文本进行的 w c b 挖掘被归类到基于文本的知识发现( k d t ) 领域，也称文本数据挖掘或文本 挖掘，是w e b 挖掘中比较重要的技术领域，也引起了许多研究者的关注。最近在 w e b 多媒体数据挖掘方面的研究成为另一个热点。 w e b 内容挖掘一般从两个不同的观点来进行研究。从资源查找( i r ) 的观点 来看，w e b 内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助用户 第二章w e b 数据挖掘概述 过滤信息。而从数据库( d b ) 的角度讲w e b 内容挖掘的任务主要是试图对w e b 上的数据进行集成、建模，以支持对w e b 数据的复杂查询。 2 3 1 从资源查找的观点挖掘非结构化文档 9 非结构化文档主要指w e b 上的自由文本，包括小说、新闻等。在这方面的研 究相对比较多一些，大部分研究都是建立在词汇袋( b a go f w o r d s ) 或称向量表示法 ( v e c t o rr e p r e s e n t a t i o n ) 的基础上，这种方法将单个的词汇看成文档集合中的属性， 只从统计的角度将词汇孤立地看待而忽略该词汇出现的位置和上下文环境。属性 可以是布尔型，根据词汇是否在文档中出现而定，也可以有频度，即该词汇在文 档中的出现频率。这种方法可以扩展为选择终结符、标点符号、不常用词汇的属 性作为考察集合。词汇袋方法的一个弊端是自由文本中的数据丰富，词汇量非常 大，处理起来很困难，为解决这个问题人们做了相应的研究，采取了不同技术， 如信息增益，交叉熵、差异比等，其目的都是为了减少属性。另外，一个比较有 意义的方法是潜在语义索引( l a t e n ts e m a n t i ci i l d e x i n g ) ，它通过分析不同文档中相 同主题的共享词汇，找到他们共同的根，用这个公共的根代替所有词汇，以此来 减少维空间。例如：“曲肌i n g ”、 “i r 岣珊砒i o n ”、“i n f o m 瑚”、“i r 曲n n e d ” 可以用他们的根“m f 0 n ”来表示，这样可以减少属性集合的规模。 其他的属性表示法还有词汇在文档中的出现位置、层次关系、使用短语、使 用术语、命名实体等，目前还没有研究表明一种表示法明显优于另一种。 用资源查找( i n f o 衄a t i o nr e t r i e v a l ) 的观点挖掘半结构化文档： 与非结构化数据相比，w e b 上的半结构化文档挖掘指在加入了h t m l 、超连 接等附加结构的信息上进行挖掘，其应用包括超连接文本的分类、聚类、发现文 档之间的关系、提出半结构化文档中的模式和规则等。 2 3 2 从数据库的观点挖掘非结构化文档 数据库技术应用于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 知识库或虚拟数据库来实现。相关 研究主要是基于半结构化数据进行的。 数据库观点主要利用0 e m ( o b j e c te x c h a i l g em o d e i ) 模型将半结构化数据表示 竺董三塑壁堡堕竖里壁丝垫塑蔓鎏盟婴塞 成标识图。o e m 中的每个对象都有对象标识( o i d ) 和值，值可以是原子类型，如 整型、字符串型，g i f 、h t m l 等，也可以是个复合类型，以对象引用集合的形式 表示。由于w e b 数据量非常庞大，从应用的角度考虑，很多研究只处理办结构化 数据的一个常用自集。一些有意义的应用是建立多层数据库( m l d b ) ，每一层是 它下面层次的概化，这样就可以进行一些特殊的查询和信息处理。对于在半结构 化数据上的查询语言研究也得到了人们的重视并做了专题研究。 由于在数据库观点下数据的表示方法比较特殊，其中包含了关系层次和图形 化的数据，所以大部分建立在扁平数据集合之上的数据挖掘方法不能直接使用， 目前已经有人针对多层数据库挖掘算法进行研究。 2 4w 曲结构挖掘 w e b 结构挖掘的对象是w e b 本身的超连接，即对w e b 文档的结构进行挖掘。 对于给定的w e b 文档集合，应该能够通过算法发现他们之间连接情况的有用信 息，文档之间的超连接反映了文档之间的包含、引用或者从属关系，引用文档对 被引用文档的说明往往更客观、更概括、更准确。 w e b 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之间 的关系分为i n c o m i n g 连接和o u t g o i n g 连接，运用引用分析方法找到同一网站内部 以及不同网站之间的连接关系。在w e b 结构挖掘领域最著名的算法是h i t s 算法 和p a g e r a n k 算法。他们的共同点是使用一定方法计算w e b 页面之间超连接的质 量，从而得到页面的权重。著名的c l e v e r 和g o 0 9 1 e 搜索引擎就采用了该类算法。 此外，w e b 结构挖掘另一个尝试是在w e b 数据仓库环境下的挖掘，包括通 过检查同一台服务器上的本地连接衡量w e b 结构挖掘w c b 站点的完全性，在不 同的w e b 数据仓库中检查副本以帮助定位镜像站点，通过发现针对某一特定领域 超连接的层次属性去探索信息流动如何影响w e b 站点的设计。 h i t s 算法和p a g e r a n k 算法是本文研究的重点，在后续几章我们会对这两个算 法进行详细的讨论和研究，在这里就进行过多的叙述。 2 5w 曲使用挖掘 即w e b 使用记录挖掘，在新兴的电子商务领域有重要意义，它通过挖掘相关 的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析日志记录中的规 律，可以识别用户的忠实度、喜好、+ 满意度，可以发现潜在用户，增强站点的服 务竞争力。w e b 使用记录数据除了服务器的日志记录外还包括代理服务器日志、 浏览器端日志、注册信息、用户会话信息、交易信息、c o o 姑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 用法挖掘分为五类： 1 、个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本 信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众 不同的个性化服务。 2 、系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量 用户满意度的关键指标，w e b 用法挖掘可以通过用户的拥塞记录发现站点的性能 瓶颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机制 和数据的分布策略。此外，可以通过分折网络的非法入侵数据找到系统弱点，提 高站点安全性，这在电子商务环境下尤为重要。 3 、站点修改：站点的结构和内容是吸引用户的关键。w e b 用法挖掘通过挖 掘用户的行为记录和反馈情况为站点设计者提供改进的依，比如页面连接情况应 如何组织、那些页面应能够直接访问等。 4 、智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的 重点，用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 用 法挖掘可以通过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销 售商合理安排销售策略。 5 、w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各 个用户在页面上的交互情况，对用户访问情况进行特征描述。 2 6w 曲数据挖掘步骤 与传统数据和数据仓库相比，w 曲上的信息是非结构化或半结构化的、动态 的、并且是容易造成混淆的，所以很难直接以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 文档中自动去除广告连接、去除多余格式标记、自 动识别段落或者字段并将数据组织成规整的逻辑形式甚至是关系表。 3 、 模式发现：自动进行模式发现。可以在同一个站点内部或在多个站点之 间进行。 4 、 模式分析：验证、解释上一步骤产生的模式。可以是机器自动完成，也 可以是与分析人员进行交互来完成。 w e b 挖掘作为一个完整的技术体系，在进行挖掘之前的信息获得 i r ( i n f o m a t i o nr e 啊“a 1 ) 和信息抽取i e ( i n f o 蚰a t i o ne x t r a c t i o n ) 相当重要。信息获得 ( i r ) 的目的在于找到相关、b 文档，它只是把文档中的数据看成未经排序的词组 的集合，而信息抽取( i e ) 的目的在于从文档中找到需要的数据项目，它对文档的 结构和表达的含义感兴趣，它的一个重要任务就是对数据进行组织整理并适当建 立索引。 信息获得( i r ) 和信息抽取( i e ) 技术的研究已近有很长时间，随着w e b 技术的 发展，基于w e b 技术的承、i e 得到了更多的重视。由于w e b 数据量非常大，而 且可能动态变化，用原来手工方式进行信息收集早已经力不从心，目前的研究方 向是用自动化、半自动化的方法在w e b 上进行i r 和i e 。在w e b 环境下既要处理 非结构化文档，又要处理半结构化的数据，最近几年在这两方面部有相应的研究 成果和具体应用，特别是在大型搜索引擎中得到了很好的应用。 2 7w 曲数据挖掘的应用前景 网络信息挖掘已广泛地应用于金融业、零售业、远程通讯业、政府管理、制 造业、医疗服务以及体育事业中，对它的应用和研究正在成为一个热点。网络信 息挖掘的应用前景主要表现在三个方面：电子商务。运用网络挖掘技术能够从 服务器和浏览器端的日志记录中自动发现隐藏在数据中的模式信息，了解系统的 访问模式以及用户的行为模式。从而做出预测性分析。例如通过评价用户对某一 信息资源浏览所花的时间，可以判断出用户对资源兴趣如何；对日志文件所收集 到的域名数据，如国家或类型( c o m ，e “，g o v ) 的分类分析；应用聚类分析来识 别用户的访问动机和访问趋势等。网站设计。通过对网站内容的挖掘，可以有 效地组织网站信息，例如采用自动归类技术实现网站信息的层次性组织：通过对 用户访问r 志记录信息的挖掘，把握用户的兴趣，有助于开展网站信息推送服务 第二章w e b 数据挖掘概述 以及个人信息的定制服务。搜索引擎。用搜索引擎进行网络信息挖掘的最大特 色体现在它所采用的对网页l i n k s 信息的挖掘技术上。如通过对网页内容挖掘， 可以实现对网页的聚类、分类，实现网络信息的分类浏览与检索；通过用户所使 用的提问式的历史记录的分析，可以有效地进行提问扩展，提高用户的检索效果； 运用网络内容挖掘技术改进关键词加权算法，提高网络信息的标引准确度，从而 改善检索效果。 上面仅仅列举了网络信息挖掘技术在这三个方面的应用。这项技术的应用正 变得越来越广泛；用户对高品质、个性化的信息的需求必将推动学术界与实业界 的研究开发工作。 面向w e b 的数据挖掘是一项复杂的技术，由于w e b 数据挖掘比单个数据仓 库的挖掘要复杂的多。我们相信，随着x m l 作为在w e b 上交换数据的一种标准 方式的出现、用户信息需求的多样化、网络信息挖掘研究的不断深入，“智能化” 的搜索引擎将会涌现，面向w e b 的网络信息挖掘也将会变得非常轻松。 第三章w e b 结构挖掘算法 第三章w e b 结构挖掘算法 w e b 结构挖掘是针对w e b 页面之间的超链接结构、内部结构、和u r l 中的 目录路径结构进行挖掘，从中抽取知识，获取权威页面。而在w c b 结构挖掘领域 最著名的算法是h i t s 算法和p a g e r a n k 算法。 3 1 1 引言 3 1 t s 算法 一、w e b 的链接结构与链接分析 w w w 是一个超文本集合，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 之间根据某个主题或页面内容，自组织性的聚集在一起形成一个群 落m ，1 2 】( c o m m u l l i t y ) ，在群落里面，w e b 之间的联系紧密，而群落之间则联系稀疏。 在每个群落中都存在两种不同页面：a u t h o r i t y 和h u b 甜。e i n b e r g 认为一个好的 h u b 就是一个文档，它自身包含着许多指向其他相关页面的超链接；而一个好的 a u t h o r 时就是有许多页面指向它的优质文档。a u t h o 嘶和h u b 之间呈现出相互增 强的关系，好的a u t h o r i t y 必定有很多好的h u b 指向它，而好的h u b 也必定指向许 多好的au _ m o r 时。h i t s 算法的实质就是通过挖掘w e b 之间的链接关系，计算出 在这w e b 集合中具有最高的值的a u t h o 衄，这就是人们查询相关主题最关心的页 面。 w e b 的这种自组织性为链接分析提供了依据，链接分析基于以下一个或两个 简单的假设【2 l ： l 、页面a 到页面b 的一条超链接，是页面a 的作者对页面b 的一种推荐和 赞赏，意味着权威性或质量。 2 、若页面a 与页面b 之间存在着一条超链接，则他们可能有相同或相近的 主题，意味着相关性。 二、主题精选 我们认为搜索是从用户提供的一个查询开始的，一般来晚，用户提供的查询 些基于超链接的w e b 结构挖掘算法的研究 可以分为这三类： l 、具体查询。比如，“卜f e t s c a p e 是否支持j d k l 1 编程接口? ” 2 、宽主题查询。比如，“查找一些跟搜索引擎相关的信息资料。” 3 、相似页面查询。比如，“查找一些跟x i d i a n e d u c n 相关的页面。” 可以看出，宽主题查询【2 】就是用户向检索服务系统提供一个主题语意不太明确或 概念范畴太大的查询( 一般包括1 3 个关键字) 而进行的搜索，而w e b 上大多数的 用户查询都属于宽主题查询。与具体查询可能面对资源稀缺的问题相反，宽主题 查询则主要面对的是信息资源过剩的问题。这是由于面对宽主题查询，搜索系统 常常返回一个按相关度排序的庞大的结果清单，这对于一般用户来说是无法消化 的，更别说从中挑选出少量高质量的权威信息源。而问题的根源是传统w e b 检索 系统的评分排序算法主要采用经典信息检索技术中基于内容分析的相关性度量而 并无关于信息源权威性的质量度量。因此需要一个质量度量的信息在过滤过程一 主题精选( t o p i cd i s t i l l a t i o n ) 。 所谓主题精选，就是给定一个宽主题查询，检索系统找到与查询主题相关的 少量高质量权威信息源的过程。其本质是试图从大量的质量评判主观意见中找到 一致公认的客观评判结论；其目标是找到与用户查询主题相关，且权威的高质量 信息源。 三、主题精选算法 主题精选利用某一个搜索引擎的爬行器和文档的索引结构，是搜索结构返回 用户前的一个后台处理操作。一个主题精选算法首勺输入是：从一个搜索引擎爬行 到的相关文档集合中经超链接扩展得到的文档基集( b a s es e t ) 诱导出的w e b 邻接图 ( n e i g h b o r l l o o d 伊a p h ) ；主题精选算法的输出是相关用户查询的质量最好的权威文 档的列表。而h i t s 及h i t s 算法的改进算法就是属于主题精选算法，下面的一节， 我们将对h i t s 的思想和原理进行详细的介绍。 3 1 2 算法原理 h i t s 算法通过挖掘w e b 链接结构，分析w e b 间的链接关系，找出w e b 集 合中的a u t l l o r i t i e s 和h u b s 。a u t l l o r i t i e s 是那些与给定查询主题的上下文最为相关 并具有权威性的网页，这也是人们对于宽主题查询最关心的网页；而h u b s 则是那 些本身的内容虽然未必具有权威性、但却包含了多个指向a u t h 删t i e s 的超链接的 网页。对于大部分主题来说，最为有力的a u t l l o r i t i e s ，即最权威的网页，它们之间 往往不存在任何链接，因此它们常常只被些作为它们之间的中间层的、相对而 言不怎么h u b s 网页所链接。那么如何确定网页的a u t h o r i t y 值和h u b 值呢，h i t s 算法主要通过两大步骤：l 、w e b 邻接图的构造；2 、链接分析与a u t h o r i t y 值和h u b 第三章w e b 结构挖掘算法 1 7 值的计算。 一