基本知识

约 1570 字大约 5 分钟

2024-04-30

我们首先来看一下四种数据挖掘任务里面的关联分析. 在关联分析中需要处理两个关键的问题:

从大型事务数据集中计算的代价非常大.
所发现的某些模式可能是虚假的, 甚至对于非虚假的模式来说, 它们的意义也会有所不同.

我们将先介绍关联分析中所需要用到的一些基础知识, 然后介绍 Apriori 算法, 最后在剩下的部分重点讨论上面提到的这两个问题.

TID	面包	牛奶	尿布	啤酒	鸡蛋	可乐
1	1	1	1	0	0	0
2	0	1	0	1	0	0
3	0	0	1	1	1	1
4	0	1	1	1	0	0

表 1.1

项集

表中的列我们称之为: 项, 包含零个或多个项的集合称为 项集. 如果一个项集包含 $k$ 个项, 则称之为 k-项集.

例如: {啤酒, 尿布, 牛奶} 是一个 3-项集.

项集我们用 $I = \{i_1, i_2, \dots, i_d\}$ 来表示.

事务

表中的行我们称之为: 事务, 用 $T = \{t_1, t_2, \dots, t_N\}$ 表示, 第 $i$ 行即为 $t_i$ . 每个事务 $t_i$ 包含的项集都是 $I$ 的子集.

支持度

对于项集 $X$ , 数学上定义其支持度 $\sigma(X)$ 表示为:

\tag{1.1} \sigma(X) = \lvert\{t_i|X\subseteq t_i, t_i \in T\}\rvert

用人话来讲就是某一个项集在所有事务中出现的个数. 例如在表 1.1 中, 项集 {面包, 牛奶} 的支持度为 1, 因为该项集只在第一行(即 $t_1$ )中出现了一次. 而项集 {尿布, 啤酒} 的支持度为 2.

频繁

我们定义:

\tag{1.2} s(X) = \frac{\sigma(X)}{N}

如果 $s(X)$ 的值比用户设置的某些阈值 minsup 大, 则称项集 $X$ 是频繁的.

可以看到, 对于项集 $X$ 来说, 在固定的事务数量 $N$ 的情况下, 其支持度越高, 我们认为其越频繁.

关联规则

关联规则是形如 $X \rightarrow Y$ 的蕴含表达式, 其中 $X$ 和 $Y$ 是不相交的项集.

关联规则通常是我们关联分析所得到的结果. 那么我们如何判断该结论是否是我们想要的, 或者说这个规则是否足够"好"呢? 通常我们使用两个度量来衡量规则的强度: 支持度 和 置信度. 其中支持度确定规则可以用于给定数据集的频繁程度, 而置信度确定 $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$ {啤酒, 牛奶}

因此, 大多数关联规则挖掘算法通常采用的一种策略是将挖掘任务分解成两个主要的子任务: 1.频繁项集产生: 其目标是发现满足最小支持度阈值的所有项集. 这些项集称为频繁项集(frequent itemset) 2. 规则的产生: 其目标是从上一步发现的频繁项集中提取所有高置信度的规则. 这些规则成为强规则(strong rule)

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

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