# 关联规则挖掘

## 经典例子##\#

一家大型超市对**购物篮分析**，发现经常有人同时购买**啤酒**和**尿布**。

原因：美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿布。而丈夫在买完尿布之后又要顺手买回自己爱喝的啤酒。

决策：超市将啤酒和尿布摆放在一起，增加购买的机会。

### 什么叫做经常同时购买？###\#

通过**支持度**（support）与**置信度**（confidence）来衡量。

* 支持度：support(A-->B) = |AB|/|N|\
  商品A和B（如啤酒和尿布） 同时出现在同一个购物清单中的数量 / 总的购物清单数
* 置信度：confidence(A-->B) = |AB|/|A|\
  同时出现在同一个购物清单中的数量/A出现的数量。即规则A-->B的可信度。

可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。\
支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越重要。

出现就行，不考虑一个购物清单中啤酒的数量。

## 关联挖掘##\#

给定一个数据集，从中找出所有支持度>最小支持度，置信度>最小置信度的关联规则（关联关系）

如果实现？\
思路1：\
穷举所有商品组合，看是否满足要求。 **不可取**

思路2：\
1.找出频繁项集\
2.生成规则

## apriori算法##\#

消除一些完全不可能是频繁项的集合。

两个原则：

* 如果一个集合是频繁项集，则它的所有子集都是频繁项集
* 如果一个集合不是频繁项集，则它的所有超集都不是频繁项集

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Feb1d4966a4e06e3d5c672365d7d1fff7c1b1dfef.jpg?generation=1589383927069210\&alt=media)

缺点：需要不停扫描全表数据

## FP growth算法##\#

能不能扫描全表数据后，将需要的信息用个数据结构存储下。

看下数据的表述形式： ![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fefe34f91ef7382aef58d046a675771c0c2572608.png?generation=1589383927285726\&alt=media)

稍微转换一下：

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fcb5cd210c9243d145cabe3c399bc4e74a940ef3a.png?generation=1589383926691397\&alt=media)

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F7864879192f00bb9c60e7e7f5d183f3a5425294d.JPG?generation=1589383927827029\&alt=media)

> 注意生成树的前，讲所有一项集按频繁度排序，排完再生成树

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fefc8fe94e5978b970ed8963cd66ca962307105b8.png?generation=1589383927442709\&alt=media)

生成树的过程中建立一个链表，最后得： ![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F1714e98801daeeda365ce9810dde07b790722d95.jpg?generation=1589383926987409\&alt=media)

树生成后如何挖掘关联规则：**FP-growth**

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fbd7aa4a59b81f7027e8f2b605d7717ac83f815d8.jpg?generation=1589383926657925\&alt=media)

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2Fd1e9d25e4f9e8e52d45d3b9b1043971c526d4deb.png?generation=1589383927610146\&alt=media)

### 参考佳文###\#

[关联规则的常用算法](http://www.bjt.name/2013/09/association-rules/)\
[关联规则挖掘基本概念与Aprior算法](http://www.cnblogs.com/fengfenggirl/p/associate_apriori.html)\
[关联规则FpGrowth算法](http://www.cnblogs.com/fengfenggirl/p/associate_fpgowth.html)

[频繁模式挖掘中Apriori、FP-Growth和Eclat算法的实现和对比（Python实现）](https://www.cnblogs.com/infaraway/p/6774521.html)

[挖掘频繁项集——Apriori、FP-Growth、Eclat、Diffset原理](https://blog.csdn.net/Xingzi_c/article/details/102801938)