數(shù)據(jù)挖掘十大算法之Apriori詳解

有時候，人們會對機器學習與數(shù)據(jù)挖掘這兩個名詞感到困惑。如果你翻開一本冠以機器學習之名的教科書，再同時翻開一本名叫數(shù)據(jù)挖掘的教材，你會發(fā)現(xiàn)二者之間有相當多重合的內(nèi)容。比如機器學習中也會講到決策樹和支持向量機，而數(shù)據(jù)挖掘的書里也必然要在決策樹和支持向量機上花費相當?shù)钠?。可見二者確有相當大的重合面，但如果細研究起來，二者也的確是各自不同的領域。

大體上看，數(shù)據(jù)挖掘可以視為數(shù)據(jù)庫、機器學習和統(tǒng)計學三者的交叉。簡單來說，對數(shù)據(jù)挖掘而言，數(shù)據(jù)庫提供了數(shù)據(jù)管理技術，而機器學習和統(tǒng)計學則提供了數(shù)據(jù)分析技術。所以你可以認為數(shù)據(jù)挖掘包含了機器學習，或者說機器學習是數(shù)據(jù)挖掘的彈藥庫中一類相當龐大的彈藥集。既然是一類彈藥，其實也就是在說數(shù)據(jù)挖掘中肯定還有其他非機器學習范疇的技術存在。Apriori算法就屬于一種非機器學習的數(shù)據(jù)挖掘技術。

我們都知道數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。 而機器學習是以數(shù)據(jù)為基礎，設法構建或訓練出一個模型，進而利用這個模型來實現(xiàn)數(shù)據(jù)分析的一類技術。這個被訓練出來的機器學習模型當然也可以認為是我們從數(shù)據(jù)中挖掘出來的那些潛在的、有意義的信息和知識。在非機器學習的數(shù)據(jù)挖掘技術中，我們并不會去建立這樣一個模型，而是直接從原數(shù)據(jù)集入手，設法分析出隱匿在數(shù)據(jù)背后的某些信息或知識。在后續(xù)介紹Apriori算法時，你會相當明顯地感受到這一特點。

基本概念

許多商業(yè)企業(yè)在日復一日的運營中積聚了大量的交易數(shù)據(jù)。例如，超市的收銀臺每天都收集大量的顧客購物數(shù)據(jù)。例如，下表給出了一個這種數(shù)據(jù)集的例子，我們通常稱其為購物籃交易（market basket transaction)。表中每一行對應一個交易，包含一個唯一標識TID和特定顧客購買的商品集合。零售商對分析這些數(shù)據(jù)很感興趣，以便了解其顧客的購買行為。可以使用這種有價值的信息來支持各種商業(yè)中的實際應用，如市場促銷，庫存管理和顧客關系管理等等。

令I={i1,i2,?,id}是購物籃數(shù)據(jù)中所有項的集合，而T={t1,t2,?,tN}是所有交易的集合。包含0個或多個項的集合被稱為項集（itemset）。如果一個項集包含k個項，則稱它為 k-項集。顯然，每個交易ti包含的項集都是I的子集。

關聯(lián)規(guī)則是形如 X→Y 的蘊涵表達式，其中X和Y是不相交的項集，即 X∩Y=?。關聯(lián)規(guī)則的強度可以用它的支持度（support）和置信度（confidence）來度量。支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定Y在包含X的交易中出現(xiàn)的頻繁程度。支持度（s：Fraction of transactions that contain both X and Y）和置信度（c：How often items in Y appear in transactions that contain X）這兩種度量的形式定義如下：

例如考慮規(guī)則{Milk, Diaper}→{Beer}，則易得： 

Association Rule Mining Task：Given a set of transactions T, the goal of association rule mining is to find all rules having

support ≥ minsup threshold

confidence ≥ minconf threshold

因此，大多數(shù)關聯(lián)規(guī)則挖掘算法通常采用的一種策略是，將關聯(lián)規(guī)則挖掘任務分解為如下兩個主要的子任務。

頻繁項集產(chǎn)生：其目標是發(fā)現(xiàn)滿足最小支持度閾值的所有項集，這些項集稱作頻繁項集（frequent itemset）。

規(guī)則的產(chǎn)生：其目標是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則，這些規(guī)則稱作強規(guī)則（strong rule）。

通常，頻繁項集產(chǎn)生所需的計算開銷遠大于產(chǎn)生規(guī)則所需的計算開銷。

最容易想到、也最直接的進行關聯(lián)關系挖掘的方法或許就是暴力搜索（Brute-force）的方法：

List all possible association rules

Compute the support and confidence for each rule

Prune rules that fail the minsup and minconf thresholds

然而，由于Brute-force的計算量過大，所以采樣這種方法并不現(xiàn)實！格結構（Lattice structure）常被用來枚舉所有可能的項集。如下圖所示為I={a,b,c,d,e}的項集格。一般來說，排除空集后，一個包含k個項的數(shù)據(jù)集可能產(chǎn)生2k?1個頻繁項集。由于在實際應用中k的值可能非常大，需要探查的項集搜索空集可能是指數(shù)規(guī)模的。 

發(fā)現(xiàn)頻繁項集的一種原始方法是確定格結構中每個候選項集（candidate itemset）的支持度計 數(shù)。為了完成這一任務，必須將每個候選項集與每個交易進行比較，如下圖所示。如果候選項集包含在交易中，則候選項集的支持度計數(shù)增加。例如，由于項集{Bread, Milk}出現(xiàn)在事務1、4 和5中，其支持度計數(shù)將增加3次。這種方法的開銷可能非常大，因為它需要進行O(NMw)次比 較，其中N是交易數(shù)，M=2k?1是候選項集數(shù)，而w是交易的最大寬度（也就是交易中最大的項數(shù)）。
 

先驗原理

在上一小節(jié)的末尾，我們已經(jīng)看到Brute-force在實際中并不可取。我們必須設法降低產(chǎn)生頻繁項集的計算復雜度。此時我們可以利用支持度對候選項集進行剪枝，這也是Apriori所利用的第一條先驗原理：

Apriori定律1：如果一個集合是頻繁項集，則它的所有子集都是頻繁項集。

例如：假設一個集合{A,B}是頻繁項集，即A、B同時出現(xiàn)在一條記錄的次數(shù)大于等于最小支持度min_support，則它的子集{A},{B}出現(xiàn)次數(shù)必定大于等于min_support，即它的子集都是頻繁項集。

Apriori定律2：如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。

舉例：假設集合{A}不是頻繁項集，即A出現(xiàn)的次數(shù)小于 min_support，則它的任何超集如{A,B}出現(xiàn)的次數(shù)必定小于min_support，因此其超集必定也不是頻繁項集。

下圖表示當我們發(fā)現(xiàn){A,B}是非頻繁集時，就代表所有包含它的超級也是非頻繁的，即可以將它們都剪除。

Apriori算法與實例

R. Agrawal 和 R. Srikant于1994年在文獻【2】中提出了Apriori算法，該算法的描述如下：

Let k=1

Generate frequent itemsets of length k

Repeat until no new frequent itemsets are identified

Generate length (k+1) candidate itemsets from length k frequent itemsets

Prune candidate itemsets containing subsets of length k+1 that are infrequent

Count the support of each candidate by scanning the DB

Eliminate candidates that are infrequent, leaving only those that are frequent

或者在其他資料上更為常見的是下面這種形式化的描述（注意這跟前面的文字描述是一致的）： 

下面是一個具體的例子，最開始數(shù)據(jù)庫里有4條交易，{A、C、D}，{B、C、E}，{A、B、C、E}，{B、E}，使用min_support=2作為支持度閾值，最后我們篩選出來的頻繁集為{B、C、E}。

上述例子中，最值得我們從L2到C3的這一步。這其實就是在執(zhí)行偽代碼中第一個藍色框條所標注的地方：Ck+1=GenerateCandidates(Lk)，具體來說在Apriori算法中，它所使用的策略如下： 

可見生成策略由兩部分組成，首先是self-joining部分。例如，假設我們有一個L3={abc, abd, acd, ace, bcd}（注意這已經(jīng)是排好序的}。選擇兩個itemsets，它們滿足條件：前k-1個item都相同，但最后一個item不同，把它們組成一個新的Ck+1的項集c。如下圖所示，{abc}和{abd}組成{abcd}，{acd}和{ace}組成{acde}。生成策略的第二部分是pruning。對于一個位于Ck+1中的項集c，s是c的大小為k的子集，如果s不存在于Lk中，則將c從Ck+1中刪除。如下圖所示，因為{acde}的子集{cde}并不存在于L3中，所以我們將{acde}從C4中刪除。最后得到的C4，僅包含一個項集{abcd}。 數(shù)據(jù)分析師培訓

回到之前的例子，從L2到C3的這一步，我們就只能獲得{B、C、E}。以上便是Apriori算法的最核心思想。當然在具體實現(xiàn)的時候，如何Count Supports of Candidates也是需要考慮的問題，我們這里略去這部分內(nèi)容的討論