当前课程知识点:互联网大规模数据分析技术 > 第二章 关联规则 > 第4讲 Apriori算法的改进与兴趣度度量 > 第4讲 Apriori算法的改进与兴趣度度量
同学们好
欢迎来到
互联网大规模数据分析技术课堂
我是这节课的主讲教师张蕊
来自武汉理工大学
这节课我们一起来了解一下
Apriori算法的改进与兴趣度度量
Ariori算法面临的主要挑战是什么
第一,需要扫描数数据库多次
第二,需要生成的候选项集数量巨大
第三,对项集的支持度计算代价很高
那对他的改进也是从这3个方面着手的
第一,减少对数据库扫描的次数
第二,减少候选项集的生成数量
第三,更好的去进行支持度计数的计算
下面我们来看几个典型的技术
比如说通过对数据库进行划分的办法
可以仅仅对数据库扫描两次
它的思想仍然是利用Apriori性质
如果一个项集在整个数据库中是频繁的
那它至少应该在
这个数据库的一个分区中是频繁的
那么我们就可以
扫描数据库两次来发现频繁项集
第一次,我们将数据库进行划分
然后发现在每个分区中的局部频繁模式
具体来说
将事务数据库划分成多个非重叠的分区
给定一个相对最小支持度阈值
那个百分比
那么用这个百分比
乘以整个数据库的事务的个数
得到它的最小支持度计数
然后对这个数据库的每个分区
也用这个百分比乘以
这个划分当中的事务条数
这样会得到这个分区的局部支持度计数
通过这样的方式
我们就可求出
每个分区当中的局部频繁项集
而这些分区都是可以直接放入内存的
以保证可以一次高效读完
因为成为全局的频繁项集
必然至少出现一个分区中
所以第二次扫描以确定
这些局部频繁项集的支持度
从而得到全局的频繁项集
第二种办法可以利用哈希
特别是在寻找频繁2-项集时
因为候选2-项集通常来说会比较大
利用哈希技术
可以将候选2项集哈希到对应的桶中
并对每个桶中的项集个数进行计数
比如
频繁1-项集是abde
然后ab ad ae出现在一个桶中
bd be de出现在另外一个桶中等等
如果ab ad ae这个桶里面的所有项集
加起来的出现次数才35
低于给定的支持度阈值
那么
这个桶中的所有项集都不可能是频繁的
那通过这种办法
就可以压缩需要考察的候选项集的个数
第三种办法是取样
不在原始数据库上去挖掘频繁项集
而是对原始数据进行取样
在样本数据集上进行频繁项集的挖掘
当然
这可能漏掉一些全局的频繁项集
但可以通过一些办法来弥补
比如
在样本数据集上
选取的支持度阈值小一点
或者再次扫描整个数据库等等
这个办法对于精度要求不是那么高
同时对计算代价很敏感的场合很适合
最后一个我们要介绍的方法
是动态项集计数
和Apriori算法不一样
不是每次扫描数据库前
确定所有的候选
而是动态添加后选项集
比如
只有当A和D都频繁时才将AD作为候选
只有当BCD的所有子集
都判断为频繁时才将BCD作为候选等等
相对Apriori算法来说
这种办法需要的数据库扫描次数比较少
时至今天
Apirori算法仍在不断的改进中
对于大规模数据的频繁项集发现
也有工作将Apriori算法
用MapReduce计算模型
或在Spark等大数据平台上实现
感兴趣的同学可以去了解下
下面我们来了解一下
更多的兴趣度度量
首先我们来看一个这样的例子
既打篮球又吃麦片的有2000人
只吃麦片不打篮球的1750人
也就是,吃麦片的有3750人
不吃麦片打篮球的有1000人
不吃麦片也不打篮球的,有250人
这时候我们可能发现
这样一条关联规则
打篮球推出吃麦片
这条规则的支持度是多少呢
既打篮球又吃麦片的有2000人
一共5000人,所以支持度是40%
可信度是多少呢
那就是要求打篮球的情况下
吃麦片的条件概率
打篮球的一共是3000人
2000除以3000,等于66.7%
看上去这个支持度
和可信度都挺高的
如果这是对的
那麦片厂商可以在打篮球的人当中
针对性地促销了
但事实上
这个规则是有问题的
我们看下,所有学生
不管他打不打篮球
吃麦片的概率是多少呢
3750除以5000,等于75%
高于66.7%
换句话说
如果一个人打篮球
她吃麦片的概率其实会降低
也就是说,打篮球
推出不吃麦片
这个规则可能更准确
虽然这个规则的支持度为
1000除以5000,只有20%
可信度为1000除以3000,只有33.3%
尽管这个规则的支持度
和可信度都比较低
但它更能反映内在的规律
那我们可以换一种方式来衡量兴趣度
这里我们用考虑lift
提升度这个度量
它是用两个项集的并集的出现概率
除以两个项集单独出现概率的乘积
如果提升度小于一
表示负相关
大于一表示正相关
在这里我们发现
打篮球和吃麦片的lift值
计算出来是0.89
因此他们是负相关的
而打篮球和不吃麦片的lift值
算出来是11.33
他们才是正相关的
所以我们发现
总用支持度和可信度
这种看上去很客观的指标
来衡量兴趣度
并不一定总是正确的
有时还可能会误导我们
刚才打篮球和吃麦片是一个例子
这里还有一个
买核桃推出买牛奶
这个可信度是80%
可是不买核桃
直接去买牛奶的人反而有85%
那这又是一个违背事实的例子
刚才我们用lift度量解决了一些
支持度和可信度不能识别的情况
那是不是lift度量就是万能的呢
答案是否定的
衡量兴趣度的指标大概有20多种
这里列举出来了一些
可以看见
每个度量都有自己的特征
他不可能具有所有的优点
而在这些特性里面
非常重要的一个特性是
null-invariant零不变
零事务指的是
不包含任何考察项的事务
零不变指的是结果不受零事务影响
比如在这个表格当中
既不买牛奶也不买咖啡
MC取非
这种就是零事务
数据集一和数据集二
在零事务这一块有很大的变化
那我们发现卡方检验
和lift的计算结果变化很大
尽管其他的事务条数没有变
而后面的5个度量就是零不变的
更多对这方面的讨论
有兴趣的同学可以去看一看相关论文
本节课的内容到此结束
谢谢大家的观看
-第1讲 大数据与数据挖掘概述
-第2讲 频繁项集和关联规则的基本概念
-第3讲 Apriori算法
-第4讲 Apriori算法的改进与兴趣度度量
-第5讲 分类的基本概念
-第6讲 决策树
--第6讲 决策树
-第7讲 简单贝叶斯分类
-第8讲 聚类的基本概念
-第9讲 K-Means & K-Medoids Clustering
--第9讲 K-Means & K-Medoids Clustering
-第四章 聚类算法--习题
-第10讲 大数据处理平台Hadoop
-第11讲 MapReduce编程
-第12讲 大数据处理平台Spark
-第13讲 NoSQL数据库
-第14讲 Web信息检索简介
-第15讲 信息检索之倒排索引
-第16讲 信息检索之TFIDF
--Video
-第17讲 信息检索之相似度排序
-第18讲 Web搜索之链接分析
-第19讲 Web搜索之PageRank
-第20讲 Lucene信息检索平台
-第七章 Web链接分析--习题
-第21讲 推荐系统简介
-第22讲 推荐系统之协同过滤
-第23讲 Mahout数据挖掘平台
-第24讲 信息过滤评价体系
-第八章 推荐系统--习题一
-第八章 推荐系统--习题二
-综合编程题





