多关系数据挖掘：方法、挑战与应用

### 多关系数据挖掘：方法、挑战与应用 #### 1. 多关系数据挖掘概述 关系数据库是结构化数据最常用的存储库，其中多个关系通过实体 - 关系链接相互关联。然而，许多传统分类方法（如神经网络和支持向量机）只能处理单一的“扁平”关系形式的数据，即单表数据。但在现实世界的许多应用中，如信用卡欺诈检测、贷款申请和生物数据分析等，决策过程需要基于关系数据库中多个关系所存储的信息。因此，多关系数据挖掘成为了一个具有战略重要性的领域。 多关系数据挖掘（MRDM）旨在直接从关系数据中发现知识，其任务包括多关系分类、聚类和频繁模式挖掘等。 #### 2. 多关系分类 ##### 2.1 多关系分类的基本概念 在多关系分类的数据库中，存在一个目标关系 \(R_t\)，其元组称为目标元组，并与类标签相关联，其他关系为非目标关系。每个关系可能有一个主键（唯一标识关系中的元组）和多个外键（一个关系中的主键可以链接到另一个关系中的外键）。以二分类问题为例，我们选择一个类作为正类，另一个作为负类。构建准确的多关系分类器的关键任务是在不同关系中找到有助于区分正、负目标元组的相关特征。 例如，在一个金融数据库中，目标关系为“Loan”，每个目标元组表示贷款是否按时偿还（正或负）。多关系分类的任务就是利用不同关系中的信息构建一个假设，以区分正、负目标元组。 多关系分类中最常用的假设形式是规则集。每条规则是一个谓词列表（逻辑合取），并与一个类标签相关联。谓词是对关系中属性的约束，通常基于特定的连接路径定义。一个目标元组只有在满足规则中的每个谓词时，才满足该规则。 例如，谓词 “\(p1 = Loan(L, , , , payment >= 12, )\)” 表示贷款 \(L\) 的期限不少于 12 个月，这是一个数值谓词；谓词 “\(p2 = Loan(L, A, , , , ), Account(A, , frequency = monthly, )\)” 定义在 “Loan ▷◁Account” 的连接路径上，表示贷款的关联账户的频率为 “每月”，这是一个分类谓词。 ##### 2.2 ILP 方法在多关系分类中的应用 归纳逻辑编程（ILP）是多关系分类中最广泛使用的方法类别。常见的 ILP 系统包括 FOIL、Golem 和 Progol 等。FOIL 是一种自顶向下的学习器，构建的规则能覆盖许多正例和较少的负例；Golem 是自底向上的学习器，从最具体的规则进行泛化；Progol 使用组合搜索策略。近年来的方法，如 TILDE、Mr - SMOTI 和 RPTs 等，借鉴了 C4.5 的思想，从关系数据中归纳构建决策树。 虽然许多 ILP 方法能实现较好的分类准确率，但大多数方法在数据库关系数量方面的可扩展性不高。在具有复杂模式的数据库中，目标关系通常可以通过多个连接路径与每个非目标关系连接，需要探索大量的连接路径。为了识别好的特征，许多 ILP 方法会沿着不同的连接路径反复连接关系，并基于连接后的关系评估特征，这非常耗时，尤其是当连接后的关系包含的元组比目标关系多很多时。 以 FOIL 为例，它是一种顺序覆盖算法，一次构建一条规则。构建规则时，每次添加一个谓词，在每一步评估所有可能的谓词，并将最佳谓词添加到当前规则中。为了评估谓词 \(p\)，FOIL 临时将其添加到当前规则中形成规则 \(r + p\)，然后构建一个新的数据集，包含满足 \(r + p\) 的所有目标元组以及连接路径上的相关非目标元组。谓词 \(p\) 的评估基于满足 \(r + p\) 的正、负目标元组的数量，使用 “foil gain” 度量： 设 \(P(r)\) 和 \(N(r)\) 分别表示满足规则 \(r\) 的正、负元组的数量。当前规则为 \(r\) 时，谓词 \(p\) 的 “foil gain” 计算如下： \(I(r) = -\log\frac{P(r)}{P(r)+N(r)}\) \(foil gain(p) = P(r + p)\cdot[I(r)-I(r + p)]\) 直观上，“foil gain(p)” 表示通过将 \(p\) 添加到当前规则中，在表示正元组时节省的总比特数，它表明了将 \(p\) 添加到规则中可以提高规则的预测能力的程度。 ##### 2.3 元组 ID 传播 元组 ID 传播是一种执行虚拟连接的技术，可大大提高多关系分类的效率。它不是物理地连接关系，而是通过将目标元组的 ID 附加到非目标关系的元组上，实现虚拟连接。这样，就可以像进行了物理连接一样评估谓词。元组 ID 传播灵活且高效，因为 ID 可以轻松地在任意两个关系之间传播，只需要少量的数据传输和额外的存储空间，并且可以减少冗余计算。 假设目标关系的主键是一个整数属性，表示每个目标元组的 ID（如果没有，可以创建这样的主键）。设两个关系 \(R_1\) 和 \(R_2\) 可以通过属性 \(R_1.A\) 和 \(R_2.A\) 连接。在元组 ID 传播中，\(R_1\) 中的每个元组 \(t\) 与目标关系中的一组 ID 相关联，用 \(IDset(t)\) 表示。对于 \(R_2\) 中的每个元组 \(u\)，设置 \(IDset(u) = \bigcup_{t\in R_1,t.A = u.A}IDset(t)\)，即 \(R_1\) 中元组 \(t\) 的 \(IDset\) 中的元组 ID 会传播到 \(R_2\) 中与 \(t\) 在属性 \(A\) 上可连接的每个元组 \(u\)。 例如，在一个包含 “Loan” 和 “Account” 关系的数据库中，通过 “account ID” 进行连接。可以将 “Loan” 元组的 ID 和类标签传播到 “Account” 关系中，避免物理连接。 元组 ID 传播虽然有价值，但需要一定的约束。有两种情况可能导致传播适得其反：一是通过大扇出进行传播，即传播到一个关系 \(R\) 后，发现 \(R\) 中的每个元组都与许多目标元组连接，且每个目标元组都与 \(R\) 中的许多元组连接，此时 \(R\) 与目标关系之间的语义链接通常很弱；二是通过长而弱的链接进行传播，例如将学生与他的汽车经销商的宠物联系起来，这种传播可能没有成效。为了提高效率和准确性，应避免通过此类链接进行传播。 ##### 2.4 使用元组 ID 传播的多关系分类：CrossMine CrossMine 是一种使用元组 ID 传播进行多关系分类的方法。为了更好地整合 ID 传播信息，CrossMine 使用复杂谓词作为规则的元素。一个复杂谓词 \(p\) 包含两部分： 1. **prop - path**：指示如何传播 ID。例如，路径 “Loan.account ID →Account.account ID” 表示使用 “account ID” 从 “Loan” 传播 ID 到 “Account”。如果不涉及 ID 传播，“prop - path” 为空。 2. **constraint**：是一个谓词，指示对传播 ID 的关系的约束，可以是分类或数值的。 例如，规则 “Loan(L,+) : −Loan(L, A, , , , ), Account(A, , frequent = monthly, )” 可以表示为 “Loan(+) : −[Loan.account ID →Account.account ID, Account.frequency = monthly]”。 CrossMine 构建一个包含一组规则的分类器，每条规则包含一个复杂谓词列表和一个类标签。其算法如下： ```plaintext Algorithm: CrossMine. Rule - based classification across multiple relations. Input: D, a relational database; Rt a target relation. ```