频繁项集的产生及经典算法

前言：

　　关联规则是数据挖掘中最活跃的研究方法之一， 是指搜索业务系统中的所有细节或事务，找出所有能把一 组事件或数据项与另一组事件或数据项联系起来的规则，以获 得存在于数据库中的不为人知的或不能确定的信息，它侧重于确 定数据中不同领域之间的联系，也是在无指导学习系统中挖掘本地模式的最普通形式。

　　一般来说，关联规则挖掘是指从一个大型的数据集（dataset）发现有趣的关 联（association）或相关关系（correlation），即从数据集中识别出频繁 出现的属性值集（sets of attribute values），也称为频繁项集 （frequent itemsets，频繁集），然后利用这些频繁项集创建描述关联关系的规则的过程。

关联规则挖掘问题:

　　发现频繁项集:现所有的频繁项集是形成关联规则的基础。通过用户给定的最 小支持度，寻找所有支持度大于或等于minsupport的频繁项集。

　　生成关联规则:通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于minconfidence的关联规则.

　　如何迅速高效地发现所有频繁项集，是关联规则挖掘的核心问题，也是衡量关联规则挖掘算法效率的重要标准。

　　经典的挖掘完全频繁项集方法是查找频繁项集集合的全集。其中包括基于广度优先算法搜索的 关联规则算法--apriori算法(通过多次迭代找出所有的频繁项集)及dhp(direct hashing pruning) 算法等改进算法；基于深度优先搜索策略的fp-growth算法，eclat算法，cofi算法等， 我将介绍两种经典算法--apriori算法和fp-growth算法。

1.apriori算法

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

　　apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：

apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步

　　（1）生成频繁1项集l1。

　　（2）连接步：为了寻找频繁k项集 ，首先生成一个潜在频繁k项集构成的候选项集 ， 中的每一个项集是由两个只有一项不同的属于 的频繁项集做k-2连接运算得到的。连接方法为：设l1和l2是 中的项集，即 ，如果l1和l2中的前k-2个元素相同，则称l1和l2是可连接的，用 表示。假定事务数据库中的项均按照字典顺序排列，li[j]表示li中的第j项，则连接l1和l2的结果项集是 。

　　（3）剪枝步：连接步生成的ck是lk的超集，包含所有的频繁项集lk，同时也可能包含一些非频繁项集。可以利用前述先验知识（定理3.2），进行剪枝以压缩数据规模。比如，如果候选k项集ck的k-1项子集不在lk-1中，那么该子集不可能是频繁项集，可以直接删除。

　　（4）生成频繁k项集lk：扫描事务数据库d，计算ck中每个项集的支持度，去除不满足最小支持度的项集，得到频繁k项集lk。

　　（5）重复步骤（2）～（4），直到不能产生新的频繁项集的集合为止，算法中止。

apriori算法是一种基于水平数据分布的、宽度优先的算法，由于 使用了层次搜索策略和剪枝技术，使得apriori算法在挖掘频繁模式时具 有较高的效率。但是，apriori算法也有两个致命的性能瓶颈：

　　（1）apriori算法是一个多趟搜索算法，每次搜索都要扫描事务数据库，i/o开销巨大。对于候选k项集ck来说，必须扫描其中的每个元素以确认是否加入频繁k项集lk，若候选k项集ck中包含n项，则至少需要扫描事务数据库n次。

　　（2）可能产生庞大的候选项集。由于针对频繁项集lk-1的k-2连接运算，由lk-1 产生的候选k项集ck是呈指数增长的，如此海量的候选集对于计算机的运算时间和 存储空间都是巨大的挑战。

交易	商品代码
t100	l1,l2,l3
t200	l2,l3
t300	l2,l3
t400	l1,l2,l4
t500	l1,l3
t600	l2,l3
t700	l1,l3
t800	l1,l2,l3,l5
t900	l1,l2,l3

 当k=1,min_sup=1时

计算c1和l1

c1
项集	支持度计数
{l1}	6
{l2}	7
{l3}	6
{l4}	2
{l5}	2

 

 

 

 

 

 

 

 

 

 

 

l1:由c1剪枝得到l1
项集	支持度计数
{l1}	6
{l2}	7
{l3}	6
{l4}	2
{l4}	2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

计算c2和l2

c2
项集	支持度计数
{l1,l2}	4
{l1,l3}	4
{l1,l4}	1
{l1,l5}	2
{l2,l3}	4
{l2,l4}	2
{l2,l5}	2
{l3,l4}	0
{l3,l5}	1
{l4,l5}	0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l2:由c2剪枝得到l2
项集	支持度计数
{l1,l2}	4
{l1,l3}	4
{l1,l5}	2
{l2,l3}	4
{l2,l4}	2
{l2,l5}	2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

计算c3和l3

c3:由l2计算三项集
{l1,l2}+{l1,l3}	{l1,l2,l3}
{l1,l2}+{l1,l5}	{l1,l2,l5}
{l1,l2}+{l2,l3}	{l1,l2,l3}
{l1,l2}+{l2,l4}	{l1,l2,l4}
{l1,l3}+{l1,l5}	{l1,l3,l5}
{l1,l3}+{l2,l3}	{l1,l2,l3}
{l1,l3}+{l2,l4}	超过三项
{l1,l3}+{l2,l5}	超过三项
{l1,l5}+{l2,l3}	超过三项
{l1,l5}+{l2,l4}	超过三项
{l1,l5}+{l2,l5}	{l1,l2,l5}
{l2,l3}+{l2,l4}	{l2,l3,l4}
{l2,l3}+{l2,l5}	{l2,l3,l5}
{l2,l4}+{l2,l5}	{l2,l4,l5}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l3:由c3剪枝得到l3
项集	支持度计数
{l1,l2,l3}	3
{l1,l2,l5}	2

 

 

 

 

 

 

 

 

 

计算c4和l4

c4:由l4计算四项集
{l1,l2,l3}+{l1,l2,l5}	{l1,l2,l3,l5}

 

 

 

 

 

 

 

 

因为它的子集{l2,l3,l5}不是频繁项集，此项集删除，c4=0；

apriori算法优缺点：

优点:思路简单；递归计算；实现方便

缺点:频繁遍历数据库；生成候选集-----连接较多；占用空间大；运算量大。

2.fp-growth算法

　　频繁模式树增长算法（frequent pattern tree growth）采用分而治之的 基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集 之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个 条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。

fp-growth算法演示-------构造fp树

事务数据库的建立

tid	items
1	l1,l2,l5
2	l2,l4
3	l2,l3
4	l1,l2,l4
5	l1,l3
6	l2,l3
7	l1,l3
8	l1,l2,l3,l5
9	l1,l2,l3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

扫描事务数据库得到频繁项目集f

从1到各点	各点路径重复次数
1-1	6
1-2	7
1-3	6
1-4	2
1-5	2

 

 

 

 

 

 

 

 

 

 

 

定义minsup=20%,即最小支持度为2,重新排列f

从1到各点	各点路径重复次数
1-2	7
1-1	6
1-3	6
1-4	2
1-5	2

 

 

 

 

 

 

 

 

 

 

重新调整事务数据库

tid	items
1	l2,l1,l5
2	l2,l4
3	l2,l3
4	l2,l1,l4
5	l1,l3
6	l2,l3
7	l1,l3
8	l2,l1,l3,l5
9	l2,l1,l3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

在fp树中可以看到，从根节点到i5:1的路径有两条：

　　i2:7-->i1:4-->i5:1

　　i2:7-->i14-->i3:2-->i5:1

　　i2:7-->i1:4和i2:7-->i14-->i3:2因为最终到达的节点肯定是i5，所以将i5省略就是i5的条件模式基，记为{i2,i1:1}{i2,i1,i3:1}

条件模式基：{i2,i1:1}{i2,i1,i3:1}

因为i3:1x小于最小支持度2,所以讲i3:1省略不计,i5的条件fp树记为{i2:2,i1:2}

根据条件fp树，我们可以进行全排列组合，得到挖掘出来的频繁模式（这里要将商品本 身，如i5也算进去，每个商品挖掘出来的频繁模式必然包括这商品本身）

项	条件模式基	条件fp树	产生频繁模式
i5	{{i2 i1:1},{i2 i1 i3:1}}	{i2:2,i1:2}	{i2 i5:2},{i1 i5:2},{i2,i1:2}
i4	{{i2 i1:1},{i2:1}}	{i2:2}	{i2 i4:2}
i3	{{i2 i1:2},{i2:2},{i1:2}}	{i2:4,i1:2,i1:2}	{i2 i3:4},{i1 i3:4},{i2 i1 i3:2}
i1	{{i1:4}}	{i2:4}	{i2 i1:4}