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

摘要：此文从原讲课PPT中，取一些素材，来解释关联规则的挖掘思路和应用方法。

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

1  通俗性与深入性的纠结

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

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

2 来自管理层的需求

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

流水号 所购物品清单 1 啤酒、薄饼、牛奶 2 烤鸭、薄饼、面酱 3 啤酒、烤鸭、薄饼、面酱 4 面酱，鸡蛋 5 烤鸭、面酱

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

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

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

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

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

单项统计 支持度 的视为结果，现有数据表明，这种因果关系有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=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译为 规模伸缩性或者简称伸缩性。

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

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

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