今天是機器學習專題的第19篇文章，我們來看經典的Apriori演算法。

Apriori演算法號稱是十大數據挖掘演算法之一，在大數據時代威風無兩，哪怕是沒有聽說過這個演算法的人，對於那個著名的啤酒與尿布的故事也耳熟能詳。但遺憾的是，隨著時代的演進，大數據這個概念很快被機器學習、深度學習以及人工智慧取代。即使是拉攏投資人的創業者也很少會講到這個故事了，雖然時代的變遷令人唏噓，但是這並不妨礙它是一個優秀的演算法。

我們來簡單回顧一下這個故事，據說在美國的沃爾瑪超市當中，啤酒和尿布經常被擺放在同一個貨架當中。如果你仔細觀察就會覺得很奇怪，啤酒和尿布無論是從應用場景還是商品本身的屬性來分都不應該被放在一起，為什麼超市要這麼擺放呢？

看似不合理的現象背後往往都有更深層次的原因，據說是沃爾瑪引進了一種全新的演算法，它分析了所有顧客在超市消費的記錄，然後計算商品之間的關聯性，發現這兩件商品的關聯性非常高。也就是說有大量的顧客會同時購買啤酒和尿布這兩種商品，所以經過數據的分析，沃爾瑪下令將這兩個商品放在同一個貨架上進行銷售。果然這麼一搞之後，兩種商品的銷量都提升了。

這個在背後分析數據，出謀劃策充當軍師一樣決策的演算法就是Apriori演算法。

關聯分析與條件概率

我們先把這個故事的真假放在一邊，先來分析一下故事背後折射出來的資訊。我們把問題進行抽象，沃爾瑪超市當中的商品種類大概有數萬種，我們的演算法做的其實是根據售賣數據計算分析這些種類之間的相關性。專業術語叫做關聯分析，這個從字面上很好理解。但從關聯分析這個角度出發，我們會有些不一樣的洞見。

我們之前都學過條件概率，我們是不是可以用條件概率來反應兩個物品之間的關聯性呢？比如，我們用A表示一種商品，B表示另外一種商品，我們完全可以根據所有訂單的情況計算出P(A|B)和P(B|A)，也就是說用戶在購買了A的情況下會購買B的概率以及在購買B的情況下會購買A的概率。這樣做看起來也很科學啊，為什麼不這樣做呢，還要引入什麼新的演算法呢？

這也就是演算法必要性問題，這個問題解決不了，我們好像會很難說服自己去學習一門新的演算法。其實回答這個問題很簡單，就是成本。大型超市當中的商品一般都有幾萬種，而這幾萬種商品的銷量差異巨大。一些熱門商品比如水果、蔬菜的銷量可能是冷門商品，比如冰箱、洗衣機的上千倍甚至是上萬倍。如果我們要計算兩兩商品之間的相關性顯然是一個巨大的開銷，因為對於每兩個商品的組合，我們都需要遍歷一遍整個數據集，拿到商品之間共同銷售的記錄，從而計算條件概率。

我們假設商品的種類數是一萬，超市的訂單量也是一萬好了，那麼兩兩商品之間的組合就有一億條，如果再乘上每次計算需要遍歷一次整個數據集，那麼整個運算的複雜度大概會是一萬億。如果再考慮多個商品的組合，那這個數字更加可怕。

但實際上一個大型超市訂單量肯定不是萬級別的，至少也是十萬或者是百萬量級甚至更多。所以這個計算的複雜度是非常龐大的，如果考慮計算帶來的開銷，這個問題在商業上就是不可解的。因為即使算出來結果帶來的收益也遠遠無法負擔付出的計算代價，這個計算代價可能比很多人想得大得多，即使是使用現成的雲計算服務，也會帶來極為昂貴的開銷。如果考慮數據安全，不能使用其他公司的計算服務的話，那麼自己維護這些數據和人工帶來的消耗也是常人難以想像的。

如果想要得出切實可行的結果，那麼優化演算法一定是必須的，否則可能沒有一家超市願意付出這樣的代價。

在我們介紹Apriori演算法之前，我們可以先試著自己思考一下這個問題的解法。我真的試著想過，但是我沒有得到很好的答案，對比一下Apriori演算法我才發現，這並非是我個人的問題，而是因為我們的思維有誤區。

如果你做過LeetCode，學過演算法導論和數據結構，那麼你在思考問題的時候，往往會情不自禁地從最優解以及最佳解的方向出發。反應在這個問題當中，你可能會傾向於找到所有高關聯商品，或者是計算出所有商品對之間的關聯性。但是在這個問題當中，前提可能就是錯的。因為答案的完備性和複雜度之間往往是掛鉤的，找出所有的答案必然會帶來更多的開銷，而且落實在實際當中，犧牲一些完備性也是有道理的。因為對於超市而言，更加關注高銷量的商品，比如電冰箱和洗衣機，即使得出結論它們和某些商品關聯性很高對超市來說也沒有太大意義，因為電冰箱和洗衣機一天總共也賣不出多少台。

你仔細思考就會發現這個問題和演算法的背景比我們一開始想的和理解的要深刻得多，所以讓我們帶著一點點敬畏之心來看看這個演算法的詳細吧。

頻繁項集與關聯規則

在我們具體了解演算法的原理之前，我們先來熟悉兩個術語。第一個屬於叫做頻繁項集，英文是frequent item sets。這個翻譯很接地氣，我們直接看字面意思應該就能理解。意思是經常會出現在一起的物品的集合。第二個屬於叫做關聯規則，也就是兩個物品之間可能存在很強的關聯關係。

用啤酒和尿布的故事舉個例子，比如很多人經常一起購買啤酒和尿布，那麼啤酒和尿布就經常出現在人們的購物單當中。所以啤酒和尿布就屬於同一個頻繁項集，而一個人買了啤酒很有可能還會購買尿布，啤酒和尿布之間就存在一個關聯規則。表示它們之間存在很強的內在聯繫。

有了頻繁項集和關聯規則我們會做什麼事情？很簡單會去計算它們的概率。

對於一個集合而言，我們要考慮的是整個集合出現的概率。在這個問題場景當中，它的計算非常簡單。即用集合當中所有元素一起出現的次數，除以所有的數據條數。這個概率也有一個術語，叫做支援度，英文稱作support。

對於一個關聯規則而言，它指的是A物品和B物品之間的內在關係，其實也就是條件概率。所以A->B關聯規則的概率就是P(AB)/P(A)和條件概率的公式一樣，不過在這個問題場景當中，也有一個術語，叫做置信度，英文是confidence。

其實confidence也好，support也罷，我們都可以簡單地理解成出現的概率。這是一個計算概率的模型，可以認為是條件概率運算的優化。其中關聯規則是基於頻繁項集的，所以我們可以先把關聯規則先放一放，先來主要看頻繁項集的求解過程。既然頻繁項集的支援度本質上也是一個概率，那麼我們就可以使用一個閾值來進行限制了。比如我們規定一個閾值是0.5，那麼凡是支援度小於0.5的集合就不用考慮了。我們先用這個支援度過一遍全體數據，找出滿足支援度限制的單個元素的集合。之後當我們尋找兩個元素的頻繁項集的時候，它的候選集就不再是全體商品了，而只有那些包含單個元素的頻繁項集。

同理，如果我們要尋找三項的頻繁項集，它的候選集就是含有兩項元素的頻繁項集，以此類推。表面上看，我們是把候選的範圍限制在了頻繁項集內從而簡化了運算。其實它背後有一個很深刻的邏輯，即不是頻繁項集的集合，一定不可能構成其他的頻繁項集。比如電冰箱每天的銷量很低，它和任何商品都不可能構成頻繁項集。這樣我們就可以排除掉所有那些不是頻繁項集的所有情況，大大減少了運算量。

上圖當中的23不是頻繁項集，那麼對應的123和023顯然也都不是頻繁項集。其實我們把這些非頻繁的項集去掉，剩下的就是頻繁項集。所以我們從正面或者是反面理解都可以，邏輯的內核是一樣的。

Apriori演算法及實現

其實Apriori的演算法精髓就在上面的表述當中，也就是根據頻繁項集尋找新的頻繁項集。我們整理一下整個演算法的流程，然後一點點用程式碼來實現它，對照程式碼和流程很容易就搞清楚了。

首先，我們來創建一批假的數據用來測試：

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

下面我們要生成只有一個項的所有集合。這一步很好理解，我們需要對所有有交易的商品生成一個清單，也就是將所有交易記錄中的商品購買記錄進行去重。由於我們生成的結果在後序會作為dict的key，並且我們知道set也是可變對象，也是不可以作為dict中的key的。所以我們要做一點轉換，將它轉換成frozenset，它可以認為是不可以修改的set。

def individual_components(dataset):
    ret = []
    for data in dataset:
        for i in data:
            ret.append((i))
    # 將list轉化成set即是去重操作
    ret = set(ret)
    return [frozenset((i, )) for i in ret]

執行過後，我們會得到這樣一個序列：

[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]

上面的這個序列是長度為1的所有集合，我們稱它為C1，這裡的C就是component，也就是集合的意思。下面我們要生成的f1，也就是長度為1的頻繁集合。頻繁集合的選取是根據最小支援度過濾的，所以我們下面要實現的就是計算Ck中每一個集合的支援度，然後過濾掉那些支援度不滿足要求的集合。這個應該也很好理解：

def filter_components_with_min_support(dataset, components, min_support):
    # 我們將數據集中的每一條轉化成set
    # 一方面是為了去重，另一方面是為了進行集合操作
    dataset = list(map(set, dataset))
    # 記錄每一個集合在數據集中的出現次數
    components_dict = defaultdict(int)

    for data in dataset:
        for i in components:
            # 如果集合是data的子集
            # 也就是data包含這個集合
            if i <= data:
                components_dict[i] += 1
rows = len(dataset)
frequent_components = []
supports = {}
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">for</span> k,v <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">in</span> components_dict.items():
    <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 支援度就是集合在數據集中的出現次數除以數據總數</span>
    support = v / rows
    <span class="hljs-comment" style="color: #998; font-style: italic; line-height: 26px;"># 保留滿足支援度要求的數據</span>
    <span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">if</span> support &gt;= min_support:
        frequent_components.append(k)
    supports[k] = support
<span class="hljs-keyword" style="color: #333; font-weight: bold; line-height: 26px;">return</span> frequent_components, supports