（计算机软件与理论专业论文）一种关联规则数据挖掘算法的设计与实现.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：日期：型堕乡广 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名红期 山东大学硕士学位论文 摘要 在基于关联规则的数据库挖掘技术中，制约数据挖掘效率的关键问题是 频繁项目集的计算问题( f re qu e n ti t e m s e tc o ur l t i n g ，f i c ) 。当事务数 据库和所包含的项目的数量很大时，频繁项集的数目也会变的非常大，导致 频繁项集计数问题所花费的时间代价很高。a p r i o r i 算法采用递推方法产生 频繁项目集，是解决f i c 问题的有效的算法之一，但a p r i o r i 在计算候选 项集的支持率方面仍然存在一些效率问题。本文对基于关联规则的数据挖掘 算法进行了研究，对经典的频繁项集计数算法进行了改进，提高了关联规则 数据挖掘的效率，并应用改进算法对税收数据信息库进行了实验性挖掘分 析。主要包括：首先，对关联规则数据挖掘算法研究进行了回顾，简要讨论 了经典算法及其优化算法的特点，分析了经典算法的不足。第二，设计一种 新的频繁项目集生成算法t p p c ，对候选项集数据存储结构和候选项集支持 度计算方法进行了研究改进。t p p c 主要采用了事务数据集、侯选项集的三 次剪枝和侯选项集的分区搜索计算技术。t p p c 首先利用a p r i o r i 性质进行 候选项集的剪枝。其次在各轮迭代中采用两个层次的事务数据集剪枝一k 和k + l 剪枝。k 剪枝和k + 1 剪枝基于以下性质：事务t 包含一个k 阶频繁 项目集i ，则i 的的所有( k - 1 ) 阶子项目集都是k 一1 阶频繁项目集：事务 t 包含一个频繁( k + 1 ) 项集i 的必要条件是i 的所有k 阶子项集属于l 。 在第k 轮迭代产生一个剪枝的事务数据库d 。，使每轮迭代使用的事务数据 集能包含事务减少，事务平均长度也不断减小，从而减少事务数据库的扫描 开销。t p p c 在频繁项目集计数算法上的改进：利用两个一维数组，建立一 种可快速搜索定位的数据结构，将侯选项集序列划分为若干连续的分区，形 山东大学硕士学位论文 成侯选项集的若干不相交的子集，将搜索和计数限定在相应的区间范围，从 而提高频繁项集搜索和计数的效率。通过在多个实验数据集上与a p r io r i 算法的对比测试，其中包括运行时间、最大占用内存情况、事务数据集剪枝 情况等，表明频繁项目集生成效率得到大幅提高，t p p c 相对a p r i o r i 可提 高运行速度l0 倍以上。本文还对t p p c 算法的时间复杂性和数据集扫描次 数进行了分析。第三，对数据挖掘技术应用于税收决策分析进行了研究。我 们对税收基础数据库数据进行了抽取，进行离散化、格式转换等预处理工 作，使关系数据库转变为事务数据集，建立了可供关联规则发现的数据挖掘 文件，并尝试采用本文提出的算法对纳税资料数据集进行关联规则挖掘实 验，结合税收管理实际对实验结果进行了分析。实验初步表明，通过对给定 的纳税数据推导出涉税经济指标与违章情况的关联规则，可以发现偷漏税异 常情况规律，有效地协助税务机关进行决策分析。 关键词数据挖掘关联规则算法设计实现 山东大学硕士学位论文 a nd e s i g na n di m p l e m e n t a t i o no fd a t a m i n i n ga l g o r i t h m f o rm i n i n ga s s o c i a t i o nr u l e s a b s t r a c t f o rd a t a m i n gt e c h n i q u eo fa s s o c i a t i o nr u l e s ，t h e p r o b l e mo ff r e q u e n ti t e m s e t c o u n t i n g ( f i e ) t h e r ei sac r u c i a lf a c t sw h i c ho b v i o u s l yi n f l u e n c e st h ee f f i c i e n c yo fd a t a m i n i n g w h e nt h en u m b e ro fi t e m si n c l u d e di nt h ed a t a b a s ea r eh u g e ，t h en u m b e ro ff r e q u e n t i t e m s e t sb e c o m e sv e r yl a r g e ，a n dt h ef i cp r o b l e mv e r ye x p e n s i v et os o l v ei nt i m e a p r i o r ii s o n eo ft h em o s te f f e c t i v ea l g o r i t h m sp r o p o s e df o rs o l v i n gt h ef i cp r o b l e m ，w h i c hi t e r a t i v e l y s e a r c h e sf r e q u e n ti t e m s e t s b u ta p r i o r is t i l lh a ss o m ep r o b l e m si ne f f i c i e n c y i nt h i sa r t i c l e ， w ea n a l y s et h ea l g o r i t h mo fd a t am i i l i n gf o ra s s o c i a t i o nr u l e s a n di m p r o v et h ec l a s s i c a l g o r i t h mf o rf r e q u e n ti t e m s e tc o u n t i n gb yi m p r o v i n gt h ee f f i c i e n c yo f d a t am i n i n g f i r s t l y w er e v i e wt h er e c e n t l ys t d u y so 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 m ，a n dd i s c u s st h ef e a t u r e o fc l a s s i ca n dm o d i f i e da l g o r i t h m w ea l s oa s s a yt h ew e a k n e s so ft h ec l a s s i ca l g o r i t h m s e c o n d l y w ep r e s e n tan e wf i ca l g o r i t h mw i t l lan e wd e s i g no fd a t as t r u c t u r ea n ds u p p o r t c o u n t i n gt e c h n i q u ef o rc a n d i d c a t es e t s ，c a l l e dt p p c ，w h i c hg r e a t l yi m p r o v et h ee f f i c i e n c y f o rf i cc o n t r a s tt oa p r i o r ii ne x p e r i m e n tw i t has e r i e so fs y n t h e t i cd a t a s e t s t p p cu s et h e t e c h n i q u eo ft r i p l ep r u n i n ga n dp a r t i t i o n a lc o u n t i n g f i r s t ，t p p ca p p l yc a n d i d c a t es e t s p r u n i n g t h e n , t p p ca p p l yt w i c ep r u a i n gt ot r a n s a c t i o ns e t ka n dk + lp r u n i n g a tt h e i t e m t i o nk t p p cp r o d u c eap r u n e dd a t a s e td k + 1w h i c hc o n t a i n sf e w e rt r a n s a c t i o n sa n d s h o r t e ra v e r a g el e n g t ho ft r a n s a c t i o n t h u scanr e d u c e 血ec o s to fs c a n i n gd a t a b a s e t p p c i m p r o v ef i ca l g o r i t h mb yt w oo n e d i m e n s i o na r r a y i tb u i l dad a t as t r u c t u r ef o rf a s t s e a r c h i n ga n dl o c a t i n g ，w h i c hd i v i d et h el i s to fc a n d i d a t es e t si n t os o m ec o n t i n o u sp a r t i t i o n ， m a k i n gs e v e r a li n d e p e n d e n ts u b s e t 1 1 1 es e a r c h i n ga n dc o u n t i n gc a nb er e s t r i c t e di n c o r r e s p o n d i n gp a r ti no r d e rt oi m p r o v et h ee f f i c i e n c y e x p e r i m e n t sw i t has e r i e so fs y n e t i c d a t a s e t sh a v es h o w nt h a tt p p cm a k eb e t t e rp e r f o r m a n c et h a na p r i o r ib ye v e nm o r et h a none o r d e ro fm a g n i t u d e w ea l s od i s s c u st h et i m ec o m p l e x i t yo ft p p c a n ds t u d yt h ef r e q u e n c y o fs c a n n i n gt h ed a t a b a s e t h i r d l y ，w ea p p l yd a t am i n i n gt e c h n i q u et ot a xa n a l y s i sa n d d e c i s i o n m a k i n gp r o j e c t w ed oe x p e r i m e n ta b o u ta s s o c i a t i o nr u l ed m a m i n gw i t hb a s i ct a x i n f o r m a t i o nu s i n gt h ea l g o r i t h mi nt h i sa r t i c l e ，a n da n a l y s et h er e s u l to ft h ee x p e r i m e n t c o n s i d e r i n gt h ep r a c t i c a lt a xm a n a g e m e n t k e y w o r d sd a t a m i n i n ga s s o c i a t i o nr u l e sa l g o r i t h md e s i g na n di m p l e m e n t a t i o n 3 山东大学硕士学位论文 符号说明 具有k 个项目的频繁项目集： 具有k 个项目的侯选项目集集合： 第i 个侯选项目集； 初始事务数据集： 第k 轮迭代生成的中间事务数据集 某个事务； 事务t 中的第i 个项目： 空集 _ _ h 文 队 队 卜 “o 山东大学顾士学位论文 l 引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够 对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可 以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关 系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐 藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。 计算机技术的另一领域一一人工智能自1 9 5 6 年诞生之后取得了重大进 展。经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是 机器学习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法 有神经网络、遗传算法等。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大 量数据背后的知识，这两者的结合促成了数据库中的知识发现( k d d ： k n o e d g ed i s o ov e p y y nd a t a b a s e s ) 的产生。实际上，数据库中的知 识发现是一门交叉性学科，涉及到机器学习、模式识别、统计学、智能数据 库、知识获取、数据可视化、高性能计算、专家系统等多个领域。从数据库 中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许 多方面。 数据挖掘是k d d 最核心的部分，是采用机器学习、统计等方法进行知 识学习的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前 大多数的研究都集中在数据挖掘算法和应用上。人们往往不严格区分数据挖 掘和数据库中的知_ i ： 发现，把两者混淆使用。一般在科研领域中称为k d d ， 而在工程领域则称为数据挖掘。其中关联规则( a s s 0c i a t i0nr u les ) 的 挖掘是一个重要的问题。 数据挖掘是一个完整的过程，该过程从大型数据库中挖掘先前未知的， 有效的，可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境可示意如下图： 多 骓斗 o 山东大学硕士学位论文 图表一l 数据挖掘环境框图 数据挖掘的任务是从数据中发现模式。模式是一个用语言l 来表示的一 个表达式e ，它可用来描述数据集f 中数据的特性，e 所描述的数据是集合 f 的一个子集f e 。e 作为一个模式要求它比列举数据子集f e 中所有元素的 描述方法简单。例如，“如果成绩在8 1 9 0 之问，则成绩优良”可称为一 个模式，而“如果成绩为8 1 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ， 则成绩优电”就不能称之为一个模式。 模式有很多种，按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描述型 ( d e s c r i p t i v e ) 模式。 预测型模式是可以根据数据项的值精确确定某种结果的模式。挖掘预测 型模式所使用的数据也都是可以明确知道结果的。例如，根据各种动物的资 料，可以建立这样的模式：凡是胎生的动物都是哺乳类动物。当有新的动物 资料时，就可以根据这个模式判别此动物是否是哺乳动物。 描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性 把数据分组。描述型模式不能直接用于预测。例如，在地球上，7 0 的表面 被水覆盖，3 0 是土地。 在实际应用中，往往根据模式的实际作用细分为以下6 种： 1 分类模式 分类模式是一个分类函数( 分类器) ，能够把数据集中的数据项映射到某 个给定的类上。分类模式往往表现为一棵分类树，根据数据的值从树根开始 搜索，沿着数据满足的分支往上走，走到树叶就能确定类别。 2 回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测 值是离散的，回归模式的预测值是连续的。如给出某种动物的特征，可以用 分类模式判定这种动物是哺乳动物还是鸟类：给出某个人的教育情况、工作 经验，可以用回归模式判定这个人的年工资在哪个范围内，是在6 0 0 0 元以 下，还是在6 0 0 0 元到1 万元之间，还是在1 万元以上。 3 时间序列模式 6 山东大学硕士学位论文 时间序列模式根据数据随时问变化的趋势预测将来的值。这里要考虑到 时间的特殊性质，像一些周期性的时间定义如星期、月、季节、年等，不同 的日子如节假日可能造成的影响，日期本身的计算方法，还有一些需要特殊 考虑的地方如时间前后的相关性( 过去的事情对将来有多大的影响力) 等。只 有充分考虑时间因素，利用现有数据随时间变化的一系列的值，才能更好地 预测将来的值。 4 聚类模式 聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差 别尽可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组和什 么样的组，也不知道根据哪一( 几) 个数据项来定义组。一般来说，业务知识 丰富的人应该可以理解这些组的含义，如果产生的模式无法理解或不可用， 则该模式可能是无意义的，需要回到上阶段重新组织数据。 5 关联模式 关联模式是数据项之间的关联规则。关联规则是如下形式的一种规则： “在无力偿还贷款的人当中，6 0 的人的月收入在3 0 0 0 元以下。” 6 序列模式 序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。为 了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时 间。例如，在购买彩电的人们当中，6 0 的人会在3 个月内购买影碟机。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是 使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督 知识，因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准 确性，模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使 用一部分数据作为样本，用另一部分数据来检验、校正模式。聚类模式、关 联模式、序列模式则是非监督知识，因为在模式建立前结果是未知的，模式 的产生不受任何监督。 如前所述，数据项之间的关联规则成为关联模式。我们所要讨论的问题 集中在数据挖掘中的关联规则( m i n i n ga s s o c i a t i o nr u l e s ) 上，也就是上述 六个模式中的第五个。关联规则是发现交易数据库中不同商品( 项) 之间的 联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品 山东大学硕士学位论文 的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买 模式对用户进行分类。关联规则是关联模式的基础，而序列模式与关联模式 相仿，只是更进一步把数据之间的关联性与时间联系起来。在税务管理中， 关联规则数据挖掘可以有效地协助税务机关进行决策分析。如根据对纳税人 已有纳税资料的分析，进行涉税项目之间的关联分析，从而对纳税人进行 分类管理，重点加强对偷、漏、欠税户的管理；还可以根据纳税人已有纳 税信息和违章情况，进行关联分析，找出涉税经济指标与可能违章手段之间 的联系，发现偷、漏税疑点，为税收分析和决策提供依据，提高税务稽查和 日常税收管理的效率。 本文主要对关联规则数据挖掘的有关算法进行设计与实现，分析了频繁 项目生成算法、规则产生算法等经典算法的问题和不足，对经典算法进行了 改进，并在多种数据集环境下进行了实验。本文的总体安排如下：第二部分 介绍关联规则有关概念和算法，回顾领域内的相关工作；第三部分是频繁项 目集生成算法的设计与实现，包括对经典算法a p r i o r i 的分析与改进，改 进算法设计、实现与实验结果分析：第四部分是关联规则分析在税务管理中 的研究与探讨及应用实验。 2 基于关联规则的有关概念及相关工作 2 1 关联规则的概念 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出 现了物品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事 务中的出现相互之间是否有规律可循呢? 在数据库的数据挖掘中，关联规则 就是描述这种在一个事务中物品之间同时出现的规律的知识模式。更确切的 说，关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的影 响。 现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大 量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处 理时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式 如下的关联规则：在购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。 山东大学硕士学位论文 这些关联规则很有价值，商场管理人员可以根据这些关联规则更好地规划商 场，如把铁锤和铁钉这样的商品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集 合，但稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保 险，一份保单就是一个事务。保险公司在接受保险前，往往需要记录投保人 详尽的信息，有时还要到医院做身体检查。保单上记录有投保人的年龄、性 别、健康状况、工作单位、工作地址、工资水平等。这些投保人的个人信息 就可以看作事务中的物品。通过分析这些数据，可以得到类似以下这样的关 联规则：年龄在4 0 岁以上，工作在a 区的投保人当中，有4 5 的人曾经 向保险公司索赔过。在这条规则中，“年龄在4 0 岁以上”是物品甲， “工 作在a 区”是物品乙，“向保险公司索赔过”则是物品丙。可以看出来，a 区可能污染比较严重，环境比较差，导致工作在该区的人健康状况不好，索 赔率也相对比较高。 2 2 关联规则的形式 设i = i l ，i2 ，i m 是一组物品集( 一个商场的物品可能有上万 种) ，d 是一组事务集( 称之为事务数据库) 。d 中的每个事务t 是一组物 品。显然满足t 互i 。称事务t 支持物品集x ，如果x c t 。关联规则是如下形 式的一种蕴含：x y ，其中x c _ i ，y i ，且xny = m 。 ( 1 )称物品集x 具有大小为s 的支持度，如果d 中有s 的事务支持 物品集x ： ( 2 ) 称关联规则x y 在事务数据库d 中具有大小为s 的支持度，如果 物品集xuy 的支持度为占： ( 3 ) 称规则x y 在事务数据库d 中具有大小为c 的可信度，如果d 中 支持物品集x 的事务中有c 的事务同时也支持物品集y 。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷 多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规 则感兴趣。一般称满足一定要求的( 如较大的支持度和可信度) 的规则为强规 则。因此，为了发现出有意义的关联规则，需要给定两个闽值：最小支持度 和最小可信度。前者即用户规定的关联规则必须满足的最小支持度，它表示 山东大学硕士学位论文 了一组物品集在统计意义上的需满足的最低程度：后者即用户规定的关联规 则必须满足的最小可信度，它反应了关联规则的最低可靠度。 在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念 间存在一种层次关系，如夹克衫、滑雪衫属于外套类，外套、衬衣又属于衣 服类。有了层次关系后，可以帮助发现一些更多的有意义的规则。例如”买 外套一买鞋子”( 此处，外套和鞋子是较高层次上的物品或概念，因而该规则 是一种泛化的关联规则) 。由于商店或超市中有成千上万种物品，平均来 讲，每种物品( 如滑雪衫) 的支持度很低，因此有时难以发现有用规则：但如 果考虑到较高层次的物品( 如外套) ，则其支持度就较高，从而可能发现有用 的规则。 另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物 品时，除了具有上述关联规律，还有时间上或序列上的规律，因为，很多时 候顾客会这次买这些东西，下次买同上次有关的一些东西，接着又买有关的 某些东西。 2 3 有关关联规则挖掘算法及讨论 a g r a w a l 等人于19 93 年 1 首先提出了挖掘顾客交易数据库中项集间 的关联规则问题，其核心方法是基于频集理论的递推方法。以后诸多的研究 人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算 法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效 率；提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应 用进行推广。 2 3 1 核心算法 a g r a w a l 等 1 在l9 9 3 年设计了一个基本算法，提出了挖掘关联规则 的一个重要方法一这是一个基于两阶段频集思想的方法，将关联规则挖掘 算法的设计可以分解为两个子问题： 1 ) 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为 频集( f r e q u e n ti t e m s e t ) ，由a p r i o r i 算法实现。 2 ) 使用第1 步找到的频集产生期望的规则。即利用大项集( 1 j t e m s e t s ) 产生所需的规则( r u e s ) 。算法的思想在于：如果说a b c d 和a b 是大项集， 我们就可以通过计算可信度，也就是c o n f = s u p p o r f ( a b c d ) 1 0 山东大学硕士学位论文 s u p p o r t ( a b ) ，并通过c o n f m i n i c o n f 来确定规则a b c d 是否确立 ( 该规则由于a b c d 是大项集故肯定具有最小支持度) 。 这里的第2 步相对简单一点。如给定了一个频集y = i 。i 。i 。，k 2 ，i 。i ，产生只包含集合f i 。，i2 ，i 。 中的项的所有规则( 最多k 条) ，其中每条规则的右部只有一项，( 即形如 y i ； = i ；，l i k ) ， 这里采用的是 4 中规则的定义。一旦这些规则被生成，那么只有那些大于 用户给定的最小可信度的规则才被留下来。 为了生成所有频集，使用了递推的方法。其核心思想如下： ( 1 ) l 1 = ( 1 a r g e1 一i t e m s e ts ： ( 2 ) f o r ( k = 2 ：lk _ i o ：k + + ) d ob e g i n ( 3 ) c k = a p r io r i g e n ( l ) ；新的候选集 ( 4 )f o r a i lt r a n s a c t i o d st dd ob e g in ( 5 )c t = s ubse t ( c k ，t ) ： 事务t 中包含的候选集 ( 6 )f o r a 1 1c a n d id a t esc c td o ( 7 )c c o u n t + + ： ( 8 )e n d ( 9 )l k = c c kc c o u n t m i ns u p ) ( 10 ) e n d ( 1 1 ) a ns w e r = uk l k ： 图表一2a p r i o r i 算法 a p r io r i g e n 函数( 图表- 3 ) 数，返回所有大七一项集的集合l 。， 以l 。( 所有大( 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 ，p i t e m k 一1 ，9 i te m k - 1 f r o ml k l p ，l k 一1g w h e r ep i t e m l = q i te m l ，p i t e m k 一2 = q i t e m k 一2 ，p i t e m k 一1 q i te m k i ： 山东大学硕士学位论文 第二步，剪枝( p r u n i n g ) ，如果存在。的( k 1 ) 一子序列不包含于 k - l 之中，则删除所有项集c c k 。 f o r a l li t e m s e tsc 孤d o f o r a l l ( k 一) 一s u bs e tsso fcd 0 i f ( s 萑l k 一- ) t h e n d e 】e t ecf r o mc k ： 图表一3a p t io r i g e n 函数 首先产生频繁卜项集l 1 ，然后是频繁2 一项集l 2 ，直到有某个r 值使 得l r 为空，这时算法停止。这里在第k 次循环中，过程先产生候选k 一项集 的集合c k ，c k 中的每一个项集是对两个只有一个项不同的属于l 。的频集 做一个( k 一2 ) 一连接来产生的。c k 中的项集是用来产生频集的候选集，最后 的频集l k 必须是c k 的一个子集。c k 中的每个元素需在交易数据库中进行 验证来决定其是否加入l 。，这里的验证过程是算法性能的一个瓶颈。这个方 法要求多次扫描可能很大的交易数据库，即如果频集最多包含10 个项，那 么就需要扫描交易数据库l0 遍，这需要很大的i 0 负载。 在论文 3 中，a g r 8 w a l 等引入了修剪技术( p r u n i n g ) 来减小候选集 ck 的本小，由此可以显著地改进生成所有频集算法的性能。算法中引入的 修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频 集。那么，如果c k 中某个候选项集有一个( k 一1 ) 一子集不属于l 。，则这个 项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的 支持度的代价。 在文 3 中，还引入杂凑树( h a s ht r e e ) 方法来有效地计算每个项集 的支持度。在产生侯选项集c k 后，a p r io r i 生成一个h a s ht r ee ，h as h t r e e 的每个叶子包含指向候选集和相应计数器的指针。在h a s ht r ee 中插 入候选项集以及在每个交易的子集中查找侯选项集c k 时，都使用一个简单的 h a s h 函数：h a s h ( i ) = im o dh ，其中h 1 ) ，采用k 剪枝技 术，对d 。中的每个事务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 。，那么t 。至少出现在k 一1 个( k 1 ) 频繁项集中。t 经过k 剪枝得到t ，若t7 所包含的项目数n k 则事务t 可以被略过而不参加计数。 例3 1 1 设k = 3 ，若事务t = 1 ，2 ，3 ，4 ，5 ，6 ，l2 = ( 1 ，2 ) ， ( 1 ，6 ) ，( 2 ，3 ) ，( 2 ，6 ) ，( 3 ，6 ) ，( 4 ，6 ) ，则要求项目l ，2 ，3 ，4 ，5 ，6 至少在l ，中出现2 次。这样t 经过剪枝后得t ： l ，2 ，3 ，6 ) ，项目4 和项目 5 被剪枝。 为了便于检查这个条件，t p p c 建立一个一维数组p 。 n ，每个单元代 表一个项目的计数器。对每一个属于l 。的( k 1 ) 频繁项目集，出现在其中 的项目所对应的计数器都增加1 。经过统计，对于每个项目t 。( 1 i n ) ， 得到一个计数值p 。 t i 。t ；t 被保留在t 中的必要条件是pk _ l t 。 k l 。经过k 剪枝，若事务t 的项目数小于k ，则事务t 被略过，因为它不可 能包含任何k 一频繁项目集。 定义2 ：k + l 剪枝( 或称候选集剪枝) 。在对每个事务t 的子项集计数 时，进行k + 1 剪枝。经过k 剪枝得到的事务t ，再经过k + 1 剪枝得到t ”。 k + 1 剪枝基于以下性质：事务t 包含一个频繁( k + 1 ) 项集i 的必要条件是 i 的所有k 阶子项集属于lk ( f re q uen tk i temse t ) 。t 中所有不出现 山东大学硕士学位论文 在频繁k 项集的项目将被剪枝。但进行k + 1 剪枝时，l 。尚未产生。因为c 。 是l 。的超集，可以使用要求较弱的必要条件对t 进行剪枝，即检查是否 ( k + 1 ) 项集i ( i t 。) 的所有k 阶子项集属于c 。只有t 的项目至少包含 于一个( k + 1 ) 项集i ，且i 的所有k 项子集属于c 。，该项目才能被继续保 留在t ”中。t 经过剪枝得到t ”，若t ”的项目数m ” n “i k 3 2 候选项目集的剪枝 候选项集的剪枝与a p r io r i 类似。c k 较大时，涉及的计算量就大。为 了压缩候选项集c k ，t p p c 利用下列性质进行剪枝：任何非频繁的( k 一1 ) 一 项集都不可能是频繁k 项集的子集；如果一个侯选k 一项集的( k 1 ) 子集 山东大学硕士学位论文 不在l 。中，则该候选项集也不可能是频繁的，可以从c k 中删除。具体方 法是： f o r a l li t e m se tsc c kd o f o r a l l ( k 1 ) 一s u bse tsso fcd o i f ( s 匹l k 1 ) t h e n d e 】e t ecf r o mc k ： 3 3 频繁k 项集的计数算法 a p r i0 r i 最大的工作量是前几轮的迭代。通过实验可以发现，在多数情 况下，k 2 时计算l k 在第k 次循环时，定义项目集合n 。，n 。只包含未被“k 剪枝”剪除的 有意义的项目。设r tk = n 。f ，n 。n ( n 为事务数据库d 中所有项目的数 目) 。 l 、数据结构 k 2 时，在每次循环中，对每个事务t ，都必须检查是否其任何c ! 个 k 项集在c 。中。最简单的方法是产生t 的所有可能的k 一子项集，然后依次 检查是否是ck 中的候选项集。a p r io r i 采用h a s htre e 技术使搜索限制在 c 。的一个子集中。t p p c 利用两个一维数组，建立一种可快速搜索定位的数 据结构，将侯选项集序列划分为若干连续的分区( p a r t i t i 0n ) ，形成侯选项 集的若干不相交的子集。划分的依据是侯选项集的前两个项目。第一个数组 存放有序的侯选项集频度计数器；第二个数组记录各分区开始位置的指针。 山东大学硕士学位论文 设c 。是有序的，则候选项集中任何前两项相同的项目子集将存在于c 。中的 一个连续的区间内。设计大小为c 最的一维数组e n t r y ，作为直接访问 入口。e n t ry 的每个单元存放一个指针，指向具有给定2 项前缀的第一个 候选项集的位置。与k = 2 相似，项集c ( c 1 ，c 2 ，c 。) 在e n t ry 中的位 置为e 。( c 1 ，c2 ) 。数据结构如下图： c k 胁”n 豆卫下丽日_ 图表一5 ，基于分区的数组结构 与k = 2 时相似，为取得e 。( c 。，c 。) ，需设计函数h 。，输入为n 。，输出 为 l ，n k ) ，则ek ( c 。，c2 ) 可走义为： x 一l e k ( c i ，c2 ) = ( nk 1 = l 其中x l = hk ( c 1 ) ：x2 = hk ( c2 ) 例3 3 2设k = 3 ，n3 = f 2 ，3 ，4 ，5 ，6 ，l2 = ( 2 ，3 ) ，( 2 ，4 ) ，( 2 ，5 ) ，( 2 6 ) ，( 3 ，4 ) ，( 3 ，5 ) ，( 3 ，6 ) ，( 4 ，5 ) ，( 4 ，6 ) ，( 5 ，6 ) ，则c3 = ( 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 。、e 。( c ，c 。) 之间的对应关系如下表： c 3 前缀对变换后的前缀对e 3 ( c 1 ，c2 ) 序号项集( c i ，c2 ) ( x 1 ，x2 ) l 2 ，3 ，42 ，31 ，2 l 2 2 ，3 ，52 ，3l ，2 i 3 2 ，3 ，62 ，31 ，2 1 山东大学硕士学位论文 4 2 ，4 ，52 ，41 ，3 2 5 2 ，4 ，62 ，4l ，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 ，52 ，4 6 10 4 ，5 ，64 ，53 ，4 8 变换后的前缀对( x ，x ：) 与入口指针e n t r y i 间的对应关系 变换后前缀变元ie n t r y i ( 该前缀对在c 。中的起始 对位置) 1 211 l ，324 1 。436 l ，54n u l l 2 ，357 2 ，469 2 ，57n u l l 3 ，4810 3 ，59n u l l 4 ，5lon u l l 若给出某个事务的某3 一项集为( 2 ，4 ，6 ) ，其前缀对为( 2 ，4 ) ，变换 后为( 1 ，3 ) ，计算e3 ( c 1 ，c2 ) = e3 ( 2 ，4 ) = 2 ，e n t ry ( 2 ) = 4 ，则项集 ( 2 ，4 ，6 ) 在c 3 中位于前缀为( 2 ，4 ) 的区段，起始位置为4 ，终止位置 为5 ，这样就可以将搜索限定在位置 4 ，5 之间，从而提高搜索和计数的效 率。 2 、算法设计 山东大学硕士学位论文 首先选取t 中所有k 项集的所有长度为2 的前缀。设事务中项目的排列 都是有序的，当前缀( t ，t 。 被选择，则共享此前缀的所有k 项集一定在 ( t 。t ；：。t h i 中。为检查某k 项集，需要访问的c 。的连续区间界于以 下入口之间： e n t ry e k ( t t 2 ) ，e n t r y ek ( t t 。2 ) + 1 ) ，且 检查可限制在后缀从t 。，开始往后的项目。 为进一步提高候选项集搜索和计数算法的效率，设计数组l o c 1 ，m 。 l o c t 。 存放t 。在t 中的位置，若t 。不在t 中，则l o c t ； = 0 。给定候选 项集c = c 。c 。 ，检查其在t = t 。，t 。) 中的存在性，若存在项目t 。，l o c t ； = o ，则