手把手教你挖掘資料：怎樣創造一個“尿布與啤酒”的都市傳奇？

作者：梅甘·斯誇爾

如需轉載請聯絡大資料（ID：hzdashuju）

在資料挖掘工具箱中，計量某個樣式的頻率是一項關鍵任務。在某些情況下，較頻繁出現的樣式可能最終成為更加重要的樣式。如果我們可以發現經常同時出現的兩個或者三個專案，就更為有趣了。

在本文中，我們開始研究頻繁項集，然後將其擴充套件為稱作關聯規則的一類樣式。我們將介紹如下主題：

• 什麼是頻繁項集？使用哪些技術找出頻繁項集？瓶頸在哪裡？如何加速這一過程？

• 如何將頻繁項集擴充套件為關聯規則？

• 什麼是好的關聯規則？我們將根據資料庫中的支援程度、對規則本身的置信度以及我們找出的規則所增加的價值，學習描述特定關聯規則的價值。

01 什麼是頻繁項集

尋找頻繁項集是一種計數活動。但是和從生成資料集中觀測到的專案的簡單計數（今天我們賣出了80個胡蘿蔔和100個馬鈴薯）相比，尋找頻繁項集稍有不同。確切地說，為了找出頻繁項集，我們要搜尋較大的組中共同出現的項集。

有時候可以把這些較大的組視為超市交易或者購物籃，整個活動有時候稱為市場籃子分析。我們仍然採用超市的類比，在這些籃子中同時出現的物品有時候被視為在超市中購買的產品組合。

例如，已知一組超市交易或者籃子，我們可能對籃子中{胡蘿蔔，馬鈴薯}的組合是否比{黃瓜、檸檬}的組合更頻繁出現感興趣。

頻繁項集挖掘的目的是發現一組交易中共同出現的有趣專案組合。換言之，如果我們發現某些組合在多個籃子中頻繁出現，則這種挖掘可能很有實用價值。如果我們發現的頻繁項集有些不同尋常或者有些意外，那就更加有趣了。

在頻繁項集挖掘中令人滿意的有趣規則的典範是一再被傳頌的都市傳奇——“尿布與啤酒”。

1. 都市傳奇“尿布與啤酒”

我記得第一次聽到這個故事是在1998年的一個資料挖掘研究生課程上。我的教授試圖解釋頻繁項集和關聯規則的實用性，他給我們班上的學生講瞭如下故事：

中西部的一家連鎖超市欲挖掘頻繁項集，以便發現一同購買的有趣商品組合。他們的計劃是透過在商店中將這些產品放在一起，最佳化銷售業績。令他們高興的是，商店的資料挖掘團隊發現，週四下午5點～7點，男人們頻繁地購買尿布和啤酒。該商店將一個小的尿布陳列櫃移到啤酒通道中，結果兩種產品的銷售量同時飆升。

我對這個故事表示懷疑，立刻提出了許多問題。

這家商店是如何知道男人購買了這些東西？畢竟，這個故事發生的時候，商店的電子優惠卡或者獎勵卡尚未出現。

這家商店怎麼可能選擇合適的尿布放入啤酒通道中間的小展示櫃？畢竟，尿布有5種不同的尺寸，至少有3種品牌，而且（我像一位初為人父的男人一樣快速學習）——一時興起地更換某種尺寸或者品牌不是好主意，那可能會帶來災難性的後果。

其他許多人也表示懷疑，有些人甚至試圖追尋這一都市傳奇的歷史。最好的研究範例包括Dan Powers的新聞稿《DSS Resources》，2001年11月10日的那一期（第3捲第23號）專門描寫了尋找這個故事真正來源的經過。

這篇引人入勝的文章的連結：

http://www.dssresources.com/newsletters/66.php

此後，英國的《The Register》於2006年也講述了一個關於這個都市傳奇的故事。

連結：

http://www.theregister.co.uk/ 2006/08/15/beer_diapers

如果你相信這兩篇文章講述的細節，尿布與啤酒的故事則是說明早期資料挖掘可能性的一個示例：使用我們的資料庫產品，你可以查詢像尿布和啤酒這樣不尋常的樣式！

這一示例以某種方式擴充套件成了這個“真實發生”的故事，此後又隨著事實的延伸，加入各種不同的細節及講述者的不同動機而演變成一個都市傳奇。在多年的傳頌中，這個故事的常見變種包括：

• 沃爾瑪進行了這項資料挖掘工作。

• 零售商利用發現的知識，在週四這天提高啤酒的價格。

• 購買啤酒的動機是作為照顧孩子的報酬（購買尿布想必是為了孩子）。

• 零售商對這些樣式特別感興趣，因為尿布是有利可圖的商品。

實際上，這一故事的真相並不神奇，但是作為一個勵志案例它一直很受歡迎。如果你對頻繁項集或者關聯規則挖掘進行了研究，就會明白市場籃子分析在現實世界中應用的這個故事是個很恰當的例子。關於關聯規則的幾乎每本書、每篇文章和每次演示都用到了它。

2. 頻繁項集挖掘基礎知識

出於我們的目的，我們將把尿布和啤酒的故事當做一個有用的隱喻。具體地說，我們可以使用這個故事中的術語，幫助定義市場籃子分析（或者頻繁項集挖掘）中的3個突出部分：

• 首先，為了進行市場籃子分析，我們需要一個市場。在這個隱喻中，市場就是真正的超市。

• 其次，我們需要一個籃子。在這個例子中，籃子是一次購物交易。有時候，我們使用“籃子”一詞，有時候，你也可能聽到“交易”一詞。

• 我們還需要商品（專案）。在這個隱喻中，為了購買要把零售商品放入籃子（或者交易）中。

只要我們有市場、籃子和商品的概念，只要這些東西的表現和我們所描述的相同，我們就很可能有一個可供挖掘頻繁項集的資料集。

但是，市場分析的故事中還埋藏著幾個假設，這些假設將影響我們是否能夠擁有可挖掘的資料集。所以，現在要明確這些假設：

• 商品和籃子之間應該是多對多的關係。籃子由許多商品組成，一件商品可以出現在許多籃子中。

• 不考慮商品的數量。不管購買的是6包尿布還是1包尿布，相關的事實都是籃子中有尿布。

• 某件商品可能不出現在任何一個籃子中（我確定大家都想到了不受歡迎的某一件商品），但是任何籃子都包含至少一件商品。空的籃子是不會讓人感興趣的！

• 籃子中商品的順序無關緊要。從這個隱喻的角度看，啤酒或者尿布哪一個先放進購物籃並不重要，哪一個放到傳送帶上、哪一個先進入收銀機也是如此。相反，我們將把購買的商品組合起來，比喻成一次交易或者一個籃子，而不管它們在籃子中的位置。

在市場籃子分析的這個階段，我們最感興趣的是找出頻繁項集，也就是在籃子中頻繁同時出現的專案組。在超市中，人們同時購買的某些商品組合很容易用常識猜出，但是有些組合則較為少見。蛋糕粉和糖霜是可預測的商品組合，但是啤酒和尿布這種組合則不同尋常。

有時候，某些組合因為天氣、假日或者地區偏好而比其他組合更可能出現。和任何資料挖掘活動一樣，重要的是理解你所研究的領域。在購物籃的例子中，由於不同的食物偏好，可能有廣泛的地區性差異。例如：

• 我生活在美國南部，我們商店中有許多在其他地區不太常見的有趣組合。例如，人們常常同時購買香草威化餅乾和香蕉，以便製作流行的甜食香蕉布丁。

• 在我所在的州，新年的常見食物包括豇豆（一種莢果）和羽衣甘藍（一種葉菜），所以在接近年底時包含這些商品的籃子可能增加。

• 我所住的地方很少下雪。每當天氣預報報告本地區將要下雪，人們都很驚慌，搶購商店中的所有牛奶和麵包。雖然不管什麼天氣，牛奶和麵包都是人們經常購買的商品，但是在下雪的日子裡，你可能發現牛奶和麵包是更常見的頻繁項集。

我們可以用集合標記符表示這些項集：

有兩個專案的項集稱為2-項集或配對，有3個專案的項集稱為3-項集（或者三元組），以此類推。有時候，配對和三元組分別稱為“雙個體集”和“三個體集”。

02 邁向關聯規則

頻繁項集的內容都很好，但是我們的終極標的是關聯規則，那更激動人心。關聯規則是從頻繁項集中經過一些小曲折形成的。我們對如下關於頻繁項集的陳述感興趣：購買香草威化的人有60%的可能性同時購買香蕉。

換言之，我們需要學習如何計算幾個附加指標，首先是被稱為“支援度”和“置信度”的兩個指標。

1. 支援度

如果你打算尋找頻繁項集，那麼還需要一種表示在籃子中看到這些組合出現的頻繁程度以及這個數量是否可稱為“頻繁”的手段。如果我看到90%的籃子中有{香草威化，香蕉}這樣的組合，可以認為是頻繁的嗎？50%的籃子呢？5%呢？我們稱這一數字為項集的支援度。支援度就是在所有籃子中看到項集的次數。

為了使支援度更有意義，再來談論“興趣度”，我們必須設定最小支援閾值。最小支援閾值是對問題領域有意義的百分比（0%～100%）。如果我們將最小支援閾值設定為5%，就意味著如果在所有籃子中至少有5%能發現該項集，則視其為頻繁項集。

2-項集的支援度通常用機率標記法書寫：

換言之，我們可以將上式讀成“X->Y的支援度等於同時包含X和Y的籃子的百分比”。

在本例中，專案X可能是香草威化，Y可能是香蕉。為了計算項集的支援度，我們統計同時包含這兩種商品的籃子數量，將結果除以籃子總數。如果項集的支援度超過最小支援閾值，則我們認為該項集可能是有用的。

2. 置信度

一旦發現了頻繁項集，我們就可以開始考慮項集中的一個或者多個專案是否引發其他專案的購買。例如，知道在購物籃裡放入香草威化的顧客中，有75%的人同時購買香蕉，這是很有用的。

但是，另一方面，在購物籃中包含香蕉的客戶中，可能只有1%的人將購買香草威化。為什麼？這是因為購買香蕉的人比購買香草威化的人多得多。香蕉較為常見，而香草威化則較為少見。所以，購買關係的方向不一定是對稱的。

這就引出了一個關鍵的概念——置信度。有向關係的置信度寫作：

我們可以將上式讀成“X導致Y的置信度為已知X的情況下Y的機率”。或者用另一種方式書寫為：

X->Y的置信度是同時包含X和Y的籃子的百分比除以只包含X的籃子百分比。

一旦有了支援度和置信度，我們就可以開始將頻繁項集擴充套件為關聯規則了。

3. 關聯規則

既然我們已經知道如何確定某個項集是否頻繁出現，也知道如何設定支援度和置信度，就可以從頻繁項集中建立可能的關聯規則。

下麵是關聯規則的一個例子：

香草威化->香蕉，生奶油

[支援度＝1%，置信度＝40%]

我們可以將這條規則讀作：在所有籃子中，有1%包含香草威化、香蕉和生奶油的組合；在購買香草威化的客戶中，有40%同時購買了香蕉和生奶油。

規則的左側是確定項，稱作先導。右側是結果項，稱作後繼。如果我們切換左側和右側的專案，則必須計算不同的關聯規則，由於香蕉很受歡迎，得到的規則可能是：

香蕉->香草威化，生奶油

[支援度＝0.001%，置信度＝10%]

4. 包含資料的示例

想象我們擁有一家商店，且有下表所示的10個商品籃子。你馬上就可以看出有人為的痕跡，因為這家商店中的所有籃子都正好有3件商品，這在真實的商店中不太可能出現。

首先，我們需要計算商店中所有單獨商品的支援度。在這10個籃子中共有9種商品：

為了簡化例子，我們現在只考慮頻繁項集{香草威化，香蕉}。該項集的支援度是同時包含香草威化和香蕉的籃子的百分比。資料中有4個籃子（1、4、7、9）同時包含這兩項。因此，香草威化->香蕉或者香蕉->香草威化這兩條規則的支援度都是40%，因為10個籃子中有4個同時包含兩者。

現在，我們可以使用這些支援度計算提議的兩條關聯規則的置信度：

香草威化->香蕉

香蕉->香草威化

置信度（香草威化->香蕉）＝支援度（香草威化U香蕉）/支援度（香草威化）＝4/6＝67%

置信度（香蕉->香草威化）＝支援度（香草威化U香蕉）/支援度（香蕉）＝4/8＝50%

香草威化->香蕉[s＝40%，c＝67%]這樣的規則是引人註目、令人滿意的。但是，這是一個非常小的資料集，只是為了舉例而人為製作的。在某些情況下，關聯規則可能很容易引起誤導，我們應該小心為之。考慮下麵的例子。

想象在一家不同的商店中，香草威化和香蕉的支援度可能是這樣的：

• {香草威化}：50%

• {香蕉}：80%

• {香草威化，香蕉}：30%

在這種情況下，商品的單獨支援度相當高，但是商品組合的支援度較低。

在這個例子中，香草威化->香蕉的置信度為0.3/0.8＝37.5%。

有什麼問題呢？有些商品自身的表現好於作為關聯規則後繼時的表現。即使規則符合某些最小支援閾值，我們也必須考慮商品在規則之外的表現。

為此，我們計算一個稱作關聯規則附加值的測度。香草威化->香蕉規則的附加值透過從規則置信度減去香蕉的支援度計算。如果附加值是大的正數，那麼規則是好的、有用的。如果附加值接近於0，則這條規則可能是正確的，但是沒太大用處。如果附加值是大的負數，那麼規則中的商品實際上是負相關的，這時單獨使用表現會更好。

我們這樣計算附加值：

附加值＝規則置信度-右側的支援度

使用上表，可以計算出：

• 規則置信度＝0.375

• 右側（香蕉）的支援度＝0.8

• 附加值＝0.375―0.8＝―0.425

這個數字告訴我們，實際上香蕉自己的表現更好。而且，我們提出的將香蕉展示櫃移到香草威化旁邊的建議可能是個錯誤，因為利用香蕉和威化之間關係的嘗試沒有任何收益。

我們可以稍微改變一下資料，人為生成正面的有用規則：

• {香草威化}：50%

• {香蕉}：30%

• {香草威化，香蕉}：30%

現在，香草威化->香蕉的置信度為0.3/0.3=100%。

• 規則置信度＝1.0

• 香蕉的支援度＝0.3

• 附加值＝1―0.3＝0.7

在這種情況下，商店中的香蕉和香草威化應該放在一起，因為明顯沒有任何人將香蕉作為唯一商品購買！

計量關聯規則興趣度的方法還有很多，但是這超出了本文的範圍。建議感興趣的讀者在谷歌學術上搜索介紹這一主題的最新論文。使用“關聯規則興趣度計量”等搜尋詞可以找到許多好的資訊來源。在這些論文中，對於不同型別的資料和問題，有許多出色的“興趣度”計量。

6. 尋找頻繁項集的方法

目前，我們已經知道，尋找關聯規則的基礎是首先尋找頻繁項集。此後，只需要根據之前找到的計數進行計算。

幫助我們更快找到頻繁項集的一條重要原則稱為向上閉包屬性。向上閉包指的是，只有在項集的所有專案都頻繁出現時，該項集才是頻繁項集。換言之，如果項集中包含的專案不都是頻繁出現的，則計算項集的支援度就毫無意義。

為什麼瞭解閉包原則很重要？因為知道這一原則將節約許多計算可能項集的時間。在擁有數十萬種商品的商店中計算每個可能項集的支援度明顯不實際！盡可能減少項集的數量對我們絕對有好處。降低項集數量的策略之一是利用向上閉包減少項集數量，構建如下演演算法：

1）首先，設定一個支援閾值。

2）構建一個1-項集（單例）串列，該串列稱為CandidateSingletonList：

• 為此，從每種可能專案的串列開始。這個串列稱作CandidateSingletonList。

• 計算CandidateSingletonList中每個單獨專案的支援度。

• 僅保留符合支援閾值的單例，並將其加入SingletonList串列。

3）構造一個2-項集串列（雙個體集）：

• 為此，從SingletonList入手。

• 建立SingletonList中專案的所有可能配對的串列，這個串列稱作Candidate-Doubleton-List。

• 僅保留符合支援閾值的候選二元組，將其新增到串列DoubletonList中。

4）構建3-項集（三個體集）串列：

• 為此，從DoubletonList入手。

• 建立DoubletonList中出現的每個可能單項的串列，將其與DoubletonList中的每個專案匹配，建立三元組。這個串列稱為CandidateTripletonList。

• 僅保留符合支援閾值的候選三元組，將其新增到串列TripletonList中。

5）重覆第4）步，用前面構建的串列中的單項生成n-項集，直到頻繁項集用完。

這個演演算法稱作Apriori演演算法，1994年Agarwal和Srikant的論文“Fast algorithms for mining association rules in large databases”（挖掘大型資料庫中關聯規則的快速演演算法）中率先概述了該演演算法。

從那時起，人們提出了許多其他演演算法，對其進行最佳化，包括利用並行性和更有趣資料結構（如樹）的方法。還有用於特種籃子資料的演演算法；例如，我們的籃子中是有序的專案，或者籃子中包含分類或者層次資料。但是，對於基本的頻繁項集生成，Apriori演演算法是經典的選擇。

在實現Apriori演演算法之前，我們要特別關註生成候選項集的幾條重要方針。雖然計算2-項集是很費時的，但這是整個過程中最為密集的工作了。由於前面提到的閉包屬性，後續的資料可能構建的項集比之前更少。

本身，減少在二元組階段需要比較的專案數量對我們肯定有利。為此，我們將設定一個最小支援閾值，但是這個閾值可以根據你所承擔專案的需要進行調整。

本文摘編自《Python資料挖掘：概念、方法與實踐》，經出版方授權釋出。

延伸閱讀《Python資料挖掘：概念、方法與實踐》

點選上圖瞭解及購買

轉載請聯絡微信：DoctorData

推薦語：在本書中，你將深入許多資料挖掘中常被忽視的領域，包括關聯規則挖掘、物體匹配、網路挖掘、情緒分析、命名物體識別、文字摘要、主題建模和異常檢測。對於每種資料挖掘技術，我們將在比較解決每種問題所用的各種策略之前，研究目前新的佳實踐。然後，將用來自軟體工程領域的實際資料，實現示例解決方案，並學習理解和解讀所得結果的方法。