（计算机软件与理论专业论文）基于xml的web数据挖掘技术研究与实现.pdf

摘要 面向w e b 的数据挖掘是一项复杂的技术，w e b 数据挖掘就是利用数据挖掘技术 从网络文档和服务中发现和提取信息。w e b 上各种形式的文档和用户访问信息就构 成 w e b 数据挖掘的对象。根据挖掘对象的不同我们将w e b 数据挖掘分为内容挖掘， 结构挖掘和访问信息挖掘。由于x m l 能够使不同来源的结构化的数据很容易地结合 在一起，因而使搜索多样的不兼容的数据库能够成为可能，从而为解决数据挖掘 难题带来了希望本文研究和探讨了使用x m l 作为数据交换格式对w e b 上的数据和 w e b 了志进行数据挖掘，从而发现关联规则。 一 本文完成的主要工作如下： ( 1 ) 完成了对基于x m l 的w e b 数据挖掘的技术研究并设计了相关系统。本文通过对 x m l 这种近几年出现的具有很大潜力的i n t e r n e t 数据交换技术的研究分析，提出了 基于x m l 的w e b 挖掘的新思路，并且完成了对x m l 的w e b 挖掘系统的系统功能设计。 ( 2 ) 实现了x i l 到数据库模式的转化工具。本文主要针对x m l 的d t d 文档，提出了一 系列从x m l 至f j 关系数据库模式的转换算法，使得x m l 数据和数据库数据的联合查询 成为可能，从而也就把基于x m l 的w e b 数据挖掘与传统的基于关系数掘模式的数据 挖掘算法建立了联系。 ( 3 ) 研究了基于x m l 的w e b 访问日志的挖掘。本文通过使用x m l 来存储和规整化w e b 日志内容，对w e b 日志内容做了必要的数据清洗和数据转化。同时通过实现a p r i o r i 算法，完成了对用户访问模式中的关联规则的提取，计算了关联规则的置信度和 支持度。 关键字：w e b 数据挖掘、关联规则、x m l 、文本挖掘 a b s t r a c t w e bm i n i n gi sac o m p l e xt e c h n o l o g y ，w h i c hr e f e rt ot h ep r o c e s so f i n f o r m a t i o no rr e s o u r c ed i s c o v e r yf r o mm i l l i o n so fs o u r c e sa c r o s st h ew o r l d w i d ew e b t h ed o c u m e n t sa n du s e ri n f o r m a t i o nu s e rb r o w s i n go n eo rm o r ew e b l o c a l i t i e sa r et h et a r g e to fw e bd a t am i n i n g w e bm i n i n gc a nd i v i d e di n t o d a t am i n i n g 、s t r u c t u r em i n i n ga n dl o gm i n i n ga c c o r d i n gt od i f f e r e n tm i n i n g t a r g e t a sx m lc a nc o m b i n es t r u c t u r a ld a t ae a s i l y ，i ti sp o s s i b l et om i n i n g m u l t i p l ed a t a b a s e i nt h i sp a p e rw es t u d ya n dd i s c u s st h eu s eo fx m la s d a t as w i t c hp a t t e r ni nw e bd a t am i n i n ga n dw e bl o gm i n i n ga r e a i nt h i sp a p e rw ew a n tt od i s c u s st h eu s eo fx m lf o rt h ew e bm i n i n g a r e aa n da c c o m p l i s h e dt h ef o l l o w i n gt a s k s ： 1 s t u d yt h em e t h o dt h a ta p p l i e st h ex m lt e c h n o l o g yi nt h ew e bm i n i n ga s y s t e mo fw e bm i n i n gb a s e do nx m l i nt h i sp a p e rw es t u d yt h ei n t e r n e td a t a s w i t c ht e c h n o l o g yo fx m lr e c e n ty e a r s w ea d v a n c ean e wm e t h o do fd a t a m i n i n gb a s e dx m l a n dw ed e s i g n e dt h ef u n c t i o no fd a t am i n i n gs y s t e mb a s e d x m l 2 i m p l e m e n t et h ea l g o r i t h m sf r o mc o n v e r t i n gx m ld o c u m e n t si n t or e l a t i o n a l d a t a b a s e i nt h i sp a p e rw ea d v a n c eag r o u po fm e t h o d so fs w i t c hx m li n t o r e l a t i o n a ld a t a b a s ep a t t e r n 3 u s e dx m la sm e d i at om i n i n gt h ew e bl o g w ed od a t aw a s h i n ga n d d a t a s w i t c h i n gt h r o u g hs a v ea n du n i t ea n dw e bl o gu s i n gx m l i nt h es a m et i m e w ec o l l e c tt h er u l e si nu s e rv i s i tp a t t e r ，a n dc o m p u t et h ec o n f i d e n c ea n d s u p p o r to fa s s o c i a t i o n k e yw o r d s ：w e bm i n i n g ，a s s o c i a t i o n ，x m l ，t e x tm i n i n g u 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 猛i ! 亚 日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其 他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：左骜毛。：逝：剧 1 1 本课题的来源和意义 第一章绪论 在网络和信息技术发展的同时，出现了“信息爆炸”的问题，即数据极大丰 富而知识相对匾乏。如何快速、准确地从海量数据里面提取有用的信息己经成为 当前计算机科学的关注热点。数据挖掘从大量信息中提取有用的知识，解决数据 的应用质量问题，从而提高学术上的可研究性，以及商业上的决策性。 x m l 的全称是可扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ) ，是s g m l ( 标准 通用标记语言，s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 的一个子集。总的来说， x m l 是一种中介标示语言，可提供描述结构化资料的格式：详细来说，x m l 是一种 类似于h t m l ，被设计用来描述数据的语言。x m l 已经成为数掘表示的一种丌放标准， 独立于机器平台、提供商和编程语言，从而在不同的系统、不同的数据库、不同 的语言之间搭起沟通的桥梁。 x m l 和数据挖掘都是近几年兴起的新技术，在网络与数据库方面等发挥了重大 作用，而两者的结合能够应用到更多领域，例如：w e b 服务、电子商务、图书馆和 医学等。x m l 促进了信息间的交流，为数据挖掘提供了更广阔的信息平台。x m l 可 看作一种半结构化的数据模型，可以很容易地将x m l 的文档描述与关系数据库中的 属性对应起来，实施精确的查询与模型抽取。因此研究基于x m l 的数掘挖掘技术对 于x m l 技术和通用的数据挖掘技术的发展都有很大的促进作用。 一 1 2 国际国内研究状况和进展 1 2 1x m l 的提出及研究发展状况 1 9 9 8 年2 月万维网协会( w 3 c ) 设计了x m l ，它是s g m l 的一个子集，是针对s g m l 和 h t m l 的局限性而创立的。它既具有s g i d l 的强大功能和可扩展性，同时又具有h t m l 的简单性。s g m l 中所有非核心的、未被使用的和含义模糊的部分都被删除，剩下 的就成为短小精悍的标记工具x m l x m l 保留了s g m l 8 0 9 6 的功能，而其复杂程度则 降低到原来的2 0 ( x m l 的规范只有2 6 页，而当初s g m l 的规范却长达5 0 0 页之多) 。 x m l 不像h t m l 那样仅仅应用于w e b 站点，它在电子商务、数据库、知识管理、 数据交流与共享、自然语言转换等方面都有广泛应用。2 0 0 0 年以后x m l 在计算机科 学外的科技领域也得到了应用，例如：m a t h x m l ( 数学x m l ) 、c m l ( 化学x m l ) 、a m l ( 天 文】( l l ) 等语言，它们使得专业语言的表示不再困难。 1 2 2 数据挖掘技术的研究发展状况 1 9 8 9 年举行的第十一届国际联合人工智能学术会议上首次提出了从数据库中 发现知识( k d d ) 一词。至u 1 9 9 9 年为止，由美国人工智能协会主办的k d d 国际研讨会 已经召开了8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐 从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为 当前计算机科学的一大热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷 纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在 1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新成果和动 态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法， 集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值等问题，k d d 系统 与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和 区别，以及相应的基本对策。6 篇论文摘要展示了k d d 在从建立分子模型到设计制 造业的具体应用。 不仅如此，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威，另一份在线周刊为d s * ( d s 代表决策支持) ，1 9 9 7 年l o 月7 日开始出版。在网上还有一个自由论坛d m e m a i l c l u b ，人们通过电子邮件 相互讨论d m k d 的热点问题。而领导整个潮流的d m k d 开发和研究中心，当数设在美 国e m d e n 的i b m 公司开发部。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家 自然科学基金首次支持对该领域研究的项目。目前，国内的许多科研单位和高等 院校竟相开展数据挖掘的基础理论及其应用研究，这些单位包括清华大学、中科 2 一 当垄盔耋霉圭耋堡鎏塞 院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工 程研究所对模糊方法在知识发现中的应用进行了较深入的研究；北京大学在开展 对数据立方体代数的研究；南京大学、四川大学和上海交通大学等单位探讨和研 究了非结构化数据的知识发现以及w e b 数据挖掘。 1 2 3x m l 和数据挖掘相结合的研究发展状况 2 0 0 0 年以后，国内外把x m l 和数据挖掘结合起来的研究逐渐增多，由于x m l 广泛 应用于w e b 上，因此基于x m l 的w e b 挖掘( w e bm i n i n g ) 的研究越来越受到重视，研究 的w e bm i n i n g 包括w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘。现在x m l 正在成为 i n t e r n e t 上数据描述和交换的标准，并且在将来x m l 将代替h t m l 而成为w e b 上驻留 数据的主要格式，为了将现有的w e b 网页转换为x m l 文档，已提出了w m a ( w e bm i n i n g a g e n t ) 系统，现今普遍认为的数据挖掘形式可以分为知识发现和预言挖掘两大类， 上述绝大部分文献在研究基于x m l 的数据挖掘应用时，往往只注意到y x m l 在w e b m i n i n g 方面的应用，这只是一种基于x m l 文档的知识发现。而对于x m l 在数掘挖掘 预言模型中的应用研究的不是太多。x m l 在数据挖掘预言模型中的主要应用是p m m l ( p r e d i c t i v em o d e lm a r k u pl a n g u a g e ) ，它是一种基于x m l 的语言，用来对数掘挖 掘预言模型进行描述和定义。它是由国际化组织数据挖掘工作组( d a t am i n i n g g r o u p ，简称d m g ) 提出的，它描述了大量不同的模型，包括预言模型、聚集和关联 规则等。 1 3 本文研究内容及组织结构 本文主要研究了x m l 和数据挖掘两项技术的结合点，提出了一个基于x m l 数据 挖掘系统模型。在该模型中对数据挖掘的各个环节都提出了用x m l 技术来解决的途 径，在实践中找到了x 札和数据挖掘一些新的结合点。课题主要研究了x m l 用于异 构数据集成、数据预处理和x m l 数据集上的数据挖掘等问题，并对重点研究的基于 x m l 的关联规则数据挖掘给出了具体实现和实验结果分析。 论文的组织结构如下： 第一章，绪论：从总体上论述了课题的来源和意义、技术背景以及课题的主要工 作；第二章，x m l 与数据挖掘技术概述：分别介绍了儿和数据挖掘技术的概念， 方法、研究现状及发展趋势等；第三章，w e b 数据挖掘的技术和原理；第四章， 基于x m l 的w e b 数据挖掘技术；第五章，系统结构设计与实现；第七章，结束语。 4 第二章x m l 及数据挖掘技术概述 2 1x m l 技术概述 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 是从s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u p l a n g u a g e ) 发展而来的一种新的标记语言，由捌l 工作组( 原称s g m l 编审部，于1 9 9 6 年a h w 3 c 主持下成立) 开发，其标准定义是于1 9 9 8 年2 月e b w 3 c 批准通过的。x m l 的目 标不在于给w e b 页面增加趣味性，而在于它想通过一种方法对文档和数据进行结构 化处理，从而使其能在部门、客户和供应商之间进行交换。 2 1 1x m l 的基本内容 x m l 用于对文档进行数字化的表示，把文档转化成某种计算机可读的代码，使 计算机可对这些文档进行诸如存储、处理、查询、传送、显示和打印等工作。为 了使计算机能够有效地处理这些文档，就必须告诉它文档的结构。 ( 1 ) 元素与属性：逻辑结构 。 大多数文档( 如书本和杂志) 都可分成一些组件( 如章节和文章) ，这些组件又可 以分为一些更小的组件( 如标题、段落、图形等等) ，而文档中的具体内容用文本 表示。在x m l 中，组件称为元素，表示具体内容的文本称为文档的字符数据。x m l 元素用来描述文档的逻辑结构。x m l 文档的这种层次结构见图2 - 1 ： 论文 i 一标题 j 摘要 ： r 段落 ；段落 i 一，章节 ： r 段落 ；r 段落 ；一一段落 章节 章节 图2 1x m l 文档的树形结构 5 其中，包含所有元素的元素( 如论文) 称为根元素，它是没有前导元素的唯一 元素。根元素直接包含的元素称为子元素，它们也可以包含自己的子元素。元素 还可以包含相关信息，这些信息称为属性，属性用以描述元素的一些特征 ( 2 ) 实体：物理结构 x m l 提供了一种机制，可以使文本线性地组织，即以多片( m u l t i p l ep i e c e s ) 的形式组织“文本片”这个概念称为实体，每个实体都有名字。x m l 元素是描述 文档的逻辑结构，而实体是描述组成x m l 文档的字节块的位置，即描述文档的物理 结构。 在文档中，可以通过插入实体引用来使用实体，) ( m l 处理器将会用实体替换相 应的实体引用，这一过程称为文本替换这样，同一文本可在很多不同的环境中 自动地重复使用，在某一处的更新就可以影响到使用这一文本的所有地方，这种 特性称为外部实体。非) ( m l 对象( 包括图形、电影、声音、原始文本p d f 。h t m l 等) 也可以用同样的方式引用，称为不可分析的实体，也称为数据实体。 ( 3 ) 标记 元素构成) ( m l 的树形文档，实体管理文档的尺寸和复杂性而描述文档的逻辑 结构、连接物理实体的记号称为标记。x m l 文档就是由标记和字符数掘构成的。两 者都使用u n i c o d e ，都称为) ( m l 文本，即字符数据+ 标记；x m l 文本。 为了区别于字符数据，标记使用一种特殊的字符，这种字符称为分隔符。最 常见的分隔符是小于号( “ ”) 、或与号( “”) 和分号( “；”) 。 在h t m l 和基于s g m l 的语言中都使用了类似的语法。 ( 4 ) 文档类型 文档类型是根据其中的元素定义的。如果两个文档包含了完全不同的元素， 或虽然元素相同，但它们以完全不同的方式组合在一起，那么它们很可能不属于 同一种文档类型。 如果是一个x m l 文档，它必须有某种由元素、属性和组件构成的结构。在为文 档创建样式表的时候，要根据这个结构知道其中的元素，根据元素类型名称知道 它们的含义，然后根据元素确定在何处显示。这种结构就是文档类型。 在x m l = p ，可以使用文档类型定义( d o c u m e n tt y p ed e f i n i t i o n 一d t d ”) 形式 6 化文档类型，也可以用说明来描述这种文档的结构，但使用d t d 可以让x m l 文档的 书写者更专注于自己的工作。 2 1 2x m l 的特点和应用范围 x m l 的优势在于它有以下突出特点： 良好的可扩展性：在没有x m l 的时候，要想定义一个标记语言并推广利用它非常 困难。而现在) ( m l 允许各个不同的行业根据自己独特的需要制定自己的一套标记， 并能迅速投入使用，使得制定新的标记语言简单易行。 内容的自描述性：x m l 是面向内容的标记语言，在x m l 中的标记一方面限定了元 素的层次结构，另一方面也说明了元素的含义。在x 札的搜寻结果中由标记就可知 道内容的含义，这也使得搜寻结果更有意义。 数据内容与形式的分离：x m l 不仅允许自定义一套标记，而且这些标记不必局限 于显示格式的描述。x m l 允许根据各种不同的规则来制定标记，比如商业规则，根 据数据描述甚至根据数据关系来制定标记。x 札是自描述语言，在x m l 中显示样式 从数据文档中分离出来放在样式单文件中；在x m l 中数据检索可以简单高效地进 行。 。 严格的语法要求：严格的语法要求固然表面上显得繁琐，但一个具有良好语法 结构的文档可提供良好的可读性和可维护性，长远来看大有裨益。 显示的多样性：x m l 一个非常鲜明的特点是把数据的显示格式和数掘的表示分 离。在x m l o ，可以用格式文件如x s l ( e x t e n s i b l es t y l el a n g u a g e ) 来定义) 【m l 的 显示格式，也可以利用h t m l 作为x m l 的显示模板，把x m l 数据以数据岛的形式内嵌 到h t m l 页面中，这种分离可以实现不同数据源数据的无缝连接，各种数据可以在 中间件上转换为x 儿格式，使得数据很容易地进行在线交换和传输。 x m l 可应用于如下方面：网络客户必须在不同的数据库问传递信息的应用： 需要把大部分从服务器下载的数据放到用户端处理的应用；相同的数据对于 不同的用户需要有不同的界面的应用；网络情报供应商要把发现的信息精心裁 剪，并发送给不同个人用户的应用；在w e b 上发布数据，使w e b 数据更有效地管 理；自然语言翻译；w e b 商务应用。 2 1 3x m l 与其他文档和数据模型的区别 普通的文本文档是无结构文档，而x m l 文档在某种意义上是一种半结构化数 据。这是因为x m l 文档具有半结构化数据的某些基本特性：结构不规则、结构易变、 结构自包含但是x m l 文档和普通的半结构化数据模型有很大的不同： 有效的x m l 文档具有d t d ，而d t d 则表示了x m l 文档的模式信息。而普通半结构化 数据模型则没有包含这一特点。 在普通半结构化数据模型中，标记是标注在边上的；而在x m l 数据模型中，标 记是标注在节点上的。当两个模型都是树结构的时候，这两者是可以相互转换的， 因此也是等价的。而当两个模型是图结构的时候，两者则不是等价的。当然，在 某些应用背景下，x m l 文档被认为是一个树模型，而另外一些应用背景下，x m l 文 档被认为是图模型( 通过i d ，i d r e f ，i d r e f s 来表明元素之间的引用关系) 在x m l 文档中，各个属性和子元素是有次序的，虽然很多场合下，次序是被忽 略的而普通半结构化数掘模型o e m 中，是不考虑次序的。 x m l 文档具有属性的概念，普通半结构化数据中没有相应的概念。 x m l 文档可以包含处理指令和注释等内容，而普通半结构化数据则没有。作为 h t m l 的扩展，) 【m l 和h t m l 也有很大的不同： x m l 文档中可以包含d t d ，而h t m l 文档则没有。 x m l 文档中的标签是用户自定义的，而h t m l 文档中的标签则是预先由w 3 c 定义。 h t m l 文档主要是用来显示的，是主要给人看的。而x m l 文档主要用来数据的存 储和交换，主要是用于计算机处理的，其中的标签表明了内嵌内容的大致信息。 2 1 4x m l 数据处理 ( 1 ) x m l 数据存取机制 从整体上讲，x m l 定义了应用间传递数据的结构，而且这种结构的描述不是基 于二进制的只能由程序去判读的代码，而是一种简单的能够用通用编辑器读取的 文本。图2 - 2 表示了x m l 的数据存取机制。 图2 - 2 x m l 数据存取机制 x m l 数据源多种多样，根据具体的应用，大概可分为下面三种：第一种是x m l 纯文本文档：第二种是关系型数据库；第三种则来源于其他各种应用数据，如邮 件、目录清单、商务报告等。其中，第一种来源，即x h i l 纯文本文档是最基本的也 是最为简单的，将数据存储于文件中，其最大的优点在于可以直接方便地读取， 或者加上样式信息在浏览器中显示，或者通过d o m 接口编程同其他应用相连。第二 种数掘来源是对第一种来源的扩展，其目的是便于开发各种动态应用，其优点则 在于通过数据库系统对数据进行管理，然后再利用服务器端应用( 如a s p ，j s p ， s e r v l e t ) 等进行动态存取。这种方式最适合于当前最为流行的基于三层结构的应 用开发，也是本系统所主要面对的数据来源。 对于x m l 文档，可以通过d o m ( d o c u m e n to b j e c tm o d e l ) 读取) ( m l 文档中的节点， 是最基本也是最底层的x m l 存取技术d o m 是w 3 c 的一种技术标准，实际上是提供一 组a p i 来存取x m l 数据。d o m 可以通过j a v a s c r i p t ，v b s c r i p t 等脚本程序来实现，也 可通过c + + 。j a v a 高级语言来实现。 其次，也可通过d s o ( d a t as o u r c eo b j e c t ) 进行x m l 的数据绑定可以方便地将 x m l 节点同h t m l 标记捆绑，从瑚l 文档中读取或写入数据，就象访问m i c r o s o f t a c c e s s 或s q ls e r v e r 一样；而h t t p + s q l 是m i c r o s o f t 新近提出的s o a p 方案的核心， 其基本原理是通过基于h t t p 协议的u r l 方式直接访i ；3 s q ls e r v e r 数据库，并返回 x m l 或h t m l 数据格式的文档。 ( 2 ) x m l 与数据库 9 当銮盔耋鎏土主篷磐銮 数据库提供了对于大批量数据的有效存储管理和快速信息检索、查询的功能。 从体系结构上看，数据库技术的发展历经了网络型数据库、层次型数据库、关系 数据库、面向对象数据库。虽然面向对象数据库融入了面向对象技术，但是到目 前为止，在各个领域使用最广的还是关系数据库。关系数据库管理系统( r d b m s ) 采用二维表格作为存储数据的模型，表格由行和列组成，一般情况下，列被称作 “字段”用于表示组成数据有效信息的属性，而行则用于指示一条完整的数据记 录。由于数据间的相关性可以通过表与表之间关键字( 外键) 来关联，由此产生了 “关系”类型的数据库。 针对x m l 数据，一般有两种存储方式：一是将其按结构层次拆分开来分别存于 不同字段，二是将x m l 文档原封不动地存入数据库。为了保持x m l 信息的完整性， 更好地研究x m l 的各种特性，本课题研究中涉及将x m l 存储到数据库的时候都以第 二种方式存储x m l 文档。 2 1 5x m l 编程：d o m 与s a x x m l 的实际应用有两个方面：对基于x m l 数据的处理以及具体行业的x m l 标准 化。文档对象模型( d o c u m e n to b j e c tm o d e l - - “d o m ”) 与x m l 简单应用编程接口 ( s u p p l ea p i f o rx m l 一“s a x ”) 是独立于具体实现语言的接口定义标准，是x m l 编程的基石。 s a x & p 简单应用编程接口，是基于事件的方式来处理x m l 文档。基于事件是指 s a ) 【为应用开发者提供了处理感兴趣的特定元素的方法，而不必要求在应用层次处 理之前预建元素。s a x 不必建立所有的元素，处理过程实时进行。 使用s a x 首先需要使用s a x 的a p i 定义感兴趣的特定元素，当x m l 解析器遍历x m l 文档时，遇到该特定元素标记，则产生事件( 如s t a r te l e m e n t 、e n de l e m e n t 等) ， 该事件会驱动应用程序调用相应的程序，开始处理该特定的元素。 d o m 即文档对象模型，是一种平台无关、语言无关的应用程序接口( a p i ) ，用 对象模型来描述文档的结构。允许程序和脚本动态访问和更新文档的内容、结构 和风格。它提供了一套标准的对象来表示h t m l 和x m l 文档，一个组合这些对象的标 准模型，以及访问和处理它们的一个标准接口。 w 3 c 的d o ml e v e l l 定义了两组d o m 编程按口：基本接口与扩展接口。基本接口 1 0 包括写x 儿文档的操作，扩展接口为开发人员提供了更便利的编程接口。 d 伽l e v e l1 主要描述了三部分内容，它们分别是： 定义表示和操作x m l 文档的接口( i n t e r f a c e ) 和对象( o b j e c t ) ； 接口和对象的语法，包括其方法和属性： 接口和对象之间的关系与协同关系。 d o m l e v e l2 在l e v e ll 的基础上增加了以下内容：文档的抽象视图、对象树 的遍历、文档范围、普通样式单、层叠式样式单等内容。另外，更重要的是，l e v e l 2 增加了对结构化文档内部所定义的事件机制的支持。 x m ld o m 将x m l 文档解析成一个非常类似于树的逻辑结构，编程人员可以使用 d o ma p i 为x m l 文档建立树结构然后遍历树来控制元素、提取信息或者进行任何类 型的处理。 每个树结点有特定的结点类型，大多数x m l 文档中最普通的结点类型是元素 ( e l e m e n t ) 、属性( a t t r i b u t e ) 及文本( t e x t ) 。由于属性不是孩子结点，属性在模 型中是特殊的，x m l d o m n a m e n o d e m a p 是专为属性提供的编程接口。 x m ld o m 提供四个主要的对象d o m d o c u m e n t ，x m l d o m n o d e 。x m l d o m n o d e l i s t 。 x m l d o m n a m e d n o d e m a p 。可以通过这些对象的方法和属性来访问对象的实例，操纵 对象的结构和数据，也能访问树中其它对象。 d o m d o c u m e n t 对象表示x m l 文档树的根结点； x m l d o m n o d e 对象表示树中的一个结点，是x m l 对象模型访问数数据的基本接口： x m l d o m n o d e l i s t 对象支持x m l d o m n o d e 对象的重复及索引操作； x n i l d o m n a m e d n o d e m a p 对象提供按属性名字访问的重复及索引操作 2 2 数据挖掘技术概述 2 2 1 数据挖掘的内涵 ( 1 ) 技术角度的定义 从技术上讲，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、 模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程。 知识的定义从广义上理解，数据、信息也是知识的表现形式，但是人们更把 概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉， 好像从矿石中采矿或淘金一样原始数据可以是结构化的，如关系数据库中的数 据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决策支持和过程 控制等，还可以用于数据自身的维护因此，数据挖掘是一门交叉学科，它把人 们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。 在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技 术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数 据挖掘这一新兴的研究领域，形成新的技术热点。 ( 2 ) 商业角度的定义 从应用上讲，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业 数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅 助商业决策的关键数据。 简而言之，数据挖掘其实是一种深层次数据分析方法，数据分析本身已有很 多年的历史，只不过过去数据收集和分析的目的是用于科学研究，另外，由于当 时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到极大限制。现 在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据 不再是为了分析的目的而收集的，而是由于纯机会的( o p p o r t u n i s t i c ) 商业运作产 生，分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正 有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量 非常大，但其中真正有价值的信息却很少，因此需要从大量数据中经过深层分析 获得有利于商业运作，提高竞争力的信息 因此，数据挖掘可以描述为按企业既定业务目标，对大量的企业数据进行探 索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一步将其模型化的先 进有效的方法。 1 2 2 2 2 数据挖掘的功能和常用技术 数据挖掘通过预测未来趋势及行为，做出前瞻的、基于知识的决策。数据挖 掘的目标是从大量数据中发现隐含的、有意义的知识，主要有以下五类功能： 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析 的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题， 数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预 测的问题包括预报破产以及认定对指定事件最可能做出反应的群体。 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数掘库中 数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 聚类 数据库中的记录可被划分为一系列有意义的子集，即聚类。聚类增强了人们 对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统 的模式识别方法和数学分类学。8 0 年代初， c h a l s k i 提出了聚类技术，其要点是 在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述， 从而避免了传统技术的某些片面性。 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性，生成区别性描述的方法很多，如决策树方法、遗传算法等。 偏差检测。 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观察结果与 模型值的偏差、量值随时间的变化等。偏差检测的基本方法是：寻找观测结果与参 照值之间有意义的差别。 一一：，也址主霉主主售鲨銮 数据挖掘常用技术常用到人工神经网络、决策树、遗传算法、最近邻技术、 规则推导和可视化等技术。其中，人工神经网络从结构上模仿生物神经网络，是 一种通过训练来学习的非线形预测模型，可以完成分类、聚类、特征开采等多种 数据挖掘任务；决策树用树形结构来表示决策集合。 这些决策集合通过对数据集的分类产生规则，典型的决策树方法有分类回归 树，典型的应用是分类规则的挖掘；遗传算法是一种新的优化技术，基于生物进 化的概念设计了一系列的过程来达到优化的目的，这些过程有基因组合、交叉、 变异和自然选择，为了应用遗传算法，需要把数据挖掘任务表达为一种搜索问题 而发挥遗传算法的优化搜索能力：最近邻技术通过k 个与之最相近的历史记录的组 合来辨别新的记录，有时也称这种技术为k 最近邻方法，这种技术可以用作聚类、 偏差分析等挖掘任务；规则推导通过统计方法归纳、提取有价值的“如果一那么” 规则，规则推导的技术在数据挖掘中被广泛使用，例如关联规则的挖掘：可视化 采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者，决策者可以 通过可视化技术交互地分析数据关系。 采用上述技术的某些专门的分析工具己经发展了大约十年的历史，不过这些 工具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工 业标准的数据仓库和联机分析系统中去了 2 2 3 数据挖掘的流程 ( 1 ) 数据挖掘环境 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的、有 效的、可实用的信息，并使用这些信息做出决策或者丰富知识。 数据挖掘环境可用下图表示： ( 2 ) 数据挖掘过程 图2 3 数据挖掘环境 数据挖掘过程一般有三个阶段组成：数据准备、数据挖掘、结果解释和表达。 数据挖掘可以表示为这三个阶段的反复过程。 1 4 第三章w e b 数据挖掘的技术和原理 3 1w e b 数据挖掘技术概述 w e b 数据挖掘就是利用数据挖掘技术从网络文档和服务中发现和提取信息。w e b 上各种形式的文档和用户访问信息就构成t w e b 数据挖掘的对象。根据挖掘对象的 不同我们将w e b 数据挖掘分为内容挖掘、结构挖掘和访问信息挖掘三大类，如下图 3 2w e b 文本数据挖掘 图3 - 1w e b 数据挖掘的分类 w e b 文档由多种类型的数据组成，如文本，图象，声音，视频等。这些数据又 分为文本数据和多媒体数据两大类，从而将w e b 容挖掘对应的分为w e b 文本挖掘 和w e b 多媒体挖掘两类。当前的多媒体挖掘处于起步阶段，仍停留在从多媒体的属 性进行挖掘而没有深入到基于多媒体内容的挖掘，从本质上讲还是文本的挖掘， 因此我们在这里重点介绍w e b 文本挖掘的具体处理过程和常用的方法。 w e b 文本挖掘的一般处理过程可以概括为下图： 图3 - 2w e b 文本挖掘的一般处理过程 ( 1 ) 文档表示：在i r 领域，文档的表示方法有很多种，如矢量空间模型 出互盔三_ j l 已耋丝鲨塞 ( v s m ) ，n g r 鲫s 表示法和文档概念分类法等。v s m 以其简单和有效性成为近年来人 们常用的表示方法。文档就是组成此向量空间的矢量。若某个词w 。在文档d 中出现 n ( d ，w 。) 次，则向量v ( d ) 的第i 个分量为n ( d ，w ) 。这是v s m 比较简单的一种表示方法， 它没有将每个词对文档d 的重要程度体现出来，解决此问题常使用t f i d f ( t e r m f r e q u e n c yt i m e si n v e r s ed o c u m e n tf r e q u e n c y ) 表示法，v ( d ) 的第1 个分量表示 为： 悱器i d f ( w , ) 其中i d f ( w 。) = l + l o g ( d f ( w 。) n ) ，d f ( w 。) 表示在n 个文档中词w 在其中至少 出现一次的文档的数目。 ( 2 ) 特征提取：文档特征集的提取一般是通过对文档的多遍扫描实现的，但是所得 到的特征向量的维数往往很高，这样就会增加处理的时间因此在基本不影响分 类结果的前提下，需进行特征子集的提取。其方法一般是构造一个评价函数，对 特征集中的特征向量进行评价，然后从中选取评价较高的特征向量作为特征子集， 常用的评价函数有信息增益( i n f o r m a t i o ng a i n ) 、交叉嫡( c r o s se n t r o p y ) 、相互 信息( m u t u a li n f o r m a t i o n ) 和几率比( o d d sr a t i o ) 等。 ( 3 ) 分类和模型评价：文档分类和模型质量评价方法与传统的数掘挖掘方法楣类 似，分类算法主要应用朴素贝叶斯分类算法( n a i v eb a y e s sc l a s s i f i e r ) 和k 邻近 参照分类算法。对模型的质量评价主要有分类的正确率( c l a s s i f i c a t i o n a c c u r a c y ) 、准确率( p r e c i s i o n ) 和信息估价( i n f o r m a t i o ns c o r e ) 。 3 3w e b 结构挖掘 w e b 本身并不是h t m l 页面的简单堆积，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 页面的内部结构。对前者的 研究具有普遍意义，而后者一般是针对特定领域的应用目的的。 1 6 w e b 结构挖掘的基本思想是将w e