Apriori算法（频繁集与关联分析）

这个算法用来发现最常一起出现的类，例如超市可以利用这个算法来看什么商品最经常一起出现，从而在摆放位置上进行优化，一个很有名的例子是美国中西部一家超市发现周四男人们经常会买啤酒和尿布，但是即使发现了这个规则，还是没有将其摆在一起,说明超市按照种类摆放的方法已经根深蒂固了。。。不过将这两个摆放在一起还是怪怪的哈哈哈

（一）Apriori原理

如图所示，5个商品的组合模式就有

 种，当商品变大的时候，计算规模会很大，由此做出以下改进，若是A不是频繁集，那么对于所有的

，B也不是频繁集。很显然当商品a不怎么出现，商品a&b肯定也是不怎么出现的。

（二）创建以frozenset为返回值的map地址

之所以用frozenset，是因为后面生成子项的时候需要用到集合的操作，同时又需要集合元素作为字典的key值，所以这里返回类型为frozenset。注意在python3中map返回的是地址，而且不能做多次迭代运算，一次迭代后指针指向的就为空，这是个巨坑，小心！

def CreatC1(dataSet):
    A=[]
    for i in dataSet:
        for j in i:
            if [j] not in A:
                A.append([j])
    A.sort()
    return map(frozenset,A)
           

（三）判断是否为频繁项

def scan(D,ck,minsupport):
    ssCnt={}
    for tid in ck:#一定要先迭代ck 
        for can in D:
            if tid.issubset(can):
                if tid not in ssCnt:
                    ssCnt[tid]=1
                else:
                    ssCnt[tid]+=1
    numItems=float(len(D))
    retlist=[]
    for key in ssCnt:
        support=ssCnt[key]/numItems
        if support>=minsupport:
            retlist.insert(0,key)
    return retlist
           

（四）由子项频繁集生成超集

例如当确定{1}，{2}为频繁集之后，我们需要生成两个元素的{1,2}，然后去判断是否为频繁集，生成的算法如下：Lk为子集集合，k为需要生成的元素每一项的长度，例如传入aprioriGen([[1],[2],[3]],2) aprioriGen([[1,2],[2,3],[1,3]],3) 

def aprioriGen(Lk,k):
    retList=[]
    lenLk=len(Lk)
    for i in range(lenLk):
        for j in range(i+1,lenLk):
            L1=list(Lk[i])
            L1=L1[:k-2]
            L2=list(Lk[j])
            L2=L2[:k-2]
            L1.sort()
            L2.sort()
            if L1==L2:
                retList.append(set(Lk[i])|set(Lk[j]))
    return retList
           

（五）Apriori算法

def apriori(dataset,minsupport):
    frequent=[]
    C1=CreatC1(dataset)
    retlist=scan(dataset,C1,minsupport)
    frequent.extend(retlist)
    lenC1=len(retlist)#retlist
    if(lenC1==1):
        return frequent
    else:
        Lk=retlist
        for i in range(1,lenC1):
            ck=aprioriGen(Lk,i+1)
            ck=map(frozenset,ck)
            retlist=scan(dataset,ck,minsupport)
            frequent.extend(retlist)
            Lk=retlist
    return frequent
           

上述完成了频繁集的获取。

（六）从频繁项集中挖掘关联规则

关联规则从频繁项集元素大于2的开始，所谓的关联规则，定义有A->B=support（A|B）/support(A)

很显然当频繁集以及对应的support确定后，关联规则就可以得出来了。