Press "Enter" to skip to content

FP增长算法

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

Apriori原理:如果某个项集是频繁的,那幺它的所有子集都是频繁的。

 

Apriori算法:

 

1 输入支持度阈值t和数据集
2 生成含有K个元素的项集的候选集(K初始为1)
3 对候选集每个项集,判断是否为数据集中某条记录的子集
4        如果是:增加候选集的计数
5 保留频繁集(计数>t)
6 根据频繁集生成含有K+1个元素的项集候选集
7 循环2-5,直至候选集为空

 

Apriori算法是有缺点的

 

缺点是:1.需要多次扫描数据库 2.产生大量的候选频繁集 3.时间和空间复杂度高。

 

从算法第3步可以看出,候选频繁项集不一定是原始数据集中某一项的子集,即:x为频繁项,y为频繁项,{x,y}可以组成一个候选频繁项集,但是原始数据集中不一定存在{x,y}的组合。这使得Apriori算法有大量时间浪费在无效的集合上。

 

FP树增长算法是一种挖掘频繁项集的算法。Apriori算法虽然简单易实现,效果也不错,但是需要频繁地扫描数据集,IO费用很大。FP树增长算法有效地解决了这一问题,其通过两次扫描数据集构建FP树,然后通过FP树挖掘频繁项集。

 

背景知识

 

1.什幺是项和项集?

 

比如我们在购物的时候,购物车内的每一件商品成为一项,若干个项的集合成为项集。例如{啤酒,尿布}成为一个二元项集。

 

2.什幺是支持度?

 

支持度是在所有的项集中{X,Y}出现的可能性。

 

例如:购买商品的数据是(表示4条购物信息):

 

①{啤酒,尿布,娃哈哈}

 

②{啤酒,方便面}

 

③{尿布,奶粉}

 

④{啤酒,尿布,洗发水}

 

在这组数据中,{啤酒,尿布}出现的可能性就是这里面数据的概率。{啤酒,尿布}的支持度是2/4=50%.

 

{尿布,奶粉}的支持度是1/4=25%

 

3.什幺是频繁项集?

 

我们首先设置一个最小阈值A,支持度大于A的项集就是频繁项集,小于A的项集被剔除。

 

比如 我们设置阈值为30%,在上面的例子中{啤酒,尿布}就是频繁项集,{尿布,奶粉}就要被剔除。

 

问题:如何求出频繁项集?

 

首先构造FP树

 

然后通过FP树可以求出频繁项集

 

FP算法

 

 

FP增长算法需要根据数据集生成FP树,步骤如下:

 

步骤一:统计每个元素出现次数,保留频繁元素(假设次数>3),按照元素出 现次数降序排序。

 

其中h,j,p,w,v,u,n,o,q,p,e,m的次数是小于等于3的.因此把它们去掉,然后把其他的字母按照次数从大到小排列。

 

 

步骤二:构建FP树

 

通过上面的序列按照每一行进入树根初始化树叶。如果没有相同的字母就重新创建叶子节点,每个叶子节点有字母其次数。

 

如图所示

 

先插入(z,r),再插入(z,x,y,s,t),再插入(z),如图

 

 

最后插完的结果是:

 

 

步骤三:FP树中找到元素的前缀路径

 

以r为例,r的前缀路径为:以根结点为起点,结点r为终点的所有路径。

 

先找到FP树中所有“r”结点,然后从每一个“r”结点向根结点方向查找,找到的所有路径就是“r”的前缀路径

 

 

然而,找到所有“r”结点,需要遍历整棵FP树,这使得算法的时间复杂度会很高。

 

为了方便查找,可以用链表来加快寻找的前缀路径。

 

将FP树中所有相同的结点用链表连接,可以将查找结点的时间复杂度从O(n)降到常数级。

 

 

通过上面的操作就得到了如下所示的信息。

 

 

步骤四:根据前缀路径构造条件FP树

 

t的条件FP树如下:

 

 

t前缀路径中的频繁元素包括{z:3,x:3,y:3},这个数字表示对应的元素在原始数据集中和t一起出现的次数,如{z,t}出现3次,{x,t}出现3次,{y,t}出现3次。显然,这些项集都是频繁项集。

 

很容易发现,t的前缀路径也是一个数据集,生成t条件FP树的过程,跟前面生成FP树的过程相同,我们也可以在t的条件FP树基础上构造x的条件FP树,对应的就是{t,x}的条件FP树。

 

显然,这是个递归的过程。

 

步骤5:递归构造下一层条件FP树,直至条件FP树为空.

 

总结:

 

1、频繁集不是从FP树产生,而是通过每一层递归获得的频繁元素组合产生。FP树的作用是寻找前缀路径。
   相比于Apriori算法,FP树的作用相当于是把遍历数据集的结果用树的结构保存下来,而避免了重复扫描数据集。
2、FP树只需要扫描两次数据集,第一次统计各个元素出现次数,第二次根据过滤排序后的数据集生成FP树。后续的过程都在FP树上进行。
3、{x,t}的条件FP树和{t,x}的条件FP树是否相同? 算法是否重复计算了这两个条件FP树?
   这个问题涉及到FP增长算法的一个根本问题,为什幺要使用前缀路径?
   找到前缀路径后,需要对前缀路径集合进行过滤和排序,获得下一层递归的数据集。
   那幺不使用前缀路径,而使用完整路径显然也可以达到目的。
   前缀路径有个非常重要的优点。
   构造FP树之前由于对元素进行了排序,如果x出现在t的前缀路径中,那幺t不可能再出现在x的前缀路径中,所以使用前缀路径避免了相同集合的重复计算!
   另外,前缀路径的查找非常方便,一个结点向上查找,获得的前缀路径是固定的,如果使用完整路径,结点向下查找可能会出现分叉,处理起来会变得非常复杂。

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。