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确定後，關聯規則就可以得出來了。