Apriori&&FPgrowth

Apriori

Apriori算法的核心思想

Apriori算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁1项集开始，采用频繁k项集搜索频繁k+1项集，直到不能找到包含更多项的频繁项集为止。

Apriori算法由以下两个关键步骤组成，其中的核心步骤是连接步和剪枝步：

1. 连接步
   为了找到频繁k项集Lk，首先将Lk-1与自身连接，产生候选k项集Ck，Lk-1的元素是可连接的。
2. 剪枝步
   候选k项集Ck是Lk的超集，因此，Ck成员即可为频繁项集也可不是频繁的，但所有的频繁项集都包括在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的(k-1)项集都不可能是频繁k项集的子集。因此，如果一个候选k项集的(k-1)项集不在Lk中，则该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。

Apriori算法描述

发现频繁项目集

1
2
3
4
5
6
7
8
9
10
11

L1 = {large 1-itemsets}; //所有1-项目频集
FOR (k=2; Lk-1!=NULL中; k++) DO BEGIN
	Ck= apriori-gen (Lk-1) ; // Ck是k-候选集
	FOR all transactions t∈D DO BEGIN 
		Ct=subset (Gk，t) ; // C是所有t包含的候选集元素
		FOR all candidates c∈Ct DO
			c.count++;
		END
	Lk={C∈Ck |c.countzminsup_ count}
END
L= ULk;

apriori-gen(Lk-1)

1
2
3
4
5
6
7
8
9

FOR all itemset p∈Lk-1 DO
	FOR all itemset q∈Lk-1 DO
		IF p.item1=q.item1，...，p.itemk2=q.itemk-2，p.itemk1 < q.itemk1 THEN BEGIN
			C= p∞q;//把q的第k-1个元素连到p后
			IF has_ jinfrequent subset (C，Lk1) THEN
				delete C;//删除含有非频繁项目子集的侯选元素
			ELSE addcto Cki 
		END
	Return Ck;

在最小支持度是 50%， 最小置信度是70%的情况下

1. 挖掘出所有频繁项集
2. 挖掘出强关联规则

Apriori算法评价

优点:

• 简单明了
• 易于实现

缺点:

• 对数据库的扫描次数过多。
• Apriori算法会产生大量的中间项集。
• 采用唯一支持度。
• 算法的适应面窄。

Apriori算法改进

鉴于Apriori算法需要多次扫描数据库，在实际应用中，运行效率往往不能令人感到满意，尤其是当数据库较大时更为棘手。为了提高Apriori算法的性能和运行效率，许多专家对Apriori算法的改进展开了研究，形成了许多改进和扩展Apriori的方法。

改进算法的途径包括以下几个方面：

1. 通过减少扫描数据库的次数改进I/O的性能；
2. 改进产生频繁项集的计算性能；
3. 寻找有效的并行关联规则算法；
4. 引入抽样技术改进生成频繁项集的I/O和计算性能；
5. 扩展应用领域。比如展开定量关联规则、泛化关联规则及周期性的关联规则的研究。

改进算法具体简要介绍如下：

• 基于划分的方法
• 事务压缩
• 基于抽样技术
• 基于动态项目集技术

FPgrowth

Apriori算法是一个候选消除算法，每一次消除都需要扫描一次所有数据记录，当数据集特别大时，需要不断扫描数据集，造成运行效率很低。

FP-growth算法基于Apriori构建，但采用了高级的数据结构以减少扫描次数，大大加快了算法速度。 FP-growth算法通过构造一个树结构FP-tree来映射数据集中的事务，在根据这棵树找出频繁项集，只需要对数据集进行两次扫描，就可以更高效地发现频繁项集。而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快。

FP-growth发现频繁项集的基本过程如下：
(1)构建FP树
(2)从FP树中挖掘频繁项集

构建FP树

第一次扫描
过滤掉所有不满足最小支持度计数(出现3次)的项；
对于满足最小支持度的项，按照全局最小支持度排序，在此基础上；
为了处理方便，也可以按照项的关键字再次排序。

第二次扫描，构造FP树

从FP树中挖掘频繁项集

1. 从header table的最下面的item开始，构造每个item的条件模式基（Conditional Pattern Base，CPB）。

2. 构造条件FP-tree（Conditional FP-tree）累加每个CPB上的item的频繁度（计数），过滤低于阈值的item，构建FP-tree。
3. FP-Growth：递归的挖掘每个条件FP-tree，累加后缀频繁项集，直到找到FP-tree为空或者FP-tree只有一条路径（只有一条路径情况下，所有路径上item的组合都是频繁项集）。可以证明（严谨的算法和证明在此不进行叙述），频繁项集即不重复也不遗漏。
4. Apriori算法可以挖掘出频繁项集和强关联规则，但是FP-Growth算法只能挖掘出频繁项集。