1990年代，知名的Walmart有這麼一則故事，銷售經理研究了消費者的消費紀錄之後發現，啤酒與尿布的相關性很高，也就是常常出現在同一筆消費紀錄中。
所以後來就有多間Walmart會將啤酒跟尿布放在同一個區域，以鼓勵民眾一起消費、提高客單價。先不論這個故事是否是真實發生的，都不失為一個引人入勝的好案例。
所以許多這類的『關聯分析』、也被常稱為『購物籃分析』（Market Basket Analysis），是研究消費者行為的重要一環。這次要介紹的是關聯分析必須認識的Apriori。
相關的程式碼、原理及演算法說明，網路上已經有相當完整的資源，我會用我自己比較容易理解的方法來重新整理過一次。我所截取的一些文字或圖片都會放在最下面的reference，若有問題可以寄信到weilihmen@gmail.com。
我們就直接以啤酒尿布的案例來思考，今天你在一間大型大賣場擔任一位數據分析組組長，你的老闆跟你說，每個季要做一份研究，來改善什麼商品應該同時被放在焦點區域，以及來客經過的前後順序，好讓消費者會順手買，提高客單價。
這時候，你已經聽過啤酒跟尿布的故事，你也想從這個方向開始做，只是還有幾個問題在你的腦袋中打轉
- 啤酒跟尿布同時出現的機率有多高，試想：如果這個組合發生的機率只有千分之一，這樣花費成本來promo似乎不划算
- 到底是買啤酒順便買尿布、還是買尿布順便買啤酒？會影響到到底是在哪個主購區域來添加這個副購推薦
- 除了啤酒跟尿布，會不會第三項可以加入這個組合，譬如啤酒＋尿布＋衛生紙？甚至是第四種？
關聯式規則(Association Rules, AR)，又稱關聯規則，是資料探勘領域中相當重要的研究課題，從數據中探勘出有價值的資料項目之間相關性。
關聯規則最早由 Agrawal et al. (1993) 所 提出，並隨後於 1994 年提出 Apriori 演算法運用在關聯規則的推導。後續許 關聯規則相關的研究亦基於此演算法，如 F-P 演算法、以布林運算為基礎的演算法、 Pincer-Search 演算法等等，皆是著名的關聯規則探勘的演算法。
關聯式演算法中最常使用的兩個衡量指標，包含了 Support & Confidence
Support 常被翻譯為支持度，也就是在所有的資料裡面，Ａ出現過的次數。也可以解讀為發生的機率，譬如說一千次交易紀錄中，單獨買尿布的為100次、同時買尿布跟啤酒的為50次，我們可以用以下的方式來表示
Support (尿布) = 100/1000
Support ({尿布, 啤酒}) = 50/1000
所以我們要先回答第一個問題，我們在評估一個商品組合是否應該合併促銷，我們首要考慮的是『實用性』
什麼叫實用性？假設這個促銷組合會發生，就代表原本只有買A商品、跟原本只有買B商品的，兩種類型的消費者會變成買A+B的組合。
但是如果A跟B本身所發生的次數很少，佔你的營業額很低，我們就會說這個促銷組合的『實用性』很差。
所以實用性高的：代表發生機率高、或是(發生機率*消費金額)高，有足夠影響到實際業績，才有納入考慮的必要性。(當然，門市促銷組合的背後，會評估產品品牌與零售企業的合作關係，例如合約毛利、贊助費用、形象綜效、當前市場趨勢等，實際考量的內容複雜很多）
而支持度(Support)可以提供給我們該產品組合發生機率的基礎，通常的做法會設定一個門檻，這個門檻也依照行業屬性不同可以變化，譬如說大賣場，動輒數千件的商品，高門檻會相對較低(可能為10%、5%甚至更低)。
而品牌專賣店，其商品可能僅有數十件，此時門檻應該就要拉高。此時考慮的的是商品頻率，譬如每賣出十個商品，就有一個商品是A。
除了看行業屬性之外，也可以考慮時間週期來評估門檻，譬如我們現在想先試跑一個月的資料，一共有五百筆，我希望這個組合平均每天發生至少一次，意思五百筆消費紀錄至少有要三十筆以上包含該商品，門檻值即為30/500。
我們在上一段探討『實用性』的時候，寫了一個假設：假設這個商品組合會發生，那實際上會發生的機率，就開始進入關聯性分析的重點，採用的指標為Confidence，可以稱為信賴度。
信賴度的概念取自於條件機率，指如果購買物品A，有較大可能購買物品B。也就是 A 出現的條件下，B 也會跟著出現的條件機率。
信賴度( A -> B)：（同時包含A和B的消費記錄數） / （所有包含A 記錄數）
譬如50次有購買蘋果的紀錄中，有10人又同時買了奇異果，我們就可以寫Confidence (蘋果->奇異果) = 10/50
信賴度本身的觀念不難理解，要進階探討的是實務上怎麼解讀。我們前一段探討實用性會影響業績發生的量體，除了量體大小還不夠，我們還要考慮發生機率。因為量體*發生機率才是真實的營收，所以就算量體大，這個『假設』沒有發生還是一樣什麼都沒有。
最後一個指標我們來談『提升度』(Lift)，這個其實只是前兩個指標(支持度與信賴度)結合起來的，不過也可以讓我們再練習過一次指標的含義，多學幾個指標的變形，在實際上戰場時會多一些感覺。
Lift(X→Y) = Confidence(X→Y) / P(Y) = P(Y|X) / P(Y)
從理論的角度來看，提升度反應了X與Y的關聯性，此公式表示當事情X發生的情況下，同時發生Y的可能性，且只看Y發生的機率。提升度>1代表正相關，提升度=1表示為互相獨立，提升度<1代表負相關性。
從公式拆開來解讀，其實只是在比較兩種機率的大小，如果 P(Y|X) 大於 P(Y)，則符合此指標的正相關定義。而P(Y|X)的意思是，在發生X的事件中，也有發生Y的機率，而P(Y)則是不限制任何條件，以所有母體來計算Y的發生機率。
所以如果在X的條件限制下，Y的機率發生，比他原本的機率還高，這樣代表X的條件對於Y的發生機率有幫助，所以稱為Lift。
舉個例子，買牛奶+麵包的消費紀錄為50次，而總共有200次買牛奶的機率，所以信賴度(牛奶->麵包)為50/200=25%，看起來還不錯。
但這卻是一間麵包店！所以有八成的人走進去都會買麵包！在這個極端的範例中，我們可以看到其實牛奶對麵包的銷售沒有幫助，從最一開始來看25%的信賴度似乎不錯，每四個人買牛奶就會有一個人買麵包，但是在考慮麵包本身銷售發生的機率之後，我們會發現，這是想法一個錯誤的出發點，因為提昇度為25%/80% < 1 。
雖然Lift根本來說只是兩個機率做比較，拿結果來看哪個機率比較大，但是如上述的例子，有可能會讓你發現一些數據上的盲點。
到這邊喘口氣，上面是在談關聯分析，而Apriori則是可以計算此關聯指標的演算法。A priori在拉丁語中指「來自以前」，當定義問題時，通常會使用先驗知識或者假設，這被稱作「一個先驗」(a priori)
那要先驗什麼？
Apriori演算法的重要原理是：假設集合{A}出現次數小於最小支持度(Min_Support)，則他的任何超集合如{A,B}出現的次數必定小於或等於最小支持度
白話來說，如果蘋果出現在消費紀錄的次數是50次，這樣蘋果+香蕉一起出現的次數一定會小於或等於50次。所以，如果我們要求的支持度比較嚴格，蘋果的50次紀錄換算機率之後沒有達到支持度，這樣子蘋果+香蕉也不可能達成支持度。
這就是Apriori的『剪枝』功能，第一次會將所有品項掃一次，把沒有達成的剪掉，再進入下一輪的剪枝。下圖中，紫色的項目就是被剪枝剪掉的，可以看到第一次剪枝之後，就再也沒有出現D的子項。
這邊就接著講第二個原理，也是第一個原理的反向推導。假設集合{A,B,C}出現次數大於最小支持度(Min_Support)，則他的任何子集合如{A,B} or {A,C} or {B,C}出現的次數必定大於或等於最小支持度。
所以上圖來看，在C3->L3的scan過程中，把ABC砍掉的原因就在於，前一次輪剪枝之後，雖然AB,BC有滿足最小支持度2，但AC沒有，所以ABC也不可能滿足最小支持度。
Apriori仰賴這兩個原理，使得在處理這種需要大量遍歷的演算過程中，用許多”項目是否存在於集合中”的判斷，來取代需要一一計數的處理，例如剛剛提到的，我們判斷了ABC的這個組合不可能滿足最小支持度，所以就被剪掉了，此項就可以省略不計算count。
不過，從算法的步驟可以看出，Aprior算法每輪迭代都要遍歷數據集，因此在數據集很大，數據種類很多的時候，算法效率很低。其他算法如下圖
其中Apriori算是較有代表性，因為原理與步驟容易理解，在處理不大的數據量時算是很方便上手。再來就屬於FP-Growth，是Apriori的進化版，透過建立頻繁模式樹(Frequent Pattern Tree)，有點像是從無到有建立一張地圖，每個點根據他的項目集合跟頻繁，來決定是否能繼續往下走。
簡單小結，我們常聽到啤酒尿布、也可能聽過Apriori，這些都屬於關聯分析的範疇，其中關聯分析最重要的三個指標為支持度(Support)、信賴度(Confidence)於提升度(Lift)，Apriori是關聯分析的其中一個演算法，他透過兩個原理來減少計算量，雖然不是最好效率但容易理解。
OK，那這篇就先到這裡，謝謝你的閱讀，ㄅㄅ
