Apriori 与 FP-growth 算法

当你买菜的时候,可曾给自己列过一个要购买的物品清单? 每个人在列清单的时候都会有不同的需求和偏好. 作为店家本身,根据物品的品类和购买频次可以更好的去理解顾客的消费习惯. 假设很多客户喜欢同事购买X,Y两个东西,那么:

1. X和Y商品可以放在同一个商品架上,消费者就能更方便的购买这两件物品
2. 可以在X,Y商品上提供同时购买的优惠券,刺激消费
3. 针对经常买X商品的顾客针对性的发放关于Y商品的广告

现在你已经看对频繁项信息挖掘能产生的价值了,那么我们怎么去实现呢?

★关联规则分析(Associate rules Analysis)

关联规则分析可以用于解释两个物品是如何关联上的, 目前有三种比较流行的关联度测量方式

1. 支持度(Support)

支持度表达的是物品的"流行度",用下面的图例来看,支苹果的持度则是苹果在8次交易中出现的概率

2. 置信度(Confidence)

置信度表示当事件X出现后,事件B出现的概率,下面的图例中的意思是已知苹果已被购买,购买啤酒的额置信度公式

注意,置信度公式的缺点是比较明显的,比如啤酒本身就非常的受欢迎,所以对于购买苹果后再购买啤酒的置信度也会很高.所以有可能会造成误导, 第三种方式便可以解决这样的问题

3. 提升度(Lift)

提升度表示当事件X出现后,并且了解到事件Y的流行度的情况下,Y出现的可能性,下图解释了提升度的计算方式

★Apriori 算法

Apriori的算法目的是减少所需计算的事件. Aprioi算法的原则为: 如果事件X是非频繁的,那么他所有的supersets都是非频繁的. 更具体的来讲,假设啤酒是一个非频繁被购买的商品,那么{啤酒,炸鸡}则同样或者更加的非频繁. 所以当我们进行频繁项挖掘的过程中,就不再考虑{啤酒,炸鸡}或者任何包含啤酒的组合购买了.

那么,什么才叫做高频繁,什么才叫做低频繁呢?下面Apriori的具体算法流程就会解释你的问题

1. 从单个样品开始,比如{啤酒},{炸鸡}和{牛肉}
2. 针对每个单品计算支持度, 保留所有高于最低支持度阈值的物品
3. 保留step2中的所有物品,找到剩下所有物品的两两组合方式
4. 重复step2-3,注意在step3中,组合个数每一次提升一个,比如第一次是{啤酒,炸鸡},那么下一次循环的时候则为{啤酒,炸鸡,牛肉}

上述的最低支持度阈值主要由专家经验进行判定,同时,在stpe2中,可以使用置信度或者提升度. 具体使用哪一个参数,可以数据本身分布情况而定

Apriori的局限性

• 高计算复杂度: 虽然Apriori算法减少了需要计算的事件,但是他在事件量特别大的情况下仍然出现大量的计算.
• 复杂的事件结合方式: 当分析非常复杂的物品组合方式的时候,我们需要降低最低支持度阈值,否则有可能无法提取到相关的组合. 但是,与此同时, 也会有大量的复杂组合方式出现干扰分析.

★FP-growth 算法

为了解决Apriori的局限性问题,FP-growth算法基于Apriori原理，将数据集存储在FP（Frequent Pattern)树上发现频繁项集。FP-growth算法只需要对数据库进行两次扫描，而Apriori算法在求每个潜在的频繁项集时都需要扫描一次数据集，其中算法发现频繁项集的过程是：

1. 构建FP树；

2. 从FP树中挖掘频繁项集。

构建FP树

FP表示的是频繁模式，其通过链接来连接相似元素，被连起来的元素可以看成是一个链表。将事务数据表中的各个事务对应的数据项按照支持度排序后，把每个事务中的数据项按降序依次插入到一棵以 NULL为根节点的树中，同时在每个结点处记录该结点出现的支持度。

FP-growth算法的流程为：首先构造FP树，然后利用它来挖掘频繁项集。在构造FP树时，需要对数据集扫描两边，第一遍扫描用来统计频率，第二遍扫描至考虑频繁项集。下面举例对FP树加以说明。

结合Apriori算法中最小支持度的阈值，在此将最小支持度定义为3，结合上表中的数据，那些不满足最小支持度要求的将不会出现在最后的FP树中，据此构建FP树，并采用一个头指针表来指向给定类型的第一个实例，快速访问FP树中的所有元素，构建的带头指针的FP树如下:

结合绘制的带头指针表的FP树，对表中数据进行过滤，排序如下：

在对数据项过滤排序了之后，就可以构建FP树了，从NULL开始，向其中不断添加过滤排序后的频繁项集。过程可表示为：