apriori算法和fp算法区别

Apriori算法和FPGrowth算法是常用的频繁项集挖掘算法。 Apriori算法是一种暴力枚举的算法，其基本思想是根据Apriori原理（即如果一个项集是频繁的，那么它的所有子集也是频繁的）逐层生成频繁项集。具体实现中，先将所有单个项看做频繁项集，然后不断扫描数据集，删除不符合最小支持度的项集，将剩余的项集组合成新的项集，重复上述过程直到无法生成新的高级频繁项集。其代码实现可参考：https://github.com/asaini/Apriori-Algorithm/blob/master/apriori.py FPGrowth算法则是一种基于FP树的频繁项集挖掘算法。FP树是一种特殊的数据结构，树中每个节点表示一个项，节点的权值表示该项在所有事务中出现的次数。具体实现中，首先将数据集按项出现频次排序，构建FP树，在FP树的基础上根据条件模式基逐层构建频繁项集。其优点是比Apriori算法更快速、占用更小的内存空间。其代码实现可参考：https://github.com/enaeseth/python-fp-growth/blob/master/fp_growth.py

Apriori算法和FP-Growth算法都是关联规则挖掘中常用的算法。 Apriori算法的原理是通过不断扫描数据集，找出频繁项集，然后由频繁项集产生候选规则，再通过支持度和置信度筛选出强规则。Apriori算法的缺点是需要不断扫描数据集，计算频繁项集，效率较低。 FP-Growth算法的原理是通过构建FP树来表示数据集，然后通过递归的方式挖掘频繁项集。FP-Growth算法的优点是只需要扫描两次数据集，不需要产生候选项集，效率较高。 以下是两个算法的Python实现： 1. Apriori算法 ```python def loadDataSet(): return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]] def createC1(dataSet): C1 = [] for transaction in dataSet: for item in transaction: if not [item] in C1: C1.append([item]) C1.sort() return list(map(frozenset, C1)) def scanD(D, Ck, minSupport): ssCnt = {} for tid in D: for can in Ck: if can.issubset(tid): if not can 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 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: retList.append(Lk[i] | Lk[j]) return retList def apriori(dataSet, minSupport=0.5): C1 = createC1(dataSet) D = list(map(set, dataSet)) L1, supportData = 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 ``` 2. FP-Growth算法 ```python class treeNode: def __init__(self, nameValue, numOccur, parentNode): self.name = nameValue self.count = numOccur self.nodeLink = None self.parent = parentNode self.children = {} def inc(self, numOccur): self.count += numOccur def disp(self, ind=1): print(' '*ind, self.name, ' ', self.count) for child in self.children.values(): child.disp(ind+1) def createTree(dataSet, minSup=1): headerTable = {} for trans in dataSet: for item in trans: headerTable[item] = headerTable.get(item, 0) + dataSet[trans] for k in list(headerTable.keys()): if headerTable[k] < minSup: del(headerTable[k]) freqItemSet = set(headerTable.keys()) if len(freqItemSet) == 0: return None, None