关联规则挖掘算法

为所有项目的集合,

为事务数据库,事物

是一个项目子集(

)。每一个事务具有唯一的事务标识

。设

是一个由项目构成的集合,称为

。事务

包含项集

,当且仅当

。如果项集

中包含

个项目,则称其为

项集

在事务数据库

中出现的次数占总事务的百分比叫做项集的

。如果项集的支持度超过用户给定的最小支持度阈值,就称该项集是

关联规则是形如

的逻辑蕴含式,其中

,且

如果事务数据库D中有

的事务包含

, 则称关 联规则

的⽀持度为

关联规则的信任度为

也就是:

强关联规则就是⽀持度和信任度分别满⾜⽤户 给定阈值的规则

例子

交易ID

购买的商品

2000

A,B,C

1000

A,C

4000

A,D

5000

B,E,F

设最⼩⽀持度为50%, 最⼩可信度为 50%, 则可得到

  • A ⇒ C (50%, 66.6%)
  • C ⇒ A (50%, 100%)

Apriori算法

命名源于算法使⽤了频繁项集性质的先验( Prior) 知识。

Apriori算法将发现关联规则的过程分为两个步骤:

  • 通过迭代, 检索出事务数据库中的所有频繁 项集, 即⽀持度不低于⽤户设定的阈值的项集;
  • 利⽤频繁项集构造出满⾜⽤户最⼩信任度的 规则。
  • 挖掘或识别出所有频繁项集是该算法的核⼼, 占整个 计算量的⼤部分

Apriori的性质

性质1: 频繁项集的所有⾮空⼦集必为频繁项集。

性质2: ⾮频繁项集的超集⼀定是⾮频繁的。

Apriori的步骤

连接步: 为找Lk,通过将Lk-1与⾃⾝连接产⽣候选k项集 的集合

剪枝步: Ck是Lk 的超集, 也就是说, Ck的成员可以是 也可以不是频繁的, 但所有的频繁k项集都包含在Ck中。 任何⾮频繁的( k-1) 项集都不是频繁k项集的⼦集

Apriori算法实例

现有A、 B、 C、 D、 E五种商品的交易记录表, 试找出 三种商品关联销售情况(k=3), 最小支持度=50%

交易号

商品代码

100

A,C,D

200

B,C,E

300

A,B,C,E

400

B,E

读入数据

data = {'交易号':range(100,500,100),'商品代码':['A,C,D', 'B,C,E', 'A,B,C,E', 'B,E']}
df_data = pd.DataFrame(data=data)

算一个事务集在事务数据库的支持度

def get_score(values):
    score = 0.0
    b = True
    for value_code in df_data['商品代码'].values:
        b = True
        for value in values:
            if value not in value_code:
                b = False
                break
        if b is True:
            score += 1              
    return score/len(df_data)

首先构造等候集C

c = []
for code in df_data['商品代码'].values:
    for _ in code.split(','):
        if {_} not in c:
            c.append({_})

输出c

 [{'A'}, {'C'}, {'D'}, {'B'}, {'E'}]

计算L

from collections import defaultdict

score = 0.5
# 这里用字典来保存频繁项集
L = defaultdict(list)
i = 0
length = len(c)
while c:
    i += 1
    for ci in c:
        if get_score(ci) >= score:
            L[i].append(ci)
    print L[i]
    c = get_c(L[i])
[set(['A']), set(['C']), set(['B']), set(['E'])]
[set(['A', 'C']), set(['C', 'B']), set(['C', 'E']), set(['B', 'E'])]
[set(['C', 'B', 'E'])]

可以得出三种商品关联销售情况(k=3), 最小支持度=50%只有一组(CBE)

Apriori算法的不⾜

中的项集是⽤来产⽣频集的候选集.

  • 最后的频集

必须是

的⼀个⼦集。

中的每个元素需在交易数据库中进⾏验证来决定其是否加 ⼊

  • 验证过程是性能瓶颈 交易数据库可能⾮常⼤ ⽐如频集最多包含10个项, 那么就需要扫描交易数据库10遍 需要很⼤的I/O负载。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是极客人

图片去霾算法实践】NDK下二维数组的传递

最近看到了一篇关于图片“去霾算法”的文章,一下子就有了兴趣,所以想着能不能实现。由于数学能力捉急,无法理解文章的思想和相关论文。于是在Github上找到了相关的...

1113
来自专栏Y大宽

RNA-seq(6): reads计数,合并矩阵并进行注释

小结 计数分为三个水平: gene-level, transcript-level, exon-usage-level 标准化方法: FPKM RPKM ...

4285
来自专栏吉浦迅科技

在Jetson TX2上跑个人脸识别小程序

不少跟我们买Jetson TX2开发板的用户在我们指导下成功刷完机后,都会迫不及待地想赶紧跑个代码了:

3083
来自专栏新智元

【TensorFlow1.2.0版发布】14大新功能,增加Intel MKL集成

【新智元导读】TensorFlow 今天发布最新版 1.2.0,公布了14大最新功能。新智元带来最新介绍,包括 API 的重要变化、contrib API的变化...

3449
来自专栏瓜大三哥

SD-SDI数据解析

凡是做模拟信号采集的,很少不涉及BT.656标准的,因为常见的模拟视频信号采集芯片都支持输出BT.656的数字信号,那么,BT.656到底是何种格式呢? 本文...

1415
来自专栏Python小屋

Python使用Apriori算法查找关系密切的演员组合

已知一些演员参演电影的信息,如下图所示,获取这些存储在Excel文件中的数据,查找关系较好的演员二人组合,也就是频繁2项集。

1581
来自专栏CVer

利用OpenCV玩转YOLOv3

YOLOv3是You Only Look Once系列的最新目标检测算法,关于YOLOv3的介绍,网上一大堆,本文就不跟风描述。想要了解YOLOv3的同学,可以...

1.7K2
来自专栏用户2442861的专栏

关于Python杂七杂八的小东西(搭建Pycharm+Anaconda、删除文档首行小程序、皮尔逊相关系数小程序)

  好久没有回来更新博客了,良心难安啊!最近要做脑电信号的分析,由于导出的数据都是文本格式的,就下定决心放弃Matlab,用Python做分析,确实是挺好用的...

1381
来自专栏数据小魔方

parklines迷你图系列1——Scales

按照之前的计划,今天开始按照sparklines插件的图表分类标准开始跟大家分享详细的做法。 按照该插件在excel菜单中的顺序,先来看测量尺度(Scales)...

2916
来自专栏生信宝典

DESeq2差异基因分析和批次效应移除

2K10

扫码关注云+社区

领取腾讯云代金券