嵌牛導讀關聯規則挖掘算法是數據挖掘中的壹種常用算法，用於發現隱藏在大型數據集中令人感興趣的頻繁出現的模式、關聯和相關性。這裏將對該算法進行簡單的介紹，之後通過Apriori算法作為實例演示算法執行結果。
嵌牛鼻子數據挖掘 關聯規則挖掘 python
嵌牛正文
壹、算法原理
1、基本概念
關聯規則用於發現隱藏在大型數據集中令人感興趣的頻繁出現的模式、關聯和相關性。 而 Apriori算法則是經典的挖掘頻繁項集的關聯規則算法，它通過層層叠代來尋找頻繁項集，最後輸出關聯規則：首先掃描數據集，得到 1-頻繁項集，記為 L1，通過合並 L1得到 2-頻繁項集 L2，再通過 L2找到 L3，如此層層叠代，直到找不到頻繁項集為止。
在Apriori算法中，定義了如下幾個概念：
? 項與項集 ：設 I={i1,i2,…,im}是由 m個不同項構成的集合，其中的每個 ik(k=1,2,…,m)被稱為壹個項 (Item)，項的集合 I被稱為項集和，即項集。在實驗中，每壹條購物記錄可以被看做 壹個項集，用戶購買的某個商品即為壹個項。
? 事務與事務集：事務 T是項集 I的壹個子集，而事務的全體被稱為事務集。
? 關聯規則：形如 A=>B的表達式，其中， A和 B都屬於項集 I，且 A與 B不相交。
? 支持度：定義如下 support(A=>B) = P(A B)，即 A和 B所含的項在事務集中同時出現的概率。
? 置信度：定義如下 confidence(A?B)=support(A?B)/support(A)=P(A B)/P(A)=P(B|A)，即如果事務包含 A，則事務中同時出現 B的概率。
? 頻繁項集：如果項集 I的支持度滿足事先定義好的最小支持度閾值（即 I的出現頻度大於相應的最小出現頻度閾值），則 I是頻繁項集。
? 強關聯規則：滿足最小支持度和最小置信度的關聯規則，即待挖掘的關聯規則。
根據以上概念，要實現關聯規則的挖掘，首先要找到所有的頻繁項集，之後找出強關聯規則（即通過多次掃描數據集，找出頻繁集，然後產生關聯規則）。
2、挖掘頻繁項集
在該步驟中有兩個較為重要的部分 ：連接和修剪。連接步驟即使用k-1頻繁項集，通過連接得到 k-候選項集，並且只有相差壹個項的項集才能進行連接，如 {A,B}和 {B,C}連接成為 {A,B,C}。修剪步驟基於壹個性質：壹個 k-項集，如果它的壹個 k-1項集（子集）不是頻繁的，那麽它本身也不可能是頻繁的。 因此可以基於這個性質，通過判斷先驗性質來對候選集進行修剪。
3、產生關聯規則
經過連接和修剪之後，即找到了所有的頻繁項集，此時可以在此基礎上產生關聯規則，步驟如下
（1）對於每個頻繁項集 l，產生 l的所有非空子集（這些非空子集壹定是頻繁項集）；
（2）對於 l的每壹個非空子集 x，計算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那麽規則 x => (l-x)”成立。
二、算法設計
1、數據集
通過語句 import xlrd導入相關的庫來進行數據的讀取 。數據內容為十條購物記錄 ，每條購物記錄有若幹個商品，表示某個顧客的購買記錄 ，如圖
對於數據加載部分 使用了 xlrd庫中的函數 open_workbook來 打開壹個表格文件，使用sheet_by_index函數得到壹個工作表， row_values函數即可讀取表格中的內容。由於每個購物記錄的商品數不壹定相同，導致讀取的內容含有空格 (’ ’)，因此對數據進行刪減以得到緊湊的數據 ，最終讀取數據的結果以列表的形式返回。
2、連接
對於連接部分，主要目標是根據已有的k-1頻繁項集生成 k-候選頻繁項集。算法步驟為：首先將項集中的項按照字典順序排序，之後將 k-1項集中兩個項作比較，如果兩個項集中前 k-2個項是相同的，則可以通過或運算（|）將它們連接起來。
3、修剪
修剪操作主要使用壹個判斷函數，通過傳入連接操作後的項集和之前的k-1頻繁項集，對新的項集中的每壹個項的補集進行判斷，如果該補集不是 k-1頻繁項集的子集，則證明新的項集不滿足先驗性質，即壹個頻繁項集的所有非空子集壹定是頻繁的 ，否則就滿足先驗形式。返回布爾類型的參數來供調用它的函數作判斷。
經過連接和修剪步驟之後，項基要成為頻繁項集還必須滿足最小支持度的條件，筆者設計了generateFrequentItems函數來對連接、修剪後產生的 k-候選項集進行判斷，通過遍歷數據集，計算其支持度，滿足最小支持度的項集即是 壹個頻繁項集，可將其返回。
以上，經過不斷的遍歷、連接、修剪、刪除，可將得到的所有結果以列表形式返回。筆者還設計了字典類型的變量 support_data，以得到某個頻繁項集及其支持度 。
4、挖掘關聯規則
generateRules函數用來挖掘關聯規則，通過傳入 最小置信度、 頻繁項集及其 支持度來生成規則 。根據定理：對於頻繁項集 l的每壹個非空子集 x，計算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那麽規則 x => (l-x)”成立，因此，該函數重點在掃描頻繁項集，得到每壹個子集，並計算置信度，當置信度滿足條件（即大於等於最小置信度）時，生成壹條規則。在函數中，使用了元組來表示壹條規則，元組中包含 x、 l-x以及其置信度 ，最後返回生成的所有規則的列表。
三、算法執行結果
設置最大頻繁項集數k為 3，最小支持度為 0.2，最小置信度為 0.8 使用 pycharm運行程序 ，得到以下結果：
由圖中結果可以看出，對於頻繁 1-項集，有五個滿足的項集，頻繁 2-項集有 6個，頻繁 3-項集有 2個，它們都滿足支持度大於或等於最小支持度 0.2。根據頻繁項集，程序得到的關聯規則有三條，即 {面包 }=>{牛奶 }，，{雞蛋 }=>{牛奶 }，，{面包，蘋果 }=>{牛奶 其中，這些規則的置信度都是 1.0，滿足大於或等於最小置信度 0.8的條件 。
四、程序源碼