输入：数据集合D，支持度阈值αα
输出：最大的频繁k项集
1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。
2）挖掘频繁k项集
a) 扫描数据计算候选频繁k项集的支持度
b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。
c) 基于频繁k项集，连接生成候选频繁k+1项集。
3） 令k=k+1，转入步骤2。
1. judegefreq函数，使用先验性质判断筛选掉那些具有非频繁子集的候选集,Cki为k候选集，subLk为k-1频繁集
defjudgefreq(Cki,subLk):
#判断子集是否是频繁集，以便使用先验性质删除那些具有非频繁子集的候选
foriinCki:
Cksub= Cki -frozenset([i])
ifCksubnot insubLk:
return False
return True
2. getLki函数，获得频繁k项集Lk。先产生候选k项集Ck，调用函数judgefreq筛选。然后扫描数据库进行计数，根据最小绝对支持度min，得到Lk
defgetLki(dataset, Lki,k, min, supportdata):
#获取频繁k项集Lk
allLki =list(Lki)
Ck =set()
foriinrange(len(Lki)): #产生候选Ck
forjinrange(1,len(Lki)):
a =list(allLki[i])
b =list(allLki[j])
a.sort();b.sort()
ifa[0:k -2] == b[0:k -2]:
ifjudgefreq(allLki[i] | allLki[j], Lki):
Ck.add(allLki[i] | allLki[j]) #加入频繁候选
Lk =set()
item_count = {}
fortindataset: #扫描数据集进行计数
forCkiinCk:
ifCki.issubset(t):
ifCkinot initem_count:
item_count[Cki] =1
else:
item_count[Cki] +=1
total =float(len(dataset))
foriteminitem_count:
if(item_count[item])>=min:
Lk.add(item)
supportdata[item] = item_count[item] / total
returnLk
3. getL函数，调用getLki获得全体频繁集L及其相对支持度
defgetL(dataset, k, minsup):
#获取所有的频繁项集L
support = {}
C1 =set()
fordataindataset:
foriindata:
item =frozenset([i])
C1.add(item)
#获取候选1项集C1
L1 =set()
item_count = {}
fortindataset:
forC1iinC1:
ifC1i.issubset(t):
ifC1inot initem_count:
item_count[C1i] =1
else:
item_count[C1i] +=1
total =float(len(dataset))
foriteminitem_count:
if(item_count[item]) >= minsup:
L1.add(item)
support[item] = item_count[item] / total
#获取频繁1项集L1
Lksub1 = L1.copy()
L = []
L.append(Lksub1)
foriinrange(2, k+1):
Li=getLki(dataset, Lksub1,i, minsup, support)
if(len(Li)==0):
break
Lksub1 = Li.copy()
L.append(Lksub1)
returnL, support
4. rulesgenerating函数，由频繁集产生关联规则，即找出其中满足最小置信度的
即对每一个频繁项集，产生其非空子集。对每个非空子集，若置信度公式结果大于最小置信度阈值，则产生该关联关系。
defrulesgenerating(L, supportcount, confidence):
#由频繁项集产生关联规则
rules = []
sublist = []
foriinrange(0,len(L)):
forfathersetinL[i]:
forsubsetinsublist:
ifsubset.issubset(fatherset):
conf = supportcount[fatherset] / supportcount[fatherset - subset]
rule = (fatherset - subset, subset,conf)
ifconf >= confidence: #与最小置信度阈值比较
ifrulenot inrules:
rules.append(rule)
sublist.append(fatherset)
returnrules
5. 主函数
这里取了取minsup为2000项，且发现取到3000以上时速度会显著提高
取最小置信度阈值为0.8
耗时:产生频繁项集 约11秒
产生关联规则 约103秒
if__name__ =="__main__":
book=xlwt.Workbook(encoding='utf-8',style_compression=0)
sheet = book.add_sheet('frequentset',cell_overwrite_ok=True)#创建excel文件
print("running...")
dataset = []
rulelist=[]
withopen('homework1.dat')asfile_object:
forjinrange(4208):
line = file_object.readline()
dataset.append(line.strip('\n').split(' ')) #获得数据共4208项，一行22列
L, support = getL(dataset,k=22,minsup=2000)
rules = rulesgenerating(L, support,confidence=0.8)#获得关联关系
m=0
forLkinL:
print("频繁"+str(len(list(Lk)[0])) +"项集")
print("*******************************************")
forfreq_setinLk:
print(list(freq_set))
p=list(freq_set)
forjinrange(len(p)):
sheet.write(m, j, p[j]) #写入frequentset表格中
m+=1
print()
print("关联规则:")
foriteminrules:
print(list(item[0]),"=>",list(item[1]))
book.save(r'E:\project\o\datamining\frequentset.xls')#保存频繁集结果表格
print("完毕......")