关联算法

1. 关联

关联, 指的是关联分析, 这里引用百度百科的定义.

关联分析又称关联挖掘,就是在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。

通过关联分析, 可以挖掘出"由于某些事件的发生而引起另外一些事件的发生"之类的规则, 比如说"面包=>牛奶", 其中面包被称为规则的前项, 而牛奶则被称为规则的后项.

常用于关联分析的算法有Apriori算法, FP-growth算法, Eclat算法, 灰色关联法等, 下面将着重介绍Apriori算法.

2. Apriori算法

在介绍Apriori算法之前, 我们先来了解几个概念:
1.事务: 一条交易记录称为一个事务
2.项: 交易中的每一个物品称为一个项
3.项集: 包含0个或多个项的集合
4.支持度计数: 项集在所有事务中出现的次数.
5.支持度: 支持度计数除于总的事务数.
6.频繁项集: 支持度大于等于某个阀值的项集.

关联规则的挖掘通常分为两步: 第一步, 找出所有的频繁项集; 第二步, 由频繁项集产生强关联规则. 而Apriori算法则是挖掘频繁项集的基本算法.

Apriori算法的过程大致可以描述为: 首先, 根据最小支持度扫描所有候选项集, 从而找出频繁1-项集的集合. 然后, 再使用频繁1-项集的集合找出频繁2-项集的集合, 如此下去, 直到不能找出频繁k-项集.

可以看到以上每个过程均需要扫描一次数据, 为了提高频繁项集逐层迭代产生的效率, 需要利用一条重要性质, 其称为先验性质:

先验性质: 频繁项集的所有非空子集也一定是频繁的.

当然, 非频繁项集的所有超集也一定是非频繁的.

将先验性质应用到Apriori算法中就是将之前的过程分为两大部分, 连接步和剪枝步.
连接步: 连接步的目的是产生候选项集.
剪枝步: 应用先验性质对候选项集进行筛选, 将不满足先验性质的候选项集剔除, 再进而根据最小支持度找出频繁项集, 这样可以有效缩短计算量.

关联分析的目标是找出强关联规则, 因此这里的关联规则是指强关联规则, 我们把满足最小支持度和最小置信度的规则称为强关联规则.
对于规则A=>B, 置信度的计算公式就是项集{A, B}的支持度计数除于项集{A}的支持度计数.

3. 优缺点

优点: 简单, 易理解, 对数据要求低
缺点: 容易产生过多的候选项集, I/O负载大.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 其实读完斯坦福的这本《互联网大规模数据挖掘》,让我感觉到,什么是人工智能?人工智能就是更高层次的数据挖掘。机...
    我偏笑_NSNirvana阅读 12,781评论 1 23
  • 定义   关联分析是一种简单、实用的分析技术,就是发现存在于大量数据集中的关联性或相关性,从而描述了一个事物中某些...
    老羊_肖恩阅读 3,381评论 0 1
  • 或许是这一站有点偏,车上竟然就戚辞和她两个人。 公交车上不适合看书,季宁莫名的想找点事干。 季宁不认为自己是...
    网媒张慧敏阅读 225评论 0 0
  • 2018年读完的第三本书,《先锋书店,生于1996》。 这本书是去年春节去南京时,在先锋书店五总山总店购买的,是先...
    尘飞扬0011阅读 809评论 0 0
  • 树幻千湖绿,草盼万山低, 水广善引雨,山低好修渠。 森林莽苍苍,山乡富有余。 草木皆有心,和谐共生辉。
    云逸1108阅读 149评论 0 0