学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

烤鸭、面饼和甜面酱之朴素关联 ---趣味数据挖掘之二 精选

已有 14268 次阅读 2011-11-22 15:07 |个人分类:科普札记|系统分类:科普集锦|关键词:趣味,数据挖掘,关联规则,因果关系| 趣味, 数据挖掘, 关联规则, 因果关系

烤鸭、面饼和甜面酱之朴素关联 ---趣味数据挖掘之二(唐常杰) 

   上文借有趣的实例介绍了关联规则的三度 (支持度、置信度,兴趣度)概念。为答博友,此文从原讲课PPT中,取一些素材,来解释关联规则的挖掘思路和应用方法。

   1  通俗性与深入性的纠结  下笔(击键)之前,为通俗性和理论性的冲突,颇纠结了一番,通俗科普博文,是否需要完全避开公式和推导?查趣味数学小册子,其技巧是:趣例为载体,简喻作引导,推导明道理,前瞻性概述--“学,然后知不足”。

   所以,此文仍有一些简单的推导,只需中学数学知识,但仍须静心思量。                          

   2 自管理层的需求 某理想小型超市, 采用mini版超市销售系统, 管理了6种商品,记录了5个顾客的购物单(数据量如此之小,是为了简单地说明思想)。

流水号

所购物品清单

1

啤酒、薄饼、牛奶

2

烤鸭、薄饼、面酱

3

啤酒、烤鸭、薄饼、面酱

4

面酱,鸡蛋

5

烤鸭、面酱

   经理不满足常识性的定性描述,想知道商品间关联,例如,顾客买了面酱就会买烤鸭吗? 要求挖掘出支持度 不小于 2/5(即至少同时被买两次)的商品间的关联。

  下面先介绍朴素而费时的笨方法,后介绍聪明一些的方法。

  记录总数记为NN=5; 商品总数记为MM=6这里的数值2/5称为支持度阈值t,支持度 不小于2/5的商品组成的集合称为高频集。

  3朴素方法

     3.1 模仿选举计票方法统计单项高频集。把上面的5条记录视为5张选票,模仿 “唱票-计票-写正字”的方法,逐条唱票-计票,得票不少于两票的商品如下:

单项统计

支持度

{啤酒}

2/5

{烤鸭}

3/5

{面饼}

3/5

{面酱}

4/5

   解释(1)单项统计中看出60%的顾客买了烤鸭、60%的顾客买了面饼、80%的顾客买了面酱。(2)如果所购物品清单中间有N条记录(这里N=5),这里扫描工作量与N称正比,用行话,称为计算复杂度是OrderN),或简单记录为O(N),统计百分比在传统的统计中常见到。

     3.2 模仿选举计票方法统计双项高频集   商品总数记为MM=6, M个对象的两两组合数目为 T=M*M-1/2,这里T=15 ,(与M2变化趋势大致相同),这一次选举对象是T种组合的每一个“商品对”,逐条 唱票-计票,得票超过两票的“同购商品对”如下

双项统计

支持度

{啤酒,面饼}

2/5

{烤鸭,面饼}

2/5

{烤鸭,面酱}

3/5

{面饼,面酱}

2/5

从双项统计中看出,5个顾客中,有60%的顾客买了烤鸭和面酱。传统的统计较少作这种组合统计工作。

   3.3 模仿选举计票方法统计三项高频集

   类似地,得到高频的同购三项集只有一项:

三项统计

支持度

{烤鸭,面饼,面酱}

2/5

  这说明2/5=40%的顾客同时买了烤鸭、面饼和面酱。


   4 从高频集导出关联规则

       R1:烤鸭 --> 面饼、面酱。支持度40%,置信度为66.6%

   解释:买烤鸭的顾客占3/5,买了烤鸭又同时买了{面饼,面酱} 顾客2/5,说明在买烤鸭的人当中又买了{面饼、面酱}的占{(2/5) / (3/5) }=66.6%。按朴素的,但不一定总是正确的看法,把买烤鸭视为原因,右边的买{面饼、面酱}的视为结果,现有数据表明,这种因果关系有66.6%的正确性(不是想当然拍脑袋得出的神仙数字)。

   且慢宣称找到了发财诀窍,因为对3.3节的结果还有另外两种演绎,(推理方法如上):

       R2:面饼 --> 烤鸭、面酱支持度40%,置信度为66.6%  

       R3:面酱 --> 面饼、烤鸭支持度40%,置信度为50%

 而这些规则的运用之妙成乎于人,例如∶

    用R1,将烤鸭降价以促销面饼、面酱,很可能会破产(一等置信度,导致了破产);

    用R2   将面饼降价,以促销烤鸭,可能会发财;     (一等置信度,导致了发财);

    用R3,引不起顾客的热情。

可见,真理(知识)藏在数据中,还要人去去伪存真。

  5  关联规则不是因果关系

   设有关联规则:

      R4  X-->Y    s=   c=  

它并不说明XY的原因,因为立刻可以写出有同样支持度的反方向规则,(置信度可能不同),

       R5   Y-->X   s=   c= 

R4仅提示,当 X发生时,Y发生的置信度为C ,如果置信度C=0.5 时,则相当于掷硬币算命,不可靠, C比较大时,例如0.7以上,就值得进一步考察,如果X包含多个项:X=A1A2…..An ,检查其中是否有多余的项,此法可用于排除过敏原,或研究饮食习惯对某种疾病的影响等场合。

 我们曾经发表过一种排除因果关系的方法,考察X发生自然波动或者人工扰动时,如果Y的波动表现混沌,则可排除因果关联,反之,则可进一步调查研究:例如啤酒和纸尿布的故事中,通过属于管理范畴的调查,发现“婴儿之父下班为孩子买尿布时顺手买回自己爱喝的啤酒”,使得挖掘出来的规则可理解、可相信。

   6 朴素方法太笨,数据量稍大就不可行。

   朴素方法关键就是“组合被选举对象--唱票--计票”, 容易理解,容易实现,在小规模数据上是可用的,例如,想挖掘一个民间药方中的较重要成分,如果一共10项,每项有10个可能剂量,容易实现程序,现在的PC机已经比较快了,能计算这样的小规模问题。  

但是,量变引起质变,当数据变得很大,此法就从可行变为不可行了

        考察挖掘关联规则实际过程,易见过程分两大步:

        (a)  筛出高频集   给定支持度阈值t ,模仿选举的“唱票-计票”把频率高于t单项集,双项集,…,K项集 找出来(如第3节),这一步至少扫描数据库K遍,而且,多项集之组合数量很大,比较费时间。

        (b)  计算置信度,比较简单,左边的支持度做分母,两边合起来的的支持度做分子(如第3节)。

   在第一步中,当商品总数T比较大,例如实际大超市中,例如T>105,  欲考察K项商品之间关联,当K比较大,例如K>10时,涉及到组合爆炸,也许,用高档计算机也需要若干天,若干月,用行话描述,朴素方法的 Scalability不好,有人把scalability译为 规模伸缩性或者简称伸缩性

   有聪明一点的方法吗?有。

   下文中将看到,发表聪明方法的学者一举成名,而那篇论文创造了被引用次数的奇迹,下文将作简介这一成果,同时,分析超高被引用论文的特征。


相关博文

1“被打”和“北大” 的关联--- 趣味数据挖掘系列之 

2 烤鸭、面饼和甜面酱之朴素关联---趣味数据挖掘系列之二 

3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之

4 巧挖科学博客之均击量公式,兼谈干预规则----趣味数据挖掘之四 

5 听妈妈讲 过去的故事,分房与分类-----趣味数据挖掘之五 

 6 借水浒传故事,释决策树思路---趣味数据挖掘之六

 7 宴会上的聚类趣味数据挖掘之七

 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八

 9 灯谜、外星殖民、愚公移山和进化计算---趣味数据挖掘之九

 10 达尔文、孟德尔与老愚公会盟:基因表达式编程--趣味数据挖之十

 11 十大算法展辉煌,十大问题现锦绣---趣味数据挖掘之十一 

 12 数据挖掘中的趣味哲学---趣味数据挖掘之十二 

 假日聚会,戏说云物人海  --漫谈大数据


                  其它系列博文的入口          唐常杰博客主页         科学博客主页

 



http://blog.sciencenet.cn/blog-287179-510577.html

上一篇:“被打”和“北大” 的关联--- 趣味数据挖掘系列之一
下一篇:一篇 "它引" 上万的大牛论文 与 数据血统论-- 趣味数据挖掘之三

34 吕喆 刘用生 黄富强 曹聪 金小伟 单博炜 杨月琴 高文龙 武夷山 刘洋 高建国 李泳 黄秀清 杨正瓴 王德华 吴飞鹏 张玉秀 钟炳 卫军英 曾新林 王达伟 刘立 王启云 陈安 张珑 贡金涛 伍加 迟菲 化柏林 crossludo wnagjiho dulizhi95 zhaochengx8707 zhangsuigen8504

该博文允许注册用户评论 请点击登录 评论 (46 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-4-3 01:20

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部