Learn R | Association Rules of Data Mining（一）

前言

在數據挖掘與機器學習中，關聯規則（Association Rules）是一種較為常用的無監督學習演算法，與我們前面所學習的分類、聚類等演算法的不同的是，這一類演算法的主要目的在於——發掘數據內在結構特徵（即變數）之間的關聯性。

簡單一點來說，就是在大規模的數據集中尋找一些有意義有價值的關係。有了這些關係，一方面，可以幫助我們拓寬對數據及其特徵的理解；另一方面，則可以實現推薦系統的構建與應用（例如購物籃分析等）。

在對關聯規則有了基本的認識後，我們對其進行進一步的細分，以日常生活中的關聯性舉例，在逛超市的顧客中，購買麵包的人很大程度上會購買牛奶，這一類的關聯性被稱為簡單關聯規則；再例如，購買汽車遮陽板的很多顧客會在近期內購買零度玻璃水，這樣的事例不僅反映了事物間的關聯關係， 而且還具有時間上的先後順序，因此這一類的關聯性則被稱為序列關聯規則。

廣義上的關聯規則包含了簡單關聯和序列關聯，接下來我們分別對這兩塊知識進行深入學習。

一、簡單關聯規則初探

首先我們需要明確關聯分析中的一些基礎概念：

• 事務：指關聯分析中的分析對象，我們可以把它理解成為一種寬泛行為（例如顧客的一次超市購買行為，電腦使用者的一次網頁瀏覽行為等都可以稱之為事務），由項目集合與事務標識（TID）組成。
• 項集：即事務中的一組項目的集合，單個的項目可以是一種商品、一個網頁鏈接等。假設為項集，為項目全體且，那麼項集。進一步的，如果中包含個項目，則稱該項集為項集。

明確了基礎概念後，接下來學習關聯規則的一般表現形式，其中：

• 和分別為規則的前項和後項，前項為項目或項集，後項表示某種結論或事實

• 表示規則支持度為，表示規則置信度為

看到這裡大家可能會有疑惑，直接得到關聯規則不就可以了嗎？為什麼要在結論中加入支持度和置信度呢？這就涉及到關聯分析中非常重要的一塊內容——有效性的判別。

二、簡單關聯規則的有效性

實際上，在數據中使用關聯分析進行探索時，我們可以找出很多關聯規則，但並非所有的關聯規則都是有效的，有的可能令人信服的程度並不高，也有的可能適用範圍很有限，帶有這些特徵的所謂的「關聯規則」，我們則稱之為不具有「有效性」。

判斷一條關聯規則是否有效，需要用到以下兩大測度指標，即規則置信度與規則支持度。

1. 規則置信度（Confidence）

置信度是對簡單關聯規則準確度的測量，定義為包含項目的事務中同時也包含項目的概率，數學表述為：

置信度的本質就是我們所學過的條件概率，置信度越高，則說明出現則出現的可能性也就越高。假設在電腦殺毒軟體的關聯規則中，置信度，表示購買電腦的顧客中有的顧客也購買了殺毒軟體。

2. 規則支持度（Support）

支持度測量了簡單關聯規則應用的普適性，定義為項目與項目同時出現的概率，數學表述為：

假設某天共有100個顧客到商場購買物品，其中有10個顧客同時購買了電腦和殺毒軟體，那麼上述關聯規則的支持度就為10％。同樣，支持度越高，表明某一關聯規則的適用性越大。

一個有效的簡單關聯規則，勢必同時具有較高的置信度與支持度。因為，如果支持度較高而置信度較低，則證明規則的可信度差；而相反，如果支持度較低而置信度較高，則說明規則的應用範圍較小。

舉例來講，假設在1000個顧客購買行為的事務中，只有1個顧客購買了燒烤爐，同時也只有他購買了碳，雖然規則「燒烤爐碳」的置信度很高，為，但其支持度僅有，說明這條規則缺乏普遍性，應用價值不高。

所以，一個有效的關聯規則，必須具有較高的置信度與支持度。那麼在實際應用中，我們就需要給定最小的置信度與支持度，只有同時大於和的規則，我們才可以將其定義為是「有效」的。

三、簡單關聯規則的實用性

在對關聯規則的有效性有一個基本的掌握後，我們在此基礎上進行進一步的探討——關聯規則的實用性。

關聯規則的實用性主要體現在以下兩個方面：

• 第一，是否具有實際意義。例如「懷孕女性」的關聯規則就沒有實用價值。

• 第二，是否具有指導意義，即幫助我們在現有的基礎上做出有價值的優化。

對第二點進一步展開說明，假設「牛奶男性顧客」在和均為時是一條有效規則時，如果進一步計算髮現顧客中男性的比例也為，也就是說購買牛奶的男性顧客等於所有顧客中的男性比例，那麼這條規則就是一條前後項無關的隨機性關聯，因此它就沒有有意義的指導信息，不具有實用性。

如何衡量關聯規則具有實用性呢？這裡我們就需要藉助規則的提升度了。

規則提升度（Lift）定義為：置信度與後項支持度之比，數學表述為：

提升度反映了項目的出現對項目出現的影響程度。從統計角度來看，如果的出現對項的出現沒有影響，即與相互獨立的話，，此時規則提升度為1。所以，具有實用性的關聯規則應該是提升度大於1的規則，即的出現對的出現有促進作用。同樣，提升度越大，證明規則實用性越強。

這樣，我們就闡述清楚了關聯規則的一些基本假定與判別標準，當數據集較小時，關聯規則的使用較為簡單，但如果數據集很大的話，如何在這海量的數據中快速找出關聯規則呢？這就引出了我們進一步要學習的內容——簡單關聯規則下的Apriori演算法。

四、Apriori演算法的基本原理

在數據量龐大的前提下，由於簡單搜索可能產生大量無效關聯規則，並導致計算效率低下。出於克服這些弊端的目的，Apriori演算法應運而生，該演算法自1996年提出後，經過不斷的完善和發展，已成為簡單關聯分析中的核心演算法。

Aprioir演算法主要包含以下兩個方面：

• 第一，搜索頻繁項集；
• 第二，依據頻繁項集產生關聯規則。

從這兩步中可以看到，頻繁項集是演算法的核心內容。接下來，我們將以頻繁項集為立足點，進行Apriori演算法的深入學習。

1. 頻繁項集的相關定義

頻繁項集非常好理解，他是指大於等於最小支持度的項集。其中，若頻繁項集中包含1個項目，則稱為頻繁1-項集，記為；若包含個項目，則稱為頻繁項集，記為。

頻繁項集具有以下兩個性質，這兩條性質將應用在我們後面頻繁項集及其關聯規則的尋找中：

• 第一，頻繁項集的子集必為頻繁項集（假設項集是頻繁項集，那麼和也為頻繁項集）；
• 第二，非頻繁項集的超集一定也是非頻繁的（假設項集不是頻繁項集，那麼和也不是頻繁項集）

進一步，當某一個的所有超集都不是頻繁項集時，我們就可以稱此為最大頻繁k-項集，確定它的目的就在於使之後得到的關聯規則具有較高的普適性。

2. 尋找頻繁項集

對頻繁項集的尋找，是Apriori演算法提高尋找關聯規則效率的關鍵。它採用迭代的方式逐層尋找下層的超集，並在超集中發現頻繁項集。經過層層迭代，直到最頂層得到最大頻繁項集為止。在每一輪的迭代中都包含以下兩個步驟：

• 產生候選集，它是有可能成為頻繁項集的項目集合；
• 修剪候選集，即基於計算相應的支持度，並依據最小支持度對候選集進行刪減，得到新的候選集，如此循環迭代，直到無法產生候選項集為止，這樣最後一輪所得的到的頻繁項集就是Apriori所要求的最大頻繁項集。

接下來我們以一個實際的小例子幫助理解：

假設我們指定的最小支持閥度為0.5（計數）

• 在第一輪迭代過程中，由於D的支持度小於0.5（0.25），所以沒有進入頻繁項集，其餘均進入頻繁項集，定義為。

• 在第二輪迭代中，候選集是中所有項目的組合，計算各項目支持度，淘汰與，其餘進入頻繁項集，定義為。

• 在第三輪迭代中，只有進入候選項集，而其餘都沒有進入，之所以會這樣，是因為這裡使用到了前面所提到的頻繁項集的第二個性質：非頻繁項集的超集一定也是非頻繁的。所以，包含與的超集是不可能成為頻繁項集的。

由於不能繼續構成候選集，所以迭代結束，得到的最大頻繁項集為。

3. 在最大頻繁項集的基礎上產生簡單關聯規則

得到最大頻繁項集並不是最終的目的。還記得嗎？之前在判斷關聯規則的有效性時，我們學習了置信度與支持度兩個指標。其中，支持度已經在尋找最大頻繁項集的過程中發揮了作用，那麼，在接下來關聯規則的產生上，就輪到置信度大顯身手了。

首先，每個頻繁項集都需要計算所有非空子集的置信度，公式為：，如果所求得的大於我們自行指定的，則生成相應的關聯規則

在上面的例子中，的非空子集就包括，舉例來說，根據公式可計算得到：

其餘置信度依次為：，，，，

如果我們設定的話，只有和可以入圍，如果設定為，那麼六條規則就都是有效規則了。置信度的選取和支持度一樣，只有結合具體應用情況，演算法才能給到我們切合實際的結論。

關聯規則簡介及Apriori演算法簡單介紹到這裡，下一文將對Apriori演算法進行一些簡單的補充，並著重學習Apriori演算法的R實現。

未完待續

References：

1. 數據挖掘：概念與技術 (豆瓣)

2. R語言數據挖掘（豆瓣）

3. 關聯規則 - xsdxs的博客 - 博客頻道 - CSDN.NET

4. Apriori | 數據挖掘十大演算法詳解

5. 關聯規則 - xiaolingfeng12345的專欄 - 博客頻道 - CSDN.NET
6. R語言與數據挖掘：最佳實踐和經典案例 (豆瓣)

推薦閱讀：