Apriori算法

关联分析 关联规则学习

Posted by jiang on November 2, 2018

关联分析 关联规则学习

apriori

频繁项集 {啤酒,尿布}

项集支持度 比例

可信度

{尿布} ➞ {葡萄酒} 支持度({尿布, 葡萄酒})/支持度({尿布})

Apriori原理

如果一个项集是频繁的那么其子集也是频繁,如果一个子集是非频繁的,那么父集也是非频繁的。

先验 来自以前

对于Apriori算法,我们使用支持度来作为我们判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思,首先,我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。

弊端

频繁扫描 大数据集 低效率

举例描述

apriori2

我们的数据集D有4条记录,分别是134,235,1235和25。现在我们用Apriori算法来寻找频繁k项集,最小支持度设置为50%。首先我们生成候选频繁1项集,包括我们所有的5个数据并计算5个数据的支持度,计算完毕后我们进行剪枝,数据4由于支持度只有25%被剪掉。我们最终的频繁1项集为1235,现在我们链接生成候选频繁2项集,包括12,13,15,23,25,35共6组。此时我们的第一轮迭代结束。

进入第二轮迭代,我们扫描数据集计算候选频繁2项集的支持度,接着进行剪枝,由于12和15的支持度只有25%而被筛除,得到真正的频繁2项集,包括13,23,25,35。现在我们链接生成候选频繁3项集,123, 125,135和235共4组,这部分图中没有画出。通过计算候选频繁3项集的支持度,我们发现123,125和135的支持度均为25%,因此接着被剪枝,最终得到的真正频繁3项集为235一组。由于此时我们无法再进行数据连接,进而得到候选频繁4项集,最终的结果即为频繁3三项集235。

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  输入:数据集合D,支持度阈值α 
  输出:最大的频繁k项集

  1)扫描整个数据集,得到所有出现过的数据,作为候选频繁1项集。k=1,频繁0项集为空集。

  2)挖掘频繁k项集

   a) 扫描数据计算候选频繁k项集的支持度

   b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空,则直接返回频繁k-1项集的集合作为算法结果,算法结束。如果得到的频繁k项集只有一项,则直接返回频繁k项集的集合作为算法结果,算法结束。

   c) 基于频繁k项集,连接生成候选频繁k+1项集。

  3) 令k=k+1,转入步骤2。