1、关联规则挖掘算法研究报告摘要：数据挖掘是一个多学科交叉融合而形成的新兴的学科，它利用各种分析工具在海量数据中发现模型和数据间的关系。而在大规模事务数据库中，挖掘关联规则是数据挖掘领域的一个非常重要的研究课题。文中介绍了关联规则挖掘的研究情况，描述了经典 Apriori 算法的实现，并对该算法进行了分析和评价，指出了其不足和原因。并对 FP 树挖掘最大频繁项集的算法描述，并得到结论：数据库中潜在的最大频繁模式越多，运行时间越长。关键词：数据挖掘；关联规则；频繁项集简单地说，数据挖掘(data mining)是揭示存在于数据里的模式及数据间的关系的学科，它强调对大量观测到的数据库的处理。它是涉及数
2、据库管理，人工智能，机器学习，模式识别，及数据可视化等学科的边缘学科。用统计的观点看，它可以看成是通过计算机对大量的复杂数据集的自动探索性分析。数据挖掘也就是通过某种方法，利用历史数据，在条件集合和结果集合之间建立一个致信度比较高的模型。而关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系，它在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品（项）之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。1 关联规则
3、的意义世间万物的事情发生多多少少会有一些关联。一件事情的发生，很可能是也会引起另外一件事情的发生。或者说，这两件事情很多时候很大程度上会一起发生的。那么人们通过发现这个关联的规则，可以由一件事情的发生来，来推测另外一件事情的发生，从而更好地了解和掌握事物的发展，动向等等。这就是数据挖掘中，寻找关联规则的基本意义。数据挖掘技术中的关联规则挖掘是通过计算机自动从一大对真实数据中发现这样的关联规则出来。对于计算机而言，它需要知道所有的事情发生情况，并且把相应的事情合并成一个事务，通过对各个事务的扫描，来确定事情的关联规则。2 关联规则的基本概念设 I=i1, i2, im是项的集合，其中的元素称为项
4、(item)。记 D 为事务(transaction)T 的集合，这里事务 T 是项的集合，并且 TI 。对应每一个事务有唯一的标识，如事务号，记作 TID。设 X 是一个 I 中项的集合，如果XT，那么称事务 T 包含 X1。一个关联规则是形如 XY 的蕴涵式，这里 XI, YI，并且 XY=。规则XY 在事务数据库 D 中的支持度（ support）是事务集中包含 X 和 Y 的事务数与所有事务数之比，记为 support(XY)，即 support(XY)= P(X Y),规则XY 在事务集中的可信度（confidence）是指包含 X 和 Y 的事务数与包含 X 的交易数之比，记为 c
5、onfidence(XY)，即 confidence(XY)= P(X|Y),给定一个事务集 D，挖掘关联规则问题就是寻找支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。3 Apriori 算法介绍3.1 关联规则的挖掘可以分成两个步骤：a. 根据最小的支持度，在大量事务寻找高频率出现的频繁项集(Itemset)。b. 根据最小的置信度，找到的频繁项集产生关联规则。其中第二个步骤比较容易，一般经过第一步的筛选后的频繁项集都不会很多，通过子集产生法就可以产生关联规则。第一个步骤是需要在大量的事务数据集中寻找高频率出现的项集 Itemset，所
6、以就需要一个比较高效的搜索查找方法。Rakesh Agrawal 等在 1993 年提出了第一步搜索频繁项集的经典 Apriori 算法12,13。通过遍历一大堆事务数据中，从一个一个的单个项开始记数，每次遍历完所有的事务后，裁减掉支持度记数少于用户给定的支持度的项，然后逐步扩展到多项事务。最后保留下来的频繁项集，通过子集产生法来产生关联规则，然后去掉其中置信度低于用户指定的最低置信度的关联规则，最后剩下的就是满足用户需要的关联规则。Apriori 算法的特点就是在于从单项开始，每次剪裁一点，利用它的 Apriori 性质,有效避免了对很多不可能的项的搜索过程 2。3.2 Apriori 性质
7、频繁项集的所有非空子集都必须也是频繁的。如果项集 I 不满足最小支持度阈值 s，则 I 不是频繁的，即 P(I) s。如果项 A 添加到 I，则结果项集(I A）不可能比 I 更频繁出现。因此，(I,A)也不是频繁的，即 P(I A) s。因此，Apriori 性质主要是用于搜索频繁项集的时候对候选式的筛选过程。Apriori 算法中利用 Apriori 性质，能够比较好地避免盲目的搜索，提高频繁项集的查找效率。3.3 算法伪码算法 Apriori 是 使用逐层迭代找出频繁项集输入：事务数据库 D；最小支持度阈值。输出：D 中的频繁项集 L。3.3 基于 Apriori 算法的数据挖掘应用实例
8、数据库样本当前是列出我们实验中用到的一个候选项集：1 4 5, 1 2 4, 4 5 7, 1 2 5, 4 5 8, 1 5 9, 1 3 6, 2 3 4, 5 6 7, 3 4 5, 3 5 6, 3 5 7, 6 8 9, 3 6 7, 3 6 8。2.3.2Apriori 算法的实现过程首先设置散列函数，和叶子大小限制。根据以上限制，先根据首项形成初步的散列树，见下图：图：生成候选的散列树（原始版本）接着根据第二项形成优化后的散列树，结果见下图：图：生成候选的散列树（中间过程）按照以上过程，按照项的顺序，我们可以将树的分裂做到最后一项，最终结果见下图：图：生成候选的散列树（最终版本）
9、4 算法分析尽管 Apriori 算法的候选产生一检查方法大幅度压缩了候选项集的大小，并且导致了很好的性能，然而，有两种可能导致了这个算法开销很大。首先产生频繁 1-项集 L1，然后是频繁 2-项集 L2，直到有某个 r 值使得 Lr 为空，这时算法停止。这里在第 k 次循环中，过程先产生候选 k-项集的集合 Ck，Ck 中的每一个项集是对两个只有一个项不同的属于 Lk-1 的频集做一个(k-2)- 连接来产生的。Ck 中的项集是用来产生频集的候选集，最后的频集 Lk 必须是 Ck的一个子集。Ck 中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这
10、个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含 10 个项，那么就需要扫描交易数据库 10遍，这需要很大的 I/O 负载。例如，如果有 10 个频繁 1 项集，那么 Apriori算法需要产生 10 个候选 2 项集，并且累计和检查它们的频繁性。而且如果发现长度为 100 的频繁模式，它必须产生多达 l0 个候选。它可能需要重复扫描数据库，对于挖掘长模式扫描的次数更多 3。因此，可能产生大量的候选集, 以及可能需要重复扫描数据库，是 Apriori 算法的两大缺点。产生这种情况的原因是，在候选多项集中可能有大量的，甚至是绝大多数的项集在事务数据库中是不存在的。这样就想到了以下几种方
11、法。5FP-树频集算法针对 Apriori 算法的固有缺陷，J. Han 等提出了不产生候选挖掘频繁项集的方法FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree） ，同时依然保留其中的关联信息，随后再将 FP-tree 分化成一些条件库，每个库和一个长度为 1 的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个 FP-tree 可以放入主存中。51 定义对于项集 X T，如果 XT,如果 X.sup s，并且对于任意 XY，均有 Y.sup S，则称 X 为 D 中的最大频繁项集。显然
12、，任何频繁项集都是某最大频繁项集的子集，所以可以把发现所有频繁项集的问题转化为发现所有最大频繁项集的问题。频繁模式树 FPtree 频繁模式树 FP-tree 是一个树结构，定义如下：(1)它由一个被标记为“null”的树根节点、作为根节点孩子的子节点集合和一个频繁项头表组成。(2)每个子节点由 6 个域组成：项 ID itemld、节点计数 support、父节点指针parent、兄妹节点指针 sibling、孩子节点指针 child、指向下一个具有相同itemld 的指针 next。其中，sibling 和 child 两个域不是必需的，仅仅为方便树的遍历而建立。(3)频繁项头表 head
13、erTable 由频繁项结点 headerTableNode 组成。headerTableNSe 包括 5 个域：项 IDitemld、支持度 support、指向前一频繁项结点的指针 prev、指向后一频繁项结点的指针 next、指向 FPtree 树中与之itemld 相同的第 1 个节点的指针 headerLink。所有的频繁项结点通过 prev 指针和 FIexi 指针形成链表结构，从而构成频繁项头表。5.2 算法描述基于FP树的最大频繁模式挖掘算法，主要包括两大步骤：Stepl：构造频繁模式树FPtree。Step2：利用FPtree挖掘最大频繁模式。下面分别描述针对以上两个步骤的频
14、繁模式树的构造算法和挖掘最大频繁模式算法。频繁模式树 FPtre 的构造算法输人：事务数据库 D；最小支持数 support输出：事务数据库 D 的频繁模式树，FPtree6. PCY算法通过实验发现，寻找频繁项集的主要计算是在生成频繁 2 项集 C2 上。文献中提出一种改进算法，名为 PCY 算法，PCY 分别是提出者 Park，Chen 和 Yu 的首字母。这种算法是一种基于杂凑的算法，引入了散列技术。所谓杂凑运算，又称 hash 运算，是将任意长的输入消息串变化成固定长的输出串的一种运算。该算法的主要思想大致是：在由 1 项集生成 2 项集时，将所有生成的 2 项集通过杂凑运算散列到散列
15、表结构的不同桶中，并增加对桶的计数，去除小于支持度阈值的 2 项集从而减少 2 项集数量。文献中又提出在 PCY 算法基础上改进的两种算法，一种叫做多级算法，一种叫做多容器算法。前者将这种散列过程应用多次，进一步减少生成的 2 项集，后者在一次计算中采用多个散列表，实现运算效率的进一步提升。7. 随机算法在寻找频繁项时，不一定要把所有频繁项都挖掘出来，而是挖掘出主要的、有用的即可。就像超市针对用户购买情况进行调整时，不一定要做到兼顾所有频繁项，而是只需考虑到大部分频繁项即可。由此，文献中提出几种最多进行两次迭代的算法，实现处理速度的大大提升。首先提出一种简单算法，即随机算法。其思想较简单，即随
16、机选择数据集中的一部分样本而非全体进行关联挖掘。随后提出了一种名为 SON 的算法。这种算法是一种基于划分的算法，它的基本思想是：先把数据库从逻辑上划分成几个互不相交的块，每次单独考虑一个分块并对它生成所有可能的频繁项集，最后计算这些频繁项集的支持度。分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。这种算法是可以并行实现的，即是一种并行化产生频集的方法。8. Toivonen算法这种算法的基本思想是：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据可的剩余部分测试这个规则。这种算法十分简单，且显著地增加了运算速度，但也带来了运算不精确的缺点。这
17、是因为，所取得的数据可能是高度相关的，不能表示整个数据库中的分布情况。9小结对于关联规则挖掘领域的发展，我认为可以在如下一些方向上进行深入研究：在处理极大量的数据时，如何提高算法效率；对于挖掘迅速更新的数据的挖掘算法的进一步研究；在挖掘的过程中，提供一种与用户进行交互的方法，将用户的领域知识结合在其中；对于数值型字段在关联规则中的处理问题；生成结果的可视化，等等。参考文献：1 Denis L.Nkweteyim,Stephen C. Hirtle: A New Joinless Apriori Algorithm for Mining Association Rules. PRIS 2005: 234-243 DBLP:conf/pris/NkweteyimH05
