Apriori算法詳解

Apriori算法簡介

Apriori算法是一種常用的用於挖掘出數據關聯規則（Association Rules）的算法，「apriori」在拉丁語中翻譯為「來自以前」，顧名思義，這個算法是使用先驗知識來預測數據的關聯規則。

說到關聯規則，我們不得不提到一個經典案例——啤酒與尿布。在這個案例中，沃爾瑪發現看似兩個無關的商品，它們卻經常被一起購買，這是為什麼呢？在美國有嬰兒的家庭中，一般是母親在家中照看嬰兒，年輕的父親前去超市購買尿布，父親在購買尿布的同時，往往會順便為自己購買啤酒，這樣就會出現啤酒與尿布這兩件看上去不相干的商品經常會出現在同一個購物籃的現象。這兩種看似不相干的商品之間顯現出強相關性，於是商家可以將啤酒貨架放在尿布貨架旁邊以增加收益。

這個案例中研究啤酒與尿布的關係的方法就叫做「購物籃分析」，本質上就是挖掘數據關聯規則，而Apriori算法就是最經典的關聯規則挖掘算法。

相關概念支持度（Support）

數據集中包含該項集的數據所佔數據集的比例，度量一個集合在原始數據中出現的頻率。關聯規則A->B的支持度support=P(AB)，指的是事件A和事件B同時發生的概率（相當於聯合概率）。

通常我們需要事先設置一個支持度的閾值來對項集進行篩選。

置信度（Confidence）

置信度 

頻繁k項集（Frequent k Itemset）

項集就是項的集合，比如牛奶和麵包組成一個集合{牛奶，麵包}，那麼牛奶和麵包就是項，而{牛奶，麵包}為一個二項集。頻繁項集表示的就是在數據集中頻繁出現的項集。如果事件A中包含k個元素，那麼稱這個事件A為k項集，並且事件A滿足最小支持度閾值的事件稱為頻繁k項集。

Apriori算法原理Apriori算法性質

如果某個項集是頻繁的，那麼它的所有子集也是頻繁的；

如果某個項集是非頻繁的，那麼它的所有超集也是非頻繁的；

如果頻繁k項集集合中包含單個項目i的個數小於k-1,則i不可能在頻繁k項集中；

基於此，Apriori算法從單元素項集開始，通過組合滿足最小支持度的項集來形成更大的集合。

其實Apriori算法就是通過排除法來選擇頻繁項集和關聯規則，算法的目標是找到最大的頻繁k項集。

Apriori算法過程

Apriori算法過程分為兩個步驟：

通過迭代，檢索出事務資料庫中的所有頻繁項集，即支持度不低於用戶設定的閾值的項集；

利用頻繁項集構造出滿足用戶最小置信度的關聯規則。

具體過程就是：

先搜索出候選1項集並計算對應的支持度，通過篩選去掉支持度低於閾值的候選1項集，得到頻繁1項集；

通過連接頻繁1項集得到候選2項集並計算對應的支持度，通過篩選去掉支持度低於閾值的候選2項集，得到頻繁2項集；

以此類推，不斷循環，直到無法發現頻繁k+1項集為止，此時的頻繁k項集便是算法的輸出結果。

Apriori算法步驟
由頻繁項集產生強關聯規則

在找到所有頻繁項集後，我們還需要根據頻繁項集生成關聯規則：

對於每個頻繁項集L，生成其所有的非空子集；

對與L的每個非空子集x，計算其置信度confidence(x)，若confidence(x)大於等於最小置信度，則強規則x->(L-x)成立。

簡單的例子R語言中實現Apriori算法

R語言中的Apriori算法實現包含在arules包中。

數據源

利用arules包中自帶的Groceries數據集，該數據集是來自一個現實世界中的超市經營一個月的購物數據，包含了9835次交易。

> library(arules)
> data(Groceries)
> Groceries
transactions in sparse format with
 9835 transactions (rows) and
 169 items (columns)

探索性數據分析

通過inspect()函數可以看到超市的交易記錄。

> inspect(Groceries[1:5])
    items                     
[1] {citrus fruit, semi-finished bread, margarine, ready soups}             
[2] {tropical fruit, yogurt,                  
     coffee}                  
[3] {whole milk}              
[4] {pip fruit, yogurt, cream cheese, meat spreads}            
[5] {other vegetables, whole milk, condensed milk, long life bakery product}

通過summary()函數可以查看該數據集的一些基本信息。

> summary(Groceries)
transactions as itemMatrix in sparse format with
 9835 rows (elements/itemsets/transactions) and
 169 columns (items) and a density of 0.02609146 

most frequent items:
      whole milk other vegetables       rolls/buns             soda 
            2513             1903             1809             1715 
          yogurt          (Other) 
            1372            34055 

element (itemset/transaction) length distribution:
sizes
   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16 
2159 1643 1299 1005  855  645  545  438  350  246  182  117   78   77   55   46 
  17   18   19   20   21   22   23   24   26   27   28   29   32 
  29   14   14    9   11    4    6    1    1    1    1    3    1 

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.000   2.000   3.000   4.409   6.000  32.000 

includes extended item information - examples:
       labels  level2           level1
1 frankfurter sausage meat and sausage
2     sausage sausage meat and sausage
3  liver loaf sausage meat and sausage

通過itemFrequency()函數可以查看商品的交易比例。

> itemFrequency(Groceries[,1:3])
frankfurter     sausage  liver loaf 
0.058973055 0.093950178 0.005083884 

通過以上數據我們可以得出以下結果：

該數據集一共有9835行（交易記錄），169列（所有交易的商品種類），因此矩陣中共有 

most frequent items：列出了事務型數據中最常購買的商品。whole milk在9835次交易中被購買了2513次，因此我們可以得出結論：whole milk有2513/9835=25.6%的概率出現在所有的交易中；

element (itemset/transaction) length distribution：呈現了一組關於交易規模的統計，總共有2159次交易中包含一件商品，有1次交易中包含了32件商品。我們可以看出，25%的交易中包含了兩件或者更少的商品，大約一半的交易中商品數量不超過3件。

為了直觀地呈現統計數據，可以使用itemFrequenctyPlot()函數生成一個用於描繪所包含的特定商品的交易比例的柱狀圖。因為包含很多種商品，不可能同時展現出來，因此可以通過support或者topN參數進行排除一部分商品進行展示。

> itemFrequencyPlot(Groceries,support = 0.1)  # support = 0.1 表示支持度至少為0.1

support = 0.1

> itemFrequencyPlot(Groceries,topN = 20)  # topN = 20 表示支持度排在前20的商品

topN = 20

通過使用image()函數可以可視化整個稀疏矩陣。

> image(Groceries[1:5]) # 生成一個5行169列的矩陣，矩陣中填充有黑色的單元表示在此次交易（行）中，該商品（列）被購買了

可視化稀疏矩陣

從上圖可以看出，第一行記錄（交易）包含了四種商品（黑色的方塊），這種可視化的圖是用於數據探索的一種很有用的工具。它可能有助於識別潛在的數據問題，比如：由於列表示的是商品名稱，如果列從上往下一直被填充表明這個商品在每一次交易中都被購買了；另一方面，圖中的模式可能有助於揭示交易或者商品的有趣部分，特別是當數據以有趣的方式排序後，比如，如果交易按照日期進行排序，那麼黑色方塊圖案可能會揭示人們購買商品的數量或者類型受季節性的影響。這種可視化對於超大型的交易數據集是沒有意義的，因為單元太小會很難發現有趣的模式。

訓練模型

> grocery_rules <- apriori(data=Groceries,parameter=list(support =,confidence =,minlen =))

運行apriori()函數很簡單，但是找到支持度和置信度參數來產生合理數量的關聯規則時，可能需要進行大量的試驗與誤差評估。

如果參數設置過高，那麼結果可能是沒有規則或者規則過於普通而不是非常有用的規則；如果閾值太低，可能會導致規則數量很多，甚至需要運行很長的時間或者在學習階段耗盡內存。

aprior()函數默認設置 

> apriori(Groceries)
set of 0 rules

因為 

解決支持度設定問題的一種方法是：考慮一個有趣的模式之前，事先想好需要的最小交易數量，例如：我們可以認為如果一種商品一天被購買了2次，一個月也就是60次交易記錄，這或許是我們所感興趣的，據此，可以計算所需要的支持度 

關於置信度：設置太低，可能會被大量不可靠的規則淹沒，設置過高，可能會出現很多顯而易見的規則致使我們不能發現有趣的模式；一個合適的置信度水平的選取，取決於我們的分析目標，我們可以嘗試以一個保守的值開始，如果發現沒有具有可行性的規則，可以降低置信度以拓寬規則的搜索範圍。

在此例中，我們將從置信度0.25開始，這意味著為了將規則包含在結果中，此時規則的正確率至少為25%，這將排除最不可靠的規則。

 

最終，根據上面的分析我們確定如下參數設置：

> grocery_rules <- apriori(data = Groceries,parameter = list(support = 0.006,confidence = 0.25,minlen = 2))
> grocery_rules
set of 463 rules

關聯規則可視化

使用arulesViz包可對關聯規則進行可視化。

> library(arulesViz)

通過plot()函數可以得到生成規則的散點圖以及散點矩陣

> plot(grocery_rules)

關聯規則散點圖

> plot(grocery_rules@quality)

關聯規則散點矩陣

> highLiftRules <- head(sort(grocery_rules, by = "lift"), 5)
> plot(highLiftRules, method = "graph", control = list(type = "items"))

lift值最高的5個關聯規則

圓圈的大小表示支持度的大小，不同的項目通過有向箭頭指向同一個支持度，表示相應項目組成的一個項集。

評估模型的性能

> summary(grocery_rules)
set of 463 rules

rule length distribution (lhs + rhs):sizes  # 前件+後件的規則長度分布
  2   3   4 
150 297  16  #有150個規則只包含2種商品，297個規則包含3種商品，16個規則包含4種商品

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  2.000   2.000   3.000   2.711   3.000   4.000 

summary of quality measures:
    support           confidence        coverage             lift       
 Min.   :0.006101   Min.   :0.2500   Min.   :0.009964   Min.   :0.9932  
 1st Qu.:0.007117   1st Qu.:0.2971   1st Qu.:0.018709   1st Qu.:1.6229  
 Median :0.008744   Median :0.3554   Median :0.024809   Median :1.9332  
 Mean   :0.011539   Mean   :0.3786   Mean   :0.032608   Mean   :2.0351  
 3rd Qu.:0.012303   3rd Qu.:0.4495   3rd Qu.:0.035892   3rd Qu.:2.3565  
 Max.   :0.074835   Max.   :0.6600   Max.   :0.255516   Max.   :3.9565  
     count      
 Min.   : 60.0  
 1st Qu.: 70.0  
 Median : 86.0  
 Mean   :113.5  
 3rd Qu.:121.0  
 Max.   :736.0  

mining info:
      data ntransactions support confidence
 Groceries          9835   0.006       0.25

> inspect(grocery_rules[1:5])
     lhs             rhs                support     confidence coverage   lift    
[1] {pot plants} => {whole milk}       0.006914082 0.4000000  0.01728521 1.565460
[2] {pasta}      => {whole milk}       0.006100661 0.4054054  0.01504830 1.586614
[3] {herbs}      => {root vegetables}  0.007015760 0.4312500  0.01626843 3.956477
[4] {herbs}      => {other vegetables} 0.007727504 0.4750000  0.01626843 2.454874
[5] {herbs}      => {whole milk}       0.007727504 0.4750000  0.01626843 1.858983
    count
[1] 68   
[2] 60   
[3] 69   
[4] 76   
[5] 76   

這裡需要解釋一下lift（提升度），表示用來度量一類商品相對於它的一般購買率，此時被購買的可能性有多大。通俗的講就是：比如第一條規則 

第一條規則解讀：如果一個顧客購買了pot plants，那麼他還會購買whole milk，支持度support為0.0070，置信度confidence為0.4000，我們可以確定該規則涵蓋了大約0.7%的交易，而且在購買了pot plants後，他購買whole milk的概率為40%，提升度lift值為1.565，表明他相對於一般沒有購買pot plant商品的顧客購買whole milk商品的概率提升了1.565倍，我們在上面的分析中知道，有25.6%的顧客購買了whole milk，因此計算提升度為 

提升度 

如果 

提高模型的性能

對關聯規則集合排序：根據購物籃分析的目標，最有用的規則或許是那些具有高支持度、信度和提升度的規則。arules包中包含一個sort()函數，通過指定參數by為"support","confidence"或者"lift"對規則列表進行重新排序。在默認的情況下，排序是降序排列，可以指定參數decreasing=FALSE反轉排序方式。

> inspect(sort(grocery_rules,by="lift")[1:10])
    lhs                                             rhs                  support     confidence lift   
3   {herbs}                                      => {root vegetables}    0.007015760 0.4312500  3.956477
57  {berries}                                    => {whipped/sour cream} 0.009049314 0.2721713  3.796886
450 {tropical fruit,other vegetables,whole milk} => {root vegetables}    0.007015760 0.4107143  3.768074
174 {beef,other vegetables}                      => {root vegetables}    0.007930859 0.4020619  3.688692
285 {tropical fruit,other vegetables}            => {pip fruit}          0.009456024 0.2634561  3.482649
176 {beef,whole milk}                            => {root vegetables}    0.008032537 0.3779904  3.467851
284 {pip fruit,other vegetables}                 => {tropical fruit}     0.009456024 0.3618677  3.448613
282 {pip fruit,yogurt}                           => {tropical fruit}     0.006405694 0.3559322  3.392048
319 {citrus fruit,other vegetables}              => {root vegetables}    0.010371124 0.3591549  3.295045
455 {other vegetables,whole milk,yogurt}         => {tropical fruit}     0.007625826 0.3424658  3.263712

提取關聯規則的子集：可以通過subset()函數提取我們感興趣的規則。

> fruit_rules <- subset(grocery_rules,items %in% "pip fruit")  # items 表明與出現在規則的任何位置的項進行匹配，為了將子集限制到匹配只發生在左側或者右側位置上，可以使用lhs或者rhs代替
> fruit_rules
set of 21 rules
> inspect(fruit_rules[1:5])
    lhs                           rhs                support     confidence lift   
127 {pip fruit}                => {tropical fruit}   0.020437214 0.2701613  2.574648
128 {pip fruit}                => {other vegetables} 0.026131164 0.3454301  1.785237
129 {pip fruit}                => {whole milk}       0.030096594 0.3978495  1.557043
281 {tropical fruit,pip fruit} => {yogurt}           0.006405694 0.3134328  2.246802
282 {pip fruit,yogurt}         => {tropical fruit}   0.006405694 0.3559322  3.392048