关联分析(Apriori)
基本概念
项集
项集是指若干个项的集合
支持度
支持度定义为数据集中包含该项集的记录的比例，或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据X和Y，则对应的支持度为:
$$
Support(X,Y) = P(XY) = \frac{number(XY)}{num(All Samples)}
$$
以此类推，如果我们有三个想分析关联性的数据X，Y和Z，则对应的支持度为:
$$
Support(X,Y,Z) = P(XYZ) = \frac{number(XYZ)}{num(All Samples)}
$$
频繁项集
频繁项集是指支持度大于等于最小支持度的集合
置信度
置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据X和Y，X对Y的置信度为:
$$
Confidence(X \Leftarrow Y) = P(X|Y)=\frac{P(XY)}{P(Y)}
$$
最小支持度
最小支持度：最小支持度就是人为按照实际意义规定的阈值，表示项集在统计意义上的最低重要性。
最小置信度
最小置信度：最小置信度也是人为按照实际意义规定的阈值，表示关联规则最低可靠性。
原理
如果某个项集是频繁的，那么它的子集也是频繁的，应用它的逆否命题，我们可以减少很多计算量
频繁项集算法
当集合中项大于0时：
构建一个k个项组成的候选项集列表
检查数据以确保每一个项集都是频繁的
保留频繁项并构建k+1项组成的候选项的列表
关联项集算法
当k(k>=2)项候补集数目大于0时:
对每一个k项数据集:
计算1~k-1项数据集的支持度
计算1~k-1项数据集的置信度
代码
# coding=gbk
def loaddataset():
return [['豆奶', '莴苣'], ['豆奶', '尿布', '葡萄酒', '甜菜'], ['豆奶', '尿布', '葡萄酒', '橙汁'], ['豆奶', '尿布', '葡萄酒', '莴苣'],
['豆奶', '尿布', '橙汁', '莴苣']]
def create_c1(dataset):
c1 = []
for transaction in dataset:
for item in transaction:
if [item] not in c1:
c1.append([item])
c1.sort()
return list(map(frozenset, c1))
def scan_d(d, ck, minsupport):
sscnt = {}
for tid in d:
for can in ck:
if can.issubset(tid):
if can not in sscnt:
sscnt[can] = 1
else:
sscnt[can] += 1
numitems = float(len(d))
retlist = []
supportdata = {}
for key in sscnt:
support = sscnt[key] / numitems
if support >= minsupport:
retlist.insert(0, key)
supportdata[key] = support
return retlist, supportdata
def apriori_gen(lk, k):
retlist = []
lenlk = len(lk)
for i in range(lenlk):
for j in range(i + 1, lenlk):
l1 = list(lk[i])[:k - 2]
l2 = list(lk[j])[:k - 2]
l1.sort()
l2.sort()
if l1 == l2:
retlist.append(lk[i] | lk[j])
return retlist
def apriori(dataset, minsupport=0.5):
c1 = create_c1(data)
d = list(map(set, data))
l1, support = scan_d(d, c1, minsupport)
l = [l1]
k = 2
while (len(l[k - 2]) > 0):
ck = apriori_gen(l[k - 2], k)
lk, supportk = scan_d(d, ck, minsupport)
support.update(supportk)
l.append(lk)
k += 1
return l, support
def calc_conf(freqset, h1, supportdata, bigrulelist, minconf=0.7):
prunedh = []
for conseq in h1:
conf = supportdata[freqset] / supportdata[freqset - conseq]
if conf >= minconf:
print(freqset - conseq, '-->', conseq, 'conf', conf)
bigrulelist.append((freqset - conseq, conseq, conf))
prunedh.append(conseq)
return prunedh
def rules_from_conseq(freqset, h1, supportdata, bigrulelist, minconf=0.7):
m = len(h1[0])
if (len(freqset)) > (m + 1):
hmp1 = apriori_gen(h1, m + 1)
hmp1 = calc_conf(freqset, hmp1, supportdata, bigrulelist, minconf)
if len(hmp1) > 1:
rules_from_conseq(freqset, hmp1, supportdata, bigrulelist, minconf)
def generate_rule(l, supportdata, minconf=0.7):
big_rule_list = []
for i in range(1, len(l)):
for freq_set in l[i]:
h1 = [frozenset([item]) for item in freq_set]
if (i > 1):
rules_from_conseq(freq_set, h1, supportdata, big_rule_list, minconf)
else:
calc_conf(freq_set, h1, supportdata, big_rule_list, minconf)
return big_rule_list
if __name__ == "__main__":
data = loaddataset()
l, support = apriori(data)
print(generate_rule(l, support, 0.8))
总结
说实话这个代码我自己写可能要花too much time，因为关键的连接步({0,1,2}->{(0,1),(1,2),(0,2)})就是很不好写,但是自己写伪代码应该是可以的，其实这个算法还存在一个提升度的概念，用来度量关联规则的价值，这都是深入了，以后遇到了会说的。
Comments | NOTHING