文章目錄
- 一、問題描述
- 二、實驗思路
- 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是把字典的鍵作為列標簽，若要讓頻繁項集一列、支持度計數一列，則需要進行轉置，
print(pd.DataFrame(C, index=['支持度計數']).T)
（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是集合
{{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}}
ii） l i l_i li?是集合L中的項集，如 l 1 = l_1= l1?={I1,I2}、 l 2 = l_2= l2?={I2,I5}
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]=I1， l 4 [ 2 ] = l_4[2]= l4?[2]=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演算法求解關聯規則完整代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243322.html
標籤：python