数据挖掘十大经典算法之Apriori算法
概述
Apriori是关联规则模型中的经典算法，是由R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项集的原创性算法。Apriori使用一种称作逐层搜索的迭代方法，k项集用于搜索k+1项集。该算法主要用于在交易数据、关联数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联性或因果结构。
重要概念
-
N项集
表示由N个元素组成的元素集合（N为大于0的整数） -
N项集的支持度
表示在所有样本中，能够匹配特定N项集要求的样本数量，它也可以表示成百分比的形式。 -
频繁N项集（L[n]）
表示满足指定的最小支持度的所有N项集 -
候选N项集（C[n]）
它由频繁N-1项集L[n-1]生成，是计算频繁N项集的基础。C[n]必须保证包括所有的频繁N项集。
重要性质
频繁项集的所有非空子集也必须是频繁的。即如果项集A不满足最小支持度阈值MinSupport，则A不是频繁的，如果将项集B添加到项集A中，也就是A
基本实现原理
- 首先寻找L[1]（即频繁1项集）；
- 在L[k]的基础上生成候选频繁k+1项集C[k+1]；
- 用事务数据库D中的事务对所有C[k+1]进行支持度测试以寻找频繁项集L[k+1]，计算每个候选频繁项集的支持度，如果大于最小支持度，则加入到L[k+1]；
- 如果L[k+1]为空集，则结束，L[1] ∪ L[2] ∪ …即为结果；否则转2继续。
伪代码形式
Apriori算法
输入:数据集D;最小支持度minsupport
输出:频繁项集L
L[1] = {频繁1项集}//初始化频繁项集L[1]（也称单品项集）
for(k=2;L[k-1]不为空;k++){
C[k] = candidate_gen(L[k-1]);//根据L[k-1]产生新的候选频繁项集C[k]
For all transactions t ϵ D; {//对所有的交易记录做循环
C = subset(C[k],t);//找出当前交易记录t和候选频繁项集C[k]的交集
For all candidates c ϵC do//对存在的候选频繁项集的交集进行支持度计数
c.count ++;
}
L[k] = {c ϵ C[k] | c.count >= minsup};//保留大于最小支持度的频繁项集到L[k]；
}
Answer = L=∪L[k]=L[1] ∪ L[2] ∪ ... ∪ L[k]
candidate_gen(L[k-1])
输入:(k-1)-项集
输出:k-候选集C[k]
for all itemset p ∈ L[k-1]
for all itemset q ∈ L[k-1]
if(p.item1 = q.item1,p.item2=q.item2,...,p.item(k-2)=q.item(k-2),p.item(k-1)<q.item(k-1))
c=p∞q;
if(has_infrequent_subset(c,L[k-1]) delete c;
else add c to C[k];
End for
End for
return C[k];
has_infrequent_subset(c,L[k-1])
输入:一个k-项集c,(k-1)-项集L[k-1]
输出:c是否从候选集中删除
for all (k-1)-subsets of c
if S ∉ L[k-1]
return true;
return false;Apriori算法的缺点
-
多次扫描事务数据库，需要很大的I/O负载。
对每次k循环，候选集C[k]中的每个元素都必须通过扫描数据库一次来验证其是否加入L[k]。加入一个频繁大项集包含10个项，那么就至少需要扫描事务数据库10次。
-
可能产生庞大的候选集。
由L[k-1]产生k-候选集C[k]是指数增长的，例如
104 个频繁1-项集就有可能产生将近107 个元素的2-候选集。如此庞大的候选集对时间和主存空间都是一种挑战。
Apriori算法的改进
基于散列(Hash)的方法
1995年，Park等提出了一种基于散列(Hash)技术产生频繁项集的算法。这种方法把扫描的项目放到不同的Hash桶中，每个频繁项最多只能放在一个特定的桶里，这样可以对每个桶中的频繁项自己进行测试，减少了候选频繁项集产生的代价。事务压缩
事务压缩是指压缩未来迭代扫描的事务数。由于不包含任何频繁k-项集的事务是不可能包含任何频繁(k+1)-项集的，因此这种事务在后续的考虑中可以加上标记或者直接删除，因此产生j-项集(j>k)的数据库扫描不再需要它们。基于数据划分(Partition)的方法
Apriori算法在执行过程中首先生成候选集，然后再进行剪枝。可是生成的候选集并不都是有效的，有些候选集根本不是事务数据的项目集。因此，候选集的产生具有很大的代价。特别是内存空间不够导致数据库与内存之间不断交换数据，会使算法的效率变得很差。
把数据划分应用到关联规则挖掘中，可以改善关联规则挖掘在大容量数据集中的适应性。其根本思想是把大容量数据库从逻辑上分成几个互不相交的块，每块应用挖掘算法(如Apriori算法)生成局部的频繁项集，然后把这些局部的频繁项集作为候选的全局频繁项目集，通过测试它们的支持度来得到最终的全局频繁项目集。基于采样(Sampling)的方法
基于采样的方法是Toivonen于1996年提出的，这个算法的基本思想是：选取给定数据D的随机样本S，然后在S而不是D中搜索频繁项集。用这种方法是牺牲了一些精度换取有效性。样本S的大小选取使得可以在内存搜索S中的频繁项集。这样只需要扫描一次S中的事务。由于算法只是搜索S中的数据，因此可能会丢失一些全局频繁项集。为了减少这样的情况，使用比最小支持度低的支持度阈值来找出局部于S的频繁项集(记做LS )。然后，数据库的其余部分用于计算LS 中每个项集的实际频率。使用一种机制来确定是否所有的频繁项集都包含在LS 中。如果LS 实际包含了D中的所有频繁项集，则只需扫描一次D。否则，可以做第二次扫描来找出第一次扫描时遗漏的频繁项集。
实例分析
下面使用宠物商店为例来介绍Apriori算法的实际应用。
假设目前宠物商店的交易系统中只有下表1中的几张顾客购物清单。
表1 顾客购物清单
| 交易订单号 | 顾客购物清单 |
|---|---|
| 001 | 鸟、鸟笼、鸟食、猫粮、猫砂 |
| 002 | 鱼食、鸟、鸟笼 |
| 003 | 猫粮、狗粮、宠物玩具 |
| 004 | 鸟、鸟笼、鸟食 |
| 005 | 猫粮、猫砂、宠物玩具 |
我们的目标是利用过去顾客已购买商品的历史信息作为参考，推荐他们可能感兴趣的其他商品。因此在这里，宠物商店的管理者经过仔细考虑和讨论，确定只要一个商品组合的购买比例占到订单交易笔数的40%（即支持度），即可认为该商品组合中的商品集合是具有较强的购买关联性。因此，如果顾客在购物篮中加入了组合其中的一种商品，则系统就会立刻将组合中的其他商品推荐给顾客。
下面模拟Apriori算法完成这项工作：
（1）计算单项商品的频繁项集L[1]
首先要找到单项商品的候选商品频繁项集C[1]，然后过滤掉其中支持度小于40%的商品频繁项集从而得到L[1]，如表2所示。
表2 计算频繁项集L[1]
| 商品频繁项集C[1] | 存在的交易订单号 | 支持度 | 是够保留该商品 |
|---|---|---|---|
| 鸟 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟笼 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 猫粮 | 001，003，005 | 3/5 x 100% > 40% | 是 |
| 猫砂 | 001，005 | 2/5 x 100% = 40% | 是 |
| 鱼食 | 002 | 1/5 x 100% < 40% | 否 |
| 狗粮 | 003 | 1/5 x 100% < 40% | 否 |
| 宠物玩具 | 003,005 | 2/5 x 100% = 40% | 是 |
得到频繁项集L[1] = {{鸟}，{鸟笼}，{鸟食}，{猫粮}，{猫砂}，{宠物玩具}}。
（2）根据频繁项集L[1]生成候选频繁项集C[2]
顾名思义。C[2]即为商品数量为2的候选频繁项集，它是由单品频繁项集L[1]中的频繁项集两两组合而来的，这里直接给出结果。
得到候选频繁项集C[2] = {{鸟，鸟笼}，{鸟，鸟食}，{鸟，猫粮}，{鸟，猫砂}，{鸟，宠物玩具}，{鸟笼，鸟食}，{鸟笼，猫粮}，{鸟笼，猫砂}，{鸟笼，宠物玩具}，{鸟食，猫粮}，{鸟食，猫砂}，{鸟食，宠物玩具}，{猫粮，猫砂}，{猫粮，宠物玩具}，{猫砂，宠物玩具}}。
（3）计算单项商品频繁项集L[2]
利用候选频繁项集C[2]进行计算，过滤掉支持度小于40%的商品频繁项集得到L[2]，如表3所示。
表3 计算频繁项集L[2]
| 商品频繁项集C[2] | 存在的交易订单号 | 支持度 | 是否保留该商品 |
|---|---|---|---|
| 鸟，鸟笼 | 001，002，004 | 3/5 x 100% > 40% | 是 |
| 鸟，鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 鸟，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 鸟笼，鸟食 | 001，004 | 2/5 x 100% = 40% | 是 |
| 鸟笼，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟笼，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟笼，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 鸟食，猫粮 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟食，猫砂 | 001 | 1/5 x 100% < 40% | 否 |
| 鸟食，宠物玩具 | 无 | 0/5 x 100% < 40% | 否 |
| 猫粮，猫砂 | 001，005 | 2/5 x 100% = 40% | 是 |
| 猫粮，宠物玩具 | 003，005 | 2/5 x 100% = 40% | 是 |
| 猫砂，宠物玩具 | 005 | 1/5 x 100% < 40% | 否 |
得到频繁项集L[2] = {{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}}。
（4）根据频繁项集L[2]生成候选频繁项集C[3]
本步和第二步中C[2]的生成规则是一样的，这里强调一点，在Apriori算法中只允许差异为1的不同项集进行组合。例如在本次计算C[3]的候选频繁项集时，{鸟，鸟笼}和{鸟，鸟食}之间是可以组合的，而{鸟，鸟笼}和{猫粮，猫砂}由于这两个频繁项集的差异为2（超过了一个元素），则不能进行组合。
得到候选频繁项集C[3] = {{鸟，鸟笼，鸟食}，{猫粮，猫砂，宠物玩具}}。
（5）计算单项商品频繁项集L[3]
表4 计算频繁项集L[3]
| 商品频繁项集C[3] | 存在的交易订单号 | 支持度 |
|---|---|---|
| 鸟，鸟笼，鸟食 | 001，004 | 2/5 x 100% = 40% |
| 猫粮，猫砂，宠物玩具 | 005 | 1/5 x 100% < 40% |
得到频繁项集L[3] = {{鸟，鸟笼，鸟食}}。
（6）循环终结条件及获得最终的商品频繁项集
由于C4应由L[3]中的频繁项集组合而来，但L[3]中目前已没有可供继续连接的频繁项集，因此循环到此结束。
根据Apriori算法，本例中最终的商品频繁项集为L[1] ∪ L[2] ∪ L[3] ={{鸟}，{鸟笼}，{鸟食}，{猫粮}，{猫砂}，{宠物玩具}，{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}，{鸟，鸟笼，鸟食}}。
根据本例中宠物商店的需求，对客户兴趣度有意义的商品关联数据为{鸟，鸟笼}，{鸟，鸟食}，{鸟笼，鸟食}，{猫粮，猫砂}，{猫粮，宠物玩具}，{鸟，鸟笼，鸟食}。因此，宠物商店可根据以上数据来进行商品推荐。
Python实现Apriori算法
我们用字母形象化地表示上述所有商品，如下：
A:鸟类 B:鸟笼 C:鸟食 D:猫粮 E:猫砂 F:鱼食 G:宠物玩具 H:狗粮
#!coding=utf-8
import copy
#初始化数据集,计算单项的出现频率,存入项字典中
def caculate_item_frequency(data_set):
freq_set_dict={}
for t in data_set:
for i in t:
if i in freq_set_dict.keys():
freq_set_dict[i] += 1
else:
freq_set_dict[i] = 1
return freq_set_dict
#根据k-1项集生成候选k项集
def generate_candidate_set(frequency):
candidate_set=[]
k=len(frequency[0]) + 1
for f1 in frequency:
for f2 in frequency:
if f1[k-2] < f2[k-2]:
c = copy.copy(f1)
c.append(f2[k-2])
flag = True
for i in range(0,k-1):
s=copy.copy(c)
s.pop(i)
if s not in frequency:
flag=False
break
if flag and c not in candidate_set:
candidate_set.append(c)
return candidate_set
# 比较两列表是否相等
def compare_list(A,B):
if len(A) > len(B):
for b in B:
if b not in A:
return False
else:
for a in A:
if a not in B:
return False
return True
#Apriori算法入口
def apriori(data_set,minsupport):
candidate_set=[] #候选频繁项集
#计算所有支持度不小于minsupport的频繁1项集
total_items = len(T)
item_frequency_dict=caculate_item_frequency(T)
keys = item_frequency_dict.keys();
keys.sort()
candidate_set.append(keys)
frequent_set=[[]]
for item in candidate_set[0]:
if item_frequency_dict[item] * 1.0 / total_items >= minsupport:
frequent_set[0].append([item])
#计算频繁k项集
k=1
while frequent_set[k-1] != []:
#用k-1频繁项集生成候选频繁k项集
candidate_set.append(generate_candidate_set(frequent_set[k-1]))
#这里加入一个空集合放入frequent_set,用意在于如果有频繁k项集,
#就将所有的频繁k项集存放在这个空集合当中,如果没有频繁k项集则当作遍历结束条件
frequent_set.append([])
#遍历候选k项集
for c in candidate_set[k]:
count = 0
#遍历数据集,找出所有支持度不小于minsupport的候选项,将其加入到频繁k项集中
for t in data_set:
if compare_list(c,t):
count += 1
if count * 1.0 / total_items >= minsupport:
frequent_set[k].append(c)
k += 1
#打印输出所有频繁项集
outcome_set=[]
for f in frequent_set:
for x in f:
outcome_set.append(x)
return outcome_set;
#T=[['A','B','C','D'],['B','C','E'],['A','B','C','E'],['B','D','E'],['A','B','C','D']]
T=[['A','B','C','D','E'],['A','B','F'],['D','G','H'],['A','B','C'],['D','E','G']]
print apriori(T,0.4)