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 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

结构化分析和方法

结构化分析方法(SA)是一种面向数据流的需求分析方法,适用于分析大型数据处理系统,是一种简单、实用的方法。 基本思想是自顶向下逐层分解。分析结果有一套分层的数据...

1676
来自专栏SDNLAB

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

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

34312
来自专栏技术专栏

初识数据仓库和维度建模的一些理解和感悟

校招面试的时候面的是java后台,收到的职位offer是大数据相关的东西,虽然啥也不会,不过想到这也是一个比较火的领域,就毅然决然的接受了这个offer。

872
来自专栏DT数据侠

如何才能像勇士队一样科学地扔三分球?

这两年库里和他的金州勇士队让整个NBA都刮起三分雨。几乎所有的球队都开始围绕三分球布置战术,甚至连高大的中锋们都不得不跑出去扔起了三分球。“小球”风格被公认成为...

620
来自专栏腾讯移动品质中心TMQ的专栏

【Android场景化性能测试】UI流畅度篇

承接《Android场景化性能测试-方向与框架篇》,本篇详述UI流畅度的测试方法,重点在于获得流畅度SM数据之后,如何利用好。

6043
来自专栏Frank的专栏

剖析广州“开四停四”交通限行的实现技术

今天我们就从技术的角度,来剖析一下如何技术上实现“开四停四”的判定执法。

1.7K60
来自专栏PPV课数据科学社区

【观点】最适合数据分析师的数据库为什么不是MySQL?!

数据分析师都想使用数据库作为数据仓库处理并操作数据,那么哪一款数据库最合适分析师呢? 虽然网上已经有很多对各种数据库进行比较的文章,但其着眼点一般都是架构、成...

2515
来自专栏AI启蒙研究院

移动通信20年:从0到5G

662
来自专栏AI研习社

如何理解Nvidia英伟达的Multi-GPU多卡通信框架NCCL?

深度学习中常常需要多GPU并行训练,而Nvidia的NCCL库NVIDIA/nccl(https://github.com/NVIDIA/nccl)在各大深度学...

2639
来自专栏绿巨人专栏

读书笔记: 博弈论导论 - 14 - 不完整信息的静态博弈 机制设计

3366

扫描关注云+社区