（电路与系统专业论文）基于XML的Web挖掘[电路与系统专业优秀论文].pdf

摘要 随着i n t e rn e t 的飞速发展，它成为了迄今为止最密集、最丰富的信息来源。那么从 这些海量数据中找到使用者感兴趣的信息逐渐成为人们关注的焦点。作为从 w e b文档 和 w e b活动中抽取感兴趣的潜在的有用模式和隐藏信息的有效技术，we b挖掘悄然兴 起，备受关注。而 x ml由于具有可扩展性、结构化和有效性等特性，建立了一种传输 结构化数据的方法，从而使用户能够对w e b 信息实施精确查询与模型抽取。因此x ml 与w e b 挖掘的结合将在数据挖掘领域内进行的研究推向了一个新的高潮。 本文首先从w e b 挖掘研究背景入手，介绍了数据挖掘相关概念，相比h t m l而言 x m l在we b 挖掘应用中的优越性， 以及w e b 挖掘的内涵和复杂性分析， we b 挖掘原理、 特点、分类等等。 接着， 阐述了如何实现w e b内容挖掘的问 题。 提出了使用标准w e b 技术h t ml , 半结构化数据模型、x ml , j a v a - 开发的一种基于 w e b的数据挖掘方法。利用对象 交换模型o e m将w e b 页转换为x ml 文档，然后用j a v a 实现从x ml文档中抽取感兴 趣的信息。 通过选择可靠的数据源以及在这些数据源中选取与内容相关但与格式无关的 引用点，可以实现数据抽取的任务。 最后讨论了结构化信息的挖掘。 使用有序树作为数据模型， 提供一种从有序树中挖 掘频繁引导子树的方法，帮助人们更有效的获取we b 上的信息。 关键词:we b 挖掘;x ml ;挖掘结构化数据 ab s t r a c t b y r a p i d p r o g r e s s o f i n t e rn e t , i t h a s b e e n t h e d e n s e s t a n d a b u n d a n t i n f o r m a t i o n s o u r c e . t h e n f i n d i n g t h e i n f o r m a t i o n fr o m l a r g e d a t a t h a t t h e u s e r s c a n b e i n t e r e s t e d i n h a s b e e n a t t r a c t i n g m o r e a n d m o r e a tt e n t i o n . we b m i n i n g i s a n e ff e c t i v e t e c h n o l o g y o f e x t r a c t i n g u s e f u l p a tt e rn s a n d i n f o r m a t i o n . x ml c a n t r a n s p o r t s t r u c t u r a l d a t a b e c a u s e i t i s e x t e n s i b l e , s t r u c t u r a l , e ff e c t iv e . s o t h e c o m b i n a t i o n o f x ml a n d w e b m i n i n g h a s b e e n t h e s o l u t i o n o f e x t r a c t i n g i n f o r m a t i o n . f i r s t , w e s t a rt w i t h t h e s t u d y i n g b a c k g r o u n d o f w e b m i n i n g a n d i n t r o d u c e t h e c o r r e s p o n d i n g c o n c e p t i o n o f d a t a m i n i n g a n d w e b m i n i n g . w e a l s o p r e s e n t t h a t x m l i s s u p e r i o r t o h t ml s e c o n d , we e x p a t i a t e h o w t o i m p l e m e n t w e b c o n t e n t m i n i n g a n d d e v e l o p a w e b m i n i n g t e c h n o l o g y b a s e d o n h t ml , s e m i - s t r u c t u re d d a t a m o d e l , x ml , j a v a . we t r a n s f o r m w e b p a g e t o x ml d o c u m e n t a n d e x t r a c t u s e f u l in f o r m a t i o n fr o m x ml b y s e l e c t i n g r e l i a n t d a t a s o u r c e a n d a n c h o r . l a s t , w e s t u d y t h e p r o b l e m o f m i n i n g s t r u c t u r a l d a t a . w e u s e l a b e l e d , o r d e r e d t r e e s a s d a t a m o d e l a n d p r e s e n t a m e t h o d o f m i n i n g fr e q u e n t i n d u c e d s u b t r e e s fr o m o r d e r e d t r e e s t o h e l p p e o p l e a c q u i re t h e u s e f u l i n f o r m a t i o n . k e y w o r d s : m i n i n g ; x ml ; mi n i n g s t r u c t u r a l d a t a i f 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得东北师范大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示谢意口 学位论文作者签名: 于毛 日 期 : 卯o 5 s. n 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规 定，即:东北师范大学有权保留并向国家有关部门或机构送交学位论文的复 印件和磁盘，允许论文被查阅和借阅。本人授权东北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 日期:7 a o ) .c. l s 指导教师签名: 日期: 学位论文作者毕业后去向: 工作单位:东北师范大学网 络信息中心 电 话: 通讯地址:东北师范大学网 络信息中心 邮 编: 1 3 0 1 9 1 1 1 3 8 0 1 3 0 0 2 4 第一章绪论 引言 i问题的提出 当前www在深度和广度方面正飞速的发展着，,i n t e rn e t 是到目 前为止最丰富最密集 的信息来源。w e b 挖掘就是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和 隐藏的信息。 但是，www 的结构使它很难用系统的方法来利用信息。近年来，越来越多的机 构、团体和个人在 i n t e rn e t 上发布信息、查找信息。不幸的是，尽管作为信息主要载体 的 h t ml提供了一种方便地向读者呈现信息的方法，但它可能不是一个很好的可以从 中自 动抽取与数据驱动的服务或应用程序相关的信息的结构。 因为w e b 上的数据以多种 形式存在， 没有特定的模型来描述， 每一个站点上的数据都是由站点开发人员自 行设计 与组织， 并且数据本身还存在着自 我描述性和动态可变性。 人们要想找到自己想要的数 据犹如大海捞针一般。解决这些问题的一个途径，就是将传统的数据挖掘技术和 we b 结合起来，进行we b 挖掘。 面向w e b的数据挖掘要比面向单个数据库中的数据挖掘复杂得多， 传统数据库中的 数据结构性很强，其中的数据为完全结构化的数据;如果把 i n t e m e t 看成一个更大、更 复杂的数据库， 则w e b 上的数据结构不可琢磨，是一种我们称之为半结构化的数据， 所 谓半结构化是相对于结构化 ( 传统数据库) 和非结构化 ( 如一本书、一张图片等) 而台 的. 但是 i n t e r n e t 上存在的数据既不是完全结构化的也不是完全非结构化的， 因为它的页 面也具有一定的描述层次， 存在一定的结构， 所以 我们将它称为半结构化的数据。针对 i n t e rne t上的数据半结构化的特点，寻找一个半结构化的数据模型则成为了解决上述问 题的关键所在。 此外，除了要定义这样一个半结构化数据模型外， 还需要一项技术能够 自 动地从现有数据中将这个模型抽取出来， 这就是所谓的模型抽取技术。 因此半结构化 数据模型及其抽取技术是面向i n t e m e t 的数据挖掘技术实施的前提。 x ml 是由wk 定 义的一种设计标记语言 ( 如 h t ml )的规范，为目 前依然十分混乱的 h t ml世界提供 了框架结构。 其t a g具有语义，由用户定义，能够反映一定的数据的含义， 且x ml文 件描述的语义非常清晰，很容易与关系数据库的属性一一对应，因此可利用x ml 对数 据挖掘技术和i n t e rn e t 上数据结构的特征进行分析， 并把x ml作为一种半结构化的数据 模型实施查询与模型抽取。由 此可见，x ml能为w e b 挖掘带来新的解决方法。 具体做法是将整个 we b网作为一个大型的分布式的数据库系统，we b上 存在各种 各样的信息资源，如h t ml 文档、数据库、w o r d 等。由于信息来源不同，有结构化信 息， 也有半结构化信息， 因此需要采用统一的x m l 数据模型， 向 土层提供统一的x m l 文档格式的数据。 用统一的x ml 数据模型描述w e b 上各种数据的好处是为用户提供了 i 基于x m l的w e b 数据库的查询界面，使w e b上 的 数据查询和数据操作像在普通关系数 据库上的查询和操作一样方便， 使 w e b上多个数据源间交换数据更方便。并使对基于统 一的x ml模型的各种信息资源进行数据挖掘成为可能。 2本文研究思路及组织 本文并没有对数据挖掘原理和 x ml基本知识进行详细论述，只在第二章进行了简 单陈述。在第二章具体分析了将 x ml应用于 w e b 挖掘的原理而弥补了h t ml这方面 的先天不足之后，第三章介绍了 w e b挖掘的内涵及复杂性分析。接着在第四章着重进 行了基于 x ml的we b挖掘的实现工作。能够完成在获得可靠数据源的前提下的we b 内容挖掘，可帮助人们抽取对某一 w e b页上的感兴趣的信息。最后重点介绍了一个挖 掘结构化数据的方法，并进行了算法的分析与设计，给出了理论推导结果，为今后的工 作提供了一个良好的切入点。 第二章 研究背景 2 . 1数据挖掘研究综述 2 . 1 . 1数据挖掘的 提出 数据采集和存储技术的进步导致庞大的数据库日益增多。 这己经发生在人类耕耘的 几乎所有领域，从普通的 ( 比如超市业务数据、信用卡使用记录、电话呼叫清单以及政 府统计数据)到不太普通的 ( 比如天体图像、分子数据库和医疗记录) 。那么，能否从 这些数据中提取出对数据库拥有者有价值的信息呢?毫无疑问， 人们对这个问题的兴趣 在不断增长。而且己经形成了致力于这个任务的一门学科，称为 “ 数据挖掘 ( d a t a m i n i n g ) 。 数据挖掘就是对观测到的 数据集 ( 经常是很庞大的) 进行分析，目 的是发现 未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。 2 . 1 .2数据挖掘组件 通常，针对数据挖掘任务的数据挖掘算法具有以下四个基本组件: 1 .模型或模式结构:决定要从数据中寻找的潜在结构或函数形式。 2 .评分函数:鉴定一个拟合模型的质量。 3 .优化和搜索方法:优化评分函数并对不同的模型和模式结构进行搜索。 4 .数据管理策略:在搜索和优化期间高效的处理数据访问问题。 因此， 不应该把数据挖掘看作是简单的一次性操作。 对于巨大的数据集合来说， 考 察和分析它的方式是没有止境的。随着时间的推进， 新的结构和模式类型可能引起我们 的兴趣，并值得在数据中寻找它们。数据挖掘所要做的是:通过筛选数据库， 对他们进 行总结，并寻找其中的模式。将有价值的信息从包围它的大量枯燥的数据中提取出来， 从而使数据拥有者可以从中取得收益。 该模式应该是有效的、 新颖的、 潜在的、 有用的、 并最终可理解的。 其中有效性是指发现的模式对于新的数据仍保持有一定的可信度; 新 颖性要求发现的模式应该是从前未知的;潜在有用性是指发现的知识将来有实际效用， 如用于决策支持系统可提高经济效益;最终可理解性要求发现的模式能被用户理解。 2 . 1 .3数据挖掘任务 1 . 聚类分析 聚类就是把一个数据集 ( 通常是多元的)分解或划分成组，使同一组中的点彼此相 似， 但与其他组中的点尽可能不同。 概括地讲， 我们可以把聚类分析算法分成三种不同 的类型:试图找到一个最优化分以把数据分成指定数量聚类的方法; 试图发现聚类结构 的层次方法; 对潜在聚类建模的基于概率模型方法。 不同的聚类分析方法适用于探测不 同类型的聚类，选择算法时应考虑到这一点。 2 . 用于分类与回归的预测建模 预测建模的目的就是在给定其他变量的条件下对感兴趣的未知变量做出预测。 只不 过用于分类的被预测变量 ( 响应变量) 是标称型变量的预测模型- - 一 也就是他仅可以从 有限 ( 通常很少)数量的值中取值，并且这些值根本没有数值意义，如根据患者的一系 列化验结果给出它的t断或在已知顾客购买了其他商品的前提下估计出他们购买产品 a的概率; 而用于回归的预测变量具有真正的数值意义， 如正常条件下某种类型汽车的 耗油率是多少或某网站在给定时间内的用户访问量有多大等等。 3 . 数据组织 组织数据的目的就是找到一种方法来存储数据，以 使对数据子群的访问尽可能快。 不论是什么数据分析项目， 都可以将其分成两个阶段。 第一个阶段是准备分析算法所需 的数据， 第二阶段是运行分析算法。 虽然第一阶段看似不重要， 但却经常成为整个项目 的瓶颈。 例如， 要分析一个数据集， 往往有必要把算法应用到这个数据集的不同子集上。 这意味着我们必须能够迅速地搜索和标识出每个子集， 并且把这个子集装入内存。 本文 后面将详细介绍的树算法有力地证明了这一点， 在树算法中， 数据集被逐步地分割成较 小的子集，在扩展树之前必须标志出每个子集。 4 . 关联规则 关联规则是数据挖掘中用来表示局部模式的最流行方法之一。 关联规则是对数据库 中的某些特定事件一起发生的概率的简单陈述， 它尤其适用于稀疏的数据集。 这里的介 绍大体上是基于著名的a p ri o ri算法- 一 寻找关联规则的 最早算法之一。 假设所有变量 都是二值的，那么关联规则具有如下的形式: 如果a = 1并且 b = 1 那么 c = 1的 概率为p 其中a , b , c 是二值 变量， 并且p = p ( c = 1 ib = 1 , a = 1 ) ， 即 给定a = 1 及b = 1 时c = 1 的 条 件 概 率。 条 件 概率p 有时 被 称为 规 则的“ 精 度” 或“ 置 信 度” ， p ( c = 1 , b = 1 , a = 1 ) 被 称 为“ 支 持度” 。 寻找关联规则的典型目 标是寻找满足以 下约束的所有规则: 置信度p大于某个 阂 值p a ， 支持度大于某个阂值p s = 5 . 根据内容检索 这里主要讨论文本文档检索，因为它应用最广而且是这种思想的最成熟应用。 可把 这类问题归纳为三个基本组成部分: ( 1 ) 如何定义对象间的 相识尺度 ( 2 ) 如何实现高计算效率的 搜索方法 ( 3 ) 如何在检索过程中融入用户的反 馈并进行交互 在第四章对根据内容检索进行了详细讨论，并完成了一定功能。 2 . 2 x m l 技术概述 2 . 2 . 1 h t ml的缺点 h t m l 的致命弱点: 1 . h t m l 只描述了 信息的显示方式而未对信息内 容本身进行描 述。换句话说h t ml只是一种 “ 显示描述” 语言， 它只说明在w e b 的主页上应如何布 置图形、 文字和按钮， 而对信息本身的属性则未作任何说明。 2 . 大量可在客户端完成的 工作，不得不交由 we b服务器去处理，这就大大加重了网络负担，降低了网络运行的 效率。3 . h t m l 通常是一个很难用程序手段处理的媒体。 w e b 页面的大多数内容按与 数据驱动的系统无关的格式编排，并且，由于要动态添加标题以及编写其服务器脚本， 所以文档结构可能在每次连接到页面时都需要进行更改。 又因为所有 w e b页面主要部 分的格式编排不合理，所以使问题变得更为复杂，其结果是现在的 w e b浏览器在其进 行h t m l 语法分析时非常不严谨。 2 .2 . 2 x ml的描述 与h t ml不同， x ml本身并不是一个解决方案。 x ml定义了一个框架结构， 用户 可以用它来创建解决方案，但是单独的x ml本身并做不了什么。由于 x ml的承诺是 创建定制的标记集合以对特定类型的信息进行编码，因此也没有一种通用的x ml 浏览 器， 为了用一种有意义的方式浏览x ml数据， 必须描述如何表示信息。 需要注意的是， x ml关心的是结构化内容而不是显示。 x ml文件的显示通常要通过样式表来实现， 可 以 使 用x s l ( e x t e n s i b l e s t y l e s h e e t l a n g u a g e ， 可 扩展的 样式表语言 ) 或者 c s s ( c a s c a d i n g s t y l e s h e e t , 层叠样式表) . x m l 具有客户定制标记 词表， 因此x m l 使得描述数据以 及数 据片之间的关系成为可能。事实上，x ml的主要目标之一就是将we b 文件的内容 ( 数 据)和描述 ( 数据的表示形式)分割开来。 x ml不仅提供关于数据本身的信息而且侧重于提供对数据结构的描述，是标志和 描述的集合，具有自 描述性。x ml数据由嵌套和标记元素组成，标记包含对文档存储 形式和逻辑结构的描述，这种嵌套标记元素结构使x ml 很适合描述w e b 上的半结构化 数据。此外，这种标记代表数据的含义而不是显示数据结构，也使x ml可用来描述内 容而非表现形式，再加上x ml文档一般是成型的合法结构文档，使一般的应用软件能 解读他，并通过标记语言的意义对其进行特定的处理，使x ml具有良 好的可扩展性。 2 .2 . 3 x ml与h t ml的比较 h t ml文档里虽然包含了丰富的数据， 但是这些数据只能为浏览器所理解， 无法为 其他应用程序所用，导致数据的复用性很差;x ml文档里的数据则能为各种应用程序 使用、复用性很好。h t ml文档形式如下: 数据内 容 其中 规定了 放在其中的 数据内 容应该如何被显示。 支持这个 的浏览器知道对 数据内容如何处理， 而其他的应用程序就无法有效的利用这些数据， 导致数据的复用性 很差;同 时，由 于 只是 规定 数 据的 显 示方式， 所以 的 语义功能 很差， 譬 如， 标签 只是说明数据按什么字体显示，而数据的内容则既可以是标题，也可以是普 通的段落。 而x ml文档的内容与应用分开特性与数据库技术很相似，大家知道，数据 库里的数据可以为不同的应用程序所用。 不同的应用程序通过数据库接口 如o d b c等就 可以访问数据库中的数据。 数据库只描述和存放数据内容， 至于数据内容如何被应用则 由应用程序来决定。 这样， 它通过将内容与应用分开的方式使得同一数据可以 被不同的 应用所复用。x ml在这一点上采用了与数据库同样的思想。在 x ml文档里通过 d t d ( d o c u m e n t t y p e d e f i n i t i o n ， 文 档类型定义 ) 描 述了 文档里的 数据是如 何组 织存放的， 但是它不涉及这些数据应被如何应用， 比如应被怎么显示。 x ml 解析器再根据d t i 把 x ml文档中的数据解析成层次型的结构化数据。这样数据就可以被不同的应用程序根 据自己的需要加以应用。 另外，x ml应用于将大量运算负荷分布在客户端， 客户可根据自己的要求选择和制 作不同的应用程序以处理数据，而服务器只需给出同一个x ml文件。处理数据的主动 权交给了客户， 服务器所作的只是尽可能完善、 准确地将数据封装进x m l 文件中。 x m l 的自 解释性使客户端在收到数据的同时也理解数据的逻辑结构与含义， 从而使广泛、 通 用的分布式计算成为可能。 这也更有利于满足网络信息数据挖掘所强调的用户个性化需 求问题的解决。这样，大大减轻了网络负担，提高了运行效率。 2 . 3 w e b 挖掘技术 we b 数据挖掘的定义是: 针对包括w e b 页面内容、 页面之间的结构、 用户访问信息、 电子商务信息等在内的各种 w e b数据，应用数据挖掘方法以发现有用的知识来帮助人 们从w w w中提取知识，改进站点设计，更好地开展电子商务。 w e b 数据挖掘是数据挖 掘技术在网络信息处理中的应用，是从 w e b网站的数据中发掘关系和规则。we b上的 每一个站点就是一个数据源， 每一站点之间的信息组织都不一样， 这就构成了一个巨大 的异构数据库环境。w e b数据挖掘不仅要利用一般和标准数据库里数据挖掘的全部技 术，还要针对网络数据的特点，采用更加特殊的方法。 第三章 w e b 挖掘的内涵及复杂性分析 3 . 1 w e b 挖掘原理 一般地， we b 数据挖掘的基本原理可用图3 - 1 所示的处理过程表示，目 标数据集就 是根据用户要求，从 we b资源中提取的相关数据，w e b挖掘将主要从这些数据中进行 数据提取; 预处理是从目 标数据集中除去明显错误的数据和冗余的数据。 进一步精简所 选数据的有效部分，并将数据转换成为有效形式，以使数据开采更有效;模式发现是根 据任务要求，选择合适的数据开采算法 包括选取合适的模型和参数) ，寻求感兴趣的 模型，并用一定的方法表达成某种易于理解的形式: 模式分析是对发现的模式进行解释 和评估，必要时需要返回前面处理中的某些步骤己反复提取; 最后将发现的知识以用户 能理解的方式提供给用户，并使用之。 预处理 模式分析 目标数据集 气 夔到 、 模式、规则、 统计结吴 一 一 月 卜 i有趣m模式 图3 - 1 w e b 挖掘的基本原理 3 . 2 w e b 挖掘的特点 w e b 挖掘具有如下特点: 1 . we b 数据挖掘的对象是大量、异质、分布的we b 文档 w e b上的每一个站点就是一个数据源海个数据源都是异构的， 因而每一站点之间的 信息和组织都不一样， 这就构成了一个巨大的异构数据库环境。 如果想要利用这些数据进 行数据挖掘， 必须要研究站点之间异构数据的集成问题， 只有将这些站点的数据都集成 起来，提供给用户一个统一的视图，才有可能从巨大的数据资源中获取所需的东西。 2 . w e b 文档是半结构化或无结构的 目前数据挖掘多应用于关系和面向对象数据库， 他们有完善的结构， 按照预先定义 的模式进行组织，存储和存取，而 w e b上的数据非常复杂，往往具有半结构化或非结 构化特性，难以映射到一个固定的模式，使传统数据模型和数据库系统难以 支持 w e b 上的信息挖掘。针对 w e b上的数据半结构化的 特点寻找一个半结构化的数据模型是解 决问题的关键所在。 除了要定义一个半结构化数据模型外， 还需要一种半结构化模型抽 取技术，即自 动地从现有数据中抽取半结构化模型的技术。 ， 3 .数据源具有很强的动态性 i n t e rn e t中数据更新非常迅速，有些信息可能很快过时，针对当前状态的信息能快 速更新知识，提供准确的决策支持要求数据发掘的动态性。 4 .用户目 标的模糊性 基于i n t e r n e t 的数据挖掘用户往往只对要采掘的主题有一个粗浅的认识，提不出很 明确的目 标来。 这就需要数据采掘系统具有一定的智能性和学习机制， 不断的跟踪用户 的兴趣，清晰明白地阐述采掘结果。 3 . 3 w e b 挖掘的分类 we b 数据挖掘就是利用数据挖掘技术从网络文档和服务中发现和提取信息。 w e b 上 各种形式的文档和用户访问信息就构成了w e b 数据挖掘的对象。根据挖掘对象的不同， 我们将w e b 数据挖掘分为内容挖掘、结构挖掘和访问信息挖掘3 大类。 i . we b内容挖掘 w e b内容挖掘是对we b 页面内容进行挖掘，从we b 文档中发现、提取有用信息。 其中 we b文档有多种类型的数据组成，如文本、图像、声音、视频等。现在使用较多 的是搜索引擎，但是搜索引擎一般只对网上的静态信息进行 “ 抓取” ，面对由用户提问 动态生成的结果或存储于后台的信息却无能为力。这也正是 w e b内容挖掘研究的重点 所在。 2 . w 亡 b 结构挖掘 每个 we b页面并不是原子对象，其内部有或多或少的结构。we b结构挖掘的基本 思想是将w e b 看作一个有向图， 他的顶点是w e b 页面， 页面间的超链就是有向图的边。 然后利用图论对 w e b的拓扑结构进行分析。we b结构挖掘就是利用社区服务分析和引 用分析技术对 w e b的链接结构进行分析，从而发现有用的模式。w e b结构挖掘的对象 可以是we b 页面之0 1 的超链，也可以是we b 页面的内部结构。 w e b 结构挖掘的目 的在于揭示蕴含在这些文档结构信息中的有用模式。 文档之间的 超链反映了文档间的某种联系。 例如饱含、从属等。我们称被链接指向的页面为链宿页 面， 包含该链接的页面为 链源页面。 那么，超链中的 标记文本( a n c h o r ) 对链宿页面也起 到了概括作用， 这种概括在一定程度上比链宿页面作者所作的概括 ( 页面的标题)要更 为客观、 准确。 超链还反映了文档间的引用关系，一个页面被别的页面所指向的次数和 指向它的页面的重要性的大小， 对于判断他在本领域内的重要性也是有贡献的。 所以可 综合考虑页面的引用次数和链源页面的重要性来判断链宿页面的重要性， 从而设计能够 查询与用户请求相关的 “ 权威”页面的搜索引擎。 3 . 访问信息挖掘 w e b访问信息挖掘是对用户访问we b时在服务器方留下的访问记录进行挖掘，即 对用户访问w e b 站点的 存取方式进行挖掘， 挖掘的对象是在服务器上的 包括s e r v e r l o g d a t a 等日 志。we b 访问信息挖掘可以从w e b 服务器那里自 动发现用户存取w e b 页面的 模式，得出群体用户或单个用户的访问模式和兴趣。 3 . 4 w e b 挖掘的难点及解决方法 1 . w e b 挖掘的难点 w e b m i n i n g 的 数据对象是: 异质的、 异构的、 模糊的、 随机的、 半结构化、 非结构 化或数据库信息。 w e b m i n i n g 中数据的动态性、不完整性、 噪声问 题更突出。 2 .如何解决we b 挖掘遇到的难题 x m l 所具有的可扩展性、结构化、有效性等特性为解决上述难题带来了希望: 首先， w e b 数据挖掘技术首要解决半结构化数据模型和半结构化数据模型的查询与 抽取问题。这就必须要有一个模型来清晰地描述 w e b上的数据，而寻找一个半结构化 的数据模型是解决问题的关键所在。除此之外，还需要一种半结构化模型抽取技术，即 自 动地从现有数据中抽取半结构化模型的技术。 x ml可看作一种半结构化的数据模型， 可以很容易的将x m l的文档描述与关系数据库中的属性对应起来，实施精确的查询与 模型抽取。 其次，如果没有 x ml ，搜索软件必须了解每个数据库是如何构建的，因为每个数 据库描述数据的格式几乎都是不同的。由于不同带来源数据的集成问题的存在。 现在搜 索多样的不兼容的数据库实际上是不可能的。x ml能够使不同来源的结构化的数据很 容易地结合在一起。 最后， 软件代理商可以 在中间 层的服务器上对从后端数据库和其他应用处来的数据 进行集成。然后，数据就能被发送到客户或其他服务器作进一步的集合、处理和分发。 由 于基于x m l的数据是自 我描述的， 数据不需要有内部描述就能被交换和处理。利用 x ml ，用户可以方便地进行本地计算和处理。x ml格式的数据发送给客户后，客户可 以用应用软件解析数据并对数据进行编辑和处理。 第四章 w e b 内容挖掘及其j a v a 实现 4 . 1 总体设计思想 面向 w e b的数据挖掘比面向单个数据仓库中的数据挖掘要复杂的多。其中如何用 一个模型来清晰的描述w e b 上的半结构化数据是关键o x ml 文件描述的语义非常清晰， 并支持十分精确的查询。由 此可见， x ml能为w e b 数据挖掘带来新的解决方法。这里 将讨论使用标准w e b 技术- h t ml 、 半结构化数据模型、 x ml , j a v a开发的一种 基于w e b的数据挖掘方法。对于图4 - 1 所示的标准h t ml页，解析数据组织成以对象 交换模型o e m表示的树型结构。利用算法 1 , 2 将树型结构映射生成x ml 文件，最后 用j a v a 解析x ml 文件以 抽取需要的数据。 4 . 2对象交换模型 o e m 下面讨论的是如图 4 - 1 所示的 w e b页，是在 d b l p站点查询 “ u n i v e r s a l r e l a t i o n d a t a b ase ”得来的。 沈. 灸 t r 加 户 ， 白 江川q若 s wt a 叭 肠目摇f a t f 因v a州 肠 d 口 s 1 d 如此， .玉 : 司 、 l a sc 贵蓝 公 . . : e 山 , - 峨 独盏 配逸 公 脸 必 w 欧d u s,-t,1- : 器裂黔咒发 老 。 国 止 组 七 出 汽 翻 却 麟 负 户 少加 息 跳i 趁 r 1 瑞加翩岔 七 所 再u 否 臼 盆 日 目 司 卯 ， _ ,4p 扣 t. i pf = 妇 ti t 一达匕创“ 盆 近 皿且: : 汕 -u- - : . g ni , . x y.-几 . . . i r c . x % f : l : : w:! 山 亩 知百 右 到 目办 户 碑扁醉 6 吐 幽 勿考 公 丹 l l n i 11 丁油 1 扑 酬 鱿孰 茹 名 念 念 图 4 - 1 从d b l p得来的网页 图4 - 2 显示了 用这个页面的数据根据o e m ( 对象交换模型 ) 组织的 标签树。 o e m是 一个众所周知的半结构化数据模型， 是一种带有嵌套标记的自 描述的对象模型。 在o e m 中侮个对象由一个标志符和一个值组成。 标识符专门用来标志对象。 一个对象记的值要 么是如整形或字符串 型的原子的 量， 要么是一组表示为 的参数对。 如图 4 - 2 中的对象 “ 1 3 : s t r i n g = / + l a b e l+ 5 1 4 :向x m l文档写入s t r i n g 生成的x ml文件: ma r k l e v e n e t h e n e s t e d u n iv e r s a l r e l a t io n d a t a b a s e mo d e l s p r in g e r 1 9 9 2 1 3 二./ / c o n t e n t a t h e r e r e p r e s e n t s f o r o b j e c t 另一个指向 它的 下一个兄弟节 点， n e x t ( ) ;第三个指向 它的 父节点， p a r e n t ( ) ;以 及节点标签。 办3 图5 - i数据树 d及模式树 t 5 . 2树的匹配 若t 和d是基于标签集l = a , b 的有序树， 分别称为模式树和数据树。 如u ,v 是 树t的两个节点， 那么用( u ,v ) e p t 表示在t中u 是v 的父节点而v 是u 的子节点而( u ,v ) e a t 表示在t中u 是v 的祖先而v 是u 的后代。 用u -t v 表示在t中v 比u 的序号大。 以1 t ( v ) 表示v 在t中的 标签。 那么可以 定义一个匹 配函数中 ， 如果4) 满足以下三个条件 可称t 匹配 d : i . 如果( v i .v 2 ) 任 p 丁 ， 那么( 小 ( v i ) , 小( v 2 ) ) 任 a d 2 加果v i c t v 2 ， 那么4) ( v o - (3 ， 令f k : = f k u t ; 3 . r e t u rn f = f , u，u f k _ , ; 算法2 e x p a n d 计算了 子树和相应最右路径的集合r m p k 的生成， r m p k 是t 在d中 出现对应的最右路经。用树结构实现它的存取。 算法2 : e x p a n d ( f , r mp ) 1 . c : = 小; r mp n e w d); 2 . f o r e a c h树 s e f , d o : f o r e a c h ( p , l ) e 1 , 二 ， d ) x l ( d 是s 的 最 右叶 节点的 标 签 ) , d o : 计算s 的 ( p , 1) 扩展得到t ; r mp n e w ( t ) : = u p d a t e ( r m p ( s ) , p , 1 ) ; c = c u ( t ) ; 3 . r e t u rn ; 算法3 u p d a t e 计算了 模式树t 在d中出 现的最右路经r m p ( t ) o 算法3 : u p d a t e ( r mp , p , l ) 1 .令r mp _二 4); 2 . f o r e a c h x e r mp , d o : ( a ) i f p = 0 ， 令y 为r m l ( x ) 的 第一 子节 点 ; ( b ) e l s e 令y 为二 。 p - 1 ( -1 ( x ) ) ( 即 与r m l ( x ) 在x 中 的 第 ( p - 1 ) 个 祖 先 节 点 对 应的d 中 的 节点 ) 的下一个兄弟节点; ( c ) w h i le y #n u l l , d o : 搜索以y 为根节点的子树， 如遇某一节点z 满足l d ( z ) = l , t h e n r m p n e w r m p , ( z ) ;/ * 附 加* / y : = n e x t ( y ) ; / * y 的 下一个兄弟节点* / 3 . re t u r n r mpe w ; 图5 - 3 显示了从图 5 - 1 d中的出现频率，若 。 二 。 . 树是频繁模式。 所示数据树d中挖掘频繁子模式集的过程，s 2则 s -。 对应的模式树是频繁的，由图 5 - 3 表示模式树在 可知有八个子 ， 。 ， ， 间 土四 间 土囚 甲志丫由 阂丁南丫 la p,b a g g 5 = 0 . 6 7串习3 3 闰工甲尚 闰工阴工囚 3 = 0. 1 7 图 5 - 3 3 =0 . 3 3 从图 5 毕 0今二 0 . 3 3 - 1 所示数据树 d挖掘频繁子模式集的过程 本章讨论了挖掘结构化数据的相关问题， 对其中的从有序树中挖掘频繁引导子树问 题进行研究， 设计算法并进行了理论分析。 但对于更实际的应用还需扩展本算法以期能 完成无序树和图数据的挖掘。 结语 由于we b 信息没有严格的结构，使人们很难将传统的数据挖掘方法应用于we b 信 息， 幸好x ml的出现解决了为半结构化数据建模的问题， 也为w e b 挖掘的发展提供了 契机。 本人通过阅读大量国内外资料， 将x ml 技术与w e b 挖掘结合进行研究， 主要完 成了以下工作: 1 . 实现了从we b 页面上提取用户感兴趣的信息的任务。通过将we b 页转换成x ml文 档并利用x ml文档的结构化特性，用j a v a 对其进行解析，将we b页面上的内容相关 但格式无关的信息提取出来并生成x ml结果文档递交给用户，以帮助用户利用这些信 息进行下一步的工作。 2 . 提出了一个挖掘结构化信息的方法。 这里的结构为有序树，目的是从有序树中发现频 繁出现的引导子树，设计并分析了算法，进行理论论证与推导， 得出了理论结果， 可以 为进行w e b 结构挖掘的用户提供一些信息。 因本人各方面的有限条件， 所做工作仍有不尽完善之处。 首先， w e b内 容挖掘部分 只能对网上的静态信息进行 “ 抓取， ，面对由用户提问动态生成的结果或存储于后台的 信息却无能为力，因此应用范围比较有限。 其次， 在挖掘结构化信息部分并没有完成实 现工作， 只给出了理论推导。另外， 有序树挖掘也只能应用在有限的数据范围内， 今后 的工作将致力于无序树及图结构数据的挖掘以适应实际的应用。 参考文献 1 1 r o y g o l d m a n , j as o n m c h u g h , j e n n i f e r w i d o m : f r o m s e m i s t r u c t u r e d d a t a t o x m l : m i g r a t i n g t h e l o r e d a t a mo d e l a n d q u e ry l a n g u a g e j . w e b d b ( i n f o r m a l p r o c e e d i n g s ) 1 9 9 9 : 2 5 - 3 0 . 2 z a k i , j: e f f i c i e n t l y mi n i n g f r e q u e n t t r e e s i n a f o r e s t j . i n : p r o c e e d i n g s o f t h e s i g k d d 0 2 , e d m o n t o n , c a n a d a , 2 0 0 2 . 3 a g r a w a l , r， m a n i l l a , h， s r i k a n t , r， t o i v o n e n , h， v e r k a m o , a . : f a s t d i s c o v e ry o f a s s o c i a t i o n r u l e s j . i n : u . m . f a y y a d e t a l .