（计算机应用技术专业论文）量化关联规则模型与挖掘算法研究.pdf

量化关联规则模型与挖掘算法研究 摘要 关联规则挖掘的研究一直是数据挖掘领域的研究热点之一。它主要是指在 满足最小支持度和最小信任度的条件下，从数据库中挖掘出如“购买物品a 和b 的客户8 0 同时也购买c 和d ”这样的规则。早前这方面的研究大都以事务数据库 为主要对象，其属性局限于布尔类型。在科学计算和商业领域的数据库中属性 类型较为丰富，且多为数量属性和类别属性，属性取值不再是布尔量0 或1 。在这 样的数据库中进行关联规则挖掘称为量化关联规则挖掘。较之布尔关联规则挖 掘，量化关联规则挖掘具有更为普遍的意义。本文主要研究工作如下： ( 1 ) 研究了量化关联规则模型，分析总结了当前量化关联规则挖掘的研究 现状，并重点研究了一些挖掘算法，总结了这些算法的优势和存在的不足。 ( 2 ) 针对量化关联规则挖掘中对不同量化属性的划分区间进行链接，计算 支持度等操作时间开销大，导致算法执行效率不高的问题，提出考察属性间互 信息值，并基于强信息关系属性挖掘量化关联规则的挖掘算法b m i q a r 。实验 表明，算法b m i q a r 有效地减少了挖掘过程中的计算量，提高了算法的性能， 并且能得到绝大部分置信度较高的规则。 ( 3 ) 针对现有的量化关联规则挖掘方法仅从项目的权值或数量某个方面 考虑，不能挖掘出满足某些特定要求的关联规则的问题，提出将项目数量与权 值进行整合，在k 获利支持期望的概念基础上设计的基于获利最大化的量化关 联规则挖掘算法w q a r 。实验表明，w a q r 算法得到的是那些真正获利最多的 项目组合，而由这些项目组合得到的规则也是获利项目间的关联知识。 关键词：数据挖掘量化关联规则获利最大化互信息 r e s e a r c ho nq 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 o d e l a n da l g o r i t h m 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 gb e i n go n eo ft h ek e yp o i n t si nd a t em i n i n gf i e l di st o f i n ds u c har u l ea s “8 0 c u s t o m e r sw h ob u yaa n dba l s ob u yca n dd i na d a t a b a s ew i t hg i v e nm i n i m u ms u p p o r ta n dm i n i m u mc o n f i d e n c e i nt h ee a r l yt i m e ， m o s to ft h es t u d i e sb a s eo nt r a n s a c t i o nd a t a b a s ec o n s i s t i n go n l yo fb o o l e a n a t t r i b u t e s w h e nc o m et ot h ed a t a b a s e si nt h es c i e n c ea n db u s i n e s sf i e l d s ，a t t r i b u t e s a r en o tl i m i t e dt ob e i n gb o o l e a nb u tc a nb ee i t h e rq u a n t i t a t i v eo rc a t e g o r i c a l m i n i n ga s s o c i a t i o nr u l e si ns u c hd a t a b a s e s ，c a l l e dq 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 m i n i n g ，i sam u c hm o r ei n f l u e n t i a lr e s e a r c hp r o b l e mw h e nb e i n gc o m p a r e dt o b o o l e a na s s o c i a t i o nr u l e sm i n i n g t h em a i nc o n t e n to ft h i sd i s s e r t a t i o ni sa sf o l l o w ： ( 1 ) m o d e l ，a l g o r i t h m sa n dc u r r e n tr e s e a r c h e so nq u a n t i t a t i v ea s s o c i a t i o nr u l e m i n i n ga r es t u d i e di nt h i sd i s s e r t a t i o n ，a n ds o m ek n o w na l g o r i t h m s a r ea n a l y z e d a n ds u m m a r i z e d ，a n dt h e a d v a n t a g e a n dd e f i c i e n c yo ft h e s ea l g o r i t h m si s r e p r e s e n t e d ，t o o ( 2 ) d u et ot h ec o m b i n a t i o no fv a l u ei n t e r v a l so fq u a n t i t a t i v e a t t r i b u t e sa n d c o m p u t a t i o no ft h es u p p o r t f o rt h o s ei n t e v a l sc o s t i n gl o t so ft i m ea n dc o n s t i t u t i n ga h a m p e rt o w a r dt h ee f f i c i e n c yo ft h em i n i n ga l g o r i t h m ，a l g o r i t h mb m i q a rm i n i n g 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 sb e a s e do na t t r i b u t e sw h i c hh a v es t r o n gi n f o r m a t i o n r e l a t i o n s h i pi sp r o p o s e d t h ee x t e n d e de x p e r i m e n t ss h o wt h a tt h em i n i n ge f f i c i e n c y o fa l g o r i t h mb m i q a rh a sb e e ni m p r o v e dg r e a t l ya n dm o s to ft h er u l e sw i t hh i g h c o n f i d e n c ea r eo b t a i n e d ( 3 ) a st h ee x i s t e d s t u d i e sj u s t p a i da t t e n t i o nt o e i t h e rt h ew e i g h to rt h e q u a n t i t a t i v ev a l u eo ft h ei t e m so n l ya n dr u l e sm i n e du s i n gt h e s em e t h o d sd i d n t a l w a y sa c c o m m o d a t et ot h er e q u i r e m e n t so ft h eu s e r sw h e nm i n i n gq 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 si nd a t a b a s ew h i c hc o n t a i nq u a n t i t a t i v ea t t r i b u t e s ，a l g o r i t h m w q a rw h i c hc o n f o r m st h ew e i g h ta n dt h eq u a n t i t a t i v e v a l u eo ft h ei t e m sa n d b a s e so nt h ec o n c e p to fk - p r o f i ts u p p o r te x p e c t a t i o ni sd e s i g n e d p r a c t i c a l e x p e r i m e n t ss h o wt h a ta l g o r i t h mw q a r c a nm i n em a x i m a lp r o f i t si t e m s e t sa n d r e l a t i o n s h i p sb e t w e e nt h ei t e m s e t s k e y w o r d s ：d a t am i n i n g ；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 s ；m a x i m ap r o f i t ；m u t u a l i n f o r m a t i o n ； i v 插图清单 引理2 图示1 1 交易分布曲线图1 4 c f 树结构1 6 三角形隶属函数模型1 9 梯形隶属函数模型1 9 正态分布隶属函数模型2 0 强信息关系图g m i 2 9 前缀树示例3 0 d 1 属性间的互信息值与其标准化后的值3 2 两种算法挖掘频繁项集的运行时间3 3 两种算法得到的规则数比值3 4 w q a r 与w a r 运行时间与数据库规模的关系4 2 w q a r 运行时间与r a p s 变化的关系4 2 l 2 3 4 5 6 1 2 3 4 5 l 2 一 一 一 一 一 一 一 一 一 一 一 一 一 2 2 2 2 2 2 3 3 3 3 3 4 4 图图图图图图图图图图图图图 表格清单 一个量化关联规则的例子9 转变后的数据库9 频繁项集表1o 等深与基于距离划分示例1 5 示例教职工数据库2 3 离散化后的数据库2 3 性别划分2 7 年龄划分2 7 工资划分2 7 学历划分2 7 属性间的标准化后的互信息2 9 示例数据库3 6 商品数据库3 8 交易数据库3 9 两种算法得到的频繁项集4 3 两种算法得到的规则的比较4 3 i x 1 2 3 4 1 2 3 4 5 6 7 1 2 3 4 5 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 一 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4表表表表表表表表表表表表表表表表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金胆王些太堂 或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名： 签字魄叫年r 月c 死 学位论文版权使用授权书 本学位论文作者完全了解金g 巴王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金起工些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 参i 豸琢 | 签字日期：沙1 年呷月( ，日 学位论文作者毕业后去向： 工作单位： 通讯地址： i i 导师签名： 签字日 电话： 邮编： 垆月7 日 致谢 首先感谢我的导师田卫东副教授近三年以来对我在学业上的指导和生活上 的关心。田老师治学严谨、思维敏捷、工作勤奋，是我学习的榜样。在我学习 过程中，出现困难时候，田老师给了我无微不至的帮助。在论文的构思和撰写 整个过程中给了我精心的指导，提出了许多宝贵意见，才使得本文得以顺利完 成。我谨在此向田卫东老师表示衷心的感谢。 同时在这里，我要十分感谢计算机与信息学院的胡学钢教授，在我攻读硕 士期间，他给了我许多指导、关怀和帮助，并提出了许多宝贵的意见，令我受 益匪浅。 除此之外，我还要感谢吴共庆、张玉红、张晶、胡春玲等老师，与他们一 起对数据挖掘的课题内容的讨论，开拓了知识范围，对我论文的构思有很大的 帮助：感谢合肥工业大学人工智能与数据挖掘研究室每个成员对我的关心和帮 助。 还要特别感谢合肥工业大学可视化与协同计算研究室( v c c ) 的老师和同 学，我在学习研究过程中得到了他们热情和无私的帮助。 感谢计算机与信息学院的王浩教授、曹航老师、徐静老师等为我所付出的 辛勤劳动! 感谢与我共同学习，给我鼓励和帮助的同学们，非常高兴与你们同渡三年 美好的时光。 最后，感谢我的父母，是您们给了我无尽的支持与鼓励! v 作者：刘乐乐 2 0 0 9 年4 月 第1 章绪论 本章介绍了量化关联规则挖掘的研究背景、意义及研究进展，并对本文研 究的主要内容进行了概括，给出了本文的组织结构。 1 1研究背景及意义 1 1 1k d d 与数据挖掘 无论是商业企业、科研机构或者政府部门，在过去若干年的时间里都积累 了海量的不同形式的数据资料。且随着i n t e r n e t 的发展，数据资料更像洪水似 地涌来。在这些大量数据的背后隐藏了很多有意义的信息。传统的数据分析和 数据库查询方法，对这些巨量数据进行分析和处理时，不仅耗费大量的计算时 间，而且很多情况是依赖于事先对数据之间关系的假设和估计，这显然己经不 能满足人们日益增长的对数据中隐含知识的渴求。于是，数据挖掘和知识发现 ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ，简称d m k d ) 技术应运而生，并得以蓬 勃发展。 数据挖掘【l 儿2 j 【3 】，就是从大型数据库的数据中提取人们感兴趣的知识。这些 知识是隐含的、事先未知的潜在有用信息，提取的知识表示为概念( c o n c e p t s ) 、 规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。这种定义把数据挖 掘的对象定义为数据库。而广义的说法是【4 】：数据挖掘意味着在一些事实或数 据的集合中寻找模式的决策支持过程。数据挖掘技术从一开始就是面向应用 的。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的。 数据挖掘的任务主要有两类：预测和描述。预测指的是预测未知的感兴趣 的变量或发现某些实例未来的行为模式；描述是指寻找可以理解的描述数据的 模式。预测和描述可以通过下列方法实现： ( 1 ) 关联规则( a s s o c i a t i o nr u l e s ) , 关联规则是指数据或对象之间的相互依 赖关系，而发现关联规则的任务就是从数据库中发现那些置信度和支持度都大 于给定值的规则。 ( 2 ) 分类( c l a s s i n c a t i o n ) ：分类的含义就是指从一组已知的、已经具有类别 的训练数据中，提取出一个分类模型，然后把该分类模型应用于数据库中的那 些有待进行类别判断的数据上，实现对它们的分类。 ( 3 ) 聚类( c l u s t e r i n g ) ：即对一系列未分类客体依据客体属性进行类别的识 别，按照其相似性分成若干类别。聚类的目的是使得属于同一类别的个体之间 的距离尽可能的小而不同类别的个体间的距离尽可能的大。 ( 4 ) 序列模式( s e q u e n t i a lp a t t e r n s ) 序列模式是指在多个数据序列中共同的 行为模式。 ( 5 ) 偏离发t l - 观( d e v i a t i o nm i n i n g ) , 是指数据库中客体与常规或期望模式的 偏离或评估。如在服务器上发现某些站点访问方式在某段时间内其行为不同于 大多数其它站点的情况。 1 1 2 布尔关联规则 关联规则最早是由i b m 的研究员r a g r a w a l 和r s r i k a n t 等人，在研究从商业 零售事务数据库中发现顾客购物规律时提出的一种有趣的规则。 早期关联规则挖掘的一般对象是事务( t r a n s a c t i o n ) 数据库，这种数据库包 含的属性都为布尔属性，得到的规则也称为布尔关联规则，其主要应用是零售 业，比如超级市场的销售管理。关联规则就是发现这些交易项目( 指交易中的内 容。比如，电脑、软件等都是项目) 之间是否存在着某种关联关系。例如，关联 规则可以表示为“购买了电脑的顾客中有8 0 的人又买了办公软件”。这种关 联规则提供的信息可以用作商品销售目录设计、商品的采购等。 关联规则挖掘任务或问题【5 】是：给定一个事务数据库，求出所有满足最小 支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 的关联规则。挖掘过程可以分为两步， 第一步是发现所有频繁项集；第二步是从频繁项集构造满足最小置信度的规 则。求出频繁项集是关联规则挖掘算法的关键，较为著名的有，r a g r a w a l 等提 出的a p r i o r i 算法【6 】，j p a r k 等提出的使用哈希( h a s h i n g ) 技术的d h p 7 】算法。 i 1 3 量化关联规则 然而实际应用中的数据库，如在科学计算和商业领域中的数据库，属性大 多是可以取多个值的，这种属性称为量化属性( q u a n t i t a t i v ea t t r i b u t e ) ，如工资、 年龄和类别型属性( c a t e g o r i c a la t t r i b u t e ) ，如学历、颜色等。这些属性取值范围 不再是布尔量0 或1 。在这样的数据库中进行关联规则挖掘称为量化关联规则挖 掘【9 1 。 量化关联规则一般形式如下： = ：, ，其中a g e 和n u m c a r s 为量化属性，m a r r i e d 为类别属性。类别属性具有少数 有限个不同值，值之间无序；量化属性取值是连续数值，并在值之间有一个隐 含的序。量化和分类属性统一的记法为【s j ：如果令i = x l ，x 2 ，x m 为属性集，n 表示正整数集，记i ，= i x n 。那么用 i v 表示属性x ，与它相联系的值为v 。 再令i r = e i x n x nj 如果x 为量化属性，则l u ；如果x 为类别属性， 则l = u 。所以，三元组 就可以表示一个取值位于区间 1 ，u 】上的量化属 性，或者一个值为l 的分类属性。 一个量化关联规则r 是形如x = y 的蕴涵式，有xci r ，yci r ， a t t r ( x ) n a t t r ( y ) = a ，且有a t t r ( r ) = a t t r ( x ) u a t t r ( y ) 。规则x = y 的支持度和置信 度分别大于用户指定的最小支持度和最小置信度。 2 由于布尔关联规则的挖掘算法已较成熟，因此一种自然的想法是将量化关 联规则挖掘问题转换为布尔关联规则的挖掘问题。当属性的全部取值数量是少 数有限个时，只需将每个属性值映射为一个布尔属性即可；当属性的取值范围 很宽时，则需将其分为若干区间，然后将每个区间映射为一个布尔属性。这样 一来，对量化关联规则挖掘算法的研究就转移到如何对量化属性定义域的合理 划分的问题上来。 1 2 现有量化关联规则挖掘研究 1 2 1基于区间划分的量化关联规则 s r i k a n t 和a g r a w a l 提出量化关联规则挖掘算法s a 9 1 ，它将量化属性定义域 划分为不同区间，使每个区间成为新的布尔属性，从而将量化关联规则挖掘问 题转变为布尔关联规则挖掘问题。采用了一种称为部分完全性的、用于测量分 区带来的信息损失的度量来指导区间划分的个数。 f u k u d a 等直接将量化属性定义域划分成多个互不相交的区间【l0 1 ，且使每个 区间中包含的元素个数相同，挖掘过程中再考虑相邻区间的合并。虽然对于大 型数据库，这种方法能较快的获得划分区间，但所形成的区间表达不出属性取 值分布的意义；张钹等为获得有价值的区间，将量化属性的取值与其在数据库 中出现的次数映射到二维表上】，找n k 对局部最小点m i n l i 和m i n r i 间的交易 次数s u m i ，若s u m i 大于某个阈值时，则认为m i n l i 和m i n r i 之间的区间是有价值 的，将之用于规则挖掘。 为了考虑属性取值分布的意义，形成有效的划分区间，聚类的方法被应用 于量化关联规则的挖掘。这类方法需要选择一个数据聚类的标准，将量化属性 定义域划分为各个聚类子区间。在文献 1 2 中，m i l l e r 和y a n g 指出等深划分的 区间缺乏意义，在获得属性的取值区间或集合时，他们期望能反应属性取值之 间的距离。由于认为把较近的属性取值放在一起更有意义，为了达到这个目的， 提出使用b i r c h 】算法在量化属性上发现聚类进而形成数据项，然后使用布尔 关联规则挖掘算法a p r i o r i 进行规则挖掘。c h i e n 等考虑了区间的距离度量，并采 用一种层次聚类算法来得到有效的划分区间【1 4 】。它通过重复计算一个代价函数 来决定对两个相邻的区间进行连接聚集，当得到区间的两个特征值内部连接性 和闭包性的误差之和的最小值时，利用区间连接次数形成最终划分。 1 2 2 模糊关联规则 区间划分普遍存在着尖锐边界问题，即区间划分会将区间附近的一些潜在 取值排斥在外，从而使某些有价值的关联规则因区间的划分不合理而无法得 到，因此需要一种划分区间之间的平滑变迁来满足人们对规则的有效获取的要 求。于是，有学者通过定义在属性论域上的模糊集来软化边界【1 5 】【1 6 】。 t ph o n g 等人将模糊集的理论引入到关联规则挖掘中，并提出一种典型的 模糊关联规则挖掘( f u z z ya s s o c i a t i o nr u l e sm i n i n g ) 算法【1 7 】。首先使用隶属函数将 每一个量化数据转化为对应模糊集的隶属度，计算所有事务中各属性抽象出的 模糊集的隶属度之和。每一个属性在下面的挖掘过程中只采用具有最大隶属度 和值的模糊集，保证了属性的数量与原来一致。算法把挖掘的重点集中于最重 要的模糊属性上，减少了时间复杂度。 模糊集的引入较好的解决了区间划分的尖锐边界问题，且可以用语言值来 标示数量( 数据) 的意义，使得得到的规则易于理解，更加符合人类的思维习 惯。a g y e n e s e i 等人提出加权模糊关联规则挖掘来反映不同属性项的不同重要 性【1 8 】【1 9 】【2 0 1 ，每个属性都附带一个用户指定的权值，再通过定义加权支持度和 加权置信度来衡量规则的有趣性。t ph o n g 在文献 2 1 】中将衡量有趣性的参数 用语言值表达，从而使之更自然。 已有的算法在进行模糊关联规则挖掘时，都只是发现在单一概念层的规 则，而项目间的多概念层的模糊关联关系在实际应用中也较为普遍。t ph o n g 等提出对已知的分类层次树的各节点编号【2 2 j 【2 3 1 ，那么数据库中的项目就可用层 次树叶节点所对应的编号代替。再将项目的量化值转化为其对应的模糊集的隶 属度，在这样的数据库中进行规则挖掘，由于项目的编号包含了不同概念层的 信息，能获得跨多层的模糊关联规则。为了进行高效的多层模糊关联规则挖掘， h e c h i u a 等提出一种利用基于聚类的模糊集表1 2 4 l 的方法，它只要求一次数据库 的扫描，以得到模糊集表，挖掘过程中的比较、计算操作只需用到表的部分内 容，避免了不必要的计算，使得算法效率有所提高。 可注意到许多数据库不是静态的而是实时更新的，当有数据记录加入或删 除时，可能导致已有的模糊关联规则不可用或带来新的规则，陆建江等认为可 通过维护频繁模糊属性( 项目) 集来对数据库中的模糊关联规则进行更新【2 5 1 。 分别计算原始数据库d b 和新增数据库d b 中的频繁模糊属性集在大数据库d bu d b 中的支持度，如果它们具有最小支持度就加入到更新的频繁模糊属性集中。 此外，陆建江等应用r f c m 算法【2 6 】确定正态模糊数的两个参数，并借助正 态模糊数模型来划分数量属性的论域【2 ，在这个基础上来挖掘模糊关联规则。 在进行模糊关联规则挖掘时，一个重要问题是根据量化属性取值的分布特 征来确定合适的模糊集及隶属函数。模糊集和隶属函数一般是领域专家提供， 但这在很多应用领域是不现实的，隶属函数较难确定，往往成为模糊关联规则 挖掘的瓶颈。上述的模糊关联规则的挖掘方法多采用三角隶属函数。隶属函数 的确定还有基于聚类的方法【2 引，以及采用遗传算法来提取特征函数从而确定和 优化隶属函数的方法【2 9 】等。另外，基因的概念也被用于形成隶属函数f 3 0 】【3 1 1 。 4 1 2 3 量化关联规则扩展模型 量化关联规则的研究不仅包括规则的挖掘，还体现在新的量化关联规则模 型的发现。量化关联规则传统的形式是：x l a - - ( x 2 y l b - y 2 ，a u m a n n 和 l i n d e l l 注意到量化属性的划分区间y l b f ( d x ) = s t a t i c ，s u p p o r t 其中x 是一个项集，其属性包含在属性集a 中，d x 是数据库d 中满足 x 的数据值，函数f 对属性集b 在d x 中的数值进行计算得到相关统计值，其 中ar 、b = 0 。由于规则的右件不是项集，s u p p o r t 是数据库d 中只支持项集x 的事务的个数。可注意到，这里规则的后件可以对多个量化属性的值进行计算。 这类规则提供了对量化属性进行分析的一种统计学观点，比较适合于某些特定 的应用场合，如股票分析等。 1 2 4 隐私保护量化关联规则 进行数据挖掘的同时保护用户数据的隐私是数据挖掘领域一个重要而富 有挑战性的课题1 35 l 。 在隐私保护关联规则挖掘中，罗永龙等提出一种基于随机响应技术 ( r a n d o m i z e dr e s p o n s e ) 的隐私保护布尔关联规则挖掘算法【36 | ，但由于量化属性 是数值型的，且需要获得全局数据的分布并进行离散化，使该方法不适合于挖 掘量化关联规则。对于隐私保护量化关联规则挖掘，k a n t a 等为实现处理各局部 节点的数据集而不透露数据的所有者给其他的节点，需要对每个数据加密n 次 【3 7 】，n 为节点个数，当n 和数据规模较大时将耗费大量计算时间。j i n g 等在文献 【3 8 中提出了一种基于聚类特征树( c f t r e e ) 的方法，他们首先采用一种公钥 加密算法r s a 将数据加密，使得数据加密的次数与节点个数没有关系，并满足 了如下要求：没一个节点能得知任何数据的所有者：由于随机划分，没有一个 节点能获悉其他节点上的数据集大小。在获取形成规则的取值区间时，采用了 在每个局部节点上对属性值构建c f t r e e ，然后将每个c f t r e e 的叶子节点发送到 主节点重建c f t r e e 的方法，由于c f t r e e 特有的性质任何单个属性值的信息不会 透露出来，而由于前面对数据集的安全处理，每个节点上的c f t r e e 信息也不会 透露。 1 3 本文主要研究内容 从上述内容可以看到，较多的研究都集中在对量化属性的处理，对定义域 进行离散化或在其上定义模糊集。在相应处理后大多采用已有的成熟布尔关联 规则的挖掘算法进行规则挖掘。对于量化关联规则挖掘问题，量化属性划分后 将形成多个取值区间，若每个属。| 生a i ( 0 i ? m i ，对这样数目的来自不同属性的区间( 项 目) 进行链接，计算支持度等操傩时间开销是相当大的。因此，有必要寻找一 种有效的方法来提高算法的效率。 量化关联规则反映了量化属性的不同取值( 区间) 之间的蕴涵关系，而这 种关系实际上间接体现了属性相互间的取值确定的概率，而在信息论中互信息 描述了两个变量之间的相关性，也可理解为某个变量的取值对另一个变量取值 的确定的能力，于是本文利用互信息的概念来考察属性间的关系。如果两个属 性的互信息量小于某个阈值其取值将不会用来形成项集。通过这种方来缓解来 自多个不同属性间的取值的组合膨胀问题，以减少计算量，提高算法效率。 另外，我们还注意到这样一个问题，数量是影响商品成本和利润的一个重 要因素，具有很高单价利润的商品项目可能因为销售量不多就不一定是获利最 多的产品。而现实中商场或公司常常希望从包含有商品项目的利润及购买数量 的交易数据库中，得到那些获利最多的产品项目或项目组合以及它们间的关联 关系。本文将项目的权值与数量整合，将权值对应商品的单价利润，并利用了 利润与数量乘积的模式，目的在于从整体获利的角度来挖掘一些有用的关联组 合与知识。 1 4 本文的内容和组织结构 本文的内容是这样组织的： 第一章主要介绍研究背景及意义，对当前国内外量化关联规则挖掘的研 究做了概括，并对已有研究内容做了分类总结，最后给出了本文研究内容和组 织结构。 第二章重点对量化关联规则模型进行了详细的论述，对典型的量化关联 规则挖掘算法进行了分析讨论。 第三章介绍了信息论中信息熵、条件熵、互信息的概念和性质。将互信 息标准化后作为衡量属性间关系的标准。详细介绍了基于属性互信息的量化关 联规则挖掘算法b m i q a r 的过程，并作了相关正确性分析和理论证明。最后通 过实验表明它有效地减少了已有算法在挖掘过程的计算量，大大提高了算法的 6 性能，并且能得到绝大部分置信度较高的规则。 第四章针对已有的研究没有综合考虑项目的重要性和数量的意义，不能 挖掘出满足某些特定要求的有趣关联规则的问题。提出将项目的权值与数量整 合并映射到商品项目获利。为解决算法中的获利频繁项集获取问题，提出了k 获利支持期望的概念，设计了基于获利最大化的量化关联规则挖掘算法 w q a r ，并对算法的复杂度和正确性做了分析。通过实验表明，该算法能得到 满足获利条件的项集，得到的规则质量较高。而且由于项集本身具有的意义， 使挖掘得到的规则更具针对性，可支持决策者做出更加准确实用的决策分析。 第五章对本文的工作做了总结分析，并对可以进一步做的工作做了展望。 1 5 本章小结 本章阐述了本文的研究背景和意义，介绍了布尔关联规则和量化关联规 则的概念，对当前国内外量化关联规则挖掘的研究做了概括，并对已有研究内 容做了分类总结。对本文的研究内容和组织结构做了说明。 7 第2 章量化关联规则挖掘相关算法 本章给出了量化关联规则的形式化描述，分析介绍了基于部分完全性划 分、基于等深划分、基于属性取值数目划分、基于属性取值距离划分、基于区 间距离划分的量化关联规则挖掘算法和模糊关联规则挖掘算法等。 2 1量化关联规则的形式化描述 令i = x l ，x 2 ，x m ) 为量化数据库d 中的属性集，某个属性x i 可以为量化属 性或类别属性。d o m ( x j ) 为属性x j 的定义域，其中1 j m 。项目定义为x 1 x ，u x 】， x 为属性， 1 x ，l l x 】为取值区间，且x i ，lx ，u x d o m ( x ) 。当x 为类别属性时， l x = u 。；为量化属性时，l x u x 。对于一个给定的项集x ，其属性集定义为 a t t r ( x ) = x lx 1 x ，u x 】x ) 。如果l a t t r ( x ) l = k ，称项集x 为k 项集，标记为x i 1 x l ， u x l 】x k 1 x k ，u x k 】。 一条事务t 表示为( v i ，v 2 v m ) ，其中v j d o m ( x j ) ，1 j m 。若对于项集 x ，对v x i 1 i ，u i 】x ，了v i t ，有l i v i y 的蕴涵式，这里x ，y 为频繁项集，并 且项集的属性有a t t r ( x ) n a t t r ( y ) = g ，称x ，y 为规则的前件和后件，且有 a t t r ( r ) = a t t r ( x ) ua t t r ( y ) 。规则r 的支持度记为s u p ( xuy ) ，其置信度定义为 e o n f ( r ) = s u p ( xuy ) s u p ( x ) 。 布尔关联规则是量化关联规则的一个特例，即当所有属性为类别属性的情 况。 量化关联规则的挖掘问题就是对于给定的数据库d ，产生支持度和置信度 分别大于用户给定的最小支持度阈值m i n s u p ( 0 4 0 l o o = 4 0 6 6 7 表2 - 2转变后的数据库 i d年龄 年龄工资工资汽车数汽车数汽车数 2 0 - 2 93 0 3 91 5 0 0 2 9 0 03 0 0 0 5 0 0 0ol 2 1 1 01 0 10o 21oo101o 3101o100 4o1o1oo1 5o1olo01 在对量化属性定义域进行区间划分时存在两个问题： ( 1 ) 最小支持度问题，即如果属性区间划分过小，即区间的划分个数过多 时，会造成每一单个区间的支持度都很低，相应地也会使包含此区间的规则的 支持度很低，从而会造成规则产生的数量过少； ( 2 ) 最小置信度问题，即如果属性区间划分过大，即区间的划分个数过少 时，会使包含此区间的规则的置信度很低，从而造成规则产生的数量过少，同 时区间划分过大，规则所包含的信息量也相应减少。 算法s a 9 l 采用了对支持度较小的相邻区间进行合并的方法改善第一个问 题。就如何避免因划分而导致的信息丢失问题，提出了部分完全性的衡量方法。 下面将详细介绍部分完全性的概念及基于此的量化区间的划分方法。 2 2 1部分完全性 令c 表示数据库d 中的所有频繁项集的集合，指定任意实数k ( k 1 ) ，称p 对于c 是k 完全的，如果( 1 ) p c ；( 2 ) x e p ，且x 7 c x = x 7 p ；( 3 ) 对于v x e c ， jx p ，使得( i ) 石是x 的泛化，并且s u p ( x ) _ k x s u p ( x ) ：( i i ) v y _ c x ，3 】，三石， 】，是y 的泛化，且s u p ( y ) _ b ，必定在r p 中存在一条 规则a = b 它满足： 1 ) 彳和b 分别是a 和b 的泛化； 2 ) s u p ( a = b ) k s u p ( a - - b ) ； 3 ) 1 k x c o n f ( a = b ) _ b ) k x c o n f ( a = b ) 。 证明：对于条件1 ) 和2 ) ，可直接从k 完全的定义得到。对于条件3 ) ，假设 规则a = b 是从r 。中产生的，则在c 中必有aub 。而由k 完全的定义，p 中必有 彳u 召，满足s u p ( aub ) _ b 的置 触肌啾孔矾枷毗虢c o n ta 高2 篙等s u o ( a i= 拶1，：、l l o 一s u p ( a vb 。) s u p ( a ) ，由于s u p ( a ub ) ，$ 口竺殴塑都在1 和k 之间，因此规则二【： 会 s u p ( aub ) s u p ( a )s u p ( aub )s u p ( a ) 的置信度必然介于规贝i j a = b 的鹭信度1 k 和k 倍的之间。 根据这条性质，给定c 的一个频繁子集p ，如果p 对于c 是k 完全的，那么从 p 中生成规则时，必须将规则的最小置信度设置为期望水平的1 k 倍( 引理1 第3 条) 以确保产生一条近似的规则。 2 2 2 决定分区的数目 接下来，给出分区后的属性的一些性质，使用这些性质可以帮助确定在给 定的部分完全性水平下区间的数目。 x 的泛化 - - - - 卜+ 二 基本区闻 x 图2 - 1引理2 图示 引理2考虑量化属性x 及实数k ( k 1 ) 。假设将x 划分为若干区间( 称为基本 区间) ，对于任何区间b ，或者有s u p ( b ) m i n s u p ) s u p ( x ) k 引理3考虑1 1 个量化属性的集合及实数k ( k 1 ) 。假设将每个量化属性都划 分为若干区间，使得对于任何基本区间b 或者有s u p ( b ) m i n s u p ( k - 1 ) ( 2 n ) ， 或者b 仅仅由单一的值组成。令p 表示分区后的属性上的全部频繁项集的集合， 那么p 对于分区前的属性上的全部频繁项集的集合是k 完全的。 证明：类似于引理2 的证明，不同在于对基本区间的支持度要求不同。设x 为任意具有最小支持度的区间集合，x 为任意属于x 的区间，x 为x 的最小泛化 并且x 是基本区间的组合，m 为x 所包含量化属性的个数。那么被x 部分覆盖的 基本区间最多为2 个，被x 部分覆盖的基本区间最多为2 m 个。同样如果某基本 区间被x 部分覆盖，那么它不可能为单值。由于非单值基本区间的支持度小于 m i n s u p ( k 1 ) 2 n ，那么被x 部分覆盖的范围的支持度必然小于 m i n s u p ( k 。1 ) 2 n 。因此当仅有x 被泛化时，泛化后的支持度最多增加 2 m i n s u p ( k 1 ) 2 n ；当所有属性被泛化时，泛化后的支持度最多增加 2 i t i x m i n s u p ( k 1 ) 2 n ，所以 s u p ( x ) s u p ( x ) + 2 m m i n