你来啦,我们谈谈人生和理想分享 http://blog.sciencenet.cn/u/iggcas010 机器学习、数据挖掘

博文

机器学习之关联分析——Apriori算法一

已有 2030 次阅读 2018-6-19 23:53 |系统分类:科研笔记| 机器学习, 关联分析, 推荐算法, Apriori

 千呼万唤始出来,犹抱琵琶半遮面。

本文仍旧进展很慢,因为纯粹的说教毫无意义,不放代码的博文都是耍流氓。

本文暂时耍个流氓,明天或者后天将代码补上这里。因为这周比较忙,开始慌了。


一、Apriori到底是什么

学过反演理论的童鞋应该对A priori不陌生,对,就是‘一个先验信息’,先验信息在优化问题、数值求解中非常重要。如果先验信息找的好,非常省力,求解时间很短,找的不好可能得不到真实解,也可能无解。

 

1.1 先验信息到是什么?

我们对要求解的问题总会或多或少地知道‘一点’答案信息,比如双色球,蓝球肯定是1~16之间,红球肯定是在1~33之间,并且6个球不一样,顺序无要求。有人说,这是废话,知道这些东西还是中不了奖,哈哈,正常!再比如,我可以知道你要么单身,要么有对象,如果有对象,虽然我猜不到你对象是男女,但我能猜到你对象一般应该有两个胳膊、两条腿,不要说就你特殊哈,不耐烦了吧,其实先验信息就是依据惯例所知道的东西,关键在于怎么用。

 

在上次的博文中提到路边摊卖的早点,根据先验信息,我们知道五种食品的组合(项集)只有以下几种(不可能出现什么都不买,让老板给你打印个购物单,肯定怼死你,神经病”)。若采用暴力算法去算,经繁琐计算知道其项集组合应该有下面31种情况,分别是组合image.png,其和就是31。采用二项式系数展开定理我们知道,如果有n个项,那么所有的项集有?种可能(如果自己推不出,可以发邮件问我)


image.png

image.png


上图在排列组合过程中很费劲,因为要把所有的情况考虑到,因此暴力算法也称蛮力算法、穷举算法。如果某店铺有20种零食,它们的项集有多少种可能呢?来,心算一下,结果是1048576-1=1048575,你把这个数字给老板还不一巴掌啪死你。因此,我们要考虑实际情况,参照实际的售卖情况进行简单的统计,如果出现某个项集(比如{油条,豆浆})的概率较大(也就是频繁),那么我们可以确定出现{油条}{豆浆}的概率也很大,这就是所谓的Apriori原理,R U Clear?

这是什么鬼??它的逆否命题为,如果子集不频繁,那么该子集的超集也不频繁

1.2 超集是什么?

在上一个博文中,支持度的概念里面应该提到超集,支持度是出现的项集只要包含指定项集即可,也可能有其他项。此时,包含项集的集合就是超集,超集的概念与子集相对。咱玩点文字游戏:空集是任何非空集合的真子集,此时的非空集合就是空集的真超集。

任何集合都是它本身的子集,同样也是它本身的超集。(无聊

 

Apriori原理很强,如果儿子不肖,那么老子也不怎么样!是不是很强?!

 

咱回到初衷——关联分析,那么关联分析的目的就是寻找频繁项集,并发掘关联规则

那么Apriori到底有什么用,是不是还没发现?

回想一下怎么提出Apriori的,是不是因为项的组合——项集太多,而不能用暴力算法计算,又因为我们只关注频繁项集,对于那些不频繁的项集就不予考虑,而Apriori就是一种发现频繁项集的方法,如果{豆浆,香肠}是不频繁项集,那么它的超集也是不频繁的,其支持度无需再计算了。因此Apriori只需知道最小的支持度(这是需要知道的参数,需要指定,将大于该支持度的项集保留,而其他项集去掉。这就是Apriori的具体作用。

1.3 伪代码在这 

那么Apriori算法流程是:参考人民邮电出版社《机器学习实战》

1 首先生成所有单个物品的项集列表

2 遍历数据集中所有项集,将不满足最小支持度的项集去掉

3 对剩下的项集组合,生成包含两个元素的项集

4 重新遍历数据集,去掉不满足最小支持度的项集

5 重复上述过程,直到所有项集都被去掉


代码在哪里?欲知后事如何,且听下回分解。

(还在调代码中……)



http://blog.sciencenet.cn/blog-1966190-1119829.html

上一篇:python3.6.5中的map函数
下一篇:等比数列求和——竟然是一道面试题?

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

全部作者的精选博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-7-22 21:04

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部