（计算机软件与理论专业论文）带否定关联规则挖掘算法的研究.pdf

华中科技大学硕士学位论文 摘要 数据挖掘作为数据库研究领域中的热点，正受到越来越多的关注。它被定 义为在数据中寻找正确的、有趣的、潜在有用的并最终可以理解的模式。基于 关联规则的挖掘是其中一个重要的研究方法，具有重要的理论价值和广泛的应 用前景。 关联规则中最有名和最有影响力的算法是a p r i o r i 算法，a p r i o r i 对布尔型 数据库的标准关联规则的挖掘有很高的效率。 在很多领域中，只挖掘出标准关联规则是不够的，需要对数据项的否定项 进行挖掘。带否定项的关联规则是指允许在关联规则中出现负项目，对关联规 则的形式做出了扩展，从而提高了关联规则的描述能力。 a p r i o r i 算法在挖掘带否定项的关联规则时显得非常笨拙和低效，不擅长处 理相关性高的数据，c a 算法对稠密型数掘库有很好的效率，但是挖掘出来的 规则会很多，并且很多规则可能是无趣的。针对这种不足，i n a 算法在支持度 置信度的模式上增加了一个新的评估参数一必趣度。通过引入兴趣度，有效 的改善了c a 算法中的候选集膨胀现象，删除了一些被挖掘出来而没有兴趣的 关联规则。这种算法能够有效挖掘出有趣的带否定关联规则。i n a 算法在多维 数据库中挖掘带否定关联规则也有较好的效率，更广泛的应用了带否定关联规 则的挖掘。对于多维数据库，采用与数据仓库相结合的方法，利用数据仓库联 机分析的一些结果，能够更好的挖掘带否定关联规则。 通过初步实验将c a 算法挖掘出的频繁项目数与a p r i o r i 算法挖掘出的f 频 繁项目数进行了比较，显示了c a 算法的有效性，同样将i n a 算法挖掘出的有 趣规则与c a 算法挖掘出的规则进行比较，表明了i n a 算法的实用性。 关键词：数据挖掘，关联规则，带否定关联规则，数据仓库 华中科技大学硕士学位论文 a b s t r a c t d a t am i n gi sr e c o g n i z e da st h eh o tt o p i ci nt h ed a t a b a s er e s e a r c hf i e l d ，a n dh a s r e c e i v e di n c r e a s i n ga t t e n t i o nb yr e s e a r c h e r s w h i c hi sd e f i n e da st h en o n t r i v i a l p r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l y u s e f u la n d u l t i m a t e l yu n d e r s t a n d a b l e p a t t e r n s i nd a t a m i n i n ga s s o c i a t i o nr u l e sf r o ml a r g ed a t a b a s e sp l a y sa ne s s e n t i a l r o l ei nm a n yd a t am i n i n gt a s k sa n dh a sb r o a da p p l i c a t i o n s a s s o c i a t i o nr u l e sm i n i n gi sc o n s i d e r e dt ob eo n eo ft h em o s ti m p o r t a n tt a s k so f d a t am i n i n g ，w h i c hi st of i n dt h er u l e sw i t ht h es u p p o r ta n dc o n f i d e n c eg r e a t e rt h a n t h et h r e s h o l d s t h em o s tf a m o u sa n de f f e c t i v ea l g o r i t h mi na s s o c i a t i o nr u l e sm i n i n g i s a p r i r o ia l g o r i t h m t h ea l g o r i t h mi se f f e c t i v ea ts t a n d a r da s s o c i a t i o nr u l e sm i n i n g i nb o o l e a nd a t a b a s e i nm a n yf i e l d s ，o n l ym i n i n gs t a n d a r da s s o c i a t i o nr u l e sa r en o te n o u g h m i n i n g n e g a t i v ea s s o c i a t i o n r u l e si sr e q u i r e d n e g a t i v ea s s o c i a t i o nr u l e sa l l o wt h en e g a t i v e i t e m s e t sa p p e a ri nt h ea s s o c i a t i o nr u l e s ，e x p a n dt h ed e f i n i n go fa s s o c i a t i o nr u l e s ， a n dt h e ni n c r e a s et h ea b i l i t yo f d e s c r i p t i o no f a s s o c i a t i o nr u l e s b e c a u s eb e t w e e nt h e n e g a t i v e i t e m s e t sa n dt h e p o s i t i v e i t e m s e t sh a sh i g h r e l a t i v i t y ，a p r i o r ia l g o r i t h m i s c l u m s ya n dl o w l y e f f e c t i v ei n m i n i n gn e g a t i v e a s s o c i a t i o nr u l e s ，a n di ti sn o tg o o da td e a lw i t ht h eh i g hr e l a t i v ed a t a b a s e do nt h e r e l a t i v i t y , c aa l g o r i t h mh a sg o o de f f i c i e n c yi nc l o s ed a t a b a s e 。b u ti tc a nm i n em a n y a s s o c i a t i o nr u l e si n c l u d i n gu s e l e s so n e sb yt h i sw a y i n aa l g o r i t h ma d d san e w e v a l u a t i n gp a r a m e t e r i n t ot h e s u p p o r t - c o n f i d e n c em o d e l i n t e r e s t i n gp a r a m e t e r , w h i c hi m p r o v e st h ep e r f o r m a n c eo fc a n d i d a t ee x p a n s i o ni nc aa l g o r i t h m ，a n d d e l e t e s m a n yu n i n t e r e s t i n g a s s o c i a t i o nr u l e s i n aa l g o r i t h mi se f f e c t i v ei nt h e m u l t i d i m e n s i o n ，w h i c ha p p l yt h en e g a t i v e a s s o c i a t i o nr u l e si nm o r ef i e l d s t o m u l t i d i m e n s i o n d a t a b a s e ，c o m b i n i n gt h e d a t aw a r e h o u s ei sm o r ee f f e c t i v ei n m i n i n ga s s o c i a t i o nr u l e s c o m p a r i n gt h ef r e q u e n ti t e m s e t sn u m b e rw i t hc aa l g o r i t h ma n dt h ep o s i t i v e f r e q u e n ti t e m s e t sb ye x p e r i m e n t ，t h ee x p e r i m e n ts h o w st h ev a l i d i t yo fc a a l g o r i t h m 华中科技大学硕士学位论文 i nt h es a m ew a y ，c o m p a r i n gt h ei n t e r e s t i n ga s s o c i a t i o nb yc aa l g o r i t h mw i t hb y i n a a l g o r i t h m ，a n dt h ee x p e r i m e n ts h o w s t h ep r a c t i c a b i l i t yo f1 n a k e y w 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 ，n e g a t i v ea s s o c i a t i o nr u l e s d a t a 纬0 r e h o u s e i l i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：耗即 日期：2 鲫斗年牛月2 岁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密订。 ( 请在阻上方框内打“4 ”) 学位论文作者签名：7 现冉 日期：口口叶年斗月；日 华中科技大学硕士学位论文 1绪论 1 1 问题的提出 今天的人们已经拥有了大量的数据，迫切希望将这些数据转化为有用的知识和 信息。在这样的背景下产生了数据挖掘这个新兴学科并迅速成为信息科学中的热r 研究领域，受到广泛的关注。数据挖掘的结果( 即挖掘所获得的知识) 能使用在如 商业管理、市场分析，工程设计和科学探索等各个领域。 数据挖掘是信息科学革命性发展的直接结果。从信息科学的发展历程来看，首 先成熟的是以文件系统为代表数据采集技术。当数据的收集不再是问题以后，对数 据的处理( 包括存贮，检索等等) 就成为了系统的瓶颈。数据库技术成功地解决了 上述问题后，人们就希望能够对数据进行更好的分析和理解。这样就产生了数据仓 库和在线数据分析o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ) 技术，解决了人们的 需求。比如在线数据分析的工具支持多维分析和一定范围内的决策支持等等。 但人们还需要对数据做出更深入的分析( 如数据的分类、聚类、特征等等) 。以 难以想象的高速度所收集的大量数据被存贮在超大规模的数据库中，远远超出了人 们能理解它的能力，这被称为“数据丰富而信息贫乏”。结果是数据库往往变成了“数 据的坟墓”，很少被人访问，决策更多地不是依赖信息，而是依赖决策者的直觉。数 据挖掘就是要改善“数据丰富而信息贫乏”的情况，将“数据的坟墓”变成隐藏着 知识的“金矿”。 1 2 数据挖掘技术概述 数据挖掘( d a t e m i n i n g ) ，又称数据库中的知识发现k d d ( 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 ) ，即从大量的数据中提取出可信、新颖、有效并能被人理解的模式的高级 处理过程。数据挖掘是从大量的、不完全的、有噪音的、模糊的、随机的实际应用 数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知识的过 程。与传统的信息处理方法相比，数据挖掘技术有其自身的特点 1 】： 华中科技大学硕士学位论文 1 ) 处理对象为大规模数据库，数据规模十分巨大； 2 ) 信息查询一般是由决策指定者( 用户) 提出的即时随机查询，往往没有精确 的查询要求，需要靠数据挖掘技术寻找其可能感兴趣的东西； 3 ) 在一些应用中，某些行为并没有实际发生或者很少发生，因而它们对输出所 造成的影响没有在数据库中体现出来，需要利用数据挖掘技术从数据库中提取有用 的规则，为这种情况提出预测： 4 ) 在一些应用中，由于数据变化迅速可能很快过时，因此要求数据挖掘技术能 很快对数据变化作出反应以提供决策支持，数据挖掘既要发现潜在的规则，还要管 理和维护规则，而规则是动态的，当前的规则只能反应当前状态的数据库特征，随 着新数据的不断加入，规则需要随之更新： 5 ) 数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必适用于 所有的数据，当达到某一个阈值时便可认为有此规律。 根据文献 1 】典型的数据挖掘系统具有以下主要部分： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子 表格或者其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服 务器负责提取相关数据。 知识库：这是领域知识，用于指导搜索或评估结果模式的兴趣度。这种知识 可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户确信方面的知 识也可以包含在内。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于 特征化、关联、分类、聚类分析以及演变和偏差分折。 模式评估模块：通常，此部分使用兴趣度度量，并与数据挖掘模块交互，以 便将搜索聚焦在有趣的模式上。它可能使用兴趣度闽值过滤发现的模式。模式评估 模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。对于有 2 华中科技大学硕士学位论文 效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以便将搜索限制 在有兴趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系统交 互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结 果进行探索式数据挖掘。此外，此部分还允许用户浏览数据库和数据仓库模式或者 数据结构，评估挖掘的模式。 系统模式如图1 1 所示： 图1 1 典型的数据挖掘系统 数据挖掘是信息技术自然演化的结果。2 0 世纪6 0 年代以来，数据库和信息技术 已经系统的从原始的文件处理演化到复杂的、功能强大的数据库系统。自7 0 年代以 来数据库系统的研究和开发已经从层次和网状数据库系统发展到开发关系数据库 系统( 数据存放在关系表结构中) 。自8 0 年代中期以来，数据库技术的特点是广泛接 华中科技大学硕士学位论文 受关系技术，研究和开发新的、功能强大的数据库系统。分析技术及数据仓库技术 的出现，提供了汇总、合并、聚集功能和可以从不同的角度观察信息的能力。尽管 o l a p 工具支持多维分析和决策，对于深层次的分析，如数据分类、聚类和数据随时 间变化的特征，仍然需要其他的分析工具。k d d 一词首次出现在1 9 8 9 年举行的第十 一届国际联合人工智能学术会议上。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 技术专刊。并行计算、计算机网络、信息工程等其他领域的国际 学会或学刊也把数据挖掘和知识发现列为专题和专刊讨论。此外，在i n t e r n e t 上 还有不少k d d 电子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威。 与国外相比，国内对d m 的研究稍晚一点。1 9 9 3 年国家自然科学基金首次支持对 该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现的基 础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空军第三 研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现 中的应用进行了较深入的研究；北京大学也在开展对数据立方体代数的研究；华中 科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则发现算法的优化和改造；南京大学、四川联合大学和上海交 通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘等。 目前，数据挖掘的应用也越来越多，据国外专家预测，在今后的5 一l o 年内， 随着数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。 1 3 数据挖掘的技术及其应用 数据挖掘任务般可以分为两类：描述和预测。描述性挖掘是刻划数据库中数 据的一般特性。预测性挖掘任务是对当前数据进行推断，以进行预测。数据挖掘功 能以及能够发现的模式类型包括： l 、概念类描述：特征化和区分( c l a s s c o n c e p td e s c r i p t i o n ) 这种描述可以通过下述方法得到；1 ) 数据特征化，一般地汇总所研究类的数据； 2 ) 数据区分，将目标类与一个或多个比较类进行比较；3 ) 数据特征化和比较。 华中科技大学硕士学位论文 2 、关联规贝f l ( a s s o c i a t i o na n a l y s i s ) 关联规则展示属性值频繁的在给定的数据集中一起出现的规则。主要用于购物 篮分析和事务型数据库分柝。 3 、分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标记未 知的对象类，分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可 能希望预测某些空缺的或者不知道的数据值，而不是类标记。当被预测的值是数值 数据时，通常称为预测。尽管预测可以设计数据值预测和类标记预测，通常预测限 于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 4 、聚类分析( c l u s t e r i n g ) 聚类分析数据对象，而不考虑已知的类标汜。对象根据最大化类内的相似性、 最小化类间的相似性的原则进行聚类或者分组。 5 、孤立点分析( o u t l i e r ) 孤立点是指数据库中可能包含的一些数据对象，与数据的一般行为和模型不一 致的点。大部分数据挖掘方法将孤立点视为噪声或者异常而丢弃。然而，在一些应 用中( 如欺骗检测) ，罕见的事件可能比正常出现的事件更有趣。 6 、演变分析( e v o l u t i o na n a l y s i s ) 演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管这可能 包括时间相关数据的特征化、区分、关联、分类或者聚类，这类分析的不同特点包 括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 根据这些模型，通常采用的技术是关联分析、决策树、遗传算法、贝叶斯网络、 粗糙集方法、神经网络和统计分析。 贝叶斯网络【2 1 是用来表示变量集合的连接概率分布的模型，它提供了一种自然的 表示因果关系的方法。贝叶斯网络本身并没有输入和输出的概念，各结点的计算是 独立的，因此，贝叶斯网络的学习既可以由上级结点向下级结点推理，也可以是由 下级结点向上级结点推理。 贝叶斯网络最初是由rh o w a r d 和j m a t h e s o n 于1 9 8 1 年提出，后来c o o p e l g 与 华中科技大学硕士学位论文 h e r s k o v i t s e 给出了b d ( b a y e s i a nd i r c h l e t ) 度量模型( 3 】，h e c k e m l a n d 等扩展了b d 的思 想 4 1 。贝叶斯网络其它方向的研究也层出不穷，例如非线性动态模型的g i b b s 抽样模 型”1 ，贝叶斯分类器 6 7 1 等等。 决策树嘲方法首先选择训练样本的一个子集以形成一个决策树，如果此树没有为 所有的对象给出一个正确的答案，则将例外情况加入树中，不断重复这一个过程， 直到发现正确的决策集。最终形成这样一颗树：每一个叶子代表一个类名，每一个 内部节点描述一个属性，节点的每个分支代表对应于该属性的每一个可能的值。 i d 3 算法 9 1 是一个决策树中最基本的算法，c 4 5e 1 也是一个非常经典的算法。 遗传算法1 是模拟生物进化过程的算法。由3 个基本算子组成。繁殖( 选择) ：是 从1 个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程。交叉( 重 组) ：选择2 个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个体。变异( 突变) ： 对某些个体的某些基因进行变异( 1 变0 ，0 变1 ) 。这种遗传算法可以起到产生优良后 代的作用。这些后代满足适应度值，经过若干代的遗传，将得到满足要求的后代( 问 题的解) 。遗传算法已在优化计算和分类机器学习方法方面显示了明显的优势。 神经网络方法 1 2 1 是基于生物神经系统的结构和功能而建立起来的，模拟人脑神 经元的方法。以m p 模型和h e b b 学习规则为基础，可以建立三大类神经网络模型： 前溃式网络( 以感知机、反向传播模型、函数型网络为代表，可用于预测、模式识 别等方面) ，反馈式网络( 以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想 记忆和优化计算) ，自组织网络( 它以a r t 模型、k o h o l o n 模型为代表，用于聚类) 。 利用神经网络所固有的并行结构、并行处理、自适应性、知识的分布存储、较强的 容错性、本质的非线性系统等特性，通过网络训练，可以建立数据库信息的非线性 模型，并从中提取相应的规则。 粗糙集方法是利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式 识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确能力就越低， 即模糊性就越强。 关联规则是本文重点讨论的内容，我们将在后面章节展开讨论。 文献1 3 1 y u 举了这些方法的应用领域，见表1 1 。 华中科技大学硕士学位论文 表11 数据挖掘的应用领域表 技术方法主要功能和特点 主耍应用领域 关联分析分类、聚类零售业、保险业和制造业 决策树归类分类，可理解性制造业、医学和零售业等 遗传算法聚类、优化，高效性金融业、保险业和农业等 贝叶斯网络分类、聚类和预测，易理解医学、制造业和电信业 粗糙集方法不确定分类零售业、金融业和制造业 神经网络预测、分类、聚类，解释性差金融业、保险业和制造业 统计分析聚类，结果精确、易理解金融业、制造业和医学 典型的数据挖掘应用包括以下几个方面： 1 、零售业 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋向，对 于零售商制定销售策略是至关重要的。通过关联规则挖掘，分析客户的响应率，发 现有利顾客的特征，有目的性的开展广告和销售业务。 2 、金融业 由于金融业中的数据相对比较完整，质量较高，因此，数据挖掘在这一领域中 的应用相对较为成熟，也取得较好的社会效益和经济效益。通过分析市场波动的因 素，建立预测模型，进行投资分析和预测，改进预测市场波动的能力，为投资决策 提供科学的依据。 3 、医疗保健 医学和生物工艺学中的基因分析中，需要处理大量的基因数据，通过数据挖掘 技术有助于对这些数据的研究和理解。医学领域中对疑难病症的攻关和研究，结合 数据挖掘技术，建立各种医疗数据模型，找出数据本质上的联系和现象，推动医学 研究的进展。 4 、制造业 在制造业中，数据挖掘广泛地应用于控制产品生产流程和技术规划方面，分析 华中科技大学硕士学位论文 产品各种指标参数的关系，优化原料的搭配，开发新的产品类型。根据市场信息数 据库中居民密度分布、收入状况和相应的城市规划等信息，企业可以借助数据挖掘 技术展开产品需求量的调查。 1 ，4 数据挖掘与数据仓库的关系 原则上讲，数据挖掘可以在任何类型的数据存储上进行。但现在的数据挖掘系 统大多主张把数据仓库当成实施理想的数据挖掘的基础。这是因为数据仓库中具有 数据面向主题集成、保存长时间的历史数据、数据具有一致性、数据具有稳定性且 随时间扩充、数据仓库提供下钻上卷功能的特点 14 1 ，非常适合数据挖掘对源数据的 要求。 构建数据仓库涉及数据清理和数据集成，可以看作数据挖掘的一个重要预处理 步骤。此外，数据仓库提供联机分析处理o l a p 工具，用于各种粒度的多维数据分 析，有利于有效的数据挖摘。进一步讲，许多其他数据挖掘功能，如分类、预测、 关联和聚类，都可以与o l a p 操作集成，以加强多个抽象层上的交互知识挖掘。因 此，数据仓库为数据挖掘提供了有效的平台。 数据仓库为数据挖掘提供了经过整理过的数据。同时，o l a p 的多角度、多层次 的数据汇总能力为数据挖掘提供了良好的基础。o l a p 与数据挖掘一体化模型是 o l a m ( o n l i n ea n a l y t i c a lm i n i n g ) ，o l a m 模型建立在多维数据视图上，在数据 立方体中数据挖掘可在多维、多层次的抽象空间中进行，利于灵活的挖掘知识。数 据立方体的计算与传统的挖掘算法的结合使数据挖掘有极大的灵活性和交互性。 数据仓库与数据挖掘关联结构见图12 。 0 l a p 和数据挖掘的功能可以视为不可交的：o l a p 是数据汇总、聚集工具， 它帮助简化数据分析，而数据挖掘是自动发现隐藏在大量数据中的隐含模式和有趣 知识。o l a p 工具的目标是简化和支持交互数据分析，而数据挖掘的目标是尽可能的 自动处理，尽管允许用户指导这一个过程。在这种意义下，数据挖掘比传统的联机 分析处理前进了步。并且数据挖掘涵盖面要比简单的o l a p 操作宽的多，因为它 不仅执行数据汇总和比较，而且执行关联规则、分类、预测、聚类、时间序列分析 华中科技大学硕士学位论文 和其他数据分析任务川。 图形用户界面 睦疟 提取、转换、加载卜舄 图12 数据仓库与数据挖掘关联结构 数据挖掘不限于分析数据仓库中的数据，它可以分析比数据仓库提供的汇总数 据粒度更细的数据，可以是事务的、文本的、空间的和多媒体数据。 数据挖掘的一般体系结构图1 3 所示 1 4 】。 1 ，5 关联规则发现的研究工作 关联规则挖掘目的是寻找在大量的数据项中隐藏着的联系或者相关性。当积累 了越来越多的数据时，他们变得对这些数据中隐含着的联系很有兴趣。发现这些有 趣的关联能帮助他们做出决策( 比如市场分析、信用卡风险鉴别、网络故障诊断、 天体识剐、基因的相似性分析等等) 。 华中科技大学硕士学位论文 用户界面 0 p e n a p i 关 分f 序列 聚 联i 类l 模式i 类 规 1 分1 分析1 分 则l 析li 析 知识库 o d b c 或其它数据库接口 数 据 仓 库 数 据 库 其 它 数 据 源 图1 3 数据挖掘的体系结构 我们将在2 1 节中给出关联规则挖掘的形式化定义。1 9 9 3 年，a g r a w a l 提出了 关联规则的概念，且提出了关联规则的挖掘可以分为两个步骤：第一步是找出数据 库中的所有频繁项目集的集合及其支持度；第二步是通过第一步所得到的频繁项目 集的信息来生成所有的关联规则。其后的研究绝大多数也遵循这两个步骤。又因为 第二个步骤计算量相对非常小，因为它不需要到数据库中去读取信息，所以关联规 则挖掘研究的重点就放在了第一个步骤上，即查找数据库中的所有频繁项目集及其 支持度。在3 1 节给出了扩展模型的定义，扩展模型参见文献 1 5 1 7 。 查找频繁项目集按策略来说可分为三大类，即经典的、基于精简集( c o n d e n s e d r e p r e s e n t a t i o n ) 的和基于最大频繁项目集( m a x i m a lf r e q u e n ti t e m s e t ) 的。 经典的方法查找频繁项目集集合的全集。这其中，广度优先搜索策略的典型代 表是a p r i o r i 算法【】”，它也是最经典最有影响力的算法。深度优先搜索策略的典型 代表是f p g r o w t h 算法l 】。这两类算法各有优缺点。 与经典的方法不同，基于精简集的方法并不查找频集项目集的全集，而是查找 华中科技大学硕士学位论文 它的一个称为精简集的子集。可以利用这个子集再生出完整的频繁项目集的全集及 其支持度来。理想的精简集应该远小于整个频繁项目集集合，这样就可以极大地提 高挖掘的效率。已知的精简集包括c l o s e d 集、f r e e 集、d i s j u n c t j o n f r e e 集、n d i 等。 基于最大频繁项目集的方法与前面两者都不同，它查找最大频繁项目集的集合。 所谓最大频繁项目集，指的是它本身是频繁项目集，但它的任何一个超集都不是。 根据 1 8 中提出的著名的反单调性质：频繁项目集的任何子集都是频繁项目集。最 大频繁项目集集合的每一个元素的所有子集的集合的并集就是完整的频繁项目集集 合，但这还不能求出每一个频繁项目集的支持度，还需要对数据库额外做一趟扫描 以求出每一个频繁项目集的支持度，这一趟扫接通常很花时间。 不管是查找完整的频繁项目集集合，还是精简集，还是最大频繁项目集集合， 都存在算法的效率问题。有许多方法已被提出用来加速关联规则挖掘的算法。这包 括从减少数据库的扫描趟数入手的p a r t i t i o n 算法，d i c 算法川等，从候选集剪枝 入手的d h p 算法，主要的还有增量式挖掘算法f u p 23 1 ，并行挖掘算法【2 “，抽样挖 掘算法f ”1 。这些方法极大地提高了关联规则算法挖掘的效率。 随着应用领域要求的不同，关联规则有不少变种。可以大致将它们分为两类。 一类是从扩展关联规则的形式出发，增强关联规则的描述能力。1 9 9 5 年a g r a w a l 和 s r i k a n t 提出的序列模式挖掘、1 9 9 5 年k e p e r s k 与h a n 提出的挖掘空间关联规则、 1 9 9 7 年m a n n i a l 等提出的e s p i s o d e s 挖掘、1 9 9 8 年o z d e n 等提出的挖掘有环关联规 则、1 9 9 8 年s a v a s e r e 等挖掘否定的关联规则【2 6 】、1 9 9 8 年l u 等提出的挖掘事务间关 联规则和日历购物篮分析、1 9 9 8 年b a y a r d o 提出的最大模式的挖掘等扩展模型。另 一类是从提出新的兴趣度量标准出发，更好地表达用户的兴趣所在，如采用模板 ( t e m p l a t e ) 算法刚等，我们在后面有专门介绍。这些变种增强了关联规则的描述 能力，拓广了关联规则的应用领域。 对关联规则的研究还包括更好的结果表达方式( 如可视化) ，在关联规则挖掘中 保护数据的隐密以保护用户的隐私，给用户提供更多的交互机制等等。 华中科技大学硕士学位论文 ! = = ! = = ! ! = = = = = = = = = = = = 2 = = ；= = = = = = = = = = = = = = ； 16 本文的组织结构 本文的组织如下： 在第一章中，我们讨论数据挖掘的背景、意义、应用范围和国内外的研究概况； 第二章介绍经典的关联规则算法a p r i o r i 和f p g r o w t h ：针对经典算法的不足，介绍 了几种较为有影响的关联规则的改进算法，如p a r t i t i o n 算法，d i c 算法和d h p 算法； 第三章讲述了带否定关联规则的出现以及目前的研究状况，更重要的是提出了挖掘 否定关联规则的算法c a 和1 n a ，以及i n a 算法在多维多值属性的数据库中挖掘否 定项的应用；第四章根据实验结果对上面的算法进行了分析和比较，更深刻的论述 了算法的优点和缺点；第五章对本文所讲述的内容进行了简单的小结，并对在今后 要做的工作进行了展望。 1 7 小结 今天，人们已经拥有了大量的数据，迫切希望将这些数据转化为有用的知识和 信息。在这样的背景下产生了数据挖掘这个新兴学科并迅速成为信息科学中的热门 研究领域，受到广泛的关注。数据挖掘的结果( 即挖掘所获得的知识) 能使用在如 商业管理、市场分析，工程设计和科学探索等各个领域。关联规则作为数据挖掘的 一个重要方法，在决策支持中体现了重要的价值。 华中科技大学硕士学位论文 2 1 关联规则的定义 2 关联规则挖掘算法 设i = ( i ，i ：，i 。) 是项的集合，其中的元素称为项( i t e m ) 。记d 为交易 ( t r a n s a c t i o n ) t 的集合。这里交易，是项的集合，并且丁，。对应每一个交易有 唯一的标识，如交易号，记作t i d 。设z 是一个项的集合z 1 ，如果z t ，那 么称交易r 包含x 。记t ( x ) 为包含x 的交易r 的集合。项集z 的支持度是包含工的 交易数与所有交易数之比，记为s u p ( x ) ，即s u p ( x ) = t ( x ) i l d i 。 一个关联规则是形如z j y 的蕴涵式，这里x c l ，y 仁i ，并且x n y ：中。 规则jy 在交易集d 中的支持度( s u p p o r t ) 是交易集中包含j 和y 的交易数与 所有交易数之比，记为s u p ( x jy ) ，即s u p ( x y ) = s u p ( x u n 。规则并y 在交 易集中的可信度( c o n f i d e n c e ) 是指包含z 和，的交易数与包含z 的交易数之比， 记为c o n f 瞵jy ) ，即c o n f ( x j y ) = s u p ( x u y ) s u p ( x ) 。 给定一个交易集d ，关联规则的发现就是产生支持度和可信度分别大于用户给 定的晟小支持度( m i i l s u p p ) 和最小可信度( m i n c o n o 的关联规则。同时满足最小支持度 阈值和最小可信度阈值的规则成为强规则。可信度和支持度是最常用的挖掘关联规 则的度量模式，在文献 1 5 1 6 中，分别采用其它的兴趣度模式，改变兴趣度模式是 一种广义的关联规则模型。 2 2 两种经典的关联规则挖掘算法 2 21 a p r i o r i 算法 最著名最经典的是a g r a w a l & s r i k a n t1 9 9 4 提出的种布尔型数据的关联规则挖 掘算法一a p r i o r i 算法，该算法将关联规则的发现分为两步：第一步是识别所有的频 华中科技大学硕士学位论文 繁项集，即支持度不小于用户指定的最小支持度的项集，第二步从频繁项集中构造 其置信度不低于用户给定置信度的规则。 算法流程如下： c k ：c a n d i d a t e i t e m s e to fs i z ek l k ：f r e q u e n t i t e m s e to fs i z ek l 1 = f i n d _ f r e q u e n t j 。i t e m s e t s ( d ) ； f o f ( k = 2 ；l k i ! = o ；k + + ) c k 2 a p r i o f i g e n ( l k 1 ，m i ns u p ) ； f o re a c ht r a n s a c t i o nt d s c a ndf o rc o u n t s c l = s u b s e t ( c k ，t ) ；g e t t h es u b s e t s o f t t h a t a r ec a n d i d a t e s f o re a c hc a n d i d a t ec c c c o u n t + + ： ) k = c c kl c c o u n t m i n _ s u p ) r e t u r n u k ； p r o c e d u r ea p r i o r i _ g e n ( l k i ，m i n _ _ s u p ) f f o re a c hi t e m s e ti t l k 1 f o re a c hi t e m s e t1 2 l k 一1 i f ( 1 t 1 1 = 1 2 1 1 ) a ( 1 1 2 1 = 1 2 1 2 1 ) a a ( 1 1 k - 2 = 1 2 k - 2 ) a ( 1 t k l 】 1 2 k 1 1 ) t h e n ( c = l l 阅1 2 ； i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，l k - i ) t h e n d e l e t ec ； e l s e a d dc t o c k ； ) r e t u r n c k ； ) 华中科技大学硕士学位论文 p r o c e d u r eh a s i n f r e q u e n ts u b s e t ( c ，l k i i ) f o re a c h ( k 1 ) 一s u b s e tso f c i f s 仨l k 1 t h e n r e t u r nt r u e ： e l s e r e r u r nf a l s e ； 下面我们来看a p r i o r i 算法是如何从长度为k 的频繁项目集中生成长度为( k + 1 ) 的候选项目集的，产生候选集主要分为两步：连接与剪枝。 1 ) 连接步：为找l ，通过l k 自连接产生候选k + l 一项集的集合。该候选项集 的集合记作c k 十i 。例如l i l 并l il t i l 是l k 中的项集，记l 口 表示第j 项。为方便计，假定 事务或项集中的项按字典次序排序。执行l k 与k 自连接，如果其中两个元素的前( k 1 ) 个项相同，那么这两个l k 的元素是可连接的。按照字典次序排序，是简单地保 证不产生重复。 2 ) 剪枝步：c k 是l k 的超集，也就是说，c k 的成员可以是也可以不是频集的， 但所有的频集k 一项集都包含在c k 中。扫描数据库，确定c k 中每个候选的计数。从 而确定l k ( 即根据定义，计数值不小于最小支持度计数的所有候选是频繁的，属于 l k ) 。然而，c k 可能很大，这样所涉及的计算量就很大，为压缩c k ，可以使用a p r i o r i 的反单调性：任何非频繁的( k - 1 ) 一项集都不可能是频繁k 一项集的子集。因此，如 果一个候选k 一项集的( k 1 ) 一项子集不在lk 1 中，则该候选也不可能是频繁的，从 而可以从c k 中删除。 例如：l 1 = a b c ，a b d ，a c d ，a c e ，b c d ) ，a b c d = a b c + a b d ，a c d e 一m i n s u p ； a n s w e r = l g ； p r o c e d u r e g e n _ l a r g e _ i t e m s e t s ( p ：d a t e b a s ep a r t i t i o n ) 2 n 华中科技大学硕士学位论文 四= l a r g e1 - i t e m s e t sa l o n gw i t ht h e i rt i d l i s t s ； f o r ( k = 2 ；e 巾；k + + ) d ob e g i n f o r a l li t e m s e t st i 噩1d ob e g i n f o r a l li t e m s e t sh 噩一 d ob e g i n i f i i 【1 卜1 2 1 1 八1 1 2 】1 2 1 2 】 a l l k 一1 m i a s u pt h e n e = 珲u c ； e n d e n d e n d r e t u r nuk 皿 在p a r t i t i o n 算法中，由于每个子数据库可放入内存，所以i o 操作比较少，算法 总体执行速度比较快。但在数据库庞大时，子数据库数目增大，p a r t i t i o n 算法生成的 无效候选频繁项集数目快速增长，导致效率降低。p a r t i