（计算机应用技术专业论文）基于闭模式的关联规则产生算法研究.pdf

江苏大学硕士研究生学位论文 摘要 数据挖掘技术是数据库和人工智能领域研究的热点课题，被用来发现大量数 据中隐含的有用的知识；而用于描述多个数据项之间的相关性的关联规则挖掘则 是数据挖掘应用中的一个重要组成部分，关联规则揭示的信息广泛应用在市场分 析和商业决策之中。 与使用频繁模式相比较，使用频繁闭模式来产生关联规则具有很大的优势， 民前已经出现了缀多挖掘闭模式的算法，然露这些算法仍然存在着一些润题：产 生的关联规则数量较多，不方便用户理解和使用；挖掘过程中需要保存数据副本 或中间结果，内存开销较大；算法中存在着大量冗余的、无效的操作，执行效率 较低等。本文针对上述i 闻题，对基于频繁闭模式的关联规则挖掘算法进行了深入 的研究。 首先简要说明关联规则挖掘的相关概念和分类：其次介绍f c a ( f o r m a l c o n c e p ta n a l y s i s ) 在关联规则挖掘中的应用，分析了使焉i c e b e r g 概念格从频繁闭 模式产生有限关联规则的方法，利用此类方法得到的这些有限关联规则可以准确 地描述出项目集之间的关联关系，并且数量很少；然后在c l o s e t 算法的基础上， 提出了一种新的高效挖掘频繁闭模式的算法f c i m 。该算法使用频繁模式树来保 存需要挖掘的数据集，采用“分两治之 的策略、按照深度优先的顺序进行挖掘， 在挖掘过程中使用相等子节点保存已挖掘到的频繁闭模式的信息，保证抽取到的 每一个局部频繁闭模式一定都是全局闭合的，可以直接输感到外部文件，减少了 大量的冗余操作和内存空间占用，使算法获得较好的可伸缩性；同时提出了二种 优化操作，利用当前获取的信息进行分析预测，尽可能早地抽取出频繁闭模式， 从而使f c i m 算法获得很高的运行效率；最后给出算法的伪代码描述和运行示铡。 试验结果表明，f c i m 算法能够得到正确的结果；并且与c l o s e t + 算法相比， f c i m 算法具有更高的挖掘效率和良好的可伸缩性，证明该算法是切实有效的。 关键词：数据挖掘，关联规则，闭模式，频繁模式树，概念格 江苏大学硕士研究生学位论文 a b s t r a c t d a t am i n i n gi sah o tr e s e a r c ht o p i ci nd a t a b a s ea n da r t i f i c i a li n t e l l i g e n c ef i e l d st o f i n dt h eu s e f u lk n o w l e d g eh i d d e ni nt h ev a s td a t a a s s o c i a t i o nr u l e sa r ea ni m p o r t a n t p a r to fd a t am i n i n g ，w h i c hc o u l dd e s c r i b et h er e l a t i o n s h i p sb e t w e e n m u l t ii t e m st h a t m a yb eu s e f u li nm a r k e ta n a l y s i sa n db u s i n e s sd e c i s i o n - m a k i n g m i n i n gd o s e dp a t t e r n sc a np r o d u c em u c hs m a l l e re q u i v a l e n tr e s u l ts e t st h a n m i n i n gf r e q u e n tp a t t e r n s n o w ，t h e r eh a v eb e e nm a n ya l g o r i t h m st om i n i n gf r e q u e n t c l o s e dp a a e r n s b u tt h e yc a n tp r o v i d eab e s ta p p r o a c ht om i n i n gd o s e dp a r e m s t h e ym u s tc o u s e r v et h ed o s e dp a t t e r n si nm e m o r yo rt r a v e r s et h e d i l l - s e ta n d c o m p u t et h ec l o s u r er e l a t i o n ，s 0t h e y c a n tg e tt h eh 谫e f f i c i e n c ya n dg o o ds c a l a b i l i t y t h en u m b e ro fp r o d u c e dr u l e si sv e r yl a r g e ，a n dm a n yo ft h e ma r eu s e l e s st ou s e r s i n o r d e rt or e s o l v et h e s ep r o b l e m s ，w ed os o m er e s e a r c h e so na s s o c i a t i o nr u l e sm i n i n g b a s e do nc l o s e dp a t t e r n s t h i sp a p e rf i r s ti n t r o d u c e ss o m et h e o r yk n o w l e d g e ，s u c h 弱t h eb a c k g r o u n d k n o w l e d g eo fd a t am i n i n ga n da s s o c i a t i o nr u l e s n e x tw ei n t e r p r e tt h ed e f i n i t i o no f d o s e dp a t t e r n sw h i c hp r o v i d eam i n i m a lr e p r e s e n t a t i o no fi t e m s e t sw i t h o u tl o s i n g s u p p o r ti n f o r m a t i o n a f t e rt h a t ，b a s e do nt h et h e o r e t i c a l f r a m e w o r ko ff o r m a l c o n c e p ta n a l y s i sa n di c e b e r gc o n c e p tl a t t i c e ，w ed i s c u s sh o w t oe x t r a c tr e l a t i v e l y s m a l lb a s e sf o ra s s o c i a t i o nr u l e sf r o mw h i c ha l lr u l e sc a nb ed e d u c e d t h e n ，an e w a l g o r i t h mf o rm i n i n gf r e q u e n tc l o s e dp a r e m sb a s e do i lf r e q u e n tp a t t e r nt r e e ，f c i m a l g o r i t h mi sp r e s e n t e d t h ea l g o r i t h mi si na c c o r d a n c ew i t ht h ed i v i d e a n d - c o n q u e r m e t h o d w ea d v a n c eac o n c e p to fe q u a l c h i l di nt h ea l g o r i t h m ，w i t hi tw ec o u l d u t i l i z et h ef o r e g o n ei n f o r m a t i o nt or e d u c er e d u n d a n tc o m p l i c a t e do p e r a t i o n s a c c o r d i n gt ot h eo r d e rf r o mb o t t o mt ot o p ，a n dt h e nf m do u te v e r yf r e q u e n td o s e d p a t t e mw i t h o u td u p l i c a t e sg e n e r a t i o na n dm e m o r yc o n s e r v a t i o n w ea l s ot a k et w o m e a s u r e st op r e d i c ta n de x t r a c tt h ec l o s e dp a t t e r n s 嬲s o o n 勰p o s s i b l e i th e l p st o s o l v ean u m b e ro fp r o b l e m st h a te x i s ti nt h ec u r r e n ta l g o r i t h m s ，s u c h 弱h i g hm e m o r y 江苏大学硕士研究生学位论文 r e q u e s t ，r e p e t i t i o u si oa c 嬲s s i n g ，a n ds oo n a tl a s t , w ed e s c r i b eo u ra l g o r i t h ma n d l i s ta ne x a m p l e t h ee x p e r i m e n t s p r o v et h ec o r r e c t n e s sa n dt h eb e t t e rp e r f o r m a n c eo ft h i s a l g o r i t h m a f t e rc o m p a r i s o nw i t hc l o s e t + a n da n a l y s i si no u re x p e r i m e n t s ，w ec a n c o n c l u d et h a tt h ea l g o r i t h mi se f f i c i e n ta n dp r a c t i c a l 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 , c l o s e dp a t t e r n ，f r e q u e n tp a t t e r nt r e e ， c o n c e p t l a t t i c e 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密函 学位论文作者签名：杏世松 叫年i 乙月i e l 指导教师签名名l 忾芍 堋年从月阳 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：专苗极 日期：吲年i - 月i e l 江苏大学硕士研究生学位论文 i 1 研究背景 第一章绪论 随着数据库技术的迅速发震以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。嚣前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了 “数据爆炸但知识贫乏”的现象，人们迫切需要解决快速增长的数据量与网益频繁 却难以发现的隐性知识之间的矛盾。数据挖掘技术正是在这种背景下应运而生 的，它使人们最终有簏力认识到数据的真正价值，即蕴藏在数据中的信怠和知识。 数据挖掘通过预测未来趋势及行为，做出基于知识的决策，图前广泛应用于 银行、电信、保险、交通、零售( 如超级市场) 等商业领域，它所能解决的典型 商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e r s e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉销售 ( c r o s s - s e l l i n g ) 等市场分析行为，以及客户流失性分析f e 飘舶臣a n a l y s i s ) 、客户 信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等【1 1 。 1 。2 研究现状 作为一门处理数据的新兴技术，数据挖撅是许多学科的交叉，运用了统计学、 计算机、数学等学科的知识，这些学科的成熟与发展不断推动了数据挖掘技术的 进步。当前数据挖掘的研究焦点主要集中在以下凡个方面1 2 1 ：( 1 ) 发现语言的形式 化描述，即研究专门用予知识发现的数据挖掘语言；伫) 研究在网络环境下的数 据挖掘技术( w e bm i n i n g ) ；( 3 ) 寻求数据挖掘过程中的可视化方法，使知识发现的 过程能被用户理解；鳓寻求高效的、可伸缩性良好的挖掘算法等。 目前世界上比较有影响的典型数据挖掘系统包括：s a s 公司的e n t e r p r i s e m i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、o r a c l e 公司的d a r w i n 、h n c 公司的d a t a b a s e m i n i n gw o r k s t a t i o n 、s g i 公司的s e t m i n e r 、s p s s 公司的c l e m e n t i n e 、a n g o s s 公 司的k n o w l e d g es e e k e r 和k n o w l e d g es t u d i o 、s y b a s c 公司的w a r e h o u s es t u d i o ， 此外还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、 q u e s t 等【3 j 1 4 j 。 江苏大学硕士研究生学位论文 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要包括五类功 能：自动预测趋势和行为、关联分析、聚类、概念描述和偏差检测等【5 1 。其中关 联分析是数据挖掘的一个重要组成部分，通过关联分析发现的关联规则在指导企 业进行商务决策等方面具有重要意义。1 9 9 3 年a g r a w a l 等人最先对挖掘顾客交 易数据库中项目集之间的关联规则问题进行了研究，并提出了a p r i o r i 算法1 6 1 。 以后诸多的研究人员对关联规则的挖掘问题进行了大量的研列7 】【8 】，但是使用频 繁模式抽取到的关联规则的数量往往大得惊人，难以理解与运用【9 1 ，这个问题直 到1 9 9 9 年p a s q u i e r 等人提出闭模式( c l o s e dp a t t e r n ) 的概念1 1 0 】后，才获得了较 好的解决。当前已有的基于频繁闭模式的关联规则挖掘算法主要包括：1 9 9 9 年 p a s q u i e r 等人提出的a - c l o s e 算法【1 0 】；2 0 0 0 年p e i 等人提出c l o s e t 算法【1 1 】；2 0 0 1 年b u r d i c k 等人提出深度优先搜索算法m a f i a 1 2 】；2 0 0 2 年z a k i 等人提出的 c h a r m 算法【1 3 】；t i t a n i c 算法( s t u m m e 等。2 0 0 2 ) i x 4 ；2 0 0 3 年w a n g 等人于又提 出对c l o s e t 算法改进的c l o s e t + 算法f 1 5 】；2 0 0 4 年u n o 等人提出的l c m 算 法【1 6 】；d c i c l o s e d 算法【1 7 1 ( l u c c h e s e 等，2 0 0 4 ) ；2 0 0 5 年h a m r o u n i 等人又提出了 p r i n c e 算法【1 8 1 等。 1 3 论文研究内容 目前的这些算法仍然存在着一些问题，以常用的c l o s e t 算法为例，它主要 存在如下的缺点：产生的关联规则的数量仍然较多，不方便用户理解和使用；挖 掘过程中需要保存数据副本或中间结果，内存开销较大，在最小支持度较低时无 法正常运行；挖掘频繁闭模式是一项耗时的工作，算法中又存在着大量冗余的、 无效的操作，导致算法的执行效率不高等。本文对以上的这些问题进行分析和研 究，然后提出解决方法，具体工作包括： ( 1 ) 解释利用概念格抽取有限关联规则的方法。 介绍f c a ( f o r m a lc o n c e p ta n a l y s i s ) 在关联规则挖掘中的应用，分析了使 用i c e b e r g 概念格从频繁闭模式产生有限关联规则的方法，利用此类方法得到的这 些有限关联规则可以准确地描述出项目集之间的关联关系，并且数量很少，方便 用户的分析和使用。 ( 2 ) 提出一种新的闭模式挖掘算法f c i m 。 采用“分而治之 的策略进行频繁闭模式的挖掘时，主要思想是通过不断划 分搜索空间，在子空间中抽取局部频繁闭模式，进而获得所有的全局频繁闭模式； 缺点是需要检查抽取到的局部频繁闭模式是否具有全局闭合性，这种检查操作一 般需要与已挖掘到的全局频繁闭模式进行比较，判断是否存在与当前频繁闭模式 2 江苏大学硕士研究生学位论文 具有相同支持度的超集，因而代价非常高，并且需要保存之前挖掘到的中间结果。 本文提出了一种解决方法：在采用自下而上的顺序进行挖掘时，能够证明与局部 频繁闭模式具有相同支持度的全局频繁闭模式一定在此之前已经被挖掘到；利用 这个性质在算法执行过程中使用附加的节点来保存这些信息，这样在子空间中抽 取局部频繁闭模式时先进行判断，如果具有附加节点则直接进行剪枝，根本不用 产生这些多余的频繁闭模式，从而保证抽取到的每一个局部频繁闭模式一定都是 全局闭合的，可以直接输出到外部文件。这样既减少了空间占用，又不需要进行 复杂的判断操作，从而消除大量的冗余操作。另外，在挖掘过程中提出了二种优 化操作，利用当前挖掘出的信息进行分析预测，尽可能早地抽取出频繁闭模式， 这样就减少了构造条件频繁模式树的代价，提高了算法的执行效率。我们的试验 结果表明，与c l o s e t 算法的改进算法c l o s e t + 相比，f c i m 算法具有更高的运 行效率和良好的可伸缩性。 1 4 论文组织结构 论文共分五章，主要内容概要如下： 第一章绪论：介绍了本文的研究背景和国内外的研究现状，说明本文的研 究内容和论文的组织结构。 第二章基本理论及常用算法：首先阐述数据挖掘的概念、过程和分类；介 绍有关关联规则的基本理论知识，并以关联规则挖掘中的两个经典算法( a p r i o r i 和f p g r o w t h 算法) 为例，说明关联规则挖掘的传统方法；然后给出闭模式的定 义，指出采用闭模式进行关联规则挖掘的优点，最后说明如何利用频繁闭模式产 生有限的关联规则，其中重点介绍概念格的定义并详细描述了通过概念格得到有 限关联规则的方法。 第三章f c i m 算法：说明算法的理论基础和执行过程中可以执行的二种优化 操作，并阐述利用相等子节点保存已挖掘到的频繁闭模式信息的方法，说明了利 用该算法进行频繁闭模式挖掘的详细方法和步骤，最后给出算法的伪代码描述。 第四章试验与结果分析：通过试验来对算法进行验证，首先利用在各个数 据集中挖掘到的频繁闭模式及其数量来验证算法的正确性；然后与c l o s e t + 算 法在不同类型的数据集中的运行效率进行对比，从而证明f c i m 算法的有效性和 可行性。 第五章总结与展望：对本文的研究工作进行归纳和总结，探讨进一步的研 究方向。 3 江苏大学硕士研究生学位论文 第二章基本理论及常用算法 2 1数据挖掘的概念和应用 2 1 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 指的是从数据库或数据仓库中提取人们感兴趣的知 识，这些知识是隐含的、事先未知的、潜在的有用信息。这个定义包括以下含义： 数据源必须是真实的、大量的；发现的是用户感兴趣的知识；发现的知识要可接 受、可理解、可运用，最好能用自然语言表达【1 9 1 。 从商业角度看，数据挖掘是一种新的商业信息处理技术，其主要特点是对商 业数据库中的大量业务数据进行抽取、转换、分析和其它模型化处理，从中提取 辅助商业决策的关键性数据【加1 。 一 2 1 2 数据挖掘的分类 数据挖掘是个多学科交叉的研究领域，它受到包括数据库、统计学、机器学 习、可视化和信息学等多学科的影响，因此分类的方法很多，主要有以下几种【2 1 】： ( 1 ) 根据挖掘的任务分类：分类或预测模型发现、数据总结与聚类发现、关 联规则发现、序列模式发现、相似模式发现、异常和趋势发现等。 ( 2 ) 根据挖掘的对象分类：关系型数据库挖掘、面向对象数据库挖掘、空间 数据库挖掘、时序数据库挖掘、文本数据源挖掘、多媒体数据库挖掘、异质数据 库挖掘、w e b 数据挖掘等。 p ) 根据挖掘的方法分类：机器学习方法、统计方法、聚类分析方法、神经 网络方法、遗传算法方法、数据库方法、粗糙集方法等 ( 4 ) 根据数据挖掘所能发现的知识分类：挖掘广义型知识、挖掘差异型知识、 挖掘关联型知识、挖掘预测型知识、挖掘异常型知识、挖掘不确定性知识等。 以上的分类从不同的角度刻画了数据挖掘研究的策略和范畴，它们是互相补 充和交叉的。 2 1 3 数据挖掘的主要步骤 数据挖掘的主要步骤如下【2 2 】： ( 1 ) 问题定义 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种 知识就成为整个过程中第一个也是最重要的阶段。在问题定义的过程中，一方面 4 江苏大学硕士研究生学位论文 明确实际工作对数据挖掘的要求，另一方面通过对各种学习算法的对比来确定可 用的学习算法。 ( 2 ) 数据准备 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。 数据选取的目的是确定发现任务的操作对象，是根据用户的需要从原始数据 库中抽取一组数据；数据预处理一般包括消除噪声、推导缺失值、消除重复记录、 完成数据类型的转换等；数据变换的主要目的是消减数据的维数，即从初始特征 中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数【2 1 1 。 ( 3 ) 数据挖掘 它是数据挖掘算法的执行阶段，首先根据对问题的定义明确挖掘的任务或者 目的，如分类、聚类、关联规则发现或序列模式发现等【2 1 1 。确定了挖掘任务后， 就要决定使用什么样的算法。 ( 4 ) 结果解释和评估 数据挖掘的结果有些是有实际意义的，而有些是没有意义的，或是与实际情 况相违背的，这就需要对结果进行评估。评估可以根据用户多年的经验，也可以 直接用实际数据来验证模型的正确性，进而调整挖掘模型，不断重复数据挖掘和 模型构建过程。 ( 5 ) 分析决策 数据挖掘的最终目的是辅助决策，决策者可以根据数据挖掘的结果，结合实 际情况，调整竞争策略等。 以上的步骤不是一次完成的，可能其中某些步骤或者全部要反复进行，才有 可能达到预期的效果。 2 2 关联规则 典型的关联规则挖掘应用，是发现交易数据库中不同商品( 项) 之间的联系， 这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响等。 例如，“9 0 的顾客在购买面包和黄油的同时也会购买牛奶，其直观的意义是， 顾客在购买某些东西的时候有多大的倾向也会购买另外一些东西( 可信度) ，发 现这样的规则可以应用于商品货架设计把顾客经常同时买的商品摆放在一起) 、 库存安排( 按一定比例互相搭配进货) 以及根据购买模式对用户进行分类，对于 确定市场策略是很有价值的。可以看出，关联规则是描述事件之间同时出现的规 律的知识模式，其目的是为了描述隐藏在数据间的相互关系【矧。 5 江苏大学硕士研究生学位论文 2 2 1 关联规则的相关定义 设i = i 1 ，i 2 ，i m 是由不同项目( i t e m ) 构成的集合，记d 为交易事务 ( t r a n s a c t i o n ) t 的集合，其中事务t 是项目的集合称为项目集( i t e m s e t ) ，并且匹i 。 对应每一个事务有唯一的标识，记作t i d ，如事务编号。设x 是一个项目集，如 果x g t ，则称事务t 包含了项目集x ；项集x 的支持度计数可以表示为 o ( x ) 爿口ix 呈t ，t d i ，i i 表示集合中元素的个数。 定义2 1 设x 是一个项目集，若其中含有k 个项目，则称其为k _ 项目集。 定义2 - 2 一个项目集x 的支持度( s u p p o n ) 为数据集d 中包含x 的事务数量与 数据集d 的总事务数量之比，记为刚p 岱户三掣。 i u l 定义2 - 3 如果一个项目集x 在d 中的支持度s u p ( x ) 大于等于用户指定的最小 支持度( 记为m i ns u p ) ，则此项目集为频繁项目集或频繁模式；否则为非频繁项 目集或非频繁模式。 定义2 _ 4 一个关联规则蕴涵式是形如x _ y 的式子，其中x c i ，y c i 且有 x m y = o 。x 称为规则的前项( 或左项) ，y 称为规则的后项( 或右项) 。 关联规则一般采用支持度、可信度作为挖掘的指标，其中支持度是指规则所 包含的项的集合在事务数据集出现的概率，可信度是指在规则前项发生的情况下 后项发生的条件概率。 定义2 - s 规则x y 在数据库d 中的支持度是指项目集xuy 的支持度，即 s u p ( x _ y ) = s u p ( xu 。 定义2 6 规则x _ y 在数据库d 中的可信度( c o n f i d e n c e ) ：是指包含x 和y 的交易 数与包含x 的交易数之比，记为c o 螂寸2 笔半2 等。 给定一个交易数据库d ，关联规则挖掘的目标就是产生支持度和可信度分别 大于等于用户给定的最小支持度( m i n _ s u p ) i 和最小可信度( m 砸c o n 9 的规则。 2 2 2 关联规则的分类 根据关联规则挖掘的不同特征，可以对关联规则进行不同的分类： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段 进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型 6 江苏大学硕士研究生学位论文 关联规则中也可以包含种类变量。例如：性别= “女 呻职业= “秘书，是布 尔型关联规则；性别= “女”一a v g ( 收a ) = 2 3 0 0 ，涉及的收入是数值类型，所以 是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层关联规则中，所有器变量都没有考虑至l 现实的数据是具有多个不同的 层次的；在多层关联规则中，对数据的多层性已经进行了充分的考虑。例如：m m 台式机- s o n y 打印机，是一个细节数据上的单层关联规则；台式机- - - s o n y 打 印机，是一个较高层次和细节层次之闻的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多 维关联规则。 在单维关联规则中，只涉及到数据的一个维，如用户购买的物品；在多维关 联规则中，簧处理的数据将会涉及多个维。例如：啤酒一尿布，这条规则只涉及 到用户的购买的物熙；性别= “女”一职业= “秘书 ，这条规则就涉及到两个 字段的信息，是两个维上的一条关联规则。 国基予约束( c o n s r a i n t - b a s e d ) 的挖掘，具体约束的内容可以有： i ) 数据约束，可以指定对哪些数据进行挖掘，而不一定是全部的数据； i 埝指定挖掘的维和层次，可以指定对数据哪些维以及这些维上的哪些层次 进行挖掘； i i i ) 规则约束，可以指定哪些类型的规则是用户所需要的。引入一个模板 ( t e m p l a t e ) 的概念，用户使用模板来判断哪些规则是令人感兴趣的规则，哪些 规则不是。 2 3 基于频繁模式的关联规则挖掘 基于频繁模式的关联规则挖掘可以分解成以下两个子闻题l 碉：娃找出数据 库d 中所有满足用户指定的最小支持度的项目集。( 2 ) 利用频繁项目集生成所需要 的关联规则：对于每一个频繁项目集a ，找出a 的所有非空子集a ，如果 s u p ( a ) s u p ( a ) m i n c o n f ，就生成关联规则氇呻( 矗一a ) 。下面通过几个常用算法 来说明解决这两个子问题的方法。 2 3 1 频繁模式挖掘算法 2 3 1 1a p t i o r i 算法 a p r i o d 算法是频繁项目集生成的一个经典算法，本节主要讨论算法的第一步 7 江苏大学硕士研究生学位论文 即抽取频繁模式的问题，首先引入以下的定义和定理。 定理2 1 如果一个项瞪集x 是频繁项目集，则x 的所有子集一定也都是频繁 项目集。 设 c d ，e 是一个项目集，因为任何包含 c ，d ，e ) 的事务一定也包含它的子集 扔田， c e ， d ，e ， e ，擘 和 e ，所以翔采 c ，d ，e 是频繁项是集，则它的 所有子集一定也是频繁项目集。 相反地，如果项目集 a ，b 不是频繁项目集，则它的所有超集一定也是非频 繁的。所以一旦确定 a ，b 是非频繁的，那么在挖掘频繁项目集时，所有包含 a ，b 的项目集都应该直接被剪枝。这种剪枝策略称为基于支持度的剪枝，产生该策略 的原因是支持度指标具有的一种性质：任何项麓集的支持度都不可能超过它的超 集的支持度，这种性质称为支持度指标的反单调性( a n t i 。m o n o t o n ep r o p e r r y ) 。 定义2 7 设l 是一个由多个项酱构成的集合，j = 2 1 是i 的幂集q o w e fs e t ) ，如果 有v x , y j ：僻的_ ，g ) ，则称指标f 是单调的或向上封闭的( u p w a r d d o s e d ) 。 该定义说明：如果x 是y 的一个子集，则印q 一定不会大于f m 。同理，如果 v x ，y 蒜歹：g y ) ，卿f ( x ) ，称指标堤反单调的或向下封闭的( d o w n w a r d d o s e d ) ，这时的指标f 表明：如果x 是y 的一个子集，则f 定不会大于 c ) 。 设c k 表示候选k 项集构成的集合，巩表示频繁k _ 项集构成的集合，则a 0 r i o r i 算法的执行过程描述如下： 首先对数据集进行一次扫描来确定各个项目的支持度，此步完成后得到 所有的频繁1 。项集鹣。 利用上次循环中得到的频繁( k - 1 1 。项集来产生新的候选k 一项集。 为了计算候选集的支持度，算法需要重新扫描数据集。该子函数用来确 定q 中所有包含在每一个事务中的的候选集。该过程一般通过哈希树来 实现，具体方法可以参考文献，本文不再详细描述。 计算得到支持度赢，消除所有支持度小于给定最小支持度的候选集。 执行过程中如果没有产生新的频繁项目集( r p f k = o 时) ，则算法终止。 下面分析a p f i o 矗算法的性能嘲： ( 1 ) 产生1 频繁项目集：对于每一个事务，需要更新该事务所包含的各个项目 的支持度；设事务的平均长度为w ，事务的总数目为n ，该操作的时间复杂度为 q 对嘞。 ( 2 ) 产生候选集：为了产生候选k - 项集，需要对每对频繁( k - 1 ) 一项集进行合并， 以检验其中是否包含有相同的k - 2 个项爵，每个合并操作最多需要进行k - 2 次比较 8 江苏大学硕士研究生学位论文 操作。在最佳条件下，每次合并产生一个有效的l 【- 项集；在最差情况下，算法必 须两两合并之前所找到的所有频繁( k - 1 ) - 项集。因此，合并频繁项目集的操作的 总代价为： ( k - 2 ) l c k | c o s to f m e r g i n g 彩 a ( f 3 ，c ：3 ) 1 ( f 3 ，c ：3 ) la c ( f ：3 ) ( f 3 ) l c fa 囝 ( a ) p r e f i xp a t h se n d i n gi np t r e e f o r m ( d ) c ) c o n d i t i o n a lf p - t r e ef o rc m 国c o n d i t i o n a lf p - t r e ef o ra e m 图2 2 利用f p t r e e 进行频繁模式挖掘的过程图 对于项目m ，首先输出频繁模式 m ：3 ，并发现两条包含m 的路径( f 4 c ：3 ， l l 苫善f苫莹一暑 (1|o、，_ ， 、， e ， 江苏大学硕士研究生学饺论文 a ：3 ，m ：2 ) 和( f 4 ，c ：3 ，a ：3 曲：王，搬：1 ) ，注意此时不再考虑项h p ：从而可以找 到l n 的条件模式基为 2 ，c ：2 ，a ：2 ) ，( f 1 ，c ：l ，a ：l ，b ：1 ) ，从而构造描m 的条 件f p - t r e e ，如图2 - 2 ( c ) 所示，然后调用子过程对m 的条件f p - t r e e 进行挖 掘：首先输出频繁模式 a m ：3 ，并调用予过程时锄的条件f p t r e e ( 虱 2 - 2 ( d ) ) 进行挖掘；然麓输出频繁模式 c 毽：3 ，并调爰子过程对激的条件 f p 。t r e e ( 图2 - 2 ( e ) ) 进行挖掘；最后输出频繁模式 舳黻：3 。其中，在挖掘a m 的条件f p - t r e e 时，可馘得到频繁模式 c a m ：3 和 r a m ：3 ，之后还需要 挖掘c a i n 条件f p - t r e e 得到最长的频繁模式 r e a m ：3 ；同理挖掘c m 的条件 f p t r e e 时可以输岛 f c m ：3 。所以，所有包含m 的频繁模式为 m ：3 ， 鼗嫩：3 k 隧：辩， 蠡瞳：3 ， 鼹翦躲3 ， 瓢撒：3 f c a m ：3 , 受黻：3 羚。 按照同样的方法继续进行挖掘，可以得到所有的频繁模式。 f p - g r o w t h 算法l l a p r i o r i 算法大约要快一个数量缓，原因魏一f 2 6 1 ：直接生 成频繁项爨集，不生成候选集，不需要候选测试；使用压缩的数据结构，可以 显著减少存储空间，例如对于c o n n e c t 数据集，该数据集包含6 7 ，5 5 7 条事务，每条 事务包含钙个顼毯，在给定酶最小支持度y 擎5 0 的条件下，频繁顼星出现的总数 为2 ，2 1 9 ，6 0 9 ，然而在阡t r c e 中只需要1 3 , 4 4 9 个节点，比率为1 6 5 0 4 ，如果数据集 趣含的事务的宽度更大，则这个冼率可麓会受大； 避免了重复数据库扫攒； 基本操作是计数和建立f p - t r e e 。 2 3 2 关联规则产生算法 基于频繁项圈集的荚联规则产生方法蹴较简单，以a p r i o r i 算法中的关联规则 产生算法为铡，主要过糕是寻找每一个频繁顼基集的菲空子集，然辱计算抽驭刮 的规则的可信度并与最小可信度比较，从而得到满足最小支持度和可信度的全部 关联规赠矧。 2 。3 。2 。i 基于可信麦的剪鼓 对手个频繁珏顼集y ，不考虑规篓彩帅y 秘y 呻彩，总共可以产生擞2 条溉 则。产生方法是把y 分成两个非空的子集x 和y - x ，满足最小可信度的规则 x - - - y - x 就是关联规荧 j 。鬻为该烧剥是及频繁顼銎集中抽取蘸，所瑷它一定满足 最小支持度。 例2 2 设x 篙租，2 3 是频繁项目集，则根据x 可以产生6 条候选的关联规鼹 j ： 董，2 卜 3 ， 董，3 卜 2 ， 2 崎 重 ， 重 峙 2 ，3 ，鼍2 坤 圭，3 和 鼍一 圭2 。因 为每条规则的支持度都与x 的支持度相等，所以它们一定满足最小支持度。 可信凄与支持度不阚，宅不吴备任褥单调性。捌如援刘x - 峥y 静褥信度既霹 1 2 江苏大学硕士研究生学位论文 以比规则羔y 的可信度低，也可以离，甚至相等( 其中x x ，y y 。 但是，如果比较从同一个项目集y 中抽取到的规则，可以找到如下的定理。 定理2 - 2 如果规则z y x 不满足给定的最小可信度，那么对于x 的任意 子集x ，规则x 啼y x t 一定也不满足最小可信度。 证明：考虑规n x ，一y 一工和x y x ，其中z ，是x 的子集。规则的可 信度分别为拶7 拶和o - ( v ) o f x ) ，因为x 是x 的子集，有o - ( x ) o c x ) ，所 以规则x y 一盖，的可债度一定小于等于规则x 专y x 的可信度。 定理得证。 计算规则的可信度时，不用褥次扫描事务数据库。例如对于规则 l ，2 - - - - 3 ， 该规则的可信度为似 1 ，2 ，3 ) 0 ( 0 ，2 ) ，因为 l ，2 ，3 是频繁项目集，根据支持度的 反单调性， l ，2 一定也是频繁项目集，而这两个频繁项目集的支持度在产生频 繁项爨集的过程中已经找如，所以可以直接计算出规则的可信度。 2 。3 2 2 存在问题及解决方法 按照这种传统方法抽取关联规则的复杂度为d ( 尹2 | ) ，其中f 是频繁项譬集 的数日，l 是频繁项目集的最大长度。即使我们仅仪考虑具有最大长度l 的频繁 项目集，因为它的z 1 个子集都是频繁项目集，按照这种方法产生的总的关联规则 的数黧也为二( ；) 2 t - 二( ：矽= 2 7 二( ；) = 2 1 = 联2 2 7 ) 。实际应用孛很难 从这些数目庞大的规则中得到用户真正感兴趣的规则，因为其中相当一部分的规 则都是无效的、冗余的。 例2 。3 设在一个商店的事务分析中，6 0 的事务包含购买计算机游戏，7 5 的事务包含购买录像，而4 0 的事务同时购买计算机游戏和录像。设a 墨购买计 算枫游戏，b = 购买录像，则有：p ( a ) = ，p = 7 5 ，p ( aub ) = ， p ( a - - b ) = p ( a u1 3 ) = 4 0 ，c o n f ( a 哼鳓= 笔铲= 等娟溉 设最小支持度为3 0 ，最小置信度为酌，则会得到规受| ja 峥b 。似乎可以 认为，购买计算机游戏的人趋向于购买录像，购买计算机游戏的顾客越多，购买 录像的顾客也将随之增加，刺激游戏的销售量有助予增加录像的销售量，在摆放 商品的时候可以应用这条规则。然恧仔细分析却发现事实并非如此：购买了计算 机游戏的顾客有6 0 的可能性购买录像，比购买录像自身的可能性7 5 还要小。 这就说骧，一个购买了计算机游戏的顾客还要购买录像的可戆性事实上毖一个不 江苏大学硕士研究生学位论文 知道任何信息的普通顾客购买录像的可能性还要低。因此这条规则所揭示的信息 就没有价值，且具有误导性和欺骗性，它只是给定的x 、y 的条件概率的估计值， 并不能表示x 和y 之间的实际关联程度。事实上，不购买游戏的顾客购买录像 的可能性为p ( bi a ) = 璺气紫= o 8 7 5 ，比购买游戏的顾客购买录像的可 能性6 0 还要大，所以这条规则实际上是一条无效的关联规则。 为了获得有效的关联规则，目前提出了在对产生的频繁数据集和关联规则进 行分析和验证的多种验证方法。对于产生的频繁项目集，可以采用的验证指标包 括：兴趣度i n t e r e s t ( i ) ( b r i n ，1 9 9 7 ) 、c o r r e l a t i o n ( 由1 ( 相关系数) 、j a c c a r d ( c o h e n ， 2 0 0 0 ) 、c o s i n e ( i s ) 和a l l c o n f