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

FP-growth算法比Apriori算法更快，它基于Apriori构建，但在完成相同任务时采用了不同的技术。这里的任务是将数据集存储在一个特定的称为FP树的结构之后发现频繁项集。

FP-growth算法只需要对数据集进行两次扫描，而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁，因而FP-growth算法的速度要比Apriori算法快。

FP-growth算法发现频繁项集的基本过程如下：

  • 构建FP树
  • 从FP树挖掘频繁项集

FP-growth算法的优缺点：

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

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式(Frequent Pattern) 。一棵FP树是通过link链接来连接相似元素，被连接起来的元素项可以看成一个链表。同搜索树不同的是，一个元素项可以在一棵FP树中出现多次。FP树会存储项集的出现频率，而每个项集会以路径的方式存储在树中。

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

FP-growth算法一般流程

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

构建FP树

创建FP树的数据结构

In [1]:
import fpGrowth
In [2]:
rootNode = fpGrowth.treeNode('pyramid', 9, None)
In [3]:
rootNode.children['eye'] = fpGrowth.treeNode('eye', 13, None)
In [4]:
rootNode.disp()

	pyramid 	9
		eye 	13
In [5]:
rootNode.children['phoenix'] = fpGrowth.treeNode('phoenix', 3, None)
In [6]:
rootNode.disp()

	pyramid 	9
		eye 	13
		phoenix 	3

构建FP树

这里面的重点是建树的过程，主要为createTree函数。该函数使用数据集和最小支持度作为参数来构建FP树。

树构建过程遍历数据集两次。
第一次遍历扫描数据集并统计每个元素项出现的频度，并将频度保存在头指针表中。
扫描头指针表删掉出现次数小于minSup(最小支持度)的项。
遍历数据集(只考虑频繁项的每一条事务)，对每一条事务中的元素进行频数大小排序，并根据此来建树(更新树，调用updateTree方法)。
updateTree函数会调用每一条事务，并根据此来更新树节点。
此外在updateTree函数中会调用updateHeader函数，这个函数用来将每个元素的链表串接起来。例如，树的不同分支都有'x'这个字母，需要用头指针将'x'全部连起来形成链表。

In [7]:
reload(fpGrowth)
Out[7]:
<module 'fpGrowth' from 'fpGrowth.pyc'>
In [8]:
simpDat = fpGrowth.loadSimpDat()
In [9]:
simpDat
Out[9]:
[['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']]
In [10]:
initSet = fpGrowth.createInitSet(simpDat)
In [11]:
initSet
Out[11]:
{frozenset({'e', 'm', 'q', 's', 't', 'x', 'y', 'z'}): 1,
 frozenset({'n', 'o', 'r', 's', 'x'}): 1,
 frozenset({'z'}): 1,
 frozenset({'s', 't', 'u', 'v', 'w', 'x', 'y', 'z'}): 1,
 frozenset({'p', 'q', 'r', 't', 'x', 'y', 'z'}): 1,
 frozenset({'h', 'j', 'p', 'r', 'z'}): 1}
In [12]:
myFPtree, myHeaderTab = fpGrowth.createTree(initSet, 3)

headerTable:  {'s': 3, 'r': 3, 't': 3, 'y': 3, 'x': 4, 'z': 5}
In [13]:
myFPtree.disp()

	NULL Set 	1
		x 	1
			s 	1
				r 	1
		z 	5
			x 	3
				y 	3
					s 	2
						t 	2
					r 	1
						t 	1
			r 	1
In [14]:
myHeaderTab
Out[14]:
{'r': [3, <fpGrowth.treeNode instance at 0x03EE6468>],
 's': [3, <fpGrowth.treeNode instance at 0x03EE6260>],
 't': [3, <fpGrowth.treeNode instance at 0x03EE6198>],
 'x': [4, <fpGrowth.treeNode instance at 0x03EE61C0>],
 'y': [3, <fpGrowth.treeNode instance at 0x03EE6288>],
 'z': [5, <fpGrowth.treeNode instance at 0x03EE6210>]}

从FP中挖掘频繁项集

从FP树中挖掘频繁项集的基本步骤如下：

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

抽取条件模式基

从上一节中的头指针表的中抽取。对于每个元素项，获得其对应的条件模式基(conditional pattern base)。
条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径(prefix path)。简而言之，一条前缀路径是介于所查找元素项与根节点之间的所有内容。
符号x的前缀路径为FP树中每条到x的路径的前缀(x元素前的部分)形成的集合。每条前缀路径都与一个计数值关联，该计数值为树中符号x节点出现的频数。

In [15]:
reload(fpGrowth)
Out[15]:
<module 'fpGrowth' from 'fpGrowth.pyc'>
In [16]:
fpGrowth.findPrefixPath('x', myHeaderTab['x'][1])
Out[16]:
{('z',): 3}
In [17]:
fpGrowth.findPrefixPath('x', myHeaderTab['z'][1])
Out[17]:
{}
In [18]:
fpGrowth.findPrefixPath('r', myHeaderTab['r'][1])
Out[18]:
{('x', 's'): 1, ('z',): 1, ('z', 'x', 'y'): 1}
In [19]:
fpGrowth.findPrefixPath('t', myHeaderTab['t'][1])
Out[19]:
{('z', 'x', 'y', 'r'): 1, ('z', 'x', 'y', 's'): 2}

创建条件FP树

程序中的mineTree函数对头指针表中的元素项按照其出现频率进行排序，默认是从小到大。

In [20]:
reload(fpGrowth)
Out[20]:
<module 'fpGrowth' from 'fpGrowth.pyc'>
In [21]:
freqItems = []
In [22]:
fpGrowth.mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)

bigL:  ['t', 's', 'y', 'r', 'x', 'z'] ; level:  1
basePat:  t ; level:  1
condPattBases:  {('z', 'x', 'y', 'r'): 1, ('z', 'x', 'y', 's'): 2}
headerTable:  {'y': 3, 'x': 3, 'z': 3}
conditional tree for:  set(['t'])
	NULL Set 	1
		y 	3
			x 	3
				z 	3
bigL:  ['z', 'x', 'y'] ; level:  2
basePat:  z ; level:  2
condPattBases:  {('y', 'x'): 3}
headerTable:  {'y': 3, 'x': 3}
conditional tree for:  set(['z', 't'])
	NULL Set 	1
		y 	3
			x 	3
bigL:  ['y', 'x'] ; level:  3
basePat:  y ; level:  3
condPattBases:  {}
headerTable:  {}
basePat:  x ; level:  3
condPattBases:  {('y',): 3}
headerTable:  {'y': 3}
conditional tree for:  set(['x', 'z', 't'])
	NULL Set 	1
		y 	3
bigL:  ['y'] ; level:  4
basePat:  y ; level:  4
condPattBases:  {}
headerTable:  {}
basePat:  x ; level:  2
condPattBases:  {('y',): 3}
headerTable:  {'y': 3}
conditional tree for:  set(['x', 't'])
	NULL Set 	1
		y 	3
bigL:  ['y'] ; level:  3
basePat:  y ; level:  3
condPattBases:  {}
headerTable:  {}
basePat:  y ; level:  2
condPattBases:  {}
headerTable:  {}
basePat:  s ; level:  1
condPattBases:  {('z', 'x', 'y'): 2, ('x',): 1}
headerTable:  {'x': 3}
conditional tree for:  set(['s'])
	NULL Set 	1
		x 	3
bigL:  ['x'] ; level:  2
basePat:  x ; level:  2
condPattBases:  {}
headerTable:  {}
basePat:  y ; level:  1
condPattBases:  {('z', 'x'): 3}
headerTable:  {'x': 3, 'z': 3}
conditional tree for:  set(['y'])
	NULL Set 	1
		x 	3
			z 	3
bigL:  ['x', 'z'] ; level:  2
basePat:  x ; level:  2
condPattBases:  {}
headerTable:  {}
basePat:  z ; level:  2
condPattBases:  {('x',): 3}
headerTable:  {'x': 3}
conditional tree for:  set(['y', 'z'])
	NULL Set 	1
		x 	3
bigL:  ['x'] ; level:  3
basePat:  x ; level:  3
condPattBases:  {}
headerTable:  {}
basePat:  r ; level:  1
condPattBases:  {('x', 's'): 1, ('z', 'x', 'y'): 1, ('z',): 1}
headerTable:  {}
basePat:  x ; level:  1
condPattBases:  {('z',): 3}
headerTable:  {'z': 3}
conditional tree for:  set(['x'])
	NULL Set 	1
		z 	3
bigL:  ['z'] ; level:  2
basePat:  z ; level:  2
condPattBases:  {}
headerTable:  {}
basePat:  z ; level:  1
condPattBases:  {}
headerTable:  {}
In [23]:
freqItems
Out[23]:
[{'t'},
 {'t', 'z'},
 {'t', 'y', 'z'},
 {'t', 'x', 'z'},
 {'t', 'x', 'y', 'z'},
 {'t', 'x'},
 {'t', 'x', 'y'},
 {'t', 'y'},
 {'s'},
 {'s', 'x'},
 {'y'},
 {'x', 'y'},
 {'y', 'z'},
 {'x', 'y', 'z'},
 {'r'},
 {'x'},
 {'x', 'z'},
 {'z'}]