學習筆記【機器學習重點與實戰】——11 頻繁項集與關聯關係挖掘演算法

1 頻繁項集與關聯關係挖掘演算法

從大規模資料集中尋找物品間的隱含關係被稱作關聯分析(association analysis ) 或者關聯規則學習(association rule learning)。關聯分析是用於發現大資料集中元素間有趣關係的一個工具集,可以採用兩種方式來量化這些有趣的關係。第一種方式是使用頻繁項集,它會給出經常在一起出現的元素項。第二種方式是關聯規則,每條關聯規則意味著元素項之間的“如果……那麼”關係。

關聯分析是資料探勘中最活躍的研究方法之一,目的是在一個資料集中找出各項之間的關聯關係,而這種關係並沒有在資料中直接表現出來。

這裡的主要問題在於,發現元素項間不同的組合是一項十分耗時的任務,不可避免需要大量昂貴的計算資源,蠻力搜尋方法並不能解決這個問題,所以需要用更智慧的方法在合理的時間範圍內找到頻繁項集。 其中常見的關聯關係演算法如下表所示。

常用關聯規則演算法

演算法名稱演算法描述
Apriori關聯規則最常用也是最經典的挖掘頻繁項集的演算法,其核心思想是通過連線產生候選項及其支援度然後通過剪枝生成頻繁項集
FP-Tree針對Apriori演算法的固有的多次掃描事務資料集的缺陷,提出的不產生候選頻繁項集的方法。Apriori和FP-Tree都是尋找頻繁項集的演算法
Eclat演算法Eclat演算法是一種深度優先演算法,採用垂直資料表示形式,在概念格理論的基礎上利用基於字首的等價關係將搜尋空間劃分為較小的子空間
灰色關聯法分析和確定各因素之間的影響程度或是若干個子因素(子序列)對主因素(母序列)的貢獻度而進行的一種分析方法

(1)關聯規則的一般形式

項集A、B同時發生的概率稱為關聯規則的支援度(也稱相對支援度)。

Support(A→B)=P(AUB)” role=”presentation” style=”text-align: center; position: relative;”>Support(A→B)=P(AUB)Support(A→B)=P(AUB)

Support(A→B)=P(A U B)

項集A發生,則項集B發生的概率為關聯規則的置信度。

Confidence(A→B)=P(B|A)” role=”presentation” style=”text-align: center; position: relative;”>Confidence(A→B)=P(B|A)Confidence(A→B)=P(B|A)

Confidence(A→B)=P(B| A )

(2)最小支援度和最小置信度

最小支援度是使用者或專家定義的衡量支援度的一個閥值,表示專案集在統計意義上的最低重要性;最小置信度是使用者或專家定義的衡量置信度的一個閾值,表示關聯規則的最低可靠性。

同時滿足最小支援度閾值和最小置信度網值的規則稱作強規則。

(3)項集

項集是項的集合。包含k個項的項集稱為k項集,如集合{牛奶,麥片,糖}是一個3項集。

項集的出現頻率是所有包含項集的事務計數,又稱作絕對支援度或支援度計數。如果項集 I” role=”presentation” style=”position: relative;”>III 的相對支援度滿足預定義的最小支援度閾值,則 I” role=”presentation” style=”position: relative;”>III 是頻繁項集。頻繁k項集通常記作k。

(4)支援度計數

項集A的支援度計數是事務資料集中包含項集A的事務個數,簡稱為項集的頻率或計數。

已知項集的支援度計數,則規則A→B的支援度和置信度很容易從所有事務計數、項集A和項集AUB的支援度計數推出。

(5)Support(A→B)=A,B同时发生的事务个数所有事务个数=Support_count(A∩B)Total_count(A)(6)Confidence(A→B)=P(B|A)=Support(A∩B)Support(A)=Support_count(A∩B)Support_count(A)” role=”presentation” style=”position: relative;”>Support(A→B)Confidence(A→B)=A,B同時發生的事務個數所有事務個數=Support_count(A∩B)Total_count(A)=P(B|A)=Support(A∩B)Support(A)=Support_count(A∩B)Support_count(A)(5)(6)(5)Support(A→B)=A,B同時發生的事務個數所有事務個數=Support_count(A∩B)Total_count(A)(6)Confidence(A→B)=P(B|A)=Support(A∩B)Support(A)=Support_count(A∩B)Support_count(A)

\begin{align}
Support(A→B)&=\frac{A,B同時發生的事務個數}{所有事務個數}=\frac{Support\_count(A∩B)}{Total\_count(A)}\\
Confidence(A→B)&=P(B| A )=\frac{Support(A∩B)}{Support(A)}=\frac{Support\_count(A∩B)}{Support\_count(A)}
\end{align}

也就是說,一旦得到所有事務個數,A,B和A∩B的支援度計數,就可以匯出對應的關聯規則A→B和B→A,並可以檢查該規則是否是強規則。

2 Apriori

Apriori演算法是最經典的挖掘頻繁項集的演算法,第一次實現了在大資料集上可行的關聯規則提取,其核心思想是通過連線產生候選項與其支援度,然後通過剪枝生成頻繁項集。

為了降低所需的計算時間,研究人員發現一種所謂的Apriori原理。Apriori原理可以幫我們減少可能感興趣的項集。Apriori原理是說如果某個項集是頻繁的,那麼它的所有子集也是頻繁的。也就是說如果一個項集是非頻繁集,那麼它的所有超集也是非頻繁的。 使用該原理就可以避免項集數目的指數增長,從而在合理時間內計算出頻繁項集。

優 點:易編碼實現。

缺點:在大資料集上可能較慢。

適用資料型別:數值型或者標稱型資料。

——《機器學習實戰》P201″ role=”presentation” style=”position: relative;”>P201P201P_{201}

實現程式碼如下:

from numpy import *
def loadDataSet():
'''
建立資料集
:return: 資料集
'''
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
def createC1(dataSet):
"""
建立不重複、排序並轉換為frozenset的候選項集列表C1
Parameters
----------
:param dataSet: 資料集
Returns
-------
:param frozenset: 候選項集列表
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 9:25
"""
C1 = []
for transaction in dataSet:     # 遍歷資料集
for item in transaction:    # 遍歷項集中元素
if not [item] in C1:    # 去重
C1.append([item])
C1.sort()                       # 升序排序
return list(map(frozenset, C1))
def scanD(D, Ck, minSupport):
"""
計算支援度符合要求的候選項集和支援度字典
Parameters
----------
:param D: 資料集
:param Ck: 候選項集
:param minSupport: 最小支援度
Returns
-------
:param retList: 支援度大於 最小支援度 的集合
:param supportData: 候選項集支援度字典
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 9:35
"""
ssCnt = {}                      # 存放候選集元素的頻率
#  統計候選項集元素的頻率
for tid in D:                   # 遍歷資料集
for can in Ck:              # 遍歷候選項集
if can.issubset(tid):   # 候選項集元素在資料集中,則計數
if not ssCnt.__contains__(can): ssCnt[can]=1
else: ssCnt[can]  = 1
numItems = float(len(D))        # 資料集大小
retList = []                    # 支援度大於 minSupport 的集合
supportData = {}                # 候選項集支援度字典
for key in ssCnt:
support = ssCnt[key]/numItems   # 支援度大小
if support >= minSupport:   # 支援度大於最小支援度,則新增集合
retList.insert(0,key)
supportData[key] = support  # 儲存候選項集支援度
return retList, supportData
def aprioriGen(Lk, k):
"""
生成合並後的頻繁項集
Parameters
----------
:param Lk: 頻繁項集列表
:param k: 項集元素個數
Returns
-------
:param retList: 合併後的頻繁項集列表
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 9:52
"""
retList = []
lenLk = len(Lk)
# 遍歷頻繁項集
for i in range(lenLk):
for j in range(i 1, lenLk):
# 分別取前k-2個元素並排序
L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]
L1.sort(); L2.sort()
# 前k-2個元素相同,則進行合併
if L1==L2:
retList.append(Lk[i] | Lk[j])
return retList
def apriori(dataSet, minSupport = 0.5):
"""
生成頻繁項集和支援度集
Parameters
----------
:param dataSet: 資料集
:param minSupport: 最小支援度
Returns
-------
:param L: 頻繁項集列表
:param supportData: 所有元素的支援度字典
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 10:34
"""
C1 = createC1(dataSet)      # 建立不重複、排序並轉換為frozenset的候選項集列表C1
D = list(map(set, dataSet)) # 轉換為set
# 計算支援度符合要求的候選項集和支援度字典
L1, supportData = scanD(D, C1, minSupport)
L = [L1]
k = 2   # 項集元素個數
while (len(L[k-2]) > 0):                # 遍歷,直到沒有新生成頻繁項
Ck = aprioriGen(L[k-2], k)          # 生成合並後的頻繁項集
Lk, supK = scanD(D, Ck, minSupport) # 計算支援度符合要求的候選項集和支援度字典
supportData.update(supK)            # 更新候選項集的支援度字典
L.append(Lk)                        # 更新頻繁項集
k  = 1
return L, supportData
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
"""
計算可信度
Parameters
----------
:param freqSet: 頻繁項集元素
:param H: 頻繁項集中元素集合
:param supportData: 支援度字典
:param brl: 關聯規則列表
:param minConf: 最小可信度
Returns
-------
:param prunedH: 可信度大於最小可信度的集合
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 12:55
"""
# 可信度大於最小可信度的集合
prunedH = []
for conseq in H:
# 計算可信度
conf = supportData[freqSet]/supportData[freqSet-conseq]
if conf >= minConf: 
print(freqSet-conseq,'-->',conseq,'conf:',conf)
# 關聯規則列表新增規則
brl.append((freqSet-conseq, conseq, conf))
prunedH.append(conseq)
return prunedH
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
"""
遞迴計算頻繁項集關聯規則
Parameters
----------
:param freqSet: 頻繁項集元素
:param H: 頻繁項集中元素集合
:param supportData: 支援度字典
:param brl: 關聯規則列表
:param minConf: 最小可信度
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 13:04
"""
m = len(H[0])
if (len(freqSet) > (m   1)):    # 頻繁項集中元素可以合併
Hmp1 = aprioriGen(H, m 1)   # 生成合並後的頻繁項集
# 計算可信度,並得到可信度大於最小可信度的集合
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1):         # 集合大小大於1則遞迴計算頻繁項集關聯規則
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
def generateRules(L, supportData, minConf=0.7):
"""
生成關聯規則
Parameters
----------
:param L: 頻繁項集列表
:param supportData: 支援度字典
:param minConf: 最小可信度
Returns
-------
:param bigRuleList: 包含可信度的規則列表
Author:  dkjkls
Blog:    https://blog.csdn.net/dkjkls
Modify:  2018/5/5 12:20
"""
bigRuleList = []
# 從含有兩個元素的頻繁項集開始遍歷
for i in range(1, len(L)):
for freqSet in L[i]:    # 遍歷頻繁項集中的元素
H1 = [frozenset([item]) for item in freqSet]    # 頻繁項資料轉換
if (i > 1):
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
else:   # 兩個元素的組合直接計算
calcConf(freqSet, H1, supportData, bigRuleList, minConf)
return bigRuleList
if __name__ == '__main__':
L, supportData = apriori(loadDataSet(),0.1)
rules = generateRules(L, supportData,0.1)

每次增加頻繁項集的大小,Apriori演算法都會重新掃描整個資料集。當資料集很大時,這會顯著降低頻繁項集發現的速度。

3 FP-growth

FP-growth演算法將資料集儲存在一個特定的稱作FP樹的結構之後發現頻繁項集或者頻繁項對,即常在一塊出現的元素項的集合FP樹。該演算法只需要對資料庫進行兩次掃描,而Apriori演算法對於每個潛在的頻繁項集都會掃描資料集判定給定模式是否頻繁,因此FP-gr0wth演算法的速度要比Apri0ri演算法快,通常效能要好兩個數量級以上。

這種演算法雖然能更為高效地發現頻繁項集,但不能用於發現關聯規則。

優 點:一般要快於Apriori。

缺點:實現比較困難,在某些資料集上效能會下降。

適用資料型別:標稱型資料。

——《機器學習實戰》P224″ role=”presentation” style=”position: relative;”>P224P224P_{224}

FP代表頻繁模式(Frequent Pattern)。一棵FP樹看上去與電腦科學中的其他樹結構類似,但是它通過連結(link)來連線相似元素,被連起來的元素項可以看成一個連結串列。

這裡寫圖片描述

同搜尋樹不同的是,一個元素項可以在一棵FP樹中出現多次。FP樹會儲存項集的出現頻率,而每個項集會以路徑的方式儲存在樹中。存在相似元素的集合會共享樹的一部分。只有當集合之間完全不同時,樹才會分叉。 樹節點上給出集合中的單個元素及其在序列中的出現次數,路徑會給出該序列的出現次數。

FP樹類定義如下:

class treeNode:
def __init__(self, nameValue, numOccur, parentNode):
self.name = nameValue       # 節點名
self.count = numOccur       # 計數值
self.nodeLink = None        # 相似元素項的連結
self.parent = parentNode    # 父節點
self.children = {}          # 子節點
# 對count變數增加給定值
def inc(self, numOccur):
self.count  = numOccur
# 文字形式顯示樹
def disp(self, ind=1):
print('  '*ind, self.name, ' ', self.count)
for child in self.children.values():
child.disp(ind 1)

FP-growth只會掃描資料集兩次,發現頻繁項集的基本過程如下:

  1. 構建FP樹
  2. 通過查詢元素項的條件基及構建條件FP樹來發現頻繁項集
  3. 過程2不斷以更多元素作為條件重複進行,直到FP樹只包含一個元素為止

4 參考

  1. 《機器學習實戰》第11章 使用Apriori演算法進行關聯分析
  2. 《機器學習實戰》第12章 使用FP-growth演算法來高效發現頻繁項集
  3. 《Python資料分析與挖掘實戰》5.3 關聯規則

===========文件資訊============
學習筆記由博主整理編輯,供非商用學習交流用
如本文涉及侵權,請隨時留言博主,必妥善處置
版權宣告:非商用自由轉載-保持署名-註明出處
署名(BY) :dkjkls(dkj卡洛斯)
文章出處:http://blog.csdn.net/dkjkls