上文《趣味数据挖掘系列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张选票，模仿“唱票-计票-写正字”的方法，逐条唱票-计票，得票不少于两票的商品如下：
| 单项统计 | 支持度 |
| {啤酒} | 2/5 |
| {烤鸭} | 3/5 |
| {面饼} | 3/5 |
| {面酱} | 4/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 ,（与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= ？
它并不说明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译为 规模伸缩性或者简称伸缩性。
有聪明一点的方法吗？有。
下文中将看到，发表聪明方法的学者一举成名，而那篇论文创造了被引用次数的奇迹，下文将作简介这一成果，同时，分析超高被引用论文的特征。
作者：唐常杰，四川大学，计算机学院，教授
本文采用「CC BY-SA 4.0 CN」协议转载自互联网、仅供学习交流，内容版权归原作者所有，如涉作品、版权和其他问题请给「我们」留言处理。
