（计算机应用技术专业论文）不完备系统中混合数据关联规则挖掘的研究.pdf

摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多，激增的数据背后隐藏着许多重要的信息，人们希望能够对数据进行 分析，以便挖掘出其中的关系和规则。数据挖掘技术应运而生，它是目前数据库 和信息决策领域最前沿的研究方向之一。关联规则挖掘作为数据挖掘的一个重要 分支，其主要目的是从大型数据集中发现隐藏的、有趣的、属性间存在的规律。 关联规则挖掘问题最初仅涉及事务数据集。事务数据集中不存在属性值丢失 的问题，但空缺值广泛存在于日常数据库中。粗糙集正是处理不精确、不确定以 及不完全数据的数学理论。它对问题的不确定性的描述或处理比较客观，与其它 数据挖掘技术有很强的互补性。另外，对含有离散属性和连续属性的混合数据进 行关联规则提取是一个重要的课题，通常的做法是先对连续属性进行离散化预处 理，然后进行关联规则提取。 本文的主要研究工作包括以下几个方面： ( 1 ) 分析了现有的对不完备信息系统中空缺值的处理方法及其优缺点，根据粗 糙集的上下近似及边界域的概念，提出了不完备系统中关联规则支持度和置信度 的新计算方法。使用新的支持度和置信度可以不处理空缺值而直接提取带结论域 的关联规则。实例分析验证了算法的正确性和有效性。 ( 2 ) 提出了一种计算候选断点集合的算法，该算法不但能够保证信息系统的分 辨关系，而且求得的候选断点集合的基数远小于全部断点总数。算法分析表明该 算法减小了后续算法的时间和空间丌销。 ( 3 ) 构造了一种双层免疫遗传算法，该算法不进行离散化预处理，而直接在混 合数据中挖掘关联规则，克服了连续属性的离散化预处理会使原始信息系统失真 的缺点。实验表明，该算法具有良好的计算性能，并且得到有效的关联规则。 ( 4 ) 设计了一个针对不完备系统的混合数据关联规则挖掘模型，应用本文算法 在该系统中无需处理空缺值、无需进行离散化预处理而直接提取规则，最后部分 实现该模型的功能。 关键词：数据挖掘；关联规则；不完备信息系统；遗传算法；双层结构染色体； 粗糙集 a bs t r a c t p e o p l en e e dt om a n a g ew i t hm o r ea n dm o r ed a t aw i t ht h er a p i dd e v e l o p m e n to f d a t a b a s et e c h n o l o g ya n dt h ew i d eu s eo fd a t a b a s em a n a g e m e n ts y s t e m s t h e r ei sal o t o fi m p o r t a n ti n f o r m a t i o nh i d d e ni nt h ei n c r e a s i n gd a t a p e o p l ew a n tt oa n a l y z et h e s e d a t ai no r d e rt of i n do u tt h er e l a t i o n s h i p sa n dr u l e sc o n c e a l e di nd a t a t h u s ，d a t a m i n i n gw a sp r o p o s e d d a t am i n i n gi so n eo ft h em o s tf o r w a r dl i n e so fd a t a b a s ea n d i n f o r m a t i o nd e c i s i o na r e a a s s o c i a t i o nr u l e sm i n i n gi sa ni m p o r t a n tf o r mo fd a t a m i n i n gt od i s c o v e rp r e v i o u s l yu n k n o w n ，i n t e r e s t i n gr e l a t i o n s h i p sa m o n ga t t r i b u t e s f r o ml a r g ed a t a b a s e s a s s o c i a t i o nr u l e sm i n i n gw a sf i r s t l yd e v e l o p e di nt r a n s a c t i o nd a t a b a s e sw h e r et h e p r o b l e mo fm i s s i n gv a l u e sd o e sn o tp r a c t i c a l l ye x i s t h o w e v e rm i s s i n gv a l u e sw i d e l y e x i s ti nd a i l yd a t a b a s e s r o u g hs e t t h e o r y i san e wm a t h e m a t i c a l a p p r o a c h t o i m p r e c i s i o n ，u n c e r t a i n t ya n di n c o m p l e t e n e s s i ti sm o r eo b j e c t i v ei nd e s c r i b i n ga n d d e a l i n gw i t hu n c e r t a i n t yt h a ns o m eo t h e rm e t h o d s t h e r ea r es t r o n gc o m p l e m e n t a r i t i e s o fr o u g hs e tt h e o r ya n do t h e rd a t am i n i n ga l g o r i t h m s i na d d i t i o n ，m i n i n ga s s o c i a t i o n r u l e sf r o md a t aw i t hb o t hd i s c r e t ea n dc o n t i n u o u sa t t r i b u t e si sa ni m p o r t a n tp r o b l e m t h ec o m m o np r o c e s si sd i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e sf i r s t ，a n dt h e ne x t r a c t i o n o fa s s o c i a t i o nr u l e s t h em a i nr e s e a r c ho ft h i sp a p e ri sa sf o l l o w s ： ( 1 ) i tr e v i e w st h ee x i s t i n ga p p r o a c h e st op r o c e s s i n gm i s s i n gv a l u e sa n da n a l y z e s t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e si ni n c o m p l e t ei n f o r m a t i o ns y s t e m s a n da c c o r d i n g t or o u g hs e t su p p e ra n dl o w e ra p p r o x i m a t i o na n db o u n d a r y ，i tp r e s e n t san e wm e t h o d t or e d e f i n et h es u p p o r ta n dc o n f i d e n c eo fa s s o c i a t i o nr u l e si ni n c o m p l e t ei n f o r m a t i o n s y s t e m s t h en e wd e f i n i t i o n sc a nb eu s e dt om i n er u l e sw i t hd e c i s i o na t t r i b u t e sd i r e c t l y w i t h o u tp r o c e s s i n gm i s s i n gv a l u e s t h er e s u l t so fe x p e r i m e n t sp r o v et h ec o r r e c t n e s s a n dv a l i d i t yo ft h ea l g o r i t h m ( 2 ) an e wa l g o r i t h mo fc o m p u t i n gt h ec a n d i d a t ec u t s e t si s p r o p o s e d t h i s a l g o r i t h mc a nm a i n t a i nt h es y s t e md i s c e r n i b i l i t yr e l a t i o n ，a n da l s op r o d u c ec a n d i d a t e c u ts e t sw i t hm u c hs m a l l e rc a r d i n a li t i e st h a nt h et o t a lo fc u t s t h et h e o r e t i c a la n a l y s e s s h o wt h a t t h i sa l g o r i t h mr e d u c e st h et i m ea n ds p a c ec o m p l e x i t yo ft h ef o l l o w i n g a l g o r i t h m s ( 3 ) an o v e lt w o - l a y e ri m m u n eg e n e t i ca l g o r i t h mi sp u tf o r w a r d t h i sa l g o r i t h m c a nm i n ea s s o c i a t i o nr u l e sd i r e c t l yw i t h o u td i s c r e t i z a t i o np r e p r o c e s s i n g i to v e r c o m e s t h ed r a w b a c k st h a td i s c r e t i z a t i o np r e p r o c e s s i n gm a ym a k et h eo r i g i n a l 1 n f o r m a t l o n s v s t e md i s t o r t i o n t h ee x p e r i m e n t ss h o wt h a tt h en e wa l g o r i t h mh a sn i c ec o m p u t i n g p e r f o r m a n c ea n d c a nm i n ee f f e c t i v ea s s o c i a t i o nr u l e s - f 4 ) i te s t a b l i s h e sam o d e lf o ra s s o c i a t i o nr u l e sm i n i n gi ni n c o m p l e t e1 n f o r m a t l o n s v s t e mw i t hm i x e dd a t a i tu s e st h ea l g o r i t h m sp u tf o r w a r di nt h i sp a p e r t 0m l n er u l e s d i r e c t l vw i t h o u tp r o c e s s i n gm i s s i n gv a l u e sa n dd i s c r e t i z a t i o np r e p r o c e s s l n g f 1 n a l l y t h ef u n c t i o n so ft h i sm o d e la r er e a l i z e dp a r t l y k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o n r u l e s ；i n c o m p l e t ei n f o r 砌t i o ns y s t e m s ； g e n e t i ca l g o r i t h m ；t w o l a y e rc h r o m o s o m e s ；r o u g h s e t 1 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 王翮翮 日期：砒年f 月加日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ) 作者签名：王丽确 导师签名：强可 日期：础年歹月加日 日期：d 8 年歹月如日 1 1 研究的背景和意义 第一章绪论 数据挖掘( d a t am i n i n g ，简称d m ) 是一个新兴的、具有广泛应用前景的研究 领域。它不但可以帮助人们从海量数据中提取出所感兴趣的知识、规律，而且还 可以进一步预测未来的发展趋势，它的出现为自动地、智能地把海量数据转化为 有用的知识提供了有力的手段。关联规则挖掘作为数据挖掘的一个重要研究分支， 自a g r a w a l 等人比1 在s i g m o d 9 3 上首次提出以来，一直是众多学者的研究热点，其 主要的研究目的是从大型数据集中发现隐藏的、有趣的、属性间存在的规律。 关联规则挖掘最初仅涉及事务数据集，在事务数据集中不存在空缺值，然而 当我们尝试发现大型数据库中的关联规则时，就可能面对空缺值。粗糙集正是处 理不精确、不确定以及不完全数据的数学理论，它是由波兰学者zp a w l a k 首次提 出的凹1 。粗糙集理论可以支持数据挖掘的多个步骤，如数据预处理、数据缩减、规 则生成等，其最显著的优点在于它无需提供问题所需处理数据集合之外的任何先 验信息。近几年来，粗糙集理论已广泛应用于机器学习、知识发现、决策支持与 分析、专家系统、智能控制、模式识别等领域。因此，利用粗糙集理论在含有空 缺值的不完备系统中提取关联规则是很有意义的。 现实的数据集中包括了大量的连续属性数据，而很多数据挖掘技术如贝叶斯 技术、粗糙集理论等要求数据是离散数据，因此连续属性离散化对于数据挖掘而 言具有十分重要的意义。有效的离散化可以减少系统对存储空间的实际需求，加 快后续数据挖掘算法的运行速度。连续属性离散化实际上是在候选断点集中进行 搜索寻找最优断点集的过程，而遗传算法h 1 正是一种基于生物自然选择与遗传机理 的可调节的、高效率的随机搜索算法。与启发式算法比较，遗传算法不仅具有很 好的全局搜索能力，同时能较好地处理数据库中不同属性之间的相互关系，因此 遗传算法应用于连续属性离散化等方面的文献不断涌现咱】。 在含有连续属性的数据集中提取关联规则，一般先将连续属性离散化，再对 离散化的结果进行关联规则提取。在整个过程中，先期的离散化与后续规则提取 的过程是完全独立的，这样先进行的离散化处理可能会改变信息系统原有的不可 分辨关系，容易使规则提取产生错误。怎样直接在混合属性数据中挖掘规则是当 今研究的热点问题之一。 本文研究构造了一种新的免疫遗传算法模型，该模型结合粗糙集对不完备数 据的处理优势，适用于不完备信息系统中混合属性数据关联规则的挖掘。该模型 无需处理空缺值、无需进行离散化预处理而直接在信息系统中提取规则。 1 2 数据挖掘概述 1 2 1 数据挖掘的发展背景 近年来，由于计算机性能提高、成本下降及数据管理技术的成功运用，使各 部门内部的信息化程度越来越高，同时也造成了大量数据的积累。“数据丰富，知 识贫乏”。如何理解已有的历史数据并用以预测未来的行为，如何从这些海量数据 中发现信息，变被动的数据为主动的知识，如何快速、准确地获得有价值的网络 信息和网络服务，为用户提供重要的、未知的信息或知识，指导政府决策、企业 决策，获取更大的经济效益和社会效益，这些都迫使人们去寻找新的、更为有效 的数据分析手段，对各种“数据矿藏”进行有效的挖掘以发挥其应用潜能。2 0 世 纪8 0 年代后期至今，高级数据分析一一数据挖掘( 州) 与数据库中的知识发现 ( 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 o ) 正是在这样的应用需求背景下产生 并迅速发展起来的、开发信息资源的一套科学方法、算法及软件工具和环境。 简单地说，数据挖掘是提取或“挖掘”知识。目前，数据挖掘可以从统计学、 数据库和机器学习等三个角度进行定义m 。“挖掘”一词最早出现于统计学中，从 统计学的角度，数据挖掘是指分析所观察的数据集以发现可信的数据间的未知关 系并提供给数据拥有者可理解的、新颖的和有用的归纳数据。从数据库的观点来 看，数据挖掘是指从存储在数据库、数据仓库或其它信息仓库中的大量数据中发 现有趣的知识的过程。从机器学习的角度，数据挖掘定义为从数据中抽取隐含的、 明显未知的和潜在的信息。 数据库中的知识发现( k d d ) 是识别有效的、新颖的、具有潜在用处的、可理解 的数据模式的过程。简单地讲，k d d 表示了从低层数据抽象高层知识的整个过程。 通过数据库中的知识发现，人们可以从数据库的数据及相关集合中抽象出有用的 知识、数据的规律性或高层的信息。本质上，数据挖掘( d m ) 与数据库中的知识发 现( k 叻) 是不同的，但也有一些人把d m 和k 胁等同看待，其实d m 仅仅是k d d 的一 个步骤。 数据挖掘是一个交叉的学科领域，包括了数据库技术、统计学、机器学习、 可视化和信息科学等。数据挖掘中采用的主要技术有神经网络、模糊理论、粗糙 集理论、遗传算法、归纳逻辑等。通过数据挖掘，可以从数据集中发现有趣的知 识、规律和信息，并可以从不同的角度观察和浏览，所发现的知识可用于决策、 信息管理、查询处理、过程控制等等。因此，数据挖掘是当今信息技术学科最前 沿的领域之一。 数据挖掘按照功能主要分为以下几种：( 1 ) 关联规则；( 2 ) 分类；( 3 ) 聚类；( 4 ) 孤立点分析；( 5 演变分析。其中关联规则挖掘是数据挖掘领域中的一门重要的研 究课题。 1 2 2 数据挖掘的研究现状 知识发现和数据挖掘是近年来十分活跃的研究领域。数据库中的知识发现 2 ( k d d ) 一词首先出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会议( i j c a i ) 上。从1 9 8 9 年到19 9 4 年举行了四次k d d 的国际研讨会。在此基础上，1 9 9 5 年召 开了第一届知识发现与数据挖掘的国际学术会议。1 9 9 8 年建立了新的学术组织 a c m s i g k d d ，即a c m 下的数据库中的知识发现专业组( s p e c i a li n t e r e s t e dg r o u p o nk n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。1 9 9 9 年a c m s i g k d d 组织了第五届知识 发现与数据挖掘国际学术会议( k d d 9 9 ) ，专题杂志d a t am ir l i n ga n dk n o w l e d g e d is c o v e r y 自1 9 9 7 年起由k 1 u w e r s 出版社出版。此外，还有一些国际和地区性数 据挖掘会议，如“知识发现与数据挖掘太平洋亚洲会议 ( p a k d d ) 、“数据库中的 知识发现原理与实践欧洲会议”( p k d d ) 、“数据仓库与知识发现国际会议”( d a w a k ) 、 “a c m s i g m o d 数据管理国际会议”( s i g m o d ) 等等。近几年数据挖掘的研究重点从 算法研究向具体应用过渡，从实验室原型走向商品化阶段。1 9 9 9 年，国际上从事 数据挖掘产品研发的软件公司已从1 9 8 9 年的几个公司，猛增为上百家公司，每年 都有若干软件产品推出。 与国外相比，国内对数据挖掘的研究稍晚，我国的数据挖掘研究开始于2 0 世 纪9 0 年代中期，到了9 0 年代后期，初步形成了知识发现和数据挖掘的基本框架。 一批研究成果陆续发表在计算机学报、计算机研究与发展、软件学报、人 工智能与模式识别等刊物上。1 9 9 3 年国家自然科学基金首次支持该领域的研究 项目，国内许多学术会议如数据库学术会议、机器学习会议等也都将k d d 列为重 要的研究方向。现在，研究重点e 由发现方法转向系统应用，并且注重多种发现 策略和技术的继承，以及多种学科间的相互渗透。 1 3 关联规则概述 1 3 1 关联规则简介 关联规则挖掘用于寻找给定数据集中数据项之间的有趣的关联或相关关系。 关联规则提示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一 个数据对象的信息来推断另一个数据对象的信息。 关联规则的一个典型例子是购物篮分析，系统通过对顾客放入其购物篮中的 不同商品的分析，了解顾客的购买习惯及行为特征。一旦发现有趣的规则，就可 以指导商家制定正确的销售决策，如交叉购物、目录设计、商品陈列等，从而使 他们在市场竞争中取得更大的主动权。例如，购物篮分析可以帮助经理设计不同 的展场。一种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些 商品一起销售。如一个超市中顾客购买面包的同时一般要购买牛奶或者饮料，那 么把销售牛奶或者饮料的展台放在销售面包的展台附近，就可以促进二者的销售。 另一种策略是：将面包和牛奶分别放在展场的两端，在两者之间放上销售情况一 般或者不好的商品，那么顾客在决定购买面包以后，从一端的面包展场走向另一 端牛奶展场的路上，他可能看到果酱，就会产生购买果酱的愿望。 事实上，关联规则的应用不仅局限于购物篮分析，还有着广泛的应用领域， 3 如商业与金融、人口普查数据分析、工程技术数据分析、医疗、电子商务等等。 1 3 2 关联规则挖掘的研究现状 关于关联规则挖掘算法的文献层出不穷，其中最著名的关联规则发现算法是 a p r i o r i 瞳1 ，a p r i o r i 算法通过多次迭代找出所有的频繁项目集。由于关联规贝| l 的数 目可能是相当大的，人们在探索发现关联规则的同时，对于提高挖掘过程的效率 也做了不少的研究。如a g r a w a l 等人在v l d b 9 4 提出的快速算法阳1 ，p a r k 等人在 s i g m o d 9 5 提出了利用h a s h 表的d h p 算法阳1 ，t o i v o n e n 提出了基于采样的算法u 叭， z a i a n e 等人提出了并行关联规则挖掘算法1 ，s c h u s t e r 等人提出了分布式关联规 则算法n 引，h a n 等人提出了多层关联规则挖掘算法n3 i 。还有一些研究采用了不同 的数据结构进行关联规则的挖掘。如w a n g 等人给出了基于兴趣度进行数值型关联 规则合并的算法n4 1 ，通过合并相邻的数值，从底向上，利用b 树从关系表中挖掘 关联规则；l e v e n e 和l o i z o h 总结了关联规则的概念，提出了结构化有向图的概念 n 5 1 ，重新定义了支持度和置信度的概念，给出了在超文本数据库中挖掘关联规则 的两个算法。 国内对关联规则挖掘的研究起步较晚，中科院计算所的欧阳为民首先弓 入国 外关联规则挖掘的概念和思想，并在基于a p r i o r i 算法的基础上提出了时态约束的 关联规则“引。目前国内从事数据关联规则挖掘研究的人员主要在大学、研究所或 公司，所涉及的研究领域一般集中于关联规则算法的研究、关联规则的实际应用 等。目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、九五计划等，其中，中科院计算机研究所的智能信息处理重点实验室研 制开发的多策略数据挖掘平台m s m i n e r 系统，将关联规则挖掘算法集成到此系统 中。复旦大学研制开发的a r m i n e r 系统是专门针对智能化的p o s 系统开发的关联 规则挖掘工具，此系统的关联规则挖掘算法是基于a p r i o r i 的改进算法。 不难看出，关联规贝l j 挖掘一直是数据挖掘的研究热点，从商场购物篮分析、 数据仓库中的关联规则发现到i n t e r n e t 上数据的关联规则挖掘等等，充分说明近 年来的研究正逐步走向深入和成熟。 1 3 3 关联规则挖掘存在的问题 目前，关联规则挖掘方面的研究已经取得了较大的进展，但对下歹l j 问题仍有 待于进一步研究： ( 1 ) 算法的效率问题 数据库规模的不断增大不仅加大了挖掘算法的搜索空间，而且也增加了盲目 挖掘的可能性。因此必须结合领域知识去提取与我们发现任务有关的数据，删除 无用数据，有效地降低问题的维数，提高挖掘算法的效率。在这方面，基于约束 的关联规则挖掘具有广阔的前途，约束的引入可以提高挖掘的效率，并使挖掘的 目标朝着符合用户需求的方向进行。 ( 2 ) 不完备信息系统中挖掘关联规贝i 在含有空缺值的不完备信息系统进行关联规则挖掘通常的方法是先通过各种 4 方法将数据集完备化，但这会使知识存在不同程度的失真。我们希望在保持原始 信息不发生变化的前提下对信息系统进行关联规则挖掘。 ( 3 ) 在混合数据中挖掘关联规则 在含有连续属性和离散属性的混合数据中提取关联规则，一般先将连续属性 离散化，再对离散化的结果进行关联规则提取。在整个过程中，先期的离散化与 后续规则提取的过程是完全独立的，这样先进行的离散化处理将会使原始信息系 统丢失一些信息。怎样在混合属性数据中直接挖掘关联规则是当今研究的热点问 题之一。 1 4 本文的工作 本文主要从以下四个方面对不完备信息系统中的混合数据关联规则挖掘进行 了研究： ( 1 ) 不完备信息系统中带结论域的关联规则挖掘研究 不完备信息系统中挖掘关联规则的关键问题在于关联规则的支持度和置信度 不能象完备信息系统中那样精确地计算，本文根据粗糙集理论的上下近似、边界 域等概念，提出了新的关联规则支持度、置信度的计算方法，在不完备系统中不 处理空缺值而直接挖掘带结论域的关联规则。 ( 2 ) 候选断点集的选取研究 离散化的实质就是将利用选取的断点将连续属性值划分成区间。候选断点集合 的确定是解决数据离散化的基础，保证候选断点集具有尽可能小的基数可以减小 系统开销。本文提出了一种计算候选断点集合的算法，根据熵的二分离散化原则 在属性断点集中选取一部分作为候选断点。该算法不但能够保证决策系统的分辨 关系，而且求得的候选断点集合的基数远小于此属性全部断点总数。 ( 3 ) 混合属性数据关联规则挖掘研究 对含有离散属性和连续属性的混合属性数据进行关联规则提取是一个重要的 课题。我们提出了一种双层免疫遗传算法将连续值属性离散化与关联规则提取过 程融为一体。该算法在结构上采用双层染色体，第一层搜索连续属性数据的最优 断点集，第二层对混合数据进行规则提取，采用此算法同时得到连续属性的最优 断点集和关联规则集，并进行了实例分析。 ( 4 ) 设计了一个关联规则挖掘模型，该模型以本文提出的关联规则挖掘算法 r s t i g a - m a i l s 为基础，为不完备信息系统混合数据关联规则挖掘的实现提供了 一个基本框架，最后部分实现了该系统。 1 5 本文的组织 第一章阐述了本文的研究意义和背景，介绍了数据挖掘和关联规则挖掘的国 内外研究现状及研究中存在的问题，最后对本文的主要研究内容进行了介绍。 第二章介绍了关联规则的基本概念，分析了经典频繁项目集挖掘算法一 5 a p r i o r i 算法及其改进算法，并对关联规则挖掘的其它方向进行了探讨，重点分析 了基于约束的关联规则挖掘。 第三章主要讨论了不完备信息系统中关联规则的提取。首先介绍了不完备系 统中空值的定义及产生原因，比较了处理空值的几种方法，然后提出了一种基于 粗糙集的不完备系统关联规则挖掘模型，重新定义了关联规则的支持度和置信度 等概念，利用此模型可以不处理空缺值，直接提取带结论域的关联规财。 第四章主要介绍了连续属性离散化的基础知识，重点研究了一种候选断点的 选取方法，在保证系统分辨关系的前提下，使候选断点集合具有尽可能小的基数， 减小了后续算法的时间和空间开销。 第五章主要讨论了混合属性数据中关联规则的提取。首先介绍了遗传算法的 基本知识，然后针对含有离散属性数据和连续属性数据的混合数据，提出了一种 双层免疫遗传算法，该算法不需要先做离散化处理，而直接对混合属性数据进行 关联规则提取，将连续属性离散化和规贝i j 提取过程有效地融为一体。实验结果表 明了算法的可行性和有效性。 第六章主要研究了一种不完备系统混合数据关联规则挖掘模型。将第三章和 第五章的方法结合起来提出了一个适用于既不完备、又含有混合数据的信息系统 的关联规则挖掘模型。 第七章总结了本文的研究工作，阐明其难点和创新点，并提出进一步研究的 方向。 6 第二章关联规则 弟一早大驮机火u 关联分析用于发现关联规则，关联规则挖掘通过关联性发现一组项目之间的 关联关系和相关关系，并将这些关系表示为规则形式，即在事务数据集和关系数 据库中采集关联规则的集合。 2 1 关联规则基本概念 给定一个事务数据集，人们往往希望发现事务中的关联事实，即事务中一些 项目的出现必定隐含着同事务中其它项目的出现，这是关联规则的一个简单的描 述。关联规则挖掘的有关定义性描述如下： 定义2 1 ：设j 一 1 1 ，i ：，i 。 是项目的集合，事务集记为d 一缸。，t ：，t n ，其中 每个事务t i = ，f 。，：，厶) 是项目的集合，使得e i ，关联规则是形如xj y 的蕴 含式，其中x i ，y i 是两个项目集合，且xn y ；a 。 定义2 2 ：对于规则x 号y ，若事务集d 中包含的事务数占事务总数的s ， 则称规则x 号y 的支持度s u p p o r t 为s 。记为s u p p o r t ( xj y ) = s u p p o r t ( xu y ) = s 。 定义2 3 ：对于规则xjy ，若事务集d 中包含x 的事务中有c 同时包含y ， 则称规则x 号y 的置信度c o n f i d e n c e 为c 。记为c o n f i d e n c e ( x 净n = c ，则 c o n 乒d 绷c e ( x 净y ) ：s u p p o r t ( x u y ) - c 。 、。 s u p p o r t ( x ) 支持度和置信度是关联规则挖掘中的一类重要的约束，由用户根据不同的挖 掘任务和欲达到的目标来指定。支持度是对关联规则重要性的衡量，表示规则的 频度；置信度是对关联规则正确程度的衡量，表示规则的强度。如果关联规则的 置信度很高，但支持度很低，说明该关联规则实用机会很小；如果支持度很高， 而置信度很低，则说明规则不可靠。 定义2 4 ：事务集d 中，由用户指定最小支持度( 汜为m i n s u p ) 和最小置信度( 记 为m i n c o n t ) ，对规则x j y ，若s u p p o r t ( xjn之m i n s u p 且 c o n f i d e n c e ( xj y ) m i n c o n f , 称规则x 辛y 为强关联规则。 关联规则挖掘过程就是产生所有强关联规则的过程。即在事务数据集d 中找 出所有满足用户给定的最小支持度阈值和最小置信度阈值的关联规则。每一条被 挖掘出来的关联规则可以用一个蕴含式、两个阈值唯一标识，即x 寺y ( 支持度， 置信度) 。 2 2 关联规则的分类 根据不同的标准，关联规则有多种分类方法： 7 ( 1 ) 根据规则中所处理的值的类型可以分为布尔关联规则和量化关联规则。 布尔关联规则处理的值都是离散的、种类化的，它所考虑的是项的在与不在。 例如，“牛奶号面包”所描述的就是市场购物分析所获得一条布尔关联规则。 若一个规则仅描述定量数据项( 或属性) 之问的关系，那么它就是一个量化关 联规则。例如规则：a g e ( x ，“3 0 - 3 9 ”) 八i n c o m e ( x ，“2 万一4 万”) 兮b u y s ( x ， “c o m p u t e r ”) 。对量化关联规贝呼的挖掘问题由s r i k a n t 等人提出n ，已引起许 多研究学者的极大关注。 ( 2 ) 根据规则中数据的维数可以分为单维关联规则和多维关联规则。 单维关联规则只涉及到数据的一个维。例如，规贝吩b u y s ( x ，“牛奶”) 专b u y s ( x ， “面包” 只涉及一个维( 属性b u y s ) 。 在多维关联规则中，要处理的数据将会涉及多个维。例如，上面的规则涉 及三个维a g e ，i n c o m e 和b u y s 。 ( 3 根据规则集所涉及的抽象层可以分为单层关联规贝i j 和多层关联规则。 一些关联规则挖掘方法可以发现不同抽象层次的项或属性。例如，规则和 规则： 规则：a g e ( x ，“3 0 4 0 ”) c b u y s ( x ，“笔记本电脑”) 规贝| j ：a g e ( x ，“3 0 4 0 j b u y s ( x ，“电脑”) 在规则和中属性b u y s 的数据项描述涉及不同抽象层次内容：电脑是笔记 本电脑的更高层次，由于规则和内容涉及多个不同抽象层次概念，因此就构 成了多层次关联规则；相反若一个关联规则的内容仅涉及单一层次的概念，那么 这样的关联规则就称为单层关联规则。 目前已有许多基于概念层次的关联规则挖掘算法，如h a n 等人根据共享多层 次挖掘过程和减少事务编码表的不同方式，提出了发现多层次关联规则的四种算 法”，其它算法还有r s r i k a n t 等人的c u m u l a t e 、s t r a t i f y 及其变种e s t i m a t e 、 e s t m e r g e 等n 8 。 ( 4 ) 根据关联规则的各种扩充可以分为挖掘最大模式和频繁闭项目集。 最大模式是频繁模式p ，使得p 的任何真超模式都不是频繁的。频繁闭项目集 是一个频繁的闭的项目集，不存在c 的真超集c ，使得每个包含c 的事务也包含c 。 使用最大模式和频繁闭项目集可以显著地压缩挖掘所产生的频繁项目集数。 2 3 经典关联规则算法 关联规则挖掘的过程如下： 第一步，产生全部频繁项目集。在挖掘过程中， 小支持度阂值的项目集称为频繁项目集； 第二步，根据所得频繁项目集产生强关联规则。 其置信度不小于用户指定的最小置信度阂值。 支持度不小于用户指定的最 产生关联规则的基本原则是 这两步中，第一步是关键，第二步比较容易实现。因此挖掘出所有频繁项目 8 集是挖掘过程的核心，占据整个计算量的大部分。 自a g r a w a l 等人首先提出了挖掘事务数据集中项目集问的关联规则问题以来， 诸多研究人员对关联规则的挖掘问题进行了大量的研究。下面对一些经典的算法 作简单的介绍。 2 3 1 a p r i o r i 算法 a p r i o r i 算法是挖掘产生关联规则所需频繁项目集的基本算法，它也是一个很 有影响的关联规则挖掘算法。a p r i o r i 算法就是根据有关频繁项目集特性的先验知 识( p r i o rk n o w l e d g e ) 而命名的。该方法使用一种称作逐层搜索的迭代方法，k 一项 目集用来产生 k + l _