本文主要是介绍关联分析 Apriori算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在日常生活中,我们每个人都会去超市、商场、电商平台购物,每次的购物记录都会进入商家的用户数据库中。商家希望从这些海量的消费记录中,发现一些有价值的规律,来提高自己的盈利水平。
当我们在Amazon上购买图书时,会经常看到下面两个提示:1.这些书会被消费者一起购买,并且价格上有一定的折扣;2.购买了这本书的人,也会购买其他书。Amazon对平台中海量的用户记录进行挖掘,发现了这些规律,然后将这些规律应用于实际销售工作当中。有数据显示,基于这种向用户进行主动推荐的营销方式,使得亚马逊的营业额增加了35%。我们的淘宝,京东也是一样的,比如我买了一件外套,店家就会向我推荐比较搭配的裤子和鞋子,并且告诉你同时购买会有一定的折扣优惠。
那么商家是如何发现这些商品会被一起购买的呢?
在生活中,当我们去超市买东西的时候,牛奶和面包会一起购买,啤酒和花生或者啤酒和炸鸡会一起购买,泡面和火腿肠或者泡面和辣条会被一起购买等等。这些现象在我们看来是显而易见的,不需要去探索的。拿电商京东来举个例子,其平台上的商品有几十万种甚至上百万种,用户数量有几千万甚至上亿人,这将会形成一个行为消费者,列为商品的大规模数据集,会被一起购买的商品也不止于两件。对于这样一个庞大的数据集,如果我们人工去挖掘其中的相关规律,那工作量将是非常的大。所以这项艰巨的任务,就得交给不怕辛苦的计算机来处理。
计算机是如何去发现商品之间的相关关系呢?
第一步,寻找频繁项集(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。
那么如何判断一件商品或商品组合是否会被频繁购买,我们需预先设定一个支持度标准,比如σ = 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算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!