数据挖掘中的实体识别问题

如今，在几乎所有存储和处理大量数据的场所都在使用数据挖掘。数据集成是数据预处理的主要任务之一。将多个数据库或数据文件集成到一个同类数据的单一存储中，称为数据集成。

数据集成通常是为了创建机器学习算法的数据集，并在数据挖掘过程中预测数据中的统计信息。我们从各种资源集成数据，例如银行交易、发票、客户记录、Twitter、博客文章、图像、音频或视频数据、电子数据交换 (EDI) 文件、电子表格和传感器数据。

数据挖掘通常需要数据集成，合并来自多个数据存储的数据，将来自多个来源的数据合并到一个一致的数据存储中，就像在数据仓库中一样。这些来源可能包括多个数据库、数据立方体或平面文件。数据集成中有许多问题需要考虑，例如模式集成和对象匹配。

因此，仔细的集成可以帮助减少和避免结果数据集中出现的冗余和不一致。这有助于提高后续数据挖掘过程的准确性和速度。数据的语义异构性和结构给数据集成带来了巨大挑战。我们如何匹配不同来源的模式和对象？或者如何匹配来自多个数据源的等效的现实世界实体？这个问题被称为实体识别问题。

数据集成中的问题

数据集成中存在以下问题，例如：

1. 数据冗余

当我们合并来自多个数据库的数据时，会出现数据冗余。如果不删除冗余数据，数据分析期间将获得不正确的结果。冗余数据出现的原因如下。

• 对象标识：同一属性或对象在不同数据库中可能有不同的名称。
• 可导出数据：一个属性可能是另一个表中的“导出”属性，例如，年收入

2. 重复数据属性

信息中的重复项通常存在于一个或多个其他属性中。

3. 不相关属性

数据中的某些属性不重要，在执行数据挖掘任务时不会考虑它们。例如，学生 ID 通常与预测学生 GPA 的任务无关

。在数据中包含此类不相关属性没有用处。

4. 实体识别问题

实体识别问题发生在数据集成过程中。在集成来自多个资源的数据时，一些数据资源会相互匹配，如果集成，就会变得冗余。来自多个数据源的等效现实世界实体被匹配起来，就称为这个问题。

例如：A.cust-id =B.cust-number。其中 A、B 是两个不同的数据库表。Cust-id 是表 A 的属性，cust-number 是表 B 的属性。这里 cust-id 和 cust-number 是不同表的属性，这些表之间没有关系，但 cust-id 属性和 cust-number 属性的值相同。这是关系中实体识别问题的一个例子。元数据可用于避免此类模式集成中的错误。这确保了源系统的功能依赖和引用约束与目标系统匹配。实体识别问题有助于检测和解决数据值冲突。数据通常从多个资源收集到一个一致的存储中，并且可以是不同的维度和数据类型。数据有不同的表示方式，数据也有不同的尺度。实体识别问题可能发生在虚拟和实际数据库集成中。

• 虚拟集成：通常使用公共数据模型和集成模式在组件数据库之上创建虚拟集成数据库。组件保留其身份和使用方式。联邦自治数据库的努力方向是这个方向。
• 实际集成：从组件数据库创建实际集成数据库。原始数据库被丢弃，应用程序迁移到新的集成数据库。

在单个数据库上下文中，对象实例通常可以唯一地建模一个现实世界实体。此属性不适用于多个自治数据库，因此会出现实体识别问题。例如，当我们将两个对象实例添加到单个数据库中的关系时，对象实例与现实世界实体之间的一对一对应关系确保了两个新的对象实例引用不同的现实世界实体。但是，当两个对象实例被添加到不同数据库中的关系时，这种一对一对应关系可能消失。

大多数组织中预先存在的数据库是由不同的人在不同的时间定义的和填充的，以响应不同的组织或最终用户需求。这种独立开发数据库的结果常常是两个数据库捕获了同一现实世界域的部分内容。通常，当需要为这些相关数据库提供集成访问时，在不指定额外的语义信息来解决这种歧义的情况下，将同一现实世界实体在两个数据库中的表示联系起来通常是困难的，甚至是不可能的。

数据库集成中的实体识别

集成预先存在的自治数据库的任务必须解决参与数据库独立设计时出现的逻辑异构性。逻辑异构性可以在模式级别和实例级别发生。模式级别异构性的分辨率称为模式集成。实例级别异构性的分辨率称为实例集成。

1. 模式级别

参与数据库的元数据信息，同样适用于所有实例，是不兼容的。此级别的兼容性问题包括：

• 域不匹配：相似属性的域在结构或语义上不兼容。例如，一个关系中的货币属性是美元，而另一个关系中的货币属性是日元。结构不匹配的例子是，一个关系中的姓名属性数据类型为字符串。相比之下，另一个关系中的姓名属性由三个字符串数据类型的子属性组成：姓、名和中间名。这是一个语义不匹配的例子。
• 模式不匹配：当两个数据库的模式结构和语义不兼容时，就会出现此问题。例如，一个数据库中的“员工”表可能对应于另一个数据库中的“兼职员工”和“全职员工”表的联合。
• 约束不匹配：参与数据库中指定的约束可能不兼容。例如，研究生数据库可能要求所有研究生累积 GPA 大于 3.0。相比之下，计算机科学系数据库可能要求所有研究生累积 GPA 大于 3.5。

2. 实例级别

模式在结构（属性域）和语义（属性含义）上是兼容的，但尚未识别和合并对应于同一现实世界实体的实例。在此级别发生的两个问题是：

• 实体识别：这是从不同数据库中识别对应于同一现实世界实体的对象实例的问题。
• 属性值冲突：当两个数据库中建模现实世界实体相同属性的属性值不匹配时，就会发生属性值冲突。这种冲突可能由数据尺度冲突、数据不一致、数据缺失甚至潜在的模式建模错误引起。数据尺度冲突发生在语义相关的属性的域使用不同的测量单位时。数据不一致发生在语义等效的属性具有不同值时。缺失数据是指建模相同现实世界的对象实例没有相同属性集的情况。很明显，属性值冲突的解决只能在实体识别问题解决之后进行。

模式级别的同名异义词和同义词问题通常在模式集成阶段解决。在实际数据库集成的情况下，实例级别的问题必须随后解决才能完成集成过程。在虚拟数据库集成的情况下，解决实例级别问题所需的策略和信息必须在设计时（即模式集成阶段）指定，但实际处理仅在查询时发生。

当对参与数据库进行更新时，可能需要执行实例集成。因为实体识别是实例集成中要解决的第一个问题，所以需要有效和高效的方法来处理它。

方法

现有的实体识别方法可分为以下几类：

1. 使用键等价：许多方法假设来自不同数据库的、建模同一实体类型的关系之间存在一些公共键，例如 Multibase。因为键可用于唯一地将对象实例与现实世界实体关联起来，所以可以使用公共键值的等价性来解决问题。然而，这种方法是有限的，因为关系可能没有公共键，即使它们可能共享一些公共键属性。

2. 用户指定等价：此方法要求用户指定对象实例之间的等价性，例如，作为映射本地对象 ID 到全局对象 ID 的表，即匹配对象实例的责任分配给用户。由于匹配表可能非常大，因此这种方法可能非常繁琐。尽管如此，它是一种通用方法，可以处理同名异义词和同义词问题。已为 Pegasus 项目建议了此技术。

3. 使用概率键等价：Pu 没有坚持键的完全等价，而是建议使用受限域中键值的子集来匹配对象实例。作为键等价的一个例子，通过匹配名字的子字段来解决名字匹配问题。如果两个给定名字中的大部分子字段匹配，则认为这两个名字是相同的。虽然这种方法可以产生高置信度的匹配结果，但它仅适用于关系之间存在公共键的情况。匹配的概率性质也可能导致错误的匹配。

4. 概率属性等价：Chatterjee 和 Segev 建议使用两个关系之间的所有公共属性来确定实体等价。根据概率模型，为两个关系中的每对记录分配一个比较值。

5. 使用启发式规则：Wang 和 Madnick 使用基于知识的方法来解决问题。一组启发式规则用于推断要匹配的对象实例的附加信息。由于使用的知识是启发式的，因此产生的匹配结果可能不正确。

实体识别问题解决方案

我们提出了一种解决实体识别问题的新方法。该方法与以前的方法在以下几个方面不同：

1. 我们的技术是在期望获得健全的匹配结果的假设下开发的。例如，一家希望解雇销售业绩不达预期的员工的公司，需要匹配一个数据库中的员工记录和另一个数据库中的绩效记录。匹配的记录必须是正确的；否则，一些人可能会被错误地解雇。我们的技术通过使用关于集成现实世界的有效约束来执行匹配，从而实现了健全性。只有当对象实例满足某种身份规则时，才对其进行匹配。这与一些依赖于启发式方法或概率模型的其他方法形成对比。
2. 我们的技术消除了对要匹配的关系之间存在公共键的要求。这为实体识别提供了一种更通用的方法。
3. 通过使用匹配表来包含实体识别的结果，我们的技术并不排除使用其他方法来断言表中其他可能的匹配记录对。例如，知识渊博的用户可以直接向匹配表中添加条目。