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

上文《趣味数据挖掘系列1：被打”和“北大” 的关联》借有趣的实例介绍了关联规则的三度（支持度、置信度，兴趣度）概念。为答博友，此文从原讲课PPT中，取一些素材，来解释关联规则的挖掘思路和应用方法。

1 通俗性与深入性的纠结

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

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

2 来自管理层的需求

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

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

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

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

3朴素方法

3.1 模仿选举计票方法统计单项高频集

把上面的5条记录视为5张选票，模仿“唱票-计票-写正字”的方法，逐条唱票-计票，得票不少于两票的商品如下：

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

3.2 模仿选举计票方法统计双项高频集

商品总数记为M，M=6, M个对象的两两组合数目为T=M*（M-1）/2，这里T=15 ,（与M²变化趋势大致相同），这一次选举对象是T种组合的每一个“商品对”，逐条唱票-计票，得票超过两票的“同购商品对”如下

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

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

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

这说明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= ？

它并不说明X是Y的原因，因为立刻可以写出有同样支持度的反方向规则，（置信度可能不同），

R5： Y–>X s=？ c=？

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

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

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

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

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

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

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

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

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

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

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

作者：唐常杰，四川大学，计算机学院，教授