441
《Python數據挖掘：概念、方法與實踐》關聯規則挖掘
關聯規則挖掘
在數據挖掘工具箱中，計量某個模式的頻率是一項關鍵任務。在某些情況下，較頻繁出現的模式可能最終成為更加重要的模式。如果我們可以發現經常同時出現的兩個或者三個項目，就更為有趣了。
在本章中，我們開始研究頻繁項集，然後將其擴展為稱作關聯規則的一類模式。我們將介紹如下主題：
什麼是頻繁項集？使用哪些技術找出頻繁項集？瓶頸在哪裏？如何加速這一過程？
如何將頻繁項集擴展為關聯規則？
什麼是好的關聯規則？我們將根據數據庫中的支持程度、對規則本身的置信度以及我們找出的規則所增加的價值，學習描述特定關聯規則的價值。
為此，我們將編寫一個程序，在關於一組軟件項目的元數據（事實）公開數據集中尋找頻繁項集。然後，學習在用於描述那些項目的標記中尋找頻繁項集。接著，將學習通過計算數據庫支持度，然後增加概率導向（X蘊含Y）置信區間，將頻繁項集擴展為關聯規則。最後，將學習如何解讀關聯規則。具體地說，我們應該理解關聯規則說明以及沒有說明的情況。
2.1 什麼是頻繁項集
尋找頻繁項集是一種計數活動。但是和從生成數據集中觀測到的項目的簡單計數（今天我們賣出了80個胡蘿卜和100個馬鈴薯）相比，尋找頻繁項集稍有不同。確切地說，為了找出頻繁項集，我們要搜索較大的組中共同出現的項集。有時候可以把這些較大的組視為超市交易或者購物籃，整個活動有時候稱為市場籃子分析。我們仍然采用超市的類比，在這些籃子中同時出現的物品有時候被視為在超市中購買的產品組合。例如，已知一組超市交易或者籃子，我們可能對籃子中{胡蘿卜，馬鈴薯}的組合是否比{黃瓜、檸檬}的組合更頻繁出現感興趣。
頻繁項集挖掘的目的是發現一組交易中共同出現的有趣項目組合。換言之，如果我們發現某些組合在多個籃子中頻繁出現，則這種挖掘可能很有實用價值。如果我們發現的頻繁項集有些不同尋常或者有些意外，那就更加有趣了。在頻繁項集挖掘中令人滿意的有趣規則的典範是一再被傳頌的都市傳奇—“尿布與啤酒”。
2.1.1 都市傳奇“尿布與啤酒”
我記得第一次聽到這個故事是在1998年的一個數據挖掘研究生課程上。我的教授試圖解釋頻繁項集和關聯規則的實用性，他給我們班上的學生講了如下故事：
“中西部的一家連鎖超市欲挖掘頻繁項集，以便發現一同購買的有趣商品組合。他們的計劃是通過在商店中將這些產品放在一起，優化銷售業績。令他們高興的是，商店的數據挖掘團隊發現，周四下午5點～7點，男人們頻繁地購買尿布和啤酒。該商店將一個小的尿布陳列櫃移到啤酒通道中，結果兩種產品的銷售量同時飆升。”
我對這個故事表示懷疑，立刻提出了許多問題。這家商店是如何知道男人購買了這些東西？畢竟，這個故事發生的時候，商店的電子優惠卡或者獎勵卡尚未出現。這家商店怎麼可能選擇合適的尿布放入啤酒通道中間的小展示櫃？畢竟，尿布有5種不同的尺寸，至少有3種品牌，而且（我像一位初為人父的男人一樣快速學習）—一時興起地更換某種尺寸或者品牌不是好主意，那可能會帶來災難性的後果。
其他許多人也表示懷疑，有些人甚至試圖追尋這一都市傳奇的曆史。最好的研究範例包括Dan Powers的新聞稿《DSS Resources》，2001年11月10日的那一期（第3卷第23號）專門描寫了尋找這個故事真正來源的經過。這篇引人入勝的文章可以在https://www.dssresources. com/newsletters/66.php上找到。此後，英國的《The Register》於2006年也講述了一個關於這個都市傳奇的故事。這篇文章可以在https://www.theregister. co.uk/ 2006/08/15/beer_diapers上找到。
如果你相信這兩篇文章講述的細節，尿布與啤酒的故事則是說明早期數據挖掘可能性的一個示例：使用我們的數據庫產品，你可以查詢像尿布和啤酒這樣不尋常的模式！這一示例以某種方式擴展成了這個“真實發生”的故事，此後又隨著事實的延伸，加入各種不同的細節及講述者的不同動機而演變成一個都市傳奇。在多年的傳頌中，這個故事的常見變種包括：
沃爾瑪進行了這項數據挖掘工作。
零售商利用發現的知識，在周四這天提高啤酒的價格。
購買啤酒的動機是作為照顧孩子的報酬（購買尿布想必是為了孩子）。
零售商對這些模式特別感興趣，因為尿布是有利可圖的商品。
實際上，這一故事的真相並不神奇，但是作為一個勵誌案例它一直很受歡迎。如果你對頻繁項集或者關聯規則挖掘進行了研究，就會明白市場籃子分析在現實世界中應用的這個故事是個很恰當的例子。關於關聯規則的幾乎每本書、每篇文章和每次演示都用到了它。
2.1.2 頻繁項集挖掘基礎知識
出於我們的目的，我們將把尿布和啤酒的故事當做一個有用的隱喻。具體地說，我們可以使用這個故事中的術語，幫助定義市場籃子分析（或者頻繁項集挖掘）中的3個突出部分：
首先，為了進行市場籃子分析，我們需要一個市場。在這個隱喻中，市場就是真正的超市。
其次，我們需要一個籃子。在這個例子中，籃子是一次購物交易。有時候，我們使用“籃子”一詞，有時候，你也可能聽到“交易”一詞。
我們還需要商品（項目）。在這個隱喻中，為了購買要把零售商品放入籃子（或者交易）中。
隻要我們有市場、籃子和商品的概念，隻要這些東西的表現和我們所描述的相同，我們就很可能有一個可供挖掘頻繁項集的數據集。
但是，市場分析的故事中還埋藏著幾個假設，這些假設將影響我們是否能夠擁有可挖掘的數據集。所以，現在要明確這些假設：
商品和籃子之間應該是多對多的關係。籃子由許多商品組成，一件商品可以出現在許多籃子中。
不考慮商品的數量。不管購買的是6包尿布還是1包尿布，相關的事實都是籃子中有尿布。
某件商品可能不出現在任何一個籃子中（我確定大家都想到了不受歡迎的某一件商品），但是任何籃子都包含至少一件商品。空的籃子是不會讓人感興趣的！
籃子中商品的順序無關緊要。從這個隱喻的角度看，啤酒或者尿布哪一個先放進購物籃並不重要，哪一個放到傳送帶上、哪一個先進入收銀機也是如此。相反，我們將把購買的商品組合起來，比喻成一次交易或者一個籃子，而不管它們在籃子中的位置。
在市場籃子分析的這個階段，我們最感興趣的是找出頻繁項集，也就是在籃子中頻繁同時出現的項目組。在超市中，人們同時購買的某些商品組合很容易用常識猜出，但是有些組合則較為少見。蛋糕粉和糖霜是可預測的商品組合，但是啤酒和尿布這種組合則不同尋常。
有時候，某些組合因為天氣、假日或者地區偏好而比其他組合更可能出現。和任何數據挖掘活動一樣，重要的是理解你所研究的領域。在購物籃的例子中，由於不同的食物偏好，可能有廣泛的地區性差異。例如：
我生活在美國南部，我們商店中有許多在其他地區不太常見的有趣組合。例如，人們常常同時購買香草威化餅幹和橡膠，以便製作流行的甜食香蕉布丁。
在我所在的州，新年的常見食物包括豇豆（一種莢果）和羽衣甘藍（一種葉菜），所以在接近年底時包含這些商品的籃子可能增加。
我所住的地方很少下雪。每當天氣預報報告本地區將要下雪，人們都很驚慌，搶購商店中的所有牛奶和麵包。雖然不管什麼天氣，牛奶和麵包都是人們經常購買的商品，但是在下雪的日子裏，你可能發現牛奶和麵包是更常見的頻繁項集。
我們可以用集合標記符表示這些項集：
有兩個項目的項集稱為2-項集或配對，有3個項目的項集稱為3-項集（或者三元組），以此類推。有時候，配對和三元組分別稱為“雙個體集”和“三個體集”。
2.2 邁向關聯規則
頻繁項集的內容都很好，但是我們的終極目標是關聯規則，那更激動人心。關聯規則是從頻繁項集中經過一些小曲折形成的。我們對如下關於頻繁項集的陳述感興趣：購買香草威化的人有60%的可能性同時購買香蕉。換言之，我們需要學習如何計算幾個附加指標，首先是被稱為“支持度”和“置信度”的兩個指標。
2.2.1 支持度
如果你打算尋找頻繁項集，那麼還需要一種表示在籃子中看到這些組合出現的頻繁程度以及這個數量是否可稱為“頻繁”的手段。如果我看到90%的籃子中有{香草威化，香蕉}這樣的組合，可以認為是頻繁的嗎？50%的籃子呢？5%呢？我們稱這一數字為項集的支持度。支持度就是在所有籃子中看到項集的次數。
為了使支持度更有意義，再來談論“興趣度”，我們必須設置最小支持閾值。最小支持閾值是對問題領域有意義的百分比（0%～100%）。如果我們將最小支持閾值設置為5%，就意味著如果在所有籃子中至少有5%能發現該項集，則視其為頻繁項集。
2-項集的支持度通常用概率標記法書寫：
換言之，我們可以將上式讀成“X->Y的支持度等於同時包含X和Y的籃子的百分比”。在本例中，項目X可能是香草威化，Y可能是香蕉。為了計算項集的支持度，我們統計同時包含這兩種商品的籃子數量，將結果除以籃子總數。如果項集的支持度超過最小支持閾值，則我們認為該項集可能是有用的。
2.2.2 置信度
一旦發現了頻繁項集，我們就可以開始考慮項集中的一個或者多個項目是否引發其他項目的購買。例如，知道在購物籃裏放入香草威化的顧客中，有75%的人同時購買香蕉，這是很有用的。但是，另一方麵，在購物籃中包含香蕉的客戶中，可能隻有1%的人將購買香草威化。為什麼？這是因為購買香蕉的人比購買香草威化的人多得多。香蕉較為常見，而香草威化則較為少見。所以，購買關係的方向不一定是對稱的。
這就引出了一個關鍵的概念—置信度。有向關係的置信度寫作：
我們可以將上式讀成“X導致Y的置信度為已知X的情況下Y的概率”。或者用另一種方式書寫為：
X->Y的置信度是同時包含X和Y的籃子的百分比除以隻包含X的籃子百分比。
一旦有了支持度和置信度，我們就可以開始將頻繁項集擴展為關聯規則了。
2.2.3 關聯規則
既然我們已經知道如何確定某個項集是否頻繁出現，也知道如何設置支持度和置信度，就可以從頻繁項集中建立可能的關聯規則。
下麵是關聯規則的一個例子：
香草威化->香蕉，生奶油
[支持度＝1%，置信度＝40%]
我們可以將這條規則讀作：在所有籃子中，有1%包含香草威化、香蕉和生奶油的組合；在購買香草威化的客戶中，有40%同時購買了香蕉和生奶油。
規則的左側是確定項，稱作先導。右側是結果項，稱作後繼。如果我們切換左側和右側的項目，則必須計算不同的關聯規則，由於香蕉很受歡迎，得到的規則可能是：
香蕉->香草威化，生奶油
[支持度＝0.001%，置信度＝10%]
2.2.4 包含數據的示例
想象我們擁有一家商店，且有下表所示的10個商品籃子。你馬上就可以看出有人為的痕跡，因為這家商店中的所有籃子都正好有3件商品，這在真實的商店中不太可能出現。
籃 子 商品1 商品2 商品3
1 香草威化 香蕉 狗糧
2 香蕉 麵包 酸奶
3 香蕉 蘋果 酸奶
4 香草威化 香蕉 生奶油
5 麵包 香草威化 酸奶
6 牛奶 麵包 香蕉
7 香草威化 蘋果 香蕉
8 酸奶 蘋果 香草威化
9 香草威化 香蕉 牛奶
10 香蕉 麵包 花生醬
首先，我們需要計算商店中所有單獨商品的支持度。在這10個籃子中共有9種商品：
商 品 支 持 度 商 品 支 持 度
蘋果 3 花生醬 1
香蕉 8 香草威化 6
麵包 4 酸奶 4
狗糧 1 生奶油 1
牛奶 2
為了簡化例子，我們現在隻考慮頻繁項集{香草威化，香蕉}。該項集的支持度是同時包含香草威化和香蕉的籃子的百分比。數據中有4個籃子（1、4、7、9）同時包含這兩項。因此，香草威化->香蕉或者香蕉->香草威化這兩條規則的支持度都是40%，因為10個籃子中有4個同時包含兩者。
現在，我們可以使用這些支持度計算提議的兩條關聯規則的置信度：
香草威化->香蕉
香蕉->香草威化
置信度（香草威化->香蕉）＝支持度（香草威化U香蕉）/支持度（香草威化）＝4/6＝67%
置信度（香蕉->香草威化）＝支持度（香草威化U香蕉）/支持度（香蕉）＝4/8＝50%
寫成關聯規則，可以得到：
香草威化->香蕉[支持度＝40%，置信度＝67%]
香蕉->香草威化[支持度 ＝40%，置信度＝50%]
規則“香草威化->香蕉”強於（支持度相同，置信度更高）規則“香蕉->香草威化”。
2.2.5 附加值—修複計劃中的漏洞
香草威化->香蕉[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
在這種情況下，商店中的香蕉和香草威化應該放在一起，因為明顯沒有任何人將香蕉作為唯一商品購買！
計量關聯規則興趣度的方法還有很多，但是這超出了本書的範圍。建議感興趣的讀者在穀歌學術上搜索介紹這一主題的最新論文。使用“關聯規則興趣度計量”等搜索詞可以找到許多好的信息來源。在這些論文中，對於不同類型的數據和問題，有許多出色的“興趣度”計量。
2.2.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實現Apriori算法，用它找出一個現實世界的數據庫中的關聯規則。
2.3 項目—發現軟件項目標簽中的關聯規則
1997年，Freshmeat網站創立，它是一個跟蹤免費、自由和開放源碼軟件（FLOSS）項目的目錄。2011年，該網站更名為Freecode。在出售、並購和多次網站重新設計之後，2014年，Freecode網站的所有更新都停止了。這個網站仍然在線，但是不再更新，目錄中也不再加入任何新項目。現在，Freecode是20世紀90年代和21世紀初FLOSS項目相關信息的快照。每個軟件項目的相關事實包括名稱、描述、下載軟件的URL、描述其特征的標簽、代表其流行度的一個數值，等等。
作為我的FLOSSmole項目的一部分，我從2005年起就將來自Freshmeat/Freecode的數據編目。Freshmeat/Freecode提供定期的RDF下載，描述網站上的每個項目。我下載了這些RDF，解析出項目數據，將其組織為數據庫表，並提供基本的數據可視化處理。對於本書，我們可使用這個數據回答關於哪些項目標簽在FLOSS項目中最經常同時出現的問題。為此，我們將從項目標簽中找出頻繁項集，並生成後續的關聯規則。頻繁項集將采用{GPL, Linux, C}這樣的形式。關聯規則的樣板形如：GPL, Linux -> C [s=.60, c=.90, av=.15]。
首先，登錄MySQL服務器，選擇本項目使用的數據庫（我的是test），創建一個數據庫表，保存項目的主列表及標簽：
在這個數據集中，每個項目由Freecode網站提供的一個數字和將項目添加到目錄中的人指定的一個標簽列表標識。例如，編號為8的項目有標簽GPL、多媒體和語音/音頻標簽。
要填入這個表的內容，可以使用本書GitHub網站（https://github.com/megansquire/mastering DM）上的數據文件，具體文件在chapter 2目錄中：https://github.com/megansquire/ mastering DM/blob/master/ch2/fc_project_tags.sql.gz。
為了在命令行上將這些數據加載到MySQL數據庫中，將該文件解壓到你的工作目錄，然後登錄MySQL服務器，使用正確的數據庫，發出source命令運行所有INSERT命令。過程如下：
在本章的項目中，每個項目僅由其編號標識。但是，如果你想要找出單獨項目的更多相關細節，或者將這些數據用於另一個項目，所有Freshmeat/Freecode數據都可以從FLOSSmole網站上的如下目錄免費訪問：https://flossdata.syr.edu/data/fc/。我們用於本章的數據來自2014年3月，在FLOSSmole係統中，該數據集編號為8079。為簡單起見，本章的例子不使用該編號。
為了回答前麵的問題（哪些標簽最經常同時被發現？），我們需要先對數據稍作研究。首先，可以計算項目標簽組合的總數，注意，一個項目可能有多個標簽：
接下來，可以計算項目的總數。按照相關規則的術語，可以將Freecode項目視為購物籃或者交易，每個項目標簽等價於購物籃中的一件商品：
數據集中有多少個唯一的項目？
這樣，有46 510個籃子，11 006件商品。為減少可能的相關規則數量，可以計算含有每個標簽的項目有多少個（包含各個產品的籃子有多少個），並刪除非常罕見的標簽。下表展示了達到每個可能支持閾值所需的項目數：
標簽支持率 需要的項目數
50% 23 255
40% 18 604
30% 13 953
10% 4651
5% 2325
例如，使用5%的閾值，我們可以將可能的項集從11 006降低為29個。精簡後的標簽集將成為單例。所有頻繁出現的二元組將以這些單例為基礎，三元組將從二元組構建。下麵是生成單例列表、保持5%最小支持閾值的SQL：
下表列出了前幾個結果：
標 簽 名 稱 項 目 數 量
GPL 21 182
POSIX 16 875
Linux 16 288
C 10 292
OS Independent 10 180
程序代碼可以在本書的GitHub存儲庫上找到（https://github.com/megansquire/mastering DM/tree/master/ch2），這段程序計算籃子數量，然後使用最小支持閾值找出單例，代碼如下。MINSUPPORTPCT是可以任意設置的常數，開始時設置為5：
接下來，計算籃子數量—數據庫表中的項目數：
使用籃子數和前麵設置的最小支持閾值，可以計算籃子的最小數量：
現在，可以得到一組符合最小支持閾值的標簽：
接下來，使用頻繁的單例創建候選二元組。將這一任務封裝在find Doubletons()函數中。稍後，我們將討論findDoubletons()、findTripletons()和generate Rules()函數。程序的最後一行在完成工作時關閉數據庫連接：
正如已經討論過的，前麵在概述Apriori策略時講過，預先用所有可能的候選二元組填寫數據庫，然後對其進行計數是不切實際的，因為可能的配對太多了。相反，我們在內存中生成候選二元組，計算其支持閾值，僅保留滿足支持閾值條件的二元組。正如前麵的單例計數，二元組和三元組的閾值都保持為5%（2325個項目），使用常數MINSUPPORT保存這個支持值。此外，依賴itertools.combinations()函數，從allSingletonTags列表中生成所有size=2的可能組合。最後，將這些頻繁出現的標簽添加到新列表allDoubletonTags中，將在下麵的findTripletons()函數中使用這個列表：
程序將二元組（以及之後的三元組）寫入兩個新的數據庫表，如果你不想這麼做，可以刪除INSERT語句。這兩個表的CREATE語句在下麵的代碼中顯示。這些SQL語句可以在additionalQueries.sql文件中找到，該文件可以從前麵提到的本書GitHub網站上下載：
得到二元組列表之後，該程序使用列表找出候選三元組。findTripletons()函數與findDoubletons()函數類似，但是我們必須考慮閉包屬性。意思是，我們不能生成其中的二元組本身不頻繁出現的任何候選三元組。正如findDoubletons()函數結束之前那樣，創建所有二元組的列表（doubletonList），現在我們用enumerate()函數獲得候選三元組中的所有可能二元組，如果那些二元組不都在頻繁二元組列表中，就可以拒絕該三元組。
這似乎有些混亂，所以舉個例子來說明。假定已經生成了如下頻繁二元組：
如果簡單地使用列表中的所有項目創建一個候選三元組{foo, bar, baz}，則該三元組就是無效的，因為它包含了非頻繁二元組{foo,baz}。因此，隻能生成其中所有可能二元組都頻繁出現的三元組。找出三元組的代碼如下：
在Freecode數據集上運行時，程序生成了37個二元組，下表按支持度從高到低列出了這些二元組：
標簽1 標簽2 項 目 數
C GPL 5543
C Linux 5653
C POSIX 6956
C++ GPL 2914
C++ Linux 3428
C++ POSIX 3502
Communications GPL 2578
Dynamic Content Internet 3173
Dynamic Content Web 3171
English Linux 2662
GPL Internet 4038
GPL Linux 8038
GPL Multimedia 2883
GPL OS independent 4405
GPL PHP 2376
GPL POSIX 10 069
GPL Software development 3319
GPL Web 2901
GPL Windows 2605
Internet OS 3007
Internet POSIX 2832
Internet Web 5978
Java OS independent 3436
Java Software development 2360
Libraries Software development 5638
Linux Mac OS X 2974
Linux POSIX 11 903
Linux Software development 2336
Linux Unix 2494
Linux Windows 5281
Mac OS X Windows 3131
Multimedia POSIX 2539
OS independent Software development 3566
OS independent Web 2605
POSIX Software development 3503
POSIX Unix 2326
POSIX Windows 4467
該程序還生成了4個三元組，在下表中按照支持度從高到低排列：
標簽1 標簽2 標簽3 項 目 數
Internet OS independent Web 2519
GPL Linux POSIX 7384
C GPL Linux 3299
C GPL POSIX 4364
GPL Internet Web 2878
Dynamic Content Internet Web 3166
Linux POSIX Windows 3315
C++ Linux POSIX 2622
C Linux POSIX 4629
得到這些頻繁項集之後，就可以開始從中設計關聯規則，為每條規則指定支持度和置信度了。下麵是從三元組中生成規則的例程代碼。首先生成右側有單一項目的規則，這是根據和生成頻繁項集時相同的閉包屬性。換言之，如果{香草威化，香蕉->棉花糖}這樣的規則不令人感興趣，那麼計量其他右側有棉花糖存在的選項（如{香草威化->香蕉，棉花糖}就毫無意義。
最後，這段代碼還打印每條規則的附加值得分，這是通過從整條規則的置信度中減去右側項支持值計算的：
從上述代碼生成的Freecode規則如下所示。因為每個三元組可能生成3條規則，因此每條的右側都有單一項目。為了顯示的目的，我們將此分為包含3行的組：
根據上述結果，我們如何知道哪些規則是有意義的？隻觀察支持值並不能得到特別有意義的線索，因為我們規定所考慮的每條規則至少必須有5%的支持度。
置信度與支持度的組合可能是有趣的計量手段。例如，規則{GPL , Linux -> POSIX}的支持度最高（16%）且置信度超過90%。相反，規則{Linux , POSIX -> C++}的支持度剛好超過閾值（6%）且置信度最低（22%）。
附加值告訴我們，關聯規則在預測方程右側上與簡單地觀察右側本身相比有多大的優勢。這組規則沒有任何直接負相關的項目，但是有幾條規則極其接近於0，這表明僅使用右側的效果與將其作為規則一部分相同。舉個例子，{Internet , Web -> GPL}的附加值非常低，這表明僅使用GPL可能起到相同的效果，因為它作為單一項時的得分非常高。規則{Linux , POSIX -> C++}也屬於附加值很低的類別，是列表中第二低的。加上非常低的支持度和置信度得分，使這條規則成為列表上價值最低的規則。
附加值得分較高的規則包括{Dynamic Content , Internet -> Web}和{Dynamic Content , Web -> Internet}。這兩條規則特別有趣，因為分組中的第三條規則{Internet, Web -> Dynamic Content}的附加值（0.53）很平常。接下來我們注意到，列表中最高附加值的規則的右側都有Web或者Internet，而另一個項目則出現在左側的某個地方。這說明Web和Internet是本數據集中聯係非常緊密的項目，它們對其他項目的預測能力不如相互預測的能力。
發現這種關係，意味著我們可以更深入地探究Web和Internet之間的關係。確切地說，我們應該關注規則Web -> Internet和 Internet -> Web。由於我們在數據庫中保存了支持計數，因此可以使用SQL查詢找出這兩條規則的支持度、置信度和附加值：
上述SQL將得到如下結果：
上述SQL代碼看起來很嚇人，所以這裏用一個小的Python腳本對數據庫運行每個單獨查詢，使用得到的數值計算支持度、置信度和附加值。和以前一樣，填寫數據庫連接細節，並將想要比較的兩個術語填入常量X和Y中：
對於Internet和Web這兩個術語，結果和前麵較長的SQL查詢一樣：
這些結果似乎沒有給人留下太深刻的印象—畢竟，Internet和Web緊密相關並不是特別令人震驚的事情。但是，我們從這一過程中得到了一些重要的教訓。首先，結果可用於提出建議，如果有人為項目打上標簽“Web”，我們可能也想建議用“Internet”作為相關的標簽。此外，我們可能也想向關注Internet項目的人們交叉推銷Web項目，反之亦然。和在商店中將商品放置在同一位置不同，在數字化環境中作出推薦或者建議的代價沒有那麼高。在任何情況下，找出頻繁項集並生成關聯規則都是有用的工作，其可以確認我們對數據產生的懷疑，或者幫助我們理解數據中的底層模式，而用其他手段不一定能發現這種模式。
2.4 小結
本章，我們學習了如何用Apriori算法從數據集中生成頻繁項集。然後，通過描述支持度和置信度，從這些項集中提出關聯規則。我們檢查額外的附加值計量，確保提出的規則有意義。我們用免費的Freecode開放源碼項目及標簽數據集實現了這些概念。計算出單一標簽的支持度，然後生成滿足最小支持閾值的二元組和三元組。對於右側有一個項目的規則，我們計算了每條規則的置信度和附加值。最後，我們密切關注生成的規則，用已經計算出的指標嚐試找出感興趣的規則。
在下一章中，我們將繼續尋求數據集項目之間的聯係。但是，和本章中試圖找出由兩個或者三個已經有某種聯係的項目組成的分組不同，下一章中我們將嚐試關聯尚未確定有聯係的項目！
最後更新：2017-05-19 16:37:53