關聯規則演算法應用

① apriori演算法是什麼

Apriori演算法是第一個關聯規則挖掘演算法，也是最經典的演算法。它利用逐層搜索的迭代方法找出資料庫中項集的關系，以形成規則，其過程由連接（類矩陣運算）與剪枝（去掉那些沒必要的中間結果）組成。該演算法中項集的概念即為項的集合。包含K個項的集合為k項集。項集出現的頻率是包含項集的事務數，稱為項集的頻率。如果某項集滿足最小支持度，則稱它為頻繁項集。

演算法應用

隨著高校貧困生人數的不斷增加，學校管理部門資助工作難度也越加增大。針對這一現象，提出一種基於數據挖掘演算法的解決方法。將關聯規則的Apriori演算法應用到貧困助學體系中，並且針對經典Apriori挖掘演算法存在的不足進行改進，先將事務資料庫映射為一個布爾矩陣，用一種逐層遞增的思想來動態的分配內存進行存儲，再利用向量求＂與＂運算，尋找頻繁項集。

② 關聯演算法

關聯, 指的是關聯分析, 這里引用網路的定義.

通過關聯分析, 可以挖掘出"由於某些事件的發生而引起另外一些事件的發生"之類的規則, 比如說"麵包=>牛奶", 其中麵包被稱為規則的前項, 而牛奶則被稱為規則的後項.

常用於關聯分析的演算法有Apriori演算法, FP-growth演算法, Eclat演算法, 灰色關聯法等, 下面將著重介紹Apriori演算法.

在介紹Apriori演算法之前, 我們先來了解幾個概念:
1.事務: 一條交易記錄稱為一個事務
2.項: 交易中的每一個物品稱為一個項
3.項集: 包含0個或多個項的集合
4.支持度計數: 項集在所有事務中出現的次數.
5.支持度: 支持度計數除於總的事務數.
6.頻繁項集: 支持度大於等於某個閥值的項集.

關聯規則的挖掘通常分為兩步: 第一步, 找出所有的頻繁項集; 第二步, 由頻繁項集產沒判答生強關聯規則. 而Apriori演算法則是挖掘頻繁項集的基本演算法.

可以看到以上每個過程均需要掃描一次數據, 為了提高頻繁項集逐層迭代產生的效率, 需要利用一條重要性質, 其稱為先驗性質:

當然, 非頻繁項集的所有超集也一定是非頻繁的.

將先驗性質應用到Apriori演算法中就是將之枯慧前的過程分為兩大部分, 連接步和剪枝步.
連接步: 連接步的目的是產生候選項集.
剪枝步: 應用先驗性質對候選項集進行篩選, 將不滿足先驗性質的候選項集剔除, 再進而根據最小支持度找出頻繁項集, 這樣可以有效縮短計算量.

關聯分析的目標是找出強關聯規則, 因此這里的關聯規則是指強關聯規則, 我們把滿足最小支持度和最小置信度的規則稱為強關聯規則.
對於規則A=>沖敏B, 置信度的計算公式就是項集{A, B}的支持度計數除於項集{A}的支持度計數.

優點: 簡單, 易理解, 對數據要求低
缺點: 容易產生過多的候選項集, I/O負載大.

③ 關聯規則-演算法原理與案例

✓ 關聯規則（Association Rules）反映一個事務與其他事務之間的相
互依存性和關聯性。如果兩個或者多個事務之間存在一定的關聯關
系，那麼，其中一個事務就能夠通過其他事務預測到。
✓ 關聯規則是無監督的機器學習方法，用於知識發現，而非預測
✓ 關聯規則的學習器（learner）無需事先對訓練數據進行打標簽，因
為無監督學習沒有訓練這個步驟。缺點是很難對關聯規則學習器進
行模型評估，一般都可以通過業務經驗觀測結果是否合理

關聯規則之前，需要理解一些基本概念。
下圖數據集中，每一組數據ti表示不同的顧客一次在商場購買的商品
的集合，以該數據為例來說明關聯規則相關概念。

圖片顯示, 表中存儲著二維結構的記錄集，記為D，簡稱事務集D，含事務的個數稱為|D|。那麼圖片中從t1,t2,......直到t7含7個事務，|D|=7。

設I={i1,i2,…im}是m個不同項目的集合，每個ik（k=1,2,…m）稱為一個項目(Item),I是所有項目(Item)的集合，稱為所有項集(Items)。圖片中所有項集I={牛肉，雞肉，牛奶，乳酪，靴子，衣服}，其中，「牛 肉」、「雞肉」等均為項目。

在事務數據集里的一筆記錄，記為事務T，{牛肉、雞肉、牛奶}便是一個事務，每個事務T（Transaction）是所有項集I的一個子集。

項目的集合簡稱為項集（Itemset），其元素個數為項集的長度，長度為k的項集稱為k-項集（k-Itemset）。
如{牛肉}、{雞肉}均為1-項集，{牛肉、乳酪}為2-項集，{雞肉、衣 服、牛奶}為3-項集。

重點概念5-項集的支持度：項集支持度用於描述X的重要性，對於項集X，count為事務集D中包含X的事務的數量，項集X的支持度就是項集X出現的概率。

項集的支持度就是該項集出現的次數除以總的記錄數，例如，上述的7個事務中，{牛肉、雞肉}出現的次數是3次，支持度就是3/7 。

我們在發現規則的時候，希望關注頻次高的項集，發現關聯規則要求項集必須滿足的最小支持閾值，稱為項集的最小支持度（Minimum Support），記為supmin。支持度大於或等於最小支持度的項集稱為頻繁項集，簡稱頻繁集，反之則稱為非頻繁集。支持度在這個演算法中通常是人為規定的參數。

規則R的支持度是交易集中同時包含X和Y的交易數與所有交易數之比；

支持度計算在事務集中，既有A又有B的概率。
例：在7條記錄中，既有牛肉又有雞肉的記錄有3條，則 R:牛肉 雞肉的支持度為3/7，即 ，表示在所有顧客當中有3/7同時購買了牛肉和雞肉，其反映了同時購買牛肉和雞肉的顧客在所有顧客當中的覆蓋范圍。

規則R的置信度是指包含X和Y的交易數與包含X的交易數之比。

規則的置信度的意義在於項集{X，Y}同時出現的次數占項集{X}出現次數的比例，即發生X的條件下，又發生Y的概率。

關聯規則的最小支持度也就是衡量頻繁集的最小支持度（Minimum
Support），記為supmin，它用於衡量規則需要滿足的最低重要性。
Minimum Support是一個閾值參數，必須在處理關聯規則之前指定該
參數。該參數表示用戶對某些項集和規則感興趣，這些規則表示數
據集的最低支持度。它是用於對項集進行限制，而不是對規則進行
限制。

✓ 如果關聯規則R: A→B滿足Support(A→B )>=supmin 且
Confidence( A→B )>=confmin,則稱關聯規則R: 為強關聯規則，否
則稱關聯規則為弱關聯規則;
✓ 在挖掘關聯規則時，產生的關聯規則要經過supmin和confmin的衡量，
篩選出來的強關聯規則才能用於指導商家的決策;

引入例題來計算這個概念，例：在所分析的10000個事務中，6000個事務包含計算機游戲，7500包含游戲機游戲，4000個事務同時包含兩者。
下面我們計算：關聯規則（計算機游戲 → 游戲機游戲）支持度=4000/10000=0.4，置信度=4000/6000=0.67，但其實這個關聯規則是一個誤導。

在用戶購買了計算機游戲後有（4000/6000）=0.667的概率去購買游戲機游戲，而在沒有任何前提條件下，用戶反而有（7500/10000） =0.75的概率去購買游戲機游戲，也就是說設置了購買計算機游戲這樣的條件反而會降低用戶去購買游戲機游戲的概率，所以計算機游戲和游戲機游戲是相斥的。

此時需要引入提升度的概念。

如果兩個條件相互獨立，則P(XY)=P(X)· P(Y),即提升度為1；如果小於1，說明使用這條規則來進行推薦，還不如不推薦（推薦無效）；
一般在數據挖掘中當提升度大於3時，我們才承認挖掘出的關聯規則是有價值的。

上述例子中，假設購買計算機游戲為X，購買游戲機游戲為Y，則有提升度數=0.667/0.75<1

這表明這樣的推薦是無效的，提升度小於1，還不如不推薦。

第一步，生成候選項集，然後根據指定的最小支持度，過濾掉非頻繁項集，生成頻繁項集。
該步驟需要多次遍歷：第一次遍歷，對所有單項的支持度進行計數並確定頻繁項；在後續的每次遍歷中，利用上一次遍歷所得頻繁項集作為種子項集，產生新的頻繁項集-候選項集，並對候選項集的支持度進行計數，在本次遍歷結束時統計滿足最小支持度的候選項集，本次遍歷對應的頻繁項集就算是確定了，這些頻繁項集又成為下一次遍歷的種子；重復此遍歷過程，直到再不能發現新的頻繁項集。

第二步，找出第一步的頻繁項集中的規則，然後根據指定的最小置信度，過濾掉弱規則。第一步的計算量比第二步的計算量大。

步驟1：
✓ 生成候選1-項集C1,計算支持度
✓ 根據最小支持度，生成頻繁1-項集L1

步驟2：
✓ 生成候選2-項集C2,計算支持度
✓ 根據最小支持度，生成頻繁2-項集L2

✓ 生成關聯規則時，最簡單的方法就是對於每個頻繁項集，列出其所有非空
真子集，任取其中兩個分別作為LHS和RHS，形成關聯規則，並計算每條關
聯規則的置信度，刪除弱規則
✓ 上例中 ， 對於頻繁項集 {B,C,E} ， 它的非空子集有 {B},{C},{E},
{B,C},{B,E},{C,E}。據此獲得的關聯規則及其置信度，置信度>=50%(最小
置信度)，都是強關聯規則

✓ Apriori原理可以幫助減少計算量
✓ Apriori原理：某個項集是頻繁的，那麼它的所有子集也是頻繁的；
更常用的是它的逆否命題，即如果一個項集是非頻繁的，那麼它的
所有超集也是非頻繁的（稱為項集的反單調性，向下閉合性）

已知陰影項集{2,3}是非頻繁的。利用Apriori原理，我們知道項集{0,2,3}， {1,2,3}以及{0,1,2,3}也是非頻繁的。也就是說，一旦計算出了{2,3}的支持 度 ， 知 道 它 是 非 頻 繁 的 ， 就 可 以 緊 接 著 排 除 {0,2,3} ， {1,2,3} 和 {0,1,2,3}。

✓ 反單調性能迅速剪枝，提高搜索頻繁項集的處理效率

在商品列表中找出頻繁項集,構建商品列表。

創建模型，傳入數據，輸出的support就是支持度。

該段輸出結果如下

接下來可以篩選支持度大於某特定值的二項集

輸出結果

④ 關聯規則演算法(The Apriori algorithm)

        關聯規則的目的在於在一個數據集中找出項之間的關系，也稱之為購物籃分析 (market basket analysis)。例如，購買鞋的顧客，有10%的可能也會買襪子，60%的買麵包的顧客，也會買牛奶。這其中最有名的例子就是"尿布和啤酒"的故事了。

        本篇的Apriori演算法主要是基於頻繁集的關聯分析。其主要目的就是為了尋找強關聯規則。

        要理解頻繁集、強關聯規則，要先藉助下面的一個情境，來介紹幾個重要概念。

        下表是一些購買記錄：

將購買記錄整理，可得到下表，橫欄和縱欄的數字表示同時購買這兩種商品的交易條數。如購買有Orange的交易數為4，而同時購買Orange和Coke的交易數為2。

        置信度，表示這條規則有多大程度上值得可信。

        設條件的項的集合為A,結果的集合為B。置信度計算在A中，同時也含有B的概率。即Confidence(A->B)=P(B|A)。例 如計算"如果Orange則Coke"的置信度。由於在含有Orange的4條交易中，僅有2條交易含有Coke。其置信度為0.5。

        支持度，計算在所有的交易集中，既有A又有B的概率。

        例如在5條記錄中，既有Orange又有Coke的記錄有2條。則此條規則的支持度為2/5=0.4。現在這條規則可表述為，如果一個顧客購買了Orange,則有50%的可能購買Coke。而這樣的情況（即買了Orange會再買Coke）會有40%的可能發生。

支持度大於預先定好的最小支持度的項集。

       關聯規則：令項集I={i1,i2,...in}，且有一個數據集合D，它其中的每一條記錄T，都是I的子集。那麼關聯規則是形如A->B的表達式，A、B均為I的子集，且A與B的交集為空。這條關聯規則的支持度：胡頌support = P(A並B)。這條關聯規則的置信度：confidence = support(A並B）/suport(A)。

       強關聯規則：如果存在一條關聯規則，它的支持度和置信度都大於預先定義好的最小支持度與置信度，我們就稱它為強關聯規則。

下面用一個例子說明演算法的過程：

項目集合 I={1，2，3，4，5};

事務集 T：

設定最小支持度（minsup）=3/7，最小置信度（misconf）=5/7。

假設：n-頻繁項目集為包含n個元素的項目集，例如1-頻繁項目集為包含1個元素的項目集

則這里，1-頻繁項目集有：{1}，{2}，{3}，{4}，{5}

生成2-頻繁項目集的過程如下：

       褲燃鄭 首先列出所有可能的2-項目集，如下：

        {1，2}，{1，3}，{1，4}，{1，5}

        {2，3}，{2，4}，{2，5}

        {3，4}，{3，5}

        {4，5}

        計算它們的支持度，發現只有{1，2}，{1，3}，{1，4}，{2，3}，{2，4}，{2，5}的支持度    滿足要求，因此求得2-頻繁項目集：

        {1，2}，{1，3}，{1，4}，{2，3}，{2，4}

生成3-頻繁項目集：

對於現有的2-頻繁項目集，兩兩取並集，並段純確保第三個二元組也在2-頻繁項目集內，把得到的所有3-項目集分別計算支持度，剔除不滿足最小支持度的項目集；

例如，

{1，2}，{1，3}的並集得到{1，2，3}；

{1，2}，{1，4}的並集得到{1，2，4}；

{1，3}，{1，4}的並集得到{1，3，4}；

{2，3}，{2，4}的並集得到{2，3，4}；

但是由於{1，3，4}的子集{3，4}不在2-頻繁項目集中，所以需要把{1，3，4}剔除掉。{2，3，4} 同理剔除。

然後再來計算{1，2，3}和{1，2，4}的支持度，發現{1，2，3}的支持度為3/7 ，{1，2，4}的支持度為2/7，所以需要把{1，2，4}剔除。因此得到3-頻繁項目集：{1，2，3}。

重復上面步驟繼續尋找n-頻繁項目集，直到不能發現更大的頻繁項目集。所以，到此，頻繁項目集生成過程結束。

這里只說明3-頻繁項目集生成關聯規則的過程，即以集合{1，2，3}為例：

回顧事物集，先生成1-後件的關聯規則：

（1，2）—>3，置信度=3/4（出現（1，2）的記錄共4條，其中有3條包含3，所以3/4）；

（1，3）—>2，置信度=3/5；

（2，3）—>1，置信度=3/3；

第二條置信度<5/7，未達到最小置信度，所以剔除掉。所以對於3-頻繁項目集生成的強關聯規則為：（1，2）—>3和（2，3）—>1。

這表示，如果1、2出現了，則極有可能出現3；2、3出現，則極有可能有1。

http://www.cnblogs.com/junyuhuang/p/5572364.html

⑤ 關聯規則分析怎麼做

關聯規則是反映一個事物與其他事物之間的相互依存性和關聯性，常用於實體商店或在線電商的推薦系統：通過對顧客的購買記錄資料庫進行關聯規則挖掘，最終目的是發現顧客群體的購買習慣的內在共性，例如購買產品A的同時也連帶購買產品B的概率，根據挖掘結果，調整貨架的布局陳列、設計促銷組合方案，實現銷量的提升，最經典的應用案例莫過於<啤酒和尿布>。

關聯規則分析中的關鍵概念包括：支持度(Support)、置信度(Confidence)與提升度(Lift)。首先，我們簡單溫故下這3個關鍵指標：

支持度 (Support)
支持度是兩件商品（A∩B）在總銷售筆數(N)中出現的概率，即A與B同時被購買的概率。

公式：

例子說明：
比如某超市2016年有100w筆銷售，顧客購買可樂又購買薯片有20w筆，顧客購買可樂又購買麵包有10w筆，那可樂和薯片的關聯規則的支持度是20%，可樂和麵包的支持度是10%。

置信度 (Confidence)
置信度是購買A後再購買B的條件概率。簡單來說就是交集部分C在A中比例，如果比例大說明購買A的客戶很大期望會購買B商品。

公式：

例子說明：
某超市2016年可樂購買次數40w筆，購買可樂又購買了薯片是30w筆，顧客購買可樂又購買麵包有10w筆，則購買可樂又會購買薯片的置信度是75%，購買可樂又購買麵包的置信度是25%，這說明買可樂也會買薯片的關聯性比麵包強，營銷上可以做一些組合策略銷售。

提升度 (Lift)
提升度表示先購買A對購買B的概率的提升作用，用來判斷規則是否有實際價值，即使用規則後商品在購物車中出現的次數是否高於商品單獨出現在購物車中的頻率。如果大於1說明規則有效，小於1則無效。

公式：

例子說明：
可樂和薯片的關聯規則的支持度是20%，購買可樂的支持度是3%，購買薯片的支持度是5%，則提升度是1.33>1, A-B規則對於商品B有提升效果。

理論很簡單，真正實踐起來卻會遇到種種困難，印證了那句"數據分析師的50%～80%的時間都花在了處理數據上」，例如一般POS明細是以下圖表形式展現：

要計算支持度(Support)、置信度(Confidence)與提升度(Lift)，首先需要知道Freq(A∩B)、Freq(A)、Freq(B)和總筆數數值，那麼需要對商品進行排列組合。

所以，我們希望轉換成下表形式，如銷售ID=000001， 4種商品的兩兩組合（種）：

若一個收銀小票（銷售ID）有30種商品，則組合數達到:

而可視化層級上還需要展現集團下每個分公司、每個城市、每個門店、月度、季度或者年度時間的關聯規則分析，如果用傳統的工具來實現上述分析無異於大海撈針。

下面我們就來看看在BDP中如何實現Apriori演算法，實現關聯規則分析：

商品兩兩組合的初步想法是通過量化的思想對商品進行編碼，比方說可按照增序（從1開始），算出每筆銷售單最大值，求出兩者差值得到一組數組，通過數組行轉列形式實現2種商品兩兩組合。

圖：銷售單2種商品兩兩組合邏輯圖

操作①：

【工作表】-【創建合表】-【SQL創建】

圖：商品量化

上圖轉換成日期的形式，主要目的是為下一步的數組轉列做准備，為配合explode（）函數使用。其中需要說明的是上圖[日期]欄位是自定義日期，可以更改成任意日期，沒有實際日期意義。

圖：商品組合數效果

上圖主要使用的關鍵函數是FILL_DATES（[日期1],[日期2]），Explode（）。組合效果初顯現，只是缺另一個商品名，然後把[下一日期]欄位通過LEFT JOIN 關聯出商品B的名稱。

操作②：

【工作表】-【創建合表】-【多表關聯】 用於創建表關聯 包括（LEFT/INNER/ FULL JOIN）

圖：商品組合數實現

從上圖可以看到A商品和B商品兩兩組合邏輯已完成，在當前表基礎上我們已經可以去做連帶分析內容。

在這里，求Freq(A)和Freq(B)和總筆數數值就不祥述了，思想大致是求出所有銷售商品的A 和B商品的頻次，通過合表關聯，整合到一張大表。

操作③：

【工作表】-【創建合表】-【追加合並】合並訂單總數 ，A商品訂單數，B商品訂單數和A∩B商品連帶筆數

圖：追加合並邏輯實現

追加合並可以把相同欄位商品合並在一起，方便計算三個指標（支持度、置信度、提升度）有利於可視化展現。

操作④：

可視化展現：【BDP】-【儀表盤】

圖：儀表盤全局展示

註：為了更好體現可視化效果，這部分的可視化展示成果並非使用上述的測試數據或某個企業數據。

製作三個圖表進行購物籃分析：

圖： TOP 20商品連帶次數

上圖反映季度連帶最高頻次商品，高聯帶商品意味著對客戶吸引力大商品粘性強，同時也可以查看不同分公司的TOP20連帶情況。根據結果我們可以合理設計促銷策略，例如買2送1等。

圖：商品組合指標

置信度高說明商品連帶緊密，說明客戶連帶意願強，同時關注支持度，支持度高說明是需求量大，如果支持度低，置信度高其實對市場作用是有限小的。

圖：購物籃分析詳情

通過單價，支持度，置信度，提升度綜合指標來看待商品組合，發現高價值關聯商品，有助於提升客單價，同時也需要考慮提升度，提升度小於1，提升效果有限，可以把精力花在提升度大於1的商品組合。

同樣地，我們是否可以實現三種商品的組合呢？答案是顯然的，只要我們深入理解以上過程，三種商品關聯也是可以在BDP中實現的。 作者 熊輝 本文轉載自 BDP商業數據平台，轉載需授權