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

论文摘要 近十几年来，随着i n t e m e t 的迅速发展，互联网上的数据越来越趋于庞大。 怎样能够有效地利用这些复杂而无章的w e b 数据、从中发掘出有价值的信息成 了现今的研究热点。 随着x m l 的不断发展，互联网上越来越多的信息都开始使用x m l 表示。x m l 以其可扩展、平台独立、灵活、规范和简单等特点以及强大的数据表达能力，在 网络和其他领域的数据表示和交换方面都扮演着越来越重要的角色。因此，人们 迫切地需要寻找一些有效的方法从这些大量的x m l 数据中提取一些潜在的、有 价值的信息和知识。但是w e b 上的x m l 数据非常复杂，没有特定的模型描述数 据，是半结构化的甚至是无结构的数据。所以，面向x m l 的数据挖掘技术有着 不同于传统数据库上的数据挖掘技术的特点。它对半结构化数据的集成和组织， 对挖掘算法的性能都提出了新的挑战。 本文根据w e b 上x m l 数据的半结构化的特点以及x m l 查询语言 x q u e r y 、n e td o m 对x m l 操作的支持，针对如何直接从x m l 数据中提取有 价值的关联规则进行了探索性研究。论文首先对x q u e r y 实现的a p r i o d 算法作 了比较深入的研究，针对a p r i o r i 算法不适应挖掘结构复杂不规则的x m l 文档数 据和挖掘大规模的x m l 文档数据效率不高的局限分别作了相应地改进。实验表 明，改进后的算法能够有效地从x m l 数据中抽取关联规则。其次，论文也重点 探讨了如何使用n e td o m 对x m l 数据进行直接关联规则挖掘。n e td o m 采 用面向对象机制将对x m l 的操作封装成类库，用其实现的关联规则挖掘算法更 符合人类的思维方式，更容易理解。而且，n e td o m 实现的算法的可视化更强， 算法编译执行，速度更快。此外，论文从电子商务网站的购物篮数据中抽取了一 部分典型的挖掘数据，构造了具体的实验，根据实验的结果对上述两种算法的优 缺点进行了对比分析。实验结果表明，在不同的环境需求下，两种算法有着各自 的强势和劣势，从而可以指导人们在未来x m l 的关联规则挖掘过程中，应该根 据不同的需求和挖掘环境选择不同的挖掘方法，才能使数据挖掘的效率和性能得 到优化。最后，本文提出了一个基于x m l 和关联规则挖掘的w e b 挖掘系统的五 层架构模型，对该模型的各个功能模块进行了详细地介绍。并且根据该模型，设 计了一个面向电子商务网站的基于x m l 的关联规则挖掘系统模块。该模块能够 处理多种数据源，支持多种关联规则挖掘算法以及挖掘结果的可视化表达，具有 综合性和可扩展性的特点。 关键字l 关联规则，x m l ，x q u e r y ，a p r i o d 算法，n e td o m ，w e b 挖掘 基于x m l 和w e b 数据的关联规则挖掘研究 a b s t r a c t i nt h er e c e n ty e a r s ，b e c a u s eo ft h ef a s td e v e l o p m e n to fi n t e r n e t ，m o r e a n d m o r ed a t ah a sb e e ng e n e r a t e do nt h ew e b h o wt om a k e g r e a tu s e o ft h e n e wk n o w l e d g ea n di m p r o v et h eu t i l i t yo ft h ei n f o r m a t i o nb e c o m e sab i g c h a l l e n g e a l o n gw i t ht h ei m p r o v e m e n to ft h ex m lt e c h n o l o g y , m o r ea n dm o r ew e b d a t ab e g a nt ob er e p r e s e n t e du s i n gx ml x m li sp l a y i n ga ni n c r e a s i n g l y i m p o r t a n tr o l ei nt h ee x c h a n g ea n dr e p r e s e n to faw i d ev a r i e t yo fd a t ao nt h e w e ba n de l s e w h e r ed u et oi t se x p a n s i b i l i t y , p l a t f o r m i n d e p e n d e n c e ，f l e x i b i l i t y , s i m p l e n e s s ，s t a n d a r d i z a t i o na n dp o w e r f u la b i l i t yf o rr e p r e s e n t i n gd a t a s o t h e r eh a v eb e e ni n c r e a s i n gd e m a n d sf o re f f i c i e n tm e t h o d st h a tc a ne x t r a c t r u l e sa n dp a f f e m sf r o mx m ld a t a h o w e v e et h ex m ld a t ao nt h ew e bi st o o c o m p l e xa n ds e m i - s t r u c t u r e dw i t hn oc e r t a i nd e s c d p t i o np a f f e r n t h u s ，w e c a n n o td i r e c t l ya p p l yt ox m ld a t aw i t ht h et r a d i t i o n a ld a t am i n i n gm e t h o d sf o r r e l a t i o n a ld a t a b a s e s h e n c e ，i ti sag r e a tc h a l l e n g et od e v e l o pe f f i c i e n ta n d s c a l a b l em e t h o d sf o rx m ld a t am i n i n g b a s e do nt h ec h a r a c t e r i s t i c so ft h ex m ld a t ai t s e l fa n dt h ex m l o p e r a t i o n s u p p o r to fx q u e r ya n d n e td o m w eh a v ed o n eag r e a ta n dd e e pr e s e a r c h o nh o wt oe x t r a c tm e a n i n g f u la s s o c i a t i o nr u l e sf r o mx m ld a t ad i r e c t l y f i r s t l y , w ei m p r o v e dt h ex q u e r ya l g o r i t h mt os o l v et h et w ol i m i t a t i o n st h a ti t c a n tm i n ec o m p l e xa n di r r e g u l a rx m ld a t aa n dl a r g es e t so fx m ld a t a t h e e x p e r i m e n t a lr e s u l tv e n f i e dt h a to u ri m p r o v e m e n tc o u l de f f i c i e n t l ye x t r a c t a s s o c i a t i o nr u l e sf r o mx m l d a t a s e c o n d l y , w ed i s c u s s e dh o wt om i n ex m l d a t au s i n gt h ea l g o r i t h mi m p l e m e n t e db y n e td o m t h e n e td o mu s e s o b j e c to r i e n t e dm e c h a n i s mt oo p e r a t et h ex m ld a t a ，m o r es i m i l a rt oh u m a n t h i n k i n g ，e a s i e rt ou n d e r s t a n d m o r e o v e r , t h ea l g o r i t h mi m p l e m e n t e db y n e t d o mi sm o r ep o w e r f u lf o rv i e wa n df a s t e rr u n n i n gw i t hc o m p i l a t i o n t h i r d l y , w e c o m p a r e dt h ea b o v et w om e t h o d sf o rm i n i n gx m ld a t ab ym a d d i n ga n e x p e n m e n tw i t ht h ex m ld a t ae x t r a c t e df n 3 mw e b w ef o u n dt h a tt h e yb o t h h a v ea d v a n t a g e sa n dd i s a d v a n t a g e si nd i f f e r e n tm i n i n ge n v i r o n m e n t l a s t l y , w ep r o p o s e daf i v el e v e lf r a m e w o r km o d e lf o rm i n i n ga s s o c i a t i o nr u l e sf r o m x m ld a t aa n de v e r yf u n c t i o nm o d u l eo ft h em o d e li sd e s c r i b e di nd e t a i l s t h e n ， b a s e do nt h em o d e l ，w ed e s i g n e da na s s o c i a u o nr u l e sm i n i n gs y s t e mo ft h e e - c o m m e r c ew e bs i t e t h i ss y s t e mi sa b l et op r o c e s sd i f f e r e n tk i n d so fi n p u t 2 基于x m l 和w e b 数据的关联规则挖掘研究 d a t a ，s u p p o r tc o m m o na s s o c i a t i o nr u l e sm i n i n ga l g o r i t h m sa n dt h ev i s u a l e x p r e s s i o no fm i n i n gr e s u l t s i ta l s oh a sag o o di n t e g r a t i o na n de x t e n s i b i l i t y k e y w o r d s ：a s s o c i a t i o nr u l e s ，x m l ，x q u e r y ，a p r i o r ia l o g r i t h m ，n e td o m ， w e bd a t am i n i n g 3 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得 的研究成果。据我所知，除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡 献的个人和集体。均已在文中作7 明确说明并表示谢意。 作者签名：哗 e l t 啦i ：j 塑脚 目 学位论文授权使用声明 本人完全了解华东师范大学有关保留，使用学位论文的规定。学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进行检 索。有权捋学位论文的标题和摘要汇编出版。保密的学位论文在解密 后螽用本规定。 学位论文作者签名：嗜齑鸷 导师签名： 日期： 兰塑；车! 三囤 日 彬i 毛 基于x m l 和w e b 数据的关联规则挖掘研究 第1 章引言 随着互联网络技术的迅速发展和数据管理系统的广泛应用，人们拥有和积累 的w e b 数据也越来越多。面对如此庞大的w e b 数据信息，人们迫切希望将这些 看似纷繁芜杂的数据转换成可供利用的信息和知识，以得到关于数据的总体特征 以及对其发展趋势的预测。例如：电子商务网站的经营者希望通过分析客户的购 买行为，分析出客户的购买习惯和爱好，向其推荐商品，从而增加网站的营业额； 医学人员希望从成千上万份病例中找出患有某种疾病的病人的共同特征，从而为 诊断和治愈这种疾病提供帮助。 传统的数据挖掘技术可以从大量的关系数据中提取有价值的知识，解决关系 数据的应用质量问题，从而提高学术上的可研究性和商业上的决策性。但是，面 向w e b 的数据挖掘比面向关系数据的数据挖掘复杂的多。因为传统数据库中所 存储的数据是结构化的，而w e b 上的数据绝大多数是半结构化和非结构化的， 这对w e b 数据挖掘的研究提出了极大的挑战。 1 1w e b 数据挖掘的研究背景 面向w e b 的数据挖掘是数据挖掘技术的一个分支，它是利用数据挖掘技术 从网络文档和服务中发现和提取信息。目前对w e b 数据的研究主要包括w e b 内容挖掘、w e b 结构挖掘和w e b 使用记录挖掘。而随着w e b 上越来越多的数 据使用x m l 来表示，人们迫切地希望从这些丰富的x m l 数据中挖掘出可供利用 的有价值的信息。 x m l 是一种文本文档的可扩展标记语言，其自描述性使其非常适用于不同应 用间的数据交换。它独立于机器平台、提供商和编程语言，因此可以作为数据表 示的一种开放标准，在不同的系统、不同的数据库和不同的语言之间搭起沟通的 桥梁。但是，由于x m l 是一种半结构化的文本数据，与生具有文本文档和半结 构化数据的诸多缺点：对信息的组织不规则，或者其结构可能经常变化，甚至可 能不完整等。而传统的数据挖掘技术主要面向的是以结构化数据为主的关系数据 库、事务数据库和数据仓库，这样，我们不能将传统的基于关系数据库的挖掘方 法直接应用到x m l 文档的挖掘中。因此，开发出有效的针对x m l 的数据挖掘方 法已经是w e b 挖掘领域和x m l 技术领域的一项重要课题。 目前，国内外有不少文献提出了从x m l 数据中挖掘关联规则的方法，但是 大多数挖掘方法都需要对x m l 数据进行一定的预处理和后处理工作。例如，首 2 基于x m l 和w e b 数据的关联规则挖掘研究 先需要将x m l 模式映射到关系模式，然后再使用针对关系数据的挖掘方法来挖 掘关联规则，最后将得到的结果再映射到x m l 模式。在整个挖掘过程中，需要 对数据进行两次模式转换，往往会造成数据访问效率的下降和语义的丢失“一。 x m l 文档查询语言x q u e r y 的出现，使直接挖掘x m l 数据成为可能。x q u e r y 是针对x m l 的一种易于使用的、高水平的查询语言。它对于x m l 而言就像s q l 对于数据库一样。x q u e r y 可以灵活地查询广泛的x m l 信息源，包括数据库和 文档。它同时支持不同类型的表达式，支持路径表达式以及元素和属性构造函数。 使用这些功能，我们能够将x q u e r y 应用到查询、转换甚至构建x m l 文档之中。 正是基于x q u e r y 的强大功能和操作x m l 数据的灵活性，才可以有效地使用 x q u e r y 实现经典的数据挖掘算法，不需要进行任何其它形式的转换工作，从而 实现了对x m l 文档直接的数据挖掘，提高了x m l 文档挖掘的效率。 此外，w 3 c 为了给访问和操纵x m l 文档提供统一的编程接口，定义了文档 对象模型，即d o m ”。d o m 是一个对象化的x m l 数据接口，它本身是一组对 象的集合，通过操作这些对象，可以操作x m l 数据，对x m l 文档进行读取、遍 历、修改、添加和删除操作。d o m 的出现，为直接挖掘x m l 数据提供了另一 个重要方法。d o m 将要操作的x m l 文档一次性装入内存，将该文档分成几个 独立的原子信息：元素、属性、注释和处理指令等，并将这些原子信息建立一个 树型结构。树的每个节点都被表示成一个x m l n o d e 的抽象类，可以使用x p a t h 对x m l n o d e 进行查询和定位操作，因此可以实现对x m l 数据的直接挖掘。 1 2 基于x m l 和w e b 数据的关联规则挖掘的研究现状 随着x m l 在w e b 上的广泛应用，x m l 逐渐成为互联网上数据描述和信息 交换的标准。为了更加充分地利用日益增长的海量的x m l 数据信息，基于m l 的w e b 数据挖掘技术便如火如荼地发展起来。 在众多挖掘x m l 的技术中，关联规则挖掘一直是研究的热点。1 9 9 3 年 a g r a w a lr “。等首先提出了关联规则的问题，并于1 9 9 4 年提出了挖掘关联规则 的经典的算法一a p r i o r i 算法。，后来有不少学者对关联规则挖掘问题进行了 大量的研究，对原有a p r i o r i 算法进行优化，如引入哈希方法、划分的思想、随 机采样等，以提高算法挖掘规则的效率。但是，这些经典算法的挖掘对象主要是 存储在关系型数据库中的关系数据，而x m l 数据是半结构化的，不像关系数据 那样是严格的结构化数据。所以，目前比较流行的挖掘x m l 数据中关联规则的 方法一般是将x m l 数据模型映射到关系数据模型，然后再使用挖掘关系数据中 关联规则的挖掘方法进行挖掘，最后将得到的结果再映射到x m l 模式，在整个 挖掘过程中，需要将数据的模式进行两次转换，导致数据访问效率不高。 3 基于x m l 和w e b 数据的关联规则挖掘研究 为了解决上述问题，j a c k yw w w a n “。中提出了使用x q u e r y 从x m l 文档 中挖掘关联规则的方法，d a n i e l eb r a g a “。等使用了一个扩展的x q u e r y 来实现 从x m l 文档中挖掘关联规则。但是，目前使用x q u e r y 实现的关联规则挖掘算 法不适合挖掘结构复杂且不规则的x m l 文档，同时对数据量较大的x m l 文档的 挖掘效率也不高。 数据挖掘算法的挑战性在于其所面临的数据量巨大，算法的效率是关键，因 此有必要研究出占用内存小、i o 操作少、执行速度快的高效算法。本文针对 x q u e r y 实现的a p r i o r i 挖掘算法的局限性进行了改进，改进后的算法对x m l 数 据的挖掘效率得到了一定的提高。另外，本文也提出并且实现了一种更为高效的 对x m l 数据进行直接关联规则挖掘的方法，即使用n e t 的x m ld o m 实现的 a p d o r i 算法。这种方法不仅可以做出非常友好的挖掘交互界面，而且挖掘的速 度和效率都比较高。 1 3 论文的主要工作 本文研究的目标是如何对w e b 上海量的x m l 数据进行高效率的关联规则挖 掘，特别是对现有x q u e r y 实现的a p r i o r i 算法局限性的改进和使用n e td o m 挖掘x m l 数据中关联规则算法的实现。 论文首先讨论的是如何改进目前x q u e r y 实现的a p r i o d 算法，从而实现对 x m l 数据更为高效、灵活地直接关联规则挖掘。通过研究发现，现有的x q u e r y 实现的a p r i o r i 算法有两个局限：无法适应挖掘结构复杂不规则的x m l 文档和不 能适合挖掘大规模的x m l 数据。上述两个局限是使用x q u e r y 挖掘x m l 数据的 瓶颈，也是使用x q u e r y 挖掘x m l 数据不能获得突破性进展的绊脚石。论文对 x q u e r y 实现的a p r i o r i 算法作了比较深入的研究，针对上述两个局限分别作了相 应地改进。引入了标准文档模板的概念( 标准文档模板是一种结构规则、统一的 x m l 数据表示格式) ，与此同时对a p d o r i 算法内部的x q u e r y 代码实现作了不同 程度的修改和调整，使其充分适应对标准文档模板的挖掘。对于任何一个复杂不 规则的x m l 文档，都可以使用x s l t 将其转换为标准文档模板，而文档本身的 性质保持不变。也就是说，对标准文档模板的挖掘等效于对转换前的复杂不规则 的x m l 文档的挖掘。因此，改进后的算法通过对标准文档模板的关联规则挖掘， 间接实现了对转换前的结构复杂不规则的x m l 文档的关联规则挖掘。同时，论 文以实例分析和探讨了如何使用x s l t 将一个任意的复杂不规则的x m l 文档转 换成标准文档模板。而后，论文针对x q u e r y 实现的a p r i o r i 算法不适合挖掘大 规模x m l 数据的局限，在现有的x q u e r y 算法中引入了删除计数，通过在每次 计算频繁项集的同时删除那些对下次生成频繁项集不再起作用的项集，从而能够 4 基于x m l 和w e b 数据的关联规则挖掘研究 有效地减少挖掘过程中读取数据库时的比较次数和减小读入数据集的规模，从而 提高了算法挖掘大规模x m l 文档数据的效率，减少了挖掘过程所需的时间。 论文其次探讨的是如何使用n e td o m 对x m l 数据进行直接关联规则挖 掘。d o m 完全不同于x q u e r y ，它有着自身独特的优点。n e td o m 对x m l 的 操作采用了面向对象机制，用其实现的挖掘算法更符合人类的思维方式，更容易 理解。而且d o m 实现的a p r i o r i 算法是编译执行的，因此该算法的运行速度要 比x q u e r y 实现的算法快得多。此外，论文从电子商务网站的购物篮数据中抽取 了部分具有代表性的挖掘数据，将x q u e r y 和d o m 实现的两种挖掘算法分别应 用到具体的数据中，根据得到的挖掘结果对这两种算法的优缺点进行了对比分 析。结果表明，在不同的环境需求下，上述两种方法有着各自的强势和劣势，从 而指导我们在未来x m l 的关联规则挖掘过程中，应该根据不同的挖掘需求和挖 掘环境选择不同的挖掘方法，才能使数据挖掘的效率和性能得到优化。 论文最后提出了一种基于x m l 和关联规则挖掘的w e b 挖掘系统的五层架构 模型，对该模型的各个功能模块进行了详细地介绍。并且根据该模型，设计了一 个面向电子商务网站的基于x m l 的关联规则挖掘系统模块，将其开发成一个较 为实用的基于x m l 的w e b 关联规则挖掘工具。在系统挖掘功能的实现上，将挖 掘算法做成算法库嵌入到系统中，并且规范其调用接口，使其能够完成不同挖掘 环境下的关联规则的挖掘任务。 现将本文工作的要点总结如下： 研究分析了x m l 的数据表示格式和x q u e r y 查询语言，使用x q u e r y 实现了 传统的a p r i o r i 算法。 针对a p r i o r i 算法不适应挖掘复杂不规则x m l 文档的局限，本文提出了标准 文档模板的概念，与此同时对a p r i o r i 算法内部的x q u e r y 代码实现作了不同 程度的修改和调整，使其充分适应对标准文档模板的挖掘。其次介绍了如何 使用x s l t 将复杂不规则的x m l 文档转换为标准文档模板。通过将标准文 档模版作为a p r i o r i 算法的挖掘对象进行关联规则挖掘，从而实现对复杂不 规则x m l 文档的关联规则挖掘。 针对a p r i o r i 算法挖掘大规模x m l 数据的效率不高这一局限，对算法进行进 一步改进，在算法计算频繁项集的时候引入删除计数，能够在一定程度上减 少扫描数据库时的比较次数和每次读入内存的数据量，减少了c p u 的计算 时间，使改进后的算法更能适应挖掘大规模的x m l 数据。 深入分析了n e t 的x m ld o m 数据访问类接口，使用n e t 的x m ld o m 实现了更为高效的直接挖掘x m l 数据中关联规则的a p r i o r i 算法，并且对比 分析了x q u e r y 实现的a p r i o r i 算法和，n e td o m 实现的a p r i o r i 算法的性能、 5 基于x m l 和w e b 数据的关联规则挖掘研究 效率和优缺点。 提出了一种基于x m l 和关联规则挖掘的w e b 挖掘系统的五层架构模型，对 该模型的各个功能模块进行了详细地介绍。针对x m l 在模型中的一些重要 环节的作用进行了探讨。 设计了一个面向电子商务网站的基于x m l 的关联规则挖掘系统模块，并将 其开发成一个较为实用的基于x m l 的w e b 关联规则挖掘工具。在系统挖掘 功能的实现上，将挖掘算法做成算法库嵌入到系统中，并且规范其调用接口， 使其能够完成不同挖掘环境下的关联规则的挖掘任务。 1 。4 论文的安排 本文一共分为7 个章节以及附录，各章的内容介绍如下： 第1 章为引言部分，介绍了w e b 数据挖掘技术的研究背景、基于x m l 和 w e b 数据的关联规则挖掘的研究现状以及本文所做的主要工作和组织结构。 第2 章为数据挖掘技术简介，首先介绍了数据挖掘技术的发展历史、相关理 论和发展方向。其次介绍了关联规则挖掘的概念、目的和任务。最后描述了 几种挖掘x m l 数据的关联规则算法。 第3 章为基于x m l 的w e b 挖掘技术，首先介绍了x m l 的概念、组成、优 点以及基本的理论和技术。其次介绍了面向x m l 的数据挖掘技术的概念、 分类，以及挖掘x m l 数据的方法等。 第4 章为基于x q u e r y 和x s l t 的x m l 关联规则挖掘，首先从改进x q u e r y 算法效率出发，提出了标准文档模板的概念，同时改进x q u e r y 算法，使其 能够适应对复杂不规则x m l 数据的关联规则挖掘。其次在算法计算频繁项 集时引入了删除计数，减少了扫描数据库时的比较次数和每次读入内存的数 据量，减少了c p u 的计算时间，使改进后的算法更能适应挖掘大规模的x m l 数据。 第5 章为基于n e td o m 的x m l 关联规则挖掘，首先分析了n e t 的x m l d o m 数据访问类接口，其次使用n e t 的x m ld o m 实现了更为高效的挖掘 x m l 数据中关联规则的a p r i o r i 算法，最后对比分析了x q u e r y 实现的a p r i o r i 算法和n e td o m 实现的a p r i o r i 算法的性能、效率和优缺点。 第6 章为基于x m l 的关联规则挖掘在电子商务中的应用，首先提出了一种 基于x m l 和关联规则挖掘的w e b 挖掘系统的五层架构模型，对该模型的各 个功能模块进行了详细地介绍。其次根据该模型，设计了一个面向电子商务 网站的基于x m l 的关联规则挖掘系统模块，将其开发成一个较为实用的基 于x m l 的w e b 关联规则挖掘工具。在系统挖掘功能的实现上，将挖掘算法 6 基于x m l 和w e b 数据的关联规则挖掘研究 做成算法库嵌入到系统中，并且规范其调用接口，使其能够完成不同挖掘环 境下的关联规则的挖掘任务。 第7 章为总结与展望，对本文所做的工作进行了总结，并对进一步的工作做 了展望。 7 基于x m l 和w e b 数据的关联规则挖掘研究 第2 章数据挖掘技术简介 随着计算机硬件和软件的飞速发展，尤其是数据库技术和互联网络的日益普 及，人们面临着快速扩张的数据海洋，如何有效利用这一丰富的数据海洋的宝藏 为人类服务，业已成为广大信息技术工作者所关注的焦点之一。为有效解决“数 据丰富但知识匮乏”这一问题，自二十世纪9 0 年代开始，数据挖掘技术逐步发 展起来，并且显示了强大的生命力。 2 - 1 数据挖掘技术概述 随着数据库的广泛应用和海量数据的迅速增长，仅仅对数据进行简单的查询 和检索已经不能满足人们对数据库应用的需求。简单的查询和检索不能帮助用户 从数据中提取带有结论性的有用信息，也不能充分地发掘和利用数据库中蕴藏的 丰富知识，从而导致大量有用信息的浪费。数据挖掘技术正是为了解决这一问题 而产生并且迅速发展起来的用于挖掘海量数据中有用信息的数据处理技术。 从技术上讲，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用 信息和知识的过程。从应用上讲，数据挖掘其实就是一种新的商业处理技术，其 主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化 处理，从中提取辅助商业决策的关键性数据“。 数据挖掘的过程一般分为三个阶段：数据准备、数据挖掘和知识的确认与提 炼，并且根据挖掘的结果不同，这一个过程可以反复执行”。过程如图2 - 1 所示： 图2 一l 知识发现过程的反复性 8 基于x m l 和w e b 数据的关联规则挖掘研究 2 1 1 数据挖掘技术的发展历史 数据挖掘，又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， 简称k d d ) ，它是一个从大量数据中抽取挖掘出未知的，有价值的模式或规律等 知识的复杂过程9 。k d d 一词首次出现在1 9 8 9 年8 月举行的第十一届国际联合 人工智能学术会议上“。到目前为止，由美国人工智能协会主办的k d d 国际研 讨会的规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方 法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗 透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算 机科学研究领域的一大熟点。 国内学术界对数据挖掘的研究与国外相比起步稍晚。国家自然科学基金在 1 9 9 3 年才首次支持该领域的研究项目。目前，数据挖掘的基础理论及其应用研 究在国内的许多科研单位和高等院校竞相开展，深入地进行研究模糊方法在知识 发现中的应用、数据立方体代数、关联规则挖掘、非结构化数据的挖掘以及w e b 数据挖掘等。 数据挖掘的趋势是向着开放的、标准化和与w e b 等应用紧密结合的方面发 展。数据挖掘协会。发布了基于x m l 的预言模型标准p m m l 的2 0 版；从1 9 9 9 年开始s i g k d d 开始设立w e b kd d 研讨组，讨论数据挖掘技术在互联网上的 应用：2 0 0 1 年s l g k d d 又设立了b l o k d d 研讨组，研究数据挖掘技术在生物信 息学中的应用。 数据挖掘技术有着广阔的应用背景，所以在工业界和学术界都得到了普遍的 关注，如微软、i b m 等很多国外公司和大学等研究机构，都投入了大量人力物力 进行数据挖掘的研究工作，研究的主要目标是发展有关数据挖掘的方法论、理论 和工具，以支持从大量数据中提取有用的和让人感兴趣的知识和模式，并进行工 具的开发。 数据挖掘作为知识开发和创新的数学工具可以广泛地应用于金融、市场开 发、医疗诊断决策、交通管理、企业业绩评估等众多的社会信息化领域，以此提 高上述行业数据分析的可靠性和精确度。据有关专家预测，在未来十年内，随着 数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。 2 1 2 数据挖掘技术的主要任务 数据挖掘的目标主要是指在指定数据挖掘任务中要找的模式类型。数据挖掘 通过预测数据中包含的知识和信息的未来趋势及行为，做出前瞻的、基于知识的 9 基于x m l 和w e b 数据的关联规则挖掘研究 决策和预测。一般地，数据挖掘的任务可以分为两类：描述和预测，主要分为以 下几个方面”“： 概念类描述 概念描述就是对某类对象的内涵进行描述并概括逾期有关的特征。通常，概 念描述包括区别性描述和特征性描述。特征性描述的是某类对象的共同特征，区 别性描述的是不同类对象之间的区别。 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的取 值重复出现且概率很高时，它就可能存在某种关联，可以建立起这些数据项的关 联规则。关联分析的目的是要找出数据中隐藏的关联关系网。 分类 分类在数据挖掘中的应用比较多，它是找出一个代表一类数据的整体信息的 概念性描述，也就是类的内涵描述。分类通常使用规则或者决策树模型表示。 聚类分析 聚类就是将数据库中的记录划分为一系列有意义的子集。聚类增强了人们对 客观现实的认识，是概念描述和偏差分析的先决条件。聚类分析是一种多元统计 方法，是当代分类学与多元分析的结合。根据事物彼此不同的属性进行辨认，将 具有相似属性的事物聚为一类，使同一类事物具有高度的相似性。 偏差预测 偏差预测是指从数据分析中发现数据库中存在的一些异常数据，从而引起人 们的注意。偏差包括很多有用的知识，如：分类中的反常实例、模式的例外、观 察结果对模型预测的偏差、量值随时间的变化等。通常情况下，采用寻找观察结 果与参照之间的差别的方法进行偏差预测。 自动趋势预测 数据挖掘能自动在大型数据库中寻找潜在的预测性信息。以往需要很多专家 进行手工分析的问题，现如今可以迅速直接地从数据本身中得出结论。市场的 目标驱动营销就是一个利用数据挖掘进行预测的例子。数据挖掘可以根据过去 有关营销的大量数据来寻找未来投资中回报最大的客户。 2 1 3 数据挖掘研究的发展方向 目前，数据挖掘已经成为数据库研究、开发和应用领域中的焦点之一。数据 挖掘技术有着广阔的应用背景，涉及到了计算机科学的诸多领域，包括数据库技 术、人工智能、模式识别等。随着这些领域的不断发展，数据挖掘技术也会随之 更加成熟起来，数据挖掘的研究将会形成更大的高潮，研究与开发的焦点可能会 1 0 基于x m l 和w e b 数据的关联规则挖掘研究 集中在以下几个方面1 4 1 ： 开发专门用于知识发现的数据挖掘语言：类似于其他的高级语言，高层次的 数据挖掘语言应该能够允许用户定制特殊的数据挖掘任务。 研究可视化、形象化的数据挖掘过程：使知识发现的过程能被用户理解，也 便于在知识发现的过程中进行人机交互。 复杂数据的处理：目前数据挖掘的主要方面是关联性和事务性的数据，但是 对于半结构化以及非结构化的数据进行挖掘，也是一个非常重要而极富挑战 性的方面。 高性能的数据挖掘算法：高效性和可伸缩性一直都是数据挖掘算法追求的目 标，随着并行的、分布式的以及增长式的数据挖掘技术的发展，这种趋势将 会继续得到发展和强化。 研究在网络环境下的数据挖掘技术：在互联网上建立数据挖掘服务器，使之 与传统的数据库服务器配合，实现在线的、联机的网络数据挖掘。 2 2w 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 的用户访问信息中发现人们感兴趣的，有价值的信息或知识的过程。通 常根据挖掘对象的不同，可以将基于w e b 的挖掘分为w e b 内容挖掘、w e b 结构挖 掘和w e b 日志挖掘“。如图2 - 2 所示： 基于x m l 和w e b 数据的关联规则挖掘研究 图2 2w 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 日志挖掘方面的研究 方向主要有两个：一般性访问模式挖掘和个性化使用记录挖掘。 2 3 关联规则挖掘 关联规则挖掘是数据挖掘领域一个重要研究方向之一。关联规则的概念最早 是由a g r a w a l 等人在1 9 9 3 年提出的 4 ，其目的是为了发现数据集合中不同域或 属性之间的关系规则。之后很多学者开始对关联规则的挖掘进行了广泛而深入的 研究和探索，在原有算法的基础上进行了诸多改进，也提出了很多新的关联规则 挖掘算法。 1 2 基于x m l 和w e b 数据的关联规则挖掘研究 2 3 1 关联规则的定义 关联规则挖掘的任务就是给定一个事务数据库d ，在基于支持度、可信度的 框架中，发现大量数据中的各个项目之间有趣的相关性，生成所有的支持度和可 信度分别高于用户给定的最小支持度和最小可信度的关联规则。a g r a w a l 等在 1 9 9 4 年设计了著名的a p d o r i 算法”。，这是一个基于两阶段频繁集思想的方法， 关联规则算法的设计可以分解为两个步骤： 1 ) 找到所有支持度大于或等于最小支持度的项集，即频繁项集。 2 ) 使用第1 步中找到的频繁项集，产生期望的关联规则。 对于如表2 - 1 中的数据表示的一个典型的事务数据库，关联规则的挖掘问题 可以进行如下的形式化描述”。： 事务数据i d商品 1 号购物篮 p e n ，n o t e b o o k ，p e n s i l eb o x ) 2 号购物篮 p e n n o t e b o o k ，p e n s i l eb o x ，i n k 3 号购物篮 i n k ，m i l k ) 4 号购物篮 p e n ，n o t e b o o k ，p e n s i l eb o x ，i n k ，m i l k ，p a p e r , e r a s e r ) 5 号购物篮 p e n ，i n k n o t e b o o k 表2 一l 一个事务数据库 设，2 之，) 是n 个不同项的集合，d 是基于j 的事务数据库。d 中的一 个事务是一个项集，它包含若干个，中的项，r ，。每个事务都对应一个标识 符t i d 。与关联规则相关的定义如下： 定义l 关联规则 形如z _ y 的蕴涵式，满足工，y c l 并且x n y = a 。 定义2 支持度 在事务数据库d 中，如果有j 的事务包含了x u y ，那么关联规则的支持 度为s 。 定义3 置信度 在事务数据库d 中，如果包含x 的事务中有c 同时也包含了r ，那么关联 规则x = y 的置信度为c 。 定义4 强规则 如果关联规则x _ y 同时满足最小支持度阈值，则z - y 为强规则。 定义5 频繁项集 1 3 基于x m l 和w e b 数据的关联规则挖掘研究 项集是项的集合，频繁项集就是其支持度大于或等于最小支持度的项集。 以表2 1 的事务数据库为例，关联规则“p e n ，n o t e b o o k = p e n s i i eb o x ”的支 持度和置信度分别是0 6 和0 7 5 。它意味着购买钢笔和笔记本的顾客在其7 5 的购买行为中也购买了铅笔盒，而同时购买钢笔、笔记本和铅笔盒的行为占了事 务数据库中所有购买行为的6 0 。 通常，从事务数据库中可以挖掘出大量的关联规则，但是并不是所有的关联 规则都是有价值的。针对挖掘出的关联规则，用户会根据经验和测评预先设定最 小支持度和最小置信度。只有当关联规则同时满足支持度大于或等于最小支持 度，置信度大于或等于最小置信度时，它才是有价值的。 2 3 2 关联规则的经典挖掘算法 关联规则的挖掘通常分解为两个子方向来解决：从事务数据库中找出所有频 繁集和从频繁集中生成强关联规则。 由于从频繁集中生成强关联规则的算法相对比较简单，因此大量的