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

西南交通大学硕士研究生学位论文第1 页 摘要 数据挖掘技术是近年来数据库和人工智能等领域研究的热点课题，它引 起了科学界和产业界的广泛关注。在数据挖掘技术发展繁荣的大背景下，关 联规则技术得到了蓬勃发展，并正朝更为广泛而深入的方向继续发展。 关联规则挖掘作为数据挖掘领域的一个重要研究分支，它的任务是发现 所有满足支持度阈值和置信度阈值的强关联规则。近年来，关联规则挖掘研 究己经成为数据挖掘中的一个热点，并被广泛应用于市场营销、事务分析等 应用领域。关联规则挖掘算法是关联规则挖掘研究的主要内容，迄今为止己 提出了许多高效的关联规则挖掘算法。 本文对关联规则挖掘进行了系统的分析与研究，并在已有研究的基础上 提出了两个改进算法。论文的主要工作如下： ( 1 ) 对关联规则挖掘的基本理论进行了总体研究，包括关联规则挖掘的 基本概念、分类、挖掘过程、改善关联规则挖掘质量的主要策略等，并在此 基础上分析了关联规则的扩充问题，从而指出关联规则挖掘的研究方向。 ( 2 ) 对关联规则经典算法a p d o r i 作了全面的分析，指出了挖掘中的关 键步骤并提出算法的不足，并分析总结了二进制算法和矩阵算法的相关研究， 提出了一种基于频繁项集矩阵的关联规则挖掘算法。该算法不需要生成频繁 候选项集，并且只需要扫描事务数据库一次，采用频繁项集矩阵存储事务数 据并对其约简，占用的存储空间也少得多。理论分析和测试实验证明了新算 法在性能上的优越性。 ( 3 ) 研究并分析了频繁模式增长算法f p g r o w t h ，结合用户访问模式的 特点，提出了一种新的用户访问模式挖掘算法a p m i n i n g 。该算法将w e b 用 户的会话集映射为一棵访问模式树，然后在访问模式树上挖掘频繁访问模式 并生成模式数组，最后在模式数组中找到所有的频繁访问模式。利用挖掘出 来的模式知识，可以更好地对w e b 站点进行设计与维护。 关键词：数据挖掘；关联规则；a p r i o r i 算法；频繁项集矩阵；f p g r o w t h 算法 用户频繁访问模式 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t d a mm i n i n gt e c h n o l o g yh a sb e e nah o tt a s ki nt h ef i e l do fd a t a b a s ea n d a r t i f i e i a l i n t e l l i g e n c ei nr e c e n ty e a r s ，a n da t t r a c t e de x t e n s i v ea t t e n t i o n sf r o m s c i e n c ea n di n d u s t r y n o w a d a y s ，i nt h ep r o s p e r o u sb a c k g r o u n do fd a t am i n i n g t e c h n o l o g y , a s s o c i a t i o nr u l e st e c h n o l o g yo b t a i n st h ev i g o r o u sd e v e l o p m e n 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 ts u b - b r a n c ho ft h ed a t am i n i n g ，w h i c h t a s ki st od i s c o v e ra s s o c i a t i o nr u l e ss a t i s f y i n gb o t ham i n i m u m s u p p o r tt h r e s h o l d a n dm i n i m u mc o n f i d e n c et h r e s h o l d a s s o c i a t i o nr u l em i n i n gh a sb e c o m eah o t r e s e a r c ht o p i ci nr e c e n ty e a r s ，a n dh a sb e e nu s e dw i d e l yi n m a r k e t i n ga n d t r a n s a c t i o na n a l y s i s a s s o c i a t i o nr u l em i n i n ga l g o r i t h m sa r et h ec o r ec o n t e n t si n t h ea r e a s of a r , m a n yf a m o u sa l g o r i t h m so fa s s o c i a t i o nr u l e sh a v eb e e np r o p o s e d t h i st h e s i sh a ss y s t e m i c a l l ya n a l y z e da n dr e s e a r c h e da s s o c i a t i o nr u l em i n i n g ， a n dp u t sf o r w a r dt w oi m p r o v e da l g o r i t h m so nt h eb a s i so fe x i s t i n gr e s e a r c hw o r k t h em a i nt a s k si nt h et h e s i sa r ca sf o l l o w s ： ( 1 ) t h eb a s i ct h e o r i e sf o ra s s o c i a t i o nr u l em i n i n ga r ed i s c u s s e ds y s t e m a t i c a l l y i nt h i st h e s i s ，i n c l u d i n gt h eb a s i cc o n c e p t s ，c l a s s i f i c a t i o n ，m i n i n gp r o c e s s ，t h ev a l u e o fm e a s u r e m e n t , a n do nt h i sb a s i sa na n a l y s i so ft h ee x p a n s i o no ft h ei s s u eo f a s s o c i a t i o nr u l e s ，p o i n t i n go u tt h a tt h ea s s o c i a t i o nr u l em i n i n gr e s e a r c h ( 2 ) a f t e rt h ec l a s s i ca l g o r i t h mo fa s s o c i a t i o nr u l e s ，i e a p r i o r i ，i sa n a l y z e d t h r o u g h l y , t h ek e ym i n i n gs t e p sa n dl a c k so ft h ea l g o r i t h ma r ep o i n t e do u t t h e n , t h ec o r r e l a t i v es t u d i e so ft h e b i n a r ya l g o r i t h ma n dt h em a t r i xa l g o r i t h ma r e a n a l y z e da n ds u m m a r i z e d ，a n dan e wm i n i n ga l g o r i t h mf o ra s s o c i a t t i o nr u l e sb a s e d o nf r e q u e n ti t e m s e t sm a t r i xi sp r o p o s e d t h en e wa l g o r i t h md o e sn o tn e e dt o g e n e r a t ec a n d i d a t ef r e q u e n ti t e ms e t s ，a n ds c a i r l sd a t a b a s eo n l yo n c e ，s ot h es t o r a g e s p a c ei tt a k e si sm u c hl e s sb ys t o r i n ga n dr e d u c i n gt h et r a n s a c t i o nd a t a 、析t ht h e f r e q u e n ts u p p o f tm a t r i x t h en e wa l g o r i t h mi sp r o v e ds u p e r i o ri nt h ep e r f o r m a n c e t h r o u g ht h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lt e s t s ( 3 ) t h r o u g hs t u d y i n ga n da n a l y z i n gt h ef r e q u e n tp a t t e m - g r o w t h ( f p - g r o w t h ) a l g o r i t h m ，a n dc o m b i n i n gt h ec h a r a c t e r i s t i co fu s e ra c c e s sp a t t e r n , a n o t h e rn e w a l g o r i t h m ，n a m e da p m i n i n g ，i sp u tf o r w a r d ，w h i c hi su s e dt om i n eu s e ra c c e s s 西南交通大学硕士研究生学位论文第1 i i 页 p a t t e m t h ea p - m i n i n ga l g o r i t h mm a p st h ew e bu s e r ss e s s i o ns e tt o a na c c e s s p a u e mt r e e ，t h e nn l i n e st h ef r e q u e n ta c c e s sp a t t e r na n dg e n e r a t e s t h ep a t t e r na r r a y o nt h ea c c e s sp a t t e r nt r e e ，a n df i n a l l y , f i n d sa l lf r e q u e n ta c c e s sp a r e r n si nt h e p a _ t t e ma r r a y i nf a c t ，t h em i n e dp a t t e mk n o w l e d g ec a n s e r v et o d e s i g na n d m a i n t a i nw e bs i t e sb e “e r 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 nr u l e s ；a p r i o r ia l g o r i t h m ；f r e q u e n ti t e m s e t sm a t r i x ；f p - g r o w t ha l g o r i t h m ；f r e q u e n tu s e ra c c e s sp a t t e r n s 西南交通大学曲南父逋大罕 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作 所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 在对关联规则核心算法中a p r i o r i 的全面分析和二进制关联规则算法 及矩阵关联规则算法的分析总结基础上，利用这两类算法的优势，发现了改 进频繁项集挖掘算法的切入点，提出了一种基于频繁项集矩阵的关联规则挖 掘算法。该算法只需要扫描事务数据库一次，采用频繁项集矩阵存储事务数 据并对其约简，占用的存储空间也少得多。理论分析和测试实验证明了新算 法在性能上的优越性。 ( 2 ) 研究并分析了频繁模式增长算法f p g r o w t h ，结合用户访问模式的特 点，提出了一种新的用户访问模式挖掘算法a p m i n i n g 。从理论上证明，该算 法能够有效地识别出频繁访问模式，通过对该算法进行了实验分析，证明了 该算法的性能优于f p g r o w t h 算法，在时间性能方面得到了提高。 学位论文作者签名：宅祭遵 冲月馏日 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位 论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密团，使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：瓠树 日期：砷年月馏e t t 万 ，红尸 日嗍 移 6 名 年 签 ? 删 棚 导 期 捌 刚 西南交通大学硕士研究生学位论文第1 页 1 1 研究背景与意义 第1 章绪论 以往的数据库着重于收集、存储和有效管理数据，近年来，随着信息技术的迅 猛发展，数据挖掘引起了信息产业界的极大关注。其主要原因是随着数据库技术的 成熟和数据库管理系统的广泛应用，特别是国际互联网的快速发展，人类积累的数 据量正在以指数速度增长。在这被称之为信息爆炸的时代，如何才能不被信息的汪 洋大海所淹没，从中及时发现有用的知识，提高信息利用率是人们面临的一个重要 的挑战。数据挖掘技术就是适应这一要求迅速发展起来的一种处理数据的新技术， 并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘是面向发现的数据分析技术，它可以从大型数据库中的海量原始数 据中提取人们感兴趣的、隐含的、尚未被发现的有用的信息和知识。它的发展不仅 可以为商务管理、科学研究、查询优化、过程控制等领域提供决策支持，而且为相 关的计算机学科注入新的活力，从而推进计算机科学向纵深方向发展。 经过十几年的研究，数据挖掘领域产生了许多新的概念和方法，目前的研究主 要集中在分类、聚类、关联规则挖掘、序列模式发现、异常和趋势发现等方面。其 中，关联规则( a s s o c i a t i o nr u l e s ) 挖掘在商业等领域的成功应用，使它成为数据挖 掘中最成熟、最重要、最活跃的研究内容。 关联规则挖掘就是为了在数据库中发现关联关系，它是数据挖掘最先研究的问 题之一，也是数据挖掘的一个主要研究方向。实际上，关于数据挖掘方面的文章， 尤其是早期的一些研究论文和领域应用，多数集中在对不同的关联规则的定义和挖 掘算法的设计上。甚至可以说，提到数据挖掘，人们首先想到的是关联规则挖掘f 2 j o 关联规则挖掘问题由a g r a w a l 等【5 】在对市场购物篮问题进行分析时首次提出， 用以发现商品销售中的顾客购买模式，可以用来指导商家科学地安排进货、库存以 及货架设计等。自从1 9 9 3 年以来，数据挖掘领域的研究者在挖掘关联规则上做了大 量工作，使之成为一个具有普遍意义和实用意义的数据挖掘技术。关联规则挖掘可 以发现存在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的和被隐 藏的。所发现的关联规则可以辅助人们进行市场运作、决策支持及商业管理，网站 设计等。 关联规则已经在电子商务、生物医学、金融信贷业等领域得到成功应用，这些 西南交通大学硕士研究生学位论文第2 页 成功的例子为关联规则在其他行业的应用提供了很好的借鉴。由于关联规则挖掘可 以发现以前用传统人工智能和统计方法无法得到的规则或规律，因此具有重要的研 究价值。此外，关联规则挖掘可以处理的数据量十分巨大，这也迎合了人们从当今 日益增长的w e b 数据中获取知识的迫切要求。关联规则挖掘既可以检验行业内长期 形成的知识模式，也能够发现隐藏的新规律。有效地发现、理解、运用关联规则是 完成数据挖掘任务的重要手段，因此对关联规则的研究具有重要的理论价值和现实 意义f 3 1 。 关联规则挖掘近几年得到了很多人的重视，对关联规则挖掘的研究主要是对关 联规则挖掘算法的研究，挖掘算法的效率和健壮性直接影响着关联规则挖掘的应用。 目前有关关联规则的算法很多，大部分都是以a p r i o r i 算法为基础。这些关联规 则挖掘算法的基本思想都是在基于频繁项目集的发现算法基础之上的，即关键问题 就是求满足用户指定的最小支持度的项目集。为了提高挖掘关联规则的执行效率， 其方法不外是减少非相关项目集的产生，或者是降低搜索数据库的次数，但相对地 增加了在其他方面的时问成本【4 】。针对以上描述的关联规则挖掘算法的一些缺点， 希望能提出更好、更有效率的关联规则挖掘算法是本研究的最大动机。 本课题在研究分析a p r i o r i 算法及其已有的相关改进措施的基础上，针对频繁项 目集的发现算法瓶颈问题，提出两个改进的关联规则挖掘算法，较好地改善了经典 算法存在的效率瓶颈问题，提高了关联规则的挖掘效率。 1 2 国内外研究现状 1 2 1 国外研究现状 国外在关联规则挖掘领域研究的内容十分广泛，取得了明显的成果，研究重点 已从发现方法逐步转向系统应用。a g r a w a l 等在1 9 9 3 年【5 】首先提出了挖掘顾客交易 数据库中项集问的关联规则问题，并于1 9 9 4 年提出了挖掘关联规则的经典a p r i o r i 算法【6 】。此后，诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的 工作包括对原有a p r i o r i 算法进行优化，如采用基于散y o t 4 3 1 、事务压缩 4 4 1 、划分1 4 5 1 、 随机采样【4 6 1 、动态项集计数【4 7 】等的优化方法，以提高算法挖掘规则的效率。但这些 算法都不能避免a p r i o r i 系列算法固有的缺陷，即需要多次重复扫描数据库，而且可 能产生大量的候选项集。有的学者为了避免频繁项集产生方法的一些缺陷，提出了 独立于a p r i o r i 算法的挖掘关联规则的新方法，如j i a w e ih a n 等【4 1 】提出的不产生候选 频繁项集的f p g r o w t h 方法。 西南交通大学硕士研究生学位论文第3 页 目前，一般关联规则挖掘算法是从大量的数据中挖掘关联规则，从而找到数据 库中数据项间联系的规律。经典a p r i o r i 算法是通过对数据库进行多次扫描，反复迭 代直至产生所有的频繁项集。基于约束的关联规则1 7 】挖掘是关联规则挖掘发展的另 一个重要方向。还有，由于数据项在概念上可以有多个层次，因此不同概念层次数 据项间的关联规则可以转化为普遍化关联规则，这也是目前研究的一个热点问题。 另外，引入各种评测参数( 比如兴趣度) 【8 ，9 】的关联规则挖掘算法，以及随着o l a p 技 术的成熟和应用，将o l a p 技术和关联规则挖掘相结合，也成为近年来人们研究的 重要的方向【l o 1 1 1 。 这些关联规则挖掘算法在实际数据挖掘系统中得到了很好的应用【1 2 1 。例如，i b m 公司a l m a d e n 研究中心开发的q u e s t 系统，s g i 公司开发的m i n e s e t 系统，以及 d b m i n e rt e c h n o l o g y 公司开发的d b m i n e r 系统，各系统均提供多种数据挖掘方法。 其中，著名的d b m i n e r 是基于数据立方体的联机分析挖掘工具，包含多种有效的频 繁模式挖掘功能和集成的可视化分类方法。 此外，由于互联网的飞速发展，促使对w e b 数据的挖掘也成为一个非常重要的 研究领域，将关联规则挖掘应用于w e b 上方面的研究也取得了较大的进展，w e b 日志 中的关联规则挖掘等技术已经得到了很好的实践与应用。 c h e n 等【1 3 】最早提出基于w e b 事务的w e b 日志挖掘技术，用于在日志预处理阶段 辨识用户访问事务，然后采用与关联规则相似的方法挖掘频繁访问路径，以发现用 户浏览模式。r c o o l e y 等【1 4 】提出了识别用户序列 e p i s o d e s 的算法，并分别应用关联 规则和序列模式挖掘p e p i s o d e s 。j e r o m e m o o r e 等【1 5 】提出了用关联规则来聚类w r e b 文档。 m i u n e s o t a 大学的w e bm i n e r 系统【1 6 1 设计了一种通用的w e b e t 志挖掘的体系结构， 该系统能自动从w e b 日志中发现关联规则和序列模式等。w e bm i n e r 的思路，是通过 对w e b 日志进行处理，将数据组织成传统的数据挖掘方法能够处理的事务数据形式， 然后利用传统的数据挖掘方法( 如传统的关联规则算法) 进行处理。 i b m 公司的w 曲日志挖掘和分析i 具s p e e d t r a c e r l l 7 】，通过在用户会话上应用数 据挖掘，能够发现频繁遍历路径和频繁访问页组f 其中的页面经常被一起访问，但不 一定位于同一条遍历路径上。 1 2 2 国内研究现状 近年来，国内的关联规则挖掘研究也正逐渐掀起高潮，对关联规则挖掘所涉及 的研究领域很多，一般集中于算法的研究、关联规则挖掘的实际应用以及关联规则 西南交通大学硕士研究生学位论文第4 页 挖掘理论方面的研究。 中科院计算所的欧阳为民首先引入国外关联规则挖掘的概念和思想，并在基于 a 研o r i 算法的基础上提出了时态约束的关联规则。近两年，国内的部分学者对关联 规则挖掘进行了大量的研究，但提出的算法也都是基于国外所提出算法的改进算法。 宋爱波等【1 8 】提出了一种新颖的m b p 算法，利用关联规则挖掘发现的频繁项目集可以 加快速度，能找出所有满足阈值约束的频繁浏览路径。王瑜、刘连臣等【1 9 1 通过对 a p r i o r i 方法的分析，运用对事务集和候选项目集有效约简的方法，提出了基于a p r i o r i 算法的、改进的快速w e b 资源关联规则挖掘算f a 研耐方法。 潘雷、苏晶和徐汀荣【2 0 】对传统的关联规则挖掘方法进行了扩充和改进，改进后 的方法能够结合系统设计的属性参数及概念划分要求，提取有价值的关联规则，有 效反映用户的访问行为模式。 刘滨【2 l 】在研究一些a p r i o r i 改进算法的基础上，提出了1a 研o r i 算法，通过缩减 数据库和与连接方法，实现了对a p r i o r i 算法的改进，并应用到所在学校5 0 周年校庆 网站的日志挖掘中。 吴胜兵和周兴斌等【2 2 】研究了基于关联规则的w e b 使用模式挖掘，通过关联规则 对w e b 使用数据进行深层次的分析，从而挖掘出有意义的模式及规则，以利于设计 w e b 站点时，将关联的产品进行捆绑销售等等。 目前国内从事数据关联规则挖掘研究的人员主要在大学，也有部分在研究所或 公司。大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划等。 具体的研究项目有中科院计算机研究所的智能信息处理重点实验室研制开发的 多策略数据挖掘平台m s m i n e r 系统【2 3 1 ，此系统集成了关联规则挖掘算法。复旦大学 开发的a r m i n e r 系统【2 3 1 ，该系统采用的关联规则挖掘算法是基于a p r i o r i 的改进算 法，是专门针对智能化的p o s 系统开发的关联规则挖掘工具。 目前，在关联规则挖掘领域方面己经取得了相当的成功，但在处理极大数据量 时，需要进一步考虑和研究：如何提高算法效率；数据迅速更新的挖掘算法： 一种与用户进行交互的方法，以将用户的领域知识结合在其中；数值型字段在 关联规则中的处理问题；生成结果的可视化等等。 1 3 本论文研究内容及章节安排 1 3 1 本论文研究内容 本文在以上的研究背景下，展开了对关联规则挖掘算法的研究。对关联规则挖 西南交通大学硕士研究生学位论文第5 页 掘的基本理论和经典算法进行全面的归纳与总结，并对前人对其算法的优化和改进 进行分析和研究：针对目前关联规则算法的缺陷，提出两种关联规则改进算法，并 论证算法的有效适用性。主要工作包括以下一些内容： ( 1 ) 将深入研究关联规则经典算法a p r i o r i 和模式增长算法f p g r o w t h ，并对这 两种算法进行分析和总结。 ( 2 ) 针对关联规则经典算法a p r i o r i 重复扫描数据库，产生大量候选频繁项集 的缺陷，将利用二进制关联规则算法和矩阵关联规则算法这两类算法的优势，提出 一种新的基于频繁项集矩阵的关联规则挖掘算法，通过对事务项目编码以及将事务 数据库映射为一个频繁项集矩阵，对该矩阵进行操作以期得到所有的频繁项目集。 ( 3 ) 考虑到用户访问网站的页面序列所构成的图与模式增长算法的频繁模式树 具有一定的相似性，将提出一种新的用户访问模式挖掘算法a p m i n i n g 。由于模式 增长算法需要生成条件子树，占用内存较大，a p m i n i n g 不需要生成条件子树，拟 利用直接前缀基性质和增加条件模式数组，来找到所有的频繁访问模式。 1 3 2 本论文章节安排 全文共分四章，各章节安排如下： 第l 章：绪论，阐明了本文选题的研究背景及意义，并对题目相关领域的国内 外研究现状进行了综述，引出了论文的研究内容和论文的结构安排。 第2 章：关联规则挖掘技术研究。介绍了关联规则的基本概念与性质、分类及 挖掘过程，同时详细讲述了改善关联规则挖掘质量的主要策略以及进一步研究方向。 第3 章：介绍了关联规则挖掘算法，并对经典的挖掘算法a p r i o r i 及其优化算法 进行了研究与分析，针对a p r i o r i 算法的缺点，提出了一种基于频繁项集矩阵的新算 法，通过理论分析和实验证明了新算法在性能上的优越性。 第4 章：研究与分析了关联规则的不产生候选项集的经典算法f p g r o w t h ，并且 对a p r i o r i 算法和f p g r o w t h 算法进行了比较。在对用户访问模式的形式化描述基础 上，提出了一种新的用户访问模式挖掘算法。进而研究了新算法的设计与实现，并 通过其与g s p 算法的比较，指出新算法具有更高的性能。 最后对整篇论文的工作进行了总结与展望，提出下一步的研究方向。 西南交通大学硕士研究生学位论文第6 页 第2 章关联规则挖掘研究 关联规则挖掘是数据挖掘中最活跃的研究方法之一，同时也是数据挖掘研究的 主要模式之一。挖掘关联规则就是发现大量数据中项集之间相关联系的过程。它在 数据挖掘中是一个重要的课题，最近几年己被业界公开研究，成为一个热点。最初 关联规则的研究只是为了帮助发现交易数据库中不同商品之间的联系，找出顾客购 买行为模式，可以用来指导商品货架布局、货存安排以及根据购买模式对用户进行 分类，目前它已经被广泛地应用到各个领域中。本章首先对关联规则的分类，挖掘 过程进行全面的分析、总结。然后对改善关联规则挖掘质量的主要策略及研究方向 进行详细阐述和分析。 2 1 关联规则描述 2 1 1 基本概念及性质 a g r a w a l 等【5 】首先提出了挖掘顾客交易数据库中项集间的关联规则问题，以后诸 多的研究人员对关联规则的挖掘问题进行了深入的研究，对最初的关联规则挖掘算 法进行了改进和扩展。同时，关联规则的挖掘被应用到许多其它领域的数据库，取 得了良好的挖掘效果。 关联规则是一种简单、实用的分析规则，就是发现存在于大量数据集中的关联 性或相关性，从而描述了一个事物中某些属性同时出现的规律和模式。 关联规则的基本模型【2 4 】如下： 设卢 f l ，2 ，乙 是所有项目的集合，j d 为全体事务的集合，事务丁是一个项目 子集合( t o _ i ) 。每个事务具有惟一的事务标识符t i d 。设a 是一个由项目构成的集 合，称其为项集。事务丁包含项集么，当且仅当a n 如果项集4 中包含k 个项目， 则称其为肛项集。 定义2 1 ：设x 是一个，中项的集合，如果项集x _ c 乃则称事务丁支持( s u p p o r t ) 项集彤也称事务丁包含项集妊一个关联规则是如下形式的一种蕴含：x k 其 中x c i ，y c i ，且x n 殍囝。x 称为前项项集，】，称为后项项集。 挖掘关联规则，就是从数据集中挖掘出形如z jy 的蕴含式。但是，如果没有 限制，挖掘出来的关联规则将是大量的，可能也是无用的。因此，就要对关联规则 属性进行考察。支持度和置信度是描述关联规则属性两个重要的参数，它们的定义 西南交通大学硕士研究生学位论文第7 页 如下： 定义2 - 2 ：关联规则。糙l 其中x 和】，都是项目集，规则的支持度s u p p o r t d 就是项目集xul ，的支持度，即为x 和】，同时出现的可能性，即 s u p p o r t jy ) 2 p ( x r ) - - p ( x ud 。 支持度反映了x 和】，中所含的项在事务集中同时出现的频率。例如“同时购买 乒乓球网和乒乓球拍的顾客有4 8 。 定义2 - 3 ；规则的置信度c o n f i d e n c e ( x = = n 定义为d 中包含x 事务的同时也包 含】，的百分比，即c o n f i d e n c e ( x = = 的- 尸( 砟矽= 置信度反映了在包含x 的事务中，出现】，的条件概率。例如“在所有购买乒乓 球拍的顾客中有6 0 的顾客购买了乒乓球网”。 关联规则的支持度和置信度分别反映了所发现规则在整个数据库中的统计重要 性和可信程度。一般来说，只有支持度和置信度均较高的关联规则才是用户感兴趣 的、有用的关联规则。 定义2 - 4 ：项集在统计意义上的最低支持度定义为最小支持度或支持阈值，用 m i ns u p 表示；规则应该满足的最低置信度定义为最小置信度或置信阈值，用 m i nc o n f 表示。前者描述了关联规则的最低重要程度，后者规定了关联规则必须满 足的最低可靠性。 定义2 - 5 ：项集x 支持度s u p p o r t ( x ) 不小于用户给定的最小支持度m i ns u p ，即 s u p p o r t ( x ) m i ns u p ，则称项集x 为频繁项集。如果x 是肛项集，则称项集x 为频 繁肛项集。 性质2 - 1 ：频繁项目集的所有非空子集都是频繁项集。 证明：设胙 ，厶，厶 为一项目集，且x c _ l 降9 ，y _ c x 。设事务数据库丁 中支持彳的记录数( 或元组数) 为s l ，支持】，的元组数为观。由项目集支持度的定 义，可知支持x 的元组一定支持n 有s l s 2 ，s u p p o r t ( x ) - s u p p o r t ( y ) 。又因项目集 x 是频繁项目集，即s u p p o r t ( x ) m i n _ s u p 。因此，s u p p o n ( y ) s u p p o r t ( x ) - m i n _ s u p ， 故】，也是频繁项目集。证毕。 性质2 - 2 ：非频繁项目集的所有超集都是非频繁项目集。 证明：设胆 ，恳，厶) 为一非频繁项目集，且x c _ lz o ，x c _ z o 设事务 数据库丁中支持x 的记录数为s l ，支持z 的元组数为s 3 。由项目集支持数的定义， 可知支持z 的元组一定支持兄有s 3 - s 1 ，即s u p p o r t ( z ) s u p p o r t ( x ) 。按假设，项目 集x 是非频繁项目集， 即s u p p o g ( x ) m i ns u p 。 因此， s u p p o r t ( z ) 西南交通大学硕士研究生学位论文第8 页 _ m i n c o n f , 称关联 规则( x jy ) 为强关联规则，否则称为弱关联规则。 2 。1 2 关联规则的分类 前一小节定义的关联规则源于超级市场的购物篮问题，是指发现数据库中各项 间有价值的关联关系，然而它只是关联规则挖掘的一种最简单形式。随着关联规则 挖掘研究的发展，出现了很多全新形式的关联规则。关联规则挖掘研究根据处理的 数据集的性质和挖掘结果的不同有不同的分类方式。 1 根据数据值类型的分类 根据规则里所处理的值的类型，关联规则可以分为布尔型关联规则和数值型关 联规则f 2 卯。 布尔型关联规则是只考虑关联项在数据库的事务中出现或不出现两种情况，处 理的值都是离散的、种类化的，它显示了这些变量之间的关系。而数值型关联规则 是描述量化项目( 或属性) 之间的关系，一般采用对项目( 或属性) 量化值的区间化处 理，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处 理，当然数值型关联规则中也可以包含种类变量。因此，数值关联规则处理的变量 的取值是连续的、数值化的。例如，性别= “女”职业= “秘书，是布尔型关联 规则；性别= “女ja v g( 平均收入) ，涉及的平均收入是数值类型，i n c = 2 3 0 0 所以是一个数值型关联规则。 2 根据数据抽象层次的分类 根据规则中数据所涉及的抽象层次，关联规则可以分为单层关联规则和多层关 联规贝l j 2 6 ，2 7 。 单层关联规贝1 j ( s i n g l e l e v e la s s o c i a t i o nr u l e ) 是指在给定的规则集中，规则不涉 及不同抽象层的项或属性，没有考虑到现实的数据具有多个不同的层次；而在多层 的关联规则中，对数据的多层性已经进行了充分的考虑。例如，i b m 台式机js o n y 打印机，是一个细节数据上的单层关联规则；台式机js o n y 打印机，是一个较高 层次和细节层次之间的多层关联规则。 3 根据数据维数的分类 根据规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多维关联 规贝, u t 2 s j 。 单维关联规则中的项或属性每个只涉及一个维，如用户购买的物品，仅考虑物 西南交通大学硕士研究生学位论文第9 页 品维。而在多维的关联规则中，要处理的数据将会涉及多个维。也就是说，单维关 联规则是处理单个属性中的一些关系，而多维关联规则是处理各个属性之间的某些 关系。例如，“啤酒j 尿布”这条规则只涉及到用户的购买的物品；“年龄2 0 3 0 、 月收入3 0 0 0 j 买电脑”这条规则同时涉及到年龄、收入和购买物品这三个维，故 而是多维关联规则。 4 根据挖掘扩充的分类 根据对关联挖掘的不同扩充，可以扩充为相关分析、最大频繁模式与频繁闭项 集挖掘【2 9 1 。相关分析可以识别项是否相关。最大模式是一个频繁模式尸，使得尸的 任何真超模式( 即包含尸的模式) 都不是频繁的。频繁闭项集是一个频繁的闭的项集， 即如果项目集c 是闭的，那么就不存在c 的任何真超集c ，使得包含c 的子模式 的每个事务也包含c 。使用最大频繁模式与频繁闭项集可以显著地减少挖掘所产生 的频繁模式集的数量。 了解了关联规则的分类之后，就可以在具体的分析过程中考虑某些具体方法适 用于哪一类规则的挖掘，某类规则又可以用哪些方法处理。 2 1 3 关联规则挖掘过程及注意问题 关联规则挖掘是数据挖掘中最常用方法之一，为了发现有意义的关联规则，需 要给定两个阈值：最小支持度和最小置信度，关联规则的任务就是在数据库d 中找 出所有支持度和置信度均分别超过m i n和 的关联规则，即要求满足s u p m i nc o n f s u p p o r t ( x = ：, 玢m i ns u p ，且c o n f i d e n c e ( x ：= , n m i nc o n f 的关联规则精y o 挖掘关联规则可以分解为以下两个子问题【5 6 ，3 0 ，3 1 】： ( 1 ) 找出事务数据库中所有大于等于用户指定的最小支持度的数据项集； ( 2 ) 利用频繁项集生成所需要的关联规则，根据用户设定的最小置信度进行取 舍，最后得到强关联规则。 关联规则挖掘所面临的主要问题是数据库规模巨大，如何提高效率是算法的关 键。第一个子问题的任务是快速有效地找出数据库中的频繁项集，目前有很多产生 频繁项目集的算法，这些算法产生频繁舡项集时，扫描数据库的每个事务用以统计 这些候选肛项集的支持度，并按照事务数确定的最小支持度在第k 次迭代时找出所 有频繁肛项集。然而，由于数据库的规模通常是非常大的，所以在每次迭代时产生 候选项目集以统计其支持度是非常耗时的。因而，相对于较为容易和直观的第二个 子问题，第一个子问题是关联规则的挖掘过程中的核心问题，这也是近年来关联规 则挖掘研究的重点。 西南交通大学硕士研究生学位论文第1 0 页 一般的发现频繁模式集的算法，都是先产生候选频繁模式集( c a n d i d a t ei t c m s e t ) 。 候选频繁模式集是所有频繁模式集的超集，其产生算法需要具有可实现性，并且保 证所有的潜在的频繁模式集都包含在候选频繁模式集中。在上述条件下，如何能生 成尽可能小的候选频繁模式集是所有方法都遵循的原则。不同的算法其候选频繁模 式集的生成方法也不尽相同，但其产生候选频繁模式集的规模应该保证使它进一步 的验证过程可以被计算【9 】9 。 在关联规则的挖掘中要注意以下几点： ( 1 ) 充分理解数据基础上明确目标。 ( 2 ) 做好数据准备工作做好。当然能否做好数据准备又取决于前两点，数据准 备将直接影响到问题的复杂度及目标的实现。 ( 3 ) 选择适当的最小支持度和最小置信度。这依赖于用户对目标的估计，如果 取值过小，那将会发现大量的无用的规则，不但影响执行效率浪费系统资源，而且 可能把目标埋没；如果取值过大，则又有可能找不到规则，与知识失之交臂。 ( 4 ) 深刻理解关联规则。数据挖掘工具能够发现满足条件的关联规则，但它不 能判断关联规则的实际意义。对关联规则的理解需要熟悉业务背景，丰富的业务经 验对数据有足够的理解。在发现的关联规则中，可能有两个主观上认为没有多大关 系的物品，它们的关联规则支持度和置信度却很高，需要根据业务知识和经验，从 各个角度判断这是个偶然现象还是有其内在的合理性；反之，可能有主观上认为关 系密切的物品，结果却发现它们之间相关性不强。只有很好的理解关联规则，才能 去其糟粕，取其精华，充分发挥关联规则的价值 3 3 】。 2 2 改善关联规则挖掘质量的主要策略 使用关联规则挖掘算法得到了一些结果后，需要对挖掘结果进行衡量，确定哪 些规则对用户是有用的、有价值的。可以通过两个角度来进行衡量：客观评价方法 和主观评价方法。 1 客观评价方法 有趣性的客观评价【3 2 】是指关联规则的有趣性，是由规则的具体结构和在数据挖 掘过程中所依赖的数据决定的。这种方法主要是在这些规则上应用统计学方法，用 定量的数值来判定规则的有趣性，从而避免了人为的主观意见。因此，从这个意义 上讲，规则有趣性的客观评价是可靠的、有说服力的。 支持度和可信度度量是评价关联规则的两个常用客观性指标。支持度度量反映 西南交通大学硕士研究生学位论文第1 1 页 了规则的实用性，而可信度度量反映了规则的有效性。很多的算法都使用“支持度 可信度”的框架。这样的结构有时会产生一些错误的结果。甚至，如果我们把支持 度和可信度设得足够低，那么我们还可能会得到矛盾的规则。另一方面，如果我们 把那些参数设得足够高，我们也可能得到不精确的规则。总之，没有一对支持度和 可信度的组合可以产生完全正确的关联。 于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成“错觉”的关联规 则。一般，一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度 之比，即兴趣度i n t e r e s t = p ( c o n d i t i o na n dr e s u l 0 p ( c o n d i t i o n ) * p ( r e s u l t ) 。当兴趣度大于l 的时候，这条规则就是比较好的；当兴趣度小于l 的时候，这条规则就是没有很大意 义的。兴趣度越大，规则的实际意义就越好【3 4 l 。 2 主观评价方法 关联规则有趣性的客观评价只是基于数据本身的结构来展开的。关联规则的产 生完全基于事实数据，并没有考虑规则之间的联系和用户( 专家) 对规则的认同程度。 但是，一个规则是否有趣，最终要取决于用户的感觉，只有用户可以决定规则的有 效性和可行性。我们应该将用户的需求和挖掘系统结合起来，才能挖掘出更加有效 的关联规则。 因此，判断规则的有趣性必须考虑到主观层面上的意义。也就是说，在评价规 则的有趣性时，要体现用户参与和领域知识的融合等主观因素。从上面的分析可知， 高支持度和高可信度的规则对用户来讲并不一定有意义。从用户的主观角度看，规 则的非预期性和可行性可能是用户更感兴趣的【3 5 1 。 我们可以采用一种基于约束( c o n s t r a i n t - b a s e d ) 的挖掘方法，具体约束的内容有以 下几个方面： ( 1 ) 数据约束