在美國有這樣一家奇怪的超市， 它將啤酒與尿布這樣兩個奇怪的東西放在一起進行銷售，并且最終讓啤酒與尿布這兩個看起來沒有關聯(lián)的東西的銷量雙雙增加 。這家超市的名字叫做沃爾瑪。

你會不會覺得有些不可思議？雖然事后證明這個案例確實有根據(jù)，美國的太太們常叮囑她們的丈夫下班后為小孩買尿布，而丈夫們在買尿布后又隨手帶回了他們喜歡的啤酒。但這畢竟是事后分析， 我們更應該關注的，是在這樣的場景下，如何找出物品之間的關聯(lián)規(guī)則 。接下來就來介紹下如何使用Apriori算法，來找到物品之間的關聯(lián)規(guī)則吧。

一. Apriori關聯(lián)分析概述

選擇物品間的關聯(lián)規(guī)則也就是要尋找物品之間的潛在關系。要尋找這種關系，有兩步，以超市為例

1. 找出頻繁一起出現(xiàn)的物品集的集合，我們稱之為 頻繁項集 。比如一個超市的頻繁項集可能有{{啤酒,尿布},{雞蛋,牛奶},{香蕉,蘋果}}
2. 在 頻繁項集 的基礎上，使用 關聯(lián)規(guī)則 算法找出其中物品的 關聯(lián)結果 。

簡單點說，就是先找頻繁項集，再根據(jù)關聯(lián)規(guī)則找關聯(lián)物品。

為什么要先找頻繁項集呢？還是以超市為例，你想想啊，我們找物品關聯(lián)規(guī)則的目的是什么，是為了提高物品的銷售額。如果一個物品本身購買的人就不多，那么你再怎么提升，它也不會高到哪去。所以從效率和價值的角度來說，肯定是優(yōu)先找出那些人們頻繁購買的物品的關聯(lián)物品。

既然要找出物品的關聯(lián)規(guī)則有兩步，那我們也一步一步來。我們會先介紹如何用Apriori找出物品的頻繁項集，然后下一篇會在Apriori處理后的頻繁項集的基礎上，進行物品的關聯(lián)分析。

二. Apriori算法基礎概念

在介紹Apriori算法之前，我們需要先了解幾個概念，別擔心，我們會結合下面的例子來進行說明的。

這些是一個超市里面的一部分購買商品記錄：

2.1 關聯(lián)分析的幾個概念

支持度（Support） ：支持度可以理解為物品當前流行程度。計算方式是：

支持度 = （包含物品A的記錄數(shù)量） / （總的記錄數(shù)量）

用上面的超市記錄舉例，一共有五個交易，牛奶出現(xiàn)在三個交易中，故而{牛奶}的支持度為3/5。{雞蛋}的支持度是4/5。牛奶和雞蛋同時出現(xiàn)的次數(shù)是2，故而{牛奶，雞蛋}的支持度為2/5。

置信度（Confidence） ：置信度是指如果購買物品A，有較大可能購買物品B。計算方式是這樣：

置信度( A -> B) = （包含物品A和B的記錄數(shù)量） / （包含 A 的記錄數(shù)量）

舉例：我們已經知道，(牛奶，雞蛋)一起購買的次數(shù)是兩次，雞蛋的購買次數(shù)是4次。那么Confidence(牛奶->雞蛋)的計算方式是Confidence(牛奶->雞蛋)=2 / 4。

提升度（Lift） ：提升度指當銷售一個物品時，另一個物品銷售率會增加多少。計算方式是：

提升度( A -> B) = 置信度( A -> B) / (支持度 A)

舉例：上面我們計算了牛奶和雞蛋的置信度Confidence(牛奶->雞蛋)=2 / 4。牛奶的支持度Support(牛奶)=3 / 5，那么我們就能計算牛奶和雞蛋的支持度Lift(牛奶->雞蛋)=0.83
當提升度(A->B)的值大于1的時候，說明物品A賣得越多，B也會賣得越多。而提升度等于1則意味著產品A和B之間沒有關聯(lián)。最后，提升度小于1那么意味著購買A反而會減少B的銷量。

其中 支持度 和Apriori相關，而置信度和提升度是下一篇尋找物品關聯(lián)規(guī)則的時候會用到。

2.2 Apriori算法介紹

Apriori的作用是根據(jù)物品間的支持度找出物品中的頻繁項集。通過上面我們知道，支持度越高，說明物品越受歡迎。那么支持度怎么決定呢？這個是我們主觀決定的，我們會給Apriori提供一個最小支持度參數(shù)，然后Apriori會返回比這個最小支持度高的那些頻繁項集。

說到這里，有人可能會發(fā)現(xiàn)，既然都知道了支持度的計算公式，那直接遍歷所有組合計算它們的支持度不就可以了嗎 ？

是的，沒錯。確實可以通過遍歷所有組合就能找出所有頻繁項集。但問題是遍歷所有組合花的時間太多，效率太低，假設有N個物品，那么一共需要計算2^N-1次。每增加一個物品，數(shù)量級是成指數(shù)增長。而Apriori就是一種找出頻繁項集的高效算法。它的核心就是下面這句話：

某個項集是頻繁的，那么它的所有子集也是頻繁的 。

這句話看起來是沒什么用，但是反過來就很有用了。

如果一個項集是 非頻繁項集，那么它的所有超集也是非頻繁項集 。

如圖所示，我們發(fā)現(xiàn){A,B}這個項集是非頻繁的，那么{A,B}這個項集的超集，{A,B,C},{A,B,D}等等也都是非頻繁的，這些就都可以忽略不去計算。

運用Apriori算法的思想，我們就能去掉很多非頻繁的項集，大大簡化計算量。

2.3 Apriori算法流程

要使用Apriori算法，我們需要提供兩個參數(shù)， 數(shù)據(jù)集和最小支持度 。我們從前面已經知道了Apriori會遍歷所有的物品組合，怎么遍歷呢？答案就是遞歸。先遍歷1個物品組合的情況，剔除掉支持度低于最小支持度的數(shù)據(jù)項，然后用剩下的物品進行組合。遍歷2個物品組合的情況，再剔除不滿足條件的組合。不斷遞歸下去，直到不再有物品可以組合。

下面我們來用Apriori算法實戰(zhàn)一下吧。

三. Apriori算法實戰(zhàn)

我們用一個簡單的例子來用一下Apriori吧，這里用到的庫是mlxtend。

在放代碼之前，先介紹下Apriori算法的參數(shù)吧。

          
            def apriori(df, min_support=0.5,  
            use_colnames=False, 
            max_len=None)
參數(shù)如下：
df：這個不用說，就是我們的數(shù)據(jù)集。
min_support：給定的最小支持度。
use_colnames：默認False，則返回的物品組合用編號顯示，為True的話直接顯示物品名稱。
max_len：最大物品組合數(shù)，默認是None，不做限制。如果只需要計算兩個物品組合的話，便將這個值設置為2。

          
        

OK，接下來就來用一個簡單的例子來看看怎么使用Apriori算法找到頻繁項集吧。

          
            import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori

#設置數(shù)據(jù)集
dataset = [['牛奶','洋蔥','肉豆蔻','蕓豆','雞蛋','酸奶'],
        ['蒔蘿','洋蔥','肉豆蔻','蕓豆','雞蛋','酸奶'],
        ['牛奶','蘋果','蕓豆','雞蛋'],
        ['牛奶','獨角獸','玉米','蕓豆','酸奶'],
        ['玉米','洋蔥','洋蔥','蕓豆','冰淇淋','雞蛋']]
        
te = TransactionEncoder()
#進行 one-hot 編碼
te_ary = te.fit(records).transform(records)
df = pd.DataFrame(te_ary, columns=te.columns_)
#利用 Apriori 找出頻繁項集
freq = apriori(df, min_support=0.05, use_colnames=True)

          
        

首先，需要先將商品進行one-hot編碼，編碼后用boolean值表示。所謂ont-hot編碼呢，直觀來說就是有多少個狀態(tài)就有多少比特，而且只有一個比特為1，其他全為0的一種碼制。比如冰淇淋只存在最后一共交易單中，其他交易中都沒出現(xiàn)。那冰淇淋就可以用[0,0,0,0,1]來表示

這里編碼后的數(shù)據(jù)如下：

          
                 冰淇淋     洋蔥     牛奶    獨角獸     玉米    肉豆蔻    蕓豆     蘋果     蒔蘿     酸奶     雞蛋
0  False        True   True       False      False    True     True    False    False   True     True
1  False        True  False       False      False    True     True    False     True   True     True
2  False       False   True       False      False   False     True     True    False  False     True
3  False       False   True        True       True   False     True    False    False   True    False
4   True        True  False       False       True   False     True    False    False  False     True
          
        

我們設定的最小支持度是0.6，那么只有支持度大于0.6的物品集合才是頻繁項集，最終結果如下：

          
                support      itemsets
0       0.6          (洋蔥)
1       0.6          (牛奶)
2       1.0          (蕓豆)
3       0.6          (酸奶)
4       0.8          (雞蛋)
5       0.6      (蕓豆, 洋蔥)
6       0.6      (洋蔥, 雞蛋)
7       0.6      (牛奶, 蕓豆)
8       0.6      (酸奶, 蕓豆)
9       0.8      (蕓豆, 雞蛋)
10      0.6  (蕓豆, 洋蔥, 雞蛋)
          
        

四. 小結

今天我們介紹了關聯(lián)分析中會用到的幾個概念，支持度，置信度，提升度。然后講述了Apriori算法的作用，以及Apriori算法如何高效得找出物品的頻繁項集。

最后使用Apriori算法找出例子中的頻繁項集。

以上~

---

推薦閱讀：
Scala 函數(shù)式編程指南（一） 函數(shù)式思想介紹
通俗地說決策樹算法（二）實例解析
大數(shù)據(jù)存儲的進化史 --從 RAID 到 Hadoop Hdfs
C，java，Python，這些名字背后的江湖！