【频繁模式挖掘】FP-Tree算法（附Python实现）

一、实验内容简介

该实验主要使用频繁模式和关联规则进行数据挖掘，在已经使用过Apriori算法挖掘频繁模式后，这次使用FP-tree算法来编写和设计程序，依然使用不同规模的数据集来检验效果，最后分析和探讨实验结果，看其是否达到了理想的效果。本实验依然使用Python语言编写。

二、算法说明

首先简单介绍频繁模式和关联规则：

  • 频繁模式一般是指频繁地出现在数据集中的模式。

  • 关联规则是形如X→Y的蕴涵表达式，其中X和Y是不相交的项集，即X∩Y=∅。关联规则的强度可以用它的支持度（support）和置信度（confidence）来度量。计算公式如下：

  • 支持度：support(A=>B)=P(A∪B)，表示A和B同时出现的概率。

  • 置信度：confidence(A=>B)=support(A∪B)/support(A)，表示A和B同时出现的概率占A出现概率的比值。

  • 强关联规则是指达到了最小支持度和最小置信度的关联规则。

然后再介绍FP-Tree算法：

2000年，Han Jiawei等人提出了基于频繁模式树（Frequent Pattern Tree, FP—Tree）的发现频繁模式的算法FP-Growth。其思想是构造一棵FP-Tree，把数据集中的数据映射到树上，再根据这棵FP-Tree找出所有频繁项集。

FP-Growth算法是指，通过两次扫描事务数据集，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP-Tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据集，而仅在FP-Tree中进行查找即可。通过递归调用FP-Growth的方法可直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。由于只对数据集扫描两次，因此FP-Growth算法克服了Apriori算法中存在的问题，在执行效率上也明显好于Apriori算法。

image-20240407103431324

上图为FP-Tree示意图，展示了该数据结构的构成方式。

三、算法分析与设计

了解完算法的基本原理后，现在开始真正实现该算法。首先需要读取最小支持度，读取数据集。这里的数据集可大可小，我用Python中的字典来表示数据

这里的数据存储格式与之前写Apriori算法时一样，使用字典来存储。然后由用户来输入支持度和置信度（因为这次还要挖掘关联规则，所以增加了置信度输入）。

作为FP-Tree的基础，首先构建树节点。一个节点有四个基本属性，分别节点名称、出现次数、双亲节点和孩子节点。因为这里不是二叉树，树的孩子节点个数不确定，因此用字典来存储，大小可控。

class Node:def __init__(self, value, parent, count=0):self.value = valueself.parent = parentself.count = countself.children = {}def addChild(self, child):self.children.update(child)def __init__(self, value, parent, count=0):

前置准备完成后，开始实现FP-Tree算法。FP-Tree算法可大致分为构建项头表、构建FP-Tree、利用条件模式基挖掘频繁模式和关联规则几步。把这几步集成到一个类中，这样避免了大量函数传参操作，思路更清晰。

首先构建项头表，先扫描一遍数据集挖掘频繁1项集，挖掘出来的数据按支持度降序排列，并按此顺序重新排列原数据集的数据，对于不符合要求的数据直接删除。

    def first_scan(self):"""生成项头表，整理数据"""Dict = dict()for i in self.data.values():for j in i:if j not in Dict.keys():Dict.update({j: 1})else:Dict[j] += 1self.first_list = list(Dict.items())self.first_list.sort(key=lambda l: l[1], reverse=True)for i in range(len(self.first_list) - 1, 0, -1):if self.first_list[i][1] < self.support * len(self.data):continueelse:rubbish = [self.first_list[j][0] for j in range(i + 1, len(self.first_list))]self.first_list = self.first_list[:i + 1]break# 将原来的数据重新按支持度排序并剔除非频繁1项集sort_refer = [i[0] for i in self.first_list]for i in self.data.values():for j in i:if j in rubbish:i.remove(j)i.sort(key=lambda l: sort_refer.index(l))# 添加频繁1项集self.pinfan.extend([list(i) for i in self.first_list])# 整理项头表self.value_list = [i[0] for i in self.first_list]temp = {}for i in self.first_list:temp.update({i[0]: []})self.first_list = temp

然后构建FP-Tree。这里的过程就比较复杂了，简要说明步骤。第二次遍历数据集，从上往下构建分支，每次若遇到之前没出现的节点，就新建一个新节点，同时更新FP-Tree和项头表，若遇到之前已经出现的节点，则该节点的次数加一。特殊的根节点不需要存储任何数据，只需要存储孩子节点。

    def first_scan(self):"""生成项头表，整理数据"""Dict = dict()for i in self.data.values():for j in i:if j not in Dict.keys():Dict.update({j: 1})else:Dict[j] += 1self.first_list = list(Dict.items())self.first_list.sort(key=lambda l: l[1], reverse=True)for i in range(len(self.first_list) - 1, 0, -1):if self.first_list[i][1] < self.support * len(self.data):continueelse:rubbish = [self.first_list[j][0] for j in range(i + 1, len(self.first_list))]self.first_list = self.first_list[:i + 1]break# 将原来的数据重新按支持度排序并剔除非频繁1项集sort_refer = [i[0] for i in self.first_list]for i in self.data.values():for j in i:if j in rubbish:i.remove(j)i.sort(key=lambda l: sort_refer.index(l))# 添加频繁1项集self.pinfan.extend([list(i) for i in self.first_list])# 整理项头表self.value_list = [i[0] for i in self.first_list]temp = {}for i in self.first_list:temp.update({i[0]: []})self.first_list = temp

然后基于FP-Tree同时挖掘频繁模式和关联规则。利用项头表，从支持度低的元素到支持度高的元素，找到该元素在FP-Tree的所有位置，然后自底向上读取其所有祖先节点（除了根节点），同时把出现的次数都改为该元素所对应节点的次数。挖掘出结果后，先剔除掉不满足支持度要求的项，再通过两两组合挖掘出频繁2项集，然后递归挖掘出频繁多项集。同时两两组合算出条件概率与置信度比较，挖掘出1对1的关联规则。

这里涉及到的操作最为复杂，代码量也最大，分了三个方法来实现。

# 详见附录
def find(self):
def cal(self, Dict: dict, delete=False, length=1):
def rules(self, Dict: dict):

四、测试结果

写完代码后，就又到了测试环节。分别测试正确性和性能。在测试性能的时候也会与Apriori算法做比较，以更好地感受到FP-Tree算法的高效性。

首先验证正确性。我使用了教材上的数据集来验证。

img

先给定0.5的支持度和0.75的置信度：

img

经过验证是正确的，再给定0.2的支持度和0.5的置信度：

img

可以看到输出结果大大增加，经过验证也是正确的。

接下来就要扩大数据集的容量了，这样才能分析算法的性能。这里再次使用随机变量来模拟大量的数据：

img

在这里，arr和data2都可以修改，arr可以修改其中的元素来改变权重，data2可以修改数量，这里统一使用0.5作为支持度，0.75作为置信度。

首先用100000的数据来测试：

img

可以看到，一共花了0.288秒。相比其他条件相同下的Apriori算法是1.7秒。

然后把数据量变为1000000来试试：

img

一共花了2.845秒，相比同期Apriori算法一共花了15.58秒。

然后把数据量变为10000000来试试：

img

一共花了28.054秒，相比同期Apriori算法一共花了171.1秒。

最后再把数据量变为一亿，下图是最终结果。

img

差不多跑了8分钟，同期Apriori算法半个小时也没跑出来。可以看出，两个算法所耗费的时间都随时间呈线性增长，但FP-Tree算法显然效率比Apriori算法高得多。

五、分析与探讨

测试完算法后，来分析它的性能，思考FP-Tree算法的优势和缺陷。与Apriori算法相比，FP-Tree算法改进了Apriori算法的I/O瓶颈，巧妙的利用了树结构。Apriori的核心思路是用两个长度为l的频繁项集去构建长度为l+1的频繁项集，而FP-growth则稍有不同。它是将一个长度为l的频繁项集作为前提，筛选出包含这个频繁项集的数据集。用这个数据集构建新的FP-tree，从这个FP-tree当中寻找新的频繁项。如果能找到，那么说明它可以和长度为l的频繁项集构成长度为l+1的频繁项集。然后，我们就重复这个过程。

FP-Tree算法无论从复杂度还是实现难度还是具体技术点来看都比Apriori算法更复杂，但复杂度提高此带来的好处则是更高的效率和更好的性能。二者均为频繁模式挖掘的经典算法，都有必要学习和掌握，期待未来还能不断开发出挖掘频繁模式更加高效的算法。

附录：源代码

# 使用FP-tree实现频繁模式和关联规则挖掘
import itertools
import random
from time import time# 构建树的节点
class Node:def __init__(self, value, parent, count=0):self.value = valueself.parent = parentself.count = countself.children = {}def addChild(self, child):self.children.update(child)# 构建FP-tree
class FP_tree:def __init__(self, data, support, confidence):self.data = dataself.first_list = []self.value_list = []self.support = supportself.confidence = confidenceself.tree = Noneself.pinfan = []self.rule = []def first_scan(self):"""生成项头表，整理数据"""Dict = dict()for i in self.data.values():for j in i:if j not in Dict.keys():Dict.update({j: 1})else:Dict[j] += 1self.first_list = list(Dict.items())self.first_list.sort(key=lambda l: l[1], reverse=True)for i in range(len(self.first_list) - 1, 0, -1):if self.first_list[i][1] < self.support * len(self.data):continueelse:rubbish = [self.first_list[j][0] for j in range(i + 1, len(self.first_list))]self.first_list = self.first_list[:i + 1]break# 将原来的数据重新按支持度排序并剔除非频繁1项集sort_refer = [i[0] for i in self.first_list]for i in self.data.values():for j in i:if j in rubbish:i.remove(j)i.sort(key=lambda l: sort_refer.index(l))# 添加频繁1项集self.pinfan.extend([list(i) for i in self.first_list])# 整理项头表self.value_list = [i[0] for i in self.first_list]temp = {}for i in self.first_list:temp.update({i[0]: []})self.first_list = tempdef build_tree(self):"""建立FP-tree:return:fp-tree"""root = Node('root', None)parent = rootfor i in self.data.values():for j in i:# 更新树和项头表head = self.first_listif j not in parent.children.keys():node = Node(j, parent, 1)temp = {j: node}parent.addChild(temp)head[j].append(node)else:parent.children[j].count += 1parent = parent.children[j]parent = rootself.tree = rootdef find(self):"""利用建立好的树挖掘频繁模式"""for i in self.value_list[::-1]:i_dict = {}for j in self.first_list[i]:k = jcount = j.countwhile k != None:if k.value not in i_dict.keys():i_dict[k.value] = countelse:i_dict[k.value] += countk = k.parentdel i_dict['root']self.cal(i_dict, True)def cal(self, Dict: dict, delete=False, length=1):if delete:# 预处理，删去支持度低的项d = Dict.copy()for i, j in d.items():if j < self.support * len(self.data):del Dict[i]if length == 1:self.rules(Dict)# 递归挖掘频繁模式if length <= len(Dict):l = list(Dict.keys())pinfan = [l[0], Dict[l[0]]]del l[0]result = itertools.combinations(l, length)for i in result:p = pinfan.copy()for j in i:p.insert(-1, j)if Dict[j] < p[-1]:p[-1] = Dict[j]p[0:-1] = p[-2::-1]self.pinfan.append(p)self.cal(Dict, length=length + 1)def rules(self, Dict: dict):"""只生成1对1的关联规则:param Dict:数据源"""if len(Dict) > 1:l = list(Dict.keys())for i in l[1:]:if min(Dict[l[0]], Dict[i]) / Dict[l[0]] > self.confidence:self.rule.append(f"{l[0]}=>{i}")def __str__(self):"""输出频繁模式:return: 所有的频繁模式"""print("1对1的关联规则：" + str(self.rule))self.pinfan.sort(key=lambda l: (len(l), l[-1]), reverse=True)return "所有的频繁模式：" + str(self.pinfan)if __name__ == '__main__':data = {1: ['牛奶', '鸡蛋', '面包', '薯片'],2: ['鸡蛋', '爆米花', '薯片', '啤酒'],3: ['牛奶', '面包', '啤酒'],4: ['牛奶', '鸡蛋', '面包', '爆米花', '薯片', '啤酒'],5: ['鸡蛋', '面包', '薯片'],6: ['鸡蛋', '面包', '啤酒'],7: ['牛奶', '面包', '薯片'],8: ['牛奶', '鸡蛋', '面包', '黄油', '薯片'],9: ['牛奶', '鸡蛋', '黄油', '薯片'],10: ['鸡蛋', '薯片']}arr = ['牛奶', '面包', '鸡蛋', '馒头', '包子', '饼干']support = float(input('请输入最小支持度：'))confidence = float(input('请输入最小置信度：'))data2 = {i: [random.choice(arr) for j in range(10)] for i in range(100000)}begin = time()f = FP_tree(data2, support, confidence)f.first_scan()f.build_tree()f.find()print(f)print("总花费时间为%.3f秒" % (time() - begin))

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/301504.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

微服务架构下，如何通过弱依赖原则保障系统高可用？

微服务架构下，如何通过弱依赖原则保障系统高可用？

前言 当我初次接触高可用这个概念的时候&#xff0c;对高可用的【少依赖原则】和【弱依赖原则】的边界感模糊&#xff0c;甚至有些“傻傻分不清楚”。这两个原则都关注降低模块之间的依赖关系&#xff0c;但它们之间的确存在某些差异。 那么&#xff0c;「少依赖原则」和「弱…
阅读更多...
15.队列集

15.队列集

1.简介 在使用队列进行任务之间的“沟通交流”时&#xff0c;一个队列只允许任务间传递的消息为同一种数据类型&#xff0c;如果需要在任务间传递不同数据类型的消息时&#xff0c;那么就可以使用队列集。FreeRTOS提供的队列集功能可以对多个队列进行“监听”&#xff0c;只要…
阅读更多...
Unity类银河恶魔城学习记录12-4 p126 Item Tooltip源代码

Unity类银河恶魔城学习记录12-4 p126 Item Tooltip源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili UI.cs using System.Collections; using System.Collections.Generic; usi…
阅读更多...
xilinx AXI CAN驱动开发

xilinx AXI CAN驱动开发

CAN收发方案有很多&#xff0c;常见的解决方案通过是采用CAN收发芯片&#xff0c;例如最常用的SJA1000,xilinx直接将CAN协议栈用纯逻辑实现&#xff0c;AXI CAN是其中一种&#xff1b; 通过这种方式硬件上只需外接一个PHY芯片即可 上图加了一个电平转换芯片 软件设计方面&…
阅读更多...
Scala大数据开发

Scala大数据开发

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Scala简述 在此&#xff0c;简要介绍 Scala 的基本信息和情况。 Scala释义 Scala 源自于英语单词scalable&#xff0c;表示可伸缩的、可扩展的含义。 Scala作者 Scala编…
阅读更多...
【考研数学】张宇《1000题》刷不动，做不下来怎么办❓

【考研数学】张宇《1000题》刷不动，做不下来怎么办❓

学长肯定是用着效果不错才给你推荐的&#xff0c;但是习题册有很多&#xff0c;各自有不同的风格&#xff0c;1000题适不适合你的情况是你要考虑的点。 选书还是要结合自身的情况&#xff0c;如果当前用着不错的话&#xff0c;继续完全没有问题&#xff0c;核心就是要从自身的…
阅读更多...
IT外包服务：企业数据资产化加速利器

IT外包服务：企业数据资产化加速利器

随着数字化时代的兴起&#xff0c;数据成为企业最为重要的资源之一。数据驱动创新对于企业的竞争力和可持续发展至关重要。在这一进程中&#xff0c;IT外包服务发挥着关键作用&#xff0c;加速企业数据资产化进程&#xff0c;为企业提供了重要支持。 首先&#xff0c;IT外包服务…
阅读更多...
【学习心得】Python中的queue模块使用

【学习心得】Python中的queue模块使用

一、Queue模块的知识点思维导图 二、Queue模块常用函数介绍 queue模块是内置的&#xff0c;不需要安装直接导入就可以了。 &#xff08;1&#xff09;创建一个Queue对象 import queue# 创建一个队列实例 q queue.Queue(maxsize20) # 可选参数&#xff0c;默认为无限大&am…
阅读更多...
基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…
阅读更多...
【chrome扩展】简 Tab (SimpTab)‘每日一句名言’样式

【chrome扩展】简 Tab (SimpTab)‘每日一句名言’样式

背景&#xff1a;最初参考“每日诗词”发现总是那几句&#xff0c;可以更换API接口完成“每日一句名言” 声明&#xff1a;本人不会ajax及ccs样式&#xff0c;非专业人士&#xff0c;借助CHATGPT代码生成完成。请友善交流。 每一句名言API: "https://api.xygeng.cn/open…
阅读更多...
libVLC 提取视频帧

libVLC 提取视频帧

在前面的文章中&#xff0c;我们使用libvlc_media_player_set_hwnd设置了视频的显示的窗口。 libvlc_media_player_set_hwnd(vlc_mediaPlayer, (void *)ui.widgetShow->winId()); 如果我们想要提取每一帧数据&#xff0c;将数据保存到本地&#xff0c;该如何操作呢&#x…
阅读更多...
OPC UA遇见chatGPT

OPC UA遇见chatGPT

最近opc 基金会将召开一个会议&#xff0c;主题是”OPC UA meets IT“。由此可见&#xff0c;工业自动化行业也开始研究和评估chatGPT带来的影响了。 本文谈谈本人对OPC UA 与chatGPT结合的初步实验和思考。 构建OPC UA 信息模型 chatGPT 的确非常强大了&#xff0c;使用自然…
阅读更多...
用户登录时md5加密源码解析

用户登录时md5加密源码解析

首先&#xff0c;在登录的时候&#xff0c;将页面提交的密码password加密处理&#xff0c;即password DigestUtils.md5DigestAsHex(password.getBytes()); 接着按ctrl鼠标左键&#xff0c;进入md5DigestAsHex函数中进行查看&#xff1a; 可以发现&#xff0c;md5DigestAsHex函…
阅读更多...
Mysql底层原理六：InnoDB 数据页结构

Mysql底层原理六：InnoDB 数据页结构

1.行格式 1.1 Compact行格式 1.1.1 示意图 1.1.2 准备一下 1&#xff09;建表 mysql> CREATE TABLE record_format_demo (-> c1 VARCHAR(10),-> c2 VARCHAR(10) NOT NULL,-> c3 CHAR(10),-> c4 VARCHAR(10)-> ) CHARSETascii ROW_FORMATCOM…
阅读更多...
积木-蓝桥每日真题

积木-蓝桥每日真题

0积木 - 蓝桥云课 (lanqiao.cn) 题目描述 小明用积木搭了一个城堡。 为了方便&#xff0c;小明在搭的时候用的是一样大小的正方体积木&#xff0c;搭在了一个n行m列的方格图上&#xff0c;每个积木正好占据方格图的一个小方格。 当然&#xff0c;小明的城堡并不是平面的&#x…
阅读更多...
Discord注册教程：Discord刚注册就被封怎么办？附申诉教程！

Discord注册教程：Discord刚注册就被封怎么办？附申诉教程！

Discord如今在海外社交媒体平台中迅速崛起&#xff0c;许多社交媒体营销人员也纷纷利用其社群特性进行推广&#xff0c;Discord注册也就成为社媒营销人员必经之路。然而&#xff0c;很多人注册Discord账号时常常会想&#xff1a;“在国内使用Discord会封号吗&#xff1f;”事实…
阅读更多...
个推助力小米汽车APP实现智能用户触达，打造智能出行新体验

个推助力小米汽车APP实现智能用户触达，打造智能出行新体验

4月3日&#xff0c;小米SU7首批交付仪式在北京亦庄的小米汽车工厂总装车间举行&#xff0c;全国28城交付中心也同步开启首批交付。随着小米SU7系列汽车的正式发售和交付&#xff0c;小米汽车APP迎来了用户体量的爆发式增长。 小米汽车APP是小米汽车官方推出的手机应用&#xff…
阅读更多...
数据库面试题

数据库面试题

文章目录 事务未提交和提交事务的4大特征事务的隔离级别并发事务的问题MVVCundo log 和 redo log记录的隐藏字段readview&#xff08;读视图&#xff09; 事务未提交和提交 事务未提交时数据存在于数据库系统的缓存中&#xff0c;而在事务提交后&#xff0c;数据才会被写入到磁…
阅读更多...
多叉树题目：子树中标签相同的结点数

多叉树题目：子树中标签相同的结点数

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;子树中标签相同的结点数 出处&#xff1a;1519. 子树中标签相同的结点数 难度 5 级 题目描述 要求 给你一个树&#xff08;即一个连通的无向无环图…
阅读更多...
【Canvas技法】图解绘制圆弧的重要函数 arc(x,y,r,startAngle,endAngle,clockWise)

【Canvas技法】图解绘制圆弧的重要函数 arc(x,y,r,startAngle,endAngle,clockWise)

【一图释疑】 【绘制上图用代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>Html5/Canvas中绘制圆弧的重要函数 arc(x,y,r,startA…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023