積跬步以致千里,積怠惰以致深淵
主要內(nèi)容
“啤酒與尿布”的例子相信很多人都聽說過吧，故事是這樣的：在一家超市中霍转，人們發(fā)現(xiàn)了一個特別有趣的現(xiàn)象荐绝，尿布與啤酒這兩種風馬牛不相及的商品居然擺在一起。但這一奇怪的舉措居然使尿布和啤酒的銷量大幅增加了避消。這可不是一個笑話低滩，而是一直被商家所津津樂道的發(fā)生在美國沃爾瑪連鎖超市的真實案例。原來岩喷，美國的婦女通常在家照顧孩子恕沫，所以她們經(jīng)常會囑咐丈夫在下班回家的路上為孩子買尿布，而丈夫在買尿布的同時又會順手購買自己愛喝的啤酒纱意。這個發(fā)現(xiàn)為商家?guī)砹舜罅康睦麧櫳羲荩侨绾螐暮迫鐭熀s又雜亂無章的數(shù)據(jù)中，發(fā)現(xiàn)啤酒和尿布銷售之間的聯(lián)系呢?這種從大規(guī)模的數(shù)據(jù)中發(fā)現(xiàn)物品間隱含關系的方法被稱為關聯(lián)分析偷霉，也就是本文要主要研究的一種常用的分析方法迄委，Apriori算法是最著名的關聯(lián)規(guī)則挖掘算法之一。下面就圍繞該算法展開學習类少。
關聯(lián)分析
關聯(lián)分析是在大規(guī)模數(shù)據(jù)集中尋找有趣關系的任務跑筝。這些關系可以有兩種形式：
1、頻繁項集
2瞒滴、關聯(lián)規(guī)則
頻繁項集（frequent item sets）是經(jīng)常出現(xiàn)在一塊兒的物品的集合曲梗，關聯(lián)規(guī)則（association rules）暗示兩種物品之間可能存在很強的關系赞警。
下面用一個例子來說明這兩種概念：圖1給出了某個雜貨店的交易清單。
頻繁項集是指那些經(jīng)常出現(xiàn)在一起的商品集合虏两，圖中的集合{葡萄酒,尿布,豆奶}就是頻繁項集的一個例子愧旦。從這個數(shù)據(jù)集中也可以找到諸如尿布->葡萄酒的關聯(lián)規(guī)則，即如果有人買了尿布定罢，那么他很可能也會買葡萄酒笤虫。使用頻繁項集和關聯(lián)規(guī)則，商家可以更好地理解顧客的消費行為祖凫，所以大部分關聯(lián)規(guī)則分析示例來自零售業(yè)琼蚯。
我們用支持度和可信度來度量這些有趣的關系。一個項集的支持度（support）被定義數(shù)據(jù)集中包含該項集的記錄所占的比例惠况。如上圖中遭庶，{豆奶}的支持度為4/5，{豆奶,尿布}的支持度為3/5稠屠。支持度是針對項集來說的峦睡，因此可以定義一個最小支持度，而只保留滿足最小值尺度的項集权埠。
可信度或置信度（confidence）是針對關聯(lián)規(guī)則來定義的榨了。規(guī)則{尿布}?{啤酒}的可信度被定義為"支持度({尿布,啤酒})/支持度({尿布})"，由于{尿布,啤酒}的支持度為3/5攘蔽，尿布的支持度為4/5龙屉，所以"尿布?啤酒"的可信度為3/4。這意味著對于包含"尿布"的所有記錄满俗，我們的規(guī)則對其中75%的記錄都適用叔扼。
Apriori原理
假設我們有一家經(jīng)營著4種商品（商品0，商品1漫雷，商品2和商品3）的雜貨店瓜富，2圖顯示了所有商品之間所有的可能組合：
對于單個項集的支持度，我們可以通過遍歷每條記錄并檢查該記錄是否包含該項集來計算降盹。對于包含N中物品的數(shù)據(jù)集共有2^N-1種項集組合与柑，重復上述計算過程是不現(xiàn)實的。
研究人員發(fā)現(xiàn)一種所謂的Apriori原理蓄坏，可以幫助我們減少計算量价捧。Apriori原理是說如果某個項集是頻繁的，那么它的所有子集也是頻繁的涡戳。更常用的是它的逆否命題结蟋，即如果一個項集是非頻繁的，那么它的所有超集也是非頻繁的渔彰。
在圖3中嵌屎，已知陰影項集{2,3}是非頻繁的推正。利用這個知識，我們就知道項集{0,2,3}宝惰，{1,2,3}以及{0,1,2,3}也是非頻繁的植榕。也就是說，一旦計算出了{2,3}的支持度尼夺，知道它是非頻繁的后尊残，就可以緊接著排除{0,2,3}、{1,2,3}和{0,1,2,3}淤堵。
使用Apriori算法來發(fā)現(xiàn)頻繁項集
前面提到拐邪，關聯(lián)分析的目標包括兩項：發(fā)現(xiàn)頻繁項集和發(fā)現(xiàn)關聯(lián)規(guī)則慰毅。首先需要找到頻繁項集，然后才能獲得關聯(lián)規(guī)則（正如前文所講庙睡，計算關聯(lián)規(guī)則的可信度需要用到頻繁項集的支持度）。
Apriori算法是發(fā)現(xiàn)頻繁項集的一種方法技俐。Apriori算法的兩個輸入?yún)?shù)分別是最小支持度和數(shù)據(jù)集乘陪。該算法首先會生成所有單個元素的項集列表。接著掃描數(shù)據(jù)集來查看哪些項集滿足最小支持度要求雕擂，那些不滿足最小支持度的集合會被去掉啡邑。然后，對剩下來的集合進行組合以生成包含兩個元素的項集井赌。接下來谤逼，再重新掃描交易記錄，去掉不滿足最小支持度的項集仇穗。該過程重復進行直到所有項集都被去掉或直至包含個數(shù)等于所有候選元素個數(shù)的頻繁項集流部。
從頻繁集中挖掘相關規(guī)則
解決了頻繁項集問題，下一步就可以解決相關規(guī)則問題纹坐。
要找到關聯(lián)規(guī)則枝冀，我們首先從一個頻繁項集開始。從雜貨店的例子可以得到耘子，如果有一個頻繁項集{豆奶,萵苣}果漾，那么就可能有一條關聯(lián)規(guī)則“豆奶?萵苣”。這意味著如果有人購買了豆奶谷誓，那么在統(tǒng)計上他會購買萵苣的概率較大绒障。注意這一條反過來并不總是成立，也就是說捍歪，可信度(“豆奶?萵苣”)并不等于可信度(“萵苣?豆奶”)户辱。
前文也提到過鸵钝，一條規(guī)則P?H的可信度定義為support(P | H)/support(P)，其中“|”表示P和H的交集焕妙〗祝可見可信度的計算是基于項集的支持度的。
圖4給出了從項集{0,1,2,3}產(chǎn)生的所有關聯(lián)規(guī)則焚鹊，其中陰影區(qū)域給出的是低可信度的規(guī)則痕届。可以發(fā)現(xiàn)如果{0,1,2}?{3}是一條低可信度規(guī)則末患，那么所有其他以3作為后件（箭頭右部包含3）的規(guī)則均為低可信度的研叫。
可以觀察到，如果某條規(guī)則并不滿足最小可信度要求璧针，那么該規(guī)則的所有子集也不會滿足最小可信度要求嚷炉。以圖4為例，假設規(guī)則{0,1,2} ?{3}并不滿足最小可信度要求探橱，那么就知道任何左部為{0,1,2}子集的規(guī)則也不會滿足最小可信度要求申屹。可以利用關聯(lián)規(guī)則的上述性質(zhì)屬性來減少需要測試的規(guī)則數(shù)目隧膏，類似于Apriori算法求解頻繁項集哗讥。
總結
關聯(lián)分析是用于發(fā)現(xiàn)大數(shù)據(jù)集中元素間有趣關系的一個工具集，可以采用兩種方式來量化這些有趣的關系胞枕。第一種方式是使用頻繁項集杆煞，它會給出經(jīng)常在一起出現(xiàn)的元素項。第二種方式是關聯(lián)規(guī)則腐泻，每條關聯(lián)規(guī)則意味著元素項之間的“如果……那么”關系决乎。
發(fā)現(xiàn)元素項間不同的組合是個十分耗時的任務，不可避免需要大量昂貴的計算資源派桩，這就需要一些更智能的方法在合理的時間范圍內(nèi)找到頻繁項集构诚。能夠?qū)崿F(xiàn)這一目標的一個方法是Apriori算法，它使用Apriori原理來減少在數(shù)據(jù)庫上進行檢查的集合的數(shù)目铆惑。Apriori原理是說如果一個元素項是不頻繁的唤反，那么那些包含該元素的超集也是不頻繁的。Apriori算法從單元素項集開始鸭津，通過組合滿足最小支持度要求的項集來形成更大的集合彤侍。支持度用來度量一個集合在原始數(shù)據(jù)中出現(xiàn)的頻率。
關聯(lián)分析可以用在許多不同物品上逆趋。商店中的商品以及網(wǎng)站的訪問頁面是其中比較常見的例子盏阶。
每次增加頻繁項集的大小，Apriori算法都會重新掃描整個數(shù)據(jù)集闻书。當數(shù)據(jù)集很大時名斟，這會顯著降低頻繁項集發(fā)現(xiàn)的速度脑慧。FP-growth算法，和Apriori算法相比砰盐，該算法只需要對數(shù)據(jù)庫進行兩次遍歷闷袒，能夠顯著加快發(fā)現(xiàn)頻繁項集的速度。
