目錄

1 關聯規則挖掘概念

2 關聯規則基本模型

2.1 基本概念

2.2 關聯規則的挖掘步驟

3 Apriori算法

3.1 介紹?

3.2 實現步驟

3.3 偽代碼

---

1 關聯規則挖掘概念

一、定義

關聯規則反映一個事物與其它事物之間的依賴和相互關聯性。

經典例子為購物籃分析，通過分析購物籃數據來分析顧客經常同時購買哪些商品（購買習慣）。這是BI(Business Intelligence)的一項應用。

二、目的

關聯規則挖掘的目的是從數據中發現有趣的規律。

“有趣”是指發現的規律是有意義的、能夠指導實踐的。

上述購物籃分析有一個舉爛了的例子：早期沃爾瑪超市的一次購物籃分析發現，啤酒和尿布位于榜單的第三位，即部分顧客經常同時購買啤酒和尿布。其原因竟然是，下班回家的丈夫經常會在順路幫妻子購買尿布的同時，買些喜歡的啤酒犒勞自己。

聽說之后沃爾瑪超市立刻就推出了啤酒和尿布捆綁消費的優惠活動，大獲好評。

總之，沃爾瑪超市從消費數據中提取的這項規律顯然是有現實意義的，是“有趣”的。

另外還可以做以下關聯思考：

1. 購買了筆記本電腦后，下一步會買什么？

當然是鼠標和鍵盤了，又或者是一個相匹配的電腦包/保護套。

因此，很多商家都推出了套餐購買方案，買電腦，送相關套裝。

2. 我們如何對文檔進行分類？

可以嘗試提取出文檔的關鍵詞，比較文檔之間關鍵詞的關聯關系，再通過聚類分析等方法進行分類。

我們還可以從購物籃分析的例子中得到引申。在網購中，也悄悄進行著購物籃分析，并為您推薦相關商品。

另外還有視頻網站、新聞網站等等，通過分析您的行為與其它用戶行為的關聯性，進行相關推薦。

2 關聯規則基本模型

2.1 基本概念

先用通俗的語言進行介紹，不甚準確，僅幫助理解。

現在開始進行購物籃分析，分析A，D商品被同時購買的可能性。

裝著A，D商品的購物籃稱為項集，因為現在購物籃中只有兩件商品，故叫做“2項集”。

假設我們擁有無限多的購物籃，且顧客結算后都保留購物籃的拷貝，那么將所有的購物籃放在一起做統計（當然你的也是），發現：

同時裝著A，D商品的購物籃占總購物籃數的50%，裝有A商品的購物籃有60%的可能也裝有D商品！

可你還記得做這該死的統計之前，你曾和朋友打賭，只要這兩項指標超過50%，就承認這件事是絕對有趣的……

很遺憾，你必須苦著臉承認了。

---

咳咳。

現在對以上出現的概念給出系統的介紹：

設?I={i1, ..., im}?為所有項目的集合，D為數據庫，事務T是一個項目子集，每一個事務具有唯一的事務標識TID。

頻繁項集：頻繁出現在數據集中的模式。上述沃爾瑪的例子中，頻繁出現在交易數據集中的“啤酒”和“尿布”的集合就是頻繁項集。

項集：項的集合稱為項集，設為集合A。包含k個項的項集稱為k項集。

項集的出現頻度（相對支持度）：包含項集的事務數，簡稱為項集的頻度、支持度計數或計數（下稱出現頻度）。

規則興趣度的兩種度量：支持度，置信度。

• 支持度（相對支持度）：項集A在事務數據庫中出現的次數占D中總事務的百分比。即A中所有元素在D中同時出現的概率。有：

support(A蘊含D) = P(A ∪ D)

反映規則的有用性：k項集中元素的關聯性。

• 置信度（可信度）：A出現的條件下，D出現的概率，即

confidence(A蘊含D) = P( D | A )

反映規則的有趣性：結論的可靠性。

• 最小支持闕值&最小置信度闕值：由專家確定。當支持度和置信度分別滿足最小闕值時，關聯規則被認為是有趣的。

若項集I的相對支持度滿足預定義的最小支持度闕值，則I是頻繁項集(frequent itemset)；若支持度和置信度同時滿足最小支持度闕值和最小置信度闕值，則規則被稱為強規則。

▲ 其中需要特別注意的是，支持度沒有方向性，而置信度是有方向的。

現在將數據集整理如下，令min_sup = 50%，min_conf = 50%：

則有：

support(A蘊含D) = P(A∪D) = 3/5 = 60%

confidence(A蘊含D) = P(D | A) = 100%

confidence(D蘊含A) = P(A |?D) = 3/4 = 75%

則關聯規則Association rules：

(1) A → D （60%,100%）

(2) D → A?（60%,75%）

故，可認為A，D之間的關聯規則是有用且可信的。

其中，(1)式表示商品A和商品D同時購買的可能性為60%，而購買A的顧客中所有的人都會購買商品D；

(2)式表示商品A和商品D同時購買的可能性為60%，而購買D商品的顧客中有75%的人會購買商品A。

(1)(2)兩式應證了支持度的無方向性以及置信度的方向性。

舉一個例子加深理解：

買電腦的時候經常會推薦購買包含電腦包的套餐，但購買電腦包時不見得會推薦你買一個電腦吧？

2.2 關聯規則的挖掘步驟

找出所有的頻繁項集：根據定義，這些項集的每一個頻繁出現的次數至少與預定義的最小出現頻度min_sup一樣。

由頻繁項集產生強關聯規則：根據定義，這些規則必須滿足最小支持度和最小置信度。

3 Apriori算法

3.1 介紹?

Apriori算法是一種發現頻繁項集的基本算法，是Agrawal和R.Srikant于1994年提出的，為布爾關聯規則挖掘頻繁項集的原創性算法。

這里回顧幾個概念：

頻繁項集：頻繁出現在數據集中的模式。

布爾關聯規則：項集中的每一項都用一個布爾值表示的關聯規則。

支持度

• 相對支持度：由support(A蘊含B) = P(A∪B)定義
• 絕對支持度：出現頻率，又稱支持度計數，簡稱為頻率、計數。

Apriori算法使用逐層搜索的迭代方法，使用k項集（記作Lk）探索(K-1)項集（記作Lk-1）。

為提高頻繁項集逐層產生的效率，使用先驗性質壓縮搜索空間：

頻繁項集的所有非空子集也一定是頻繁的。——這一類特殊性質被稱為反單調性。

3.2 實現步驟

1. 令k=1，創建初始候選1項集C1。

2. 掃描C1，對每個候選項計算支持計數（在數據庫D中的出現頻率）。

3. 去除支持度計數小于最小支持度計數的項，得到L1。

4. 連接步：為找出Lk，通過Lk-1自連接產生候選k項集合，記為Ck。

5. 剪枝步：利用先驗性質進行剪枝，從Ck中剔除包含非頻繁項集的項（即Lk-1的補集），得到頻繁k項集，記為Lk。

6. 若步驟5得到的Ck集合不為空，返回步驟4繼續執行；否則，得到所有頻繁項集，算法終止。

舉書上的例子如下：

該數據庫有9個事務，設最小支持度計數為2，頻繁項集的產生過程如圖6.2。

3.3 偽代碼

/***輸入：* D：事務數據庫* min_sup：最小支持度閾值輸出：L，D中的頻繁項集 ***//**主函數**/ procedure main()//1 從事務數據庫D找出頻繁1項集L1 = find_frequent_1itemset(D);//2 掃描for(k=2;Lk-1≠空集;k++){//2.1 調用函數：從頻繁k-1項集Lk-1得到候選k項集Ck = aproiri_gen(Lk-1);//2.2 分別計算候選k項集中項的支持度for each 事務 t∈D{ //遍歷事務數據庫中的每一個事務tCt = subset(Ck,t); //得到事務t在候選集Ck中的子集for each 候選 c∈Ct;c.count++; //累加計數}//2.3 剪枝：去除小于最小支持度閾值min_sup的項Lk = {c(Ck|c.count >= min_sup)}}//3 返回頻繁k項集return L = ∪kLk;/**產生候選k項集**/ procedure apriori_gen(Lk-i:frequent(k-1) itemset)for each 項集 l1∈Lk-1for each 項集 l2∈Lk-1if (l1[1] = l2[1])∧...∧(l1[k-2] = l2[k-2])∧(l1[k-1] = l2[k-2]) thenc = l1 ?? l2;//調用函數：若候選k項集當前項包含非頻繁項，則刪除該項if has_infrequent_subset(c,Lk-1) thendelete c;//否則將該項加入頻繁k項集else add c to Ck;return Ck;/**判斷目標集合是否包含非頻繁項若包含返回TRUE，否則返回FALSE **/ procedure has_infrequent_subset(c:candidate k itemset; Lk-1:frequent(k-1)itemsets)for each(k-1)subset s of cif s 不屬于 Lk-1 thenreturn TRUE;return FALSE

?

注：文章內容中未說明的引用部分，為教材《概念與技術（中文第三版）》和課堂講義的整理。

總結

以上是生活随笔為你收集整理的数据挖掘学习日记3·关联规则挖掘的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。