影响规则发现中修剪派生部分规则

### 影响规则发现中修剪派生部分规则 #### 1. 引言 探索性规则发现旨在从可用样本数据中，检索出满足用户定义约束条件的所有隐式模式和规律。例如关联规则发现，多数方法寻找前件 A 和后件 C 存在关联的规则 A → C。然而，当找到一个这样的规则时，可能会发现许多派生且可能无趣的规则 A′ → C′。这些派生规则的前件和后件的关联，仅仅是因为 A 和 C 之间的关联。比如，若 A 和 C 相关，那么对于与 A、C 都无关的项 B，AB 也会与 C 相关。 目前已有不少研究致力于自动识别和丢弃这类派生规则。例如，闭项集技术可识别那些移除某些元素而不改变规则支持度的规则；最小改进技术能识别移除某些元素而不降低规则置信度的规则。但由于探索性规则发现是基于样本数据来推断总体特征，规则可能因抽样波动而显得有趣。因此，也会应用统计测试来评估是否有证据表明移除元素会显著改变规则相对于总体的状态。不过，这些技术仅能处理因添加无关或无效元素而产生的派生规则。 实际上，还存在另一种派生规则，可能会产生大量对用户来说可能无趣的规则。对于规则 AB → C，若其并非从其他规则派生而来，且前件和后件存在关联，那么 A 和 B 可能分别仅因 AB 和 C 的关联而与 C 相关。此时，A → C 和 B → C 可能就是探索性规则发现系统会发现的潜在无趣的派生规则。 例如，零售商试图识别可能购买新产品的客户群体。应用影响规则发现和规则过滤器后，得到两条规则： - District = A → profit(coverage = 200, mean = 100) - District = A & age < 50 → profit(coverage = 100, mean = 200) 虽然这两条规则经规则过滤器判定为“显著”，但第一条规则具有误导性。实际上，属于地区 A 且年龄大于 50 岁的客户不会产生利润。零售商应更关注地区 A 中年龄小于 50 岁的客户群体，保留第一条规则可能会使决策者困惑。 影响规则发现是探索性规则发现的一种，其规则的后件是未离散化的定量变量（目标），并通过其分布来描述。本文将在影响规则发现的背景下研究第二种派生规则的识别。 #### 2. 探索性规则发现 许多机器学习系统从可用数据中发现单个模型，期望该模型在未知未来数据上最大化某个有趣性目标函数，并基于此模型进行预测或分类。然而，可能存在性能相当的替代模型，且判断模型优劣的标准因应用场景而异。探索性规则发现技术通过搜索满足用户定义约束条件的多个模型，并将这些模型呈现给用户，提供更多选择，从而实现更大的灵活性。 探索性规则发现技术可分为命题规则发现和分布后件规则发现。命题规则发现寻找仅含定性属性的规则，命题规则由布尔条件组成；分布后件规则发现寻找后件为未离散化定量变量的规则，其未离散化定量属性的状态或性能通过分布描述。关联规则发现、对比集发现和相关规则发现属于命题探索性规则发现，而影响规则发现或定量关联规则发现属于分布后件规则发现。分布后件规则能更好地描述定量变量和定性属性之间的相互关系。 由于命题规则发现和分布后件规则发现存在差异，它们在规则修剪和优化技术上也有内在区别。研究人员已付出大量努力开发规则修剪和优化技术。 探索性规则发现的一些关键概念定义如下： 1. 对于命题规则发现，记录是应用布尔谓词（条件）的元素；对于分布后件规则发现，记录是一对 < c, v >，其中 c 是非空布尔条件集，v 是用户感兴趣的定量变量的值集。 2. 若规则 r1 的主体是规则 r2 主体的子集，则 r1 是 r2 的父规则。若 r1 主体的基数比 r2 小 1，则 r2 是 r1 的直接父规则；否则，r2 是 r1 的非直接祖先规则。 3. 用 coverset(A) 表示满足条件 A 的记录集。若记录 x 在 coverset(A) 中，则称 x 被 A 覆盖。若 A 为空集，coverset(A) 包含数据库中的所有记录。Coverage(A) 是被 A 覆盖的记录数，即 coverage(A) = |coverset(A)|。 #### 3. 影响规则发现 本文的影响规则发现算法基于 OPUS 搜索算法构建，该算法能成功发现满足用户指定约束条件的前 k 个影响规则。 k - 最优影响规则发现的相关术语定义如下： 1. 影响规则形式为 A → target，目标通过覆盖度、均值、方差、最大值、最小值、总和和影响等指标描述。例如： Address = Brighton & profession = programmer → income (coverage : 23%, mean : 60000, variance : 4000, max : 75000, min : 44000, sum : 1380000, impact : 3903.98) 2. 影响是 Webb 提出的有趣性度量：impact(A → target) = (mean(A → target) - targ) × coverage(A)。 3. k - 最优影响规则发现任务是一个 6 元组：KOIRD(D, C, T, M, λ, k)。 - D：非空记录集，即数据库。记录是一对 < c, v >，c ⊆ C，v 是 T 的值集。D 是全局总体 D 的可用样本。 - C：非空布尔条件集，是影响规则前件的可用条件集，由 D 中的给定数据生成。 - T：用户感兴趣的变量的非空集。 - M：约束集，规则必须满足的标准。 - λ：{X → Y} × {D} → R 是从规则和数据库到值的函数，定义了一个有趣性度量，λ(X → Y, D) 值越大，规则在该数据库中的有趣性越高。 - k：用户指定的整数，表示规则发现任务最终解决方案集中的规则数量。 影响规则发现的原始算法伪代码如下： ```p ```