《机器学习实战》学习笔记（十二）

第12章 使用FP-growth算法来高效发现频繁项集

引言

FP-growth 将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或者频繁项对，即常在一块出现的元素项的集合FP树。

通常性能要比Apriori好两个数量级以上。
FP-growth虽然能更为高效地发现频繁项集，但不能用于发现关联规则。

发现频繁项集的基本过程如下：

1. 构建FP树
2. 从FP树中挖掘频繁项集

FP-growth算法优缺点

• 优点：一般要快于Apriori。
• 缺点：实现比较困难，在某些数据集上性能会下降。
• 适用数据类型：标称型数据

FP-growth 的一般流程：

1. 收集数据：使用任意方法。
2. 准备数据: 由于存储的是集合，所以需要离散数据。如果要处理连续数据，需要将它们量化为离散值。
3. 分析数据：使用任意方法。
4. 训练算法：构建一个FP树 ，并对树进行挖据。
5. 测试算法：没有测试过程。
6. 使用算法: 可用于识别经常出现的元素项，从而用于制定决策、推荐元素或进行预测等应用中。

12.1 FP树：用于编码数据集的有效方式

FP代表频繁模式（Frequent Pattern)

FP树通过链接来连接相似元素，被连起来的元素项可以看成一个链表。如下图所示：

FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。存在相似元素的集合会共享树的一部分。只有当集合之间完全不同时，树才会分叉。 树节点上给出集合中的单个元素及其在序列中的出现次数，路径会给出该序列的出现次数。相似项之间的链接即节点链接(node link),用于快速发现相似项的位置。

元素项Z出现了5次 ，集合{r,z}出现了1次。于是可以得出结论：z 一定是自己本身或者和其他符号一起出现了4次。我们再看下z的其他可能性。集合{t,s,y,x,z,}出现了2次 ，集合{t,r,y,x,z}出现了1次。元素项z的右边标的是5，表示出现了5次，其中刚才已经给出了4次出现，而且没有别的连接(箭头连接的是相似项)，所以它一定单独出现过1次 。

12.2 构建FP树

数据库的第一遍扫描用来统计出现的频率，如果元素不满足最小支持度，则删掉此元素.而第二遍扫描中只考虑那些频繁元素。

12.2.1 创建FP树的数据结构

class tree_node:
    def __init__(self, name, num_occur, parent_node):
        self.name = name
        self.count = num_occur
        self.node_link = None
        self.parent = parent_node
        self.children = {}
 
    def inc(self, num_occur):
        self.count += num_occur
 
    def disp(self, ind=1):
        print("%r%r%r%r" % ('  ' * ind, self.name, ' ', self.count))
        for child in self.children.values():
            child.disp(ind + 1)
            
#创建根节点
rootNode = tree_node ('pyramid',9, None)
# 增加子节点
rootNode.children['eye'] = tree_node('eye', 13, None)
#增加子节点
rootNode.children['phoenix'] = tree_node('phoenix', 3, None) 
# 打印子节点
rootNode.disp()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

其中inc()对count变量增加给定值，而另一个方法disp()用于将树以文本形式显示。创建两个子节点并使用disp输出,得到结果如下：

pyramid为根节点，eye与Phoenix为子节点。子节点相比父节点缩进一些。

12.2.2 构建FP树

头指针表来指向给定类型的第一个实例。利用头指针表 ，可以快速访问FP树中一个给定类型的所有元素。下图为头指针表示意图：

构建时，读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在，则创建一条新路径。每个事务就是一个无序集合。假设有集合{z、x、y}和 比{y，z，r } , 那么在FP树中 , 相同项会只表示一次。为了解决该问题，所以在将集合添加到树之前，需要对每个集合进行排序。排序基于元素项的绝对出现频率来进行。

从空集（符号为0） 开始，向其中不断添加频繁项集。过滤、排序后的事务依次添加到树中，如果树中巳存在现有元素，则增加现有元素的值；如果现有元素不存在，则向树添加一个分枝。

FP树构建函数如下：

from time import *
from numpy import *

# FP树创建函数
def create_tree(data_set, min_sup=1):
    header_table = {}

    for trans in data_set:
        for item in trans:
            # get(item,0)#返回指定键（item）的值，
            # headerTable中已有的次数+事务中出现的1次
            header_table[item] = header_table.get(item, 0) + data_set[trans]
    
    # keys函数是Python的字典函数，它返回字典中的所有键所组成的一个可迭代序列。
    # 使用keys()可以获得字典中所有的键。
    # 移除不满足最小支持度的元素项，headerTable中的key即为具体元素
    for k in list(header_table.keys()):
        if header_table[k] < min_sup:
            #pop删除对应位置的值，返回值为删除的值
            header_table.pop(k)
    # set() 函数创建一个无序不重复元素集
    freq_item_set = set(header_table.keys())
    
    # 元素集为空就返回
    if len(freq_item_set) == 0: return None, None
    #第二次遍历获得头指针表
    for k in header_table:
        # 调整头指针列表的结构，使其可以链接到其他元素，即变成一个链表形式
        # 将键与值存储到header_table中
        header_table[k] = [header_table[k], None]
    # 创捷根节点
    ret_tree = tree_node('Null Set', 1, None)
    # items() 函数以列表返回可遍历的(键, 值) 元组数组。
    for tran_set, count in data_set.items():
        local_dataset = {}
        # 遍历每个事物每个元素项
        for item in tran_set:
            # 如果在频繁项集中
            if item in freq_item_set:
                #找出所有事务中的频繁项
                local_dataset[item] = header_table[item][0]
        
        if len(local_dataset) > 0:
            # 按照出现频率对当前事务中的元素进行排序
            # key=lambdap:p[1] 是匿名函数用来作为排序的依据，就是对localD.items()所返回的
            # 键值对{元素–出现次数}作为p，而p[1]就是出现次数，那么就是对出现次数进行排序，
            # reverse=True就是按照降序排列
            # [v[0] for v in sorted()] 是指取出sorted()所返回的序列中的每一个元素的索引为0的部分来组成一个列表，
            # 那么就是取出排完序之后的元素部分来组成列表。
            ordered_items = [v[0] for v in sorted(local_dataset.items(), key=lambda p: p[1], reverse=True)]
            # 更新树
            update_tree(ordered_items, ret_tree, header_table, count)
    return ret_tree, header_table
 
#升级树
def update_tree(items, in_tree, header_table, count):
    # 如果第一个元素满足已有路径
    if items[0] in in_tree.children:
        # 增加这个路径的元素的次数，按照这个事务出现次数来增加
        in_tree.children[items[0]].inc(count)
    else:
        #不存在，直接添加，使其父节点指向in_Tree
        in_tree.children[items[0]] = tree_node(items[0], count, in_tree)
        #如果头表目标节点为空，则将其指向inTree
        # 如果头指针表中该元素没有记录过指针
        if header_table[items[0]][1] == None:
            header_table[items[0]][1] = in_tree.children[items[0]]
        else:
            # 头指针表中已有了，那么要形成连接
            update_header(header_table[items[0]][1], in_tree.children[items[0]])
    # 如果长度大于1则继续迭代下去，items[1::]从索引为1的位置取到最后
    if len(items) > 1:
        # 递归调用
        update_tree(items[1::], in_tree.children[items[0]], header_table, count)
 
#  更新头指针表的节点链接
def update_header(node_to_test, target_node):
    # 找到列表最后一个
    while (node_to_test.node_link != None):
        node_to_test = node_to_test.node_link
    # 将更新的节点挂上去
    node_to_test.node_link = target_node
 
# 加载数据集函数
def load_simp_dat():
    simp_data = [['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 simp_data

# 计算项集在数据集的出现次数
def create_init_set(data_set):
    ret_dict = {}
    for trans in data_set:
        key = frozenset(trans)
        if key in ret_dict :   
            #这个统计次数直接等于一有问题
            ret_dict[frozenset(trans)] += 1
        else:
            ret_dict[frozenset(trans)] = 1
    return ret_dict
 
start_time = time()
data = create_init_set(load_simp_dat())
tree, table = create_tree(data, min_sup=3)
print("Head table:")
print(table)
print("FP Tree:")
tree.disp()
end_time = time()
print('总共执行时间:', end_time - start_time)


'''
#创建根节点
rootNode = tree_node ('pyramid',9, None)
# 增加子节点
rootNode.children['eye'] = tree_node('eye', 13, None)
#增加子节点
rootNode.children['phoenix'] = tree_node('phoenix', 3, None) 
# 打印子节点

rootNode.disp()

'''
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树对比书中的结果相同，但是输出次序与书中展示的有所不同。我认为是书中使用版本与程序使用版本不同所以导致的，但没有实际去试一下。

12.3 从一棵FP树中挖掘频繁项集

从FP树中抽取频繁项集的三个基本步骤如下：

1. 从FP树中获得条件模式基；
2. 利用条件模式基，构建一个条件FP树 ；
3. 迭代重复步骤(1)步骤( 2 ) ,直到树包含一个元素项为止。

12.3.1 抽取条件模式基

条件模式基（conditional pattern base )是以所查找元素项为结尾的路径集合 。每一条路径其实都是一条前缀路径(prefix path )。简而言之，一条前缀路径是介于所査找元素项与树根节点之间的所有内容。

如上图所示，符号 r 的前缀路径是{x，s}、{z，x，y} 和 {z}

为了获得这些前缀路径 ，可以对树进行穷举式搜索，直到获得想要的频繁项为止，或者使用一个更有效的方法来加速搜索过程。可以利用先前创建的头指针表来得到一种更有效的方法。头指针表包含相同类型元素链表的起始指针。一旦到达了每一个元素项，就可以上溯这棵树直到根节点为止。

发现 以给定元素项结尾的 所有路径的 函数

 
#上溯FP树
def ascendTree(leafNode, prefixPath): 
    #如果不是根节点
    if leafNode.parent != None:
        # 将当前节点记录
        prefixPath.append(leafNode.name)
        # 继续去找根节点
        ascendTree(leafNode.parent, prefixPath)
    
# 寻找前缀路径
def findPrefixPath(basePat, treeNode): 
    condPats = {}
    # 该元素的链还没到最后
    while treeNode != None:
        prefixPath = []
        # 寻找路径，这里传递的参数是可变的列表，是引用传递
        ascendTree(treeNode, prefixPath)
        if len(prefixPath) > 1: 
            # 这条路径出现次数
            condPats[frozenset(prefixPath[1:])] = treeNode.count
        treeNode = treeNode.node_link
    return condPats


start_time = time()
# 加载数据并计算出现次数
data = create_init_set(load_simp_dat())
# 创建FP树
tree, table = create_tree(data, min_sup=3)
# print("Head table:")
# print(table)
print("FP Tree:")
tree.disp()

zPreFix = findPrefixPath('z', table['z'][1])
rPreFix = findPrefixPath('r', table['r'][1])
xPreFix = findPrefixPath('x', table['x'][1])
print('zprefix: ',zPreFix)
print('rprefix: ',rPreFix)
print('rprefix: ',rPreFix)

end_time = time()
print('总共执行时间:', end_time - start_time)

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

输出结果如下：

从输出结果得到 ‘z’ 是没有前缀路径的，'r’的前缀路径是{‘z’}{‘s’, ‘x’}{‘z’, ‘x’}x的前缀路径是{‘z’}，与分析头指针表示意图得到的结果类似。

12.3.2 创建条件FP树

对于每一个频繁项，都要创建一棵条件FP树 。我们会为z、x以及其他频繁项构建条件树。可以使用刚才发现的条件模式基作为输入数据，并通过相同的建树代码来构建这些树。然后，我们会递归地发现频繁项、发现条件模式基，以及发现另外的条件树。

举个例子来说，假定为频繁项 t 建一个条件FP树，然 后对似 {t，y}、{t,x}, •••重复该过程。元素项t的条件FP树的构建过程如图所示。

在 t 的条件树中，{t，s}、{t，r}是不频繁的，所以这两个项集的超集就不是频繁的。

接下来，对集合{t，z}、{t，x}以及{t，y}来挖掘对应的条件树。这会产生更复杂的频繁项集。该过程重复进行，直到条件树中没有元素为止，然后就可以停止了。

上述过程是书中的，我理解的就是，先找单个的频繁项集，找到之后看他们和其余频繁项构成的超集是否也是频繁项，保留其中的频繁项，之后再增加一个其余的单个频繁项，依次重复直到条件树中没有元素。

递归查找频繁项集的mineTree的函数

#递归查找频繁项集
def mineTree(inTree,headerTable,minSup,preFix,freqItemList):
    #排序，从频率低到频率高排列树中的元素
    # key=lambdap:p[1] 是匿名函数用来作为排序的依据，就是对headerTable.items()所返回的
    # 键值对{元素–出现次数}作为p，而p[1]就是出现次数，那么就是对出现次数进行排序，
    bigL=[v[0] for v in sorted(headerTable.items(),key=lambda p:p[1][0])]
    #遍历headerTable中的所有元素
    for basePat in bigL:
        newFreqSet=preFix.copy()
        # 新增一个元素，形成新的频繁项集
        newFreqSet.add(basePat) 
        # 将频繁项添加到频繁项列表
        freqItemList.append(newFreqSet)
        #寻找元素basePat及其相似元素的所有前缀路径，并以字典的形式存储它们
        conPattBases=findPrefixPath(basePat,headerTable[basePat][1])
        # 在前缀路径的基础上创建FP树
        myCondTree,myHead=create_tree(conPattBases,minSup)
        #只要头指针表中还有元素，递归调用mineTree函数
        if myHead!=None:
            print ('conditional tree for: ', newFreqSet)
            myCondTree.disp(1)
            mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)
    
    return


start_time = time()

# 加载数据并计算出现次数
data = create_init_set(load_simp_dat())
# 创建FP树
tree, table = create_tree(data, min_sup=3)

freqItems=[]
mineTree(tree,table,3,set([]),freqItems)

end_time = time()
print('总共执行时间:', end_time - start_time)


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

输出结果如下：

[{'r'}, {'y'}, {'y', 'z'}, {'y', 'x'}, {'y', 'z', 'x'}, {'t'}, {'t', 'y'}, {'t', 'z'},
 {'t', 'y', 'z'}, {'t', 'x'}, {'t', 'y', 'x'}, {'t', 'z', 'x'}, {'t', 'y', 'z', 'x'}, 
 {'s'}, {'x', 's'}, {'x'}, {'z', 'x'}, {'z'}]
1
2
3

对比条件FP树与频繁项集，条件树输出都是包含有前缀路径的项次，而没有展示单个的频繁项次。对比频繁项集就可以知道。此外条件FP树展示的频繁项与前缀路径组合起来后形成的频繁项集有顺序区别，而输出的频繁项集却不包含顺序区别。

12.4 示例：在Twitter源中发现一些共现词

资源需要翻墙，没有梯子。所以就只分析一下代码。

import twitter
from time import sleep

import re
# 正则表达式有关的库

def textParse(bigString):

    urlsRemoved = re.sub('(http:[/][/]|www.)([a-z]|[A-Z]|[0-9]|[/.]|[~])*', '', bigString)    
    # 这个是正则表达式，将bigString中的字符替换为网址
    # http://www.*****/.
    listOfTokens = re.split(r'\W*', urlsRemoved)
    #利用匹配的子串分割
    # 在所有连续的非单词字符组成的字符串处，把bigString“切分开”，就是其间不论有多少空格、
    # 换行符什么，通通一刀切。然后过滤掉单词长度为2的字符串（空串），再把所有字母变成小写。
    return [tok.lower() for tok in listOfTokens if len(tok) > 2]


def getLotsOfTweets(searchStr):
    #从网上获取信息，使用twitter的API
    CONSUMER_KEY = ''
    CONSUMER_SECRET = ''
    ACCESS_TOKEN_KEY = ''
    ACCESS_TOKEN_SECRET = ''
    api = twitter.Api(consumer_key=CONSUMER_KEY, consumer_secret=CONSUMER_SECRET,
                      access_token_key=ACCESS_TOKEN_KEY, 
                      access_token_secret=ACCESS_TOKEN_SECRET)
    #you can get 1500 results 15 pages * 100 per page
    resultsPages = []
    # 搜索API可以一次获得100条推文。每100条推文作为一页，而Twitter允许一次访问14页。
    # 在完成搜索调用之后，有一个6秒钟的睡眠延迟，这样做是出于礼貌，避免过于频繁的访问请求。
    for i in range(1,15):
        print ("fetching page %d" % i)
        searchResults = api.GetSearch(searchStr, per_page=100, page=i)
        resultsPages.append(searchResults)
        sleep(6)
    return resultsPages


def mineTweets(tweetArr, minSup=5):

    parsedList = []
    # 这部分是处理数据
    for i in range(14):
        for j in range(100):
            parsedList.append(textParse(tweetArr[i][j].text))
    # 计算项集在数据集的出现次数
    initSet = createInitSet(parsedList)
    # 创建FP树
    myFPtree, myHeaderTab = createTree(initSet, minSup)
    myFreqList = []
    #条件FP树
    mineTree(myFPtree, myHeaderTab, minSup, set([]), myFreqList)
    # 输出频繁项集
    return myFreqList

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

12.5 示例：从新闻网站点击流中挖掘

start_time = time()

parsedDat = [line.split() for line in open ('./Ch12/kosarak.dat').readlines()]
# 获取数据
initSet =  create_init_set (parsedDat)
#计算数据集出现次数
myFPtree , myHeaderTab = create_tree (initSet, 100000)
#创界FP树
myFreqList = []
mineTree (myFPtree, myHeaderTab, 100000, set([]), myFreqList)
# 创建条件FP树
print("输出频繁项集：")
print(myFreqList)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果如下：

代码很简单，导入数据然后统计频繁集出现的次数，之后创建FP树，创捷条件FP树，输出频繁集。现在的置信度是100000，降低置信度后，我认为频繁项集会增多，因为门槛降低了，所以应该会有更多的频繁项集。
调整置信度为10000输出频繁项集如下：

与预料中的一样，频繁项集多了很多，但是随之运行时间也大大增加了。

12.6 小结

本章学习了FP-growth算法，目的是为了加快寻找数据中的频繁项集。使用了Apriori的思想，但是通过优化数据存储的结构，达到了更加快的速度寻找到频繁集的目标。
数据结构类似于双向列表，有父节点有子节点，能知道在当前几点的前一个节点和后一个节点是谁。