（计算机软件与理论专业论文）交互式关联规则挖掘的研究和应用.pdf

y1 0 1 5 8 4 6 摘要 随着信息技术的飞速发展，数据爆炸和知识贫乏之间的矛盾越来越大，使 数据挖掘在许多领域所起的作用越来越重要。在数据挖掘的各分支中，关联规则 挖掘的研究最为深入和广泛。目前对关联规则挖掘算法的研究主要基于支持度 一可信度框架，由于这种框架自身的缺陷，用户与挖掘系统的交互度不高，使挖 掘的关联规则中用户感兴趣的却不多，因此如何增加用户与系统的交互度使用户 对挖掘的关联规则算法更感兴趣已成为了一项新的研究任务，不少学者放弃采用 支持度可信度框架，而尝试采用新方法来进行关联规则挖掘，以提高用户的 满意度和兴趣度。本文正是在这种背景下，研究交互式关联规则挖掘技术，提出 了一种交互式关联规则挖掘算法i 姒r 算法。 本文酋先介绍了数据挖掘和关联规则挖掘的相关理论；其次介绍了传统的 基于支持度可信度框架的关联规则挖掘算法a p r i o r i 算法；最后提出并详细 论述了种交互式关联规则挖掘算法一i m a r 算法。 i m a r 算法定义了规则约束。规则约束不仅包括了传统的支持度和可信度阈 值而且还允许用户指定关联规则左部和右部必须出现的项和禁止出现的项。i m a r 算法采用布尔表达式形式化的表示规则约束。i m a r 算法在“概念格”的理论基 础上生成频繁集集合。算法首先将规则约束布尔表达式转化成集合约束布尔表达 式，然后采用最小频繁集扩充的方式在等价类上搜索频繁集，最后算法根据搜索 出的频繁集集合和规则约束生成出符合用户约束的关联规则。本文最后通过中学 生智能评估系统给出了算法在教育信息系统中的应用实例。 关键词关联规则；交互式；约束；数据挖掘：概念格； a b s t r a c t w i t ht h er a p i d l yd e v e l o p m e n to fi n f o r m a t i o ni n d u s t r i a li z a t i o n ，t h e c o n f l i c tb e t w e e ne x p l o s i o no fd a t aa n dp o o r n e s so fk n o w l e d g eh a s b e e nm o r e a n dm o r ea c u t e ，a n dd a t am i n i n gp l a y sm e r ea n dm o r ei m p o r t a n tr o l e si n m a n ya r e a s o fa l1t h eb r a c h e so fd a t am i n i n g ，t h er e s e a r c ho na s s o ci a t i o n r u l em i n i n gi st h eo n ed e e p e s te x p l o r e da n di t sa p p l i c a t i o ni st h em o s t w i d e l yu s e d a tp r e s e n tt h er e s e a r c ho na s s o c i a t i o nr u l em i n i n gi sm o s t l y b a s e do nt h e s u p p o r t c o n f i d e n c ef r a m e w o r k d ut ot h ei n t r i n s i e s h o r t c o m i n go ft h ef r a m e ， u s e r sc a nn o tu s et h e m i n i n g s y s t e m i n t e r a c t i v e l ya n dt h i sr e s u l t si nt h a tf e wa s s o c i a t i o nr u l e sa r e i n t e r e s t i n gt ot h e m s ot h ee x p l o r a t i o no fh o wt os e tu pa ni n t e r a c t i v e s y s t e mo fa s s o c i a t i o nr u l em i n i n gi no r d e rt op r o d u c em o r ei n t e r e s t i n g a s s o c i a t i o nr u l e s5 a sb e c o m ean o v e l a n dp o p u l a rt a s ki nt h er e s e a r c ho f a s s o c i a t i o nr u l em i n i n g s e v e r a le x p e r t se m p l o y e dn e wm e a s u r e st oi m p r o v e t h es a t i s f a c t i o na n di n t e r e s to fa s s o c i a t i o nr u l e sw i t h o u t a d o p t i n g s u p p o r t c o n f i d e n c ef r a m e w o r ki na s s o c i a t i o nr u l e m i n i n g u n d e rs u c h b a c k g r o u n d ，t h i sp a p e rm a k e sas t u d yo ft h ei n t e r a c t i v ea s s o c i a t i o nr u l e m i n i n ga n dp r o p o s e sa na l g o r i t h mf o ri n t e r a c t i v em i n i n go fa s s o c i a t i o n r u l e s ( i m a r ) f i r s t l y ，t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r yr e l a t e dt od a t am i n i n g a n da s s o c i a t i o nr u l em i n i n g t h e ni sat r a d i t i o n a la l g o r i t h m ( a p r i o r i ) o fa s s o c i a t i o nr u l em i n i n gb a s e do ns u p p o r t c o n f i d e n c ef r a m e w o r k f i n a l l y ， t h e p a p e rp u tf o r w a r d sa n dd i s c u s e si nd e t a i la na l g o r i t h m f o r t a c k l i n gi n t e r a c t i v ea s s o c i a t i o nm i n i n g ，w h i c hi sc a l l e di n t e r a c t i v e m i n i n go fa s s o c i a t i o nr u l e s ( i m a r ) t h ea l g o r i t h mp r e s c r i b e st h er u l ec o n s t r a i n t s a n de x p r e s s e st h e mu s i n g b o o l e a ne x p r e s s i o n t h er u l ec o n s t r a i n t si n c l u d en o to n l yt h em i n i m a l s u p p o r ta n dc o n f id e n c et h r e s h o ldb u ta ls ot h eit e m st h a tt h eh e a da n dt h e b o d yo fa na s s o c i a t i o nr u em u s th a v eo rm u s tn o th a v e i m a rs e t su pt h e s e to ff r e q u e n ts e t su s i n gt h e a t t ic e b a s e da p p r o a c h f i r s t l y ，t h e i j a l g o r i t h mt r a n s l a t e st h eb o o l e a ne x p r e s s i o no fr u l ec o n s t r a i n t si n t ot h e c o r r e s p o n d i n gb o o l e a ne x p r e s s i o n so fs e tc o n s t r a i n t s s e c o n d l y ，t h e a l g o r i t h ms e a r c h e st h ef r e q u e n ts e ti nt h ee q u i v a l e n tc l a s s e su s i n gt h e a p p r o a c ho ft h ee x p a n s i o no fm i n i m a lf r e q u e n ts e t t h i r d l y ，a c c o r d i n gt o t h ep r o d u c e ds e to ff r e q u e n ts e t sa n dt h er u l ec o n s t r a i n t s ，t h ea l g o r i t h m p r o d u c e st h ea s s o c i a t i o nr u l e s i nt h ee n d ，t h ep a p e r g i v e sa na p p l i c a t i o n o fi g a rt oa ne d u c a t i o ns y s t e m k e yw o r d s ：a s s o c i a t i o nr u l e ；i n t e r a c t i v e n e s s ： c o n s t r a i n t s ；d a t am i n i n g ； c o n c e p tl a t t i c e 1 1 河海大学硕士学位论文 1 1 引言 第一章绪论 今天的人们在拥有了大量的数据的基础上迫切希望将这些数据转化为有用 的知识和信息。数据挖掘一个新兴学科一在这样的背景下产生了并迅速 成为信息科学中的热门研究领域，受到广泛的关注。 数据挖掘是信息科学革命性发展的直接结果。从信息科学的发展历程来看， 首先成熟的是以文件系统为代表的数据采集技术。当数据的采集不再是问题以 后，对数据的处理( 包括存贮，检索等等) 就成为了系统的瓶颈。于是数据库技术 应运而生。数据库技术成功地解决了上述问题后，人们就希望能够对数据进行更 好的分析和理解。这样就产生了数据仓库和在线数据分析( o l a p ) 技术【“2 1 。这些 技术部分地解决了人们的需求。比如0 l a p 的工具支持多维分析，一定范围内的 决策支持等等【2 3 l 。 但人们还需要对数据做出更深入的分析f 如数据的分类、聚类、特征等等) 。 以难以想象的高速度收集的大量数据被存贮在超大规模的数据库中，远远超出了 人们能理解它的能力，这被称为“数据丰富而信息贫乏”。结果是数据库往往变 成了“数据的坟墓”，很少被人访问，决策更多地不是依赖信息，而是依赖决策 者的直觉。数据挖掘就是要改善“数据丰富而信息贫乏”的情况，将“数据的坟 墓”变成隐藏着知识的“金矿”【钔。 数据挖掘就是从大量原始数据中提取人们感兴趣的、隐含的、尚未被发现的、 有用的信息和知识【5 1 ，使它们可以有利于指导决策支持，其提取的知识可以表示 为概念、规则、规律、模式等形式，是当今数据库和人工智能相互结合的最前沿 和极富应用前景的研究领域，己引起了国内外众多学者和业界的高度重视，对数 据挖掘的方法论、理论和工具开展了广泛深入的研究工作。根据挖掘任务数据挖 掘可分为：分类、聚类分析、关联规则、序列模式发现、回归分析等1 6 。7 j 。在这 些数据挖掘任务中，关联规则挖掘是其中的最为流行、研究尤为深入和广泛的一 种应用之一。 关联规则挖掘于1 9 9 3 年由a g r a w a l 8 。9 1 0 1 1 】等人在对市场购物篮问题进行分 析时首次提出，用以发现商品销售中的顾客购买模式。关联规则挖掘可以发现存 在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的和被隐藏的。 河海大学硕士学位论文 所发现的关联规则可以辅助人们进行市场运作、决策支持及商业管理，网站设计 等各个领域 1 2 j 。 本文也是对关联规则挖掘在教育领域的一个应用，在中学生智能评估系统中 有大量的关于现在和过去学生的资料，包括学习成绩、思想道德表现、行为表现、 奖惩情况等等，在数据比较完备的前提下，原有系统“l 主要通过a p r i o f i 算法 【8 一一5 l 实现关联规则数据挖掘，用户只能绘出支持度和可信度两个约束值，系统 和用户交互的程度不高，导致系统挖掘出许多用户不感兴趣的和表述冗余的关联 规则。本文正是在上述问题的驱动下，在“概念格”1 1 0 1 7 1 8 】的基础上提出了一 种交互式关联规则挖掘算法( i m a r ) 并将其应用到了中学智能评估系统中大增 强了原有系统在关联挖掘子模块中和用户的交互性，使得挖掘出的关联规则更加 符合用户的需求，提高了挖掘效率。 1 2 本文的主要工作 原有的中学生智能评估系统中的关联规则挖掘子模块通过采用a p r i o r i 算法 实现关联规则的挖掘，在挖掘过程中用户只能提出最小支持度和最小可信度两个 挖掘约束，这就使得系统挖掘出大量对于用户来说不感兴趣和意义重复的关联规 则。此外，a p r i o r i 算法需要从候选集中产生频繁集，而且需要重复的扫描数据 库，因此大大降低了算法执行的效率。 本文针对原有系统存在的问题，提出了一种交互式关联挖掘算法1 m a r 算法并将该算法应用到了系统中。i m a r 算法使用户在挖掘过程中不仅可以定制 支持度和可信度的约束还可以对规则左右项集定制约束，这样就增强了用户与系 统的交互性，提高了挖掘的效率。此外，i m a r 算法在“概念格”理论的基础上 在垂直数据集中生成等价类并在等价类中采取最小频繁集扩充方式生成频繁集 集合，该方式较传统的从候选集中产生频繁集的方式来说大大减少了系统扫描数 据库的次数从而有效提高了算法的执行效率。 1 3 本文的内容与组织 本文共有6 个章节组成，这6 个章节分别是这样安排的： 第一章绪论。介绍了本文的研究背景、主要工作以及全文的组织结构 第二章数据库中的知识发现和数据挖掘。介绍了知识发现( k d d ) 和数据 挖掘的相关概念及其应用。 第三章关联规则挖掘相关理论。介绍了关联规则挖掘的重要技术和思想并 重点介绍了经典的关联规则挖掘a p r i o r i 算法。 河海大学硕士学位论文 第四章交互式关联规则挖掘算法的设计与实现。这一章是本文论述的重点。 这一章介绍了基于“概念格”理论的e c l a t 算法，给出了用户的规则描述并提出 了交互式关联规则( i m a r ) 算法并实现了它。 第五章i m a r 算法在中学生智能评估系统中的应用。介绍了中学生智能评 估系统的概况，在i m a r 算法的基础上设计出了交互式关联规则挖掘系统并应用 到了评估系统中，最后将挖掘系统的结果和原系统作了比较，以实例证明了交互 式关联规则挖掘系统的优越性。 第六章小结与展望。对本文的工作进行了总结，并对今后应该开展的工作 做了展望。 河海大学硕士学位论文 第二章数据库中的知识发现和数据挖掘 2 1 数据库中的知识发现 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大，可是目前用于对这些数据进行分析处理的工具却很少，有关收 集和存储各种各样数据的能力已经大大超过了分析、综合和挖掘知识的能力【5 ， 1 2 】。目前数据库系统所能做到的只是对数据库中已有的数据进行存取和有限的处 理，人们通过这些数据所获得的信息量仅仅是整个数据库所包含的信息量的一部 分，隐藏在这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对 其发展趋势的预测，这些信息在决策生成的过程中具有重要的参考价值1 3 1 。 在数据库技术飞速发展的同时，人工智能领域的一个分支机器学习的 研究也取得很大进展。自5 0 年代开始机器学习的研究以来，在不同时期的研究 途径和目的也不尽相同，一般大致可分为三个阶段，其研究内容分别为：神经模 型和决策理论、概念符号获取及知识加强和论域专甩学习j 根据人类学习的不同 模式人们提出了很多机器学习方法，如实例学习、观察和发现学习、神经网络和 遗传算法等【埘。其中某些常用且较成熟的算法已被人们运用于实际的应用系统及 智能计算机的设计和实现中。 正是由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作中 的需要，数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a i a b a s e ；k d d ) m 1 l ”】技术逐渐发展起来。数据库中的知识发现是近年来随着数据库和人工智能技术 的发展而出现的，它主要采用机器学习算法或统计方法进行知识学习，一般将 k d d 中进行知识学习的阶段称为数据挖掘( d m am i n i n g ) 吼数据挖掘是k d d 中的一个非常重要的处理步骤。人们往往不加区分地使用两者，在本文中统一以 k d d 称之。一般来说，在工程应用领域多称数据挖掘，而在研究领域人们则多 称为数据库中的知识发现。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第一届k d d 国际学术会议上 正式形成的。国际k d d 学术会议起初每两年召开一次，1 9 9 3 年后每年召开一次。 1 9 9 5 年，在加拿大召开了第一届知识发现和数据开采国际学术会议。由于数据 库中的数据被形象地喻为矿床，因此数据挖掘一词很快流传歼来。1 9 9 5 年以来， 国外在这方面的论文非常多，已形成热门研究方向。 河海大学硕士学位论文 k d d 定义 随着k d d 研究的不断深入，人们对k d d 的理解越来越全面，对k d d 的定 义也不断修改，下面是对k d d 的比较公认的一个定义 4 1 ： “t h en o n t r i v i a lp 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 yu s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a ”，即k d d 是从大量数据中提取出有效的、 新颖的、有潜在作用的、可信的、并能最终被人理解的模式的非平凡的处理过程。 k d d 的特点 由以上可以看出，i d d 是利用机器学习的方法从数据库中提取有价值知识 的过程，是数据库技术和机器学习两个学科的交叉学科。数据库技术侧重于对数 据存储处理的高效率方法的研究，而机器学习则侧重于设计新的方法从数据中提 取知识。k d d 利用数据库技术对数据进行前端处理，而利用机器学习方法从处 理后的数据中提取有用的知识。i d d 与其他学科也有很强的联系，如统计学、 数学和可视化技术等。 既然k d d 和机器学习都是从数据中提取知识，那么两者有什么区别呢? i a v g ( 收a ) = 2 3 0 0 ，涉及的收入是数值类型，所以 是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则1 3 1 5 1 9 1 。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的，而在多层的关联规则中，对数据的多层性己经进行了充分的考虑。例 如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台式机 = s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的1 3 1 1 。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品，而 在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关 系。 例如：啤酒= 尿布，这条规则只涉及到用户购买的物品；性别= “女”= 职业= “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 3 1 5 关联规则挖掘算法的研究发展 1 9 9 4 年，a g r a w a l 8 】等人提出了a p r i o r i 算法，这是关联规则挖掘的发展过程 中一个具有里程碑意义的算法，下一节将详细论述a p f i o r i 算法。1 9 9 5 年，p a r k 等人提出了d h p 4 】( 动态哈希裁剪) 算法，对事务集通过哈希裁剪，将由于项数 比较小的事务从哈希树上剪掉( 或加标志) ，从丽减少了以后需要遍历的事务数。 2 0 0 0 年z a k i 【1 7 l 等人提出了e c l a t 、m a x e c l a t 、c l i q u e 、m a x c l i q u e 四种算法，其中 用到了概念格的思想，第四章将详细论述e c l a t 算法。2 0 0 0 年j i a w e ih a n p j 提出 了不采用候选集的f p t r e e 算法，通过f p t r e e 存储事务集，最大程度的压缩数 据并保证数据的完整性，通过对f p t r e e 的一次遍历生成全部的频繁集。2 0 0 3 年 z a k i 等人提出了采用异项集的垂直挖掘算法，主要适用于稠密事务集j 对于稀疏 事务集就不适合了。 总之关联规则的研究的延伸幅度非常广，以上的算法大多是从提升生成频繁 河海大学硕士学位论文 集效率的角度出发，而本文提出的i m a r 算法则是从增强系统与用户交互度，提 高挖掘效率的角度出发。 3 2 经典关联规则发现算法a p r i o r i 算法 3 2 1 算法描述 在a p f i o f i 算法中，引入以下若干记号。由频繁k 项目集组成的集合记作h ， 由候选项目集组成的集合记作c k 【3 8 强2 9 3 。 a p f i o f i 算法的原理是，如果项目集x 是频繁项目集，则x 的任一子集必定 也是频繁项目集：反过来说，如果x 有一子集不是频繁项目集，则x 肯定也不 是，即频繁集的反单调性3 1 3 2 1 。因此，如果已经生成了h ，则可以根据k 来生成c k + 1 由于c k + 1 中的候选项目集的长度为k + l ，因此要求它的每个子集， 比如长度为k 的物品子集是集合k 中的元素。这样就保证了【“1 包含在c k + l 中 了。 频繁项目集的发现是一个渐进的过程，即按照频繁项目集的长度，从1 一项目 集开始，依次增加项目集的长度。以如下的事务数据库为例，描述频繁项目集的 发现过程。 t j d 物品集 1 0 0a c d 2 0 0b c e 3 0 0a b c e 4 0 0b e 表3 1 ：事物数据库d 假设用户设定的最小支持度为o 5 。首先遍历数据库d ，得到每个项目的支 持数，然后根据所有不低于最小支持度的项目构成频繁1 项目集 l 1 = “a ， b ) ， c ) ， e ) ) 。链接l 1 中的所有项目构成候选2 。项目集 c 2 = “a b ) ， a c ) ， a e ， b c ， b e ， c e ) ) ，再次遍历数据库，计算c 2 中每个候选 项目集的支持数目，然后根据所有不低于最小支持度的项目构成频繁2 。项目集 l 2 = a c ， b c ， b e ) ， c e ) 。在通过链接k 中的所有项目构成候选3 项目集 c 3 = “b c e ) ) ，再次遍历数据库，计算c 3 中每个候选项目集的支持数目，然后根 河海大学硕士学位论文 据所有不低于最小支持度的项目构成频繁3 - 项目集l 3 = “b c e ) ) 。由于l 3 中只 有一个元素，不能产生新的候选项目集，所以算法到此结束【3 8 瑚2 9 3 ”。 上述过程可以用如下算法描述： f o ra l lt r a n s a c t i o nt dd o b e g i n c l = g e t _ s u b s e t ( c 1 ，t ) ，a l lc a n d i d a t ec o n t a i n e di nt ；+ f o re a c hc a n d i d a t ec c td oc c o u m + + ： e n d ； l 1 = c lc c o u n t - - - - s ，c c 1 8 l 1 为数据库中的频繁1 - 项目集+ f o r ( k = 2 ；i 士乃；k + + ) b e g i n c k = a p r i o r i g e n ( l k q ) f o ra nt r a n s a c t i o nt dd o b e g i n g = g e t _ s u b s e t ( c k ，t ) 4a l lc a n d i d a t ec o n t a i n e di nt + f o re a c hc a n d i d a t ec c td oc c o u n t + + ； e n d ； l k = c lc c o u n t = s ，c c k ) 丰【士为数据库中的频繁k 项目集+ e n d ； a n s w e r = - ul 赴； 其中，a p r i o r i g e n 候选生成算法是以频繁( k - 1 ) 一项目集生成候选k 一项目集的。 该算法分为如下两步 ( 1 ) 拼接 i n s e r ti n t oc k s e l e c tp i t e m l ，p i t e m 2 ， f r o ml kl p ，l k 1 q 河海大学硕士学位论文 ( 2 ) 修剪 对c k 中的任一候选c ，如果c 中存在一个不属于k 一1 的长度为k - 1 的子项目，那 么就从q 中删除该候选c 。 f o ra l li t e m s e t sc q qd o f o ra l l ( 1 ( 一1 ) 一s u b s e tso fcd o i f ( s 曲- 咄- 1 ) t h e n d e l e t ecf r o mc k ； 3 2 2 a p r i o r i 的算法瓶颈 很显然，a p r i o r i 算法有两个致命的性能瓶列孤3 2 “3 4 1 ： 1 、多次扫描事务数据库，需要很大的i 0 负载。对每次k 循环，侯选集c k 中的每个元素都必须通过扫描数据库一次来验证其是否加入k 。假如有一个频 繁大项集包含1 0 个项的话，那么就至少需要扫描事务数据库1 0 遍。 2 、可能产生庞大的侯选集。由l b l 产生l 【- 侯选集q 是指数增长的，例如 1 0 4 的1 频繁项集就有可能产生接近1 0 7 个元素的2 候选集。如此大的侯选集对 时间和主存空间都是一种挑战。 3 3 小结 本章主要就关联规则的基础理论和经典算法进行了阐述，为后两章提供了理 论基础。本章首先介绍了关联规则挖掘的一些基本概念以及关联规则的研究现 状；其次分析了支持度可信度框架下关联规则挖掘的经典算法a p r i o r i 算法；最后分析了a p r i o r i 算法的不足。 河海大学硕士学位论文 第四章交互式关联规则挖掘算法的设计与 实现 4 1 概述 交互式关联规则挖掘的本质就是数据挖掘查询语言( d a t am i n i n gq u e r y l a n g u a g e ) 【1 12 8 3 5 的本质，即允许用户输入自己定制的一组查询约束挖掘出自 己感兴趣的信息。所以本文提出的- 交互式关联规则挖掘i m a r 算法( i n t e r a c t i v e m i n i n go fa s s o c i a t i o nr u l e s ) 本质上就是一种基于约束m 3 2 3 5 3 6 。3 7 l 的关联规则 挖掘算法。本文提出的i m a r 算法主要基于以下两点考量： ( 1 ) 传统的关联规则挖掘算法如a p d o d 算法及它的许多变体算法和扩展算 法32 5 2 6 l 为了计算所有满足条件( 最小支持度和最小置信度) 的频繁集时需要反 复扫描数据库，加重了系统处理 0 的负担，因而挖掘教率很低，而一种基于等 价类的e c l a t ( e q u i v a l e n c ec l a s st r a n s f o r m a t i o n ) 算法【1 7 1 在生成频繁集时只需一 次遍历数据库从而大大提高了计算速度，所以i m a r 算法在e c l a t 算法的基础上 生成频繁集。 ( 2 ) i m a r 算法的优越性在于能将用户的定制信息整合到挖掘过程中从而 挖掘出更加符合用户需要的信息。用户的定制信息本质上就是一组挖掘约束。 i m a r 算法将采用布尔表达式表示挖掘约束并将其整合到挖掘过程中。 4 2 生成频繁项目集的e c l a t 算法( e q u i v a l e n c ec l a s s t r a n s f o r m a t i o n ) 4 2 1 数据的垂直分布 e c l a t 算法用了垂直数据库结构【1 61 7 3 8 1 。a p r i o r i 等算法中的数据呈水平分 布其数据集由一系列事务构成。每个事务标识符t j d 以及相应事务所包含项目 集。而数据的垂直分布是指，数据集由一系列项目构成，每一个项目均带有其相 应的i i d 列表，即包含该项目的所有事务标识符表，且按字典序的升序排列，这 样使得任何一个频繁集的支持度都可以通过一些t i d l i s t 的交集运算求得i 3 8 】。图 4 1 和图4 2 分别为数据水平分布的事物数据库和其数据垂直分布t i d - l i s t 形式的 示例： 河海大学硕士学位论文 图4 1 ：水平数据分布 4 2 2e c l a t 算法描述 图4 2 ：垂直数据分布 e c l a t 算法在概念格理论1 1 6 1 7 1 1 8 】的基础上，利用基于前缀的等价关系将搜索 空间( 概念格) 划分为较小的子空间( 子概念格) 采用了自底向上( 对于等价类) 的频 繁集搜索方法，将等价类分解为较小的等价类。通过枚举每一个等价类中所有原 予项的交集来逐层递归求出所有的等价类。如对于图4 2 的实例数据库，令i 是 所有项( i t e m s ) 的集合，p ( i ) 是它的完全概念格。p ( i ) 被划分为【a 】， c 】，【d 】， 【q ，【w 1 5 个等价类( 子概念格) ，并且是有序的。e c l a t 算法采用基于前缀的分类， 即【x 】等价类表示所有前缀为x 的项集构成的子概念格。如【a 】= a , a c ，a d ，a t , a w , a c d ，a c t , a c w , a d t , a d w , a t w , a c d t , a c d w , a c r w , a d t w ； a c r d w ，图4 3 描述了等价类【a 】的实际挖掘过程和其中用到的原予。 图4 3 ( a ) ：等价类 a 的实际挖掘过程图4 3 ( b ) ：等价类 a j 的原子 河海大学硕士学位论文 以上是对e c l a t 算法的概述，下面是对该算法的具体描述。对于数据垂直分 布可以采用等价类生成候选频繁项目集。设在a r ，r i o d 算法中，第k 次遍历所 需的候选项目集c k 是由频繁项目集k 1 得到。令各项目集中的项目按字典序的 升序排列。按照前k 2 个项目( 称为张一一前缀) 是否相同来对l k 。1 进行等价类 划分，即具有相同( k 2 ) 前缀的项目集属于同一个等价类，记作：p a 【a = b 【k 1 】 l l l a 1 ，k 2 】_ b 【1 ，k 一2 】) 。于是，候选k 项目集可以通过连接同一等价类中所有的 元素对，然后再以类标识符作为各连接结果的前缀来生成。例如：对图4 2 中 的数据库，由k = a c ，a d a t ，a w ，c d ，c t ，c w ，d t ，d w ，t w ，可得 到如下等价类：p a a 】= c ，d ，t ，w ) ，p c 【c 】_ d ，t ，w ) ，p d 【d 】： t ，w ， p t 【t 】= w ) 。由等价类【a 】，【c 】，【d 】，【叨连接生成的集合分别为 a c d ，a c t ， a c w ，a d t ，a d w ，a t w ， c d t ，c d w ，c r w ， d t w 。这3 个集合相 互独立，但其并集构成了候选频繁项目集c k 。其算法如下： a l g o r i t h m ：e c l a t i n p u t ：频繁项目集l k o u t p u t ：频繁项目集k + 1 k + 1 的等价类t k b e g i n ( 1 ) f o r i - 1 t o i 刈 ( 2 ) t k 【i 】= d ； ( 3 ) f o r j = i + l t oi 吲 ( 4 )c = l k i 1 】l k 【i 】【2 】l k i 】【k 】l kd 】【k 】； ( 5 )j o i n ( l k 【i 1 ，l x 【j 】) ； ( 6 )i f s ( c ) m i n s u p t h e n ( 7 ) r 【i 】= t k 【i u c ) ； (8)tk+1=lk+iuc)； ( 9 ) e n d i f ( 1 0 ) ( 1 1 ) ( 1 2 ) f o ra l lt k 【i 】dd o g e t e q u i v a l e n c e _ c l a s s e s & g e t _ & n d i d a t e _ i t e m s e t s ( t k i ) e n d 算法晚明： 河海大学硕士学位论文 ( 1 ) 算法的第4 步把等价类中两个长度为k 的频繁项目l k 拼接成一个长度k + l 的候选 项目c k + l 。 ( 2 ) 第5 步由算法j o i n 连接等价类中两个项目的1 1 d 列表算法如下所述。 ( 3 ) 第6 ，7 ，8 步由连接得到c 的支持度，然后判断是否为频繁项目集。若是，则 把c 分别加入到等价类和频繁项目集中。 ( 4 ) 若等价类非空，重复调用此算法，可得到所有的等价类和频繁项目集。 a l g o r i t h m ：j o i n ( x ，y ) i n p u t ：两个长度为k 的项目集x 和y 及其d 列表x t i d s 和y t i d s o u t p u t ：长度为k + l 的新的项目集c 彭j t r d 列表 b e g i n o ) c s u p p o r t = 0 ； ( 2 ) i = 1 j = 1 ；k = 0 ； ( 3 ) w h i l e i i x la n dj i y id o ( 4 )i f x t i d s i 】= y t i d s u 】t h e n ( 5 )k + + ； ( 6 )c s u p p o r t + + ； ( 7 ) c r i d s 哟= y t i d s j ； ( 8 ) ( 9 ) e l s ej fx t i d s i 】y t i d s j 】t h e ni + + ( 1 0 ) e l s e j + + ； ( 1 1 ) ) e n d 4 3 交互式关联规则挖掘i m a r 算( i n t e r a c t i v em i n i n go f a s s o c i a t i o nr u l e s ) 4 3 1 规则约束描述 正如本章概述所述，本文将采用布尔表达式2 8 1 来描述约束。表达式中的每项 都是一个原子约束，每项原子约束用合取符号连接，规则中的原子约束不能相同， 河海大学硕士学位论文 原子约束可以分为四类： 1 、某项i 必须出现在规则左部记为u i ) ， “i ) 表示项i 禁止出现在规则左 部。 2 、某项j 必须出现在规则右部记为r ( i ) ， r 0 ) 表示项i 禁止出现在规则右 部。 3 、最小支持度闽值记为s 。 4 、最小可信度闽值记为c 。 设用户给出如下规则约束： 三a ) al ( d ) a ( ，工( r ) ) r ( c ) a ( 一r ( r ) ) a - r o e ) as ( 4 ) ac ( 5 0 ) 该规则约束表示项a 、d 必须出现在规则的左部，项c 必须出现在规则的右 部，项t 禁止出现在规则中，项w 禁止出现在规则的右部，挖掘出的关联规则 的最小支持度是4 ，最小可信度是8 0 。 4 3 2i m a r 算法设计 4 3 2 1 建立集合约束 设1 1 。1 2 ，1 3 是必须出现在规则左部的项，h ，1 5 ，1 6 是禁止出现在规则左部 的项，1 1 ，1 2 ，1 3 是必须出现在规则右部的项，h ，1 5 ，1 6 是禁止出现在规则右 部的项。根据关联规则的定义，只有当x u y 是频繁集的时候才会产生形如x = y 的关联规则。所以i m a r 算法根据用户约束生成联规则的过程中必须要产生下列 三种频繁集： 1 、包含1 1 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 的频繁集集合s e t a ，但s e t a 不能含有1 4 ，1 5 ， 1 6 ， 1 4 ，1 5 ，1 6 的交集。定义4 1 ：s e t a = s is s e t a a n ds 规则约束中必 须出现的项) a n dsn 规则约束中禁止出现的项) = 中) 。 2 、包含1 1 ，1 2 ，1 3 的频繁集集合s e t l ，但s e t l 不能含有1 1 ，1 2 ，1 3 及1 4 ， 1 5 ，1 6 。 定义4 2 ：s e t l = s is es e t la n dsc _ c a 规则约束中必须出现在左部的 项 a n dsn 规则约束中禁止出现在左部项) = 中a n dsn 规则约束中必须出现 在右部的项 = 中 。 3 、包含1 1 ，1 2 ，1 3 的频繁集集合s e t r ，但s e t r 不能含有l l ，1 2 ，1 3 及1 4 ， 1 5 ，1 6 。定义4 3 ：s e t r = s is s e t ra n ds 规则约束中必须出现在右部的 项) a n dsn 规则约束中禁l 匕出现在右部项) = oa n dsn 规则约束中必须出现 在左部的项，= 巾， 河海大学硕士学位论文 根据约束的反单调性( 即给定一个约束条件c 。如果一个项集s 不满足c ， s 的任何超集也不可能满足c ，则称约束条件c 是反单调的) 原则，s e t l 和s e t r 中的每个频繁集都是s e t a 中某个频繁集的子集。 如上所述，i m a r 算法的第一步就是根据规则约束建立集合约束，集合约束 的表达形式也是布尔表达式，建立步骤如下所示： 1 、对出现在规则约束布尔表达式中的每个l ( i ) 或r ( i ) ，都将s e t ( i ) j i a 至l 集 合约束的布尔表达式中。 2 、对同时出现在规则约束布尔表达式中的 坪) 和 r ( i ) ，将- is e t ( i ) 加入