文章目錄
- 一、問題描述
- 二、實驗思路
-
- 1、資料格式
- 2、頻繁項集
-
- （1）連接配接步—産生候選式Ck
- （2）剪枝步—産生頻繁項集Lk
- （3）輸出結果
- 3、關聯規則
-
- （1）計算方法
- （2）輸出結果
- 三、完整代碼
一、問題描述
某個商場的事務資料庫D如表1所示，包括9個事務，即|D|=9。假設最小支援度min_sup=2，請使用Apriori算法找到D中的頻繁項集，并輸出所有的關聯規則（實驗程式設計語言不限）。
二、實驗思路
1、資料格式
（1）想要得到類似于下圖的表格輸出，則需用到DataFrame，使用DataFrame則Lk、Ck集确定為字典的格式。
（2）由于DataFram是把字典的鍵作為列标簽，若要讓頻繁項集一列、支援度計數一列，則需要進行轉置。
（3）字典是無序的，Apriori算法需要字典是有序的，是以在計算每一項出現的次數之前，先把key按順序排列好放入字典中。
以C1的處理為例：
# C1
C={}
Lkey = []
for values in data['商品ID的清單']:
Lkey.extend(["{"+item+"}" for item in values if item not in Lkey])
Lkey.sort()# 整理鍵的順序
for i in Lkey:
C[i]=0
for values in data['商品ID的清單']:
for item in values:
C["{"+item+"}"]+=1
"""
——————C1——————
支援度計數
{I1} 6
{I2} 7
{I3} 6
{I4} 2
{I5} 2
"""
（4）字典不是不支援清單嗎？如果要生成如下圖的效果怎麼用字典實作？
強制類型轉換，把清單轉成字元串。同時增加對額外字元“{”、"}"的處理。
# 對額外字元的處理-删去
for key in L.keys():
key = key.replace('{','')
key = key.replace('}','')
Lstr.append(key)
Lkey.append(key.split(','))
# 對額外字元的處理-增加
Lkey_new.sort()# 整理鍵的順序
for i in Lkey_new:
C["{"+i+"}"]=0
2、頻繁項集
（1）連接配接步—産生候選式Ck
敲重點：
1）以集合 L 1 = L_1= L1=
{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}
為例(下标從1開始數)
i） L L L是集合ii） l i l_i li是集合L中的項集，如 l 1 = l_1= l1={{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}
、 l 2 = l_2= l2={I1,I2}
iii） l i [ j ] l_i[j] li[j]表示 l i l_i li的第 j j j項，如 l 1 [ 1 ] = l_1[1]= l1[1]={I2,I5}
， l 4 [ 2 ] = l_4[2]= l4[2]=I1
I3
iiii）前 k − 2 k-2 k−2個項相同等價于除了最後一個項以外其它項都相同。
如
，第一項相同，最後一項不同，合并為{I1,I2},{I1,I3}
如{I1,I2,I3}
，第一項不同，不進行合并，若合并則會與前面的項重複，這條規則是為了不産生重複項。{I1,I2},{I2,I3}
2）項按字典序排序，即
{I1,I2}
需放在
{I1,I3}
的前面，這步在二、1、資料格式中介紹過了。
# 産生候選C
def Apriori_gen(Lkey,Lstr):
# Lkey-字典L的key-清單/Lstr-字典L的key-字元串
# 連接配接步
C={}
Lkey_new = []
for i in range(len(Lkey)-1):
j=i
flag = 0
for j in range(i+1,len(Lkey)):
# 檢查Lkey[i]和Lkey[j]是否除最後一項外前面的幾項都相同
for x in range(len(Lkey[i])):
if x==len(Lkey[i])-1:
if Lkey[i][x]==Lkey[j][x]:
print("ERROR:出現重複的頻繁項")
print(Lkey[i])
print(Lkey[j])
exit(0)
else:
# 找到合并項集,加入
temp=Lstr[i]+','+str(Lkey[j][x])
# 若子集都是頻繁項集，則加入到新的鍵表中
if not Has_infrequent_subset(temp,Lkey):
Lkey_new.append(temp)
# 若前k-2項出現不同，退出循環
elif Lkey[i][x]!=Lkey[j][x]:
flag=1
break
if flag==1:
break
# 整理鍵的順序
Lkey_new.sort()
for i in Lkey_new:
C["{"+i+"}"]=0
return C
（2）剪枝步—産生頻繁項集Lk
1）把有非頻繁子集的候選集剔除
# 判斷是否存在非頻繁項集
def Has_infrequent_subset(candi_set,Lkey):
# candi_set-候選集、L_k-1的頻繁集
candi_set = candi_set.split(',')
for x in candi_set:
subset = candi_set[:]
subset.remove(x)
if subset not in Lkey:
return True
return False
# 若子集都是頻繁項集，則加入到新的鍵表中
if not Has_infrequent_subset(temp,Lkey):
Lkey_new.append(temp)
2）把小于最小支援度的頻繁項集删除，即把大于等于最小支援度的頻繁項集加入到L中
L = {}
for key, values in C.items():
if values >= min_sup:
L[key] = values
（3）輸出結果
——————Data——————
商品ID的清單
0 [I1, I2, I5]
1 [I2, I4]
2 [I2, I3]
3 [I1, I2, I4]
4 [I1, I3]
5 [I2, I3]
6 [I1, I3]
7 [I1, I2, I3, I5]
8 [I1, I2, I3]
——————C1——————
支援度計數
{I1} 6
{I2} 7
{I3} 6
{I4} 2
{I5} 2
——————L1——————
支援度計數
{I1} 6
{I2} 7
{I3} 6
{I4} 2
{I5} 2
——————C2——————
支援度計數
{I1,I2} 4
{I1,I3} 4
{I1,I4} 1
{I1,I5} 2
{I2,I3} 4
{I2,I4} 2
{I2,I5} 2
{I3,I4} 0
{I3,I5} 1
{I4,I5} 0
——————L2——————
支援度計數
{I1,I2} 4
{I1,I3} 4
{I1,I5} 2
{I2,I3} 4
{I2,I4} 2
{I2,I5} 2
——————C3——————
支援度計數
{I1,I2,I3} 2
{I1,I2,I5} 2
——————L3——————
支援度計數
{I1,I2,I3} 2
{I1,I2,I5} 2
3、關聯規則
（1）計算方法
敲重點：
1）頻繁項集 l l l是集合 T T T的子集，這裡的集合 T T T即為上一步的結果 L L L。
2）如求解 A = > B A=>B A=>B的置信度，則先求資料庫中 A ∪ B A\cup B A∪B的數目，再求資料庫中 A A A的數目，做除法，結果為 A = > B A=>B A=>B的置信度。若大于最小置信度門檻值則輸出關聯規則。
# 産生非空子集并計算關聯度
def Non_subset(Lkey,D,min_conf):
# Lkey-頻繁項集的集合、D-資料庫、min_conf-最小置信度
conf={}
for l in Lkey:
non_subset = []
# 擷取頻繁項集l的所有非空子集
for i in range(len(l)):
for j in combinations(l, i + 1):
non_subset.append(j)
# 對非空子集進行格式處理
non_subset_new = []
for i in non_subset:
temp = []
for j in i:
temp.append(j)
non_subset_new.append(temp)
# 産生關聯規則/計算關聯度
for i in range(len(non_subset_new)-1):
for j in range(i+1,len(non_subset_new)):
A = non_subset_new[i]
B = non_subset_new[j]
AB = list(set(A).union(set(B))) # 取并集
# 存在相同元素
if len(AB)!=len(A)+len(B):
continue
# 計算數目
A_cnt = Cul_itemcnt(D,A)
B_cnt = Cul_itemcnt(D,B)
AB_cnt = Cul_itemcnt(D,AB)
if len(A) == 1:
Astr = A[0]
else:
Astr = Conf_deal(A)
if len(B) == 1:
Bstr = B[0]
else:
Bstr = Conf_deal(B)
# 與最小置信度門檻值比較
if AB_cnt/A_cnt>=min_conf:
s = Astr+"=>"+Bstr
s = s.replace("'","")
conf[s] = AB_cnt/A_cnt
if AB_cnt/B_cnt>=min_conf:
s = Bstr+"=>"+Astr
s = s.replace("'","")
conf[s] = AB_cnt/B_cnt
return conf
（2）輸出結果
假定最小置信度門檻值為0
置信度
I1=>I2 0.666667
I2=>I1 0.571429
I1=>I3 0.666667
I3=>I1 0.666667
I1=>{I2, I3} 0.333333
{I2, I3}=>I1 0.500000
I2=>I3 0.571429
I3=>I2 0.666667
I2=>{I1, I3} 0.285714
{I1, I3}=>I2 0.500000
I3=>{I1, I2} 0.333333
{I1, I2}=>I3 0.500000
I1=>I5 0.333333
I5=>I1 1.000000
I1=>{I2, I5} 0.333333
{I2, I5}=>I1 1.000000
I2=>I5 0.285714
I5=>I2 1.000000
I2=>{I1, I5} 0.285714
{I1, I5}=>I2 1.000000
I5=>{I1, I2} 1.000000
{I1, I2}=>I5 0.500000
三、完整代碼
Apriori算法求解關聯規則完整代碼