（控制理论与控制工程专业论文）基于关联规则挖掘的kdd的研究.pdf

华中科技大学硕士学位论文 摘要 i 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a b b l e ，简称k d d ) ，就是 从数据中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的高级 过程。k d d 作为新的决策支持技术，从人工智能领域的机器学习发展而来，既 是信息科学的前沿课题，也是一个融合了多个研究领域的理论和实践问题。其 中，关联规则数据挖掘为发现数据之间潜在的联系提供了一种有效的机制，是 k d d 中比较成熟、重要和活跃的研究内容。j 首先，本文就k d d 的起源、概念、处理过程和研究现状进行了综述，并且 简单介绍了几种主要的k d d 技术。作为的研究重点，关联规则数据挖掘问题被 提出，并且得到了详细的阐述。就如何解决关联规则挖掘问题本文介绍了三种 经典算法：a i s 算法、a p d o f i 算法和d i c 算法。其中，a 砸o r i 算法对候选集进 行剪枝大大减少了候选项目集的数量和计算时间，是关联规则挖掘算法中最 具影响的一种。 随后，在经典关联规则算法的基础上，本文提出了一种数据集划分算法 d p a r m 。d p a r m 利用数据集中存在的概念层次对数据集进行划分，并分别从 划分形成的数据块中进行关联规则的挖掘。通过实验得到以下结论：1 ) 随着数 据量的增大，该算法的挖掘效率优于a p f i o d 算法；2 ) 数据集划分的精度越高， 该算法的挖掘效率越高。由于该算法比较占用系统内存，本文进一步指出了并 行处理的改进思路。 最后，就如何在关系数据库中实现关联规则的挖掘问题，本文提出了一个 基于数据集市的关联规则挖掘系统，阐述了系统的框架结构和各部分实现中的 关键技术。 关键词：数据慝嘞知识发现；数据挖掘：关联规则挖掘；a p f i o f i 算法； d p a r m 算法：数字关族规则挖掘 华中科技大学硕士学位论文 a b s t r a c t k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ( k d d ) i st h en o n t r i v i a l p r o c e s s o f i d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si n d a t a a san e wt e c h n o l o g yo fd e c i s i o ns u p p o r ts y s t e m ，i tw a sd e v e l o p e df r o ma b r a n c ho fa in a m e dm a c h i n el e a r n i n g k d di sn o to n l ya na d v a n c e dd i r e c t i o no f i n f o r m a t i o ns c i e n c e ，b u ta l s oas y n c r e t i cp r o b l e mo fm u l t if i e l d si nt h e o r ya n d p r a c t i c e c o m p a r e dw i t h o t h e rk d d t e c h n o l o g i e s ，a s s o c i a t i o nr u l e sm i n i n gi s a m u c hm o r em a t u r e ，m o r ei m p o r t a n ta n dm o r ea c t i v er e s e a r c hd i r e c t i o n i tp r o v i d e s a t 2e f f e c tm e c h a n i s mt od i s c o v e rt h ep o t e n t i a la s s o c i a t i o ni nd a t a a tf i r s t ，t h i sp a p e rp r e s e n t st h eo r i g i n ，t h ec o n c e p t ，t h ep m s e s s i n ga p p r o a c ha n d t h er e s e a r c hs t a t u sa b o u tk d d a n ds o m em a i nt e c h n o l o 百e so fk d dh a v eb e e n i n t r o d u c e ds u m m a r i l y a st h er e s e a r c hf o c u so f t h i sp a p e r , a s s o c i a t i o nr u l e sp r o b l e m h a sb e e nd e s c r i b e di nd e t a i l t h e n ，t h r e et y p i c a la l g o r i t h m so fa s s o c i a t i o nr u l e s m i n i n g h a v eb e e nr e c o m m e n d e d ：a i s ，a p r i o r i ，d i c a m o n gt h e s e a l g o t i t h m s ， a p r i o f ii s t h em o s ts u c c e s s f u lb e c a u s et h r o u g ht h ep r u n i n gf o rc a n d i d a t ei t e m s ，i t r e d u c e st h en u m b e ro fc a n d i d a t ei t e m sa n ds h o r t e n st h et i m eo fc a l c u l a t i o ng r e a t l y t h e n ，o n t h eb a s eo f t y p i c a la s s o c i a t i o nr u l e sa l g o r i t h m s ，t h i sp a p e rp r o v i d e s a nd a t a s e t sp a r t i t i o na l g o r i t h mn a m e dd p a r m i t p a r t i t i o n sd a t ai t e m s i n t os m a l ld a t a b l o c k sb yt h ec o n c e p tl e v e l se x i s t i n gi nd a t ai t e m s ，a n dt h e nm i n e st h ea s s o c i a t i o n r u l e si ne a c hd a t ap a r t i t i o nb l o c k t h et e s tr e s u l t so ft h i sa l g o d t h mp r o v e ：1 ) b y i n c r e a s i n g t h ed a t ai t e m s d p a r mi sm o r ea n dm o r ev a l i dt h a na p r i o r i 2 ) t h ed a t a m i n i n ge f f i c i e n c yw i l lb eh i g h e ri fi n c r e a s i n gt h ep r e c i s i o no f d a t a p a r t i t i o n f u r t h e r ， 华中科技大学硕士学位论文 t h ei m p r o v e dt h o u g h to fp a r a l t e lp r o c e s s i n gi sp o i n t e do u tt ot r e a tt h ep r o b l e mt h a t t h ee x e c u t i o no fd p a r m a l g o r i t h m n e e d s 狂l o r em e m o r y a tl a s t ，f o rt h e p r o b l e m t h a th o wt or e a l i z ea s s o c i a t i o nr u l e sm i n i n gi n r d b m s ，a nq u a n t i t m i v ea s s o c i a t i o nr u l e sm i m i n gs y s t e m h a sb e e ng i v e nb a s e do r l ：d a t a m a r k e t 。n e 舾m es t r u c t u r ea n dt h ek e yt e c h n o l o g i e so ft h es y s t e mh a v eb e e n d e s c r i b e d i nd e t a i l k e yw o r d s ：k n o m e d g ed i s c o v e r y i nd a t a b a s e s ( d ) ；d a t a m “n g ( d m ) ； a s s o c i a t i o nr u l e sm i n i n g ( a r m ) ；a 研。娃a l g o r i t h m ；d p a r m a l g o r i t h mq u a n t i t a t i v ea s s o c i a t i o nr u l e sm i n i n g i i i 华中科技大学硕士学位论文 1绪论 数据库技术和数据库管理系统的广泛发展，使全球范围内数据库中存储的 数据量急剧增大。有些公司日积月累下来的商业数据目前己达到千万条记录。 有些面向科学研究的数据库的数据量更是惊人，如记录天体信息的数据库容量 达到t b 级( i t b = 1 0 6 m b ) 。因此，人们越来越重视对数据更深入的分析和科学研 究，以得到数据总体特征以及对发展趋势的预测来辅助决策。例如：超市的经 营者希望经常被同时购买的商品放在一起，以增加销售；保险公司想知道购买 保险的客户一般具有哪些特征；医学研究人员希望从已有的成千上万份病例中 找出患某种疾病的病人的共同特征。对于以上问题，现有的管理信息中数据分 析工具无法给出答案。数据库知识发现( 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 s ，简称 k d d ) 就是应这种需要产生并迅速发展起来的一门技术，是用于开发信息资源 的一种新的数据分析技术。 本文结合了k d d 研究方面的发展，对k d d 中的关联规则挖掘问题进行了 详细的介绍，深入地研究了关联规则挖掘算法，并且提出了一个基于数据集市 的关联规则挖掘系统。 1 1k d d 综述 1 1 1 k d d 的起源和研究现状 k d d 是应用需求推动下数据库技术、人工智能等多种学科融合的结果【l “。 首先是数据库技术。随着数据库技术的不断发展及数据库管理系统的广泛 应用，大型数据库系统已经在各行各业普及，数据库中存储的数据量急剧增大。 在大量的数据背后隐藏着许多重要信息，而这些重要信息可以很好地支持人们 的决策。可是目前用于对这些数据进行分析处理的工具却很少。目前人们用到 的主要是数据库的存储功能，而隐藏在这些数据之后的更重要的信息则没有充 华中科技大学硕士学位论文 分利用。这些信息是关于数据的整体特征的描述及对发展趋势的预测，在决策 生成的过程中具有重要的参考价值。 其次，在数据库技术飞速发展的同时，人工智能领域机器学习的研究也取得 很大进展。机器学习的研究先后经历了神经模型和决策理论、概念符号获取及 知识加强和论域专用学习三个阶段，根据人类学习的不同模式人们提出了很多 机器学习方法，如：实例学习、观察和发现学习、神经网络和遗传算法等等。 一些常用且较成熟的算法已被人们用于实际的应用系统及智能计算机的设计和 实现中。k d d 中的许多挖掘技术就来源于机器学习【5 1 。 最后，是应用领域的推动。由于数据存储技术的日渐成熟，数据库和联机 事务处理( o l l l p ) 已经被广泛应用于金融、证券、保险、销售以及天气预报、工 业生产、分子生物学、基因工程研究等各行各业【6 - 8 】。大量的数据被积累，而且 还有更多的数据正产生着。对于这些数据，人们已经不满足于传统的统计分析 手段，而需要发现更深层次的规律，提供更有效的决策支持。目前k d d 在货篮 数据( b a s k e td a t a ) 分析、金融风险预测、产品产量、质量分析、分子生物学、 基因工程研究、i n t e m e t 站点访问模式发现以及信息搜索和分类等许多领域得到 了成功的应用【9 - 乃j 。 “深蓝”计算机( d e e pb l u e ) 自g 够战胜人类国际象棋世界冠 军，成功的一个重要因素是具有知识发现能力，能从存储了7 0 万盘棋谱的数据 库中提取有用的知识1 1 4 1 ；如果你通过i n t e m e t 访问著名的亚马逊网上书店，会发 现当你选中一本书后，会出现“该书的购买者中有百分之x x 同时购买了x x 书” 的推荐。可见，k d d 已经步入人们日常生活。 因此，k d d 是应用需求推动下跨学科发展的产物。由于k d d 不但能够学 习已有的知识，而且能够发现未知的知识。得到的知识是“显式”的，既能为 人所理解，又便于存储和应用，因此一出现就得到广泛的重视。 目前，k d d 的深入研究主要有以下几方面【1 4 _ 1 9 j ： 1 ) 基础理论研究。因为k d d 的理论体系尚不完整，还没有形成- - f 独立 的学科。在1 9 9 9 年的k d d 年会上，有关专家提出要加强k d d 的理论研究，使 之成为一种主流技术。 2 华中科技大学硕士学位论文 2 ) k d d 技术和算法的研究。包括新技术在k d d 中的应用、算法的改进与 优化、并行算法的设计与实现。此外，k d d 往往直接面对的是现实数据，因此 对不完整、不确定或有噪声的数据进行处理也是k d d 必须解决的问题 3 ) 应用领域的拓展。这是推动k d d 发展的根本动力。一方面，k d d 需要 向更多的应用领域渗透。另一方面，需要开发更多面向应用的k d d 系统和产品。 建立行业内的数据标准和通用挖掘平台、建立可交换信息、共享知识的通用数 j 据仓库是今后要解决的问题。 到目前为止，国际k d d 年会( 1 9 9 3 年以前是研讨会，1 9 9 5 年后每年一次) 已经召开了8 届，参加会议人数从1 9 8 9 年研讨会的3 0 人增加到1 9 9 9 年的6 0 0 人。k d d 9 9 的论文收录比例大致是1 0 ：1 。1 9 9 3 年i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 率先出版了k d d 专刊。随后，各类k d d 会议、研讨会纷纷涌现， 许多领域的国际会议也将k d d 列为专题讨论。与此同时，许多著名的计算机公 司开始开发尝试k d d 软件的开发。比较典型的如s a s 公司的e n t e r p r i s em i n e r i b m 公司的i n t e l l i g e mm i n e r s g i 公司的s e t m i n e r ，s p s s 公司的c l e m e n t i n e 等。 1 9 9 9 年以后，i e e e 和a c m 多次推出k d d 专刊，介绍k d d 在各个领域的应 用成果。 总之，k d d 在当今的信息时代的发展前景是非常广阔的。 1 1 2 k d d 的基本概念和处理过程 。 k d d 是包含了数据准备、数据挖掘等环节的循环往复过程。数据挖掘( d a t a m i n i n g ) ，又称为数据采掘、数据开采等，是k d d 的一个环节，采用具体的数 据挖掘算法从数据中自动高效地提取有用模式的过程。许多专家都给出了有关 k d d 的定义，在k d d 研究领域一致认可的描述性定义是f a y y a d 等人给出的【2 0 】， 定义1 1 ： k n o w l e d g ed i s c o v e r y i nd a t a b a s e si st h en o n t r i v i a l p r o c e s so f i d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l e p a r e m si nd a t a 数据库中的知识发现是从数据中识别出有效的、新颖的、 3 华中科技大学硕士学位论文 潜在有用的，以及最终可理解的模式的高级过程。 其中： 数据：是指一个有关事实，的集合，它是用来描述事物有关方面的信息， 是我们进一步发现知识的原材料。 有效性：是指发现的模式应用于新的数据时要具有一定的可信度。 新颖性：要求发现的模式应该是新的、用户未知的或未预料到的。 潜在有用：提取出的模式应该是有意义的，发现的知识将来具有实际效用。 可被人理解：k d d 的一个目标就是将数据库中隐含的模式以容易被人理解 的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。 模式：对于集合f 中的数据，可以用语言工来描述其中数据的特性。 高级过程：k d d 包括数据准备、数据挖掘、知识评价等多个阶段，以及上 述过程的反复求精。该过程是非平凡的、高级的，是指整个过程是自动的、智 能的，对数据进行更深层处理的过程，而不是仅仅对数据进行加减求和等简单 运算或查询。因此说它是一个高级的过程，也称为不平凡的过程。 在k d d 中模式的有效性、新颖性、潜在有用性和最终可理解性综合在一起 称为兴趣度( i n t e r e s t i n g n e s s ) 【2 “。 k d d 过程是一个与用户不断交互的循环往复过程，可划分为数据准备、数 据挖掘与知识的解释和评价三个环节。用户可以与k d d 的任何一个环节进行交 互，并可以在任何时候返回到前面的环节重新开始整个过程，实现对k d d 过程 的指导和控制。k d d 的整个过程如图1 1 所示。 数据准备 数据准备主要包含三个过程：数据选择抽样( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据转换( d a t at r a n s f o r m a t i o n ) 。数据选择抽样确定k d d 的操作对象，即目标数据( t a r g e t d a t a ) ，并根据用户的需要从原始数据库中选择 或抽样一部分数据；数据预处理一般包括消除噪声、缺值数据处理、消除重复 和错误数据和数据类型的转换( 如把连续型数据转换为离散型数据便于关联规 则挖掘【1 8 】，或把离散型数据转换为连续型数据以便于构造神经网络) 等；数据 4 华中科技大学硕士学位论文 转换的主要目的是消减数据的维数( d i m e n s i o nr e d u c t i o n ) ，选择出对数据挖掘真 正有用的数据特征以减少数据挖掘时需要计算的特征数，提高数据挖掘的效率。 图1 ik d d 的处理过程 数据挖掘 数据挖掘就是根据k d d 的任务或目的( 如数据总结、分类、聚类、关联规 则挖掘或序列模式发现等) ，选取相应算法从数据中挖掘出有关信息和知识。数 据挖掘是k d d 过程中最复杂、研究最多的环节，数据挖掘的效率和有效性直接 影响整个k d d 过程的效率和挖掘结果的兴趣度。 解释评价 挖掘得到的模式，有可能是没有实际意义或没有实用价值的，也有可能不 能准确反映数据的真实意义，因此需要对数据挖掘所发现的模式进行修剪和评 估，去除冗余的、用户不感兴趣的模式，并将最终的挖掘结果转换成用户容易 理解的形式或用各种可视化方法加以显示( 如各种图表方式、图文方式、图形 方式、自然语言方式等) 1 1 9 。 11 3 主要的k d d 技术介绍 k d d 是从人工智能领域的一个分支机器学习发展而来的，因此机器学 习、模式识别、人工智能领域的常规技术，如聚类( c l u s t e r i n g ) 、决策树( d e c i s i o nt r e e ) 、 5 华中科技大学硕士学位论文 统计等方法经过改进，大都可以应用予知识发现，馒德k d d 技术星现各种各样 的形式。 近年来 孛经网络、糕糙集理论、关联规则等技术在数据挖掘中的应用发展 很快；可援化技术受到越来越多的璧视：w e b 挖掘是随着两络的发展两趣观舱 一个新兴研究方向。 人工神经两络 入工神经网络在知识获取方面有先天的不足。出于弹经网络的知识获取过 程是个“鬈箱”系统，得到的知识也是以权值形式存在的黪式知识，因此难 以为入所理解2 朝。但是，人们在寻找新的知识获取手段的罔翳并没有放弃人工 神经网络。在数据挖掘中，对神经鄹络静改进重点是解决两个闷题：知识表达 和知识获取 2 3 , 2 4 1 。 知识表达( k n o w l e d g er e p r e s e n t a t i o n ) 是往神经两络中抽象的枚值代袁定的 知识，例如傻权值代表兢劂莳编码，这样在阏络训练结束后，通过解码就可以 得到规剡。这种方法已经在d n a 结构分析、自然语亩处理的语法规则提取和化 学反应的预测中得到应用。 知识提取( k n o w l e d g ee x t r a c t i o n ) 是给定个已经谢练好的神经网络，扶中提 取显式的知识( 一般是符号形式) 。知识提取麓方法分麓自盒法( o p e nb o x ) 和黧 盒法( c l o s e d - b o x ) 。自愈法是考察神经网络内部的每个神经元，找出萁中的联系 与规待；黑盒法是不篱神经黯络内部结构，哭考察网络的输出与输入间的联系。 般米说，自盒法更适合于理论分析，黑盒法受便于实际应用。 从数据挖掘韵角度对入工神经网络进行研究的方向主要商鼹个：个是研 究崮更好的知识提取方法，另一个建设计新的网络，使耪经网终中舱隐含知识 更容易解码。 粗糙集理论 糖髓集理论是静研究不耩赡、不磷定髌知识的数学工具，由波兰科学容 z 。p a w l a k 在1 9 8 2 年嚣先提出 2 5 1 。船识工程研究中，一壹存在着信息的含糊缝 ( v a g u e n e s s ) 等阗题，含糨性有三种：术语韵模糊性，如高矮；数疆的不确定 6 华中科技大学硕士学位论文 性，如噪声引起的；知识自身的不确定性，如规则的前后件间的依赖关系并不 是完全可靠的。人工智能的基础理论之一经典逻辑不足以解决这些不确定性问 题。为此，人们提出了一些解决方法，包括统计方法、模糊集理论，以及 d e m p s t e r s h a f f e r 证据理论，但这些方法都有一些内在缺陷或限定范围。相比之 下，粗糙集方法则有几个优点：不需要预先知道的额外信息；算法简单、易于 操作。 ? 随着数据挖掘的兴起，粗糙集理论也受到数据挖掘研究者的重视进而受到 研究界的广为注意 2 5 3 0 1 。粗糙集和数据挖掘关系密切，它为数据挖掘提供了一 种新的方法和工具。首先，数据挖掘研究的实施对象多为关系型数据库。关系 表可被看作为粗糙集理论中的决策表，这给粗糙集方法的应用带来极大的方便。 第二，现实世界中的规则有确定性的，也有不确定性的。从数据库中发现不确 定性的知识，为粗糙集方法提供了用武之地。第三，从数据中发现异常，排除 知识发现过程中的噪声干扰也是粗糙集方法的特长。第四，运用粗糙集方法得 到的知识发现算法有利于并行执行，这可极大地提高发现效率。对于大规模数 据库中的知识发现来说，这正是求之不得的。第五，数据挖掘中采用的其它技 术，如神经网络的方法，不能自动地选择合适的属性集，而利用粗糙集方法进 行预处理，去掉多余属性，可提高发现效率，降低错误率。第六，粗糙集方法 比神经网络方法在得到的决策规则和推理过程方面更易于证实和检测。 w e b 挖掘 近年来，i n t e m e t 正以令人难以置信的速度在飞速发展，越来越多的机构、团 体和个人在i n t e m e t 上发布信息、查找信息。虽然i n t e m e t 上有海量的数据，但由 于w e b 是无结构的、动态的，并且w e b 页面的复杂程度远远超过了文本文档，人 们要想找到自己想要的数据犹如大海捞针一般。信息检索界开发了许多搜索引 擎，但其覆盖率有限，因此查全率低，一般的搜索引擎是基于关键字的查询，命中率 较低，另外不能针对特定的用户给出特殊的服务，因为每个人感兴趣的东西是不 一样的，因此不具有个性化。解决这些问题的一个途径，就是将传统的数据挖掘技 术和w e b 结合起来，进行w e b 挖掘p “。 7 华中科技大学硕士学位论文 w e b 挖掘就是从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和 隐藏的信息。w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘， 确定权威页面，w e b 文档分类，w e bl o g 挖掘、智能查询，建立m e t a w e b 数据仓 库等。 我们可以将w e b 挖掘一般地定义为：从与w w w 相关的资源和行为中抽取 感兴趣的、有用的模式和隐含信息。一般地，w e b 挖掘可分为3 类：w e b 内容挖 掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs 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 ) 。 w e b 内容挖掘是从文档内容或其描述中抽取知识的过程。w e b 文档文本内 容的挖掘，基于概念索引的资源发现，以及基于代理的技术都属于这一类。w e b 内 容挖掘有两种策略：直接挖掘文档的内容，或在其它工具搜索的基础上进行改进。 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识。由于文档之 间的互连，w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页 面进行排序，发现重要的页面。 w e b 使用记录挖掘的主要目标则是从w e b 的访问记录中抽取感兴趣的模 式。w w w 中的每个服务器都保留了访问日志( w e ba c c e s sl o g ) ，记录了关于用户 访问和交互的信息分析这些数据可以帮助理解用户的行为，从而改进站点的结 构，或为用户提供个性化的服务。这方面的研究主要有两个方向：一般的访问模 式追踪和个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录来了 解用户的访问模式和倾向，以改进站点的组织结构；而个性化的使用记录追踪则 倾向于分析单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提 - 一 供定制的站点。 w e b 挖掘是一个较新的研究领域，有许多问题有待于进一步的研究和深化。 未来随着x m l 的兴起，w e b 页面会蕴涵更多的结构化和语义信息，这会使w e b 挖掘工作变得更为有效，也更为容易。同时w e b 文档的自动分类、多层次w e b 信 息库的建立以及w e bl o g 挖掘仍然会是w e b 挖掘的主题。 8 华中科技大学硕士学位论文 1 2 关联规则挖掘 关联规则挖掘作为一种重要的数据挖掘技术，目前已经成为了数据挖掘研 究的重要内容。对关联规则挖掘问题的研究是由a g r a w a l 等人在1 9 9 3 年提出来， 并给出了关联规则挖掘的a i s 算法【3 2 】。最初是希望从存储商品销售数据的事务 数据库中挖掘出反应有关顾客购买行为的知识，以指导商业决策。事务数据库 中的每条事务记录了顾客在商场或超市中一次购物的交易内容( 商品的种类、 数量等信息) 。关联规则挖掘考察每位顾客购物的交易内容，从而发现类似于“一 些商品j 另一些商品”形式的规则，称之为关联规则。本文的第二章对关联规则 挖掘问题进行了详细的描述。 根据关联规则挖掘数据集的不同，可以将关联规则挖掘技术分为两大类： 布尔关联规则挖掘技术和数值关联规则挖掘技术。布尔关联规则挖掘技术研究 仅包含二值属性的数据集中的关联规则挖掘，数值关联规则挖掘技术研究包含 多值属性或连续属性的数据集中的关联规则挖掘。 12 1 布尔关联规则挖掘技术 布尔关联规则挖掘技术研究仅包含二值属性的数据集的关联规则挖掘，挖 掘对象是事务数据库中的布尔型数据集，主要的任务是如何提高算法的挖掘效 率。影响布尔关联规则挖掘算法效率的主要因素有算法需要扫描数据集的次 数、需要计算支持率的项目集( 称为候选项目集) 的多少等。层次算法在修剪 候选项目集上比较有效，典型的层次算法主要是a p r i o r i 【3 引。数据集划分算法主 要从减少扫描数据集的次数着手，d i c 就是较典型的数据集划分算法【3 4 1 。本文 将在第三章详细描述典型的布尔关联规则挖掘算法a i s 、d i c 和a p r i o r i 。根据 数据集中存在的概念层，将数据集中所有项目分类，并根据各个项目类别对数 据集中的所有事务进行划分，最后将数据集划分成各个数据块。根据上述的概 念层分类思想，本文第四章提出了数据集划分算法d p a r m 及对其进行并行处 理改进的思路。 9 华中科技大学硕士学位论文 1 2 2 数值关联规则挖掘技术 关系数据库的广泛应用，使对关系数据库的数据挖掘变得越来越迫切。关 系数据库中数据集的数据类型主要是连续的或多值的非二值属性。如何对关系 数据库中的关系数据集应用布尔关联规则算法挖掘关联规则呢? 数值关联规则 挖掘技术【3 5 1 就是针对上述问题提出的。数值关联规则挖掘技术的中心问题是连 续属性和多值属性的离散化。在完成了连续属性的离散化之后，数值关联规则 挖掘问题就转化为布尔关联规则挖掘问题，可以应用布尔关联规则算法来对预 处理后的数据集进行挖掘。 将布尔关联规则挖掘技术和连续属性、多值属性的离散化技术集成，以期 构成完整的数字关联规则挖掘系统。本文第四章提出了一个基于数据集市的数 字关联规则挖掘系统，包含后台数据集市、前台交互界面和中间挖掘部分三层 结构，并且将分别阐述各部分实现中的关键技术。 1 3 本文的主要工作 本文所做的工作主要包括以下几个方面的内容： 结合国内外的研究进展全面介绍了k d d 起源、发展和主要技术； 在阐述了关联规则挖掘问题的基础上，对解决关联规则挖掘问题的几种 典型算法进行了详细的描述和比较： 针对数据集中存在的概念层，提出了一种数据集划分的关联规则挖掘算 法d p a r m ，通过实验证明了d p a r m 算法具有一定的挖掘效率，并指出了并行 处理的改进思路： 提出了基于数据集市的三层结构的数字关联规则挖掘系统，阐述了实现 中的关键技术，对于中小型关系数据库的关联规则挖掘具有一定的参考意义。 1 0 华中科技大学硕士学位论文 2 关联规则挖掘技术 在数据挖摁的知识模式中，关联毅则模式是比较重要的一稀。 关联规则模式属于描述型模式，也就是描述在一个事务中物品之间耐时出 现的规律的始识模式。现实中，这样钓例子很多。例如超级市场剃用前端收款 税牧集存储了大量售货数据，这些数据是一条条的购买交易记录，存储了交易 时间、购买物晶、购买数量及金额等。这些数据中誊常隐含女酲下形式躲媲律： 在购买商晶a 的顾客中，商7 0 的人间时购买商品1 3 。比较经典的案例是“尿 布和啤酒”的故事。在美国，一些年轻的父亲下班盾经常要到超市遁去买婴儿 的尿布，越市也隗此发现了个规律，在购买婴儿尿布韵年轻父亲们中，有6 0 7 0 鲍人月时赡买一些蹿潘。超市隧后调整了货架的摆放，把尿布和啤酒放在一 起，明显增加了销售额。 关联规剡挖掘闷题f 3 2 】1 9 9 3 年由r a k e s ha g r a w a l 、t o m a s zi m i e l i n s k i 和a m n s w a m i 提疆，其最初的研究目标就是从事务数据霹中发现有关顾客煦买行为方厦 的知识，并厢关联规贝f j 的形式来表达所发现的知识。耳翦，关联规则挖搀在瘫、韭 等领域的成功应用，馒它成为数据挖撼中比较成熟、薰要和活跃的研究两容。 2 ，1 关联规则挖掘阃题的基本概念 为了准确地定义关联婉耐挖掘问题，便予问题的描述。需要给出关联规则 挖掘闯题的正式定义。下面就通过事务数据库来给鹰关联觏则挖掘阅题的盟确 定义f 3 2 】。 定义2 1 ： 关联规则挖掘的数据集记为d ( d 为事务数据痒) ， d 。 t l t 2 、，k ，t k = f l ，k ，i p ( b i 2 n ) 为一条事务；t k 中 的元素( j 一! 2 ，p 称为矮岛 s u p p o r t ( y )( 2 2 ) ( i i ) 若x y ，如果x 是非频繁项目集，则y 也是非频繁项目集。 ( i i i ) 若x y ，如果y 是频繁项目集，则x 也是频繁项目集。 定义2 4 ： 若x 、y 为项目集，且x n y = a ，蕴涵式x j y 称为关联规则，x 、 1 2 华中科技大学硕士学位论文 y 分别称为关联规则x j y 的前提和结论。项目集( x u y ) 的支持率 称为关联规则x j y 的支持率，记作：s u p p o r t ( x = ： y ) ， s u p p o r t ( x j y ) = s u p p o r t ( x l ) y )( 2 3 ) 关联规则x j y 的置信度记作：e o n f i d e n e e ( x j ， c 。n f i d e n c e ：( ) ( j 2 塑s u p 雩p o r t 旱1 0 0 ( 2 4 ) l 通常用户根据采掘需要指定的最小置信度记为r n i n c o n f i d e n c e 。 支持率和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则 在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说， 只有支持率和置信度均较高的关联规则才可能是用户感兴趣的、有用的关联规 则。 定义2 5 ： 如果s u p p o r t ( x j y ) m i n s u p p o r t ， 且c o n f i d e n c e j m i n c o n f i d e n c e ， 称关联规则x j y 为强规则，否则称关联规则x ；y 为弱规则。 2 - 2 关联规则挖掘问题的分解 关联规则挖掘的任务就是要挖掘出d 中所有的强规则。强规则x j y 对应 的项目集( x u y ) 必定是频繁项目集( 由定义2 5 和( 2 3 ) 式可知) ；由定理2 1 ( i i ) 和( 2 4 ) 式可知：频繁项目集( x u y ) 导出的关联规则x y 的置信度可由频 繁项目集x 和( x u y ) 的支持率计算。因此，可以把关联规则挖掘划分为两个 子问题： 1 ) 根据最小支持率找出数据集d 中的所有频繁项目集： 2 ) 根据频繁项目集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频繁项目集，是关联规则 挖掘的中心问题，是衡量关联规则挖掘算法的标准，目前大多数有关关联规则 挖掘问题的研究都是针对第一个子问题而展开的；第二个子问题可直接( 2 1 ) 1 3 华中科技大学硕士学位论文 式和( 2 4 ) 式求解。 2 _ 2 1 根据频繁项目集产生强规则 由( 2 4 ) 式知，强规则的产生过程如下： 1 ) 对于每个频繁项目集c 产生f 的所有非空真子集； 2 ) 对于f 的每个非空子集m ，如果型墼掣1 0 0 m i n c o n f i d e n c e ，则 s u pp o r t ( m ) 输出强规则“m ( f - m ) ”。 推论2 1 ： 对项目集f 和其子集r r t 和m ，若r n _ m ，则关联规则m j f - m 的 置信度不可能大于关联规则m j f - m 的置信度。 在根据频繁项目集产生强规则时，利用推论2 1 可以减少计算量，进一步提 高强规则的产生效率。 2 2 2 关联规则挖掘的基本模型 综上所述，关联规则挖掘的基本模型可用图2 1 表示。 图2 1 中d 为数据集，a l g o r i t h m l 为频繁项目集的搜索算法，a l g o r i t h m 2 为 关联规则的产生算法，r 为挖掘出的关联规则集合。 用户通过指定m i n s u p p o r t 、m i n c o n f i d e n c e 分别与算法a l g o r i t h m l 和 a l g o r i t h m 2 交互，并通过与r 的交互对挖掘结果进行解释和评价。 图2 1关联规则挖掘的基本模型 1 4 华中科技大学硕士学位论文 2 3 关联规则挖掘方法及其发展方向 关联规则的挖掘问题最初是针对超市的交易数据而提出的，通常称为经典 关联规则挖掘问题。后续的关联规则挖掘问题一方面集中在对经典关联规则挖 掘的改进，主要是减少候选项目集的生成数量和提高算法的效率：另一方面致 力于对经典关联规则的扩展和应用方面。迄今为止主要的关联规则挖掘方法和 方向包括以下几方面。 2 3 1经典关联规则算法及其改进算法的研究 解决关联规则问题的原始算法是a g r a w a l 等人提出的a i s 算法【3 2 】，该算法 产生的候选项目集过大。为了改进a i s 算法，h e i k k im a n n i l a 等人提出了o c d 算法【3 6 】，o c d 算法利用上次搜索的组合信息来减少本次候选项目集的生成数量。 r a k e s ha g r a w a l 等人有在文献【3 3 中提出了著名的a p r i o r i 算法以及其变种 a p r i o r i t i d 和a p r i o r i h y b i r d 算法，a p r i o r i 算法改进了a i s 算法中支持度的计算 方法，利用定理2 1 来对候选集进行剪枝，从而大大减少了候选项目集的数量和 计算时间，其后的很多关联规则算法都是基于a p n o f i 算法。a s h o k as a v a s e r e l 等人与1 9 9 5 年提出了对交易数据进行分区的p a r t i t i o n 3 7 算法，该算法首先把数 据库分为多个分区，然后在每个分区上寻找频繁项目集，最后得到整个数据库 上的频繁项目集，大大减少了扫描数据库的次数。s e r g e yb r i n 等人提出了对候 选项目集进行动态计算的d i c 算法1 3 4 1 ，该算法产生较少的频繁项目集，效率更 高。本文提出的算法d p a r m ，利用数据集中存在的概念层次对数据集进行划分， 并从划分的数据集中挖掘关联规则，实验证明对概念层次较明显的数据集具有 一定的挖掘效率。 2 3 2 意外或例外关联规则的挖掘 传统的关联规则挖掘算法，一般用来发现数据库中的大多数数据所遵循的 规律。但是同时在数据库中还存在有另外一些规律，这些规律是有少数数据所 维持的，其支持度要小于一般关联规则的支持度，用传统的关联规则挖掘算法 1 5 华中科技大学硕士学位论文 无法发现这些规则，而且这些规则常常容易被人忽视，这些规律出乎人们的意 料之外，所以称它们为意外或例外( e x c e p t i o nr u l e s ) ，例外规则常常有很大的 价值。p m h o s c h k a 等提出了e x p l o r a 3 8 l 系统来发现例外规则，该系统利用专 业人员的背景知识来发现规则。e i n o s h i ns u z u k i 提出了一个基于统计学中多维正 态分布的规则发现算法p e d r e 3 9 】。h u a nl i u 等人认为p e d r e 算法的效率不高， 提出了一个效率更高的算法来挖掘例外规则【4 。 2 3 3 数值属性或量化关联规则的挖掘 经典的关联规则挖掘是指布尔类型的规则挖掘，然而现实生活中除了布尔 属性以外，还有如年龄、工资、生产量等数字属性( 或量化属性) ，和如民族、 国家、职业等分类属性的数据。为处理这类属性的数据，提出了是数字属性的 关联规则挖掘问题。 r a m a k f i s h n a ns f i k a n t 等人提出把量化和分类属性的数据按区间映射成布尔 属性的数据，然后在此基础上利用传统的关联规则挖掘方法来挖掘这些属性的 数据【3 5 】。t a k e s h if u k u d a 等人在文献 4 1 1 提出了数字属性优化关联规则的问 题，即最优支持度规则和最优置信度规则，两者统称为优化关联规则。c h a nm a n k u o k 等人提出了使用模糊逻辑方法来挖掘量化关联规则的方法【4 2 1 。该方法是假 定模糊集合已经给定的情况下进行算法设计的。为解决上述问题，a d aw a i - - c h e e f u 等人提出了利用聚类方法来发现模糊集合的方法【4 3 1 。 2 3 4 基于限制和约束的关联规则挖掘 对海量数据集合来讲，使用一般的关联规则