版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc
前言
最近打算给我的博客做个性化推荐，初步选定使用关联规则算法来实现。
常见关联规则算法又有Apriori算法、FP-树频集算法、Eclat算法 3种。
请务必阅读参考资料1，了解Support(支持度), Confidence(置信度)， Lift（提升度）
Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time. Association rule generation is usually split up into two separate steps:
A minimum support threshold is applied to find all frequent itemsets in a database. A minimum confidence constraint is applied to these frequent itemsets in order to form rules. While the second step is straightforward, the first step needs more attention.
关联规则一般分为2步
- 根据最小支持度查找所有的频繁的项目集(itemsets)
- 根据最小置信度，在1)找出的频繁的项目集中, 创建关联规则 第2步比较简单，重点关注第1步，寻找频繁的项目集
Eclat算法
Eclat算法是一种基于集合交集的深度优先搜索算法。 它适用于具有局部性增强特性的顺序执行和并行执行。笔者先实现了Python版，后期可以直接实现Spark版本，进行并行化计算。
首先看下参考资料2举的例子 表1：关联规则的简单例子
| TID | 网球拍 | 网球 | 运动鞋 | 羽毛球 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 |
| 4 | 1 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
为了计算方便，我们把网球拍等商品直接用A ~ D来取代 表2
| TID | items |
|---|---|
| 1 | A,B,C |
| 2 | A,B |
| 3 | A |
| 4 | A,C |
| 5 | B,C,D |
| 6 | A,B |
Eclat算法加入了倒排的思想，以商品项为key，以事务为value 表3
| item | Tids |
|---|---|
| A | 1,2,3,4,6 |
| B | 1,2,5,6 |
| C | 1,4,5 |
| D | 5 |
在这里把
- 以1个商品项构建项集，称为1项集
- 以2个商品项构建项集，称为2项集
- 以3个商品项构建项集，称为3项集 以此类推 可知表3 就是1项集，如果它们满足指定支持度，就是频繁1项集
基本思想
要得到频繁项集，如果不考虑性能，我们需要穷举商品[A-D]的能构成的所有组合，然后判断该项集是否是频繁项集。解空间可以构成如下的树
我们知道，如果k + 1项集是频繁项集，那么k项集一定是频繁项集，反之如果k项集不是频繁项集，那么果k + 1项集一定不是频繁项集。根据此规则，我们能对解空间的搜索进行裁剪。上图中的粉红色节点表示当支持度是0.5时，能够被裁剪掉的节点。
Eclat算法思想是 由频繁k项集求交集，生成候选k+1项集 。对候选k+1项集做裁剪，生成频繁k+1项集，再求交集生成候选k+2项集。如此迭代, 直到搜索完整个解空间。
详细代码见 eclat.py
参考资料
请我喝瓶饮料
