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

山东大学硕士学位论文 摘要 本文在系统介绍数据挖掘相关知识的基础上，重点研究了关联规则挖掘算法 及其在税收领域的部分应用。 关联规则挖掘算法的关键是频繁项目集的计算，其典型算法是a g r a w a l 等人 提出的a p r i o r i 算法，但它适合挖掘事务数据库中的单维关联规则，而税收数据 是基于关系数据库的，而且大多是多维的，为此，我们提出了一个基于数据立方 体的、适合税收数据的多维关联规则挖掘算法m u l t i _ a p r i o r i ，并用一个税收应用 实例说明了该算法的执行过程。为了提高该算法执行效率，在此基础上，我们设 计了一个基于o l a p 技术和约束的多维关联规则挖掘算法u p _ a p r i o r i ，该算法仅 针对维间关联规则，特别适于从关系数据库中挖掘税收关联规则，应用该算法， 我们成功实现了税负数据的关联分析挖掘，有效协助了税务系统纳税评估工作的 开展。 关联规则挖掘算法的应用是多方面的，但效率永远都是关键，在a p r i o r i 算 法的基础上，我们设计并实现了一个改进的关联规则挖掘算法s u p ，该_apriori 算法基于多次剪枝和分区搜索技术，废弃了a p r i o r i 算法中的h a s h t r e e 数据存储 结构，而改用一维数组结构方式来存放候选项目集，并进行合理分区，从而提高 了搜索的效率。分析结果证明，在频繁项目集的计算上该算法效率大大提高。要 将该算法应用到税务系统，需要将税收关系数据集转换为事务数据集，利用上述 算法和方法，我们实现了税务稽查选案数据的关联分析挖掘。 关键词：数据挖掘，关联规则，算法，税收数据，税负分析 山东大学硕士学位论文 a b s t r a c t t h i sa r d d ei n t r o d u c e ds o m ek n o w l e d g ea b o u td a t am i n i n gs y s t e m i c l y i nt h e b a s eo fi t , w es t u d i e da s s o c i a t i o nr u l e sm i n i n ga n di t sa p p l i c a t i n gi nt a xd o m a i n m o s t l y 1 1 l ek e yo fa s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mi st h ec o u n t i n go ff r e q u e n t i t e m s e t s a p r i o r ii sat y p i c a la l g o r i t h mt h a ti sp u t d ef o r w a r db ya g r a v a l i ti ss u i t a b l e f o rm i n i n gi n g l e - d i m e n s i o n a la s s o c i a t i o nr u l e sf r o mt r a n s a c t i o nd a t a b a s e s b u tt a x d a t ai ss t o r e dt e l a t i o nd a t e b a s ea n di ti sm u l t i d i m e n s i o n a l t h e r e f o r e ，w es u m m a r i z e d a na l g o r i t h mo fm u l t i _ a p r i o r i 1 1 1 i sa l t o f i t h mi sb a s e do nd a t ac u b ea n di ts u i tt o m u l t i d i m e n s i o n a lt a xd a t a ，i no r d e rt oi m p r o v ei t se f f i c i e n c y , w ed e s i g n e da n i m p r o v e da l t o r i t l l mo fu p _ a p r i o r i w em a yu s et h i sa l g o r i t h mt or e a l i z ea s s o c i a t i o n r u l e s1 1 1 i l l i n ga b o u tt a xb u d e md a t a t h ee f f i c i e n c yo fa l t o r i t h mi sk e yf o r e v e r s o , i nt h i sa r f i d e , w ed e s i g n e da h i g h l ye f f e c t i v ea l t o f i t h mo fs u p _ a p r i o r i i ta p p l i e sm a n yp r u n i n ga n dp a r f i t i o n a l c o u n t i n gt e c h n o l o g y i ta p p l i e so n e d i m e n s i o na r r a yt os t o r ec a n d i d c a t es e t s t h e a r r a yi sd i s t r i c t e dt os u i ts e a r c h i n g b yt h i sw a y , t h ee f f i c i e n c yo fa l t o r i t h mi si m p r o v e d h i g h l y u s e i n gt h i sa l t o r i t h m , w ec a nm i n ea s s o c i a t i o nr u l e si nt a xd a t a b a s ea b o u t a x a m i n a t i o nd a t a e n ta p p l i c a f i o n k e yw o r d s ：d a t am i n i n g a s c i a t i o nr u i e a 。a i g o t i t h mt a x t a xb u r d e n a n a i y s is i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：痘童拦 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：鱼避导师签名：醴日 期： 丛立 y 称为关联规则，x 、 y 分别称为关联规则x = y 的前提和结论。 关联规则x = y 的支持度就是项目集x u y 的支持度，记作s u p p o r t ( x = y ) ： s u p p o r t ( x = y ) s u p p o r t ( xuy ) 关联规则x - y 的置信度记作c o n f i d e n c e ( x = y ) ： s u p p o r t ( x u y )， c o n f i d e n c e ( x = y ) = s u p p o r t ( x ) 支持度s 定义为：在数据集d 中至少有s 的事务包含项目集x u y ，支持度 表示在规则中出现该型式的频度，用来衡量关联规则在整个数据集中的统计重要 山东大学硕士学位论文 性； 置信度c 9 6 定义为：在数据集d 中包含项目集x 的事务中至少有c 9 6 也同时包 含项目集y 。置信度表示蕴含式的强度，用来衡量关联规则的可信程度； 5 、定义2 5 如果s u p p o r t ( x = y ) m i n _ s u p ，并且c o n f i d e n c e ( x = y y ) m i n _ c o n f ，则称关联规则x - y 为强关联规则，否则称其为弱关联规则。 根据以上的定义我们可得出下面的定理是成立的： 6 、定理2 1 设x y 是数据集d 中的项目集； ( i ) 若x c y ，则s u p p o r t ( x ) 一 s u p p o r t ( y ) ； ( 2 ) 若x c y ，如果x 是非频集，则y 也是非频集： ( 3 ) 若x _ y ，如果y 是频集，则x 也是频集。 7 、关联规则挖掘的任务就是要挖掘出数据集d 中的所有的强关联规则。一般 将关联规则挖掘划分为以下两个子问题： ( i ) 根据最小支持度找出数据集d 中所有的频繁项目集： ( 2 ) 根据第一步找出的频繁项目集和最小置信度产生关联规则。 其中子问题2 的解决方法较为简单，对每个频繁项目集l ，对l 的每个非空 子集a ，考察规则a _ ( l a ) ，如果该规则满足最小支持度和最小置信度则输出 此规则。子问题i 是关联规则挖掘的中心问题，是衡量关联规则挖掘算法的标准， 它的任务是迅速高效地找出d 中的全部频繁项目集。目前所有的关联规则挖掘算 法都是针对第一个子问题而提出的，关联规则挖掘的基本模型( 如图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 和m i n _ c o n f 分别与算法a l g o r i t h m - - i 、a l g o r i t h m - - 2 交互，并通过与r 的交互对挖掘结果 进行 图2 - 1 关联规则挖掘的基本模型 9 山东大学硕士学位论文 2 2 关联规则的种类 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值 型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理， 将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中 也可以包含种类变量。 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。 在多层关联规则中，对数据的多层性已经进行了充分的考虑。 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维关联规则中，我们只涉及到数据的一个维，如用户购买的物品在多维关联规则 中，要处理的数据将会涉及多个维。 2 3 关联规则挖掘的核心算法a p r i o r i l 6 9 , 1 0 1 1 ，”】 2 3 1a p r l o r i 算法设计思想 a g r a w a l 等人1 9 9 4 年设计了一个基本算法a p r i o r i ，一个最有影响、最经典 的挖掘单维、单层、布尔关联规则的算法。这个算法基于前面提到的两阶段频繁 项集的思想，由定理2 1 ，我们就得到求频繁项目集的方法： ( 1 ) 先生成长度为l 的频繁项目集，记为l e l 。 ( 2 ) 在l 【k 】的基础上生成候选项目集( c a n d i d a t ei t e m s e t ) c 【“l 】，要求候 选项目集的所有的子集均为频繁项目集。 ( 3 ) 扫描事务数据库d ，计算每个候选项目集的支持度，如果大于r a i n _ s u p ， 则加入到l k + l l q b 。 ( 4 ) 如果l 【k + 1 】为空集，则结束，所求结果即为l 1 】u l 2 】u ，否则转2 ， 继续。 2 3 2a p r l o r i 算法描述 a l g o r i t h m ：a p r i o r i i n p u t ：( 1 ) 格式为( t i d ，i t e m s e t ) 的事务数据库d ，其中t i d 为事务标识符， 山东大学硕士学位论文 i t e m s e t 为该事务所对应项目集： ( 2 ) 用户最低支持度r a i ns u p ； o u t p u t ：所有的频繁项目集； b e g i n l , = 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 ：h l o ：k + + ) c k = a p r o i r i g e n ( k l ，r a i n _ s u p ) ：新的候选 f o re a c ht r a n s a c t i o nt d c t = s u b s e t ( c k ，t ) ；l i t 中所包含的候选 f o re a c hc a n d i d a t ec c t c c o u n t + + ； ) l k = c e c te c o u n t m i n _ s u p ) ) r e t u r n 仁u x k e n d 其中，a p r i o r i g e n 是以频繁( k - 1 ) 项目序列集l k - 1 为自变量的候选生成函 数。该函数返回所有频繁k 项目集的超集，分连接和修剪两步执行： ( 1 ) 连接( j o i n ) f o re a c hi t e m s e t1 1 l k - l f o re a c hi t e m s e t1 2 缸1 i fl 。 1 = 1 。 1 ) 八( 1 1 2 = l 。 2 ) a a ( 1 1e k - 2 = 1 ： k - 2 ) a ( 1 ， k - 1 - - 2 ，a k = a k - - a k _ l ，耐于a k 中的每个元素a ，如果k - d 数据 方体已经存在，则将k _ d 数据方体中所有的格放入q ；如果k - d 数据方体不存在 则计算它：生成方体的所有的格( k 个谓词q ，所有可能的维一值对) 。搜索关系数 据库，分别对每个格在关系数据库中的出现计数，存储在方体的单元中，将k - d 数据方体中所有的格放入q 。 第三步：对于c t 中的每个元素c ，如果它的任何一个子集不是频繁的，那么 删除c 。 第四步，对于q 中的每个元素c ，如果它的单元中的计数 r a i n _ s u p ，那么将 c 放入h 。 第五步：重复第二步一第四步，直至l k 为空集。 第六步：由频繁谓词集合产生强关联规则。 2 、m u l t i _ a p r i o r i 算法描述 算法：m u l t i _ a p r i o r i 找出频繁谓词集 输入：关系数据表d ，最小支持度阂值m i n _ s u p 输出：d 中的频繁谓词集l 方法： i f1 _ d 方体e x i s t 山东大学硕士学位论文 t h e nc 。= i - d 数据方体中所有的格的集合： e l s e 计算1 - d 数据方体： c 。= l 加数据方体中所有的格的集合： f o re a c hr e d ( f o re a c he c l ( i fr q i = q i j 】t h e nq 。 j c o u n t + + ： ) ) i f q i j c o u n t m i n _ s u pt h e nq 。 j l - ； ) a 。= ( q t lq 。 j e l ，) f o r ( k = 2 ：l k - 1 中：k + + ) ( a k = a k - la k - 1 p q f o re a c ha e a k i fk - d 数据方体存在 t h e nc k = k - d 数据方体中所有的格的集合： e l s e 计算k - d 数据方体； c k = k - d 数据方体中所有的格的集合：) f o re a c hr d f f o re a c hc c k i fc 的任何一个子集不是频繁的 t h e nd e l e t ec ： i fr q 。= q 。 j a n dr q k = q k 1 a n d r q = q i n t h e nc c o u n t + + ： )* c 是形如q t j q k 1 q n 共p 个谓词的维一值对， 山东大学硕士学位论文 其中i ，k ，m = ( 1 ，2 ，p ) i f c c o u n t r a i n _ s u pt h e nc k r e t u r nl = u 止k ， 我们用一个简单的例子来说明算法的执行过程： 纳税人识别号行业区域税负 3 7 0 4 0 5 0 0 0 0 1 药品零售业台儿庄城区二级 3 7 0 4 0 5 0 0 0 0 2 超级市场零售业 台儿庄涧头 三级 3 7 0 4 0 5 0 0 0 0 3 超级市场零售业台儿庄城区 一级 3 7 0 4 0 5 0 0 0 0 4 药品零售业台儿庄城区二级 3 7 0 4 0 5 0 0 0 0 5 超级市场零售业台儿庄涧头一级 3 7 0 4 0 5 0 0 0 0 6 超级市场零售业台儿庄城区二级 3 7 0 4 0 5 0 0 0 0 7 药品零售业 台儿庄涧头 二级 3 7 0 4 0 5 0 0 0 0 8 超级市场零售业台儿庄涧头一级 3 7 0 4 0 5 0 0 0 0 9 药品零售业 台儿庄涧头 三级 3 7 0 4 0 5 0 0 0 0 1 0 超级市场零售业台儿庄城区二级 表1 纳税人税负表 上表中共有1 0 条记录，以纳税人识别号加以标识。共有四个维：纳税人识 别号、行业、区域和税负。假定r a i ns u p = 4 ，算法执行过程如下： 1 、算法执行完第一步后，得到频繁卜谓词集： l i = 行业( 药品零售业) ，行业( 超级市场零售业) ， 区域( 台儿庄城区) ，区域( 台儿庄涧头) ， 税负( 一级) ，税负( 二级) ，税负( 三级) a 。= 行业，区域，税负) 2 、a 2 - - a ，aa i = 行业 区域，行业 税负，区域a 税负 q = 行业( 药品零售业) 八区域( 台儿庄城区) ， 山东大学硕士学位论文 行业( 药品零售业) a 区域( 台儿庄涧头) ， 行业( 超级市场零售业) a 区域( 台儿庄城区) ， 行业( 超级市场零售业) a 区域( 台儿庄涧头) ， 行业( 药品零售业) a 税负( 一级) ， 行业( 药品零售业) a 税负( 二级) ， 行业( 药品零售业) 八税负( 三级) ， 行业( 超级市场零售业) a 税负( 一级) ， 行业( 超级市场零售业) a 税负( 二级) ， 行业( 超级市场零售业) a 税负( 三级) ， 区域( 台儿庄城区) 八税负( 一级) ， 区域( 台儿庄城区) a 税负( 二级) ， 区域( 台儿庄城区) 税负( 三级) ， 区域( 台儿庄涧头) 八税负( 一级) ， 区域( 台儿庄涧头) 税负( - - 级) ， 区域( 台儿庄涧头) 八税负( 三级) l 2 = 区域( 台儿庄城区) 八税负( 二级) ，4 0 ) 3 、l 3 = 4 、l = l 1 u k 算法m u l t i 【a p r i o r i 的基础是数据立方体的计算，对于一个有n 维，每个维 上有m 层概念层的多维主题数据，通过聚集运算可以产生( 1 + m ) “个子立方体， 这个空间对于维度来说是指数级的( e x p o n e n t i a l ) ，如果一个关系数据库的维数 较多，算法m u l t i _ a p r i o r i 将会引起“组合爆炸”。算法m u l t i _ a p r i o r i 可以找 出所有的频繁p 一谓词，由此可以推导出强关联规则，这些维间关联规则反映的 是关系数据表中不同的属性值组合同时出现的支持度和置信度。在很多情况下， 有些属性的组合是没有意义的，因此，很有必要引入约束机制，以减少属性组合 的可能，提高算法效率。下面我们提出一个适合税收数据的基于约束的关联规则 挖掘算法。 山东大学硕士学位论文 2 5 基于约束的多维关联规则挖掘算法 本文采用先进行o l a p 操作，再进行数据挖掘的思想，引入约束机制，设计 了一个基于o l a p 技术和约束的多维关联规则挖掘算法u p _ a p r i o r i 。该算法仅针 对于维间关联规则，所以特别适合用于从关系数据库中挖掘关联规则。 2 5 1 基本概念嘲制 1 ) 多层关联规则：由具有概念分层的关联规则挖掘产生的规则称为多层关 联规则，因为它们考虑多个概念层。 多层关联规则的挖掘基本上可以沿用“支持度一置信度”的框架。不过，在 支持度设置的问题上有一些要考虑的东西。同层关联规则可以采用两种支持度策 略： 统一的最小支持度。对于不同的层次，都使用同一个最小支持度。这样对 于用户和算法实现来说都比较的容易，但是弊端也是显然的。 递减的最小支持度。每个层次都有不同的最小支持度，较低层次的最小支 持度相对较小。同时还可以利用上层挖掘得到的信息进行一些过滤的工作。 层间关联规则考虑最小支持度的时候，应该根据较低层次的最小支持度来 定。 2 ) 基于约束的关联挖掘：在基于约束的挖掘中，挖掘在用户提供的各种约 束的指导下进行。这些约束包括： 知识类型约束。指定要挖掘的知识类型，如关联规则。 数据约束。指定任务相关的数据集。 维层约束。指定所用的维及其概念分层。 规则约束。指定要挖掘的规则形式，这些规则可以用规则模板表示。 在下面的u p _ a p r i o r i 算法中主要考虑了数据约束、维层约束和规则约束。 2 5 2u p _ a p r i o r i 算法实现步骤 u p _ a p r i o r i 算法是基于o l a p 技术和约束机制的，可以分为o l a p 操作和维 间关联规则挖掘两部分，其中第一步属于o l a p 操作部分，第二步至第 五步属于关联规则挖掘部分。 u p _ a p r i o r i 算法的主要步骤： 给定数据集及每个属性的属性值的集合、最小支持度阈值r a i ns u p 。 2 l 山东大学硕士学位论文 第一步：在给定的数据集上做o l a p 操作，形成新的数据集。 对数据集中出现的每个维及其概念分层，由用户指定在哪些维及哪个概念分 层上进行分析挖掘。然后根据选定的维及概念分层在数据集上进行o l a p 操作， 即利用维或维的概念分层进行诸如上卷、下钻、切片和切块等操作，得到新的数 据集。 众所周知，许多概念分层结构蕴涵在数据库模式中。通过分析税收数据，我 们发现几乎所有税收数据的概念分层都隐含在属性值中。以纳税人税负数据为 例，相关的数据有行业、区域、税负等几个属性，区域的属性值“1 3 7 0 4 4 5 0 0 0 1 ” 代表的是山东省枣庄市台儿庄区城区分局，其前5 位“1 3 7 0 4 ”代表山东省枣庄 市，前7 位“1 3 7 0 4 4 5 ”代表山东省枣庄市台儿庄区。三个概念分层隐含在属性 值中，可以通过对属性值进行计算得出。如果用户需要较高的、一般化的抽象层 上进行挖掘，可以将利用“上卷”计算较高层的数据立方体；相反，如果用户认 为结果数据过于一般化，可以利用“下钻”计算较低层的数据立方体。 第二步：量化属性离散化。 对o l a p 操作后得到的结果集中的量化属性根据预先定义好的量化规则进行 离散化，使其满足关联规则分析的要求。 第三步：定义元规则。 元规则可以根据分析者的经验、期望或对数据的直觉来定义，也可以根据数 据库模式自动产生。本算法采用用户定义的方式。元规则是形如： p 1 a p 2 a a p k = q 1 八q 2 a aq r 的规则模板。其中，p i ( i = l ，2 ，k ) 和 q j ( j = l ，2 ，r ) 是谓词变量，元规则中谓词的个数为p = k + r 。 用户用元规则来说明其感兴趣的规则形式。一般元规则形成一个关于用户希 望探索或证实的、他感兴趣的关联的假定。例如： 行业( x ，y ) 八区域( x ，w ) = 税负( x ，四级) 第四步：计算p _ d 数据方体，生成频繁p 一谓词集l p 。 对元规则中定义的p 个谓词p ，p 2 ，p k ，q ，晓，q r ( k + r = p ) ，求 出所有可能的维一值对的集合，记为c p 。搜索关系数据表，对c p 中的每个元素的 山东大学硕士学位论文 出现计数，如果其大于r a i n _ s u p ，那么将它放入l p 第五步：由频繁p 一谓词集l p 产生强关联规则。 2 5 3u p _ f l p r i o r i 算法描述 算法：u p _ a p r i o r i 基于元规则找出频繁谓词集合 输入：关系数据表d ，支持度阈值m i n _ s u p ，元规则，概念层次。 输出：d 中的频繁谓词集合l p 。 方法： ( 1 ) 在d 上做o l a p 操作：列出d 中的所有谓词变量q 。( i = 1 ，2 ，q ) ，对存在 概念分层的每个谓词列出其分层，由用户选择谓词变量q 。及其分层 l e v e l 用于分析挖掘，根据q t 和l e v e l 进行数据立方体的计算，形成 新的关系数据表d 。 ( 2 ) 列出d 中的所有谓词变量，用户定义元规则： p 。ap 2 a a p k = q 八q 2 八八q r p = k + r * p 记录了元规则中的谓词变量个数衫 ( 3 ) g = 谓词p ，p 。，p k ，q 。，晓，q r ( k + r = p ) 所有可能的维一值 对的集合，搜索关系数据表，计算每个谓词的支持度，保留满足最小支 持度m i n _ s u p 的属性值，生成频繁谓词集合l p 。 f o re a c hr d f f o re a c he q ( i fr q i - q l j a n dr q k _ q l 【 1 a n d r “= q - n t h e nc c o u n t + + ： ) l * c 是形如q i j q k 1 q - n 共p 个谓词的维一值对，其中 i ，k ，m ：( 1 ，2 ，p ) ) 衫 i f c e o u n t m i n _ s u pt h e n cek ) 山东大学硕士学位论文 第三章改进的关联规则挖掘算法设计 由于关联规则挖掘的核心问题是频繁项目集的计算，因此，我们在改进关联 规则算法上，将重点放在提高生成频繁项目集的效率方面。因为传统的频繁项目 集生成算法a p r i o r i 在计算候选项集的支持度方面存在以下不足：例如算法在第 k 轮的递推中，对数据库中的每个事务t 的所有k 阶子项集，都要判断其是否在 k 阶候选项集中。虽然a p r i o r i 采用了h a s ht r e e 和h a s ht a b l e 表技术来降低 这个过程的复杂性，但是当k 较小时( k 4 ) 其计算量就能占到执行时间的9 0 以上，可见效果很不理想。鉴于此，我们设计了一种改进的频繁项目集生成算法 s u p _ a p r i o r i ，该算法主要采用下列技术来提高运算效率： 对事务数据集两次剪枝。在s u p _ a p r i o r i 中采用对事务数据集的两次剪 枝和对侯选项集的剪枝方法，不使用h a s ht a b l e ，减少建立h a s ht a b l e 的开销。 采用数组结构计算侯选项集的支持度。在s u p _ a p r i o r i 中不采用h a s h t r e e 数据结构来计算频繁集，而采用两个一维数组建立基于连续分区的、可快 速查找的数据存储结构，提高直接检索的效率，完成侯选项集的搜索和支持度的 计数。 3 1s u p _ a p r i o r i 中事务数据集剪枝 s u p _ a p r i o r i 在每次迭代中( 设第k 次) ，产生一个剪枝的事务数据集吣， 在下一轮迭代中使用。d 比d k 包含较少的事务，同时事务的平均长度也会变 小，从而减少扫描事务数据集的花费。s u p _ a p r i o r i 采用两个层次的剪枝：k 剪 枝和k + i 剪枝。 3 1 1k 剪枝 t i ( t i t ) 至少应出现在k - 1 个( k - 1 ) 频繁项目集中，否则在下轮迭代中t i 被 剪枝。在第k 轮迭代中( k 1 ) ，采用k 剪枝技术，对d k 中的每个事务t 进行剪 山东大学硕士学位论文 枝，形成剪枝后的事务t 。k 剪枝基于以下性质：事务t 包含一个k 阶频繁项目 集i ，则i 的所有( k - 1 ) 阶子项目集都是k l 阶频繁项目集。 如果检查i 的所有( k 一1 ) 子项目集是否都是频繁项目集，则需要花费非常 大的代价。注意到，任何k 项集i ( i t ) ，其( k - 1 ) 子项集恰好有k 个，且任何 属于i ( i t ) 的项目在这样的( k 一1 ) 子项集中仅出现k - 1 次。因此，可以得出这 样的结论：即若要在事务t 中保留项目t i ，那么t i 至少出现在k - 1 个( k - 1 ) 频 繁项集中。t 经过k 剪枝得到t ，若t 所包含的项目数n 7 k - 1 。经过k 剪枝， 若事务t 的项目数小于k ，则事务t 被略过，因为它不可能包含任何k 一频繁项 目集。 3 1 2k + i 剪枝 在对每个事务t 的子项集计数时，进行k + i 剪枝。经过k 剪枝得到的事务 t ，再经过k + i 剪枝得到t ”。k + i 剪枝基于以下性质：事务t i 包含一个频繁( k + 1 ) 项目集i 的必要条件是i 的所有k 阶子项集属于l k ( 频繁k 项目集) 。t i 中所有 不出现在频繁k 项集的项目将被剪枝。但进行k + i 剪枝时，h 尚未产生。因为 q 是l k 的超集，可以使用要求较弱的必要条件对t 进行剪枝，即检查是否( k + 1 ) 项集i ( i t 。) 的所有k 阶子项集属于c k 。只有t 的项目至少包含于一个( k + 1 ) 项集i ，且i 的所有k 项子集属于c k ，该项目才能被继续保留在t ”中。t 经过剪 山东大学硕士学位论文 枝得到t ”，若t 的项目数m ” i k 3 2 s u p _ _ a p r i o r i 中候选集剪枝 s u p _ a p r i o r i 中候选项集的剪枝与a p r i o r i 类似。c k 较大时，涉及的计算量 就大。为了压缩侯选项集c k ，s u p _ _ a p r i o r i 利用下列性质进行剪枝：任何非频繁 的( k - 1 ) 一项集都不可能是频繁k 一项集的子集；如果个侯选k 一项集的( k - 1 ) 山东大学硕士学位论文 子集不在h 一- 中，则该侯选项集也不可能是频繁的，可以从q 中删除。具体方法 是： f o ra l li t e m s e t sc gd o f o ra l l ( k - 1 ) - s u b s e t sso fcd o i f ( s 芒u 【一1 ) t h e l l d e l e t ecf r o mc k ： 3 3 s u p _ a p r i o r i 中频集的计算 a p r i o r i 最大的工作量是前几轮的迭代。通过实验可以发现，在多数情况下， k 2 时，在每次循环中，对每个事务t ，都必须检查是否其任何c ，个k 项集在c k 中。最简单的方法是产生t 的所有可能的k 一子项集，然后依次检查是 否是q 中的候选项集。a p r i o r i 采用h a s ht r e e 技术使搜索限制在c k 的一个子 集中。s u p _ a p r i o r i 利用两个一维数组，建立一种可快速搜索定位的数据结构， 山东大学硕士学位论文 将侯选项集序列划分为若干连续的分区( p a r t i t i o n ) ，形成侯选项集的若干不相 交的子集。划分的依据是侯选项集的前两个项目。第一个数组存放有序的侯选项 集频度计数器；第二个数组记录各分区开始位置的指针。设q 是有序的，则候 选项集中任何前两项相同的项目子集将存在于c k 中的一个连续的区间内。设计 大小为c 孟的一维数组e n t r y ，作为直接访问入口。e n t r y 的每个单元存放 一个指针，指向具有给定2 项前缀的第一个候选项集的位置。与k = 2 相似，项集 c ( c l ，e 2 ，c k ) 在e n t r y 中的位置为e k ( c l ，c 2 ) 。数据结构如图3 1 所示： e n t r y k h ( 3 。4 )e k ( 4 。5 ) 以 _ 3 。4 )( 3 ，4 ) ( 4 ，5 ) 图3 1 基于分区的数组结构图 与k = 2 时相似，为取得e k ( c ，c 。) ，需设计函数h k ，输入为n k ，输出为 1 ，n k ) ， 则e k ( c 。c 。) 可定义为： x 广1 e k ( c 1 ，c d = ( n l _ i ) + ( x 2 _ x i ) = m ( x 广1 ) 一x l ( x 广1 ) 2 + x 2 一x l i = l 其中x l = h k ( c 1 ) ，x 2 = h k ( c 2 ) 例：设k = 3 ， n a = 2 ，3 ，4 ，5 ，6 ) ， k = “2 ，3 ) ，( 2 ，4 ) ，( 2 ，5 ) ，( 2 ，6 ) ，( 3 ，4 ) ，( 3 ，5 ) ，( 3 ，6 ) ，( 4 ，5 ) ，( 4 ，6 ) ，( 5 ，6 ) ， 山东大学硕士学位论文 则 c a = “2 ，3 ，4 ) ，( 2 ，3 ，5 ) ，( 2 ，3 ，6 ) ，( 2 ，4 ，5 ) ，( 2 ，4 ，6 ) ，( 2 ，5 ，6 ) ，( 3 ，4 ，5 ) ，( 3 ，4 ，6 ) ，( 3 ，5 ，6 ) ，( 4 ，5 ，6 ) ) ， 则c 3 、e 3 ( c 1 ，c 2 ) 之间的对应关系如表3 - 2 所示： 岛 变换后的 前缀对 前缀对 e 3 ( c 1 e d 序号项集 ( c l ，c 2 ) ( x l ，x d 1 2 ，3 ，4 2 ，3 1 ，2 1 2 2 ，3 ，52 ，3 1 ，2 l 3 2 ，3 ，62 ，31 ，2 1 4 2 ，4 ，52 ，41 ，3 2 5 2 ，4 ，62 ，4 1 ，3 2 6 2 ，5 ，62 ，51 ，4 3 7 3 ，4 ，53 ，42 ，3 5 8 3 ，4 ，63 ，42 ，3 5 9 3 ，5 ，63 ，5 2 ，4 6 1 0 4 ，5 ，64 ，53 ，4 8 表3 - 2c a 、e 3 ( c l ，c d 之间的对应关系表 山东大学硕士学位论文 变换后的前缀对( x 。x ：) 与入口指针e n t r ye i 间的对应关系如表3 - 3 所示： 变换后 e n t r y f i 变元i 前缀对 ( 该前缀对在c 3 中的起始位置) 1 。211 1 。324 1 ，436 l ，5 4n u l l 2 ，357 2 ，4 69 2 。5 7 n u l l 3 ，4 81 0 3 59n u l l 4 ，5 1 0n u l l 表3 - 3 ( x 1 ，x ：) 与e n t r y i 间的对应关系表 若给出某个事务的某3 一项集为( 2 ，4 ，6 ) ，其前缀对为( 2 ，4 ) ，变换后为( 1 ， 3 ) ，计算e 3 ( c l ，c 2 ) = e z ( 2 ，4 ) = 2 ，e n t r y ( 2 ) = 4 ，则项集( 2 ，4 ，6 ) 在岛中位 于前缀为( 2 ，4 ) 的区段，起始位置为4 ，终止位置为5 ，这样就可以将搜索限 定在位置 4 ，5 之间，从而提高搜索和计数的效率。 2 、算法设计 首先选取t 中所有k 项集的所有长度为2 的前缀。设事务中项目的排列都是 有序的，当前缀“i t ，t i 2 ) 被选择，则共享此前缀的所有k 项集一定在 t i 2 + l ，t i 2 + z t l t | ) 中。为检查某k 项集，需要访问的瓯的连续区间界于以下入口 之间： e n t r ye e k ( t i l ，t i 2 ) ，e n t r y e k ( t i l ，t i 2 ) + 1 ) ，且检查可限制在后 缀从t i ”1 开始往后的项目。 为进一步提高候选项集搜索和计数算法的效率，设计数组l o c 1 m 。l o c i t i 存放t 。在t 中的位置，若t i 不在t 中，则l o ce t i = o 。给定候选项集c = ( c 。，c k ) 。 山东大学硕士学位论文 检查其在t _ t “t l t i ) 中的存在性，若存在项目t l ，l o c t d = 0 ，则c 不可能包 含在t 中。同时，由于c k 和t 的有序性，若l o c c 1 0 ( e l 在t 中) ，但下式成 立： ( i t i l o c c 。 ) ( k i ) 则c 不可能包含于t 中。 例：有关参数同前例。设m - f 1 ，2 ，3 ，4 ，5 ，6 ，t = ( 2 ，4 ，6 ) ，其中( 2 ，4 ) 为前 缀对，需要访问的c 3 的连续区间界于以下入口之间： 4 ，6 ) l o c 1 = o ，l o c 2 = 1 ，l o c 3 = 0 ，l o c 4 = 2 ，f o e 5 】= o ，l o c 6 = 3 。当搜索到c 3 中的侯选项集( 2 ，4 ，5 ) 时，注意到i o c 5 ：o ，因此侯选项集 2 ，4 ，5 ) 不可能包 含于t 中，可以略过。 例：有关参数同前例。设m _ 1 ，2 ，3 ，4 ，5 ，6 ) ，若t = ( 1 ，2 ，3 ，4 ，5 ，6 ) ，k = 5 时， 当搜索到c 5 中的侯选项集c = 1 2 6 7 8 )