Apriori算法及python代码实现
Apriori算法的作用就是在数据集中寻找满足最低支持度的数据项集及其频繁程度。这个概念可能不够直观。比如你经营一家超市那么你需要分析多份顾客购买记录来发现哪些种类的商品经常被同时购买。具体来说首先你需要收集所有商品的信息然后统计每个物品对整个数据集的支持度也就是有多少比例的顾客会同时购买它接着筛选出那些支持度超过设定阈值的商品组合最后就能得到所有符合条件的商品集合这就是Apriori算法的基本思路。
在阐述该算法的具体操作流程之前, 我认为首先应当对需要解决的问题进行大致分析, 经过分析会发现, 如果一个商品集合被同时购买的次数少于k, 那么任何包含该商品集合的商品集合都会被同时购买的次数也必定少于k, 因此这启示我们应从小到大的方式逐步推进解决问题.
下面按我自己的理解描述和下Apriori算法的具体步骤：
既然按照规模由小到大逐步推进的方式进行处理的话,那么首先要做的是找出所有规模为1的数据集合,这部分操作需要我们遍历整个数据集中的每一项数据,然后根据特定条件筛选出符合条件的结果并将其收集起来并放入一个集合L中（其中L₁是一个集合,其元素均为规模为1的所有可能结果）。
所有解构成规模为i的集合记作Li；每一次从Li中生成下一个集合Li+1；寻找的方式是从Li中选取任意两个子集（每个子集都是一个集合），只要这两者的前缀部分（即它们共享相同的前缀部分）完全一致；这样就可以构造出一个新的子集；接着，在新子集中添加各自的第i项；最后将这一新子集加入到新的候选集合中并标记为Ci+1
根据Apriori算法的特点，在生成候选集C_{i+1}时，其中任意一个元素都是一个集合，并且该集合必须包含在所有之前生成的列表L₁, L₂,…, L_i中；如果某个子集不在这些列表中的任何一个中，则会直接移除该元素；随后需要遍历整个数据库并计算其出现频率是否不低于k次；符合条件的所有项将构成L_{i+1}。
4回到2，假如Li为空时，算法停止。
附上python代码如下：
def creatDataSet():
dataset= [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
return dataset
def apriori(minspt,dataset):
num=len(dataset)
ps=num*minspt
level=1
C=ToC1(dataset)
supt={}
L,supt=CtoL(C,ps,dataset)
Lres=[L]
while 1:
C=un(L,level)
L,supk=CtoL(C,ps,dataset)
if len(L)==0:
break
supt.update(supk)
Lres.append(L)
level+=1
return Lres,supt
def ToC1(dataset):
C=[]
for da in dataset :
for yu in da :
if not [yu] in C:
C.append([yu])
C.sort()
return map(frozenset,C)
def CtoL(C,ps,dataset):
cnt={}
L=[]
su={}
for ci in C:
for da in dataset:
if ci.issubset(da):
if not cnt.has_key(ci): cnt[ci]=1
else: cnt[ci]+=1
for cn in cnt:
if cnt[cn]>=ps:
L.append(cn)
su[cn]=cnt[cn]
return L,su
def un(Lk,level):
C=[]
lenk=len(Lk)
for i in range(lenk):
for j in range(i+1, lenk):
L1= list(Lk[i])[:level-1]
L2= list(Lk[j])[:level-1]
L1.sort()
L2.sort()
if L1==L2:
C.append(Lk[i]|Lk[j])
return C