为什么Apriori算法和FP-growth算法得到的结果不一样
时间: 2023-12-01 17:15:13 浏览: 240
Apriori算法和FP-growth算法都是用于挖掘频繁项集的算法,但它们的实现方式不同,因此得到的结果可能会有所不同。
Apriori算法是一种基于迭代的算法,它通过自底向上的逐层扫描数据集来挖掘频繁项集。Apriori算法的核心思想是利用先验知识,即频繁项集的子集也必须是频繁的,从而减少搜索空间,提高效率。但是,由于Apriori算法需要多次扫描数据集,因此在处理大规模数据集时,其效率会受到限制。
FP-growth算法是一种基于分治的算法,它通过构建FP树来挖掘频繁项集。FP-growth算法的核心思想是将数据集压缩成一棵FP树,并利用FP树的性质来高效地挖掘频繁项集。FP-growth算法只需要遍历数据集两次,因此在处理大规模数据集时,其效率比Apriori算法更高。
由于Apriori算法和FP-growth算法的实现方式不同,其得到的结果可能会有所不同。特别是在处理包含大量项的数据集时,FP-growth算法的效率更高,因此得到的结果可能更准确。
相关问题
Apriori算法和fp-growth算法
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
apriori算法和FP-Growth算法的区别
apriori算法和FP-Growth算法都是用于数据挖掘中的频繁模式挖掘的算法。它们的区别主要在于两个方面:
1. 树结构不同
apriori算法利用候选集和频繁项集的特性,引入了先验性质,通过逐层扫描数据集来生成频繁项集。其核心操作是利用多次扫描数据库来不断生成新的候选频繁项集,并用频繁项集生成更高级别的候选频繁项集,直到不再有新的频繁项集产生。
FP-Growth算法则是直接利用了数据集的FP-树(Frequent Pattern Tree)结构,将数据集压缩为一棵FP-树,对FP-树进行遍历,从而挖掘出频繁模式。通过对每个模式的路径的合并,FP-Growth算法可以用较少的时间生成更多的频繁项集。
2. 扫描次数不同
由于FP-Growth算法的直接利用FP-树结构和路径合并算法,它避免了多次扫描数据库的操作,简化了算法运算的步骤,因此FP-Growth算法的时间效率优于apriori算法,尤其是在数据集过大时,FP-Growth算法的优势更加明显。
阅读全文