引子：啤酒與尿布
據(jù)說這是一個真實的案例：沃爾瑪在分析銷售記錄時哗咆，發(fā)現(xiàn)啤酒和尿布經(jīng)常一起被購買，于是他們調(diào)整了貨架益眉，把兩者放在一起晌柬，結(jié)果真的提升了啤酒的銷量。后來還分析背后的原因呜叫，說是因為爸爸在給寶寶買尿布的時候空繁，會順便給自己買點啤酒……這已經(jīng)成為了數(shù)據(jù)挖掘領(lǐng)域的一個經(jīng)典橋段殿衰，甚至被維克托?邁爾?舍恩伯格在2012年最火爆的《大數(shù)據(jù)時代》中大書特書……這個故事我們權(quán)當是真的朱庆，不過今天是要看看它背后的細節(jié)，也就是關(guān)聯(lián)分析（或者直接成為購物籃分析）
一闷祥、關(guān)聯(lián)分析中的若干概念
關(guān)聯(lián)規(guī)則就是說娱颊，如果顧客買了啤酒，那么很可能他也會買尿布凯砍，我們在這表示為【啤酒-->尿布】箱硕。
關(guān)聯(lián)規(guī)則背后的數(shù)學(xué)原理是很簡單的，就是古典概率悟衩，大家都能夠理解剧罩。比如，如果我們想看看【啤酒-->尿布】這個規(guī)則是不是存在座泳，那么首先就要看看惠昔，有多大的概率幕与，人們既買了啤酒，也買了尿布镇防。為了更好的說明問題啦鸣，我們偽造一個例子：
借用當下比較火的一個電影中的人物，在一個小賣部中有4種商品来氧，這幾位分別買了不同的東西诫给，1表示買，0表示沒有買啦扬。
我們的例子中中狂，六爺、悶三兒扑毡、洋火兒這老哥兒仨是一起買了啤酒和尿布吃型，我們一共假定了八位人物，因此僚楞，同時購買啤酒和尿布的概率就是3/8勤晚，這就是古典概率中計算概率的方法，在關(guān)聯(lián)規(guī)則中泉褐，這個概率叫做這條規(guī)則的“支持度（Support）”赐写，表示同時購買啤酒和尿布的顧客在所有顧客當中的覆蓋范圍。
雖然我們現(xiàn)在知道膜赃，啤酒和尿布挺邀，經(jīng)常一起出現(xiàn)，但是是不是買了啤酒的就一定買尿布呢跳座？這里又要從另外一個角度來看端铛，那就是，對于所有買了啤酒的人疲眷，有多大的可能性買尿布禾蚕。買啤酒的人包括六爺、悶三兒狂丝、燈罩兒换淆、洋火兒、小飛几颜，一共五位倍试。這五位中，六爺蛋哭、悶三兒县习、洋火兒買了尿布，所以，在購買了啤酒的前提下躁愿，買尿布的概率是3/5哈蝇。這個概率其實是古典概率中的條件概率，在關(guān)聯(lián)分析中叫做關(guān)聯(lián)規(guī)則【啤酒-->尿布】的“置信度（Confidence）”攘已，表示可預(yù)測的程度炮赦，即顧客購買啤酒的話有多大可能性買尿布。
現(xiàn)在样勃，看來【啤酒-->尿布】這條規(guī)則應(yīng)該可以促進尿布銷售啊吠勘，應(yīng)該在結(jié)賬的時候，讓收銀員對買了啤酒的人都問：“這位爺峡眶，您要來包兒日本原裝進口花王紙尿褲嗎剧防？”。這時候問題來了：我利用這條規(guī)則辫樱，是想促進尿布的銷售峭拘，但是只對買啤酒的人促銷是不是合理呢？
回到我們的表格從整體來看狮暑，購買尿布的一共有四位鸡挠，也就是說，人們逛這個小賣部有4/8的幾率會購買尿布搬男，是在純天然條件下拣展，尿布銷售的概率。當利用了關(guān)聯(lián)規(guī)則【啤酒-->尿布】缔逛，理論上尿布銷售的概率為3/5备埃，大于4/8，所以我們認為這條規(guī)則是有效的褐奴，有一個評價指標叫“提升度（Lift）”按脚，就是用3/5除以4/8，為6/5敦冬，通俗解釋就是利用關(guān)聯(lián)規(guī)則后一種東西的賣出概率除以純天然環(huán)境下賣這樣?xùn)|西的概率辅搬。
如果Lift>1，證明這個規(guī)則是有確實提升作用的匪补，是有效的伞辛；
如果<1烂翰，說明不用這個規(guī)則夯缺，賣東西的概率更高，規(guī)則還不如不用甘耿；
如果=1踊兜，說明有沒有規(guī)則，對賣東西的概率沒影響佳恬。
其實就關(guān)聯(lián)規(guī)則的日常應(yīng)用來說捏境，即使不知道算法細節(jié)于游，了解了Support、Confidence和Lift就可以利用分析工具開展分析工作了垫言，在分析中需要手工定義最小支持度和最小置信度（當然一般工具中也都有默認值）贰剥，滿足最小支持度和最小置信度的規(guī)則，叫做“強關(guān)聯(lián)規(guī)則”筷频，然后蚌成，“強關(guān)聯(lián)規(guī)則”中也分有效和無效，如果Lift（X-->Y）>1凛捏，則規(guī)則“X-->Y”是有效強關(guān)聯(lián)規(guī)則担忧，如果Lift（X--Y)<=1，則規(guī)則“X-->Y”是無效強關(guān)聯(lián)規(guī)則坯癣。
關(guān)聯(lián)分析瓶盛，就是從大量的銷售記錄中，通過算法示罗，找出所有的有效強關(guān)聯(lián)規(guī)則的過程
Support是第一個門檻惩猫，考察關(guān)聯(lián)規(guī)則在“量”上的多少，剔除出鏡率較低的購買組合
Confidence是第二個門檻蚜点，考察關(guān)聯(lián)規(guī)則在“質(zhì)”上的可靠性
Lift是第三個門檻帆锋，是基于Confidence的指標，考察關(guān)聯(lián)規(guī)則的有效性
支持度和置信度這兩個指標的設(shè)置是很見功夫的禽额。支持度很低锯厢，說明在整個的購買行為中覆蓋范圍很小，即使置信度很高脯倒，也可能是一種偶然的行為实辑。支持度設(shè)置的很高，說明覆蓋范圍很大藻丢，但有可能會發(fā)現(xiàn)一些常識性的結(jié)論剪撬，比如買手機的用戶很有可能買手機殼，這種規(guī)則就不要費力氣挖掘了……直接憑常識都知道悠反。所以關(guān)聯(lián)規(guī)則的使用和其他的數(shù)據(jù)挖掘方法一樣残黑，一定要結(jié)合業(yè)務(wù)知識，一定要有業(yè)務(wù)專家的支持斋否。
補充一點是梨水，一些微軟開發(fā)的數(shù)據(jù)挖掘工具中，Confidence稱為Probobility茵臭，同時還引入一個類似于Lift的概念叫做Importance在跳，但是不知道具體的計算方法煮岁。
二孕讳、關(guān)聯(lián)分析的過程和Apriori算法
根據(jù)上面的分析，關(guān)聯(lián)分析的過程為：
1. 設(shè)定最小支持度和置信度
2. 找出滿足最小支持度的購買組合（術(shù)語叫頻繁項集）
3. 對于第二步中的每一個購買組合雏亚，找到滿足最小置信度的關(guān)聯(lián)規(guī)則
4. 驗證關(guān)聯(lián)規(guī)則的有效性
最基本最著名的關(guān)聯(lián)規(guī)則算法是Apriori算法，這個算法用來找到所有頻繁項集摩钙。這個算法背后的思想是集合論罢低，證明雖然不長，但是牽扯到太多的數(shù)學(xué)了胖笛，不講了奕短。下面只手工執(zhí)行以下這個算法，把我們例子做一下匀钧，領(lǐng)略一下Apriori算法的執(zhí)行過程：
步驟1：設(shè)定Support和Confidence
我們設(shè)定支持度30%翎碑，置信度70%。（人為設(shè)定）
步驟2：計算滿足支持度的購買組合（及計算頻繁項集）
首先計算只有一個商品的購買組合：【啤酒】【尿布】【PM2.5口罩】【iPhone 6S】之斯，這幾個分別出現(xiàn)了5日杈，4，5佑刷，2次莉擒，因此【iPhone 6S】的支持度為2/8，被剔除瘫絮，剩下的為【啤酒】【尿布】【PM2.5口罩】
然后計算兩個商品的購買組合：要基于上一步的結(jié)果涨冀，把剩下的三樣兩兩組合【啤酒、尿布】【啤酒麦萤、PM2.5口罩】【尿布鹿鳖、PM2.5口罩】，這三個組合分別出現(xiàn)了3壮莹、3翅帜、2次，淘汰最后一個命满，剩下【啤酒涝滴、尿布】【啤酒、PM2.5口罩】
然后計算三個商品的購買組合：基于上一步結(jié)果胶台，三樣商品只能有一個組合【啤酒歼疮、尿布、PM2.5口罩】诈唬，在表格中出現(xiàn)了2次韩脏，淘汰
最終得到的滿足最小支持度的購買組合為【啤酒】【尿布】【PM2.5口罩】【啤酒、尿布】【啤酒讯榕、PM2.5口罩】
注：由于我懶得寫太多骤素，所以故意把例子搞得很簡單匙睹，感覺像把所有可能情況全部列出來愚屁，再用支持度篩選……但其實Apriori算法在每一步組合時候济竹，先對上一步的每個組合排序，然后只合并除了最后一個元素不同霎槐，其他元素相同的組合
假如計算出包含三個商品的購買組合為{1送浊，2，3}丘跌，{1袭景，3，4}闭树，{1耸棒，2，6}报辱，那么{1与殃，2，3}和{1碍现，2幅疼，6}只有最后一個元素不同，可以兩兩組合成四個元素的購買組合{1昼接，2爽篷，3，6}慢睡，然后進行支持度判斷逐工；{1，3漂辐，4}可以不用管钻弄，因為它最后一個和倒數(shù)第二個元素和其他兩個都不一樣。為啥能這么搞呢者吁？背后都是有強大的數(shù)學(xué)證明的窘俺，Apriori也是這么實現(xiàn)的。
步驟3：生成關(guān)聯(lián)規(guī)則复凳，判斷置信度
下一個步驟瘤泪，就是利用找到的購買組合，生成規(guī)則育八。只有一個商品的很明顯不可能有任何規(guī)則对途，所以只需要考慮【啤酒、尿布】【啤酒髓棋、PM2.5口罩】实檀。
生成規(guī)則最一般的方法就是窮舉法（也有一些優(yōu)化過的方法惶洲，不過程Sir沒有研究），一共有【啤酒-->尿布】【尿布-->啤酒】【啤酒-->PM2.5口罩】【PM2.5口罩-->啤酒】四個規(guī)則需要用置信度判斷膳犹。（如果是三個商品的恬吕，比如【1，2须床，3】铐料，那就是【1，2-->3】【1豺旬，3-->2】【2钠惩，3-->1】【3-->1，2】【2-->1族阅，3】【1-->2篓跛，3】）
【啤酒-->尿布】，置信度3/5坦刀，小于70%愧沟，淘汰
【尿布-->啤酒】，置信度3/4求泰，大于70%央渣，保留
【啤酒-->PM2.5口罩】，置信度3/5渴频，小于70%芽丹，淘汰
【PM2.5口罩-->啤酒】，置信度3/5卜朗，小于70%拔第，淘汰
步驟4：計算Lift，驗證有效性
最后驗證有效性场钉，自然條件下蚊俺，買啤酒的概率為5/8，小于【尿布-->啤酒】的置信度3/4逛万，可以算出Lift為6/5=1.2泳猬，是一條“有效的強關(guān)聯(lián)規(guī)則”。
因此宇植，對于這個例子來說得封，在設(shè)定的30%支持度和70%置信度的水平下，我們挖掘出了一條規(guī)則：【尿布-->啤酒】
三指郁、其他關(guān)聯(lián)分析的算法
各種關(guān)聯(lián)分析算法的核心都是快速的找出所有的頻繁項集忙上，Apriori算法需要對數(shù)據(jù)庫進行多次掃描，同時產(chǎn)生大量的候選頻繁集闲坎，這就使Apriori算法時間和空間復(fù)雜度較大疫粥。后來茬斧，伊利諾伊大學(xué)的華裔數(shù)據(jù)科學(xué)家Jiawei Han（韓家煒）老爺爺在2000年提出了FP-growth算法，利用一個叫做頻繁模式樹（FP-tree）的數(shù)據(jù)結(jié)構(gòu)梗逮，加快了數(shù)據(jù)挖掘的速度项秉。這里提一句，Jiawei Han老爺爺寫了一本大部頭重量級著作库糠，號稱是數(shù)據(jù)挖掘領(lǐng)域里程碑意義的經(jīng)典著作伙狐。
FP-growth算法比Apriori算法快一個數(shù)量級涮毫，在空間復(fù)雜度方面也比Apriori也有數(shù)量級級別的優(yōu)化瞬欧。但是對于海量數(shù)據(jù)，F(xiàn)P-growth的時空復(fù)雜度仍然很高罢防，可以采用的改進方法包括數(shù)據(jù)庫劃分艘虎，數(shù)據(jù)采樣等等。
四咒吐、關(guān)聯(lián)分析的應(yīng)用領(lǐng)域
很多很多領(lǐng)域都可以應(yīng)用野建，電商推薦系統(tǒng)、交叉銷售恬叹、商品目錄的設(shè)計候生、商品貨架擺放等，就我本身所從事的電信行業(yè)來說绽昼，運營商可根據(jù)用戶的APP安裝和使用情況唯鸭，挖掘關(guān)聯(lián)規(guī)則，提升自有互聯(lián)網(wǎng)業(yè)務(wù)和流量包業(yè)務(wù)的訂購量
五硅确、啤酒與尿布其實只是一個傳說
看起來最靠譜的“啤酒與尿布”的起源目溉，來自 KDnuggets News 00:13, item 23, Publications：
The "diapers and beer" example was created by Tom Blishok who ran a retail consulting group for NCR. ?They first did market basket forOsco Drugs in Chicago. ?This pre-dated commercial availability of associations algorithms (1992?). ?Tom had a team of a half dozen or so SQL hackers (I know a couple of them) creating queries that defined affinities that theythought might be in the data. ?They found "cosmetics and greeting cards" and a few others.
In the process of Tom creating materials for NCR to make the argument for why you want to house transaction data he needed a snappy example, sohe dreamed up the "diapers and beer" example. ?To the best of my knowledge it was never supported in any data that they analyzed. ?Tom's original example had "diapers and beer" appearing in C-Store data which,to the best of my knowledge, they never analyzed at the transaction level.
It's still a nice example, of course. ?As they say, never let truth get in the way of a good story.
雖然“啤酒與尿布”的故事是假的，但并不是說關(guān)聯(lián)分析本身是毫無價值的菱农。這個故事成為了傳播數(shù)據(jù)挖掘理念的重要的案例缭付，同時，上文中提到的NCR后來分離出了大名鼎鼎的Teradata循未，直到今天也是數(shù)據(jù)挖掘領(lǐng)域的主要玩家之一陷猫，尤其在電信領(lǐng)域。
尾聲：
其實我很喜歡最后這句話的妖，never let truth get in the way of a good story.?就如同《老炮兒》绣檬，雖說有很多人指出真正的老炮兒并不是電影中表現(xiàn)的樣子，但是誰也無法阻止一路飆升的票房羔味，畢竟河咽，這還算是一個不錯的故事。
