文本的關聯規則演算法

⑴ 關聯演算法

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

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

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

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

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

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

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

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

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

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

⑵ 關聯規則挖掘演算法的介紹

學號：17020110019    姓名：高少魁

【嵌牛導讀】關聯規則挖掘演算法是數據挖掘中的一種常用演算法，用於發現隱藏在大型數據集中令人感興趣的頻繁出現的模式、關聯和相關性。這里將對該演算法進行簡單的介紹，之後通過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的條件 。

四、程序源碼

⑶ 關聯規則演算法的關聯規則的定義

所謂關聯，反映的是一個事件和其他事件之間依賴或關聯的知識。當我們查找英文文獻的時候，可以發現有兩個英文詞都能形容關聯的含義。第一個是相關性relevance，第二個是關聯性association，兩者都可以用來描述事件之間的關聯程度。
設I={i1,i2…,im}為所有項目的集合，設A是一個由項目構成的集合，稱為項集。事務T是一個項目子集,每一個事務具有唯一的事務標識Tid。事務T包含項集A，當且僅當AT。如果項集A中包含k個項目，則稱其為k項集。D為事務資料庫，項集A在事務資料庫D中出現的次數佔D中總事務的百分比叫做項集的支持度（support）。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。
關聯規則就是形如XY的邏輯蘊含關系，其中XI，YI且XY=Φ，X稱作規則的前件，Y是結果，對於關聯規則XY，存在支持度和信任度。
支持度是指規則中所出現模式的頻率，如果事務資料庫有s%的事務包含XY，則稱關聯規則XY在D中的支持度為s%，實際上，可以表示為概率P（XY），即support（XY）= P（XY）。信任度是指蘊含的強度，即事務D中c%的包含X的交易同時包含XY。若X的支持度是support(x)，規則的信任度為即為：support(XY)/support(X)，這是一個條件概率P（Y|X），即confidence（XY）= P（Y|X）。

⑷ apriori演算法是什麼

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

演算法應用

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