机器学习|Apriori算法与python实现频繁项集|关联规则|Apriori

Apriori算法 ??Apriori算法用于关联分析，其目标包括两个：发现频繁项集，发现关联规则。首先需要发现频繁项集，然后才能发现关联规则。本文Apriori部分的代码来自《机器学习实战》，有需要可以看看。
发现频繁项集 ??频繁项集指那些经常出现在一起的集合。若某个项集是频繁项集，则它的所有子集也是频繁的。反之，若一个项集是非频繁项集，则它的所有超集也是非频繁的。Apriori利用这个原理，避免计算非频繁项集及其所有超集的支持度。
??给定数据集，用Apriori发现频繁项集，只有一个输入参数：最小支持度。Apriori初始生成所有单个物品的候选集，然后扫描数据集，滤掉小于最小支持度的候选集，接着把剩下的集合进行组合，生成包含两个元素的候选集，如此持续下去，直到所有候选集被消去。
??频繁项集的量化指标是支持度，频繁项集必须满足支持度需求。

# 提取数据集的单元素集合（大小为1的候选集的集合） def createC1(dataSet): C1 = set() for transaction in dataSet: for item in transaction: C1.add(item) C1 = list(C1) C1.sort() # 用frozenset是为了能作为key return map(lambda x:frozenset([x]), C1)# 计算Ck中每项的支持度并过滤 def scanD(D, Ck, minSupport): ssCnt = {} for tid in D: for can in Ck: if can.issubset(tid): if not ssCnt.has_key(can): ssCnt[can] = 1 else: ssCnt[can] += 1 retList = [] # Lk supportData = https://www.it610.com/article/{} # 支持度（出现比例） for key in ssCnt: support = ssCnt[key] / float(len(D)) if support>= minSupport: retList.insert(0, key) # 阈值过滤 supportData[key] = support return retList, supportData

??createC1()用于初始化，构建集合C1，它的每个元素都是大小为1的候选集，顾名思义，Ck的每个元素大小为k。scanD()用于扫描数据集，判断C1里的每一个候选集是否满足最小支持度需求，过滤掉，然后剩下的构成L1，L1中的元素后续会进行组合，构成C2，然后过滤成L2，如此循环往复。

# 构造下一个候选集Ck def aprioriGen(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: # 如果它们前k-2项相同 retList.append(Lk[i] | Lk[j]) # 合并 return retListdef apriori(dataSet, minSupport=0.5): C1 = createC1(dataSet) D = map(set, dataSet) L1, supportData = https://www.it610.com/article/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

??aprioriGen()接收Lk，创建候选集Ck，比如输入{0}、{1}、{2}，就会输出{0,1}、{0,2}、{1,2}。注意这里有一个判断，若输入的两个元素（集合）有k-2项相同才合并，这个做法的目的是减少遍历次数。主函数是apriori()，它将持续生成Ck，然后过滤生成Lk，一直到无法继续为止。
挖掘关联规则 ??关联规则源于频繁项集，任意一个频繁项集都能产生若干条关联规则，其中只有一部分成立。例如{“啤酒”，“奶粉”}，可能有一条规则“啤酒”→“奶粉”，但是反之不一定成立。
??关联规则的量化指标是可信度，规则P→H的可信度定义为 support(P∪H)/support(P)。对于任何一个频繁项集，其产生的所有关联规则，都要计算可信度，把低可信度的规则去掉。然而有时候频繁项集的元素个数太多，可能产生很多关联规则，为了减少计算复杂度，利用这个规律：若某条规则不满足最小可信度需求，则该规则的所有子集也不满足最小可信度需求。

# 计算可信度 def calcConf(freqSet, H, supportData, br1, minConf=0.7): prunedH = [] for conseq in H: conf = supportData[freqSet] / supportData[freqSet - conseq] if conf >= minConf: # 过滤 # print "{0} --> {1} conf:{2}".format(freqSet - conseq, conseq, conf) br1.append((freqSet - conseq, conseq, conf)) prunedH.append(conseq) return prunedHdef rulesFromConseq(freqSet, H, supportData, br1, minConf=0.7): m = len(H[0]) if len(freqSet) > m+1: Hmp1 = aprioriGen(H, m+1) Hmp1 = calcConf(freqSet, Hmp1, supportData, br1, minConf) if len(Hmp1)>1: rulesFromConseq(freqSet, Hmp1, supportData, br1, minConf)def generateRules(L, supportData, minConf=0.7): 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

??generateRules()是主函数，它有三个输入：频繁项集列表L、支持度表supportData和最小可信度minConf，输出一个包含可信度的规则列表bigRuleList。它会遍历L中每一个频繁项集，对每个频繁项集创建只包含单个元素集合的列表H1，如果每个项集只有1个元素，直接用calcConf()计算可信度，否则用rulesFromConseq()进行合并。
示例：发现毒蘑菇的相似特征 ??Apriori还可以拿来做分类。我们不寻找所有的频繁项集，只对包含label的项集感兴趣。也就是说我们需要找到一些关联规则P→H，在H中包含label。这样我们就可以遍历所有样本，若P是样本的子集，就将对应的置信度作为样本是对应label的概率。当匹配的P很多时，可以取平均值。这种做法具有可解释性，可以理解为，“特征搭配为xxx和xxx时，平均有xx%的概率是正例”。
蘑菇数据可以在这里或这里找到。
为了保证label被包含在H中，需要对calConf()函数做一点改动。

def calcConf(freqSet, H, supportData, br1, minConf=0.7): prunedH = [] for conseq in H: conf = supportData[freqSet] / supportData[freqSet - conseq] if conf >= minConf: # 仅当label被包含在H中 if "1" in conseq or "0" in conseq: # print "{0} --> {1} conf:{2}".format(freqSet - conseq, conseq, conf) br1.append((freqSet - conseq, conseq, conf)) prunedH.append(conseq) return prunedH

主函数

import apriori import time import numpy as np# 读取训练集 with open("./data/agaricus_train.csv", "rb") as f: dataSet = [line[:-1].split(',') for line in f.readlines()]# L中的每一个元素都至少在25%的样本中出现过 L, suppData = https://www.it610.com/article/apriori.apriori(dataSet, 0.25) # 阈值越小，越慢# 生成规则，每个规则的置信度至少是0.6 bigRuleList = apriori.generateRules(L, suppData, 0.6)# P→H，根据P集合的大小排序 bigRuleList = sorted(bigRuleList, key=lambda x:len(x[0]), reverse=True)# 读取测试集 with open("./data/agaricus_test.csv", "rb") as f: dataSet = [line[:-1].split(',') for line in f.readlines()] labels = np.array([int(x[0]) for x in dataSet])scores = [] for line in dataSet: tmp = [] for item in bigRuleList: if item[0].issubset(set(line)): if "1" in item[1]: tmp.append(float(item[2])) # 因为是预测“为1的概率”，所以要用1减 if "0" in item[1]: tmp.append(1 - float(item[2])) scores.append(np.mean(tmp)) # 求取均值# 用置信度作为预测概率 scores = map(lambda x:x>0.5, scores) scores = np.array(scores, dtype='int') print sum(np.equal(scores, labels)), len(labels), sum(np.equal(scores, labels))/float(len(labels))

输出

1427 1611 0.8857852265673495

虽然88.6%的识别率很低，但将最小支持度进一步调低，应该还可以提高识别率，此外，也可以将这个置信度当做一维特征，而不是单纯作为预测概率。
Apriori的缺点 ??如上所见，Apriori是真的很慢，慢到令人发指。尽管它已经利用非频繁项集的超集非频繁的原理节省了不少计算量，但才不到1w行的mushroom数据，支持度选取25%，都要3分钟左右的处理时间。这是由于对于每一个 kk ，Apriori都要遍历一次整个数据集，而当支持度变低，满足条件的频繁项集变多，这个时间消耗就进一步增加。
完整实验代码 https://github.com/SongDark/Apriori
参考资料 【机器学习|Apriori算法与python实现】《机器学习实战》
数据挖掘十大算法之Apriori详解
Frequent Itemset Mining Dataset Repository
UCI mushroom
mushroom 分训练集测试集