一、關聯規則

關聯規則，顧名思義，就是尋找事物之間的關聯關系。比如《啤酒與尿布》中，在某個特定時間段，會出現啤酒與尿布同時出現在購物籃中的現象，且出現頻率非常高。調研發現這是一群愛喝啤酒的奶爸群體。如果可以通過類似的方式挖掘更多特定的群體需求，就可以進行交叉銷售或捆綁銷售來提升銷售額和利潤。Apriori算法就是經典的尋找物品的關聯算法。

二、Apriori算法原理

1、基礎概念
項集 ：包含0個或者多個項的集合稱為項集
頻繁項集：那些經常一起出現的物品集合

2、關聯規則
規則A->B的度量包括支持度，置信度
支持度：項集A、B同時發生的概率 —P(A∩B)
置信度：當A發生時發生B的概率—P(B|A) = P(A∩B)/P(A)
兩者都會有一個閾值，支持度低于閾值說明A,B同時出現的概率低，兩者有沒有關聯關系都對實際業務沒啥幫助；置信度低于閾值說明A在發生情況下B的發生可能性小，我們想要挖掘的是在A發生時B有很大可能也會發生的情況。
舉例：
方便面 -> 火腿腸：{支持度：0.2， 置信度：0.8}
說明方便面和火腿腸同時出現的概率20%，這個概率已經相當高了，而當購買了方便面時，有80%的可能性會購買火腿腸，如果兩者分開陳列都能達到這樣的效果，那交叉陳列或者捆綁銷售肯定會進一步提升置信度。

一般支持度和置信度的閾值設定有2種方法：1是聽取行業專家的意見，2是求所有項集的平均值或中位數

3、自連接和剪枝原理

自連接是保證除掉最后一個元素后相同的情況下，將兩者求并集得到新的項集。
剪枝步
① 支持度：是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。比如{A},{B}都是不頻繁的，那么{A,B}也是不頻繁的，因為單個都發生的可能性極低了，那組合在一起不是更低了嗎？（剪枝法是算法科學中一種比較重要的思路，是利用數據特性或一些其余技巧過濾掉那些沒必要計算的情況，降低算法的時間復雜度）
單品組合也可以使用笛卡爾積：兩個集合中的元素做一對一的循環匹配，再去掉重復的
② 置信度：如果{A,B,C}->{D}是置信度低的，那么{A,B}->{C,D},{A}->{B,C,D},{B}->{A,C,D}都是低的

4、Apriori算法流程
思路：
通過迭代，檢索出所有頻繁項集；利用頻繁項集構造出關聯規則

具體做法：
首先，找出頻繁“1項集”的集合，該集合記作L1。L1用于找頻繁“2項集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項集”

算法步驟：
① 發現頻繁項集，過程為（1）掃描（2）計數（3）比較（4）產生頻繁項集（5）連接、剪枝，產生候選項集 重復步驟（1）~（5）直到不能發現更大的頻集
② 產生關聯規則:
<> 對于每個頻繁項集L，產生L的所有非空子集；
<> 對于L的每個非空子集S，如果
P（L）/P（S）≧min_conf
則輸出規則“SàL-S”

5、關聯規則價值
通過Apriori算法得到了滿足最小支持度和最小置信度的關聯關系，但是否就能直接用了呢？
一般還會增加以下考量：
① 提升度
提升度：衡量A的發生是否促進了B的發生—P(B|A) / P(B)
前者是A發生時B發生的概率，后者是在全樣本空間中B發生的概率，如果大于1，說明A發生時B發生的概率要列高，有提升作用；如果等于1，說明沒有影響；如果小于1，說明A發生能抑制B的發生。
② 是否去除熱門商品影響
熱門商品是活躍度較高的商品，基本上熱門商品之間的支持度和置信度都會很高，但這樣的關系是沒有太大意義的，因為不做任何處理，他們都已經賣得相當好了。
④ 是否新穎
所謂新穎就是要尋找一些平常想不到但是確實又有這樣的需求的群體存在的組合，才能對業務有較大幫助。像鮮奶和酸奶，啤酒和葡萄酒這種司空見慣的組合模式，也沒有太大價值

6、稀有模式
當A,B各自的支持度很高，但是AB的支持度卻非常非常低，那么AB就是稀有模式，說明A,B之間存在負相關關系。一般來說，P(A∩B) 遠遠小于 P(A)*P(B)，就能說明A和B是強負相關
挖掘負相關的場景，可以用來預測用戶在某一領域的預算規模和購物規律，比如買了電腦的，可能就不會再買PAD；也可以用來發現有關聯的疾病，比如在得過A疾病的病患，患B疾病的比例要比普通人小很多等

三、Apriori算法的Python實現

這里借鑒博主-gamer_gyt的代碼

            
              from numpy import *


def loadDataSet():
    return [[1, 2, 3, 4], [2, 3, 4, 5], [1, 2, 3, 5], [1, 2, 4, 5]]

# 創建L1項集
def createC1(dataSet):
    C1 = []
    for transaction in dataSet:
        for item in transaction:
            if not [item] in C1:
                C1.append([item])
    C1.sort()
    return map(frozenset, C1)  # frozenset是不可變集合，相對集合來說，好處是可以做為字典的鍵

#計算支持度
def scanD(D, Ck, minSupport):
    ssCnt = {}
    for tid in D:
        for can in Ck:
            if can.issubset(tid):  # 集合用法：檢查是否是子集
                ssCnt[can] = ssCnt.get(can, 0) + 1
    numItems = float(len(D))
    retList = []
    supportData = {}
    for key in ssCnt:
        support = ssCnt[key] / numItems
        if support >= minSupport:  # 判斷是否滿足最小支持度
            retList.insert(0, key)
        supportData[key] = support
    return retList, supportData


# 由Lk頻繁項集生成LK+1項集
def aprioriGen(Lk, k):
    retList = []
    lenLk = len(Lk)
    for i in range(lenLk):
        for j in range(i + 1, lenLk):
            # 前k-2項相同時，將兩個集合合并
            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
            L1.sort(); L2.sort()
            if L1 == L2:
                retList.append(Lk[i] | Lk[j])  # 集合用法：并集
    return retList

# 輸出所有頻繁項集和支持度
def apriori(dataSet, minSupport=0.5):
    C1 = list(createC1(dataSet))
    D = list(map(frozenset, dataSet))
    L1, supportData = scanD(D, C1, minSupport)
    L = [L1]
    k = 2
    while (len(L[k-2]) > 0):  # 判斷項集是否為空
        Ck = aprioriGen(L[k-2], k)
        Lk, supK = scanD(D, Ck, minSupport)
        if len(Lk)>0:
            L.append(Lk)
            supportData.update(supK)
            k += 1
        else:
            break
    return L, supportData  


def conf(freqset,H,support,br1,min_f = 0.5):
    p = []
    i = 1
    for con in H:
        print(i)
        i += 1
        print(type(con))
        conf = support[freqset]/support[freqset-con]
        if conf>=min_f:
            print(freqset-con,con)
            br1.append(((freqset-con),con,conf))
            p.append(con)
    return p


def rules(freqset, H, support, br1, min_f=0.5):
    m = len(H[0])
    while (len(freqset)>m):
        H = conf(freqset, H, support, br1, min_f)
        if (len(H)>1):
            H = apriori(H, m+1)
            m += 1
        else:
            break


def generator(L,support,min_f=0.5):
    bigrules = []
    print(len(L))
    for i in range(1, len(L)-1):
        for freqset in L[i]:
            H1 = [frozenset([item]) for item in freqset]
            rules(freqset, H1, support, bigrules, min_f)
    return bigrules


dataSet = loadDataSet()
C1 = list(createC1(dataSet))
D = list(map(frozenset, dataSet))
L1, suppData = scanD(D, C1, 0.5)
L, support = apriori(dataSet)
print(L)
g = generator(L, support, min_f=0.3)
print(g)