不完整数据库关联规则的概率方法及非均匀数据库序列模式挖掘

### 不完整数据库关联规则的概率方法及非均匀数据库序列模式挖掘 #### 1. 关联规则研究背景 关联规则发现问题最初是针对销售交易数据库提出的，例如“80%购买鱼的顾客也会购买白葡萄酒”就是一个典型的关联规则。不过，在关系数据库中，数据不完整的问题经常出现，缺失的数据可能源于错误、测量失败、数据库模式变更等。 在人工智能的分类领域，针对数据不完整问题已经提出了一些解决方案。简单的方法包括移除含有未知值的示例，或者用最常见的值替换未知值。更复杂的方法如[2]使用贝叶斯形式，[4]根据示例的其他属性值和类别信息来预测属性值。 在关联规则的研究中，也有相关论文探讨数据不完整问题。[3]提出了计算关联规则支持度和置信度的悲观和乐观估计方法，并引入了基于数据库已知属性值的支持度和置信度期望值的概念。[5]的主要思路是将数据库分割成多个没有缺失值的有效数据库。 #### 2. 完整关系数据库中的关联规则 考虑一个表 $D = (O, AT)$，其中 $O$ 是一个非空有限元组集，$AT$ 是一个非空有限属性集，对于任意 $a \in AT$，有 $a: O \to V_a$，这里 $V_a$ 表示属性 $a$ 的域。任何属性 - 值对 $(a, v)$（其中 $a \in AT$ 且 $v \in V_a$）被称为一个项，一组项被称为项集。项集 $X$ 的统计显著性称为支持度，记为 $\sup(X)$，它被定义为 $D$ 中包含 $X$ 的交易的百分比（或数量）。 关联规则的形式为 $X \to Y$，其中 $X$ 和 $Y$ 是项且 $X \cap Y = \varnothing$。规则 $X \to Y$ 的统计显著性（支持度）记为 $\sup(X \to Y)$，定义为 $\sup(X \cup Y)$。规则 $X \to Y$ 的强度称为置信度，记为 $\conf(X \to Y)$，定义为 $\sup(X \cup Y) / \sup(X)$。 #### 3. 数据不完整导致的不确定性 在存在缺失属性值的数据库中，计算项集的真实支持度和关联规则的真实置信度是不可行的。不过，可以计算支持度和置信度的可能最小值和最大值，并尝试预测它们的最可能值。为了表达数据不完整的特性，引入以下概念： - 缺失值用 “*” 表示。 - 必然匹配项集 $X$ 的最大元组集记为 $n(X)$，定义为 $n(X) = \{t \in D | \forall (a, v) \in X: a(t) = v\}$。 - 可能匹配项集 $X$ 的最大元组集记为 $m(X)$，即 $m(X) = \{t \in D | \forall (a, v) \in X: a(t) \in \{v, *\}\}$。 - $m(X)$ 和 $n(X)$ 的集合差记为 $d(X)$。 - 肯定不匹配项集 $X$ 的最大元组集记为 $n(-X)$，即 $n(-X) = D \setminus m(X)$。 - 可能不匹配项集 $X$ 的最大元组集记为 $m(-X)$，即 $m(-X) = D \setminus n(X)$。 以下是一个不完整数据库的示例： | Id | X1 | X2 | X3 | X4 | | --- | --- | --- | --- | --- | | 1 | * | a | a | c | | 2 | a | a | b | * | | 3 | a | b | c | c | | 4 | a | b | d | c | | 5 | * | b | e | d | | 6 | b | b | f | * | | 7 | b | c | g | * | | 8 | b | c | h | * | 不同项集对应的元组集如下表所示： | 项集 $X$ | $n(X)$ | $m(X)$ | $d(X)$ | $n(-X)$ | $m(-X)$ | | --- | --- | --- | --- | --- | --- | | $\{(X1, a)\}$ | $\{2, 3, 4\}$ | $\{1, 2, 3, 4, 5\}$ | $\{1, 5\}$ | $\{6, 7, 8\}$ | $\{1, 5, 6, 7, 8\}$ | | $\{(X4, c)\}$ | $\{1, 3, 4\}$ | $\{1, 2, 3, 4, 6, 7, 8\}$ | $\{2, 6, 7, 8\}$ | $\{5\}$ | $\{2, 5, 6, 7, 8\}$ | | $\{(X1, a), (X4, c)\}$ | $\{3, 4\}$ | $\{1, 2, 3, 4\}$ | $\{1, 2\}$ | $\{5, 6, 7, 8\}$ | $\{1, 2, 5, 6, 7, 8\}$ | | $\{(X1，a), (X2, b)\}$ | $\{3, 4\}$ | $\{3, 4, 5\}$ | $\{5\}$ | $\{1, 2, 6, 7, 8\}$ | $\{1, 2, 5, 6, 7, 8\}$ | | $\{(X2, b), (X4, c)\}$ | $\{3, 4\}$ | $\{3, 4, 6\}$ | $\{6\}$ | $\{1, 2, 5, 7, 8\}$ | $\{1, 2, 5, 6, 7, 8\}$ | | $\{(X1, a), (X2, b), (X4, c)\}$ | $\{3, 4\}$ | $\{3, 4\}$ | $\varnothing$ | $\{1, 2, 5, 6, 7, 8\}$ | $\{1, 2, 5, 6, 7, 8\}$ | 项集 $X$ 的最小可能支持度记为 $pSup(X)$（悲观情况），最大可能支持度记为 $oSup(X)$（乐观情况），计算公式如下： - $pSup(X) = |n(X)| / |D|$ - $oSup(X) = |m(X)| / |D|$ 若 $X \subset Y$，则有 $n(X) \supseteq n(Y)$ 且 $m(X) \supseteq m(Y)$，所以 $pSup(X) \geq pSup(Y)$ 且 $oSup(X) \geq oSup(Y)$。 规则 $X \to Y$ 的最小可能置信度和最大可能置信度分别记为 $pConf(X \to Y)$ 和 $oConf(X \to Y)$，可根据以下公式计算（证明见[3]）： - $pConf(X \to Y) = |n(X) \cap n(Y)| / [|n(X) \cap n(Y)| + |m(X) \cap m(-Y)|]$ - $oConf(X \to Y) = |m(X) \cap m(Y)| / [|m(X) \cap m(Y)| + |n(X) \cap n(-Y)|]$ 规则的乐观和悲观估计之间的差异可能很大。能够预测接近真实（尽管未知）的支持度和置信度值是很有意义的。无论在不完整数据集中对最可能的支持度和置信度如何定义，都必须满足以下属性： - $\sup(X) \in [pSup(X), oSup(X)]$ - 对于 $X \subset Y$，有 $\sup(X) \geq \sup(Y)$ - $\conf(X \to Y) = \sup(X \cup Y) / \sup(X)$ - $\conf(X \to Y) \in [pConf(X \to Y), oConf(X \to Y)]$ - $\sum_{X \in Instances(A)} \sup(X) = 1$ #### 4. 不完整数据的概率方法 设 $\mu_t^a: V_a \to [0, 1]$