[[182123]]

關聯算法是數據挖掘中的一類重要算法。1993年,R.Agrawal等人***提出了挖掘顧客交易數據中項目集間的關聯規則問題，其核心是基于兩階段頻繁集思想的遞推算法。該關聯規則在分類上屬于單維、單層及布爾關聯規則，典型的算法是Apriori算法。

Apriori算法將發現關聯規則的過程分為兩個步驟：***步通過迭代，檢索出事務數據庫1中的所有頻繁項集，即支持度不低于用戶設定的閾值的項集;第二步利用頻繁項集構造出滿足用戶最小信任度的規則。其中，挖掘或識別出所有頻繁項集是該算法的核心，占整個計算量的大部分。

Apriori算法是常用的用于挖掘出數據關聯規則的算法，它用來找出數據值中頻繁出現的數據集合，找出這些集合的模式有助于我們做一些決策。比如在常見的超市購物數據集，或者電商的網購數據集中，如果我們找到了頻繁出現的數據集，那么對于超市，我們可以優化產品的位置擺放，對于電商，我們可以優化商品所在的倉庫位置，達到節約成本，增加經濟效益的目的。下面我們就對Apriori算法做一個總結。

1. 頻繁項集的評估標準

什么樣的數據才是頻繁項集呢?也許你會說，這還不簡單，肉眼一掃，一起出現次數多的數據集就是頻繁項集嗎!的確，這也沒有說錯，但是有兩個問題，***是當數據量非常大的時候，我們沒法直接肉眼發現頻繁項集，這催生了關聯規則挖掘的算法，比如Apriori, PrefixSpan, CBA。第二是我們缺乏一個頻繁項集的標準。比如10條記錄，里面A和B同時出現了三次，那么我們能不能說A和B一起構成頻繁項集呢?因此我們需要一個評估頻繁項集的標準。

常用的頻繁項集的評估標準有支持度,置信度和提升度三個。

支持度就是幾個關聯的數據在數據集中出現的次數占總數據集的比重。或者說幾個數據關聯出現的概率。如果我們有兩個想分析關聯性的數據X和Y，則對應的支持度為

以此類推，如果我們有三個想分析關聯性的數據X，Y和Z，則對應的支持度為:

一般來說，支持度高的數據不一定構成頻繁項集，但是支持度太低的數據肯定不構成頻繁項集。

置信度體現了一個數據出現后，另一個數據出現的概率，或者說數據的條件概率。如果我們有兩個想分析關聯性的數據X和Y，X對Y的置信度為

也可以以此類推到多個數據的關聯置信度，比如對于三個數據X，Y，Z,則X對于Y和Z的置信度為：

舉個例子，在購物數據中，紙巾對應雞爪的置信度為40%，支持度為1%。則意味著在購物數據中，總共有1%的用戶既買雞爪又買紙巾;同時買雞爪的用戶中有40%的用戶購買紙巾。

提升度表示含有Y的條件下，同時含有X的概率，與X總體發生的概率之比，即:

提升度體先了X和Y之間的關聯關系, 關聯度高則提升度小，一個特殊的情況，如果X和Y獨立，則有

達到***，因為此時

一般來說，要選擇一個數據集合中的頻繁數據集，則需要自定義評估標準。最常用的評估標準是用自定義的支持度，或者是自定義支持度和置信度的一個組合。

2. Apriori算法思想

對于Apriori算法，我們使用支持度來作為我們判斷頻繁項集的標準。Apriori算法的目標是找到***的K項頻繁集。這里有兩層意思，首先，我們要找到符合支持度標準的頻繁集。但是這樣的頻繁集可能有很多。第二層意思就是我們要找到***個數的頻繁集。比如我們找到符合支持度的頻繁集AB和ABE，那么我們會拋棄AB，只保留ABE，因為AB是2項頻繁集，而ABE是3項頻繁集。那么具體的，Apriori算法是如何做到挖掘K項頻繁集的呢?

Apriori算法采用了迭代的方法，先搜索出候選1項集及對應的支持度，剪枝去掉低于支持度的1項集，得到頻繁1項集。然后對剩下的頻繁1項集進行連接，得到候選的頻繁2項集，篩選去掉低于支持度的候選頻繁2項集，得到真正的頻繁二項集，以此類推，迭代下去，直到無法找到頻繁k+1項集為止，對應的頻繁k項集的集合即為算法的輸出結果。

可見這個算法還是很簡潔的，第i次的迭代過程包括掃描計算候選頻繁i項集的支持度，剪枝得到真正頻繁i項集和連接生成候選頻繁i+1項集三步。

我們下面這個簡單的例子看看：

我們的數據集D有4條記錄，分別是134,235,1235和25。現在我們用Apriori算法來尋找頻繁k項集，最小支持度設置為50%。首先我們生成候選頻繁1項集，包括我們所有的5個數據并計算5個數據的支持度，計算完畢后我們進行剪枝，數據4由于支持度只有25%被剪掉。我們最終的頻繁1項集為1235，現在我們鏈接生成候選頻繁2項集，包括12,13,15,23,25,35共6組。此時我們的***輪迭代結束。

進入第二輪迭代，我們掃描數據集計算候選頻繁2項集的支持度，接著進行剪枝，由于12和15的支持度只有25%而被篩除，得到真正的頻繁2項集，包括13,23,25,35。現在我們鏈接生成候選頻繁3項集,123, 125，135和235共4組，這部分圖中沒有畫出。通過計算候選頻繁3項集的支持度，我們發現123,125和135的支持度均為25%，因此接著被剪枝，最終得到的真正頻繁3項集為235一組。由于此時我們無法再進行數據連接，進而得到候選頻繁4項集，最終的結果即為頻繁3三項集235。

3. Aprior算法流程

下面我們對Aprior算法流程做一個總結。

輸入：數據集合D，支持度閾值αα

輸出：***的頻繁k項集

1)掃描整個數據集，得到所有出現過的數據，作為候選頻繁1項集。k=1，頻繁0項集為空集。

2)挖掘頻繁k項集

a) 掃描數據計算候選頻繁k項集的支持度

b) 去除候選頻繁k項集中支持度低于閾值的數據集,得到頻繁k項集。如果得到的頻繁k項集為空，則直接返回頻繁k-1項集的集合作為算法結果，算法結束。如果得到的頻繁k項集只有一項，則直接返回頻繁k項集的集合作為算法結果，算法結束。

c) 基于頻繁k項集，連接生成候選頻繁k+1項集。

3) 令k=k+1，轉入步驟2。

從算法的步驟可以看出，Aprior算法每輪迭代都要掃描數據集，因此在數據集很大，數據種類很多的時候，算法效率很低。

4. Aprior算法總結

Aprior算法是一個非常經典的頻繁項集的挖掘算法，很多算法都是基于Aprior算法而產生的，包括FP-Tree,GSP, CBA等。這些算法利用了Aprior算法的思想，但是對算法做了改進，數據挖掘效率更好一些，因此現在一般很少直接用Aprior算法來挖掘數據了，但是理解Aprior算法是理解其它Aprior類算法的前提，同時算法本身也不復雜，因此值得好好研究一番。

不過scikit-learn中并沒有頻繁集挖掘相關的算法類庫，這不得不說是一個遺憾，不知道后面的版本會不會加上。

作者：劉建平Pinard(十年碼農，對數學統計學，數據挖掘，機器學習，大數據平臺，大數據平臺應用開發，大數據可視化感興趣。博客：劉建平Pinard)