机器学习（十一）：FP增长（FP-growth）

更多内容关注公众号：数学的旋律

tb店铺搜：FUN STORE玩物社，专业买手挑选送礼好物

引言

    FP增长（FP-growth）算法是一种高效发现频繁项集的方法，只需要对数据库进行两次扫描。它基于Apriori构建，但在完成相同任务时采用了一些不同的技术。该算法虽然能更为高效地发现频繁项集，但不能用于发现关联规则。
    本文用到的部分术语已在简介中介绍（具体看‘基本概念-关联分析’），这里不再重述。

一、FP-growth算法

    FP-growth算法发现频繁项集的基本过程如下：
① 构建FP树
② 从FP树中挖掘频繁项集

二、构建FP树

    FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项，因此它们的路径可能部分重叠，路径相互重叠越多，使用FP树结构获得的压缩效果越好。
    为构建FP树，需要对原始数据集扫描两遍。
① 第一遍对所有元素项的出现次数进行计数，丢弃支持度小于阈值的非频繁项，得到频繁项集，并对频繁项集按照支持度的递减排序。
② 第二遍扫描时，构建FP树。从空集开始，依次读入排序好的频繁项集中各条事务。如果树中已存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。
例1
数据集如下（需满足的最小支持度计数为3）：

三、从FP树中挖掘频繁项集

    从FP树中抽取频繁项集的三个基本步骤如下：
① 从FP树中获取前缀路径（prefix path）
    一条前缀路径是介于所查找元素项与树根节点之间的所有内容。为了获得这些前缀路径，可以对树进行穷举式搜索，直到获得想要的频繁项为止，或者使用一个更有效的方法来加速搜索过程。可以利用先前创建的头指针表来得到一种更有效的方法，头指针表包含相同类型元素链表的起始指针，一旦到达了每一个元素项，就可以上溯这棵树直到根节点为止。
② 将前缀路径转化为条件FP树（conditional FP-tree）
    对于每一个频繁项，都要创建一棵条件FP树，条件FP树的结构与FP树类似。先对单个元素构建条件FP树（即删除前缀路径中支持度计数小于阈值的树），再对剩下的元素与单个元素两两组合构建新的条件FP树，递归直至条件FP树为空。
例2
挖掘例1中数据的频繁项集
① 获取前缀路径
先创建头指针表及FP树，得到如下所示数据结构

以 t 为例，上图从左往右寻找第一个 t ，通过上溯到根节点可以获取第一个前缀路径为{s,y,x,z}，接着利用头指针表寻找下一个 t ，再上溯到根节点可以获取第二个前缀路径为{r,y,x,z}。
每个频繁项的前缀路径如下：

四、代码实现（python）

以下代码来自Peter Harrington《Machine Learing in Action》
代码如下（保存为fpGrowth.py)：

# -- coding: utf-8 --
class treeNode:
    # FP树中节点的类定义，用于构建FP树
    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)

def loadSimpDat():
    # 数据集
    simpDat = [['r', 'z', 'h', 'j', 'p'],
               ['z', 'y', 'x', 'w', 'v', 'u', 't', 's'],
               ['z'],
               ['r', 'x', 'n', 'o', 's'],
               ['y', 'r', 'x', 'z', 'q', 't', 'p'],
               ['y', 'z', 'x', 'e', 'q', 's', 't', 'm']]
    return simpDat

def createInitSet(dataSet):
    # 对数据集进行格式化处理
    retDict = {}
    for trans in dataSet:
        retDict[frozenset(trans)] = 1
    return retDict

def createTree(dataSet, minSup=1):
    # 该函数用于创建FP树
    # 该函数接收两个参数，分别是格式化后的数据集和需满足的最小支持度计数
    headerTable = {}                                # 存储头指针
    for trans in dataSet:
        # 循环每一个事务
        for item in trans:
            # 循环事务中的每一个元素，存储各元素的支持度计数
            headerTable[item] = headerTable.get(item, 0) + dataSet[trans]
    # 移除不满足最小支持度计数的元素项
    for k in headerTable.keys():
        if headerTable[k] < minSup:
            del(headerTable[k])
    freqItemSet = set(headerTable.keys())           # 存储删除后的元素项，即频繁项
    if len(freqItemSet) == 0: return None, None     # 如果没有元素项满足要求，则退出
    # 对头指针表扩展，以便可以保存计数值及指向每种类型第一个元素项的指针
    for k in headerTable:
        headerTable[k] = [headerTable[k], None]
    retTree = treeNode('Null Set', 1, None)         # 创建只包含空集合的根节点
    for tranSet, count in dataSet.items():          # 第二次遍历数据集，tranSet为各事务，count为初始化的计数值
        localD = {}
        for item in tranSet:
            if item in freqItemSet:                 # 如果该元素项为频繁项，则可继续操作
                localD[item] = headerTable[item][0] # 将第一次遍历得到的支持度计数赋值給相应元素
        if len(localD) > 0:
            orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: p[1], reverse=True)] # 获取元素项，并按支持度计数高到低排序
            updateTree(orderedItems, retTree, headerTable, count)
    return retTree, headerTable

def updateTree(items, inTree, headerTable, count):
    # 该函数接收4个参数，分别为已排序好的元素项、FP树、头指针表、对应计数值
    if items[0] in inTree.children:
        # 如果该元素是作为子节点存在，则更新该元素的计数
        inTree.children[items[0]].inc(count)
    else:
        # 否则，创建一个新的treeNode并将其作为一个字节点添加到树中
        inTree.children[items[0]] = treeNode(items[0], count, inTree)
        if headerTable[items[0]][1] == None:
            # 若头指针为空，更新头指针为树的子节点
            headerTable[items[0]][1] = inTree.children[items[0]]
        else:
            # 若头指针有值，更新头指针的nodeLink
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
    if len(items) > 1:
        # 对剩下的元素进行迭代调用自身
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)

def updateHeader(nodeToTest, targetNode):
    # 该函数用于更新头指针
    # 该函数接收2个参数，分别是待更新的位置和需更新的值
    while (nodeToTest.nodeLink != None):
        nodeToTest = nodeToTest.nodeLink           # 循环至链表尾端为None
    nodeToTest.nodeLink = targetNode

def ascendTree(leafNode, prefixPath):
    # 该函数用于递归上溯整颗树
    if leafNode.parent != None:
        prefixPath.append(leafNode.name)
        ascendTree(leafNode.parent, prefixPath)

def findPrefixPath(basePat, treeNode):
    # 该函数用于为给定元素项生成一个前缀路径
    # 该函数接收2个参数，分别是给定元素项和头指针表纪录的该元素的相似项路径
    condPats = {}
    while treeNode != None:
        prefixPath = []
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1:
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.nodeLink
    return condPats

def mineTree(inTree, headerTable, minSup, preFix, freqItemList):
    # 该函数用于将前缀路径转化为条件FP树
    # 该函数接收5个参数，分别是FP树、头指针表、需满足最小支持度计数、前缀路径、频繁项集
    bigL = [v[0] for v in sorted(headerTable.items(), key=lambda p: p[1])]  # 将频繁1-项集的元素按支持度计数低到高排序
    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)              # 根据给定的前缀路径构建FP树
        if myHead != None:
            # 递归直到该元素的前缀路径为空
            print 'conditonal tree for:', newFreqSet
            myCondTree.disp(1)
            mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)
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

运行命令如下：










以上全部内容参考书籍如下：
《数据挖掘导论（完整版）》人民邮电出版社
Peter Harrington《Machine Learing in Action》