（电路与系统专业论文）关联规则挖掘算法的研究与实现.pdf

项士学住论文 m a s t e r s t h e s i s 摘要 数据挖掘技术是近年来数据库和人工智能等领域研究的热点课题，它引起了科 学界和产业界的广泛关注。关联规则挖掘是数据挖掘的一个重要研究分支，主要用 于发现数据集中项之间的相关联系。由于关联规则形式简洁、易于解释和理解已成 为数据挖掘中的研究热点。关系数据库是众多行业和部门用于存储其生产、管理和 科研等大量信息的重要形式，数据量的增长极为迅速，积极研究在关系数据库中挖 掘关联规则的有效技术具有极为广阔的发展前景。 本文首先对数据挖掘和关联规则挖掘技术发展现状进行了研究，然后对数据库 中挖掘关联规则的经典算法a p i i 硎算法和一些改进算法进行分析后，针对算法的 一些不足，提出了一种改进的关联规则挖掘算法c b a p r i 础算法。该算法的核心是 根据聚类思想生成不同事务长度的聚类表替代原始数据库，减少对庞大数据库的扫 描次数，并设置多最小支持度，以便根据用户需求快速减枝，获得较高的挖掘效率。 在前述研究的基础上，设计并实现了一个以c b a p r i 耐算法为核心的可视化挖 掘工具原型。在挖掘工具中实现了挖掘结果可视化，使用户可以直观、快速理解挖 掘的关联规则。本文最后针对数据挖掘的隐私保护和信息安全问题进行研究，介绍 了一种基于随机响应技术的数据伪装方法，并结合关联规则挖掘算法进行了讨论。 关键词：数据挖掘；数据库；关联规则：c b a p i i 耐算法；隐私保护 硕士学住论文 m a s t e r st h e s i s a b s t r a c t d a t am i l l i n gt e c h n i q u ei sa na r i s e nr e s e a r c ht o p i ci nd a t a b a s e ，a r t i f i d a li n t e l l i g e n c e f i e l d sa n ds oo n ，a n di th a sa t t r a c t e da 乒e a td e a lo fa t t e t i o i nt l l ei n f o 肌a t i o ni n d u s t r y i nr c c e my e a r s m i n i n ga s s o c i a t i o nn 1 1 e sf r o mt r a n s a c t i o nd a t a b a s ei sm o s tc o m m o n l y s e e ni nd a t am i i n g i td i s c o v e r sr d a t i o n sa m o n gi t e m ss u c ht h a tt h ep r e s e n c eo fc c n a i n i t e m si nat r a l l s a c t i o nt e n d st oi m p l yt h ep r e s e n c eo fc e n a i no t h e ri t e m s a s s o c i a t i o nn l l e s m i n i n gh a sb e c o m eat 叩t 叩i c sf o ri t sc o n d s es t y l e a 1 1 de a s yu d e r s t a d i g n o w r e l a t i o n a ld a t a b a s ei st h em o s tc o m m o nm e a n st os t o r ev a s ti 碰m m a t i o no fp r o d u c t i o n ， m a i i a g e m e n t 蛐ds c i e n t i f i cr e s e a r c h s t l l d y i gt h ce m c i e n t t c c h n o l o g yo fa s s o c i a t i o n m l c sm i l l i n gi l lr e l a t i o n a ld a t a b a s eh a saw i d ed c v e l o p m e n ti nf u t u r e t h i sp a p e r 翘a l y z e sa p i i 谢a l g o r i t l i i ，w h i c hi sad a s s i c a la l g o r i t h ma b o u tm i i l i n g a s s o c i a t i o nr i l l e si nt r a i l s 剃o nd a t a b a s e ，a n do t h e r s 1 1 l c np u tf o 刑a r da ni m p r o v e d a l g o r i t h l n ，c b a p f i o r ia i g o r i t h m ，a c c o r d i n gt os o m ed e f j c i e n c i e so fa p r i o r ia l g o r i t l l i l l i t i sc o r eo ft h ea 1 9 0 r i t l i lt h a to r i g i n a ld a t a b a s ei st e p l a c e db ys o m ec l u s 把卜t a b l e sf b r d e c r c a s i n g m et i m e so fs c a n i l i n g o r i g i i l a lh u g e d a t a b a s e a tt h es a m et i m e ，s e t m u l t i - m i n s u p p o nt od e d u c tu n n e c e s s a r yi t e m sq t l i c i 【l y 1 1 l u st h ea 培o r i t h mi si m p r o v e d c 伍d c n y b 髂e do nt 圭l ea b o v et l l e o r yr e s e a r c h ，w ed e s i g n 柚dr e a l i z ea p r j m j t i v ea s s o d a t i o n m l c sm i n i n gt 0 0 l sm o d e l a n dr e a l i z et l l ev i s u a l i z a t i o no fm i l l i n gr e s u l t sf o ru s e r st o u n d e r s t a i l di ti n n l m v e l ya n dq u i c 】( 1 y w i mt h ed e v e l o p m e n to fd a t am i n i n gt e c h n i q u e s ， p d c yp r o t e c c i o na i l di n f o 咖a t i 衄s e c u r i t yp r o b l e mh a se m e r g c dg l o b a l l y w ed i s c u s s m e t i l o d so fd a t am i n i n gb a s e do np r i v a c yp r o t e c t i o n ，舡l di m f o d u c eam e t h o do f d i s g u i s i l l gd a t ab a s e do nr 蚰d o m i z e dr c s p o s et c c h n j q u e a n dc o m b i ei tw i t t la s s o d a t o n m i n i n ga 1 9 0 f i t l l m k e yw o r d s ：d a t am i n i n g ；d a t a b a s e ；舡s o c i a t i o nr u l e s ；c b a p r i o r i 舢g o r i t h m ；p r i v a c y p r o t e c t i o n 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：下暂，吊争 日期：伽多年月7 日 ， 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：阽。琦 日期州年二月7 日 导师签名：盂1 磐 日翔：如年只日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。匿童途塞毽塞奄进卮! 旦坐生；旦= 生；旦三生筮查： 作者签名： 陆、吩 日期：m 6 年石月7 日 导师签名：；7 葵 日期：伽，年月善日 硕士学位论文 m a s t e r s t h e s i s 1 1 数据挖掘产生背景 第一章绪论 近年来，以数据库和信息技术的发展为技术保障，以网络技术的迅速普及为发 展通道，以计算机硬件、数据收集设备和存储介质的大量供应为物质基础，人们的 数据收集能力得到了大幅的提高，社会各行业都存储了大量的有关生产、管理和科 研的各种信息，全球范围内数据存储量正急剧增加。然而与此形成鲜明对比的是， 人们对大规模数据的理解能力并没有得到有效的提高，仅仅依靠传统的数据检索和 统计分析等方法已远远不能满足需要，以致出现了“数据丰富，但信息贫乏f d a t ar i c h b u ti n f o 衄a t i o np 0 0 r ) ”【1 ，2 】的局面。为从海量的数据存储中抽取模式、找出数据变化的 规律和数据之间的相互关系，充分发掘数据的潜力，以指导决策和科学发现等各项 工作，人们对数据分析并使之转化为易于理解的知识的需求越来越迫切1 3 j 。 数据挖掘( d a t am i n i i l 曲技术迎合了人们的需求，它是2 0 世纪9 0 年代初期新崛 起的一个活跃的研究领域。数据挖掘是一门汇集统计学、机器学习、数据库、模式 识别、知识获取、专家系统、数据可视化和高性能计算等多种学科的新兴交叉学科 1 4 】，这个研究领域融合了多个不同学科领域的技术与成果，使其方法表现出多种多 样的形式。为自动和智能地把海量的数据转化为有用的信息知识提供了有力的手 段，给数据和知识之间的鸿沟架设了方便之桥1 1 4 i 。 1 2 数据挖掘综述 1 2 1 数据挖掘的定义 1 9 8 9 年3 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会 上首次提出了数据挖掘一词，由于它是一门新兴的、来自各种不同领域的交叉性学 科，因此数据挖掘有很多不同的术语名称和概念描述定义版本，下面给出一个被普 遍采用的定义描述n 定义1 1 ：数据挖掘，又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，简称k d 聊，是指一个从大量的数据中提取出有效的、新颖的、潜在有 用的，以及最终可理解的模式的高级过程。其中： 数据：一个有关事实f 的集合，它是用来描述事物有关方面的信息，是我们进 一步发现知识的原材料。 硕士学位论文 m a s t e r st h e s i s 新颖：经过数据挖掘提取出的模式必须是新颖的，至少对系统来说应该如此。 通常我们可以用一个函数n ( e ，f ) 来表示模式的新颖程度。 潜在有用：提取出的模式应该是有意义的，可以用某些函数的值来衡量。用u 表示模式e 的有用程度u = u ( e ，f ) 。 可被人理解：数据库中隐含的模式通过数据挖掘过程要以容易被人理解的形式 表现出来，帮助人们更好地理解数据库中所包含的信息。 模式：对于集合f 中的数据，可以用语言l 来描述其中数据的特性。表达式 e le 所描述的数据是集合f 的一个子集f c 。只有当表达式e 比列举的所有f e 中元素的描述方法更为简单时，才可称为模式。 高级过程：一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一 种螺旋式上升过程。数据挖掘是对数据进行更深层次处理的过程，而不是仅仅对数 据进行加减求和等简单运算或查询，因此说它是一个高级的过程。 也有很多人倾向于定义知识发现是从数据库中发现知识的全部过程，而数据挖 掘是全部过程的一个特定的、关键的步骤【3 1 ，是指应用特定算法从数据中提取模式。 知识发现中的其它步骤则是用来保证从数据中挖掘得到的知识是有用的知识，否 则，盲目挖掘容易导致所发现的模式是无意义的。当数据挖掘成为普及的涵盖面更 广的术语时，我们就不必关心数据挖掘与知识发现( k d d ) 之间的明确界线，事实上， 在现今文献中的大多数里，这两个术语的使用是不加区别的。本文也将不加区分地 使用两者。 1 2 2 数据挖掘过程 数据挖掘过程工业标准c r i s p - d m 是c r o s s i d u s 埘s t a i i d a r dp r o c e s sf o rd a t a m i n i n g 的缩写，是由s p s s 的d a i m l e r _ b e n z 在1 9 9 6 年提出来的，是当今数据挖掘 业界通用的过程标准之一，它不单是数据的组织或呈现，也不仅是数据分析和统计 建模，而是从一个理解业务需求，寻求解决方案到接受实践检验的完整过程。一个 数据挖掘项目的生命周期包括六个阶段，各个阶段的顺序并不是固定的，不同的阶 段之间常常需要根据其产生的结果进行前移、推后或重复。图1 1 中的箭头指示了 各个阶段之间最重要、最通常的依赖关系。这些阶段在具体挖掘实施中可能需要重 复进行，整体上呈现为一种螺旋式上升过程。 1 商业理解( b u s i n e s su n d e r s t a n d i n g ) 这是数据挖掘的初始阶段。在这个阶段必须从商业的角度来理解项目的目标及 需求，然后将这些理解转化为数据挖掘的问题定义，并制定达成目标的初步计划。 2 硕士学值论文 m a s t e r st h e s i s 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的关键前提。挖掘的 最后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘 则带有盲目性，是不会成功的。 图1 1 数据挖掘过程c r i s p - d m 模型 2 数据理解( d a t au n d c 培t a n d i n g ) 在这个阶段首先要搜集并熟悉所有与业务对象有关的内部和外部数据，在此基 础上进行数据质量问题的鉴定，并从中发现包括隐含信息的感兴趣的数据子集。 3 数据准备( d a t ap r c p a r l t i o n ) 数据准备阶段涵盖了所有从初始数据构成最终用于挖掘的数据子集所进行的 活动。数据准备的工作可能需要进行多次，而且没有任何预定的顺序。数据准备工 作包括选择数据表、记录、属性以及数据清理、数据集成、数据选择和数据变换等。 数据清理与集成是数据准备阶段的核心，在这些步骤中所花费的时间或精力往 往会比其他步骤的总和还多。一般而言，在数据准备阶段中可能花费全部数据挖掘 过程5 m 9 0 的时问和精力。 4 建立模型( m o d e l i n g ) 在这个阶段，可能需要选择和应用不同的建模技术，并将其参数校准到最佳值。 一般一个类型的数据挖掘问题都需要用到几种技术。一些技术对数据的结构具有特 定的要求，因此经常需要返回到数据准备阶段对数据进行相应地处理。 5 模型评估( e v a l u a t i o n ) 到了项目的这个阶段，已经建立了一个或多个从数据分析的角度看似高性能的 模型。在该模型最后赴诸实旌咀前，还必须彻底地评估该模型，再回顾构造该模型 正能够达到预定的商业目标。一个关键的问题就是确定是 3 硕士学住论文 m a s t e r l st h e s i s 否存在一些重要的商业问题没有被充分地考虑到。评估阶段最后应做出数据挖掘结 果的使用决定。 6 模型发布( d 印l o y m c n t ) 模型的创建通常并非一个项目的终结。即使建模的目的是增长数据的知识，获 得的知识仍需要以客户可用的方式进行组织和呈现。根据需求，实施阶段可能非常 简单( 如生成一份报告) 或非常复杂( 一个可重复的数据挖掘过程) 。在多数情况 下，进行实旌的人是客户而菲数据分析人员。然而，即使数据分析人员不是实施的 执行者，也必须预先让客户理解，为了充分利用所创建的模型而需要进行的活动。 1 2 3 数据挖掘功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般可 以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般属性；预测性挖 掘任务在当前数据上进行推断，以进行预测。 在某种情况下，用户不知道什么类型的数据模式是有趣的，因此可能想并行地 搜索多种不同的模式，这就要求数据挖掘系统要能够挖掘多种类型的模式，以适应 不同的用户需求或不同的应用。此外，数据挖掘系统应当能够发现各种粒度f 即不同 的抽象层1 的模式。数据挖掘系统应当允许用户给出提示，指导或聚集有趣模式的搜 索。数据挖掘功能以及它们可以发现的模式类型介绍如下： 1 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的 问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问题，数 据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的 问题包括预报破产以及认定对指定事件最可能做出反应的群体。 2 关联分析 关联分析( a s s o d a t i o na n a l y s i s ) 用于发现关联规则，是数据库中存在的一类重要 的可被发现的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。 关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏 的关联网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此 关联分析生成的规则带有可信度。关联分析广泛用于购物篮或事务数据分析，关联 规则将在以下的章节中详细讨论。 3 分类和预测 分类( d a s s i f i c a t i o n ) 和预测o r e d i c t i o n ) 是两种数据分析形式，可以用于提取描述 硕士学位论文 m a s t e r st h e s i s 重要数据类的模型或预测未来的数据趋势。数据分类是一个两步的过程，第一步， 建立一个模型，描述给定的数据集，通过分析由属性描述的数据元组来构造模型， 这部分的算法有：判定树( d e d s i o n1 h e ) 、贝叶斯分类算法( b a y e s i a nc l a s s i f i c a t i o n ) 、 后向传播算法( b a c kp m p a g a t i o ) ，艮最近邻分类算法( k - n e a r e s tn e i 曲b o r c l a s s i f i e f s ) 、基于案例的推理( c a s e - b a s e dr e a s o n i n 曲、遗传算法( g e n e t i c 础9 0 f ! i t h m s ) 、 租糙集算法皿o u 曲s e t 9 0 r i t h m s ) 、模糊集算法( f u z z ys e t a p p r o a c h e s ) 、神经网络算 法( n e u r a ln e t v l ，o r k s ) 等。 分类是找出描述并区分数据类或概念类的模型或函数的过程，以便能够使用模 型预测类标记未知的对象类。导出模型是基于对训练数据集( 即其类标记已知的数据 对象、的分析。预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有 的属性值或值区间。分类是预测离散或标称值，而预测用于预测连续或有序值。分 类和预测的区别是：用预测法预测类标号( 或离散值) 为分类，用预测法预测连续值 f 例如使用回归方法) 为预测。分类和预测具有广泛的应用，包括信誉证实、医疗诊 断、性能预测和选择购物等。 4 聚类分析 聚类( a u s t e 血g ) 是将数据对象分组成为多个类或簇，在同一簇中的对象之间具 有较高的相似度，而不同簇中的对象差别较大。与分类和预测不同，聚类分析数据 对象，而不考虑已知的类标记。 主要的聚类算法可以划分为如下几类：划分方法( p a n i t i o n i n gm e t h o d ) 、层次的方 法( h i e r a r c h i c a lm c t h o d ) 、基于密度的方法c n s j t y _ b 船e dm e t h o d ) 、基于网格的方法 ( g d d - b a s e dm e t b o d ) 、基于模型的方法( m 0 d e l - b 髂c dm e t h o d ) 。聚类分析已经广泛地 应用于许多方面，包括模式识别，数据分析，图像处理，以及市场研究等。 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些 数据对象被称为是孤立点( o u t l i e r ) ，大部分数据挖掘方法将孤立点视为噪声或异常 而丢弃。然而在一些应用中( 如欺骗检测) ，孤立点事件可能比正常出现的事件更有 趣，孤立点数据分析称作孤立点挖掘。基于计算机的孤立点探测方法分为三类：基于 统计的孤立点检测( s t a t i s t i c s b a s e do u t h e rd e t e c t i o n ) 、基于距离的孤立点检测 ( d i s t a n c e - b a s e do u t l i e rd e t e c t i o n ) 、基于偏离的孤立点检测( d e v i a t i o n - b a s e do u t l i e r d e t e c t i o 曲。 孤立点分析可以发现信用卡欺骗。通过检测一个给定账号与正常的付费相比， 以付款数额特别大来发现信用卡欺骗性使用。孤立点值还可以通过购物地点和类 硕士学住论文 m a s t e r s t h e s i s 型，或购物频率来检测。 6 演变分析 数据演变分析o l u t i o a n a l y s i s ) 描述行为随时问变化的对象的规律或趋势，并 对其建模。尽管这种分析可能包含时间相关数据的特征化、区分、关联、分类或聚 类，这类分析的不同特点包含时间序列数据分析、序列或周期模式匹配和基于类似 性的数据分析。 1 2 4 数据挖掘的发展趋势 当前，数据挖掘研究正方兴未艾，随着需求的不断扩大和研究的深入，数据挖 掘技术发展发展前景广阔，而以下几方面问题可能会成为研究的焦点： ( 1 ) 专门用于知识发现的数据挖掘语言的研究，也许会象s q l 语言一样形式 化和标准化。目前己提出的d m o l 【“，语言即是着眼于上述思想研究开发的。 ( 2 ) 可视化数据挖掘的研究，数据库内容和数据挖掘结果的可视化可以帮助 用户理解和评估挖掘结果，从而对数据挖掘进行相应的调整。对交互式的挖掘来说， 开发易用与易看的工具是一个很有发展空间的领域。 ( 3 ) 在网络环境下数据挖掘方法的研究，一方面可以借助网络研究分布式数 据挖掘算法，以提高挖掘效率；另一方面可以在网络上建立数据挖掘服务器，与数据 库服务器配合，实现数据挖掘。 ( 4 ) 对各种半结构化甚至是非结构化数据源进行挖掘的深入研究，如文本数 据、图形图像数据、多媒体数据等。 ( 5 ) 基于隐私保护的数据挖掘技术的研究，为了在保护数据提供者的隐私的 前提下，挖掘出准确的知识。 ( 6 ) 数据挖掘技术是在信息时代面向用户需求提出的知识获取技术，因此， 研制开发基于数据挖掘的决策支持系统工具将是数据挖掘研究首当其充的重要任 务。 目前有很多通用的数据挖掘系统趋向于提供适用于各种商业应用的横向解决 方案( h o r i z o n t a ls o i u t i o n ) ，而不是针对某个特定的应用的解决方案。对某个特定领 域的一些数据或应用可能需要特定的算法来查找模式，而通用的数据挖掘系统对这 些特定领域的数据有其固有的局限性，有可能不能满足要求。因此，研制基于某个 特定领域的数据挖掘工具将显得尤为重要。专用的数据挖掘系统能够提供纵向解决 方案m n i c a ls o l u t i o m ，把特殊领域的业务逻辑和数据挖掘系统集成起来，将数据 分析技术与特定领域知识结合以完成特定的任务。现在数据挖掘的应用领域多集中 硕士学位论文 m a s t e r st h e s l s 于生物医学，d n a 分析，金融，零售业和电信部门等。 1 3 本文的主要研究方向与内容概要 关联规则挖掘是本文的主要研究方向。由于数据挖掘任务所面对的数据集通常 是由数以百万计的记录所构成的大型数据库或数据仓库，因此如何提高从大型数据 库中挖掘关联规则算法的效率，以有效地降低计算的复杂性、提高算法的运行速度， 便成为关联规则挖掘研究中的核心问题。基于数据挖掘的研究现状和关联规则挖掘 算法存在的问题，本文主要进行了以下的研究工作： 1 对数据挖掘和关联规则挖掘技术进行了研究，提出了a p r i o r i 算法的性能 瓶颈问题，详细地讨论了提高算法效率的各种优化技术，客观地分析了它们的优缺 点。针对a p r i o r i 算法的不足，提出了一种改进的关联规则高效挖掘算法c b a p r i o r i 算法。改进算法在第一次扫描数据库的过程中，根据事务的长度生成不同的聚类表， 在接下来迭代产生频繁相集的过程中，只需扫描部分聚类表，减少了计算成本。同时 设置了多最小支持度，可以根据用户的需求快速剪枝，提高了算法的效率。 2 基于c b a p r i o r i 算法思想，以关系数据表为最基本工作单元，设计并实现了 一个简单挖掘关联规则工具原型，实现挖掘结果的可视化。 3 针对数据挖掘要面对的一个重要问题隐私保护和信息安全进行研究。介绍 了一种基于随机响应技术的数据伪装方法，并结合关联规则挖掘算法进行了讨论。 根据以上课题目的，论文结构安排如下： 第一章，介绍数据挖掘产生的背景、定义、过程和功能，本文的主要内容概要。 第二章，对关联规则挖掘问题进行了描述，给出了关联规则挖掘问题的定义和 研究现状、对数据库中经典的关联规则挖掘算法进行了详细分析。 第三章，分析现有改进算法，提出了基于聚类的关联规则挖掘改进算法，并详细 评估和分析。 第四章，介绍了以c b a p r i o r i 算法为核心的挖掘工具原型设计与实现过程。 第五章，对数据挖掘中隐私保护问题进行研究和讨论。 第六章，对所做的工作进行了总结，展望了关联规则挖掘中有待进一步解决的 问题。 7 硕士学住论文 m a s t e r s t h e s l s 2 1 关联规则概述 第二章关联规则挖掘 关联规则挖掘( a s s o d a t i o nr u l em 抽i n 曲发现大量数据中项集之间有趣的关联或 相关联系。关联规则挖掘是数据挖掘研究的个重要分支，关联规则是数据挖掘的 众多知识类型中最为典型的一种。目前关联规则挖掘问题己经引起了数据库、人工 智能、统计学、信息检索、可视化及信息科学等诸多领域的广大学者和研究机构的 高度重视，取得了许多研究成果。关联规则形式简洁、易于解释和理解并可以有效 地捕捉数据间的重要关系，从大型数据库中挖掘关联规则问题己成为数据挖掘中最 成熟、最重要、最活跃的研究内容【7 “。 关联规则可以表示为：购买了项目a 和b 的顾客中有9 5 的人又买了c 和d 。 从这些规则可找出顾客购买行为模式，可以应用于商品货架设计、生产安排、针对 性的市场营销等。采用关联模型比较经典的例子是“啤酒和尿布”的事例，在美国， 一些年轻的父亲下班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息进行 挖掘，发现在购买婴儿尿布的年轻父亲中，有3 0 4 0 的人同时要买一些啤酒。超 市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是：销售额明显增加了。 关联规则问题由a g r a w a l i7 j 等于1 9 9 3 年首先提出，以后诸多的研究人员对关联 规则的挖掘问题进行了大量的研究【n 。他们的工作包括对原有的算法进行优化， 如引入随机采样、并行的思想、增加衡量标准、规则约减、改变存储结构等，以提 高算法挖掘规则的效率，对关联规则的应用进行推广，从最初的商业指导到生活中 的其他领域，如教育、科研、医学等。 2 ，2 关联规则挖掘的基本概念 2 2 1 关联规则定义 定义2 1 项集、事务、事务集：令，= f 1 ，t ，乇) 是一组项的集合，称为项集。 事务r 是项的集合，即陷。每个事务处理有一个唯一的标志符t i d ，一个事务可 以表示成f = t 册，其中是项集，的一个子集，即事务t i d 包含项集，若4 是一个项集，且4 ，若对r = c 彻，) ，满足4 ，则称r 包含彳。事务集d 是事务r 的集合，事物集d 又称为数据集，通常用项集，表示d 中包含的所有项组 顽士学位论文 m a s t e r st h e s i s 成的集合。 定义2 2 关联规则、规则前件、规则后件：对项集爿，b ，且爿n b = 西， 用4 一口表示一条关联规则。在关联规则爿一曰中，彳称为规则前件，口称为规则 后件。 定义2 3 支持度：对于规则爿一b ，若事务集d 中包含4 = 争占的事务数占事务 总数的5 ，则称规则爿 b 的支持度( 5 唧。一) 为s 。记为s 毡印。肘 占) = j 。 定义2 4 置信度：对于规则爿一b ，若d 中包含爿的事务中有c 同时包含曰， 则称规则爿 占的置信度( ，班d e n c e ) 为c 。记为够d 唧c 8 口 b ) = c 跳c o ，脚比口郴) = 鼍焉茅。 定义2 5 最小支持度、最小置信度、强关联规则：对事务集d ，由用户指定最 小支持度( 记为m 觑s 印) 和最小置信度( 记为m 如c d 巧) 。对规则彳一占，若 s 唧d 一( 彳u b ) 2 胁s 印且c d ，e 如n 钟似 口) 小抽c 。玎，称规则爿 曰为强关联规 则。关联规则挖掘的目的就是挖掘目标事务集中所有的强关联规则。 定义2 6 频繁项集：对事务集d 和项集4 ，若s 仰。一似) m 沁印，则称4 为频繁项集位e q u c n ti t 锄s e t ) 。 定义2 7 简约关联规则：对于关联规则爿一b ，设其规则后件 b 一纯，。，+ 。) ，t 。，+ 。j ，将关联规则4 号四分解为4 一 f 卅) ， 爿= 争纯+ ，) ，一一亿+ 。) ，这些单后件的关联规贝称为筒约关联规则。 性质2 1 ：如果“，口是项集，且4 曰，则s 唧d r f 口j s 唧o r f ( 印。 性质2 2 ：设彳是大项集，丑是项集，如果4 b ，则口也是大项集。 性质2 3 ：设爿是小项集，口是项集，如果b 一，则曰也是小项集。 2 2 2 关联规则的分类 根据不同的划分标准，关联规则有如下分类： 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关 系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进 行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联 规则中也可以包含种类变量。 例如：性别= “女”= 职业= “秘书”，是布尔型关联规则；性别= “女”= ) a v g ( 收入) 9 = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多不同的层 次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n v 打印机，是个细节数据上的单层关联规则：台式 机= s o n v 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在 多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒= 尿布，这条规则只涉及到用户的购买的物品；性别= “女”= 职业 = “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 目前还推广了多层次关联规则、时态关联规则、加权关联规则、多支持度关联 规则、负关联规则和混合关联规则等。给出了关联规则的分类之后，在下面的分析 过程中，我们就可以考虑某个具体的方法适用于哪一类规则的挖掘，某类规则又可 以用哪些不同的方法进行处理。 2 3 关联规则挖掘的研究现状 由于关联规则挖掘可以发现用传统的人工智能和统计方法无法发现的项与项 或属性与属性间的关系规律，满足了人们从大规模数据存储中获取知识的迫切需 求，因此具有重要的研究价值。目前世界上知名大学的研究机构和各大公司的 研究部门都投入了大量精力对其进行研究，并取得了诸多研究成果。 美国斯坦福大学智能数据库系统实验室开发出了大量的商用化数据挖掘系统， 如d b m i n e r 挖掘系统，它包含了许多先进的挖掘算法，用户无需具有高级的统计知 识和培训即可利用它挖掘出包括关联规则、序列模式、分类等在内的多种类型的知 识：该系统可以在多种平台上运行，并与许多主流的数据库管理系统( 如s q l 广s e v e r ， 0 r a c l c 等1 结合紧密；同时还引入了在线分析挖掘技术，使得系统更能充分发挥数据 仓库的分析优势。m m 公司的a l m a d c n 实验室所进行的q u e s t 项目同样也是数据挖 掘研究领域中的佼佼者，该项目包含了对关联规则、序列模式、分类及时问序列聚 类的研究，其代表性的产品有：d b 2 i n t e u i g e n tm i n e rf o rd a t a ，该产品在1 b m 的d b 2 平台上应用，也有w i n d o w s n t 下的类似产品。除了以上提及的世界知名的公司和 科研机构外，还有许多大学的研究机构和学者对该领域的发展做出了重要贡献，如 1 0 硕士学位论文 m a s t e r st h e s i s 加拿大s i i n o nf h s e ru n i v e r s i t y 大学的j i a w e ih a n ，比利时赫尔辛基大学的m a 皿i l a ， t 0 i v o n n e n 等都是数据挖掘研究的著名专家，它们的许多工作都是在该领域中具有 奠基性的。近年来，国内的关联规则挖掘研究也正逐渐掀起高潮，出现了一批相关 的科研项目，在算法和应用方面取得了一些具有扩展性或突破性的研究成果。下面 就关联规则挖掘算法和相关扩展等状况加以介绍。 2 4 关联规则挖掘算法 2 4 1 关联规则挖掘算法两步骤 关联规则挖掘的任务就是在事务数据库d 中找出具有用户给定的最小支持度 j ，l 细s 印和最小置信度m 加c 伽，的强关联规则。强关联规则，哇 丑对应的项集a u b 必定是频繁项目集，而频繁项目集a u b 导出的关联规则爿一曰的置信度又可由频 繁项目集a 和a u b 的支持率计算。因此，关联规则挖掘可分解为两个步骤： ( 1 ) 根据最小支持度阈值找出数据集d 中所有频繁项目集； ( 2 ) 根据频繁项目集和最小置信度阈值产生所有关联规则。 第一个步骤的任务是迅速高效地找出d 中全部频繁项目集，是关联规则挖掘的 中心问题，是衡量关联规则挖掘算法效率的主要指标，目前大多数有关关联规则挖 掘问题的研究都是针对第一个子问题而展开的，本文将在后面的章节中对该过程进 行重点介绍和分析。 第二个步骤的算法相对简单，它只是由频繁项集产生强规则的枚举探查过程。 具体实现方法为：对频繁项集l 中的每一个元素f ( 即f 是l 中的某个频繁项集) ，产 生其所有非空子集，对于f 的每个非空子集s ，如 s 唧d 厶昭p d r f 4 j d d m i n c o 矽，则输出强规则“s = f f - 印”。 根据性质2 1 ，可以得出如下推论： 推论2 1 ：如果规则s = f f s ) 不满足最小置信度，则对于s 的所有非空子集s 7 ， 规则s 7 = s 7 儿包不满足最小置信度。 推论2 2 ：如果规则s = r f 0 满足最小置信度，则对于s 的所有非空子集s7 ， 规则“5 7j s 7 也一定满足最小置信度。 在根据频繁项目集产生强规则时，利用推论可以减少计算量，提高强规则的产 生效率。 综上所述，关联规则挖掘的基本模型可用图2 1 表示，其中d 为数据集， 1 1 硕士学位论文 m a s t e r st h e s i s 舢g o r i t h m 1 为频繁项集的搜索算法，灿g o r i t h m 一2 为关联规则的产生算法，r 为挖 掘出的关联规则集合。用户通过指定最小支持度阈值( m m 5 印) 和最小置信度闽值 ( m 抽c d 巧) 分别与算法舢g o r i t h m 1 和挑嘣t h m 一2 交互，并通过与r 的交互对挖掘 结果进行解释和评价。 图2 1 关联规则挖掘的基本模型 2 4 2 关联规则挖掘算法分类 自从提出挖掘顾客交易数据库中项集间的关联规则问题之后，该问题越来越受 到重视，诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包 括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则 的效率：提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进 行推广。通过分析总结，我们根据处理数据的不同方式这些算法分为下面这几类： 1 搜索算法 搜索算法是在读入数据集中的每条事务时，对该事务中包含的所有项目集进行 处理，因此搜索算法需要计算数据集d 中所有项目集的支持数。a i s 算法、s e t m 算 法，以及以建格算法为主体的关联规则挖掘算法都是这种搜索算法。 搜索算法只需对数据集一次扫描就可以找出所有的频繁项目集，对每一条包 含n 个项目的事务就将产生掣一1 个项目集，数据集d 中包含的项目数很大时，所 需计算和存储的候选项目集的数量往往非常庞大。因此，该类算法只适合于项目集 数量相对较小的数据集中的关联规则挖掘。 2 宽度优先算法，也可以说是分层算法 此类算法包括r 姆a w a l 等人提出的a l p r i o r i 、a p r i q r 弼d 和a p r i o r i h y b r i d 算法 【7 $ ，1 5 ，1 6 1 ，j s p a r k 等人的d h p 算法【1 2 1 7 】等。 a d r i o r i 算法是这类算法的典型代表，该算法需扫描数据集的次数等于最大频繁 硕士学位论文 m a s t e r st h e s i s 项目集的项目数。a p r i o r i 砸d 算法在a p r i o r i 算法的基础上对数据集进行修剪，以减 少扫描数据库的时间，但对数据集的修剪需要额外的计算和加操作。d h p 算法采 用哈希技术对数据集和候选项目集进行修剪，特别是对候选2 项目集的修剪特别有 效。a p r i c d h y b d d 算法是a p r i o r i 算法和a p r i o 栅d 算法的融合，该算法开始采用 a p r i o r i 算法，然后在每次扫描完数据集之后计算修剪后的数据集的大小；若修剪后 的数据集可在内存中进行处理，则切换至a p r i o r i 豇d 算法直到找出所有的频繁项目 集。 3 深度优先算法 此类算法中最新最高效的是j ，h a n 等人提出的f p g r o w t h 算法【1 8 j 。f p 伊。研h 算 法无须生成候选项目集，显著地缩小了搜索空间，有效地避免了产生“知识的组合 爆炸”，挖掘效率明显提高。 4 数据集划分算法 此类算法包括a s a v a s e r e 等人的p a n i t i o 算法【1 4 1 ，s b 血等人的d i c 算法1 1 9 】 等。这些算法将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访 问外存的帕开销。p a n i t i o 算法只需要对整个数据集进行两次扫描，d i c 算法在 数据块划分恰当时可以通过两次扫描数据集找出所有的频繁项目集。 数据集划分算法的候选项目集的数量一般比a p i i 耐算法的候选项目集的数量 大，数据集划分算法是各种并行关联规则挖掘算法和分布式关联规则挖掘算法的基 础。 5 抽样算法 此类算法包括j s p a r k 等人提出的可调精度的挖掘算法【拟，h t 0 i v o n c n 的 s a m