Apriori_fptree

2021-03-11

字数：789字 | 预计阅读时长：3分钟

Apriori

input
{ID1:[item1,item2…],ID2:[item3,item2…],…}

output
item1->item2,item3…
math
频率及条件概率的简单应用
支持度: 频数/样本总量
置信度: 条件概率
如果子集不为频繁集则超集一定不为；反之如果超集是频繁集则子集均为频繁集。
parameters
minSupport
minConf
过程
1-4完成了频繁集的搜寻，5及之后产生规则。

1、list存放每个用户的 itemset，生成[[],[]]存放所有item并排序，map(frozenset, C1)
2、第一轮遍历，生成一个list存放所有支持度大于minSupport，大于则insert(0,key)。遍历的函数scanD所生成list的元素是frozenset。如果can.issubset(tid)且！ssCnt.has_key(can)则加入到supportData。
3、list存放所有频繁物品集，supportData存放所有计算过的物品集的支持度，以frozenset作为key。两者更新的过程是在apriori中循环调用aprioriGen和scanD ，再更新。直到scanD得到的频繁物品集为空。
4、aprioriGen的过程，两层循环，遍历上一个(即物品集中个数为目前需要产生的个数-1)频繁物品集，L1 = list(Lk[i])[:k-2];L2 = list(Lk[j])[:k-2]取前k-2项比较，若相同则retList.append(Lk[i] | Lk[j])将物品集union。是一个merging过程。

5、如果频繁集frozenset中item多于2，先rulesFromConseq再calcConf。rulesFromConseq是个递归过程，

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    if (len(freqSet) > (m + 1)): #停止条件
        Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        if (len(Hmp1) > 1):   #至少需要两个元素才能够merge
            rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

这里一个问题是，如果len(Hmp1) =1，但是len(freqSet) > (len(Hmp1[0]) + 1)仍然成立，因此修改为：

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
    m = len(H[0])
    if (len(freqSet) > (m + 1)): #停止条件
        if(len(H) > 1):
            Hmp1 = aprioriGen(H, m+1)
        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
        rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)

fptree

概念
闭项：超集的支持度为s，子集的支持度都不超过s。
条件模式基：即一个item追溯到root的所有路径
条件fp树：即根据条件模式基创建的tree
myCondTree, myHead = createTree(condPattBases, minSup)

准备
headertable : dict，value为[count,treeNode]
treeNode : class

def __init__(self, nameValue, numOccur, parentNode):
     self.name = nameValue
     self.count = numOccur
     self.nodeLink = None
     self.parent = parentNode      
     self.children = {}

主要方法：createTree updateTree mineTree
辅助方法：updateHeader findPrefixPath ascendTree

过程

createTree首先第一次遍历计算count，headerTable[item] = headerTable.get(item, 0) + dataSet[trans]将count简单赋值为1。注意到这里的dataSet类型。
1
2
3
4
5
def createInitSet(dataSet):
retDict = {}
for trans in dataSet:
retDict[frozenset(trans)] = 1
return retDict
获得freqItemSet = set(headerTable.keys())后第二次遍历。先对item排序，orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] ，再updateTree(orderedItems, retTree, headerTable, count)。

updateTree，这里就是普通的对树的操作，也是递归。

1 2	if len(items) > 1:#call updateTree() with remaining ordered items updateTree(items[1::], inTree.children[items[0]], headerTable, count)

唯一注意之处，需要updateHeader。

mineTree和Apriori中的rulesFromConseq 一样较复杂，包含递归。先生成条件模式基，再生成conditional-fptree，再递归。
1
2
if myHead != None:
mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
循环递归mineTree的过程即生成规则过程，直到频繁2项集都得到。

本文作者： yuqing wang
本文链接： https://satyrswang.github.io/2021/03/11/Apriori-fptree/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！