20240324-2-频繁模式FrequentPattern

频繁模式(frequent pattern)

在这里插入图片描述

频繁模式一般是指频繁地出现在数据集中的模式。这种频繁模式和关联规则是数据挖掘中想要挖掘的知识。我们都知道一个很有趣的故事,就是啤酒和尿布的故事,

在某些特定的情况下,“啤酒”与“尿布”两件看上去毫无关系的商品,会经常出现在同一个购物篮中,且大多出现在年轻的父亲身上。

分析背后原因是,在美国有婴儿的家庭中,一般是母亲在家中照看婴儿,年轻的父亲去超市买尿布。父亲在购买尿布的同时,往往会顺便为自己购买啤酒。

由此,沃尔玛就在卖场尝试将啤酒与尿布摆放在相同区域,让年轻的父亲可以同时找到这两件商品,并很快地完成购物,从而极大提升商品销售收入。

数据挖掘就是想要挖掘出这种有趣的模式,可以称做频繁模式和关联规则的挖掘,一般情况下使用支持度(support)和置信度(confidence)来表示关联的程度,领域的专家设置最小支持度和最小置信度阈值,如果某个模式大于最小支持度和最小置信度,就认为是频繁模式。

为了挖掘这种模式,一般常用的有两种算法:

  1. Apriori
  2. Fp-tree

在介绍这两个算法之前需要给出一些定义:

  1. A=>B的支持度:
    s u p p o r t ( A = > B ) = p ( A ∪ B ) (1) support(A=>B)=p(A\cup B) \tag{1} support(A=>B)=p(AB)(1)
  2. A=>B的置信度:
    c o n f i d e n c e ( A = > B ) = P ( B ∣ A ) confidence(A=>B)=P(B|A) confidence(A=>B)=P(BA)
    = s u p p o r t ( A ∪ B ) s u p o o r t ( A ) = s u p p o r t c o u n t ( A ∪ B ) s u p o o r t c o u n t ( A ) (2) =\frac{support(A \cup B)}{supoort(A)}=\frac{support_count(A \cup B)}{supoort_count(A)} \tag{2} =supoort(A)support(AB)=supoortcount(A)supportcount(AB)(2)
  3. 一般关联规则的挖掘有两步过程:
    • 找出所有的频繁项集: 每一个频繁出现的次数大于等于最小支持度技术min_sup.
    • 由频繁相机产生强关联规则: 这些规则必须满足最小支持度和最小置信度.

Apriori

Apriori通过限制候选产生发现频繁项集,它是为布尔关联规则挖掘频繁项集的原创性算法. 根据先验知识(频繁项集的所有非空子集也一定是频繁的).Apriri算法使用一种称为逐层搜索的迭代过程,其中k项集用于探索(k+1)项集.
Apriori主要有两步完成: 连接步和剪枝步。
这个算法给出一个例子更容易理解:
解答(详细过程请参考《数据挖掘概念与技术第三版》

FPTree

FPTree是基于频繁模式的增长,不产生候选挖掘频繁项集的挖掘方法,
使用频繁模式增长方法,我们重新考察例图6.2事务数据库 D 的挖掘。
数据库的第一次扫描与 Apriori 相同,它导出频繁项(1-项集)的集合,并得到它们的支持度计数(频繁性)。设最小支持度计数为 2。频繁项的集合按支持度计数的递减序排序。结果集或表记作 L 。这样,我们有:
L = [I2:7, I1:6, I3:6, I4:2, I5:2]。
FP-树构造如下:

  1. 首先,创建树的根结点,用“null”标记。
  2. 二次扫描数据库 D。每个事务中的项按 L 中的次序处理(即,根据递减支持度计数排序)并对每个事务创建一个分枝.
  3. 例如,
    第一个事务“T100: I1, I2, I5”按 L 的次序包含三个项{ I2, I1, I5},导致构造树的第一个分
    枝<(I2:1), (I1:1), (I5:1)>。该分枝具有三个结点,其中,I2 作为根的子女链接,I1 链接到 I2,
    I5 链接到 I1。第二个事务 T200 按 L 的次序包含项 I2 和 I4,它导致一个分枝,其中,I2 链接到根,
    I4 链接到 I2。然而,该分枝应当与 T100 已存在的路径共享前缀。这样,我们将结点 I2 的计
    数增加 1,并创建一个新结点(I4:1),它作为(I2:2)的子女链接。一般地,当为一个事务考虑增加
    分枝时,沿共同前缀上的每个结点的计数增加 1,为随在前缀之后的项创建结点并链接。
  4. 为方便树遍历,创建一个项头表,使得每个项通过一个结点链指向它在树中的出现。扫描所有
    的事务之后得到的树展示在图 6.8 中,附上相关的结点链。这样,数据库频繁模式的挖掘问题就转换成挖掘 FP-树问题.
  5. 根据fp tree得到频繁项集,根据支持度计数依次考虑每一个满足的元素,首先考虑计数最小的ID I5. 从根节点遍历所有到I5的路径,记录这个路径作为条件模式基,之后根据最小支持度得到条件Fp-tree,最后产生频繁项集.

核心公式

  1. 如何评估哪些模式是有趣的?

相关规则是A=>B[support, confidence]进一步扩充到相关分析A=>B[support, confidence, correlation],
常用的相关性度量:

  • 提升度(lift),计算公式如下:
    l i f t ( A , b ) = p ( A ∪ B ) p ( A ) p ( B ) = P ( B ∣ A ) p ( B ) = c o n f ( A = > B ) s u p ( B ) (3) lift(A,b)=\frac{p(A \cup B)}{p(A)p(B)}=\frac{P(B|A)}{p(B)}=\frac{conf(A=>B)}{sup(B)} \tag{3} lift(A,b)=p(A)p(B)p(AB)=p(B)P(BA)=sup(B)conf(A=>B)(3)
  • 使用 χ 2 \chi^2 χ2进行相关分析
  1. 常用的模式评估度量
  • 全置信度(all_confidence)
    a l l c o n f ( A , B ) = A ∪ B m a x { s u p ( A ) , s u p ( B ) } = m i n { p ( A ∣ B ) , p ( B ∣ A ) } (4) all_conf(A,B)=\frac{A \cup B}{max\{sup(A),sup(B)\}}=min\{p(A|B),p(B|A)\} \tag{4} allconf(A,B)=max{sup(A),sup(B)}AB=min{p(AB),p(BA)}(4)
  • 最大置信度(max_confidence)
    m a x c o n f ( A , B ) = m a x { P ( A ∣ B ) , p ( B ∣ A ) } (5) max_conf(A,B)=max\{P(A|B),p(B|A)\} \tag{5} maxconf(A,B)=max{P(AB),p(BA)}(5)
  • Kulczynski(Kulc)度量
    K u l c ( A , B ) = 1 2 ( P ( A ∣ B ) + P ( B ∣ A ) ) (6) Kulc(A,B)=\frac{1}{2}(P(A|B)+P(B|A)) \tag{6} Kulc(A,B)=21(P(AB)+P(BA))(6)
  • 余弦度量
    c o s i n e ( A , B ) = P ( A ∪ B ) P ( A ) × P ( B ) = s u p ( A ∪ B ) ( s u p ( A ) × s u p ( B ) ) = P ( A ∣ B ) × P ( B ∣ A ) (7) cosine(A,B)=\frac{P(A\cup B)}{\sqrt{P(A) \times P(B)}}=\frac{sup(A \cup B)}{\sqrt{(sup(A) \times sup(B))}}=\sqrt{P(A|B)\times P(B|A)} \tag{7} cosine(A,B)=P(A)×P(B) P(AB)=(sup(A)×sup(B)) sup(AB)=P(AB)×P(BA) (7)
    对于指示有趣的模式联系,全置信度、最大置信度、Kulczynsji和余弦哪个最好? 为了回答这个问题,引进不平衡比(Imbalance Ratio, IR)
    I R ( A , B ) = ∣ s u p ( A ) − s u p ( B ) ∣ s u p ( A ) + s u p ( B ) − s u p ( A ∪ B ) (8) IR(A,B)=\frac{|sup(A)-sup(B)|}{sup(A)+sup(B)-sup(A\cup B)} \tag{8} IR(A,B)=sup(A)+sup(B)sup(AB)sup(A)sup(B)(8)

算法十问

  1. 强规则一定是有趣的吗?

不一定,规则是否有兴趣可能用主观或客观的标准来衡量。最终,只有用户能够确定规则是否是有趣的,并且这种判断是主观的,因不同用户而异。

  1. 如何提高Apriori算法的效率?
  • 事务压缩(压缩进一步迭代扫描的事务数):不包含任何 k-项集的事务不可能包含任何(k+1)-项集。这样,这种事务在其后的考虑时,可以加上标记或删除,因为为产生 j-项集(j > k),扫描数据库时不再需要它们。
  • 基于散列的技术(散列项集计数):一种基于散列的技术可以用于压缩候选 k-项集 Ck (k >1)。
    划分(为找候选项集划分数据):可以使用划分技术,它只需要两次数据库扫描,以挖掘频繁项集。
  • 选样(在给定数据的一个子集挖掘):选样方法的基本思想是:选取给定数据库 D 的随机样本 S,然后,在 S 而不是在 D 中搜索频繁项集。用这种方法,我们牺牲了一些精度换取了有效性。
  • 动态项集计数(在扫描的不同点添加候选项集):动态项集计数技术将数据库划分为标记开始点的块。
  1. Apriori算法的优缺点?
  1. 优点:
  • 简单、易理解
  • 数据要求低。
  1. 缺点:
  • 在每一步产生候选项目集时循环产生的组合过多,没有排除不应该参与组合的元素。
  • 每次计算项集的支持度时,都对数据库中的全部记录进行了一遍扫描比较,如果是一个大型的数据库时,这种扫描会大大增加计算机的I/O开销。
  1. 改进:
  • 利用建立临时数据库的方法来提高Apriori算法的效率。
  • Fp-tree 算法。以树形的形式来展示、表达数据的形态;可以理解为水在不同河流分支的流动过程。
  • 垂直数据分布。相当于把原始数据进行行转列的操作,并且记录每个元素的个数。
  1. FPtree vs Apriori算法

FP-tree算法相对于Apriori算法,时间复杂度和空间复杂都有了显著的提高。但是对海量数据集,时空复杂度仍然很高,此时需要用到数据库划分等技术。

面试真题

  1. 简述Apriori算法的思想,谈谈该算法的应用领域并举例?
    思想:其发现关联规则分两步,第一是通过迭代,检索出数据源中所有烦琐项集,即支持度不低于用户设定的阀值的项即集,第二是利用第一步中检索出的烦琐项集构造出满足用户最小信任度的规则,其中,第一步即挖掘出所有频繁项集是该算法的核心,也占整个算法工作量的大部分。在商务、金融、保险等领域皆有应用。在建筑陶瓷行业中的交叉销售应用,主要采用了Apriori算法.

  2. 简述FPtree的原理和Apriori的不同?

  3. 豆瓣电影数据集关联规则挖掘?
    如果让你分析电影数据集中的导演和演员信息,从而发现两者之间的频繁项集及关联规则,你会怎么做?

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

SCP 从Linux快速下载文件到Windows本地

需求&#xff1a;通过mobaxterm将大文件拖动到windows本地速度太慢。 环境&#xff1a;本地是Windows&#xff0c;安装了Git。 操作&#xff1a;进入文件夹内&#xff0c;鼠标右键&#xff0c;点击Git Bash here&#xff0c;然后输入命令即可。这样的话&#xff0c;其实自己本…

java农家乐旅游管理系统springboot+vue

实现了一个完整的农家乐系统&#xff0c;其中主要有用户表模块、关于我们模块、收藏表模块、公告信息模块、酒店预订模块、酒店信息模块、景区信息模块、景区订票模块、景点分类模块、会员等级模块、会员模块、交流论坛模块、度假村信息模块、配置文件模块、在线客服模块、关于…

基于深度学习的番茄成熟度检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;在本博客中&#xff0c;我们深入探讨了基于YOLOv8/v7/v6/v5的番茄成熟度检测系统。核心技术基于YOLOv8&#xff0c;同时融合了YOLOv7、YOLOv6、YOLOv5的算法&#xff0c;对比了它们在性能指标上的差异。本文详细介绍了国内外在此领域的研究现状、数据集的处理方…

9.图像中值腐蚀膨胀滤波的实现

1 简介 在第七章介绍了基于三种卷积前的图像填充方式&#xff0c;并生成了3X3的图像卷积模板&#xff0c;第八章运用这种卷积模板进行了均值滤波的FPGA实现与MATLAB实现&#xff0c;验证了卷积模板生成的正确性和均值滤波算法的MATLAB算法实现。   由于均值滤波、中值滤波、腐…

Flask Python:如何获取不同请求方式的参数

目录 前言 1. 获取GET请求中的查询参数 2. 获取POST请求中的表单数据 3. 获取JSON数据 总结 前言 在使用Flask开发Web应用时&#xff0c;我们经常需要获取不同请求方式的参数。Flask提供了多种方式来获取不同请求方式的参数&#xff0c;包括GET请求中的查询参数、POST请求…

Spring Boot Mockito (二)

Spring Boot Mockito (二) 基于第一篇Spring Boot Mockito (一) 这篇文章主要是讲解Spring boot 与 Mockito 集成持久层接口层单元测试。 1. 引入数据库 h2及其依赖包 <dependency><groupId>com.h2database</groupId><artifactId>h2</artifactId…

JavaScript基础代码练习之冒泡排序

一、要求对一个数组进行冒泡排序&#xff0c;并将排序后的结果输出到控制台。在代码中&#xff0c;数组 arr 包含了一组数字&#xff0c;然后使用嵌套的循环来进行冒泡排序。 二、编写代码 <!DOCTYPE html> <html lang"en"><head><meta chars…

NOI - OpenJudge - 2.5基本算法之搜索 - 1490:A Knight‘s Journey - 超详解析(含AC代码)

点赞关注吧~ 1490:A Knights Journey 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 Background The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. When…

《QT实用小工具·九》设备按钮控件

1、概述 源码放在文章末尾 该项目实现了设备按钮控件&#xff0c;主要包含如下功能&#xff1a; 可设置按钮样式 圆形、警察、气泡、气泡2、消息、消息2。可设置按钮颜色 布防、撤防、报警、旁路、故障。可设置报警切换及对应报警切换的颜色。可设置显示的防区号。可设置是否…

实验报告答案

基本任务&#xff08;必做&#xff09; 先用普通用户&#xff08;自己的姓名拼音&#xff09;登录再操作 编程有代码截图和执行过程结果截图 代写获取&#xff1a; https://laowangall.oss-cn-beijing.aliyuncs.com/studentall.pdf 1. Linux的Shell编程 &#xff08;1&am…

实操:Dropzone.js实现文件上传

&#x1f3e0;官网 点我前往 &#x1f953;依赖 <script src"https://unpkg.com/dropzone5/dist/min/dropzone.min.js"></script> <link rel"stylesheet" href"https://unpkg.com/dropzone5/dist/min/dropzone.min.css" type&…

unity工程输出的log在哪里?

在编辑器里进行活动输出的log位置&#xff1a; C:\Users\username\AppData\Local\Unity\Editor\Editor.log ------------------------------------ 已经打包完成&#xff0c;形成的exe运行后的log位置&#xff1a; C:\Users\xxx用户\AppData\LocalLow\xx公司\xx项目

【Qt】事件

目录 一、介绍 二、进入离开事件 三、鼠标事件 3.1 鼠标单击事件 3.2 鼠标释放事件 3.3 鼠标双击事件 3.4 鼠标移动事件 3.5 滚轮事件 四、按键事件 4.1 单个按键 4.2 组合按键 五、定时器 5.1 QTimerEvent类 5.2 QTimer类 5.3 获取系统日期及时间 六、事件分…

【游戏逆向】逆向基础----CE使用和基础

windows逆向中&#xff0c;CE扮演着不可或缺的角色。 其根本原因是&#xff0c;上手简单,功能强大&#xff0c;提供多方位的突破口。 点击小电脑图标&#xff0c; 选择我们想要调试的程序&#xff0c; 就可以附加调试了。 很多的游戏保护驱动以及反调试手段&#xff0c;都针对…

澳门媒体发稿套餐9个增长技巧解析-华媒舍

澳门作为一个国际知名的旅游胜地&#xff0c;拥有丰富的媒体资源。利用澳门媒体发稿&#xff0c;既可以提升品牌知名度&#xff0c;又可以吸引更多的目标受众。下面是9个利用澳门媒体发稿套餐的增长技巧&#xff0c;帮助你充分发挥媒体的作用&#xff0c;实现品牌的增长。 1. 制…

机器学习的模型校准

背景知识 之前一直没了解过模型校准是什么东西&#xff0c;最近上班业务需要看了一下&#xff1a; 模型校准是指对分类模型进行修正以提高其概率预测的准确性。在分类模型中&#xff0c;预测结果通常以类别标签形式呈现&#xff08;例如&#xff0c;0或1&#xff09;&#xf…

注意力机制篇 | YOLOv8改进之添加LSKAttention大核卷积注意力机制 | 即插即用,实现有效涨点

前言:Hello大家好,我是小哥谈。LSKAttention是一种注意力机制,它在自然语言处理领域中被广泛应用。LSKAttention是基于Transformer模型中的Self-Attention机制进行改进的一种变体。在传统的Self-Attention中,每个输入序列中的元素都会与其他元素进行交互,以获取全局的上下…

Linux 命令 top 详解

1 top命令介绍 Linux系统中&#xff0c;Top命令主要用于实时运行系统的监控&#xff0c;包括Linux内核管理的进程或者线程的资源占用情况。这个命令对所有正在运行的进程和系统负荷提供不断更新的概览信息&#xff0c;包括系统负载、CPU利用分布情况、内存使用、每个进程的内容…

开源量化交易研究框架Hikyuu

Hikyuu Quant Framework 是一款基于 C/Python 的开源量化交易研究框架&#xff0c;用于策略分析及回测。其核心思想基于当前成熟的系统化交易方法&#xff0c;将整个系统化交易抽象为由市场环境判断策略、系统有效条件、信号指示器、止损 / 止盈策略、资金管理策略、盈利目标策…

分享three.js实现粒子背景

three.js中粒子效果的实现方式大概分为三种&#xff1a; 1、Javascript直接计算粒子的状态变化&#xff0c;即基于CPU实现&#xff1b; 2、Javascript通知顶点着色器粒子的生命周期&#xff0c;由顶点着色器运行&#xff0c;即基于GPU实现&#xff1b; 3、粒子生成与状态维护全…