（计算机应用技术专业论文）基于属性覆盖的关联规则挖掘算法研究.pdf

基于属性覆盖的关联规则挖掘算法研究 摘要 数据挖掘( d m ，d a t am i n i n g ) 是一个涉及多学科领域的新兴学科，其中关联规则挖 掘是一个重要的研究内容。由于关联规则的挖掘对象大多包含有海量原始数据和大量 项目的事务数据库，因此，如何设计一个高效的算法，以提高数据挖掘的效率，成为 一个重要课题。 本文所做的研究工作主要如下： 对传统关联规则挖掘的概念进行了扩展，引入了交易之间基于属性的覆盖关系、 频繁项目集和项目集蜕化等概念。 在对经典关联规则挖掘算法研究的基础上，提出一种基于属性覆盖的的关联规则 挖掘算法a r b a c 。该算法只对原数据库进行1 次扫描，得到压缩数据库链表，其后 的数据挖掘过程都是在其压缩链表中进行，从而提高了算法的时间性能。由于该算法 并不产生候选项目集，因而避免了候选项目集组合爆炸的情况，提高了算法的空间性 能。 最后，为了使得a r b a c 算法应用到大型交易数据库的关联规则挖掘，本文在a r b a c 算法的基础上提出了基于属性划分的拼接树模型。 关键词：k d d 覆盖蜕化基拼接树 t h er e s e a r c ho nm i n i n g a l g o r i t h mo f a s s o c i a t i o nr u l e sb a s e d0 9 a t t r i b u t e sc o v e r i n g a bs t r a c t d a t am i n i n gi san e ws u b j e c ti n v o l v i n gm u l t i d i s c i p l i n a r yf i e l d s ，i nw h i c hd a t am i n i n g o ft h ea s s o c i a t i o nr u l e si sav e r yi m p o r t a n tr e s e a r c hb r a n c h t h eo b j e c t so fs u c har e s e a r c h i sa l w a y sad a t a b a s ec o n t a i n i n gm a s s i v er a wd a t aw i t ht h el a r g en u m b e ro fi t e m s i ti sa l l i m p o r t a n tr e s e a r c hp r o b l e mt od e s i g na ne f f i c i e n ta l g o r i t h mt oi m p r o v et h ee f f i c i e n c yo f d a t am i l l i n go ft h ea s s o c i a t i o nr u l e s t h em a j o rr e s e a r c hw o r ko ft h i sd i s s e r t a t i o ni sa sf o l l o w s ： t h ec o n c e p to ft r a d i t i o n a ld a t am i n i n go ft h ea s s o c i a t i o nr u l e sh a sb e e ne x p a n d e d a n d t h e c o n c e p t ss u c h a sf r e q u e n ti t e ms e t ，a t t r i b u t e sc o v e r i n gb a s e do nt h ed i f f e r e n t t r a n s a c t i o n sa n ds oo nh a sb e e ni n t r o d u c e d a na l g o r i t h mo fa s s o c i a t i o nr u l e sb a s e do na t t r i b u t e sc o v e r i n gh a sb e e np u tf o r w a r do n t h eb a s i so ft h er e s e a r c ho ft h ec l a s s i c a la l g o r i t h m so ft h ea s s o c i a t i o nr u l e s t h i sa l g o r i t h m s c a n st h eo r i g i n a ld a t a b a s eo n l yo n c et og e tt h ec o m p r e s s e dl i n k - l i s t - d a t a b a s e ，a n dt h e s u b s e q u e n tp r o c e s so ft h ed a t am i n i n gi sc a r r i e do u ti ni t ，s oi th a st h eh i g h e re f f i c i e n c y a n dt h ea l g o r i t h md o e sn o tp r o d u c ec a n d i d a t ei t e ms e t s ，t h u sa v o i d i n gt h ec o m b i n a t o r i a l e x p l o s i o no ft h ec a n d i d a t ei t e ms e t s f i n a l l yt h i sd i s s e r t a t i o np u t sf o r w a r dt h es t i t c h i n gt r e em o d e lb a s e do nt h ea r b a c a l g o r i t h mi no r d e rt om a k et h ea l g o r i t h ma p p l i c a b l et o t h ed a t am i n i n gi nt h el a r g e t r a n s a c t i o n sd a t a b a s e k e yw o r d s ：k d d ，c o v e r i n g ，d e g e n e r a t i o n ，c a r d i n a l ，s t i t c h i n g t r e e 插图清单 关联规则挖掘的基本模型8 结点蜕化示例1 8 修正的结点蜕化示例1 9 数据库链表结点结构示意图“2 5 子集链表结点结构示意图2 5 频繁项目集链表结点结构示意图“2 6 预处理后的数据库链表k 和频繁项目集链表p 2 7 数据库链表k 基为4 的结点蜕化结果”2 7 数据库链表k 中基为3 的结点搜索过程”2 8 数据库链表k 中基为3 的结点合并结果”2 9 频繁项目集合并结果2 9 数据库链表第二次蜕化3 0 数据库链表第二次合并3 0 所有频繁项目集生成图示”3 0 a r b a c 算法和经典算法执行时间的比较“3 1 拼接树模型示意图3 5 拼接树结点结构示意图一3 6 拼接树的初始状态图”3 6 对第1 个交易计数后的拼接树”3 7 对第2 个交易计数后的拼接树3 7 对第3 个交易计数后的拼接树”3 7 对第7 个交易计数后的拼接树3 8 对第8 、9 、1 0 个交易计数后的拼接树3 8 2 0 1 2 3 4 1 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 2 3 4 5 6 7 8 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 图图图图图图图图图图图图图图图图图图图图图图图 表格清单 表3 1交易数据库d 15 表3 2 频繁项目集合并示例1 5 表3 3 经过二进制化改造的交易数据库”2 3 表3 4 数据库链表结点访问次数- 3 2 表4 11 6 属性交易数据库d 3 4 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得金目垦王些厶堂 或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学馘文储签字3 伽f 签字醐汩歹年川6 日 学位论文版权使用授权书 本学位论文作者完全了解盒理王些态堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 起王些太堂可以将学位硷文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：山性凋p 签字日期：a 卅矿年月儿日 学位论文作者毕业后去向： 翮虢蝣磁， 签字日期诱年l 月f 白 电话： 邮编： 致谢 值此论文完成之际，我要特别感谢我的指导老师胡学钢教授! 胡老师 知识渊博，为人正直无私，平易近人。不仅在学术上给了我莫大的帮助和 指导，更教导我树立了正确严谨的学术态度，也是我在学习、研究中的良 师益友。 其次，我要感谢刘桂庆老师。在发表论文期间，她为我搜集和介绍了 该研究领域的重要资料。当我在撰写论文期间遇到困难时，她都为我指点 迷津。 同时，我也要感谢安徽财经大学信息工程学院的各位同仁，他们在我 论文期间给予了很大的关怀，为我提供了良好的实验环境。 同样要感谢我的好朋友孙春美、李凯、周巧婷、赵晓静等。在他们的 支持和帮助下，才使得我的论文顺利完成! 在这里，我还要特别感谢我的母亲! 是她默默地支持和鼓励着我，用 她的关爱帮助我克服在撰写论文时遇到的挫折和烦恼! 最后，我还要衷心地感谢我的先生巩飞对我在撰写论文期间的无微照 顾和支持l 更感谢他在我读研期间对家庭的无私奉献! 作者：王恒娜 2 0 0 7 年11 月 1 1课题的研究背景 第一章引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。激增的数据背后隐藏着许多重要的信息，这些海量信息在给人 们带来方便的同时也带来了一大堆的问题：第一是信息过量，难以消化；第二 是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致，难 以统一处理。目前的数据库系统虽然可以高效地实现数据的录入、查询、统计 等功能，但无法发现数据中存在的关系和规则，缺乏挖掘数据背后隐藏的知识 的手段，无法根据现有的数据预测未来的发展趋势。导致了“数据爆炸但知识贫 乏”的现象。面对海量的存储数据，如何从中发现有价值的信息或知识，成为一 项非常艰巨的任务。面对这一挑战新的数据处理技术数据挖掘( d a t am i n i n g ) 技术便应运而生了。数据挖掘就是为迎合这种要求而产生并迅速发展起来的。 数据挖掘是指从大型数据库或数据仓库中提取出隐含的、先前未知的、对决策 具有潜在价值的知识和规则。 从数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国 际联合人工智能学术会议上。到2 0 0 3 年为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 3 次，规模由原来的专题讨论会发展到国际学术大会， 研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成， 以及多种学科之间的相互渗透。1 9 9 8 年在美国纽约举行的第四届知识发现与数 据挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他们 的数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。1 9 9 9 年，亚太 地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的 k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并 行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和 知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。它是目前国际上数 据库和信息决策领域的最前沿的研究方向之一，引起了学术界和工业界的广泛 关注。 1 2 数据挖掘概述 数据挖掘的概念其实是一个逐渐演变的过程，电子数据处理的初期，人们 就试图通过某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。 机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输入计算 机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通用性，使 用它们可以解决某一类的问题。随后，随着神经网络技术的形成和发展，人们 的注意力转向知识工程，知识工程不同于机器学习那样给计算机输入范例，让 它生成出规则，而是直接给计算机输入已被代码化的规则，而计算机就是通过 使用这些规则来解决某些问题。专家系统就是这种方法所得到的成果，但它有 投资大、效果不甚理想等不足。8 0 年代人们又在新的神经网络理论的指导下， 重新回到机器学习的方法上，并将其成果应用于处理大型商业数据库。随之在 8 0 年代末出现了一个新的术语：即数据库中的知识发现，简称k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 。它泛指所有从源数据中发掘模式或联系的方法，人们接 受了这个术语，并用k d d 来描述整个数据发掘的过程，包括最开始的制定业 务目标到最终的结果分析，而用数据挖掘( d a t am i n i n g ) 来描述使用挖掘算法 进行数据挖掘的子过程。但最近人们也常把这两种说法等同起来，数据挖掘侧 重数据库角度，k d d 侧重人工智能角度。数据仓库技术的发展也与数据挖掘有 着密切的关系。数据仓库的发展是促进数据挖掘越来越热的原因之一。但是， 数据仓库并不是数据挖掘的先决条件，因为有很多数据挖掘可直接从操作数据 源中挖掘信息。 数据挖掘功能是数据挖掘系统的核心。一些数据挖掘系统只提供一种数据 挖掘功能，例如分类。而有些数据挖掘系统能够支持多种数据挖掘功能，例如： 描述，发现驱动的o l a p 分析，关联，分类，预测，聚类，孤立点分析，相似 性搜索，序列模式分析，可视化数据挖掘等。对于一个给定的数据挖掘功能如 分类，一些系统可能只支持一种方法，有些可能支持多种方法( 例如决策树， 贝叶斯网，神经网络，遗传算法，基于案例的推理等) 。支持多种数据挖掘功能 同时每一种功能又支持多种方法的数据挖掘系统，能提供给用户很大的灵活性 和很强的分析能力。许多问题可能要求用户尝试不同的数据挖掘功能或者把几 种功能集成起来使用，不同的数据集使用不同的方法，非常有效。当然，由于 系统更加灵活，用户可能需要进行培训或者得有经验。因此这些系统应该给初 级用户提供方便，使其能访问最通用的功能和方法，或将最通用的功能和方法 作为缺省设置。总而言之，数据挖掘的最终目标是从数据库中发现隐含的、有 意义的知识。其主要功能概括起来有以下几个方面 3 - 5 ： ( 1 ) 分类( c l a s s i f i c a t i o n ) 和预测( p r e d i c t i o n ) 分类是找出描述并区分数据类或概念的模型( 或函数) ，以便能够使用摸 型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其类标记已知 的数据对象) 的分析。分类可以用来预测数据对象的类标记。然而，在某些应 用中，人们可能希望预测某些空缺的或不知道的数据值，而不是类标记。当被 预测的值是数值数据时，通常称之为预测。如果预测的变量是连续的，这类问 题被称为回归( r e g r e s s i o n ) 。一个典型的例子是市场预测问题。 2 ( 2 )聚类( c l u s t e r i n g ) 数据库中的记录可被划分为一系列有意义的子集，即聚类。与预测模型不 同，聚类中没有明显的目标变量作为数据的属性存在。聚类算法通过监测数据 判断“隐藏属性”。通常对数据进行聚类或分组要根据“最大化类内相似度，最小 化类间相似度”的原则进行。 ( 3 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 数据关联是数据库中存在的一类重要的可被发现的知识。关联分析的目的 是发现关联规则，这些规则展示了某些属性值频繁的在给定数据集中一起出现 的条件。若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规 则的计算依赖于识别在相关数据中频繁出现的数据集。频繁出现的数据由在某 事务中同时出现的数据组成。关联分析广泛应用于购物篮或事务数据分析中。 从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定， 如分类设计、交叉购物等。 ( 4 ) 时间序列分析( t i m es e q u e n c ea n a l y s i s ) 这种分析除包括时间相关数据的特征化、区分、关联、分类或聚类，还包 括时间序列数据分析、序列或周期模式匹配和基于类似型的数据分析。在时间 序列数据库内某个字段的值总是随着时间而不断变化的，例如股票价格每天的 涨跌，科学实验，浏览网页的次序等。时间序列分析通过对时间序列的搜索， 发现重复发生概率较高的模式。 ( 5 ) 偏差分析( d e v i a t i o na n a l y s i s1 用来发现与正常情况不同的异常和变化，并进一步分析这种变化是否是有 意的诈骗行为，还是正常的变化。如果是异常行为，则提示预防措施；如果是 正常的变化，那么就需要更新数据库记录。 ( 6 ) 孤立点分析( o u t l i e ra n a l y s i s ) 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。 这些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘将孤立点视为噪音或异常而 简单的丢弃。然而，在一些应用中，罕见的事件可能比正常出现的更有价值。 例如，在医疗分析中，某些对多种治疗方式的不同寻常的反应数据可能成为孤 立点，但是这些数据对于治疗却非常重要。对孤立点数据进行分析称为孤立点 分析。孤立点的检测可以使用统计实验的方法：它假定一个数据分布或概念模 型，并使用距离度量，到其他聚类的距离很大的对象被视为孤立点。基于偏差 的方法是通过考察一群对象主要特征上的差别识别孤立点，而不是使用统计或 距离度量。 ( 7 ) 概念描述( c o n c e p td e s c r i p t i o n ) 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述：前者是目标类数据的一般特征或特征 3 的汇总。通常，用户指定类的数据可以通过数据库查询来收集。后者是将目标 类对象的一般特性与多个对比类对象的一般特性比较。目标类和对比类由用户 指定，而对应的数据也通过数据库查询检索。 数据挖掘的是一个复杂的过程，通常包括多个步骤，可粗略地分为：问题 定义( t a s kd e f i n i t i o n ) 、数据准备和预处理( d a t ap r e p a r a t i o na n dp r e p r o c e s s i n g ) 、 数据挖掘( d a t am i n i n g ) 算法执行以及结果的解释和评估( i n t e r p r e t a t i o na n d e v a l u a t i o n ) 等阶段4 1 。 ( 1 ) 问题定义 任何一种数据挖掘算法不管是统计分析方法、神经元网络、各种树分析方 法还是遗传算法没有哪一种算法是万能的。因此在该过程中，数据挖掘人员必 须与领域专家及最终用户紧密协作详细了解所研究领域的背景知识和信息，以 明确实际工作对数据挖掘的要求，另一方面通过对各种学习算法的对比进而确 定可用的学习算法。后续的学习算法选择和数据集准备都是在此基础上进行的。 ( 2 ) 数据准备和预处理 在现实世界的数据库或数据仓库中的数据往往是不完整的( 有些感兴趣的 属性缺少属性值，或仅包含聚集数据) 、含噪声的( 包含错误或存在偏离期望值 的孤立点) 而且是不一致的( 例如，用与商品分类的部门编码存在差异) 。而数 据预处理可以改进数据的质量从而有助于提高其后的挖掘过程的精度和性能。 这个过程可细分为数据选取( 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 ) - - - - 个子步骤。数据选取的主要目的是为了确定 操作对象；数据预处理包括消除噪声、消除重复记录、推导计算缺值数据、数 据类型转换等；数据变换是为了降低维数( d i m e n s i o nr e d u c t i o n ) ，即减少数据 挖掘时需要考虑的特征或变量个数。 ( 3 ) 数据挖掘算法执行 该阶段首先：由于不同的用户可能对不同类型的知识感兴趣，数据挖掘系 统应当覆盖范围很广的数据分析和知识发现任务，包括数据特征化、区分、关 联、分类、聚类、趋势和偏差分析以及类似性分析。这些任务可能以不同的方 式使用相同的数据库，并需要开发大量数据挖掘技术。其次：在数据挖掘时很 难准确知道能够在数据库中发现什么。所以该阶段首先根据对问题的定义明确 挖掘的任务或目的，之后要决定使用什么样的算法。选择实现算法要考虑两个 因素：首先，根据不同的数据选择采用与之相关的算法来挖掘；其次，根据用 户要求或实际运行系统的要求来选择。 ( 4 ) 结果解释和评估 数据挖掘阶段发现的知识应当用高级语言、可视化表示或其他表示形式表 示，使得知识易于理解，能够直接被人们使用。如果数据挖掘系统是交互的， 这一点尤为重要。这要求系统采用有表达能力的知识表示技术，如树、表、规 4 则、图、图表、交叉表、矩阵或曲线等，此外对于给定的用户，许多模式不是 有趣的，它们表示公共知识或缺乏新颖性，因此需要将这些冗余或无关的模式 剔除。 在上述过程中，一个数据挖掘系统的好坏起决定性作用的是要选择一个性 能好、伸缩性好、结果容易理解和使用并且符合用户需求的算法。当然，数据 挖掘的其他几个步骤也是非常重要的，每一步都是下一步的基础；都影响到最 后所发现的知识的精确性和可用性，所以更多的时候数据挖掘是一个反复循环 的过程，如果用户对结果不满意，可以在任何时候退回到前一阶段，如重新选 取数据、采用新的数据变换方法、设定新的参数值，甚至换一种挖掘算法。 1 3 本文的研究内容 关联规则挖掘是数据挖掘的主要研究方向之一，关联规则挖掘的对象通常 是由数以百万计的记录所构成的大型数据库或数据仓库，因此挖掘算法的效率 是至关重要的，许多学者对此进行了大量的研究。然而目前代表性的关联规则 挖掘算法中，或由于产生大量候选项目集降低了时间性能，或由于构造搜索空 间降低了空间性能。因此本文围绕着降低关联规则挖掘算法的时间、空间复杂 度展开了研究。提出了交易数据库中项目间的属性覆盖和项目集蜕化的概念， 并由此引入了一种新的基于属性覆盖的不产生候选项目集的关联规则挖掘算法 一a r b a c 算法。因此本文的结构如下： ( 1 ) 从关联规则挖掘的基本概念出发，给出关联规则的一般形式，介绍了 与关联规则挖掘算法相关的领域和研究方向，以及现有的具有代表性的挖掘算 法。 ( 2 ) 重点介绍了经典的有候选项目集的a p r i o r i 算法和不产生候选项目集 的代表算法f p g r o w t h ，对比这两种算法在时间复杂度和空间复杂度上的不同。 ( 3 ) 提出了基于属性覆盖的关联规则挖掘算法，并通过实验分析其性能。 ( 4 ) 为了使得a r b a e 算法可以应用到现实数据库的挖掘，本文又提出了 基于属性分组的拼接树模型。 1 4本章小结 本章从数据挖掘的演变过程出发，介绍了数据挖掘的产生背景，对比说明 了数据挖掘与早期的数据搜集和分析之间的区别。进而介绍了数据挖掘的概念。 本章的第二部分首先介绍了数据挖掘功能的分类，并通过对各种类的不同点明 了数据挖掘的几个重要研究方向；最后又详细介绍了数据挖掘的四个步骤，并 分析了这四个步骤对整个数据挖掘结果的影响。在本章的第三部分介绍了本文 的主要研究工作。 5 第二章关联规则挖掘技术概述 本章对关联规则挖掘的概念、步骤、及其研究方向进行了阐述，重点对比 和分析了a p r i o r i 和f p g r o w t h 算法，提出了关联规则挖掘的要求和面临的挑战。 2 1 关联规则概述 关联规则问题是美国i b ma l m a d e nr e s e a r c hc e n t e r 的r a k e s ha g r a w a l 等人 于1 9 9 3 年首先提出知识发现研究中的一个重要课题。 关联规则最初是应用于交易数据库，用来发现超市中用户购买的商品间的 隐含关系，以便为经营者提供决策依据。以后的研究广泛应用于各种事务性数 据库，从事物数据库中得到的关联规则称为布尔关联规则。 与关联规则最密切最重要的三个研究领域是：统计学( s t a t i s t i c s ) 、机器学习 ( m a c h i n el e a r n i n g ，或称人工智能a r t i f i c i a li n t e l l i g e n t ) 及数据库( d a t a b a s e ) 。 关联规则与统计学和机器学习的共同点是：都致力于从数据中发现模式和 知识。统计学的主要任务是分析数据或用相对复杂的模型匹配数据。如：计算 方差、均值、偏差等，或者寻找与大量数据匹配的统计模型，描述的都是关于 数据自身的固有属性。关联规则挖掘则是自动地对大量的、相对简单的特性进 行估价，其描述的是数据中隐藏的特性，且规则的数量大、形式简单。可以说， 关联规则挖掘是统计分析方法学的延伸和扩展。机器学习的主要任务是发现输 入和输出属性之间的规律和模型。关联规则挖掘通常并不硬性规定哪些项目一 定为输出，哪些项目为输入( 在没有项目约束的情况下) ，其作用是发现所有属 性间可能存在的规律。此外，数据挖掘中所处理的数据量远远大于机器学习中 所处理的数据量。尽管如此，统计学和机器学习中的许多概念和成果仍然在数 据挖掘研究中起着重要作用，例如关联规则挖掘中的支持度、可信度等概念就 体现了统计的概念，人工智能领域中的遗传算法、分类、聚类及模糊数学的概 念也在数据挖掘中得到了广泛的应用。关联规则挖掘与数据库研究领域的关系 最为紧密，因为关联规则挖掘的对象就是现有的数据库或数据仓库，且数据库 技术( 如在线分析处理、索引技术等) 对于关联规则挖掘的研究起到重要作用。 不过二者之间仍然有很大的不同：数据库的功能通常是数据库中信息的逻辑操 作结果( 如两个表的联接操作) ，并且可以证明得出的是关于数据的正确的结论 ( 只要数据库中提供的数据是正确的) 。而关联规则挖掘所得出的结果仅能证明 数据库中的数据支持这些规则，但是这些规则在现实世界中是否适用则不能肯 定，因此数据挖掘的主要任务是选择那些被数据库支持的、看上去最为合理的 和有趣的规则或规律。目前数据挖掘查询语言( d a t am i n i n gq u e r yl a n g u a g e ) 6 及在线分析挖掘技术( o n 1 i n ea n a l y t i c a lm i n i n gt e c h n o l o g y ) 等就是数据库技 术与数据挖掘技术结合应用的具体体现。 关联规则的形式为x = y ，其中x 称为规则的前项项集( a n t e c e d e n t i t e m s e t s ，简称前项) ，y 称为后项项集( c o n s e q u e n ti t e m s e t s ，简称后项) 。它说 明数据库中的某一条记录如果包含了x ，那么也倾向于包含y 。或者说，如果 数据库中的某条记录使x 中的属性值为真，那么也倾向于使y 中的属性值为真。 下面用两个实例进一步说明关联规则。 实例1 ： c o n t a i n s ( t , 购房”) = c o n t a i n s ( t , “贷款”) s u p p o r t = 3 ，c o n f i d e n c e = 8 0 在这 里，t 是表示事务记录( t r a n s a c t i o nr e c o r d ) 的变量。该规则表明，如果事务t 中包含“购房”，则它同时包含“贷款”的可能性为8 0 ，并且所有事务中有3 包 含了两者。 实例2 ： a g e ( t , ”2 5 4 5 ”) a b u y s ( t , “计算机”) = b u y s ( t ，“打印机”) 【s u p p o r t = 1 ， c o n f i d e n c e = 6 0 】该规则说明，年龄在2 5 4 5 之间并且购买计算机的人，其购 买打印机的可能性是6 0 。 关联规则挖掘就是从事务数据库中找出上述形式的规则。我们将关联规则 按不同情况进行分类： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间 的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值 型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当 然数值型关联规则中也可以包含种类变量。 例如：年龄= 1 6 = 职业= “学生”，是布尔型关联规则；性别“男”= a v g ( 身 高) = 1 7 5 ，涉及的是数值类型，所以是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有项或谓词的挖掘不考虑不同的抽象层。而在多 层的关联规则中，充分考虑到现实的数据是具有多个不同的层次所以对数据的 多层性进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则； 台式机= = s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维 关联规则是处理单个属性中的一些关系：多维关联规则是处理各个属性之间的 某些关系。 7 例如：啤酒= 尿布，这条规则只涉及到用户的购买的物品；性别= “女”_ - - _ - - 职业= “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 关联规则的扩展形式就是按照谓词的格式，可将关联规则x = y 的前项x 和后项y 写成条件的合取范式，每个条件a i = t r u e f a l s e 为布尔表达式，此时 的a i 为集合中的一个元素( 或项目) 。如果把结果中的条件表达式写成 b j = t r u e f a l s e ，则关联规则有如下的扩展形式： ( a l = t r u e f a l s e ) a ( a 2 = t r u e f a l s e ) a a ( a n = t r u e f a l s e ) = ( b l = t r u e f a l s e ) a ( b 2 = t r u e f a l s e ) a a ( b m = t r u e f a l s e ) 因为任何一个f a l s e 表达式都可以转化为一个t r u e 表达式，所以上述公式 可以简化成所有的条件都为真的合取形式： a la a 2 a a a n = b 1 a b 2 a a b m 2 2 关联规则挖掘算法概述 关联规则的挖掘是对给定的一个交易数据库d ，求出所有满足最小支持度 和最小可信度的关联规则的过程。该问题可分解为两个子问题： ( 1 ) 根据给定的最小支持度，按项目数自小而大的顺序找出数据库d 中 频繁项目集； ( 2 ) 根据频繁项目集和指定的最小可信度生成关联规则。 它的基本模型如图2 1 所示。 图2 1关联规则挖掘的基本模型 其中，d 为数据库，a l g o r i t h m 1 为频繁项目集搜索算法，a l g o r i t h m 一2 为 关联规则产生算法，r 为挖掘出的关联规则集合。用户通过指定m i ns u p ( 最小 支持度) 和r a i nc o n f ( 最小可信度) 分别与算法a l g o r i t h m l ，a l g o r i t h m 一2 交互， 并通过与r 的交互对挖掘结果进行解释和评价。 由于挖掘算法在数据挖掘过程中起着至关重要的作用，因此自从a g r a w a l 等提出挖掘交易数据库中项集间的关联规则问题以后，很多人对此进行了研究， 这些研究包括：关联规则的挖掘理论的探索、原有算法的改进和新算法的设计、 并行关联规则挖掘( p a r a l l e la s s o c i a t i o nr u l em i n i n g ) 以及量化关联规则挖掘 ( q u a n t i t i v ea s s o c i a t i o nr u l em i n i n g ) 等。在文献1 2 j 中，a g r a w a l 给出了关联规 则的定义以及查找频繁项集的经典算法一一a p r i o r i 算法。尽管近年来关联规则 挖掘算法不断涌现，但很多是在a p r i o r i 算法基础上改进的，用以提高效率和伸 缩性。如文献【1 3 4 】中提出利用采样( s a m p l i n go f d a t a b a s e ) 的方法对数据库进 8 行挖掘，可大大减少对数据库的扫描次数，提高计算效率；如何计算负边界以 找回部分遗漏的频繁项目集是算法的关键，因此，文献【1 4 j 对随机采样的方法进 行了进一步的讨论，给出了利用二项分布( b i n o m i a ld i s t r i b u t i o n ) 和契尔诺夫边 界( c h e r n o f fb o u n d s ) 处理采样的方法。文献【1 5 】提出了一种无需生成候选集的 频繁集生成算法一频繁模式增长( f p g r o w t h ) 方法，它采用新颖的数据结构和 分治策略，无需产生候选项集，从而大大降低了搜索开销，比a p r i o r i 算法速度 提高一个数量级。文献【l6 】给出了一种称为置信驱动( b e l i e f - d r i v e n ) 的关联规 则挖掘方法，由于该方法可以将有关的置信过程结合到挖掘的过程中，因此提 高了挖掘效率。文献【1 7 8 】中分别讨论了基于垂直数据库结构的关联规则挖掘方 法，这种方法不受数据库的大小、形状、内容等限制，可以有效地发掘最大频 繁项集，对于挖掘低支持度和长模式的关联规则特别有效。由于数据挖掘算法 是一项非常费时的工作，而并行算法可以充分利用并行系统的强大运算功能， 通过对挖掘任务的有效分割来提高算法的效率，因此不少学者对此进行了深入 的研究【1 4 , 1 9 , 2 0 】。还有一些工作【2 卜2 3 】在挖掘关联规则时采用了新的方法：首先将 属性值对( a t t r i b u t e s v a l u ep a i r ) 映射到二维欧拉平面上，然后在该平面上发 现优化区域( o p t i m i z e dr e g i o n ) ，再在这些优化区域上挖掘有趣的关联规则。 2 3关联规则挖掘的研究方向 目前，关联规则挖掘方面的研究己经取得了较大的进展，但对下列问题仍 有待于进一步研究： ( 1 ) 高效的挖掘算法 随着数据库的规模不断增大，不仅加大了挖掘算法的搜索空间，而且也增 加了盲目挖掘的可能性。因此必须结合领域知识去提取与我们发现任务有关的 数据，删除无用数据，有效地降低问题的维数，提高挖掘算法的效率。在这方 面，基于约束的关联规则挖掘具有广阔的前途 2 4 , 2 5 】。 ( 2 ) 基于不同对象的挖掘 目前大多数挖掘关联规则算法都是基于关系数据库或事务数据库的算法， 而数据挖掘的对象是多种多样的，如：面向对象数据库、多维数据库、数据仓 库等。设计应用于不同类型数据库的关联规则挖掘算法也将是十分有意义的工 作。 ( 3 ) 可视化挖掘 设计一个灵活方便的用户界面，允许用户与挖掘系统进行交互，并对所挖 掘的结果以可视化形式表示，使得挖掘的知识便于用户理解和使用。 ( 4 ) 模式评估 目前的关联规则的衡量标准可能会发现一些冗余的、虚假的和非挖掘者关 心的关联规则，它们表示了公共知识或缺乏新颖性，因而很有必要制定一些新 9 的模式兴趣度评估标准，指导关联规则。指导发现过程和压缩搜索空间，提高 规则质量。评估标准的制定要基于用户的信赖或期望，没有一种标准可以适用 于所有的领域和满足所有用户的要求，需要具体问题具体分析。 2 4 经典关联规则挖掘算法分析 a p r i o r i 算法是最为典型的一种层次算法，其核心技术被其它各类布尔关联 规则挖掘算法所广泛采用。f p g r o w t h 则是一种采用分治策略且不产生候选项 集的代表算法。 2 4 1 a p r i o r i 算法描述 算法l 用于寻找所有的频繁项集。该算法在第一次迭代时，由a 直接构成 候选l 项集c 1 。假设a - - - a l ，a 2 ，a m ) ，则c l = a l ， a 2 ) ， a m ) ) 。算法在第k 次迭代中，先根据上一次迭代过程中找到的频繁项集集合l k ，产生本次迭代的 候选项集的集合c k ，然后为c k 中的每一个项集分配一个初始值为零的计数器， 依次扫描数据库d 中的事务，确定包含在每条事务中且属于c k 的项集，增加 这些项集的计数值，当所有事物都扫描完成之后即可得到c l c 中各项集的支持 度，根据i d l 和给定的最小支持度确定c k 中的频繁项集。重复上述过程直到没 有新的项目产生为止。具体算法如下【2 】： 算法1 ：使用逐层迭代找出频繁项集 输入：事物数据库d ，最小支持度阂值m i n s u p 输出：d 中的频繁项集l l 1 = f i n d _ f r e q u e n t 一1 一i t e m s e t s ( d ) ； f o r ( k = 2 ；l k 1 ；k + + ) c k = a p r i o r i g e n ( l k i ，m i n _ s u p ) ； f o re a c ht r a n c t i o nt ds c a ndf o rc o u n t s c t = s u b s e t ( c k ，t ) ；g e tt h es u b s e t so ftt h a ta r ec a n d i d a t e s f o re a e hc a n d i d a t ec c t c c o u n t + + l k = c c ki c c o u n t 耋r a i n s u p ) r e t u r nl = u k l k ； v o i da p r i o r _ g e n ( l k i ：f r e q u e n t ( k 1 ) - i t e m s e t s ；m i n s u p ：m i ns u p p o r tt h r e s h o l d ) f o re a c hi t e m s e t1 1 l k 1 ， f o re a c hi t e m s e t s1 2 l r 1 i f ( 1 1 【l 】- 1 2 【i 】) 八( 1 l 2 = 1 2 1 2 ) a 八( 1 l 【k 一2 = 1 2 ( k 一2 ) 入( 1 l 【k - 1 12 k - 1 】) t h e n 1 0 c = l l o o l 2 ；j o i ns t e p ：g e n e r a t ec a n d i d a t e s i fh a s i n f r e q u e n ts u b s e t ( c ，l k 1 ，) t h e n d e l e t ec ； p r u n es t e p ：r e m o v eu n f r u i t f u lc a n d i d a t e e l s ea d dct oc k | r e t u r nc k v o i dh a s i n f r e q u e n t s u b s e t ( c ：c a n d i d a t ek i t e m s e t ；l k 1 ：f r e q u e n t ( k 1 ) i t e m s e t ) f o re a c h ( k - 1 ) s u b s