组织完整的 Apriori 算法
Poblog 07月05日 2017
当前一个数项(k-1)的集合中项的个数大于0时
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
保留频繁项集并构建k+1项组成的候选项集的列表
算法使用(部分算法如scanD见上一篇)
dataSet=loadDataSet();//dataSet:
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
//
L, supportData=apriori(dataSet);//L:最终满足支持度的全部组合项
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
supportData:大部分记录的支持度记录
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
//
retList=aprioriGen(L[0],2);//retList:一项数字生成的两项的组合
[frozenset({2, 5}), frozenset({3, 5}), frozenset({1, 5}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 3})]
//
算法流程
#total apriori
def aprioriGen(Lk, k): #组合,向上合并
//Lk:数字项的集合
[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
k:与项集元素个数 k
2
//
#creates Ck 参数:频繁项集列表 Lk 与项集元素个数 k
retList = []
lenLk = len(Lk)
//lenLk:数字项的集合的长度
4
//
for i in range(lenLk):
//i:循环数字项的集合
0
//
for j in range(i+1, lenLk): #两两组合遍历
//j:往后依次获取数字项的组合
1
//
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
//L1:Lk[i]的前k-2项 L2:Lk[j]的前k-2项 k:2
//
L1.sort(); L2.sort()
//排序便于下面比较
//
if L1==L2:
retList.append(Lk[i] | Lk[j]) #set union
//#若两个集合的前k-2个项相同时,则将两个集合合并
//
return retList
#apriori
def apriori(dataSet, minSupport = 0.5):
//dataSet:点集
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
minSupport:最小支持度
//
C1 = createC1(dataSet)
//C1:dataSet最小
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
//
D = list(map(set, dataSet)) #python3
//D:dataSet list map化?好像没有必要直接使用dataSet也是可以求scanD
[{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]
//
L1, supportData = scanD(D, C1, minSupport)#单项最小支持度判断 0.5,生成L1
//L1:满足0.5的点集
[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
supportData:所有单数字的支持度
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75}
//
L = [L1]
//L:记录全部的频繁项,包含组合
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]]
//
k = 2
//组合个数的起点
//
while (len(L[k-2]) > 0):#创建包含更大项集的更大列表,直到下一个大的项集为空
//前一项数字个数的列表不为空时循环//
Ck = aprioriGen(L[k-2], k)#Ck
//使用前一个数字组合生成多一个数的数字组合:注(算法优化其实目前k直接是L[k-2]单个项的长度+1)
Ck: [frozenset({2, 5}), frozenset({3, 5}), frozenset({1, 5}), frozenset({2, 3}), frozenset({1, 2}), frozenset({1, 3})]
//
Lk, supK = scanD(D, Ck, minSupport)#get Lk
//Ck中满足支持度的点集和支持度情况
Lk:[frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})]
supK:{frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25}
//
supportData.update(supK)
//支持度存入
//
L.append(Lk)
//满足支持度的点组合存入
//
k += 1
//#继续向上合并 生成项集个数更多的
//
return L, supportData
//最终的频繁项和全部组合的支持度
//