FP-growth算法发现频繁项集——构建FP树
作者:我是8位的 发布时间:2022-04-26 16:22:52
FP代表频繁模式(Frequent Pattern),算法主要分为两个步骤:FP-tree构建、挖掘频繁项集。
FP树表示法
FP树通过逐个读入事务,并把事务映射到FP树中的一条路径来构造。由于不同的事务可能会有若干个相同的项,因此它们的路径可能部分重叠。路径相互重叠越多,使用FP树结构获得的压缩效果越好;如果FP树足够小,能够存放在内存中,就可以直接从这个内存中的结构提取频繁项集,而不必重复地扫描存放在硬盘上的数据。
一颗FP树如下图所示:
通常,FP树的大小比未压缩的数据小,因为数据的事务常常共享一些共同项,在最好的情况下,所有的事务都具有相同的项集,FP树只包含一条节点路径;当每个事务都具有唯一项集时,导致最坏情况发生,由于事务不包含任何共同项,FP树的大小实际上与原数据的大小一样。
FP树的根节点用φ表示,其余节点包括一个数据项和该数据项在本路径上的支持度;每条路径都是一条训练数据中满足最小支持度的数据项集;FP树还将所有相同项连接成链表,上图中用蓝色连线表示。
为了快速访问树中的相同项,还需要维护一个连接具有相同项的节点的指针列表(headTable),每个列表元素包括:数据项、该项的全局最小支持度、指向FP树中该项链表的表头的指针。
构建FP树
现在有如下数据:
FP-growth算法需要对原始训练集扫描两遍以构建FP树。
第一次扫描,过滤掉所有不满足最小支持度的项;对于满足最小支持度的项,按照全局最小支持度排序,在此基础上,为了处理方便,也可以按照项的关键字再次排序。
第一次扫描的后的结果
第二次扫描,构造FP树。
参与扫描的是过滤后的数据,如果某个数据项是第一次遇到,则创建该节点,并在headTable中添加一个指向该节点的指针;否则按路径找到该项对应的节点,修改节点信息。具体过程如下所示:
事务001,{z,x}
事务002,{z,x,y,t,s}
事务003,{z}
事务004,{x,s,r}
事务005,{z,x,y,t,r}
事务006,{z,x,y,t,s}
从上面可以看出,headTable并不是随着FPTree一起创建,而是在第一次扫描时就已经创建完毕,在创建FPTree时只需要将指针指向相应节点即可。从事务004开始,需要创建节点间的连接,使不同路径上的相同项连接成链表。
代码如下:
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:
fset = frozenset(trans)
retDict.setdefault(fset, 0)
retDict[fset] += 1
return retDict
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):
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 createTree(dataSet, minSup=1):
headerTable = {}
#此一次遍历数据集, 记录每个数据项的支持度
for trans in dataSet:
for item in trans:
headerTable[item] = headerTable.get(item, 0) + 1
#根据最小支持度过滤
lessThanMinsup = list(filter(lambda k:headerTable[k] < minSup, headerTable.keys()))
for k in lessThanMinsup: del(headerTable[k])
freqItemSet = set(headerTable.keys())
#如果所有数据都不满足最小支持度,返回None, None
if len(freqItemSet) == 0:
return None, None
for k in headerTable:
headerTable[k] = [headerTable[k], None]
retTree = treeNode('φ', 1, None)
#第二次遍历数据集,构建fp-tree
for tranSet, count in dataSet.items():
#根据最小支持度处理一条训练样本,key:样本中的一个样例,value:该样例的的全局支持度
localD = {}
for item in tranSet:
if item in freqItemSet:
localD[item] = headerTable[item][0]
if len(localD) > 0:
#根据全局频繁项对每个事务中的数据进行排序,等价于 order by p[1] desc, p[0] desc
orderedItems = [v[0] for v in sorted(localD.items(), key=lambda p: (p[1],p[0]), reverse=True)]
updateTree(orderedItems, retTree, headerTable, count)
return retTree, headerTable
def updateTree(items, inTree, headerTable, count):
if items[0] in inTree.children: # check if orderedItems[0] in retTree.children
inTree.children[items[0]].inc(count) # incrament count
else: # add items[0] to inTree.children
inTree.children[items[0]] = treeNode(items[0], count, inTree)
if headerTable[items[0]][1] == None: # update header table
headerTable[items[0]][1] = inTree.children[items[0]]
else:
updateHeader(headerTable[items[0]][1], inTree.children[items[0]])
if len(items) > 1: # call updateTree() with remaining ordered items
updateTree(items[1:], inTree.children[items[0]], headerTable, count)
def updateHeader(nodeToTest, targetNode): # this version does not use recursion
while (nodeToTest.nodeLink != None): # Do not use recursion to traverse a linked list!
nodeToTest = nodeToTest.nodeLink
nodeToTest.nodeLink = targetNode
simpDat = loadSimpDat()
dictDat = createInitSet(simpDat)
myFPTree,myheader = createTree(dictDat, 3)
myFPTree.disp()
上面的代码在第一次扫描后并没有将每条训练数据过滤后的项排序,而是将排序放在了第二次扫描时,这可以简化代码的复杂度。
控制台信息:
项的顺序对FP树的影响
值得注意的是,对项的关键字排序将会影响FP树的结构。下面两图是相同训练集生成的FP树,图1除了按照最小支持度排序外,未对项做任何处理;图2则将项按照关键字进行了降序排序。树的结构也将影响后续发现频繁项的结果。
图1 未对项的关键字排序
图2 对项的关键字降序排序
来源:https://www.cnblogs.com/bigmonkey/p/7478698.html
猜你喜欢
- 如下所示:#-*- encoding:utf-8 -*-import csvimport sys,osimport pymysql def
- python书籍信息爬虫示例,供大家参考,具体内容如下背景说明需要收集一些书籍信息,以豆瓣书籍条目作为源,得到一些有效书籍信息,并保存到本地
- 一个不错的二级联动下拉菜单源码,您一定会用得到的。运行代码:<html><head><title>Lis
- 今天发现个好东西啊,叫片刻抠图,是一个在线对图片自动抠图去除背景的网站。只要上传图片,就可以自动把背景去掉把目标对象抠出来。不管是动物、汽车
- 日志Yii提供了一个高度自定义化和高扩展性的日志框架。根据使用场景的不同,你可以很容易的对各种消息就行记录、过滤、合并,比如说文本文件,数据
- 1.阈值化分割原理通过对图像的灰度直方图进行数学统计,选择一个或多个阈值将像素划分为若干类。一般情况下,当图像由灰度值相差较大的目标和背景组
- Python 安装Graphviz 详细教程Python安装Graphviz画图器首先,要明确他是一个独立的软件,如果大家用pip的方法装了
- 下表列出 SQL Server 查询分析器提供的所有键盘快捷方式。活动 快捷方式 书签:清除所有书签。 CTRL-SHIFT-F2
- 有时候我们需要使用python执行一些脚本,可能需要让程序自动按键或自动点击鼠标,下面的代码实现了对键盘的模拟按键,需要安装pypiwin3
- 需要分件html源代码 此例中的被抓取的html源代码如下 <p align=left>2004年8月24日星期二;白天:晴有时
- 似乎有一段时间没有更新博客了,这里就写点小功能,轻松获得电脑任意路径下的文件及文件夹,并将其写入word,以下是主要代码:**import
- torchvision.datasetsDatasets 拥有以下API:__getitem____len__Datasets都是 torc
- scrapy是用python开发的爬虫框架,从网上查了安装方法,感觉都说的挺复杂,而且很多教程都很有年头了,于是记录了自己的安装过程。首先安
- 如下所示:numpy.power(x1, x2)数组的元素分别求n次方。x2可以是数字,也可以是数组,但是x1和x2的列数要相同。 >
- 实际项目中遇到python模块相互引用问题,查资料,终于算是弄明白了。首先交叉引用或是相互引用,实际上就是导入循环,关于导入循环的详细说明,
- 你家中的CD、VCD一定很多吧?是不是常遇到为找一张CD把一抽屉的碟子翻得乱七八糟的情况,你一定没少受埋怨——你不想整理它们一下?如:影片是
- 脚本过于简单,供学习和参考。主要了解一下smtplib库的使用和超时机制的实现。使用signal.alarm实现超时机制。#!/usr/bi
- 本文实例总结了Python中numpy模块常见用法。分享给大家供大家参考,具体如下:import numpy as nparr = np.a
- 1. 使用 fileinput 进行迭代fileinput 模块可以对一个或多个文件中的内容进行迭代、遍历等操作。该模块的 input()
- 利用图标工具(有很多)制作图标文件(favicon.ico)上传到网站所在的服务器的根目录下,这个文件必须是16*16大小的图标文件。当然,