当前课程知识点:互联网大规模数据分析技术 >  第二章 关联规则 >  第4讲 Apriori算法的改进与兴趣度度量 >  第4讲 Apriori算法的改进与兴趣度度量

返回《互联网大规模数据分析技术》慕课在线视频课程列表

第4讲 Apriori算法的改进与兴趣度度量在线视频

下一节:第5讲 分类的基本概念

返回《互联网大规模数据分析技术》慕课在线视频列表

第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讲 大数据与数据挖掘概述

--第1讲 大数据与数据挖掘概述

第二章 关联规则

-第2讲 频繁项集和关联规则的基本概念

--第2讲 频繁项集和关联规则的基本概念

-第3讲 Apriori算法

--第3讲 Apriori算法

-第4讲 Apriori算法的改进与兴趣度度量

--第4讲 Apriori算法的改进与兴趣度度量

第三章 分类算法

-第5讲 分类的基本概念

--第5讲 分类的基本概念

-第6讲 决策树

--第6讲 决策树

-第7讲 简单贝叶斯分类

--第7讲 简单贝叶斯分类

第四章 聚类算法

-第8讲 聚类的基本概念

--第8讲 聚类的基本概念

-第9讲 K-Means & K-Medoids Clustering

--第9讲 K-Means & K-Medoids Clustering

-第四章 聚类算法--习题

第五章 大数据平台与技术

-第10讲 大数据处理平台Hadoop

--第10讲 大数据处理平台Hadoop

-第11讲 MapReduce编程

--第11讲 MapReduce编程

-第12讲 大数据处理平台Spark

--第12讲 大数据处理平台Spark

-第13讲 NoSQL数据库

--第13讲 NoSQL数据库

第六章 信息检索

-第14讲 Web信息检索简介

--第14讲 Web信息检索简介

-第15讲 信息检索之倒排索引

--第15讲 信息检索之倒排索引

-第16讲 信息检索之TFIDF

--Video

-第17讲 信息检索之相似度排序

--第16讲 信息检索之TFIDF

第七章 Web链接分析

-第18讲 Web搜索之链接分析

--第18讲 Web搜索之链接分析

-第19讲 Web搜索之PageRank

--第19讲 Web搜索之PageRank

-第20讲 Lucene信息检索平台

--第20讲 Lucene信息检索平台

-第七章 Web链接分析--习题

第八章 推荐系统

-第21讲 推荐系统简介

--第21讲 推荐系统简介

-第22讲 推荐系统之协同过滤

--第22讲 推荐系统之协同过滤

-第23讲 Mahout数据挖掘平台

--第23讲 Mahout数据挖掘平台

-第24讲 信息过滤评价体系

--第24讲 信息过滤评价体系

-第八章 推荐系统--习题一

-第八章 推荐系统--习题二

自我提升练习

-综合编程题

第4讲 Apriori算法的改进与兴趣度度量笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。