编程实现Apriori算法

大数据课程上机应用，作业，记录以备复习

编程应用Apriori算法输出教材P159 表4-16的所有频繁项集（设最小支持度计数为2）

import sys
import copy

def init_pass(T):   #统计所有元素各自出现的总次数
    C = {}  #C为字典
    for t in T: 
        for i in t:
            if i in C.keys():
                C[i] += 1
            else:
                C[i] = 1
    return C  

def generate(F):#生成新的集合，好进行下一轮遍历，筛选，F是之前筛选出来的所有满足支持度的集合
    C = []
    #print("F={}".format(F))
    k = len(F[0]) + 1 #k此时代表这次要选的集合中每个集合由几个元素组成
    for f1 in F:
        for f2 in F:
            #print("f1[k-2]={0},f2[k-2]={1}".format(f1[k-2],f2[k-2]))
            if f1[k-2] < f2[k-2]: #使用k-2的原因之前k+1，然后数组下标从0开始，所有k-2刚好，就比如第一次生成时正好从下标0，也就是第一个元素开始
                c = copy.copy(f1)
                c.append(f2[k-2])
                #print("c={}".format(c))
                if c not in C:
                    C.append(c)
    return C #最返回

def compareList(A,B): #比较两个列表是否相等
    if len(A) <= len(B):
        for a in A:
            if a not in B:
                return False
    else:
        for b in B:
            if b not in A:
                return False
    return True
    
def apriori(T,minSupport):
    D=[]#暂存生成的所有索引，供之后筛选，存入F[k]中
    C=init_pass(T)  #先分析一项集
    keys=list(C.keys());#.keys()方法，求出字典中的索引
    keys.sort() 
    D.append(keys)#加入D集中
    F=[[]] #二维列表  F[0]存的是所有满足条件的一项集
    for f in D[0]:
        if C[f]>=minSupport:
            F[0].append([f])  #筛选出所有满足最小支持度的一项集
    k=1 #k代表的是几项集 第几次遍历

    while F[k-1]!=[]:  #k-1是因为下标从0开始
        D.append(generate(F[k-1]))
        F.append([])
        for c in D[k]:
            count = 0;
            for t in T:
                if compareList(c,t):
                    count += 1
            if count>= minSupport:
                F[k].append(c)
        k += 1

    U = []
    for f in F:
        for x in f:
            U.append(x)
    return U


T = [['面包','甜酱','芝麻酱'],['面包','芝麻酱'],['面包','芝麻酱','牛奶'],['面包','啤酒'],['牛奶','啤酒']]

Z= apriori(T,2)
for i in Z:
    print(set(i))

{'啤酒'}
{'牛奶'}
{'芝麻酱'}
{'面包'}
{'面包', '芝麻酱'}