关联规则挖掘中的Apriori算法

一，Apriori算法的基本思想:

????????? 任意频繁项集的任何子集也是频繁的，反过来说就是，任何非频繁(k-1)-项集都不可能是频繁k-项集的子集。

二，Apriori算法的基本步骤：

?????????? 采用逐层搜索的迭代方法，利用k-项集产生(k+1)-项集。

????????? 首先，根据支持度阈值，找出频繁1-项集，记为L1；

????????? 其次，再利用L1找到频繁2-项集L2，直至不能找到频繁k-项集；

???????? 这一步可分为两小步：

????????????????? 第一：可称为连接步，通过L(k-1)与自身连接产生候选k-项集的集合（此时必须有它们的前k-2个项都相等）；

???????????????? 第二：可称为剪枝步，采用基于支持度的剪枝策略，最根本的是要进行支持度计数，可以采用枚举每个事物所包含的项集，并且利用它们更新对应的候选项集的支持度。

三，Apriori算法伪代码：

?????????? L1=find_frequent_1_itemset(D)
?????? for(k=2;L(k-1)非空;k++)
?????? {
??????????????? Ck=apiori_gen(L(k-1),min_sup);
??????????????? for each t属于D
????????????? ｛
????????????????????????? Ct=subset(Ck,t);
????????????????????????? for each t属于Ct?? count++;
?????????????? ｝
??????????????? Lk={c属于Ck|c,count>min_sup};

?????????????? return L1....Lk的并集；

??????? }

?????? Apiori算法的瓶颈在于候选项集的产生，需要多次扫描数据库。

????? 可以采用以下方法提高效率：

?????????????? 第一，事务压缩，不包含任何k-项集的事务不可能包含任何(k+1)-项集。在这种事物出现时可加上标记或删除。

????????????? 第二，划分数据，先将数据库从逻辑上划分成不同的块，对每个分块生成频繁项集，然后合并频繁项集，计算支持度。

????????????? 第三，动态项集计数，再添加一个新的候选项集之前，先估计他的所有子集是不是频繁的。这从这样，这种事务出现时，可以加上标记或删除，因为以后产生j-项集(j>k)，扫描数据库时不再需要它们。样，这种事务出现时，可以加上标记或删除，因为以后产生j-项集(j>k)，扫描数据库时不再需要它们。