目录
频繁模式增长法Frequent Pattern-growth
关联规则
关联规则又称购物篮分析，指从看似相关却又不相同的交易记录中找出潜在有用的关联规则。
衡量指标
-
支持度support：频率，表示某个或某些购买商品与总体购买商品之间的关系；如果某个项原本的支持度很低，即使关联性很强，也没有太多实际意义；实际使用时可以指定X的出现次数作为阈值。
- 利用minimum support（min sup）最小支持度作为门槛来删除不重要的关联规则。
-
-
信赖度confidence：条件概率，买了X的人又买了Y的比例有多少，表示关联性的强弱，或者说是规则的可靠性。
- 衡量关联规则是否具有可信度的指标，利用minimum confidence（min conf）最小信赖度作为门槛（一般选0.5），删除正确率较低的关联规则。
-
- 增益lift：增益值至少要大于1，表示该关联规则的预期结果比原本的表现好。
关联规则挖掘子任务
- 频繁项集产生
- 规则产生
先验演算法APRIORI
两个原则：
- 如果一个集合是频繁项集，则其所有子集都是频繁项集。
- 如果一个集合不是频繁项集，则其所有超集都不是频繁项集。
频繁项集的计算：
如图所示，设min sup=3，求出最长的频繁项目集。
- 将上图的交易信息转化为二元资料表
二元资料表
A蛋糕
B奶茶
C可乐
D饼干
E巧克力
1
0
1
1
1
1
2
0
1
1
1
0
3
1
1
0
1
0
4
1
1
1
1
1
5
1
1
1
0
0
6
0
1
0
0
1
- 统计出每个项目item出现的频次，并删除频次小于min sup的项目
B奶茶
C可乐
D饼干
A蛋糕
E巧克力
6
4
4
3
3
- 将上个步骤保留下来的项目组成集合，求每个项目集的出现频次，并删除频次小于min sup的项目集
BC
BD
BA
BE
CD
CACEDADEAE4
4
3
3
3
22221 - 重复上个步骤，直到求出最长的频繁项目集
BCD
BCABCEBDABDEBAEBACDBECD3
2222112
综上所述，最长的频繁项目集为BCD。
频繁模式增长法Frequent Pattern-growth
目前最有效率的关联规则算法。将数据库内的频繁项目集压缩到一颗频繁模式树(FP-tree)之中，保留项目集之间的重要关联信息。此方法不需要大量的候选项目集，可大幅减少运算时间，并且只需要扫描资料库2次。
1. 建立FP-tree
min_sup：最小支持度，门槛值，
step1：统计所有项目item出现的次数，并删除次数小于min_sup的项目，然后降序排序（次数）；
step2：根据上一步排序后的项目表，依序读取每一条资料，同时建立FT-tree；
FP-tree建立过程如下所示：
| 交易记录 | 商品交易项目 |
|---|---|
| 1 | A,B |
| 2 | B,C,D |
| 3 | A,C,D,E |
| 4 | A,D,E |
| 5 | A,B,C |
| 6 | A,B,C,D |
| 7 | A |
| 8 | A,B,C |
| 9 | A,B,D |
| 10 | B,C,E |
- 统计项目频次
项目 A B C D E 频次 8 7 6 5 3 - 删除次数小于min sup=2的项目，并降序排列
项目 A B C D E 频次 8 7 6 5 3 - 根据上一步排序后的项目表，依序读取每一条资料，同时建立FP-tree
2. 挖掘FP-tree
step1：根据上一步建立的FP-tree，分别以结点E、D、C、B、A作为结尾来挖掘；
step2：以step1选定的结点为条件，其余结点为结尾，分别进行挖掘；
重新设定路径数字：指从tree的叶子结点(频次不变)到NULL结点，逐一更新路径上结点的频次。
FP-tree挖掘过程如下所示：
- 以E作为结尾来挖掘，并重新设定路径数字
- 删除频次小于min sup的项目，更新tree
-
{D,E}表示以E为条件下、D结尾，并重新设定路径数字
- 删除频次小于min sup的项目，更新tree
- {A,D}表示以D为条件下、A结尾
-
{C,E}表示以E为条件下、C结尾，并重新设定路径数字
- 删除频次小于min sup的项目，更新tree
-
{A,E}表示以E为条件下、A结尾，并重新设定路径数字
以E为结尾的挖掘结果：
| 一阶 | 二阶 | 三阶 |
| E | D | A |
| E | C | |
| E | A |
以E为结尾的高频项目集：{E}、{D,E}、{C,E}、{A,E}、{A,D,E}。
同理：
- 以D作为结尾来挖掘，并重新设定路径数字
-
{C,D}表示以D为条件下、C结尾，并重新设定路径数字
- {B,C}表示以C为条件下、B结尾，并重新设定路径数字
- 删除频次小于min sup的项目，更新tree
- {A,C}表示以C为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是2)
-
{B,D}表示以D为条件下、B结尾，并重新设定路径数字
- {A,B}表示以B为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是2)
-
{A,D}表示以D为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是4)
以D为结尾的挖掘结果：
| 一阶 | 二阶 | 三阶 |
| D | C | B |
| D | C | A |
| D | B | A |
| D | A |
以D为结尾的高频项目集：{D}、{D,C}、{D,B}、{D,A}、{D,C,B}、{D,C,A}、{D,B,A}。
同理：
- 以C作为结尾来挖掘，并重新设定路径数字
-
{B,C}表示以C为条件下、B结尾，并重新设定路径数字
- {A,B}表示以B为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是3)
-
{A,C}表示以C为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是4)
以C为结尾的挖掘结果：
| 一阶 | 二阶 | 三阶 |
| C | B | A |
| C | A |
以C为结尾的高频项目集：{C}、{C,B}、{C,A}、{C,B,A}。
同理：
- 以B作为结尾来挖掘，并重新设定路径数字
-
{A,B}表示以B为条件下、A结尾，并重新设定路径数字(由于树中只有A，所以A仍然是5)
以B为结尾的挖掘结果：
| 一阶 | 二阶 | 三阶 |
| B | A |
以B为结尾的高频项目集：{B}、{B,A}。
同理：
- 以A作为结尾来挖掘，并重新设定路径数字(由于树中只有A，所以A仍然是8)
以A为结尾的挖掘结果：
| 一阶 | 二阶 | 三阶 |
| A |
以A为结尾的高频项目集：{A}。