1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#FP-growth算法用于发现“频繁项集”，其性能要比Apriori好两个数量级以上。FP-growth只要扫描数据集两次，
#便可发现频繁项，其基本过程如下：
#（1）构建FP树
#扫描数据集，记录各个元素出现的次数，计算各个元素的频率，去除频率低于阈值的元素，根据保留元素构建一棵
#FP树；
#（2）从FP树中挖掘频繁项集

#创建FP树的数据结构
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):#对count变量增加给定值
        self.count += numOccur

    def disp(self,ind=1):#将树以文本形式表示
        print(" "*ind,self.name," ",self.count)
        for child in self.children.values():#？？？
            child.disp(ind+1)

#构建FP树的步骤
#第一次遍历数据集，给出各个元素的出现次数，并且根据minSup筛选出“频繁项集”
#创建初始FP tree
#第二次遍历数据集，每遍历一条数据链，更新一次FP tree
#   如果数据链遍历时，下一个元素为当前元素的子节点，则更新节点count
#   否则，为下一个元素创建一个结点，并将其列入当前元素结点的子节点中，
#      同时，如果下一个元素头指针为Null，则将头指针指向该元素结点
#      如果，头指针不为Null，则遍历其nodeLink，将第一个为空的NodeLink指向该元素结点（这样可以使每个单独的元素实例相连）
#   如果该条数据链的长度>1,则递归运用UpdateTree函数，将数据链的其他元素也更新到树中


#FP树构建函数
def createTree(dataSet,minSup=1):#dataSet是字典{数据集:出现次数}
    headerTable = {}
    #第一次遍历数据集，给出每个元素的出现次数
    for trans in dataSet:
        for item in trans:
            headerTable[item] = headerTable.get(item,0) + dataSet[trans]#键Item的值+数据的出现次数
    #将元素出现次数
    for k in headerTable.keys():
        if headerTable[k] < minSup:#如果头指针表中的元素出现次数小于minSup
            del(headerTable[k])#删除该元素
    freqItemSet = set(headerTable.keys())#将剩下的元素放入集合freqItemSet
    if len(freqItemSet) == 0:#如果没有频繁项集，返回none
        return None,None
    for k in headerTable:
        headerTable[k] = [headerTable[k],None]#列表保存的是元素的出现次数，以及该元素节点
    retTree = treeNode('Null Set',1,None)#创建只包含空集合的根节点
    #第二次遍历数据集
    for tranSet,count in dataSet.items():
        localD = {}#存放频繁项的次数
        for item in tranSet:
            if item in freqItemSet:
                localD[item] = headerTable[item][0]#如果元素是频繁项集，则localD[item]为其出现次数
        if len(localD) > 0:#orderedTtems存放的是出现次数从大到小排列的 元素列表
            orderedItems = [v[0] for v in sorted(localD.items(),key = lambda p: p[1],reverse = True)]
            updateTree(orderedItems,retTree,headerTable,count)#更新FP tree
    return retTree,headerTable#返回FP tree,头指针表

def updateTree(items,inTree,headerTable,count):
    if items[0] in inTree.children:#如果元素在inTree的孩子中
        inTree.children[items[0]].inc(count)#将元素的出现次数+1
    else:
        inTree.children[items[0]] = treeNode(items[0],count,inTree)#否则，将元素归入inTree的孩子中，并创建该元素节点
        if headerTable[items[0]][1] == None:#如果该元素的头指针中，指针为None，则为其赋值
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            updateHeader(headerTable[items[0]][1],inTree.children[items[0]])#如果该元素头指针存在，则追溯nodeLink一直到nodeLink==NULL,并将nodeLink赋为该实例
    if len(items)>1:#如果数据链长度>1
        updateTree(items[1:],inTree.children[items[0]],headerTable,count)#递归执行updateTree


def updateHeader(nodeToTest,targetNode):#将某元素实例targetNode，连接到该元素的头指针中
    while(nodeToTest.nodeLink != None):#一直沿着NodeLink走，直到nodeLink为空
        nodeToTest= nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode#将该nodeLink赋值为targetNode，表示该元素项的另一个实例
        

######################################################################################################################
#从一颗FP 树中挖掘频繁项集
#需要明确几个定义：
#条件模式基：是以所查找元素项为结尾的路径集合（路径链，不包括该查找元素）；
#条件树：以某一元素的“条件模式基”为输入，构建的FP树为条件树，值得注意的是，条件树并不一定包含条件基中的所有部分，因为，条件基中某些元素的出现次数
#查找频繁项集的步骤：
#遍历头指针表中的所有元素
#  将该元素加入集合set([a])，以及列表list.append(set(...)) [(a)]
#  查找某一元素的所有条件模式基 
#  以该条件模式基为Input，构建树，如果构建的树其头指针表不为空的话：
#    遍历该头指针表的所有元素：
#       将该元素加入集合set([a,b])，以及列表list.append(set(...))[(a),(a,b)]
#       查找某一元素的条件模式基
#       以模式基为Input，构建树,迭代上述步骤

#某一给定元素实例的前缀路径提取函数
def ascendTree(leafNode,prefixPath):
    if leafNode.parent != Node:#追溯leafNode的父节点
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent,prefixPath)
#某一元素所有前缀路径 提取函数
def findPrefixPath(basePat,treeNode):
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode,prefixPath)#给出treeNode的前缀路径
        if len(prefixPath) > 1:
            condPats[frozenset(prefixPath[1:])} = treeNode.count #将该前缀路径锁定，并给出其出现次数
        treeNode = treeNode.nodeLink #指向该元素的下一个实例
    return codPats #返回该元素所有前缀路径的出现次数   
#给出条件树
def mineTree(inTree,headerTable,minSup,preFix,freqItemList):#preFix=set([]),freqItemList =[]
    bigL = [v[0] for v in sorted(headerTalbe.items(),key = lambda p:p[1])]#将元素按出现次数排好后输出到list中
    for basePat in bigL:#对于每一个元素
        newFreqSet = preFix.copy()
        newFreqSet.add(basePat)#相当于一个路径的存储
        freqItemList.append(newFreqSet)#用于存储各种长度的频繁项集
        condPattBases = findPrefixPath(basePat,headerTable[basePat][1])#找到basePat的前缀路径
        myCondTree,myHead = createTree(condPattBases,minSup)#以这些前缀路径为dataset，创建树
        print("conditional tree for:",newFreqSet)
        myCondTree.disp(1)
        if myHead != None:#如果这些前缀路径的频繁项集存在的话
            mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)#继续创建条件树
#freqItemList存储了所有的频繁项集