Thinking in SQL系列之数据挖掘Apriori关联分析再现啤酒尿布神话

编辑手记:SQL做为一种编程语言,能够满足各类数据处理的需要,关键就在于算法与思维方式。以SQL会友,希望结交更多的数据库、数据分析领域的朋友。

作者简介:牛超

10多年数据库技术积累,长期从事ORACLE数据库管理与开发工作。精通企业级数据库应用设计、SQL、算法实现、异常分析、性能优化。目前就职于日立咨询(中国)有限公司。Mail:10867910@qq.com

说起数据挖掘机器学习,印象中很早就听说过关于啤酒尿布的神话,这个问题经常出现在数据仓库相关的文章中,由此可见啤酒尿布问题对数据挖掘领域影响的深远程度。

先看看它的成因:

“啤酒与尿布”的故事产生于20世纪90年代的美国沃尔玛超市中,沃尔玛的超市管理人员分析销售数据时发现了一个令人难于理解的现象:在某些特定的情况下,“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中,这种独特的销售现象引起了管理人员的注意,经过后续调查发现,这种现象出现在年轻的父亲身上,买尿布的同时经常顺便带一瓶啤酒回家。

在对这个问题津津乐道的同时,可能并不是所有的人都会关注它的实现细节。啤酒尿布问题归属于关联分析,即从一组数据集中发现项之间的隐藏关系,是一种典型的无监督学习。关联规则的项集可以是同构的如啤酒->尿布,也可以是异构的如夏天->空调备货。

本篇文章Apriori算法主要是基于频繁集的关联分析,也是十大经典数据挖掘算法之一,本文中所出现的关联分析默认都是指基于频繁集的关联分析。以下为个人收集整理的Apriori算法的相关描述以辅助记忆,如有误导之处,请指正。

项的集合称为项集。包含k个项的项集称为k项集。

项集I表示为{i1,i2,...ik-1,ik},i可以是啤酒、尿布、牛奶等等。

集合D表示训练集,训练集中对应多笔交易(可理解为购物小票),每笔交易对应都是I的子集(不同商品)。

候选项集,经过关联组合构造的项集。候选项集经过剪枝处理形成频繁项集

频繁项集,即满足最小支持度条件的项集,同时它的所有子集必须是频繁的,理解为经常同时出现在同一购物篮中的一组商品。

支持度公式:support = P(A并B),由于训练集交易总次数相对固定,因此可简化为A并B的发生频次(分母相同可忽略)。

Apriori算法具有一个非常重要的性质,即先验性质,说的是频繁项集的所有子集也一定是频繁的。一般在算法的实现中利用了该性质的反语,即一个项集如果不是频繁项集,其超项集也一定不是频繁项集。利用该性质可以大大减少算法对数据的遍历次数。

两个K项集(频繁集)需要进行连接以生成超项集(候选集),连接条件是二者有K-1项相同或者K为初始频繁集。

极大频繁项集,满足最小支持度条件的最终的频繁项集。关联规则表示为A->B,其中A、B均为I的子集,且A与B的交集为空,规则相关具有单向性,因此用->表示,可理解为一种因果关系。

根据计算出来的K项集最终推导的关联规则要满足置信度条件,理解为大于已设定的概率值。

置信度公式:confidence = P(A)|P(A并B) = support(A并B)/support(A)

根据上面的描述,我们可以发现,这个算法多次出现候选集、频繁集、子集的概念,如何构建与操作集合是Apriori算法的关键,而最擅长集合操作的语言正是SQL。也是基于本系列,Thinking in SQL,看看如何用SQL来再现经典的啤酒尿布销售神话。

与穷举法不同,根据频繁集的性质,Aprior算法采用逐层搜索的方法,包含以下5个步骤:

1、首先根据集合D初始化候选集(K-1),依据最小支持度条件得到K-1项频繁集。 2、K-1项频繁集自连接获取K项候选集。第一轮K-1项频繁集就是在步骤1构造的,而其他轮是由步骤3得到(频繁集由候选集剪枝得到)。 3、对于候选集进行剪枝。如何剪枝呢?如果候选集的支持度小于最小支持度,那么就会被剪掉;另外,候选集的子集有不是频繁集的,也会被剪掉(这步处理较为复杂)。 4、递归步骤2,3,算法的终止条件是:如果自连接得到的已经不再是频繁集,取最后一次得到的频繁集作为结果。 5、构建候选的关联规则,并利用最小置信度剪枝以形成最终的关联规则。

对这个算法有进一步认识之后,下面就需要着手实现了,简要的说明一下我的思路:

1. 构建并导入用于机器学习的训练集

2. 创建集合类型以便于SQL与PLSQL交互

3. 创建支持度计算函数,用于输出项集支持度

4. 创建构建极大频繁集的函数(递归生成频繁集,剪枝操作依赖步骤3的支持度函数)

5. 主体查询SQL,利用步骤4创建的函数,构建关联规则,根据最小置信度剪枝输出结果

具体实现步骤如下(个人环境ORACLE XE 11.2):

1.构建训练集D,创建表DM_APRIORI_LEARNING_T用于存放训练集

CREATE TABLE DM_APRIORI_LEARNING_T
(
BATCH_ID NUMBER ,--批次ID,区分训练集D
TRX_ID NUMBER ,--交易票据ID
ITEM VARCHAR2(100) --商品
) ;

导入销售数据,如下效果

2. 创建集合类型以便SQL与PLSQL交互。每个项集的项数可能不相同,归属于一个项集ID。

3. 创建函数用于项集支持度计算,返回项集支持度的集合,依赖APRIORI训练集表,其中P_BATCH_ID用于界定训练集,P_TAB用于传入候选项集,重点关注如何判断项集能被训练集全匹配以及匹配次数的SQL实现,需要面向集合来思考,即Thinking in SQL。

4. 创建递归函数用于构造K项频繁集的超集,根据指定参数递归地构造极大频繁项集,而且这里可以指定P_MAXLVL最大K值以限制递归层次(默认无限制),重点关注频繁集连接构建候选超集的SQL实现,这是该算法的核心部分,Thinking in SQL,屏蔽ROW BY ROW循环处理的思路,注意如果没有面向集合的思维可能会迷失。

函数创建好了之后,可以做几个简单的查询以帮助理解:

a.查询极大频繁项集的计算结果,可以看到结果一共2个3项集

b.查询初始项集,指定最大搜索层次为1,结果是6个1项集

c.查询频繁2项集,指定最大搜索层次为2,结果是6个2项集

d.查询频繁2项集对应的支持度,注意CAST与MULTISET的用法

5. 主体查询SQL,利用步骤3、4创建的函数,构建关联规则,根据最小置信度剪枝输出结果,为了保持通用性,使用参数集PARAMS(支持度2,置信度60%)来驱动全盘,Thinking in SQL,一气呵成,如下:

执行后看看机器学习的成果,故事结局变成了啤酒尿布与纸巾的那些事,再看看迅雷不及掩耳的0.25秒(个人电脑工龄11年):

啤酒尿布这类经典算法能够让我们拓展思维,并非局限于纵向拓展(术业专攻,自认能力有限),否则会陷入“太学术”的误区死角。跳出深究算法本身,也不要只关注购物篮分析,通过头脑风暴地横向思维扩展可以发现很多应用场景。

例如身为开发DBA在工作过程中经常会分析一类问题:哪些表会经常同时被关联查询;哪些列会同时出现在谓词中;如何创建组合索引、冗余加速列、冗余加速表会对系统整体性能有战略提升效果。可以通过定期挖掘分析生产库的SQL形成训练集,通过操控频繁集找到表间关联项集,谓词列关联项集与关联规则,也可以结合欧拉定理给出支持度权重。从而为高效的数据库设计运营提供有效的决策依据。

当然现实中的开发工作无法让人思考太多战略技术层要素,对性能的要求也只不过是追求一时的快感。因此虽然工作N年很多设想只能局部落地。敏捷+结果为导向难免会让人怀揣游击战的心理,相信很多人会有同感。

回到主题,SQL语言处理数据有天生的优势,Thinking in SQL,面向集合思考问题,通过关系运算(并、交、乘、除)处理数据,ORACLE高效的SQL引擎会负责循环处理。结合ORACLE高级开发技巧,通过不断地总结归纳,注入灵魂算法,ORACLE数据库也能定制机器学习能力。

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2017-03-28

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【机器学习】Python语言下的机器学习库

Python是最好的编程语言之一,在科学计算中用途广泛:计算机视觉、人工智能、数学、天文等。它同样适用于机器学习也是意料之中的事。 当然,它也有些缺点;其中一个...

25110
来自专栏北京马哥教育

Python自然语言处理分析倚天屠龙记

? 转载自:Python中文社区 ID:python-china 最近在了解到,在机器学习中,自然语言处理是较大的一个分支。存在许多挑战。例如: 如何...

3866
来自专栏用户画像

相似人群画像算法

由于TESLA集群无法直接操作MongoDB,需要将TDW里面的用户画像数据,通过洛子系统导出至HDFS,再与MongoDB中原有群画像进行合并。

5635
来自专栏SDNLAB

5G革命的技术,一个都不能少

第五代移动网络简称5G是产业界即将实现的移动技术革命,是LTE-A网络的深层演进技术。5G网络中的关键技术包括MIMO、OFDM、SC-FDMA等。 超密集微型...

42212
来自专栏玉树芝兰

贷还是不贷:如何用Python和机器学习帮你决策?

本文我们用贷款风险判断的实际案例,帮助你一步步学习如何用Python做决策树。依靠机器学习中的分类(classification)方法,你可以快速高效地完成繁重...

914
来自专栏生信技能树

如何通过Google来使用ggplot2可视化

今天是大年初二,这篇文章我只想传达一点: 没有什么菜鸟级别的生物信息学数据处理是不能通过Google得到解决方案的,如果有,请换个关键词继续Google! 第一...

3088
来自专栏专知

【AlphaGo Zero 核心技术-深度强化学习教程代码实战02】理解gym的建模思想

点击上方“专知”关注获取更多AI知识! 【导读】Google DeepMind在Nature上发表最新论文,介绍了迄今最强最新的版本AlphaGo Zero,不...

3295
来自专栏PaddlePaddle

【AI核心技术】课程十九:神经图灵机—寻址

UAI与PaddlePaddle联合推出的【AI核心技术掌握】系列课程持续更新中!

801
来自专栏大数据风控

R关联规则算法(支持度、自信度、提升度)

关联规则(Association Rules) 用于大量数据中挖掘出有价值的数据项之间的相关关系 常用于用户购物篮分析,使用它来发现顾客的购买习惯 两个...

1978
来自专栏人人都是极客

GPU的工作原理

在GPU出现以前,显卡和CPU的关系有点像“主仆”,简单地说这时的显卡就是画笔,根据各种有CPU发出的指令和数据进行着色,材质的填充、渲染、输出等。 较早的娱乐...

3905

扫码关注云+社区