（计算机应用技术专业论文）基于xml的web数据挖掘技术研究.pdf

论文题目： 专业： 硕士生： 指导教师： 基于x m l 的w e b 数据挖掘技术研究 计算机应用技术 刘江宏( 签名) 垒1 3 望宣 刘金碹 ( 签名) 美) = 篁! 业主 摘要 近年来许多传统数据挖掘研究者，已逐步从传统数据挖掘领域过渡到w e b 数据挖 掘领域。随着w e b 上x m l 数据量爆炸式的增长，x m l 已成为i n t e r n e t 上数据交换和数 据表示的事实标准，并且在将来x m l 将代替h t m l 而成为w e b 上驻留数据的主要格 式，于是，基于x m l 的数据挖掘方法已经成为w r e b 数据挖掘领域和x m l 技术领域的 一个研究热点。 面向w r e b 的数据挖掘技术与面向传统数据库的挖掘技术不同，基于x m l 的w e b 数据挖掘过程中，一般要将h t m l 数据格式转换成x m l 格式，再对x m l 数据进行相 关挖掘操作。目前，多数基于x m l 数据的挖掘算法是用半结构化数据模型来描述x m l 数据的，并在此基础上进行频繁模式发现，而用半结构化数据模型描述x m l 数据时具 有一定的缺陷，因此影响了挖掘算法的性能。针对上述问题，论文做了如下工作： 1 描述了一个基于x m l 的w e b 数据频繁模式挖掘框架结构，它在原有半结构化数 据模式挖掘算法的基础上，根据x m l 数据的模型特点，对频繁模式挖掘算法进行了归 类；依照半结构化数据的产生方式、组织形式、存储结构，抽象和总结了原有的x m l 数据挖掘算法。 2 分析了半结构化数据模型描述x m l 数据时存在的一些缺陷，针对这些缺陷，研 究了一种面向x m l 的扩展标记树模型e t m ，作为x m l 数据挖掘任务使用的数据模型。 3 使用e t m 有序树作为数据模型，给出了x m l f p t m i n e r 算法来挖掘x m l 中的 频繁模式树，并研究了一种修剪策略对x m l f p t m i n e r 算法进行改进。根据修剪策略， 可以直接从某些已知频繁子树中产生某些未知频繁子树，因此减少了算法在候选子树的 产生和支持度计算上的开销，从而提高了算法的效率。 关键词：w e b 数据挖掘；x m l ；频繁模式；半结构化数据模型 研究类型：应用研究 s u b j e c t ：r e s e a r c ho f w e bd a t am i n i n gt e c h n i q u e sb a s e do nx m l s p e c i a l t y：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：l i u j i a n g h 。n g ( s i g n a t u r e ) 生! 丛曼驾纽 i n s t r u c t o r ：l i uj inxuan(signatur e ) _ 兰壶l 口二五l 2 m a b s t r a c t i nr e c e n ty e a r s ，m a n yt r a d i t i o n a ld a t am i n i n gr e s e a r c h e r sh a v eb e e ng r a d u a l l ys h i f t i n g f r o mt h et r a d i t i o n a la r e a so fd a t am i n i n gt ot h ef i e l do fw e bm i n i n g w i t ht h ee x p l o s i v e g r o w t ho fx m l o nw e b ，x m lh a sb e c o m et h ed e f a c t os t a n d a r do fd a t ae x c h a n g ea n dd a t a r e p r e s e n t a t i o no ni n t e r a c t ，a n dx m l w i l lr e p l a c eh t m la st h em a i nd a t af o r m a to nw e bi n t h ef u t u r e ，s o ，d a t am i n i n gb a s e do nt h ex m lm e t h o d sh a v eb e c o m ear e s e a r c hh o t s p o to ft h e f i e l do fw e bd a t am i n i n ga n dx m lt e c h n o l o g y w e b o r i e n t e dd a t am i n i n gt e c h n o l o g yi sd i f f e r e n tf r o mt r a d i t i o n a ld a t a b a s e o r i e n t e d m i n i n gm e t h o d g e n e r a l l y ，w en e e dc h a n g eh t m ld a t at ox m lf o r m a ti nt h ep r o c e s so f w e bm i n i n gb a s e do nx m l ，a n dt h e nm i n e a tp r e s e n t ，t h ex m ld a t aw a sd e s c r i b e db y s e m i s t r u c t u r e dd a t am o d e lf o rd i s c o v e r i n gf r e q u e n tp a r e mi nt h em a j o r i t yo fx m l - b a s e d d a t am i n i n ga l g o r i t h m s ，b u tt h e r ea r es o m ed e f e c t sd e s c r i b e dx m lu s i n gs e m i s t r u c t u r e dd a t a m o d e l ，t h u sa f f e c t i n gt h ep e r f o r m a n c eo ft h em i n i n ga l g o r i t h m i nr e s p o n s et ot h e s ep r o b l e m s ， w em a k et h ef o l l o w i n gt h e s i sw o r k s f i r s t l y , d e s c r i b e daf r e q u e n tp a t t e r n s f r a m e w o r ko fw e bm i n i n gb a s e do nx m l i t c l a s s i f i e st h ef r e q u e n tp a t t e r nm i n i n ga l g o r i t h ma c c o r d i n gt ot h eo r i g i n a lm i n i n ga l g o r i t h mo f s e m i s t r u c t u r e dd a t am o d e la n dt h ex m ld a t am o d e lc h a r a c t e r i s t i c s ；i ts u m m a r i z e st h e o r i g i n a la l g o r i t h m so fx m l d a t am i n i n gi na c c o r d a n c ew i t ht h ee m e r g e n c eo ft h ew a y , f o r m s o fo r g a n i z a t i o na n ds t o r a g es t r u c t u r eo ft h es e m i s t r u c t u r e dd a t a s e c o n d l y , a n a l y z i n gs o m ed e f e c t sd e s c r i b e dx m l d a t au s i n gs e m i - s t r u c t u r e dd a t am o d e l ， i nv i e wo ft h e s ed e f e c t s ，r e s e a r c hak i n do fx m l - o r i e n t e de x t e n s i b l em a r k u pt r e em o d e l ( e t m ) a s t h ed a t am o d e lo fx m l m i n i n g f i n a l l y , a na l g o r i t h mn a m e dx m l f p t m i n e rt om i n ef r e q u e n tp a t t e r n s i nx m li s p r o d u c e db a s e do ne t mo r d e r e dt r e e ，a n dap r u n i n gm e t h o di sp r o d u c e dt oi m p r o v et h e a l g o r i t h m t h ep r u n i n gm e t h o dc a r lp e r m i t su st od i r e c t l yg e ts o m eu n d i s c o v e r e df r e q u e n t p a t t e r n sf r o ms o m ed i s c o v e r e df r e q u e n tp a t t e r n s ，s ot h a td e c e a s e sq u a n t i t yo fc a n d i d a t e s u b t r e e sa n dt i m et h a tu s e dt oc o u n tt h ef r e q u e n c yo ft h e i r , t h e r e b yi m p r o v e st h ee f f i c i e n c yo f x m l f p t m i n e r a l g o r i t h m k e y w o r d s ：w e b d a t am i m n gx m l f r e q u e n tp a t t e m s s e m i s t r u c t u r e dd a t am o d e l t h e s i s ：a p p l i c a t i o nr e s e a r c h 西妻彳j | 技大学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究t 作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文巾不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使朋过的材料。与我一同t 作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：女飞江泫日期：钆岬中组 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期问 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：如蝴 指导教师签名：1 ；芝，也筮 沁 每中其蚶b 1 绪论 1 1 研究背景及意义 1 1 1 问题提出背景 1 绪论 数据挖掘( d a t am i n i n g ) 是指从数据集中提取潜在的、人们感兴趣的知识，并把提 取的知识表示为概念、规则、规律、模式等形式【。更广义的说法是：数据挖掘是指在 一些事实或观察数据集合中寻找模式的过程。从一定意义上说，数据挖掘就是从大量的 数据中发现隐含的规律性的内容，解决数据的应用质量问题。充分利用有用的数据，废 弃虚伪无用的数据，是数据挖掘技术的最重要的应用。随着网络技术的发展和应用， i n t e r n e t 上的数据( 即w - e b 数据) 呈现出激增的态势，这些数据具有庞大、动态、异构、 半结构化等不同于传统数据库中结构化数据的新特点。怎样对这些数据进行充分而合理 的应用成了现今数据库技术的研究热点。 w 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 数据是一种半结构化的数据。所谓半结构化是相对于结构化( 传统 数据库) 和非结构化( 如一本书、一张图片等) 而言的，它既不是完全结构化的也不是 完全非结构化的。因为它的页面也具有一定的描述层次、存在一定的结构，所以我们将 它称为半结构化的数据p 1 。 由于w e b 数据存在方式的特殊性，使w e b 数据控制变得十分复杂，x m l 的出现为 解决w e b 数据挖掘的难题带来了机会。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 ，可扩展标 记语言) 是由w 3 c 定义的一种标记语言，x m l 文件描述的语义非常清晰，很容易与关 系数据库的属性一一对应，因此可以利用x m l 对数据挖掘技术和i n t e m e t 上数据结构 的特征进行分析，并把x m l 作为一种半结构化的数据模型实施查询与模型抽取。w e b 上存在各种各样的信息资源，如h t m l 文档、数据库、w o r d 等，可以将整个w e b 网看 作是一个大型的分布式的数据库系统，然后采用x m l 作为统一的数据模型，向上层提 供统一的x m l 文档格式的数据，这样，基于x m l 的w e b 数据挖掘将会解决w e b 数据 西安科技大学硕士学位论文 挖掘技术中的半结构化数据模型和半结构化数据模型的抽取问题等。 1 1 2 研究意义 随着i n t e m e t 的迅速发展与广泛的应用，一个引人注目的研究焦点是i n t e m e t 上的数 据挖掘。i n t e r n e t 上存储了许多复杂数据类型的数据，用户有充分的自由，可以随意连 接到i n t e m e t 的任意站点上。全球信息网大约有数亿个工作站，其用户具有不同的背景、 不同的兴趣和目的，支持用户有效地发现和利用全球信息网络上的资源，对信息系统的 研究者提出了新的挑战。大量存储的非结构化数据，网络搜索的性能、效率及最优的信 息获取( 即知识获取) 是影响i n t e m e t 成功应用的瓶颈。在庞大的i n t e r n e t 信息源上，发 现知识、进行数据挖掘是快速获取有用信息的一种有效方法。 w e b 技术自上个世纪9 0 年代出现以来，极大地改变了人们发布、获取和使用信息 的方式，尤其是近年来，以x m l 为基础的新一代w e b 环境的出现，很好地兼容了原有 的w e b 应用，而且可以更好地实现w e b 中的信息共享与交换。其基于文本的方便性和 半结构化特征使得x m l 在信息管理、电子商务、个性化出版、移动通信、网络教育、 电子文档交换等诸多领域得到了广泛应用，而且其应用范围还在不断扩展。x m l 4 】己经 成为i n t e m e t 上数据描述和交换的事实标准。对于这些越来越多的采用x m l 文档格式 进行存储、交换和表现的数据，除了已有的信息抽取、w e b 搜索等信息处理方法之外， 人们越来越需要获取更进一步的、深层次的知识，这就需要对其进行数据挖掘。但是， 正由于x m l 是一种半结构化的文本数据，本生具有文本文档和半结构化数据的诸多弱 点，如解析文档时必须采用顺序读取的方式，访问效率不高；对信息的组织不规则，或 者其结构可能经常变化，甚至可能不完整等。而传统的数据挖掘技术主要面对的是以结 构化数据为主的关系数据库、事务数据库和数据仓库，这样，我们不能直接将传统的基 于关系数据库的挖掘方法，如a p r i o r i ，应用到半结构化数据挖掘中。因此，开发出有效 的针对x m l 的数据挖掘方法成为w e b 数据挖掘领域和x m l 技术领域的一项重要课题。 1 2 课题相关技术的国内外研究状况 1 2 1w e b 数据挖掘研究的发展状况 w e b 挖掘是数据挖掘技术和理论应用于i n t e m e t 上资源进行挖掘的一个新兴领域， 引起了人们极大的兴趣。w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行 挖掘，确定权威页面，w e b 文档分类，w e bl o g 挖掘、智能查询、建立m e t a w e b 数据 仓库等。目前在w e b 数据挖掘研究领域中，根据挖掘对象的不同大致分为三个方面的 挖掘研究：w e b 内容挖掘、w e b 结构挖掘和w e b 数据的使用挖掘【5 刊。 国外一些机构对w e b 数据挖掘进行了大量的研究并取得了一定的成果：g o l d m a n 2 1 绪论 等人开发的m u s a g ，接受从用户处获取的关键字，然后搜索w r e b 上有关的文档，产生 语义相似的相关概念的辞典；l a m a c c h i a 提出了i n t e m e tf i s h 8 1 ，是一类资源发现工具， 用于用户从i n t e m e t 上抽取有用的信息，允许使用现有的搜索引擎帮助用户浏览；m a r k o g r o b e l n i k 等提出了基于y a h o o ，利用贝叶斯分类器进行i n t e m e v w e b 上的文本分类的方 法1 9 j ，收集若干具有较高概率的特征字，以快速地分类文本；w e b w a t e h e r 是由c m u ( 卡 内基梅隆大学) 开发的一个可安装在一个w w w 站点上的导游器，它对来访的用 户的访问行为进行在线学习，通过对站点上主页的超文本结构和以前用户浏览路径的学 习，建立起一个经验模型1 1 0 1 ；a i t av i s t ad i s c o v e r y 是由d e c 公司开发的一个新型的桌面 信息检索工具，它提供了对桌面、i n t e r n e t 、u s e n e t 数据的无缝集成，可以基于内容在本 地盘、网络盘、m t e m e t 的搜索空间进行检索，可以自动对所搜索到的文档进行总结， 寻找与当i j 网页相关联的网页；s c h a r k r a b a r t i 1 1j 对超文本数据挖掘进行了研究，并指出 基于知识的算法将会在w e b 数据挖掘中扮演重要的角色；b p i n k e r t o n 1 2 】对信息的收集和 评价方法进行了讨论并引入了结构挖掘来评价查询结果：o s m a rr z a i a n e 等还对w e b 多 媒体数据挖掘进行了研究，并提出了一个多媒体数据挖掘的系统原形；s b r i n 和l p a g e t l 3 】 提出了p a g e r a n k 算法并将其应用到搜索引擎g o o g l e 。国外的数据挖掘已经有不少的成 功案例。 尽管数据挖掘的好处己经引起国内许多企业的重视，但实施的并不多，更多的企业 还在观望和考虑。目前国内企业实现数据挖掘的困难主要有：缺少数据积累；难于构建 业务模型；各类人员之间的沟通存在障碍；缺少有经验的实施者：初期资金投入较大， 尤其是国内对w r e b 数据挖掘的研究起步较晚，还没有形成整体力量。 国内进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 “九五 计划等，许多科研单位和高校开展了数据挖掘的基础理论及其应用的研究【l 4 。， 如北京大学、中科院计算技术研究所等单位对w e b 内容挖掘、w e b 访问信息挖掘、用 户访问站点的路径访问模式等进行了较系统的研究【1 5 】；南京大学、四川联合大学和上海 交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。目前，一 些搜索引擎也已具备了数据挖掘的功能，比如近来的g o o g l e 智能搜索引擎，它改变了 以往搜索引擎的链接方式，通过站点访问频率和链接方式进行数据挖掘，给用户迅速而 准确地提供w - e b 信息。 w e b 数据的最大特点是半结构化，在众多的研究课题中，对半结构化数据结构的研 究是一个非常重要的方向，半结构化数据模型和半结构化数据模型抽取技术是面向w e b 的数据挖掘技术实施的i ； 提，是当今数据挖掘研究领域的热点【1 6 1 。 1 2 2x m l 技术研究的发展状况 1 9 9 6 年7 月万维网协会w 3 c ( w b r l dw i d ew e bc o n s o r t i u m ) 在j o nb o s a k ( s u n 公 3 西安科技大学硕士学位论丈 司的网络技术专家) 的建议下成立了可扩展标记语言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 i cm a r k u p l a n g u a g e ) 方便地应用于网络。1 9 9 8 年2 月1 0 日经w 3 c 认可，x m l l 0 建议书j 下式公 布于众【l7 1 。2 0 0 0 年l o 月6 日公布了x m l l 0 第二版。它是s g m l 的个子集，是针对 s g m l 和h t m l 的局限性而创立的。它既具有s g m l 的强大功能和可扩展性，同时又 具有h t m l 的简单性。s g m l 中所有非核心的、未被使用的和含义模糊的部分都被删 除，剩下的就成为短小精悍的标记工具x m l 。x m l 的规范只有2 6 页( 当初s g m l 的 规范长达5 0 0 页之多) ，保留了s g m l8 0 的功能，复杂程度却降低到原来的2 0 。 x m l 是一种典型的半结构化数据，它既能表示关系、对象等结构化的数据，也能 表示w e b 这样的半结构、非结构的数据，具有“自描述”、“树形结构”、“结构嵌套”等特 点，在数据交换和集成中得到大量应用。x m l 目前的研究主要有：x m l 技术与数据库 技术的结合；利用x m l 技术实现和改进语音技术、软件工程、电子商务等应用；数据 交换、w e b 发布和分布式计算；基于x m l 的签名、数据加密；s v g 、g m l 、x 3 d 、v r m l 、 v m l 、x a m l 、a v a l o n 等基于x m l 的图形技术；x m l 数据查询技术等相关问题， 并取得了一定的成果。 在经历了十年的发展后，目前x m l 已经成为互联网上数据交换和数据表示的事实 标准。x m l 具有简单性、结构化、可扩展性、互操作性、开放性、通用性、灵活性等 特点，因而在数据交换、数据集成、数据发布、数据存储、数据管理、知识管理、信息 检索等诸多领域得到了广泛应用。由于x m l 在大量信息技术领域大量得到应用，并且 i b m 、微软、o r a c l e 、s u n 、惠普等信息技术公司都公开表示将对x m l 技术进行大 力支持，导致作为存储交换的x m l 数据数量呈爆炸式增长。目前支持x m l 数据格式 存储的x m l 支持数据库和x m l 原生数据库就达3 0 多个【l 引。x m l 数据的快速发展迫 切需要与之相适应的数据挖掘技术。 1 2 3 基于x m l 的w e b 数据挖掘的研究发展状况 w e b 数据是一种半结构化的数据，x m l 数据类似于半结构化数据l l9 1 ，具有半结构 化特性，可以说，x m l 是w e b 上的半结构化数据，x m l 的出现推动了半结构化数据研 究的发展，为半结构化数据的研究提供了广阔的应用前景。总言之，x m l 的出现为解 决w e b 数据挖掘的难题带来了新的机会：由于x m l 能使不同来源的非结构化的数据很 容易的结合在一起，因而使搜索多样的不兼容的数据库成为可能；x m l 的可扩展性和 灵活性允许x m l 描述不同种类应用软件中的数据，从而能够描述搜集的w e b 页中的数 据记录；同时，基于x m l 的数据是自我描述的，所以数据不需要有内部描述就能被交 换和处理。 2 0 0 0 年以后，国内外把x m l 和数据挖掘结合起来的研究逐渐增多，x m l 广泛应 4 1 绪论 用于w e b 上，因此对基于x m l 的w e b 数据挖掘的研究越来越受到重视。如今x m l 己 经成为i n t e r n e t 上数据描述和交换的事实标准，并且将来x m l 将代替h t m l 成为w e b 上驻留数据的主要格式，为了将现有的以h t m l 格式文档为主的w e b 网页转换为x m l 文档，已经提出了w m a ( w e bm i n i n g a g e m ) 系统。 总体来看，国外对基于x m l 的w e b 数据挖掘研究大体可以分为两大派：一派是以 美国为首，包括加拿大、新加坡、韩国、日本等国，以传统数据库技术为主要技术支撑， 重点研究如何利用现有的数据库技术实现对x m l 数据的管理，如w e b 数据查询系统 n i a g a r a t 2 0 1 和t u k w i l a 2 1 1 ，其底层采用的是关系数据库系统；另一派是以法国、德国为首， 包括英国、奥地利等国，重点研究如何对整个x m l 文档进行有效的管理，目标是研究 一种能够对w e b 上的所有x m l 数据进行有效管理的原生x m l 数据库，如知名的基于 x m l 的互联网查询系统_ x y l e m e j 。 国内有一些院校和研究机构从事基于x m l 的信息处理方面的研究工作。中国人民 大学孟小峰教授领导一个小组正在研究基于x m l 的w e b 数据库，他们认为未来的w e b 将完全由x m l 描述，通过对x m l 相关技术的研究，将有助于对w e b 数据的有效管理； 中国科学院计算所和软件所在研究基于x m l 的信息抽取技术；武汉大学正在进行基于 x m l 的信息搜索方面的研究；复旦大学在研究基于x m l 的构件查询技术。 相信在不久的将来，随着x m l 作为在w e b 上交换数据的一种标准方式的进一步广 泛使用，面向w e b 的数据挖掘将会变得日益轻松。 1 3 论文主要研究内容及组织结构 论文主要研究基于x m l 的w e b 数据频繁模式挖掘，描述了一个基于x m l 的w e b 数据频繁模式挖掘框架；研究了一种描述x m l 数据的数据模型扩展标记树模型 ( e t m ) ，将x m l 文档映射为e t m 树；使用e t m 有序树作为数据模型，给出了 x m l f p t m i n e r 算法来挖掘x m l 数据中的频繁模式树，并研究了一种有效的修剪策略， 以提高算法的效率。 论文的组织结构如下： 第一章绪论。本章简述了课题研究的背景和意义、与课题相关的知识、技术的国 内外研究状况以及论文主要研究的内容和组织结构。 第二章相关知识与技术综述。本章首先介绍了数据挖掘的基本知识、w e b 数据挖 掘的定义、意义和原理、w e b 数据挖掘的分类以及w e b 数据挖掘的特点；接着介绍了 x m l 标记语言的主要特点；最后阐述了w e b 数据挖掘面临的挑战珊b 上的异构数 据库环境和w e b 数据的半结构化特点、分析了半结构化数据与x m l 标记语言的关系， 并引出基于x m l 的w e b 数据频繁模式挖掘的问题。 第三章基于x m l 的w e b 数据频繁模式挖掘框架。本章描述了一个基于x m l 的 5 西安科技大学硕士学位论文 w e b 数据频繁模式挖掘框架，给出了x m l 数据模型的形式化定义。重点讨论w e b 数据 预处理( 即将w e b 页面的h t m l 格式转化为x m l 格式) 、x m l 树形结构中各种挖掘 对象概念及相互关系，通过抽取x m l 数据的节点、边、路径、子树等各种不同特征来 表示x m l 数据。在表示x m l 数据的各种特征元素基础上，给出了x m l 频繁模式挖掘 的一般过程。 第四章x m l 数据模型的研究。本章论述了半结构化数据模型描述x m l 数据时存 在的一些缺陷，然后针对这些缺陷，研究了一种面向x m l 的扩展标记树模型( e t m ) ， 用以描述x m l 文档中的数据，最后讲述了将x m l 文档映射为e t m 树。 第五章基于x m l 数据的频繁模式树发现。本章介绍了x m l 数据的频繁模式树发 现问题。使用e t m 有序树作为数据模型，给出了x m l f p t m i n e r 算法来挖掘x m l 中的 频繁模式树。主要研究了算法中的两个关键问题：第一，如何产生候选子树；第二，如 何进行候选子树的支持度计算。最后，研究了一种有效的修剪策略，以提高算法的效率。 第六章结论。本章对全文进行总结，并指出了论文的不足和以后需要进一步进行 的工作。 6 2 相关知识与技术综述 2 相关知识与技术综述 2 1w e b 数据挖掘概述 数据采集和存储技术的进步导致庞大的数据库日益增多，这已经发生在人类耕耘的 几乎所有领域，从普通的( 比如超市业务数据、信用卡使用记录、电话呼叫清单以及政 府统计数据) 到不太普通的( 比如天体图像、分子数据库和医疗记录) 。那么，能否从 这些数据中提取出对数据库拥有者有价值的信息呢? 毫无疑问，人们对这个问题的兴趣 在不断增长，而且已经形成了致力于这个任务的一门学科，称为“数据挖掘( d a t a m i n i n g ) 。数据挖掘就是对观测到的数据集( 经常是很庞大的) 进行分析，目的是发 现未知的、有价值的信息和以新颖的方式来总结数据。 w e b 数据挖掘是一项综合技术，涉及i n t e m e t 技术、数据挖掘、计算机语言学、信息 学等多个领域。w e b 数据挖掘就是从与i n t e m e t 相关的资源和行为( 如w e b 文档、w e b 活 动等) 中抽取感兴趣的、潜在的有用模式和隐含信息。w e b 数据挖掘比面向数据库和数 据仓库的数据挖掘要复杂得多，因为i n t e m e t 上的数据很复杂。w e b 数据挖掘不仅要使用 面向传统数据库的数据挖掘的全部技术，还要针对网络数据的特点，采用一些特别的技 术方法。目前，w e b 数据挖掘己经成功应用到很多领域，诸如银行、电信、保险、交通、 网络零售、电子商务、网络广告分析、客户关系管理等。 2 1 1 数据挖掘的基本知识 1 数据挖掘简介 数据挖掘( d a t am i n i n g ) ，也称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y d a t a b a s e ，k d d ) ，是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含的、事先未知的、人们感兴趣的、具有潜在价值的信息和知识的过程。 提取的信息和知识表示为：概念、规则、模式、规律和约束等形式。更广义的说法是： 数据挖掘是指在一些事实或观察数据集合中寻找模式的过程。 数据挖掘是- - l - j 涉及多个领域的交叉学科，包括数据库和数据仓库技术、人工智能、 神经网络、机器学习、模式识别、统计学、知识工程、面向对象方法、信息检索、高性 能计算、数据可视化、图像与信号处理以及空间或时间数据分析等领域。数据挖掘被称 为未来信息处理的骨干技术之一，它以一种全新的概念改变着人类利用数据的方式。通 过对数据进行组织、分析、处理，然后应用数据挖掘技术得到人们感兴趣的、有价值的 信息或知识。原始数据可以来自于关系数据库、空间数据库、面向对象数据库，也可以 来自于文本数据源、多媒体数据以及分布在i n t e m e t 上的异构数据源。可以使用不同的方 7 西安科技大学硕士学位论文 法发现知识，如数学的和非数学的方法，演绎的和归纳的方法等。发现的知识可用于信 息管理、查询优化、决策支持和过程控制等，还可以用于数据自身的维护。数据挖掘技 术把人们对数据的低层应用，如简单查询等，提升到从数据中挖掘知识，对所得知识进 行高层运用，是- i - j 具有强大实际作用和前途的学科。 2 数据挖掘的过程 数据挖掘的过程主要从三个方面来考虑：第一，数据挖掘要解决的问题是什么；第 二，为数据挖掘进行数据准备；第三，采用什么样的数据挖掘算法。数据挖掘的基本步 骤有：( 1 ) 定义问题，确定业务对象，清晰地定义出业务问题，认清数据挖掘的目的 是数据挖掘的重要一步；( 2 ) 数据准备，包括数据选择、数据预处理、数据转换三个 子步骤；( 3 ) 数据挖掘，根据所要挖掘数据的类型和特点，选择相应的算法，对净化 和转换后的数据集进行挖掘，这是整个过程的核心阶段；( 4 ) 结果分析和评估，对数 据挖掘的结果进行解释、评估，转换成为能够被用户理解的、合理的知识；( 5 ) 知识 的运用，将分析所得到的知识集成到业务信息系统的组织结构中去。图2 1 描述了数据挖 掘的基本过程和主要步骤。 知 识 的 还 用 图2 1 数据挖掘的过程和主要步骤 在数据挖掘过程中，不同的步骤需要不同专长的人员，他们大体可以分为三类：业 务分析人员，要求精通业务，能够解释业务对象，并根据各业务对象确定出用于数据定 义和挖掘算法的业务需求；数据分析人员，要求精通数据分析技术，并对统计学有较熟 练的掌握，有能力把业务需求转化为数据挖掘的各步操作，并为每步操作选择合适的技 术；数据管理人员，要求精通数据管理技术，并从数据库或数据仓库中收集数据。因此， 数据挖掘是一个多类专家合作，在资金和技术上高投入的技术领域。 2 1 2w e b 数据挖掘技术简述 1 w 曲数据挖掘的定义与意义 ( 1 ) 定义 w e b 数据挖掘是指从w e b 资源上抽取信息或知识的过程，它是将传统的数据挖掘 8 2 相关知识与技术综述 的思想和方法应用于w e b ，从与w e b 文档和w e b 活动中抽取感兴趣的、潜在的、有用 的模式和隐藏信息【2 3 l 。 也有把w e b 数据挖掘定义为：从大量w e b 文档结构和使用的集合c 中发现隐含的 模式p ，如果将c 看作输入、p 看作输出，那么w e b 数据挖掘的过程就是从输入到输出 的一个映射鼍：c - p 1 2 4 j 。 还有把w e b 数据挖掘定义为：针对包括w e b 页面内容、页面之间的结构、用户访 问信息、电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以帮助用户从w w w 中提取知识，为访问者、站点经营者以及包括电子商务在内的基于i n t e m e t 的商务活动 提供决策支持。 w e b 数据挖掘更广义的定义为：从i n t e m e t 中发现和分析有用的信息和知识。 ( 2 ) 意义 通过w e b 数据挖掘，我们可以从数以亿计存储着大量多种多样信息的w e b 页面及 其链接和用户对页面的访问中挖掘出我们需要的信息或知识，具有如下意义： 从大量的信息中发现用户感兴趣的信息 在i n t e r n e t 上，最常用的获得信息的方法是页面浏览和关键词搜索。浏览一个页面 得到的是页面的孤立信息，基于关键词查询的搜索引擎可以帮助用户查找相关信息的页 面，但是目前的搜索引擎至少有两个问题不可回避：第一，由于精确度低，使得搜索的 结果的可用性大打折扣。有时候庞大的搜索结果对用户来说是新的负担，为获得可用的 信息用户不得不再做大量的尝试性工作重新搜索；第二，这些搜索结果是凌乱的、无组 织的，因而无法反复使用。这些问题足以说明需要新的、更加有效的方法工具来挖掘 w e b 上的丰富信息。 将w e b 上丰富的信息转变成有用的知识 w e b 数据挖掘就是面向w e b 数据进行分析处理和知识提取的过程。i n t e m e t 上页面 内部、页面问、页面链接、页面访问等都包含大量对用户可用的信息，而这些信息的深 层次含义是很难被用户直接发现和使用的，必须经过数据处理和提取，从而发现隐含的 有用的信息。这也是w e b 数据挖掘所解决问题的出发点和目的。 对用户进行信息个性化 i m e r n e t 上不同的用户、不同的用户群对信息的需求是不同的。信息的个性化是将 来的发展趋势，通过对每个用户的访问行为、频度、内容等进行分析，利用w e b 数据 挖掘技术，提取出每个用户的访问行为和方式等的普遍知识，用以改进站点的w e b 服 务设计，从而给每个用户提供个性化的界面，提供个性化的电子商务服务等【2 5 1 。 2 w 曲数据挖掘的原理 与传统数据库和数据仓库相比，i n t e m e t 上的信息是非结构化或半结构化的、动态 的、并且是容易造成混淆的，所以很难将w e b 页面数据直接进行数据挖掘，必须要经 9 西安科技大学硕士学位论文 过必要的数据处理。一般地，w e b 数据挖掘的基本原理可用图2 2 所示的处理过程表示： 、 数据 、模式，、模式，、 w e b 预处理 处理后 发现 数据挖 分析 有价值 数据集广_ 数据集严掘结果严 的信息 图2 2w e b 数据挖掘的基本原理 ( 1 ) 查找资源：从各种w e b 数据源中获得数据，数据可以来自w e b 文档、电子邮 件、新闻组或w e b 日志等。图2 2 中，w e b 数据集就是从w e b 数据源中提取的与用户 需求相关的数据。 ( 2 ) 信息选择和预处理：从查找得来的资源中除去无用信息，保留有用信息，并 将信息进行必要的整理，为下一步的数据挖掘过程做好前期准备。数据预处理主要包括： 数据清理、数据集成、数据转换和数据约简。如从w e b 文档中自动去除广告连接、多 余格式标记、自动识别段落或字段等，并将数据组织成规整的逻辑形式甚至是关系表。 图2 2 中，处理后数据集就是对获得的w e b 数据集进行一系列预处理后得到的数据集( 即 参加挖掘的数据的有效形式) 。 ( 3 ) 模式发现：就是在一个站点内部或在多个站点间自动进行模式发现。根据任 务要求，选择合适的数据挖掘算法，从预处理后数据集中发现( 或挖掘) 潜在的、有价 值的、感兴趣的且能被人理解的知识模式，并将挖掘结果用一定的方法表达成某种易于 理解的形式，即为图2 2 中的数据挖掘结果。 ( 4 ) 模式分析：就是用合适的技术和工具对上一步的挖掘结果进行分析，验证、 解释挖掘出来的知识模式，从而提取出图2 2 中感兴趣的、有价值的信息或知识模式， 并将其以用户能理解的方式表述出来，以利于用户接受和相互交流。模式分析过程可以 由机器自动完成，也可以是与分析人员进行交互来完成。 2 1 3w e b 数据挖掘的分类 w e b 数据挖掘根据它所挖掘的站点信息来源可以分为w e b 内容挖掘( w r e bc o n t e n t m i n i n g ) 、w e b 结构挖掘( w e b s t r u c t u r em i n i n g ) 和w - e b 使用挖掘( w e bu s a g em i n i n g ) 【2 6 】三种主要类型，如图2 3 所示，下面将对这些内容一一作介绍。 1 w 曲内容挖掘 w e b 内容挖掘是指对w e b 页面内容进行挖掘，从文本、图像、音频、视频等各种 形式的网络资源中发现所需要的特定化信息，是普通文本挖掘结合w e b 信息特征的一 种特殊应用。 1 0 2 相关知识与技术综述 图2 3w e b 数据挖掘的分类 w e b 内容挖掘一般包括两类：w ，e b 文档挖掘，如w r e b 查询语言w 曲l o g ，w e bs q l 等；搜索结果挖掘，如对搜索引擎的返回结果进行聚类等。如图2 4 所示，对于w e b 文 档挖掘，按挖掘对象不同又分为w | e b 文本挖掘和w e b 多媒体挖掘【27 1 。对于文本文档( 包 括t e x t ，p d f ，h t m l ，x m l 等) 的挖掘称为文本挖掘。w e b 文本挖掘可以对w e b 上 大量的文档集合的内容进行总结、分类、聚类、关联分析以及利用w e b 文档进行趋势 分析等。对于多媒体文档( 包括i m a g e ，a u d i o ，v i d e o 等) 的挖掘称为多媒体挖掘。多 媒体信息挖掘，主要指通过对w e b 上的音频、视频数据和图像进行预处理，应用挖掘 技术对其中潜在的、有意义的信息和模式进行挖掘的过程。 图2 4w e b 内容挖掘的分类 w e b 多媒体挖掘与w e b 文本挖掘的不同点在于需要提取的特征不同。w e b 多媒体 西安科技大学硕士学位论文 挖掘需要提取的特征一般包括图形、语音、视频等的文件名、类型、u r l