数据挖掘之Apriori频繁项集挖掘

 def aprioriGen(Lk_1, k): #creates Ck

    
     """ 根据k-1项集产生候选k项集 
    
     Lk_1: k-1项集的列表 
    
    k: k项集的k         
    
     """     
    
     retList = [] 
    
     lenLk_1 = len(Lk_1)  # k-1项集的长度  
    
     for i in range(lenLk_1): 
    
     for j in range(i+1, lenLk_1):  
    
         L1 = sorted(list(Lk_1[i]))   # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素 
    
         L2 = sorted(list(Lk_1[j]))   # k等于2时, 1项集取空, k等于3时,2项集取第一个元素, k等于4时,3项集取前两个元素 
    
  
    
         if L1[:k-2]==L2[:k-2]: # 如果前k减2个元素相等 , 就将两几何求并  
    
             retList.append(Lk_1[i] | Lk_1[j]) #set union 
    
     return retList 
    
  
    
  
    
  
    
 def get_subset(ss): 
    
     """求一个k项集的所有k-1项集子集""" 
    
     ls = list(ss) 
    
     res = []  
    
     for i in range(len(ls)): 
    
     res.append(set(ls[:i] + ls[(i+1):])) 
    
     return res  
    
                 
    
  
    
      
    
 def check_in(Lk_1,ck): 
    
     """ 返回布尔值,  
    
     检验候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
    
     """ 
    
     i = 0  
    
     # 取出候选k项集的一个k-1项集子集 
    
     for ss_sub in get_subset(ck): 
    
     # 如果该k-1项集子集在在L_(k-1)中, 加1  
    
     if ss_sub in Lk_1: 
    
         i+= 1  
    
     # 返回候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
    
     return i == len(ck) 
    
  
    
  
    
 def cut_branch(Ck,Lk_1): 
    
     """剪枝,  
    
     只保留候选K项集集合中, 所有k-1项集都在L_(k-1) 的候选k项集 
    
     """ 
    
     Ck_res = []  
    
     # 取出一个候选k项集 
    
     for ck in Ck:  
    
     # 判断候选k项集的所有k-1项集子集 是否都在L_(k-1)中 
    
     flag = check_in(Lk_1,ck) 
    
     # 如果是, 保留该候选k项集 
    
     if flag :  
    
         Ck_res.append(ck)  
    
     return Ck_res  
    
          
    
      
    
 def createC1(dataSet): 
    
     """从数据集中构建一项集候选集,  
    
     将每个一项集都以frozenset的数据类型保存 
    
     因为frozenset可以作为字典的key, 常规的set不可以, 方便后续对候选项集计数 
    
     """ 
    
     C1 = [] 
    
     for transaction in dataSet: 
    
     for item in transaction: 
    
         if not [item] in C1: 
    
             C1.append([item]) 
    
     # frozenset 可以作为字典的key, set 不可以  
    
     return [frozenset(i) for i in C1] 
    
      
    
      
    
      
    
 def scanD(D, Ck, minSupport):         
    
     """ 
    
     D:数据集 
    
     Ck:候选k项集 
    
     minSupport:最小支持度阈值 
    
     """ 
    
     # 扫描数据集,确定Ck中每个候选的计数 
    
     ssCnt = {} 
    
     for tid in D: 
    
     for can in Ck: 
    
         if can.issubset(tid): 
    
             ssCnt[can] = ssCnt.get(can,0)+1 
    
      
    
     # 根据最小支持度阈值筛选出频繁k项集  
    
     retList = [] 
    
     supportData = {} 
    
     for key in ssCnt: 
    
     # 计算备选k项集的支持度 
    
     support = ssCnt[key] 
    
      
    
     # 如果支持度大于阈值, insert进k项集的结果列表 
    
     if support >= minSupport: 
    
         retList.insert(0,key) 
    
     # 不管支持度是否大于阈值, 都记录下该备选k项集的支持度  
    
     supportData[key] = support 
    
     return retList, supportData 
    
  
    
  
    
 def apriori(dataSet, minSupport): 
    
     C1 = createC1(dataSet) 
    
 #     print('C1:',C1) 
    
     D = [set(i) for i in dataSet] 
    
      
    
     # 检查C1中每个备选1项集的支持度, L1为筛选出的1项集, supportData为每个备选1项集的支持度 
    
     L1, supportData = scanD(D, C1, minSupport) 
    
     print(f'L1:{L1}','\n') 
    
     L = [L1] # 将1项集列表插入频繁k项集的结果列表 
    
  
    
     k = 2  # 2项集     
    
     # k项集为空的时候停止 
    
     while (len(L[k-2]) > 0):     
    
     Ck = aprioriGen(L[k-2], k)  # 连接步,产生备选k项集  
    
     print('过滤前:',len(Ck),Ck,'\n') 
    
     Ck = cut_branch(Ck,L[k-2])  # 剪枝   
    
     print('过滤后:',len(Ck),Ck,'\n') 
    
     Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk  扫描数据集,确认C_k中的每个候选k项集是否为频繁项集  
    
     print('筛选后:',len(Lk),Lk,'\n') 
    
     supportData.update(supK) 
    
     L.append(Lk)  
    
     k += 1 
    
  
    
     return L, supportData 
    
  
    
  
    
  
    
  
    
 data_ls =[['I1','I2','I5'], 
    
     ['I2','I4'], 
    
     ['I2','I3'], 
    
     ['I1','I2','I4'], 
    
     ['I1','I3'], 
    
     ['I2','I3'], 
    
     ['I1','I3'], 
    
     ['I1','I2','I3','I5'], 
    
     ['I1','I2','I3']] 
    
  
    
 L, supportData =apriori(data_ls,minSupport = 2) 
    
 print('L:',L,'\n') 
    
 print("supportData:",supportData)