关联分析 Apriori算法

2024-03-17 14:08
文章标签 算法 分析 关联 apriori

本文主要是介绍关联分析 Apriori算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在日常生活中,我们每个人都会去超市、商场、电商平台购物,每次的购物记录都会进入商家的用户数据库中。商家希望从这些海量的消费记录中,发现一些有价值的规律,来提高自己的盈利水平。

purchasing truck.png

当我们在Amazon上购买图书时,会经常看到下面两个提示:1.这些书会被消费者一起购买,并且价格上有一定的折扣;2.购买了这本书的人,也会购买其他书。Amazon对平台中海量的用户记录进行挖掘,发现了这些规律,然后将这些规律应用于实际销售工作当中。有数据显示,基于这种向用户进行主动推荐的营销方式,使得亚马逊的营业额增加了35%。我们的淘宝,京东也是一样的,比如我买了一件外套,店家就会向我推荐比较搭配的裤子和鞋子,并且告诉你同时购买会有一定的折扣优惠。
frequent bought.png
others bought recommendation.png

那么商家是如何发现这些商品会被一起购买的呢?

在生活中,当我们去超市买东西的时候,牛奶和面包会一起购买,啤酒和花生或者啤酒和炸鸡会一起购买,泡面和火腿肠或者泡面和辣条会被一起购买等等。这些现象在我们看来是显而易见的,不需要去探索的。拿电商京东来举个例子,其平台上的商品有几十万种甚至上百万种,用户数量有几千万甚至上亿人,这将会形成一个行为消费者,列为商品的大规模数据集,会被一起购买的商品也不止于两件。对于这样一个庞大的数据集,如果我们人工去挖掘其中的相关规律,那工作量将是非常的大。所以这项艰巨的任务,就得交给不怕辛苦的计算机来处理。

计算机是如何去发现商品之间的相关关系呢?

第一步,寻找频繁项集(Frequent Itemsets):发现那些购买频率高的商品。
第二步,探索关联规则(Association Rules):购买的商品之间必须存在强相关关系,比如牛奶和面包。

寻找频繁项集

假设下图是一家商店某一时刻的交易记录,transaction可以当做是不同的顾客,items是不同顾客的购物记录。接下来,我们需了解几个重要的概念:
项(item):在这份交易数据集中,单个的商品就被称为项,比如{Bread},{Butter},{Peanut}等。
项集(itemset):商品的组合就被称为项集,比如{Bread,Butter},{Chips,Jelly},{Bread,Milk}等。
交易记录(transaction):也就是我们的购物小票,比如1,2,3的每条交易记录。
数据集(dataset):所有的交易记录构成我们的数据集。下图所示是一份很小的数据集,用户数量和商品种类都非常的少。
支持度(support):购买特定商品的交易数占数据集中所有交易数量的比例,比如support({Bread}) = 6/8,support({Bread,Butter}) = 3/8。
transaction records.png
那么如何判断一件商品或商品组合是否会被频繁购买,我们需预先设定一个支持度标准,比如σ = 0.6,如果我们计算的某件商品支持度大于σ,则认为该件商品会被频繁购买。比如support({Jelly}) = 3/8 < 0.6,则果冻就不是一个会被频繁购买的商品。

寻找频繁项集的步骤

第一步:寻找单件商品频繁项集,分别计算每件商品的支持度,大于σ的就是频繁项。
第二步:对单件商品进行两两组合,再次遍历数据集,计算每一个组合的支持度,大于σ的就是频繁项集。
第三部:对上述项集进行组合,组合为含有3个元素的项集,再次遍历数据集,计算每一个组合的支持度,大于σ的就是频繁项集。
以此类推,找出含有4,5…n个元素的频繁项集。

上述的方法适合在数据量较小的时候,寻找频繁项集。如果我们的数据集很大,按照这样的方法去查找频繁项集就非常的耗时,因为每确定一个频繁项集,就需要对整个数据集遍历一遍。所以在此,我们使用Apriori算法,Apriori算法可以大大降低计算复杂度,提升计算效率。

Apriori算法没有数学推理,其核心思想有两点:
1.频繁项集的所有子集都是频繁项集。
2.非频繁项集的超集一定是非频繁项集。
举个例子来理解这两点核心思想,假设{1,2,3}是频繁项集,那么{1},{2},{3},{1,2},{1,3},{2,3}都是频繁项集。如果{1}是非频繁项集,那么{1,2},{1,3}都是非频繁项集。

Apriori算法是构造频繁项集的一种方法。Apriori算法的两个参数分别是最小支持度和数据集。该算法首先会产生所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉。然后对剩下的集合进行组合以生成包含两个元素的项集。接下来,再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行,直到所有项集都被去掉。

关联规则

找到频繁项集以后,接下来就需要验证频繁项集是否符合关联规则?当我们要向顾客推荐一件商品的时候,它必须符合两个条件,高频度(顾客购买的频率高)与强相关(商品之间的关联性很强)。
在上述交易数据集中,我们想向购买牛奶的顾客推荐黄油,则我们需要计算两个量:
support({Bread} - {Butter}) = 3/8
confidence({Bread} - {Butter}) = support({Bread} - {Butter})/support({Bread}) = 3/8 / 6/8 = 0.5
支持度support表示的是商品被购买的频率,confidence也叫置信度,表示的是两件商品之间相关性的强弱。
对于任意一次的推荐,两个指标(support,confidence)都必须满足设定的标准,才可以向顾客推荐。

数据挖掘的目标
从大量有噪声的数据中,挖掘出有趣的、有价值的、隐藏的规律。所以我们在做关联分析时,所分析出的规律最好是以前不被人所熟知、所注意的。如果我们分析了半天,分析出来了购买电脑的人,很有可能会购买机械键盘。当然这条规律不能算错,但是意义不大。

参考资料
1.机器学习实战,Petre Harrington。
2.数据挖掘-理论与算法,清华大学深圳研究生院博导,袁博。
3.数据分析与机器学习实战,同济大学计算机科学博士,唐宇迪。

这篇关于关联分析 Apriori算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三