《机器学习实战》笔记之十二——使用FP-Growth算法来高效发现频繁项集

本文主要是介绍《机器学习实战》笔记之十二——使用FP-Growth算法来高效发现频繁项集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第十二章 使用FP-Growth算法来高效发现频繁项集


FP-growth算法,基于Apriori构建,但在完成相同任务时采用了不同的技术,其只需要对数据库进行两次扫描,而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁,因此其比Apriori算法快。FP算法需要将数据集存储在一个特定的称作FP树的结构之后发现频繁项集或者频繁项对。

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

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP(Frequent Pattern)通过链接来连接相似元素,被连起来的元素项可以看成一个链表。


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

FP-growth算法首先构建FP树,然后利用它来挖掘频繁项集。为构建FP树,需要对原始数据集扫描两遍。第一遍对所有元素项的出现次数进行计数。第二遍扫描只考虑那些频繁元素。


12.2 构建FP树

数据结构:

FP树比其他树更加复杂,因此需要一个类来保存树的每一个节点。

#!/usr/bin/env python
# coding=utf-8
class treeNode:def __init__(self, nameValue, numOccur, parentNode):self.name     = nameValueself.count    = numOccurself.nodeLink = None                        #用于链接相似的元素项self.parent   = parentNode                  #指向父节点的指针self.children = {}def inc(self, numOccur):self.count += numOccurdef disp(self, ind=1):                          #将树以文本形式显示print " "*ind, self.name, " ",self.countfor child in self.children.values():child.disp(ind+1)rootNode = treeNode("pyramid", 9, None)
rootNode.children["eye"] = treeNode("eye",13, None)
rootNode.disp()rootNode.children["phoenix"] = treeNode("phoenix", 3, None)
rootNode.disp()

Figure 12-2: FP数据结构

构建FP树

除了FP树的类,还需要头指针表来指向给定类型的第一个实例。通过头指针表可以快速访问FP树中一个给定类型的所有元素。可用字典保存,并且其value存放FP树中每类元素的总数。

第一遍遍历数据集得到每个元素项的出现频率。去掉不满足最小支持度的元素项。再构建FP树。构建时,读入每个项集并将其添加到一条已经存在的路径中。如果该路径不存在,则创建一条新路径。每个事务就是一个无序集合。假设集合{z,x,y}和{y,z,r},那么在FP树中,相同项只会表示一次。为此在将集合添加到树之前,先对每个集合进行排序,排序基于元素项出现的频率。

在对事务记录过滤和排序之后,就可以构建FP树了。从空集,向其中不断添加频繁项集。过滤、排序后的事务依次添加到树中,如果树中巳存在现有元素,则增加现有元素的值;如果现有元素不存在,则向树添加一个分枝。

coding:

#================FP树构建函数=============================
def createTree(dataSet, minSup=1):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, Nonefor 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]if len(localD) > 0:orderedItems = [v[0] for v in sorted(localD.items(),key = lambda e:e[1], reverse =True)]updateTree(orderedItems, retTree, headerTable, count)       #排序后,对树进行填充return retTree, headerTabledef updateTree(items, inTree, headerTable, count):if items[0] in inTree.children:                 #测试第一个元素项是否作为子节点存在inTree.children[items[0]].inc(count)else:inTree.children[items[0]] = treeNode(items[0], count, inTree)           #创建树的新节点if headerTable[items[0]][1] == None:headerTable[items[0]][1] = inTree.children[items[0]]                #树上的新的节点的值更新else: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):while (nodeToTest.nodeLink !=None):nodeToTest = nodeToTest.nodeLinknodeToTest.nodeLink = targetNode#========简单数据集及数据包装器================================
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 simpDatdef createInitSet(dataSet):retDict = {}for trans in dataSet:retDict[frozenset(trans)] = 1return retDictsimpDat = loadSimpDat()
print simpDatinitSet = createInitSet(simpDat)
print initSetmyFPtree, myHeaderTab = createTree(initSet, 3)
myFPtree.disp()

效果

Figure 12-4: FP树构建的效果


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

有了FP树之后,就可以抽取频繁项集了,首先从单元素项集开始,然后在此基础上逐步构建更大的集合。

步骤:

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

条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径。图12-2中,符号r的前缀路径有{x,s},{z,x,y}和{z}。根据头指针表通过上溯树直到根节点抽取出条件模式基。

创建条件FP树

对于每一个频繁项,都要创建一颗条件FP树。通过递归可发现频繁项、条件模式基以及另外的条件树。假设以频繁项t创建一个条件FP树,然后对{t,y}、{t,x}、...等重复该过程。

coding:

#=========发现以给定元素项结尾的所有路径的函数=================
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.counttreeNode = treeNode.nodeLinkreturn condPats
#===============递归查找频繁项集的mineTree函数=================
def mineTree(inTree, headerTable, minSup, preFix, freqItemList):bigL = [v[0] for v in sorted(headerTable.items(), key=lambda e:e[1])]       #从头指针表的底端开始for basePat in bigL:                                                        #bigL为头指针,basePat为“t”,"r"等等newFreqSet = preFix.copy()newFreqSet.add(basePat)freqItemList.append(newFreqSet)condPattBases = findPrefixPath(basePat, headerTable[basePat][1])        #创建“t”的条件模式基myCondTree, myHead = createTree(condPattBases, minSup)                  #以条件模式基构建条件FP树,得到的结果用于下一次迭代if myHead != None:                                                      #myHead由createTree函数得到,本质是头指针表变量。print "conditional tree for: ", newFreqSetmyCondTree.disp(1)mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)freqItems = []
mineTree(myFPtree, myHeaderTab, 3, set([]), freqItems)
print freqItems

效果:

Figure 12-6: FP树找到的频繁项集


12.4 示例:从新闻网站点击流中挖掘

数据:

该文件中的每一行包含某个用户浏览过的新闻报道。一些用户只看过一篇报道,而有些用户看过2498篇报道。用户和报道被编码成整数。

Figure 12-7: kosarak.dat数据

coding:

#========================从新闻网站点击流中挖掘================
parsedDat = [line.split() for line in open("kosarak.dat").readlines()]
initSet   = createInitSet(parsedDat)
myFPtree, myHeaderTab = createTree(initSet, 100000)
myFreqList = []
mineTree(myFPtree, myHeaderTab, 100000, set([]), myFreqList)
print len(myFreqList)
print myFreqList

效果:

Figure 12-8: FP算法运行效果


12.5 小结

FP-growth算法是一种用于发现数据集中频繁模式的有效方法,利用Apriori原理,只对数据集扫描两次,运行更快。在算法中,数据集存储在FP树中,构建完树后,通过查找元素项的条件基及构建条件FP树来发现频繁项集。重复进行直到FP树只包含一个元素为止。

可以使用FP算法在多种文本中查找频繁单词。


这篇关于《机器学习实战》笔记之十二——使用FP-Growth算法来高效发现频繁项集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/990978

相关文章

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)

《使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)》PPT是一种高效的信息展示工具,广泛应用于教育、商务和设计等多个领域,PPT文档中常常包含丰富的图片内容,这些图片不仅提升了... 目录一、引言二、环境与工具三、python 提取PPT背景图片3.1 提取幻灯片背景图片3.2 提取

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin