一、關(guān)聯(lián)分析介紹

商場的銷售過程，涉及很多機器學(xué)習(xí)的應(yīng)用，商品的陳列，購物卷的提供，用戶忠誠度等等，通過對這些大量數(shù)據(jù)的分析，可以幫組商店了解用戶的購物行為，進而對商品的定價、市場促銷、存貨管理等進行決策幫組。

從大規(guī)模數(shù)據(jù)集中尋找物品間的隱含關(guān)系被稱作關(guān)聯(lián)分析（association analysis）或者關(guān)聯(lián)規(guī)則學(xué)習(xí)（association rule learning）。這里的主要問題在于，尋找物品的不同組合是一項十分耗時的任務(wù)，所需的計算代價很高，蠻力搜索方法并不能解決這個問題，所以需要用更智能的方法在合理的時間范圍內(nèi)找到頻繁項集。

關(guān)聯(lián)分析是一種在大規(guī)模數(shù)據(jù)集中尋找有趣關(guān)系的任務(wù)。這些關(guān)系可以有兩種形式：頻繁項集或者關(guān)聯(lián)規(guī)則。頻繁項集（frequent item sets）是經(jīng)常出現(xiàn)在一塊的物品的集合，關(guān)聯(lián)規(guī)則（association rules）暗示兩種物品之間可能存在很強的關(guān)系。
下圖給出了某個雜貨店的交易清單。

頻繁項集是指那些經(jīng)常出現(xiàn)在一起的物品集合，上圖中的集合{葡萄酒，尿布, 豆奶}就是頻繁項集的一個例子。從下面的數(shù)據(jù)集中也可以找到諸如尿布?葡萄酒的關(guān)聯(lián)規(guī)則。這意味著如果有人買了尿布，那么他很可能也會買葡萄酒。使用頻繁項集和關(guān)聯(lián)規(guī)則，商家可以更好地理解他們的顧客。

當尋找頻繁項集時，什么樣的數(shù)據(jù)才是頻繁項集呢？頻繁（frequent）的定義是什么？

常用的頻繁項集的評估標準有支持度，置信度兩個。

• 支持度：數(shù)據(jù)集中，包含該項集的記錄出現(xiàn)的次數(shù)占總數(shù)據(jù)集的比重。
• 可信度：也稱為置信度，體現(xiàn)了一個數(shù)據(jù)出現(xiàn)后，另一個數(shù)據(jù)出現(xiàn)的概率，或者說數(shù)據(jù)的條件概率。針對一條關(guān)聯(lián)規(guī)則來定義的。

從上圖交易清單中可以得到，{豆奶}的支持度為4/5。而在5條交易記錄中有3條包含{豆奶，尿布}，因此{豆奶，尿布}的支持度為3/5。

針對一條諸如{尿布}?{葡萄酒}的這條關(guān)聯(lián)規(guī)則，這條規(guī)則的可信度被定義為“支持度({尿布, 葡萄酒})/支持度({尿布})”。由于{尿布, 葡萄酒}的支持度為3/5，尿布的支持度為4/5，所以“尿布?葡萄酒”的可信度為3/4=0.75。這意味著對于包含“尿布”的所有記錄，我們的規(guī)則對其中75%的記錄都適用。

因此，我們可以利用支持度和可信度是用來量化關(guān)聯(lián)分析是否成功。但是，當數(shù)據(jù)量非常大的時候，物品成千上萬時，按照上述方法生成一個物品所有可能組合的清單非常非常慢，統(tǒng)計每一種組合它出現(xiàn)的頻繁程度也很非常慢。這催生了關(guān)聯(lián)規(guī)則挖掘的算法Apriori，該原理會減少關(guān)聯(lián)規(guī)則學(xué)習(xí)時所需的計算量。

二、Apriori算法原理

一雜貨店有四種商品 0，1，2，3.這些商品的組合可能有一種，二種，三種，四種。我們的關(guān)注點：用戶購買一種或者多種商品，不關(guān)心具體買的商品的數(shù)量。
集合{0，1，2，3}中所有可能的項集組合如下圖

四種商品要遍歷15次，隨著物品數(shù)目的增加遍歷次數(shù)會急劇增加。對于包含N種商品的數(shù)據(jù)集一共有2^N-1種項集組合。

Apriori原理：

• 如果某個項集是頻繁的，那么它的所有子集也是頻繁的。
• 如果一個項集是非頻繁集，那么它的所有超集也是非頻繁的。

根據(jù)Apriori原理，假設(shè)集合{2，3}是非頻繁項集，則{0，2，3}，{1，2，3}，{0，1，2，3}也是非頻繁的，它們的支持度就不需要計算了。

Apriori算法采用迭代的方法，先搜索出候選1項集及對應(yīng)的支持度，剪枝去掉低于支持度的1項集，得到頻繁1項集。然后對剩下的頻繁1項集進行連接，得到候選的頻繁2項集，篩選去掉低于支持度的候選頻繁2項集，得到真正的頻繁二項集，以此類推，迭代下去，直到無法找到頻繁k+1項集為止，對應(yīng)的頻繁k項集的集合即為算法的輸出結(jié)果。

第i次的迭代過程包括掃描計算候選頻繁i項集的支持度，剪枝得到真正頻繁i項集和連接生成候選頻繁i+1項集三步。

上面的數(shù)據(jù)集D有4條記錄，分別是134，235，1235和25?，F(xiàn)在用Apriori算法來尋找頻繁k項集，最小支持度設(shè)置為50%。首先生成候選頻繁1項集，包括所有的5個數(shù)據(jù)并計算5個數(shù)據(jù)的支持度，計算完畢后進行剪枝，數(shù)據(jù)4由于支持度只有25%被剪掉。最終的頻繁1項集為1235，現(xiàn)在我們鏈接生成候選頻繁2項集，包括12，13，15，23，25，35共6組。此時第一輪迭代結(jié)束。

進入第二輪迭代，掃描數(shù)據(jù)集計算候選頻繁2項集的支持度，接著進行剪枝，由于12和15的支持度只有25%而被篩除，得到真正的頻繁2項集，包括13，23，25，35?，F(xiàn)在鏈接生成候選頻繁3項集，123， 125，135和235共4組，這部分圖中沒有畫出。通過計算候選頻繁3項集的支持度，發(fā)現(xiàn)123，125和135的支持度均為25%，因此接著被剪枝，最終得到的真正頻繁3項集為235一組。由于此時無法再進行數(shù)據(jù)連接，進而得到候選頻繁4項集，最終的結(jié)果即為頻繁3三項集235。

使用該原理就可以避免項集數(shù)目的指數(shù)增長，從而在合理時間內(nèi)計算出頻繁項集。

三、算法實現(xiàn)

算法偽代碼：

3.1 apriori算法輔助函數(shù)

輔助函數(shù)有creat_c1、scan_d

可以看出，支持度不小于0.5的項集被選中到L中作為頻繁項集，可以根據(jù)不同的需求設(shè)定最小支持度的值，從而得到想要的頻繁項集。

3.2 組織完整的Apriori發(fā)現(xiàn)頻繁項集

3.3 從頻繁項集中挖掘關(guān)聯(lián)規(guī)則

要找到關(guān)聯(lián)規(guī)則，先從一個頻繁集開始，我們想知道對于頻繁項集中的元素能否獲取其它內(nèi)容，即某個元素或者某個集合可能會推導(dǎo)出另一個元素。從表1 可以得到，如果有一個頻繁項集 {豆奶，萵苣}，那么就可能有一條關(guān)聯(lián)規(guī)則 "豆奶 --> 萵苣"，意味著如果有人購買了豆奶，那么在統(tǒng)計上他會購買萵苣的概率較大。但是這一條反過來并不一定成立。

一個頻繁項集可以產(chǎn)生許多可能的關(guān)聯(lián)規(guī)則，如果能在計算規(guī)則可信度之前就減少規(guī)則的數(shù)目，就會很好的提高計算效率。有一條規(guī)律就是：如果某條規(guī)則并不滿足最小可信度要求，那么該規(guī)則的所有子集也不會滿足最小可信度要求，例如下圖的解釋：

結(jié)果中給出三條規(guī)則：{1} ? {3}、{5} ? {2}及{2} ? {5}?？梢钥吹剑髢蓷l包含2和5的規(guī)則可以互換前件和后件，但是前一條包含1和3 的規(guī)則不行。下面降低可信度閾值之后看一下結(jié)果：

一旦降低可信度閾值，就可以獲得更多的規(guī)則。

四、示例：發(fā)現(xiàn)毒蘑菇的相似特征

首先看一下毒蘑菇的數(shù)據(jù)集：

第一個特征表示有毒或者可食用。如果某樣本有毒,則值為2。如果可食用,則值為1。下一個特征是蘑菇傘的形狀,有六種可能的值，分別用整數(shù)3-8來表示。

為了找到毒蘑菇中存在的公共特征，可以運行Apriori算法來尋找包含特征值為2的頻繁項集。

擴大范圍到3個：

接下來需要觀察一下這些特征，以便知道了解野蘑菇的那些方面。

五、小結(jié)

關(guān)聯(lián)分析是用于發(fā)現(xiàn)大數(shù)據(jù)集中元素間有趣關(guān)系的一個工具集，可以采用兩種方式來量化這些有趣的關(guān)系。第一種方式是使用頻繁項集,它會給出經(jīng)常在一起出現(xiàn)的元素項。第二種方式是關(guān)聯(lián)規(guī)則，每條關(guān)聯(lián)規(guī)則意味著元素項之間的“如果……那么”關(guān)系。

Apriori的方法簡化了計算量，在合理的時間范圍內(nèi)找到頻繁項集：Apriori原理是說如果一個元素項是不頻繁的，那么那些包含該元素的超集也是不頻繁的。

Apriori算法從單元素項集開始，通過組合滿足最小支持度要求的項集來形成更大的集合。支持度用來度量一個集合在原始數(shù)據(jù)中出現(xiàn)的頻率。

每次增加頻繁項集的大小，Apriori算法都會重新掃描整個數(shù)據(jù)集。當數(shù)據(jù)集很大時，這會顯著降低頻繁項集發(fā)現(xiàn)的速度。下一篇會介紹FP-growth算法，和Apriori算法相比，該算法只需要對數(shù)據(jù)庫進行兩次遍歷，能夠顯著加快發(fā)現(xiàn)繁項集的速度。