Apriori算法关联规则挖掘技术研究(4)
时间:2017-06-10 14:52 来源:毕业论文 作者:毕业论文 点击:次
例如：啤酒与尿布，这条规则只涉及到用户购买的物品；性别：女与职业：秘书，这条规则就涉及到两个字段的信息，是两个文上的一条关联规则。 给出了关联规则的分类之后，在下面的分析过程中，就可以考虑某个具体的方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 2.3 关联规则挖掘的算法 2.3.1 经典频集方法 Agrawal等在1993年设计了一个基本算法，提出了挖掘关联规则的一个重要方法,这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计分解为两个子问题： 第一步：找到所有支持度大于最小支持度的项集（itemset），这些项集称为频集（frequent itemset）。 第二步：使用第1步找到的频集产生期望的规则。 这里的第2步相对简单一点。如给定了一个频集Y=I1,I2...Ik，k≥2，Ij∈I，产生只包含集合{I1，I2，...，Ik}中的项的所有规则(最多k条)，其中每一条规则的右部只有一项，一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个以上项的规则，将在之后进行介绍。 为了生成所有频集，使用了递推的方法。其核心思想如下： 首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。 之后，Agrawal等引入了修剪技术来减小候选集Ck的大小，由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。之后更是引入杂凑树（Hash Tree）方法来有效地计算每个项集的支持度。 2.3.2 频集算法的几种优化方法 虽然Apriori算法自身已经进行了一定的优化，但是在实际的应用中，还是存在诸多不令人满意的地方，于是人们相继提出了一些优化的方法。 a) 基于划分的方法 Savasere等设计了一个基于划分的算法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频集。 b) 基于hash的方法 一个高效地产生频集的基于杂凑(hash)的算法由Park等提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2-项集Lk上，Park等就是利用了这个性质引入杂凑技术来改进产生频繁2-项集的方法。 (责任编辑：qin) |