(原创)频繁模式挖掘Apriori算法详解

? ? ? 本数据挖掘算法是本人进入研究生学习阶段进行的第一项“比较难”的学习，下文除了源代码有参考Zealseeker博主之外均为原创手打，如有哪里写的不严谨，望请谅解。

? ? ? 首先频繁模式(Frequent Patten)表示频繁的出现在数据集中的模式，举个例子，去烧烤摊点串，这种菜单上的内容就是一种频繁模式，因为会有某种串被点了很多根，那么这就视为是一种“频繁”的成员，同时还有两个比较重要的概念是“支持度”和“置信度”，支持度表示表示两种事务同时发生的概率，举个例子，这家店今天有一百桌吃饭，其中同时点了羊肉串和牛肉串的有20桌，那么就认为该事件的支持度为20%；同时，点了牛肉串的有50桌，在这50桌里有20桌点了羊肉串，那么支持度为40%。“最小支持度阈值”即我们设定的支持度下限，“最小置信度阈值同理”。

? ? ? Apriori使用一种逐层迭代的方法来搜索频繁项集，所谓频繁项集，即在上文中出现的“牛肉串、羊肉串同时购买”这样的两种或多种时间同时发生并且至少达到预设的最小支持度的事件。下面我依据《数据挖掘：概念与技术（第三版）》中的某分店实物数据进行详细阐述。

? ? ? T100=[I1,I2,I5]

? ? ? T200=[I2,I4]

? ? ? T300=[I2,I3]

? ? ? T400=[I1,I4]

? ? ? T500=[I1,I3]

? ? ? T600=[I2,I3]

? ? ? T700=[I1,I3]

? ? ? T800=[I1,I3,I5]

? ? ? T900=[I1,I3]

在这里我设置最小频繁度为2，即出现了两次我就认为它是频繁的。

? ? ? 如果用传统的思想解决这个问题，我们会找到满足最小频繁度的一成员频繁项集，随即根据排列组合用两个for循环遍历所有的情况，在上面的原始数据中，I1~I5均是频繁的；在下面的寻找二成员频繁项集中就会排列组合出所有的情况，在这些情况中进行筛选。例子中的原始数据非常小，看起来不复杂，如果数据量巨大，光排列组合加每个集合对比这两个工作就会产产生指数倍的复杂度，最可怕的是其中可能会有大量的运算是无效的，因为某集合如果不是频繁的，那么更大的集合也一定不频繁，传统笨方法会将这种情况也进行运算，因此消耗大量计算及资源。

? ? ? Apriori算法采用了一种新颖的“先验性质”，即频繁项集的所有非空子集也一定是频繁的。根据这个原则，Apriori将运算分为两步：（1）连接步 ?（2）剪枝步

? ? ? （1）连接步：连接步意味着小的频繁集合如何变成更大的集合，就像原始数据中I1可以跟I2变成['I1','I2']，以此类推，再复杂一点比如(1,2),(1,3),5),(2,4),5)这样的集合连接方法是：如果每个集合中有k-1项，前k-2项都相同，那么就把他们组成更大的k项集合，因此可以组成(1,2,3,4,5)组成四个成员的集合同理。

? ? ? （2）剪枝步：剪枝步优先将该集合内的所有成员进行一次排列组合，比如(1,3)能排列成(1,3)，（代码中使用itertools.combinations函数来快速分割）,其中这三个子集全都是频繁的，那么我们就认为(1,3)是频繁的，并append()到一个装有频繁项集列表中；如果它的子集中有一个不是频繁的，那它就不频繁，拒绝append。

? ? ? 下面的代码是强化注释版Apriori算法，亲测能运行，注释非常之详细，傻瓜级。

#coding:utf-8
import itertools

class Apriori:
    def __init__(self,min_sup=0.2,dataDic={}):
        self.data = dataDic
        self.size = len(dataDic) #Get the number of events
        self.min_sup = min_sup
        self.min_sup_val = min_sup * self.size #这个数值是频繁算法的分子整数部分
    def find_frequent_1_itemsets(self):
        FreqDic = {} #{itemset1:freq1,itemsets2:freq2}  不管频繁度如何，先计算频繁度，然后装到这里面
        for event in self.data: #event表示字典里的键值，比如T100
            for item in self.data[event]:
                if item in FreqDic: #该成员是否出现过，出没出现过都要对它进行赋值
                    FreqDic[item] += 1 #出现过则+1
                else:
                    FreqDic[item] = 1 #没出现过则初始值为1
        L1 = []
        for itemset in FreqDic: #遍历第一轮“频繁”的成员
            if itemset >= self.min_sup_val: #如果频繁度大于设定值
                L1.append([itemset]) #将该成员推入列表,仅仅是将成员推入列表，频度不管
        return L1

    def has_infrequent_subset(self,c,L_last,k): #这是一个进行排列组合的函数
        subsets = list(itertools.combinations(c,k-1)) #在列表c中选择k-1个元素进行无序组合
        for each in subsets: #遍历这些组合的情况
            each = list(each) #把元素强制转换成列表
            if each not in L_last: #如果上一轮筛选出的集合中的成员没有在该组合中出现，则返回一个True，出现过则继续遍历所有组合的情况
                return True
        return False
            
    def apriori_gen(self,L_last): #L_last means frequent(k-1) itemsets 难点！！！
        k = len(L_last[0]) + 1 #len()对于列表，则返回成员的个数 如['I1','I2']就返回2
        Ck = [] #候选项集集合
        for itemset1 in L_last: #循环遍历L_last中的成员
            for itemset2 in L_last:
                #join step
                flag = 0
                for i in range(k-2):
                    if itemset1[i] != itemset2[i]:
                        flag = 1 #the two itemset can't join
                        break
                if flag == 1:
                    continue
                if itemset1[k-2] < itemset2[k-2]:
                    c = itemset1 + [itemset2[k-2]] #例：['I1']<['I2']成立，则推入一个['I1','I2']，并且先不计算它的频繁度
                else:
                    continue
                     #pruning setp
                if self.has_infrequent_subset(c,k):
                    continue
                else:
                    Ck.append(c) #候选项集集合,还没有计算频繁度，先把各种组合扔进去
        return Ck

    def do(self):
        L_last = self.find_frequent_1_itemsets()
        L = L_last
        i = 0
        while L_last != []: #只要本组频繁项集不空则继续循环
            Ck = self.apriori_gen(L_last) #候选项集集合(仅仅是各种排列组合，没筛选频繁度)推入Ck中
            FreqDic = {}
            for event in self.data: #遍历原始Data数据
                #get all suported subsets
                for c in Ck: #遍历候选的所有项集集合
                    if set(c) <= set(self.data[event]):#set()表示无序不重复元素集,如果c元素集是原始数据这个集合的子集
                        if tuple(c) in FreqDic: #如果元组c在字典中
                            FreqDic[tuple(c)]+=1 #这个元组的值+1，即又出现了一次
                        else:
                            FreqDic[tuple(c)]=1
            print FreqDic #将候选项集集合，以及出现的次数，以字典的形式打印出来，到这里时仍然没计算频繁度
            Lk = [] #满足频繁度集合的列表
            for c in FreqDic: #遍历字典里的所有候选集合
                if FreqDic[c] > self.min_sup_val: #如果大于设定的频繁度
                    Lk.append(list(c)) #将该列表推入列表Lk中
            L_last = Lk #将该列表定义为满足频繁度的最后一组列表
            L += Lk #最终结果的列表为L
        return L

#******Test******
Data = {'T100':['I1','I2','I5'],'T200':['I2','I4'],'T300':['I2','I3'],'T400':['I1','T500':['I1','T600':['I2','T700':['I1','T800':['I1','I3','T900':['I1','I3']}

a=Apriori(dataDic=Data)
print a.do()