（计算数学专业论文）含负项和数量属性的关联规则挖掘研究.pdf

含负项和数量属性的关联规则挖掘研究 计算数学专业 研究生：游晋峰 指导教9 i l i ：冯山 摘要： 关联规则挖掘是数据挖掘领域中一个重要的研究方向，揭示 数据集中不同领域或属性间的有价值联系，具有重要的理论价值 和广泛的应用前景。 本文系统地讨论了关联规则挖掘的相关理论，对现有的关联 规则挖掘算法的研究工作进行了归纳、分析，重点讨论了数量关 联规则和含负项的布尔关联规则的挖掘问题。在此基础上，完成 了如下两个创新型的工作： 1 提出了一个在频繁2 项集上挖掘数量关联规则的改进算 法。它不仅可以用于典型的购物篮分析，还可以用于购物篮分析 不能完成的带数量的关联规则的挖掘问题。例如，它可以用于带 数量的商品捆绑销售问题中的捆绑决策问题的规则提取。 2 基于对数量关联规则和含负项的布尔关联规则的研究，论 文提出了一种含负项的数量关联规则挖掘算法。详细分析了数量 属性和负项带来的问题，给出了相应的解决方案。 首先，论文研究了数量属性及其否定项问题；其次，针对巨 大的非频繁项集可能带来大量无趣规则的产生，引入了两级支持 度概念来约束产生频繁项集和非频繁项集；在候选项集的生成过 程中，为防止负项造成多余项集，对原有的印r i o r i e n 函数进行改 进，提出了新的候选项集生成函数1 a n d i d a t 咄e n 函数。改进的 算法不仅有效地将负项引入到了数量关联规则中，且挖掘出了非 频繁项集中的有趣的关联规则。 关键词：负项；数量属性；两级支持度；非频繁项集；数量关 联规则；正、负关联规则 s t u d yo nm i n i n g a s s o c i a t i o nr u l e sw i t h n e g a t i v ei t e m sa n dq u a n t i t a t i v ea t t r i b u t e s m a j o r ：c o m p u t em a t h e m a t i c s s t u d e n t y o uj i n f e n g t u t o r ：f e n gs h a h a b s t r a c t ： a s s o c i a t i o nr u l em i n i n gi sa ni m p o r t a n tr e s e a r c hd i r e c t i o no fd a t a m i n i n g ，w h i c hc a ne x p l o r ev a l u a b l er e l a t i o n sb e t w e e nd i f f e r e n tf i e l d s a n da t t r i b u t e sf r o md a t as e t sa n dh a si m p o r t a n tt h e o r e t i c a lv a l u ea n d b r o a da p p l i c a t i o np r o s p e c t t h et h e o r e t i c a lf o u n d a t i o no fa s s o c i a t i o nr u l e s m i n i n g i s s y s t e m a t i c a l l yd i s c u s s e di nt h i sp a p e r a n dt h e nw ec a t e g o r i z ea n d a n a l y z et h ee x i s t i n ga 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 dm a i n l y d i s c u s sq u a n t i t a t i v ea s s o c i a t i o nr u l e sa n db o o l e a na s s o c i a t i o nr u l e w i t hn e g a t i v ei t e m s b a s e do nt h ea b o v e m e n t i o n e ds t u d yw ef u l f i l l t w oi n n o v a t i v et a s k s ： 1 an e wa p p r o a c ho fq u a n t i t a t i v ea s s o c i a t i o nr u l em i m n gb a s e d o nf r e q u e n t2 - i t e m s e t si s p r o p o s e d i tc a nb ea p p l i e dn o to n l yf o r t y p i c a lb a s k e ta n a l y s i s ，b u ta l s of o rt h o s ew i t hq u a n t i t a t i v ea t t r i b u t e s c a s e st h a tt h ep r e s e n tb a s k e ta n a l y s i sa l g o r i t h mf a i l st oa c h i e v e f o r i n s t a n c e i tc a l lb e u s e df o rr u l e s e x t r a c t i n go fb u n d l e dd e c i s i o n p r o b l e m si nm e r c h a n d i s eb u n d l e ds a l e sp r o b l e m sw i t hq u a n t i t a t i v e 2 b a s e do nt h es t u d yo ft h eq u a n t i t a t i v ea s s o c i a f i o nr u l e sa n d b o o l e a na s s o c i a t i o nr u l e sw i t h n e g a t i v e i t e m s ，t h eq u a n t i t a t i v e a s s o c i a t i o nr u l e sw i t hn e g a t i v ei t e m si sb r o u g h tf o r w a r d w ed e t a i l e d a n a l y s i st h ep r o b l e m sc a u s i n gb yq u a n t i t a t i v ep r o p e r t i e sa n dn e g a t i v e i t e m s ，a n dp r o p o s et h ec o r r e s p o n d i n gs o l u t i o n s f i r s t ，q u a n t i t a t i v ea t t r i b u t e sa n di t sn e g a t i v ei t e m sa r ed i s c u s s e d s e c o n d lv b e c a u s et h ev a s ti n f r e q u e n ti t e m s e t sc a ni n c r e a s el o t so f b o r i n gr u l e s ，t w o _ l e v e l s u p p o r t si sb r o u g h ti nt oi m p o s er e s t r i c t i o n s o nt h eg e n e r a t i n go ff r e q u e n ti t e m s e t sa n di n f r e q u e n ti t e m s e t s ；i nt h e g e n e r a t i v ep r o c e s so f t h ec a n d i d a t ei t e m s e t s ，c a n d i d a t e _ _ g e nf u n c t i o ni s p u tf o r w a r d ，w h i c hi s t h en e wc a n d i d a t ei t e m s e t sg e n e r a t i n gf u n c t i o n b ym o d i f y i n gt h eo r i g i n a la p r i o r i _ g e nf u n c t i o n ，i no r d e r t op r e v e n t r e d u n d a n ti t e m s e t sc a u s e db yn e g a t i v ei t e m s e t s t h ea l g o r i t h mn o t o n l ye f f e c t i v e l yi n j e c t sn e g a t i v ei t e m s i n t oq u a n t i t a t i v ea s s o c i a t i o n r u l e s ，b u ta l s om i n ei n t e r e s t i n ga s s o c i a t i o nr u l e sf r o mt h ei n f r e q u e n t i t e m s e t s k e y w o r d s ：n e g a t i v ei t e m s ；q u a n t i t a t i v ea t t r i b u t e s ；t w ol e v e l _ s u p p o r t s ； t h ei n f r e q u e n ti t e m s e t s ；q u a n t i t a t i v ea s s o c i a t i o nr u l e ；a s s o c i a t i o nr u l e w i t hp o s i t i v ea n dn e g a t i v ei t e m s i v - 四 t i n 范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师冯山教授的指导 下，独立进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不含任何其他个人或集体已经发表或撰写过的作品 或成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。 如因不符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授 权所在大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究 生必须按学校规定提交印刷版和电子版学位论文，可以将学位论 文的全部或部分内容编入有关数据库供检索；2 ) 为教学、科研和 学术交流目的，学校可以将公开的学位论文或解密后的学位论文 作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：荔怎酋哮 导师签名：乏秀翻 签字日期：卅拜多月矽日 签字日鼽声了月们日 第一章绪论 数据挖掘1 1 】，顾名思义就是从数据中挖掘知识，出现- 于 2 0 世纪 8 0 年代后期。它涉及多学科的集成【2 1 ，如数据库技术、人工智能与 模式识别、机器学习、统计学和空间数据分析等，因此被认为是 信息产业中最有前途的交叉学科。目前已广泛用于市场分析、商 务管理、生产控制、工程设计等领域。 1 1 选题背景及研究意义 数据挖掘是数据库和信息决策领域的前沿学科之一，又称为 数据库中的知识发现( k d d ) ，是指从大量不完全的噪声数据中提取 可信的、有趣的、潜在的、易于用户理解的模式的过程。其结果 是面向应用的、相对的、有特定前提和约束条件的知识。 关联分析【1 - 4 】是数据挖掘的一个重要问题，揭示数据集中不同 领域或属性间的有价值联系，一般用关联规则的形式表述。很多 学者对基于关联规则的数据挖掘从不同的侧面进行了研究，如算 法效率州6 1 、关联规则增量问题【1 7 之o 】、基于约束的关联规则2 2 2 4 】 等。这些研究活动具体表现为： 1 规则只涉及项集之间的简单蕴涵关系，即xjy 形式 xjy 形式的关联规则反映的是项集之问的正关联。实际上， 在进行关联规则挖掘时，挖掘出来的知识不仅仅只有正关联规则 形式。例如，对知识“没结婚的人群不一定或很少购买房子”， 用单纯的正关联规则形式是无法表示的。但是，可以用xjy 形 式的负关联规则【3 1 7 】表示。文献【3 7 】在规则中首次考虑了否定项，讨 论了两个频繁项集间的负相关。文献 4 2 研究了负关联规则的冗余 消除问题，文献 4 6 - 4 7 1 对负关联规则的有趣度进行了研究，文献 4 8 】 研究了基于非频繁项集的负关联规则挖掘，文献 5 1 ，5 2 对负关联规 则算法的效率展开了研究。这些研究都假设规则的前提或结论要 么是正项集，要么是负项集。它们虽然对传统的正关联规则的完 整性进行了一些补充，但对基于关联规则的知识表示而言仍然不 够完整，特别是对于一些前提或结论需要同时结合正项和负项的 规则，这些扩展方法都无法表达。为此，文献f 5 7 5 9 提出了一般 关联规则概念，它是形如xn a yn b 的蕴涵式。其中， x ，y ，a ，bg ，x 和a 不同时为空，y 和b 不同时为空，x ，y ，a ，b 两 两相交为空。 2 关联规则中没有考虑数量问题 上述这些针对关联规则的研究都是以布尔属性为基础的。无 论是负关联规则还是一般化关联规则，都只是含负项的布尔关联 规则。 事实上，数量属性普遍存在于各种类型的数据库中。对于数 量关联规则挖掘的研究可以实现对现实世界中稠密数据【2 5 】的挖 掘。例如，要分析获取网上购物人群的年龄构成分布知识，会使 用如下的规则形式：在网上购物的人群中，9 0 的人群年龄不在 3 0 4 0 岁。显然，这种关联规则考虑了与问题相关的规则的数量问 题。数量关联规则的研究已有不少文献【2 6 彤】，但如何将关联规则 相关的数量属性和负项的关联规则挖掘结合，无论从理论上还是 实际应用实践上都是有意义的。 本文有效地将负项和数量属性结合，提出含负项的数量关联 规则挖掘模型，使得关联规则挖掘理论更加完善。 1 2 本文研究的结构安排 关联规则挖掘是数据挖掘领域中的重要研究内容之一。本文 研究了关联规则挖掘方法，详细讨论了布尔关联规则、数量关联 规则和含负项的布尔关联规则问题。在此基础上，提出了一种含 负项的数量关联规则模型，给出了这种新规则的定义和具体的挖 掘算法。 论文结构安排如下： 第一章为绪论。讨论研究背景和研究意义，引入论文的主要 研究内容。 第二章为关联规则挖掘理论。讨论关联规则挖掘的基本概念 和挖掘过程，系统地分析和总结了现有关联规则的挖掘算法。着 重研究了数量关联规则挖掘的方法和含负项的布尔关联规则挖 掘，给出了基本概念，并对现有的挖掘算法进行了总结归纳。 第三章为基于频繁2 项集的数量关联规则挖掘方法研究。针对 购物篮分析中带数量的捆绑销售问题，提出了一种基于频繁2 项集 的数量关联规则挖掘方法。 第四章为含负项的数量关联规则挖掘。本章提出了含负项的 数量关联规则挖掘模型，给出了新规则的定义和挖掘过程中的几 个关键算法。 第五章对全文进行了简要的总结，讨论了算法的优缺点和进 一步的工作方向。 第二章关联规则挖掘概述 本章主要讨论关联规则挖掘的基本理论、现有挖掘算法及数 量关联规则挖掘和含负项的布尔关联规则挖掘。 2 1 关联规则挖掘的基本理论 2 1 1 基本概念 设项集i = i l ，1 2 ，i i ，i 。 ，d 是任务相关的数据库事务 t j ( j = i ，2 ，m ) 的集合，记为d = t j 【j = 1 ，2 ，m 。事务t j 由项集i 的若 干项构成，且 t j c _ i 。假设每一个t i 的唯一标识记作t i d i 。对子项集 x i ，如果x c _ t ，那么称事务t 包含子项集x 。设p ( x ) 表示数据库 中的事务记录支持项集x 的概率，它等价于子项集x 在事务数据库 中的支持度，记为s u p ( x ) = p ( x ) 。 定义2 1 ( 关联规则) 关联规则是形如xjy 的蕴涵式，即满足 x 中条件的数据库元组多半也满足y 中的条件。这里，x i , y c i ， 且x n y = a 。 文献 4 】引入了规则xjy 的支持度和置信度。它们分别反映 了规则的有用性和确定性。 定义2 2 ( 支持度) 假设关联规则xjy 在事务集d 中的支持度 s u p ( x jy ) 定义为同时包含x 和y 中项的事务数的百分比，可记 为： s u p ( xjy ) = p ( x y ) 。 其中，p ( x y ) 表示d 中的事务同时支持项集x 和y 的概率。 定义2 3 ( 置信度) 假设关联规则xjy 在事务集d 中的置信度 c o n ( xjy ) 是指包含x 和y 中项的事务数与包含x 的事务数之比， 则有： c o n ( xjy ) = p ( y i x ) = p ( x y ) p ( x ) 。 其中，p ( y i x ) 是条件概率，表示d 中的事务在支持项集x 的条 件下，支持项集y 的概率。 定义2 4 ( 强关联规则和弱关联规则) 给定事务集d ，若规则的 支持度和置信度满足用户给定的最小支持度和最小置信度的关 联，规则就是强关联规则；否则称为弱关联规则。 定义2 5 ( k 一项集) 包含k 个项的项集称为k 项集。 定义2 6 ( 频繁项集和频繁k 一项集) 项集i 的支持度计数满足用 户给定的最小支持度计数时，称i 是频繁项集。如果i 是k 项集，称 为频繁k 项集，记作l k 。 定义2 7 ( 候选k 一项集) l k 1 与自身连接产生的集合称为候选k 项集，记作c k 。 2 1 2 关联规则挖掘的过程 关联规则的挖掘过程如图2 1 所示。 图2 1 关联规则的掺掘过程 其中，数据选取、数据预处理、数据变换属于数据准备阶段。 挖掘频繁项集是从数据库事务集合发现所有满足用户给定的最小 支持度的频繁项集。关联规则产生是由频繁项集生成所有满足用 户给定的最小置信度的强关联规则。规则解释评估阶段是检测规 则是否冗余且满足用户的需求。挖掘频繁项集和规则产生是关联 规则挖掘的核心步骤。 2 2 关联规则挖掘算法 自1 9 9 3 年a g r a w a l 等人提出关联规则挖掘方法以来，对基于关 联规则的挖掘技术、方法和应用等方面有大量的研刭4 枷】。主要有 以下几个方面： ( 1 ) 多循环方式的挖掘算法 多循环方式的挖掘算法是利用逐层迭代的方法，由k 一项集连接 产生( k + 1 ) 项集，如此下去，直到找不到满足最小支持度的频繁 项集为止。该类算法包括a g r a w a l 等人提出的多次扫描数据库且产 生候选项集的a p r i o r i 算、法【4 1 、a p r i o r i t i d 和a p d o m y b r i d 算法【5 1 。 a p r i o r i t i d 算法是对a p r i o r i 算法的改进，通过对数据库的修剪来减 少扫描数据库的时间，但增加了对数据库修剪的计算和i o 操作； a p r i o r i h y b r i d 算法是a p r i o r i 算法和a p r i o r i t i d 算法的结合，先采用 a p f i o f i 算法扫描数据库，然后计算修剪后的数据库大小，若其可在 内存中进行处理则采用a p r i o r i t i d 算法，直到找出所有的频繁项集； p a r k 等人提出了采用h a s h i n g 技术对数据库和候选项集进行修剪的 d h p 算法【7 】，它减少了i o 的执行时间， ：e a p r i o r i 算法的效率明显 提高；s a v a s e r e 等人提出了分割数据库的p a r t i t i o n 算澍引，将数据库 分为互不相交的n 个子数据库，从每个子数据库中挖掘频繁项集， 最后将所有的项集合并，该算法只扫描两次数据库。此外，还有 文 9 提出的h p e 算法，文 1 0 提出的结合完全连接的改进a p f i o f i 算法等。 ( 2 ) 并行挖掘算法 关联规则挖掘的并行算法是指并行地计算和产生候选项集。 目前主要的并行关联规则挖掘算法有a g r a w a l 等人的c d ( c o u n t d i s t r i b u t i o n ) 算法、d d ( d a t ad i s t r i b u t i o n ) 算法l l3 | ，c h u e n g 等人的 d m a ( d i s t r i b u t e dm i n i n go fa s s o c i a t i o nr u l e s ) 算浏1 4 j ，王华秋等人 的f p a r m 算法【1 5 】等。c d 算法是基于a p r i o r i 算法的并行处理，其速 度较快、容易实现且要求各计算机间同步次数较少，但它的通信 量和候选项集较大；d d 算法改进了c d 算法的存储问题，更好地利 用了内存空间，但是d d 算法的执行效果都不如c d 算法；d m a 算 法要求各计算机间同步次数较多；f p a r m 算法尽可能地让每个处 理器独立地工作，减少同步次数以提高算法的效率。 ( 3 ) 增量更新挖掘算法 增量更新算法是在事务数据库d b 的基础上，增加或删除部分 数据集，或改变最小支持度和最小置信度阈值时，对新的数据库 进行挖掘。主要算法是d w c h e u n g 的f u p i l7 】和f u p 2 1 8 】算法，冯玉 才的i u a 和p i u a 算法【2 0 j 。其中，f u p 算法研究数据集的增加情况， 基本框架与算法a p r i o r i 相一致。f u p 2 同时考虑了数据集的增加和 删除问题。i u a 和p i u a 讨论了当最小支持度和最小置信度阈值发 生变化时，如何挖掘数据库d b 中的关联规则，其中p i u a 是在i u a 算法的基础上实现了教育共享内存的并行化处理。 ( 4 ) 基于限制和约束的关联规则挖掘 关联规则挖掘算法可以挖掘出数以千计的规则，而有些规则 对用户来讲是无用的或不感兴趣的。这时，用户希望通过自己的 判断来减少算法生成规则的数量。这些约束条件包括知识类型约 束、数据约束、维层约束、兴趣度约束等【2 4 1 。典型的研究有：s r i k a n t 等人研究了基于布尔表达式约束的多层关联规则挖掘问题【2 2 j ； r a y m o n dt n g 等人提出了一个用户参与的、且基于两个约束属性 ( 反单调性和简洁性) 的关联规则挖掘算法c a p 2 1 1 ，解决了传统关联 规则缺乏用户的参与和控制且用户的目的性不强的缺点。 ( 5 ) 其他挖掘算法 除了以上列举的几类算法外，还有：深度优先算法：! z i m j z a k i 等人提出的e c l a t 和m a x e c l a t 算法【2 3 】、数量关联规则挖掘算法 2 6 - 3 4 、含负项的布尔关联规则挖掘算法 3 5 - 4 0 1 等等。 2 3 数量关联规则挖掘 1 9 9 6 年r s r i k a n t 和r a g r a w a l 提出了数量关联规则的挖掘方法 【2 引，其主要思想就是将其转化成布尔关联规则的挖掘，然后利用 已有的挖掘布尔关联规则的方法得到有趣的规则。如何划分属性 取值区间是实现数量关联规则挖掘问题到布尔关联规则挖掘问题 转化的关键。 2 3 1 数量关联规则的定义 设项集i = i l ，1 2 ，i i ，i n ，p 为正整数集合。i 。= i x p ， 元组 表示属性x 的值为v 。i r - ix i ，l p ，u p ， l x u a 定义2 8 ( 数值属性) 若1 u ， 表示属性x 的取值在l 和u 之间，则称x 是数量属性。 定义2 9 ( 分类属性) 若l = u ， 表示属性x 的取值为l 或u ， 则称x 是分类属性。 定义2 1 0 ( 数量属性) 数值属性和分类属性统称为数量属性。 所有的数量属性集合i 己n a t t r i b u t ( x ) = x i x ，表示集合x 所包含的属性集合。 定义2 1 1 ( 事务支持项集) 设d 是事务数据库，r e d ，r c i 、， x c _ i ，。如果对任意的 e x ，存在 r ，使得1 x u ， 则称事务 支持x 。 定义2 1 2 ( 数量关联规则及其支持度和置信度) 数量关联规则 是形如xjy 的蕴涵式。其中，x i ，y i ，且 a t t r i b u t ( x ) f q a t t r i b u t ( y ) = o 。如果事务数据库d 中有s 的事务支持x uy ，则称规则xj y 的支持度为s ；如果支持x 的事务中c 的 也支持y ，则称规则x y 的置信度为c 。 2 3 2 数量关联规则的挖掘过程 假设事务数据库中的项是数值或分类类型的属性，数量关联 规则的挖掘过程分为3 个步骤： ( 1 ) 数值属性和分类属性取值范围的区间划分和映射 区间划分和映射实质上是将与挖掘任务相关的数值或分类属 性的取值范围经过区间划分后映射成相应的布尔属性值类型，形 成新的项集表示。如果属性的取值范围有限且很少，可以将每个 属性值映射为一个布尔型属性。如果属性的取值范围很宽，可以 将其分为若干区段，然后将每个区段映射为一个布尔型属性。 例如，对于m a r r i e d 属性的值为y e s 或n o ，可以映射为 ( m a r r i e d ：y e s ) 的值为1 ，( m a r r i e d ：n o ) 的值为0 。对于a g e 属性的值域 为1 0 3 9 ，可以将区间划分成( a g e ：1 0 1 9 ) ，( a g e ：2 0 2 9 ) 和 ( a g e ：3 0 3 9 ) ，然后将各区间映射成( a g e ：1 0 1 9 ) 的值为1 ，相应的 ( a g e ：2 0 2 9 ) 和( a g e ：3 0 3 9 ) 1 约值为o 。 又如，对于某交易数据库中的m a r r i e d 币l l a g e 属性( 表2 1 ) ，按上 述的划分和映射方法可以得到表2 2 ： 表2 1 某交易数据库 t i dm a r r i e d a g e 1 0 0n o1 7 2 0 0n o2 3 3 0 0y e s2 8 4 0 0y e s3 3 5 0 0y e s3 6 表2 2 区间划分和属性映射表 t l dm ：y e sm ：n o a g e ：1 0 1 9a g e ：2 0 2 9a g e ：3 0 3 9 1 0 00ll0 0 2 0 00101 o 3 0 0100l o 4 0 0lo0ol 5 0 0lo00l ( 2 ) 由区间划分的结果项集挖掘频繁项集 以区间划分和映射结果为基础，形成满足用户给定的最小支 持度的频繁项集。即根据候选项集搜索满足最小支持度的项，形 成频繁项集，并对频繁项集结果中的相同属性进行相邻区间的合 并处理。 ( 3 ) 由频繁项集获取关联规则 根据用户给定的约束条件( 如最小置信度) 获取满足条件的( 强) 关联规则。 数量关联规则的挖掘过程中，数值属性和分类属性的取值范 围的区间划分是基础。不同的区间划分方法和结果，不仅影响算 法的时空效率，还会影响挖掘出来的规则形式及规则运用的有效 性。挖掘频繁项集的过程可以采用成熟的经典算法及其改进算法 完成。事实上，区间划分和频繁项集的挖掘是数量关联规则挖掘 研究领域中研究的主要内犁2 5 j 。 2 3 3 数量属性值域的区间划分 数量属性是数值属性和分类属性的统称。数值属性可以是连 续的( 如销售额) ，也可以是离散的( 如年龄) 。分类属性可以是有序 的( 如职称) ，也可以是无序的( 如性别) 。区间划分是数量关 联规则挖掘的关键步骤。划分的方法通常有五种类型： ( 1 ) 使用预定义的概念分层对数量属性离散化 k a m b e r 等人提出了结合数量属性的静态离散化和数据立方体 技术挖掘关联规则的方澍1 1 。该方法对数量属性的离散化主要使用 了有关数量属性的预定义的概念分层知识将数量属性的值用相应 的概念区间代替，由于它必须建立在预定义的概念层次划分上， 这种区间划分方法要求领域专家事先参与概念层次的划分工作。 如果事先无法得到有关数据的相关领域知识，运用这种方法进行 数量属性值的离散化是困难的，其划分结果的合理性无法得到保 证。 ( 2 ) 等宽划分法 该类划分方法将数据划分成长度相同的区间。l e n t 、s w a m i 、 w i d o m 等人提出了根据规则聚类挖掘数量关联规则的a r c s 系统 i l l 。它使用等宽划分，主要用于挖掘左部有两个数量属性、右部只 有一个分类属性的数量关联规则。该方法将数量属性对映射到满 足给定分类属性条件的2 d 元组栅格上，然后通过搜索栅格发现点 簇，并由此产生关联规则。 ( 3 ) 等深度划分法 等深度划分法使得区间中包含的元组个数相同。1 9 9 6 年 f u k u d a 等人提出了基于二维的数量关联规则挖掘方法( 2 6 上7 1 。其规则 前件只包含两个数量属性，规则的后件只出现一个范畴属性。 m i l l e r 和y a n g 考虑了数据之间的距离关系，用聚类算法使得数量型 数据的分区更有意义【3 1 。吉根林等提出了基于可信度最优的挖掘算 法1 2 引，它在等深度划分的基础上利用凸包处理技术，通过求解两 点之间的斜率最大值找出最优的置信度区间。 ( 4 ) 部分k 度完全方法【2 5 】 前述的几种划分方法都不可避免“c a t c h 2 2 ”问题： 1 ) 过小支持度问题：当划分区间的数目过多时，可能使每个 区段对应的属性的支持度很低，不能有效地生成全部频繁项集； 2 ) 过小置信度问题：当划分区间的数目过少时，可能使每个 区段对应的属性的置信度很低，造成信息的丢失。 为此，s r i k a n t 和a g r a w a l 等人提出了部分k 度完全法f 2 5 】，引入相 对于频繁项集c 的k 完全集概念来评估对数量数据进行划分所产生 的信息丢失。 定义2 1 3 ( 频繁项集c 的k 完全集) 假设c 是由事务数据库d 挖掘 得到的频繁项集。当集合p 符合以下条件时，称p 为频繁项集c 的k 完全集：( 1 ) p c ；( 2 ) x p r x x x 7 p ，且对任意x c ， 存在唯一一个x p ，使得 5 c 是x 的泛化，且s 印( 文) k s 妒( x ) ； 对vy x ，存在文，其中是y 的泛化，且s u p ( 9 ) k x s u p ( y ) 。 假设n 为待分区的属性个数，k 为预先指定的部分完全性级别， ( 其取值范围为1 5 k 5 ) ，m i ns u p 为最小支持度。为了达到k 完全 性，必须让每个区间的支持度小于 k 一1 m l n s 印i ( 2 1 ) 于是每个属性所要分割的区间数为： 2 n m i n s u p x ( k 1 ) f 2 2 ) 通过对k 值的有效设置，在一定程度上可以限制置信度过小造 成的信息丢失。 ( 5 ) 基于聚类的划分 聚类方法可以通过数据之间的距离关系定量地确定聚类类 型。它可以在没有已知参考模型的前提下根据样本数据的特性进 行分类。在数量关联规则挖掘问题中，利用聚类方法将数量属性 进行分类，可以准确的体现数据的分布情况。例如，文献 2 9 根据 数据的分布特点，对分类属性概括、数量属性聚类的方法将数量 属性划分成区间。文献 3 0 利用聚类方法在迭代过程中动态地调整 中心个数，形成了可用于高偏度数据挖掘f l 勺p k c a a 算法。 ( 6 ) 基于模糊理论的划分 将属性值的取值范围进行区间划分存在一个明显的缺陷，那 就是它要求区间的划分精确，否则，可能由于区间划分的不精确 带来挖掘到的知识不能准确反映应有的领域规律。为了减少由于 精确的区间划分造成的边界模糊性带来的信息丢失。t z u n g p e i h o n g - 等k t 3 1 1 将模糊集合理论引入到关联规则挖掘中。k u o kcm 、 f u a 等人提出了模糊c 均值算法讨论关联规则的挖掘问题。 也有学者将其他技术引入挖掘中，例如杨明等人【3 4 1 提出一种 基于求拐点的对数量属性进行划分的算法；刘乐乐等人利用数 量属性间互信息熵找到具有强信息关系的属性集，从而得到频繁 项集。 2 4 含负项的布尔关联规则挖掘 传统的关联规则挖掘【4 - 1 4 没有考虑项集之间的负相关问题。含 负项的关联规则挖掘的研究【3 l 】不仅丰富了关联规则的理论研 究，也得到了有效的应用，如超市商品的摆设决策问题【5 6 j 。 2 4 1 基本概念 定义2 1 4 ( 正项集、负项集) 给定项集i 和数据库事务集合d 。 如果某个项目i k i ，称该项目为正项目或正项。如果某个项目i k 萑i ， 称该项目为负项目或负项，记为( 。负项集记为x = i r a i 叶，i 。 ， 它不是集合x 的补集，而是不出现在事务t 中的项目的子集。相应 地，正项集可记为y = i 。，i 时，i n ) 。 定义2 1 5 ( 正关联规则) 正关联规则是形如x y 的蕴涵式。 其中，x i ，y i ，且x f q y = 。 对于含负项的关联规则研究，从规则类型的角度可以分为负 关联规则研究和一般化关联规则研刭5 8 】。 定义2 1 6 ( 负关联规则) 形如xjy 、xjy 及xjy 的关 联规则称为负关联规则。其中，x g ，y 日，x 和y 分别表示某条 记录中不含x 和y ，且x 、y 、x 、y 任意两个的交集为空。 也就是说，负关联规则反映的是项集之间的否定联系。例如， 假设在交易事务数据库中，x 表示购买咖啡，y 表示购买茶叶，则x 表示不购买咖啡，y 表示不购买茶叶，x jy 表示顾客购买了茶 叶后不会购买咖啡。 定义2 1 7 ( 一般化关联规则t s s j ) 形如x n ajy n b 的蕴涵式。 其中，x 、y 、a 、b 包含于t ，x 和a 不同时为空，y 和b 不同时为 空，x 、y 、a 、b 任意两个的交集为空。即对每一条支持该规则的 事务t ，只有x 、y 同时出现在事务t 中，而a 、b 不出现在事务t 中。 可见，负关联规则和正关联规则都是一般化关联规则的特殊 情形。 正项和负项是相对应的，有关负项支持度的计算方法如下： 定理2 1 对任意的负项i ，设它对应的正项i k 的支持度计数为 i k c o u n t ，那么，e 的支持度计数可表示为： i k c o u n t = l d b i - i k c o u n t( 2 3 ) 其中，l d b t 表示事务数据库中事务的总个数。 2 4 2 负关联规则的支持度和置信度的具体计算方法 负关联规则的支持度和置信度可以利用正频繁项集的支持度 和置信度得到。下面，以定理的形式给出其计算公式。 定理2 2 设非空项集xg ，yg ，且x n y 嘞，有 ( 1 ) s u p ( x ) = 1 一s u p ( x ) ； ( 2 ) s u p ( x uy ) = s u p ( x ) 一s u p ( x u y ) ； ( 3 ) s u p ( xu y ) = s u p ( y ) 一s u p ( x u y ) ； ( 4 ) s u p ( xuy ) = l s u p ( x ) 一s u p ( y ) + s u p ( xuy ) 由定理2 2 及置信度的定义，很容易得到负关联规则的置信度 计算方法。 推论2 1 设非空项集xg ，yg ，且x n y 剐，有 ( 1 ) 伽( 轴访墅挚= 1 - c o n ( x jysup ) 1 人j ( 2 ) 删( b y ) = 型警 聆(叉j-)：1-sup(x)-sup(y)+sup(xuy) ( 3 ) 1 一s u p ( x ) = 1 一c d ，l ( 又j y ) 推论2 2 设非空项集xg ，yq ，且x r l y = n u l l ，有 ( 1 ) c d 万( xjy ) + c o 以( xj y ) ：1 ( 2 ) c o n ( x y ) + c o n ( xjy ) = 1 文献 3 6 讨论了规则的前件x 和后件y 的支持度变化时 xjy 、xjy 、xjy 和x y 四种基本的关联规则的置信度 的变化。文中不仅给出了它们的值域，而且还给出了它们的变化 曲线，并指出置信度的取值对关联规则的数量有非常大的影响。 2 4 3 关联规则的相关性 关联规则的相关性的定义【3 7 】： c o 玎。：亟盟 ( 3 2 ) c o n k b 2 s u p ( 二a ) x s u p 一( b ) 【3 2 ) c 0 1 t a b 的值有3 种情况： ( 1 ) 如果c 0 1 t a , b 1 ，那么a 和b 正相关，即项集a 出现越多，项 集b 出现的也越多； ( 2 ) 如果c 0 1 t a , b = 1 ，那么a 和b 独立，项集b 的出现与项集a 无关： ( 3 ) 如果c o l l 八b 1 ，则有：( 1 ) c o r r 百 l ，则有：( 1 ) c o n ( ajb ) c o n ( ajb ) ： ( 2 ) c o n ( ajb ) c o n ( ajb ) ；反之亦反之。 由定理2 3 和推论2 3 知道，在挖掘正负关联规则时只要对项集 的相关性进行判断，就可以避免矛盾规则的出现，即： 当c o r r 九b l 时仅挖掘规则ajb 和ajb ； 当c o l r a b 1 时仅挖掘规则aj b 和ajb ； 当c o r r 九b = 1 时不挖掘规则。 2 4 4 含负项的关联规则挖掘算法 近年来，对含负项的关联规则的研究是关联规则挖掘领域研 究的热点，下面对它进行讨论。 2 4 4 1 两种最基本的算法思想 目前，挖掘含负项的关联规则基本算法有直接a p r i o r i 算法【3 8 】 和“近似负关联规则算法陬加1 。 直接a p f i o f i 算法的思想是将事务看成一个布尔矩阵，对于每一 列a 增加一个否定列a ，从初始项集及其补集中挖掘关联规则。给 定一个初始项集的矩阵，它的每一行代表一个事务，初始项集的 补集就是将初始项集的每一个0 、1 互换。从理论上讲，通过这种 方法可以挖掘出所有的正负频繁项集，但需要对原始数据集进行 扩充。扩充后的数据集是原始数据集的两倍，会使数据集变得很 庞大，而且大大地降低挖掘算法的效率。 “近似负关联规则算法首先采用传统的关联规则挖掘算法 挖掘出正频繁项集，再考察频繁项集的正项和负项的关系，并通 过定理2 2 和推论2 1 获取与主题相关的负关联规则。与直接a p r i o r i 算法相比，由于其仅仅是在挖掘出传统的正关联规则基础上通过 公式定理来推导出负关联规则，其挖掘出的负关联规则是有限的。 实际上，负关联规则不仅存在于频繁项集中，也可能存在于非频 繁项集之中1 4 ，不能轻易地删除数据集中的非频繁项集。 2 4 4 2负关联规则挖掘算法 负关联规则挖掘是挖掘形如xjy 、xjy 、xjy 及 x y 的关联规则。算法大部分是基于上述两种算法思想进行挖 掘。目前，负关联规则算法的研究内容可以归结为： ( 1 ) 加入某些特定的约束条件形成相应的挖掘算法 约束条件包含相关性、对比影响度及有效度等【 3 9 , 4 0 , 4 2 4 5 】。 在相关性检验方面，可以将相关性条件作为正负关联规则生 成的判定条件，检测并删除相互矛盾的规则。该类算法有m p n a r 算法、m i n i n g 算法f 4 0 】、p n算澍4 2 1 和算法【4 3 】p a r & n a ra rc a 等。文献【4 4 】和 4 5 】分别引入了对比影响度和有效度约束条件对算 法进一步优化，以提高算法的挖掘质量。 ( 2 ) 通过对兴趣度评估方法的改进来有效地删除无意义的、冗 余的、甚至是矛盾的规则的挖掘算法 文献 4 1 以兴趣度为基础，在生成候选项集时采用了类a p r i o r i 算法。文献【4 6 根据p i a t e t s k y s h a p i r o 的主张推广了p s 兴趣度，使 其不仅能够适用于负关联规则，还能够对关联规则的相关性进行 判断，其算法能够同时挖掘正、负关联规则。文献【4 7 】通过用提升 率代替置信度来避免挖掘出相互矛盾的虚假关联规则。 实质上，兴趣度和上述的相关性等度量