关联规则通常是我们关联分析所得到的结果, 那么我们如何判断该结论是否是我们想要的, 或者说这个规则是否足够"好"呢? 通常我们使用两个度量来衡量规则的强度: 支持度和置信度. 其中支持度确定规则可以用于给定数据集的频繁程度, 而置信度确定 $Y$ 在包含 $X$ 的事务中出现的频繁程度. 支持度( $s$ )和置信度( $c$ )的定义如下:

\tag{1.3} s(X \rightarrow Y) =\frac{\sigma(X \cup Y)}{N}

\tag{1.4} c(X \rightarrow Y) =\frac{\sigma(X \cup Y)}{\sigma(X)}

以表1.1为例: 考虑规则{牛奶, 尿布} $\rightarrow$ {啤酒}. 显然, $X \cup Y$ = {牛奶, 尿布, 啤酒}, 对于该项集计算其支持度 $\sigma$ ({牛奶, 尿布, 啤酒})=1, 而事务总数为4, 所以规则的支持度为 $\frac{1}{4}=0.25$ . 而 $X=$ {牛奶, 尿布} 的支持度为 $\sigma(X)=2$ . 易得该规则的置信度为 $\frac{1}{2}=0.5$ .

注意

由关联规则做出的推论并不必然蕴含因果关系. 只是说, 它有时候能表示规则前件和后件中的项同时出现的概率很大, 具有统计相关性.

如果想要确定因果关系, 则必须知道数据中哪些属性是导致结果发生的原因, 并且通常涉及随时间推移发生的联系.

规则挖掘

关联规则挖掘问题的形式描述

给定事务的集合 $T$ , 关联规则发现是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则, 其中minsup和minconf是对应的支持度和置信度的阈值.

现在我们根据这个定义很容易得出, 挖掘关联规则的一种暴力方法就是: 计算每个可能的规则的支持度和置信度. 但是这个方法的计算代价往往高得令人望而却步, 因为通常数据集中可以提取出的规则的数据可达指数级. 更具体地说, 假设规则的左边和右边都不是空集, 那么从包含 $d$ 个项的数据集提取的可能规则的总数 $R=3^d-2^{d+1}+1$ . 所以在计算的过程中事先对规则进行剪枝而不必计算它们的支持度和置信度将是非常重要的.

提高关联规则挖掘算法性能的第一步就是拆分支持度和置信度的要求. 我们由前面的公式(1.3)、公式(1.4)可以看出规则 $X \rightarrow Y$ 的支持度和其对应项集 $X \cup Y$ 是相同的. 所以如果项集 $X \cup Y$ 是非频繁的, 那么则可以立刻剪枝剪掉对应的候选规则 $X \rightarrow Y$ , 并且不必计算器置信度值了. 例如: 对于项集{啤酒, 尿布, 牛奶}来说, 如果其是非频繁的, 则不必计算对应的6个规则:

{啤酒, 尿布} $\rightarrow$ {牛奶}
{啤酒, 牛奶} $\rightarrow$ {尿布}
{牛奶, 尿布} $\rightarrow$ {啤酒}
{啤酒} $\rightarrow$ {尿布, 牛奶}
{牛奶} $\rightarrow$ {尿布, 啤酒}
{尿布} $\rightarrow$ {啤酒, 牛奶}

因此, 大多数关联规则挖掘算法通常采用的一种策略是将挖掘任务分解成两个主要的子任务:

频繁项集产生: 其目标是发现满足最小支持度阈值的所有项集. 这些项集称为频繁项集(frequent itemset)
规则的产生: 其目标是从上一步发现的频繁项集中提取所有高置信度的规则. 这些规则成为强规则(strong rule)

一般来说, 频繁项集的产生的计算开销是远大于规则生成的计算开销的.

在接下来的章节里面, 我们将讨论频繁项集的产生以及先验理论.