Apriori算法实例

学习Apriori算法首先要了解几个概念：项集、支持度、置信度、最小支持度、最小置信度、频繁项集。

支持度：项集A、B同时发生的概率称之为关联规则的支持度。

置信度：项集A发生的情况下，则项集B发生的概率为关联规则的置信度。

最小支持度：最小支持度就是人为按照实际意义规定的阈值，表示项集在统计意义上的最低重要性。
最小置信度：最小置信度也是人为按照实际意义规定的阈值，表示关联规则最低可靠性。
如果支持度与置信度同时达到最小支持度与最小置信度，则此关联规则为强规则。
频繁项集：满足最小支持度的所有项集，称作频繁项集。
（频繁项集性质：1、频繁项集的所有非空子集也为频繁项集；2、若A项集不是频繁项集，则其他项集或事务与A项集的并集也不是频繁项集）

#Apriori算法
from numpy import *
import timedef loadDataSet():return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]def createC1(dataSet):C1 = []for transaction in dataSet:for item in transaction:if not [item] in C1:C1.append([item])C1.sort()return list(map(frozenset,C1))def scanD(D,Ck,minSupport):ssCnt = {}for tid in D:for can in Ck:if can.issubset(tid):if not can in ssCnt:ssCnt[can] = 1else:ssCnt[can] += 1numItems = float(len(D))retList = []supportData = {}for key in ssCnt:support = ssCnt[key]/numItemsif support >= minSupport:retList.append(key)supportData[key] = supportprint(retList)return retList, supportDatadef aprioriGen(Lk, k):lenLk = len(Lk)temp_dict = {}for i in range(lenLk):for j in range(i+1, lenLk):L1 = Lk[i]|Lk[j]if len (L1) == k:if not L1 in temp_dict:temp_dict[L1] = 1return list(temp_dict)
def apriori(dataSet,minSupport =0.5):C1 = createC1(dataSet)D =list(map(set,dataSet))L1,supportData = scanD(D,C1,minSupport)L=[L1]k = 2while (len(L[k-2])>0):Ck = aprioriGen(L[k-2],k)Lk,supk=scanD(D,Ck,minSupport)supportData.update(supk)L.append(Lk)k +=1return L,supportDatadataSet = loadDataSet()
begin_time = time.time()
L,suppData = apriori(dataSet)