Apriori算法是关联规则挖掘中很基础也很经典的一个算法

2024-05-09 08:48

本文主要是介绍Apriori算法是关联规则挖掘中很基础也很经典的一个算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先,Apriori算法是关联规则挖掘中很基础也很经典的一个算法。

所以做如下补充:

关联规则:形如X→Y的蕴涵式,其中, X和Y分别称为关联规则的先导(antecedent或left-hand-side, LHS)和后继(consequent或right-hand-side, RHS) 。其中,关联规则XY,存在支持度和信任度。

支持度:规则前项LHS和规则后项RHS所包括的商品都同时出现的概率,可以理解为LHS和RHS商品的交易次数/总交易次数。

置信度:在所有的购买了左边商品的交易中,同时又购买了右边商品的交易机率,包含规则两边商品的交易次数/包括规则左边商品的交易次数。

提升度:(有这个规则和没有这个规则是否概率会提升,规则是否有价值):无任何约束的情况下买后项的交易次数/置信度。注意:提升度必须大于1才有意义

(截图来源:Apriori算法原理总结 - 刘建平Pinard - 博客园)


进入正题啦~

Apriori的算法思想

在Apriori算法z中,我们通常使用支持度来作为我们判断频繁项集的标准。

Apriori算法的目标是找到最大的K项频繁集

补充:{频繁项集产生:其目标是发现满足最小支持度阈值的所有项集,这些项集称作频繁项集(frequent itemset)}

Apriori定律1:如果一个集合是频繁项集,则它的所有子集都是频繁项集。

举个栗子:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。

Apriori定律2:如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。

举个栗子:假设集合{A}不是频繁项集,即A出现的次数小于 min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。


Apriori的算法步骤

输入:数据集合D,支持度阈值α

    输出:最大的频繁k项集

    1)扫描整个数据集,得到所有出现过的数据,作为候选频繁1项集。k=1,频繁0项集为空集。

    2)挖掘频繁k项集

      a) 扫描数据计算候选频繁k项集的支持度

      b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空,则直接返回频繁k-1项集的集合作为算法结果,算法结束。如果得到的频繁k项集只有一项,则直接返回频繁k项集的集合作为算法结果,算法结束。

      c) 基于频繁k项集,连接生成候选频繁k+1项集。

    3) 令k=k+1,转入步骤2。


敲脑壳 重点来啦~

Apriori的算法的应用

下面这个表格是代表一个事务数据库D,

其中最小支持度为50%,最小置信度为70%,求事务数据库中的频繁关联规则。

 apriori算法的步骤如下所示:

  (1)生成候选频繁1-项目集C1={{面包},{牛奶},{啤酒},{花生},{尿布}}。

  (2)扫描事务数据库D,计算C1中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为3,3,3,1,2,事务数据库D的项目集总数为4,因此可得出C1中每个项目集的支持度分别为75%,75%,75%,25%,50%。根据最小支持度为50%,可以得出频繁1-项目集L1={{面包},{牛奶},{啤酒},{尿布}}。

  (3)根据L1生成候选频繁2-项目集C2={{面包,牛奶},{面包,啤酒},{面包,尿布},{牛奶,啤酒},{牛奶,尿布},{啤酒,尿布}}。

  (4)扫描事务数据库D,计算C2中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为3,2,1,2,1,2,事务数据库D的项目集总数为4,因此可得出C2中每个项目集的支持度分别为75%,50%,25%,50%,25%,50%。根据最小支持度为50%,可以得出频繁2-项目集L2={{面包,牛奶},{面包,啤酒},{牛奶,啤酒},{啤酒,尿布}}。

  (5)根据L2生成候选频繁3-项目集C3={{面包,牛奶,啤酒},{面包,牛奶,尿布},{面包,啤酒,尿布},{牛奶,啤酒,尿布}},由于C3中项目集{面包,牛奶,尿布}中的一个子集{牛奶,尿布}是L2中不存在的,因此可以去除。同理项目集{面包,啤酒,尿布}、{牛奶,啤酒,尿布}也可去除。因此C3={面包,牛奶,啤酒}。

  (6)扫描事务数据库D,计算C3中每个项目集在D中的支持度。从事务数据库D中可以得出每个项目集的支持数分别为2,事务数据库D的项目集总数为4,因此可得出C2中每个项目集的支持度分别为50%。根据最小支持度为50%,可以得出频繁3-项目集L3={{面包,牛奶,啤酒}}。

  (7)L=L1UL2UL3={{面包},{牛奶},{啤酒},{尿布},{面包,牛奶},{面包,啤酒},{牛奶,啤酒},{啤酒,尿布},{面包,牛奶,啤酒}}。

  (8)我们只考虑项目集长度大于1的项目集,例如{面包,牛奶,啤酒},它的所有非真子集{面包},{牛奶},{啤酒},{面包,牛奶},{面包,啤酒},{牛奶,啤酒},分别计算关联规则{面包}—>{牛奶,啤酒},{牛奶}—>{面包,啤酒},{啤酒}—>{面包,牛奶},{面包,牛奶}—>{啤酒},{面包,啤酒}—>{牛奶},{牛奶,啤酒}—>{面包}的置信度,其值分别为67%,67%,67%,67%,100%,100%。由于最小置信度为70%,可得},{面包,啤酒}—>{牛奶},{牛奶,啤酒}—>{面包}为频繁关联规则。也就是说买面包和啤酒的同时肯定会买牛奶,买牛奶和啤酒的同时也是会买面包。

由这个例子可以看出apriori主要是根据 最小支持度来判断的 逐步递进

but~这其中也有一些缺点: 从算法的步骤可以看出,Aprior算法每轮迭代都要扫描数据集,因此在数据集很大,数据种类很多的时候,算法效率很低。

参考:关于apriori算法的一个简单的例子 - 宁静之家 - 博客园


附相关解释图:

数据挖掘十大算法之Apriori详解 - 白马负金羁 - CSDN博客



作者:李_颖Biscuit
链接:https://www.jianshu.com/p/26d61b83492e
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这篇关于Apriori算法是关联规则挖掘中很基础也很经典的一个算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2

Nginx路由匹配规则及优先级详解

《Nginx路由匹配规则及优先级详解》Nginx作为一个高性能的Web服务器和反向代理服务器,广泛用于负载均衡、请求转发等场景,在配置Nginx时,路由匹配规则是非常重要的概念,本文将详细介绍Ngin... 目录引言一、 Nginx的路由匹配规则概述二、 Nginx的路由匹配规则类型2.1 精确匹配(=)2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面(Facade),不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4

Spring Boot集成Logback终极指南之从基础到高级配置实战指南

《SpringBoot集成Logback终极指南之从基础到高级配置实战指南》Logback是一个可靠、通用且快速的Java日志框架,作为Log4j的继承者,由Log4j创始人设计,:本文主要介绍... 目录一、Logback简介与Spring Boot集成基础1.1 Logback是什么?1.2 Sprin

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言:1.基本查询回顾:1.1.查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为大写的J1.2.按照部门