推薦算法- Apriori（先驗算法）

先驗算法屬于關聯規則學習的經典算法之一, 被設計用來尋找交易數據的潛在關系。

關聯規則的定義：

其實就是找出類似 \(\{奶油, 面包\} \rightarrow \{飲料\}\) 的這種關系

關于蘊含關系如何獲得的，這里我們需要兩個評估的參數 置信度 和 支持度

支持度 support

定義:

其中S為全集，顯然該參數表示了元素 \(X\) 和 \(Y\) 相關性成正比，及交集在全集中所占的比例。

性質：

交換律：Support(X\rightarrow Y) = Support(Y\rightarrow X)$

置信度 cofidence

定義：

置信度表示了在\(X\)集合中 \(Y\) 所占的比例， 表示了 \(X\) 對 \(Y\) 的 包含性。

Apriori算法過程

知道上述兩個評價參數后，我們現在要做的是設定一個最小置信度和最小支持度， 找出滿足大于等于評價參數的數據。

首先我們思考一下樸素的做法， 如果單純的求出組合，那么僅僅求組合的復雜度在 \(O(2^N)\), 而交易數據通常很大，我們需要找到更優的算法。

這里我們可以根據最小置信度滿足交換律，先計算滿足最小置信度的集合。

分離計算（滿足最小支持度）

由于支持度滿足交換律，因此我們設滿足任意子集大于最小置信度的集合為頻繁項集。

對于滿足要求的 \(\{X, Y\}\) 我們稱為二階頻繁項集， 同理依次往后類推。

顯然頻繁項集滿足如下性質：

1. 任意頻繁項集的子集都是頻繁項集
2. 任意非頻繁項集的超集都不是頻繁項集

那么我們利用性質1， 可以從低階的頻繁項集產生高階的項集, 通過得到這些項集。

利用性質2， 我們利用低一階的項集去篩掉一定不符合頻繁項集的項。

Python 實現

"""
    Initial Data
"""


def create_data():
    dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
               ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
               ['Milk', 'Apple', 'Kidney Beans', 'Eggs'],
               ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'],
               ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]
    return dataset


def createK1(dataset):
    C1 = set()

    for t in dataset:
        for item in t:
            C1.add(frozenset([item]))

    return C1


"""
    Drop the data not fit with the theory
"""


def isApriori(Lksub1, Ck):
    for item in Ck:
        subset1 = Ck - frozenset([item])
        if subset1 not in Lksub1:
            return False
    return True


"""
    Generate Lk by Ck
"""


def generateLkbyCk(dataset, Ck, min_support, support_data):
    item_count = {}
    Lk = set()

    for item in Ck:
        for t in dataset:
            if item.issubset(t):
                item_count[item] = item_count.get(item, 0) + 1

    for item in item_count:
        if item_count[item] / len(dataset) >= min_support:
            Lk.add(item)
            support_data[item] = item_count[item] / len(dataset)

    return Lk


"""
    Generate Ck
"""


def createK(Lksub1, k):
    L1 = list(Lksub1)
    Ck = set()

    for i in range(len(L1)):
        for j in range(i + 1, len(L1)):
            l1 = list(L1[i])
            l2 = list(L1[j])
            l1.sort()
            l2.sort()

            if l1[:k - 2] == l2[:k - 2]:
                set1 = L1[i] | L1[j]
                if isApriori(Lksub1, set1):
                    Ck.add(set1)
    return Ck


def main():
    min_support = 0.5
    support_data = {}
    L = []
    K = 5
    dataset = create_data()
    C1 = createK1(dataset)
    L1 = generateLkbyCk(dataset, C1, min_support, support_data)
    Lksub1 = L1.copy()
    L.append(Lksub1)

    for k in range(2, K + 1):
        Ck = createK(Lksub1, k)
        Lk = generateLkbyCk(dataset, Ck, min_support, support_data)
        Lksub1 = Lk.copy()
        L.append(Lksub1)

    print(L[2])


if __name__ == '__main__':
    main()