一种基于质量控制的数据填充方法及系统的制作方法

一种基于质量控制的数据填充方法及系统的制作方法
【技术领域】
[0001] 本申请设及数据库处理技术领域，特别是设及一种基于质量控制的数据填充方法 及系统。
【背景技术】
[0002] 通常，在各类数据库的数据源中，往往会存在一些空缺信息，有些是因为原始数据 的缺失造成的，有些是因为操作上的失误造成的。该些数据库中的空缺信息会造成数据不 完整，是各类数据库中一个较为普遍的问题，数据填充技术的提出就是希望通过一些技术 手段来估算、预测、或者找回数据源中的空缺信息。
[0003] 现有的针对字符串型数据的数据填充方法通常可分为两类；基于推理的数据填充 方法和基于检索的数据填充方法。
[0004] 基于推理的数据填充方法主要是结合一些给定的数据质量规则（比如 化nctional Dependencies属性依赖关系），从数据集的其他部分推理出空缺处的空缺信 息。比如在一个地址数据集中，已知依赖关系"城市名称可W决定省份名称"，在数据集其中 一个元组中写着"学校='南京大学'，城市='南京'，省份='江苏'"，而另外一个元组写着 "学校='南航'，城市='南京'，省份(即第二个元组的省份为空缺信息），那么我们 就可W根据依赖关系把第二个元组中空缺的省份填写为"江苏"。
[0005] 基于检索的数据填充方法主要是从外部资源比如网络中检索获取空缺处的空缺 信息。当数据集中的空缺信息在万维网中存在时，该方法可W准确查找到空缺信息并填充 到数据集中的空缺处。
[0006] 然而，基于推理的数据填充方法的主要缺点体现在对于唯一的空缺信息的填补 上，也就是在数据集中的完整部分没有出现与该空缺信息相应的信息的话，那么就不可能 准确地推断和填充该空缺信息，造成数据填充的准确率低；而基于检索的数据填充方法虽 然能够准确填充空缺信息，提高数据填充的准确率，但其在对空缺信息进行检索时，需要在 外部资源中进行海量的检索查询，该会产生大量的检索查询操作，相应地就会造成很大的 系统开销。
[0007] 而且，上述方法均未考虑数据集中的数据依赖关系的可信度导致填充的数据的质 量控制问题，会导致填充的数据的可信度不高。

【发明内容】

[000引有鉴于此，本申请提供一种基于质量控制的数据填充方法及系统，W实现在较小 的系统开销下获得较高的数据填充准确率，并且提高所填充的数据的可信度。
[0009] 为了实现上述目的，本申请实施例提供的技术方案如下：
[0010] 一种基于质量控制的数据填充方法，包括：
[0011] 根据数据库中的已有数据确定所述数据库的空缺数据，构建所述数据库的数据依 赖关系并确定所述数据依赖关系的依赖可信度，重复执行W下步骤，直至所述数据库的空 缺数据被填充完毕：
[0012] 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据 中的可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据 中确定一组待检索数据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推 断数据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阔值时填充所 述可推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计 算检索可信度，在所述检索可信度大于所述预设阔值时填充所述待检索数据。
[0013] 优选地，所述根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库 的空缺数据中的可推断数据和至少一组不可推断数据，包括：
[0014] 从所述数据库的空缺数据中，根据所述数据库中的已有数据和所述数据依赖关系 确定与所述数据库中的已有数据存在数据依赖关系的空缺数据，作为所述数据库的空缺数 据中的可推断数据；
[0015] 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据 之间的空缺数据依赖关系；
[0016] W所述数据库的各个空缺数据为节点，W各个空缺数据之间的空缺数据依赖关系 作为节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数据依赖图确定所述数据 库的空缺数据中的至少一组不可推断数据。
[0017] 优选地，所述根据所述空缺数据依赖图确定所述数据库的空缺数据中的至少一组 不可推断数据，包括：
[0018] 从所述空缺数据依赖图的各个节点中，将存在相同空缺数据依赖关系且互相之间 不存在任何数据依赖关系的节点合并为一个节点，进行节点合并；
[0019] 节点合并之后，对于存在从多个节点指向自身的多个有向边的节点，删除从多个 节点指向自身的多个有向边，生成简化空缺数据依赖图；
[0020] 从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节点的有向边的节 点W及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作为所述数据库的 空缺数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。
[0021] 优选地，所述根据预设规则从所述至少一组不可推断数据中确定一组待检索数 据，包括：
[0022] 计算所述数据库中的每个空缺数据的期望值；所述期望值是所述数据库中的每个 数据成为空缺数据的概率；
[0023] 根据计算得到的所述数据库中的每个空缺数据的期望值，计算所述不可推断数据 中的每个空缺数据的解锁分数；所述解锁分数用于评估所述不可推断数据中的每个空缺数 据与所述不可推断数据中的其它空缺数据之间的数据依赖关系的大小；
[0024] 按照所述解锁分数由大到小的顺序依次选择所述不可推断数据中的空缺数据加 入检索集合，直至所述不可推断数据中的空缺数据或者在检索集合中，或者通过检索集合 中的空缺数据推断得到时，将所述检索集合中的空缺数据作为所述待检索数据。
[0025] 优选地，所述外部资源包括互联网资源。
[0026] 一种基于质量控制的数据填充系统，包括：
[0027] 构建模块，用于根据数据库中的已有数据确定所述数据库的空缺数据，构建所述 数据库的数据依赖关系并确定所述数据依赖关系的依赖可信度；
[002引填充模块，用于重复执行W下步骤，直至所述数据库的空缺数据被填充完毕：
[0029] 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据 中的可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据 中确定一组待检索数据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推 断数据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阔值时填充所 述可推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计 算检索可信度，在所述检索可信度大于所述预设阔值时填充所述待检索数据。
[0030] 优选地，所述填充模块，包括：
[0031] 第一确定模块，用于从所述数据库的空缺数据中，根据所述数据库中的已有数据 和所述数据依赖关系确定与所述数据库中的已有数据存在数据依赖关系的空缺数据，作为 所述数据库的空缺数据中的可推断数据；
[0032] 第二确定模块，用于根据所述数据库中的已有数据和所述数据依赖关系确定所述 数据库的空缺数据之间的空缺数据依赖关系；
[0033] 第=确定模块，用于W所述数据库的各个空缺数据为节点，W各个空缺数据之间 的空缺数据依赖关系作为节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数据 依赖图确定所述数据库的空缺数据中的至少一组不可推断数据。
[0034] 优选地，所述第=确定模块，包括：
[0035] 节点合并单元，用于从所述空缺数据依赖图的各个节点中，将存在相同空缺数据 依赖关系且互相之间不存在任何数据依赖关系的节点合并为一个节点，进行节点合并；
[0036] 有向边修剪单元，用于节点合并之后，对于存在从多个节点指向自身的多个有向 边的节点，删除从多个节点指向自身的多个有向边，生成简化空缺数据依赖图；
[0037] 查找单元，用于从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节 点的有向边的节点W及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作 为所述数据库的空缺数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。 [003引优选地，所述根据预设规则从所述至少一组不可推断数据中确定一组待检索数据 的填充模块，用于：计算所述数据库中的每个空缺数据的期望值；所述期望值是所述数据 库中的每个数据成为空缺数据的概率；
[0039] 根据计算得到的所述数据库中的每个空缺数据的期望值，计算所述不可推断数据 中的每个空缺数据的解锁分数；所述解锁分数用于评估所述不可推断数据中的每个空缺数 据与所述不可推断数据中的其它空缺数据之间的数据依赖关系的大小；
[0040] 按照所述解锁分数由大到小的顺序依次选择所述不可推断数据中的空缺数据加 入检索集合，直至所述不可推断数据中的空缺数据或者在检索集合中，或者通过检索集合 中的空缺数据推断得到时，将所述检索集合中的空缺数据作为所述待检索数据。
[0041] 优选地，所述外部资源包括互联网资源。
[0042] 由W上本申请提供的一种基于质量控制的数据填充方法，根据数据库中的已有数 据确定所述数据库的空缺数据，构建所述数据库的数据依赖关系并确定所述数据依赖关系 的依赖可信度，重复执行W下步骤，直至所述数据库的空缺数据被填充完毕：根据所述数 据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据中的可推断数据和至 少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据中确定一组待检索数 据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推断数据并根据所述依 赖可信度计算推断可信度，在所述推断可信度大于预设阔值时填充所述可推断数据，从所 述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计算检索可信度，在所 述检索可信度大于所述预设阔值时填充所述待检索数据。该样，通过推断和检索的交替执 行，高效且高质量地实现数据集中空缺数据的填充，可W实现在较小的系统开销下获得较 高的数据填充准确率。
[0043] 而且，由于本方法在填充数据时充分考虑了数据依赖关系的依赖可信度，并根据 依赖可信度计算推断的数据的推断可信度和检索的数据的检索可信度，只有在推断可信度 大于预设阔值时才填充推断的数据，在检索可信度大于预设阔值时才填充检索的数据，该 样能够保证填充的数据得到良好的质量控制，使得填充的数据的可信度较高。
【附图说明】
[0044] 为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本 申请中记 载的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下， 还可W根据该些附图获得其他的附图。
[0045] 图1为本申请提供的基于质量控制的数据填充方法的样例数据表W及数据依赖 关系的不意图；
[0046] 图2为本申请实施例提供的基于质量控制的数据填充方法的交互过程的示意图；
[0047] 图3为本申请实施例提供的基于质量控制的数据填充方法的构建简化空缺数据 依赖图的过程的示意图；
[0048] 图4为本申请提供的基于质量控制的数据填充方法的一种实施例的流程示意图；
[0049] 图5为本申请提供的基于质量控制的数据填充方法的另一种实施例的流程示意 图；
[0050] 图6-图10分别为本申请提供的基于质量控制的数据填充方法与现有技术的实验 数据对比图；
[0化1] 图11为本申请提供的基于质量控制的数据填充方法的质量控制阔值的选择示意 图；
[0052] 图12为本申请提供的基于质量控制的数据填充系统的一种实施例的结构示意 图；
[0053] 图13为本申请提供的基于质量控制的数据填充系统的另一种实施例的结构示意 图。
【具体实施方式】
[0054] 为了使本技术领域的人员更好地理解本申请中的技术方案，下面将结合附图，对 本申请的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施 例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性 劳动前提下所获得的所有其他实施例，都应当属于本申请保护的范围。
[0055] 下面结合附图，对本申请的实施方案进行详细描述。
[0056] 图1为本申请提供的基于质量控制的数据填充方法的样例数据表W及数据依赖 关系的不意图。
[0057] 图4为本申请提供的基于质量控制的数据填充方法的一种实施例的流程示意图。 [0化引参照图4所示，本申请实施例提供的基于质量控制的数据填充方法包括：
[0059] 步骤S100 ;根据数据库中的已有数据确定所述数据库的空缺数据，构建所述数据 库的数据依赖关系并确定所述数据依赖关系的依赖可信度；
[0060] 在本申请实施例中，首先给出方案用到的定义：
[0061] 1.对于数据表中的属性X，Y，满足属性依赖X-Y。如果表中存在某些元组违反此 约束条件，则称此属性依赖X-Y为近似属性依赖^f为表中数据满足约束X-Y 的可信程度，即依赖可信度。那么，基于该近似属性依赖关系的推断规则和检索查询的可信 度也为f。
[00创 2.推断可信度；给定近似属性依赖X-Y，元组Ti和T班属性X和Y上的表达式 为：
[0063]
[0064] T2在Y上的值为空，该里用方块表示。推断得到的结果□=yi的推断可信度由W 下公式给出：
[00 化]
[0066]即推断规则及使用的值的可信度乘积，此勿
表示元组Ti在属性X上的值Xi 的推断可信度为^'(、）。
[0067] 3.检索可信度；给定近似属性依赖X-Y，元组Ti在属性X和Y上的表达式为；
[0068]
检索得到的结果□=yi的检索可信度定义为：
[0069]
[0070] 即检索规则与使用的值的可信度乘积。
[0071] 在本申请实施例中，由于数据库中存在已有数据，则除去已有数据，即为空缺数 据。而且同一数据库中的所有数据之间通常包含一定的数据依赖关系。
[0072] 该里的数据依赖关系包括已有数据和空缺数据之间的依赖关系，已有数据和已有 数据之间的依赖关系，W及空缺数据和空缺数据之间的依赖关系。
[0073] 步骤S200 ;根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库 的空缺数据中的可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不 可推断数据中确定一组待检索数据；
[0074] 在本申请实施例中，"可推断数据"是指可W根据数据依赖关系由已有数据推断出 的空缺数据，可推断数据与已有数据之间存在数据依赖关系。
[0075] 比如；一个地址数据集中，包含数据依赖关系"城市名称可W决定省份名称"，则在 该地址数据集其中一个元组中写着"学校='南京大学'，城市='南京'，省份='江苏'"，而 另外一个元组写着"学校='南航'，城市='南京'，省份(即第二个元组的省份为空 缺信息），那么我们就可W根据数据依赖关系把第二个元组中空缺的省份推断为"江苏"。
[0076] 在本申请实施例中，"不可推断数据"是无法直接由已有数据推断出的空缺数据， 与已有数据之间并不存在直接的数据依赖关系。
[0077] 另外，"不可推断数据"作为空缺数据的一部分，可能与其它的空缺数据之间存在 数据依赖关系，也可能与其它的空缺数据之间不存在数据依赖关系。
[007引当"不可推断数据"与其它的空缺数据之间存在数据依赖关系时，"不可推断数据" 被填充W后，即可根据被填充的"不可推断数据"（被填充后即为已有数据）来推断其它的 空缺数据，当"不可推断数据"与其它的空缺数据之间不存在数据依赖关系时，即便被填充 也无法推断其它的空缺数据。
[0079] 步骤S300 ;根据所述数据库中的已有数据和所述数据依赖关系推断所述可推断 数据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阔值时填充所述 可推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计算 检索可信度，在所述检索可信度大于所述预设阔值时填充所述待检索数据；
[0080] 在本申请实施例中，将"根据所述数据库中的已有数据和所述数据依赖关系推断 并填充所述可推断数据"称为推断步骤，将"从所述数据库的外部资源中检索并填充所述待 检索数据"称为检索步骤。
[0081] 由于"可推断数据"是指可W根据数据依赖关系由已有数据推断出的空缺数据，可 推断数据与已有数据之间存在数据依赖关系，所W可W直接由已有数据和所述数据依赖关 系推断出"可推断数据"，然后填充，则填充后的"可推断数据"即成为已有数据。
[0082] 同时，由于"不可推断数据"是无法直接由已有数据推断出的空缺数据，与已有数 据之间并不存在直接的数据依赖关系，所W从外部资源比如互联网资源中查找该"不可推 断数据"并填充，可W保证所填充的数据的准确性。
[0083] 可W理解的是，本申请实施例中，当一次推断就填充了所有的空缺数据时，即可省 去后续的检索步骤，而当没有可推断的数据时，也可W先进行检索步骤再进行推断步骤，本 实施例中的步骤标号并不用作对方法实施顺序的限定。
[0084] 步骤S400 ;判断所述数据库的空缺数据是否被填充完毕；如果否，返回步骤S200 ; 如果是，结束。
[0085] 本申请实施例提出一种基于质量控制的数据填充方法，根据数据库中的已有数据 确定所述数据库的空缺数据，并构建所述数据库中所有数据之间的数据依赖关系，重复执 行W下步骤，直至所述数据库的空缺数据被填充完毕；根据所述数据库中的已有数据和所 述数据依赖关系确定所述数据库的空缺数据中的可推断数据和至少一组不可推断数据，并 根据预设规则从所述至少一组不可推断数据中确定一组待检索数据，根据所述数据库中的 已有数据和所述数据依赖关系推断并填充所述可推断数据，从所述数据库的外部资源中检 索并填充所述待检索数据。
[0086] 该方法交替使用推断和检索来填充数据：
[0087] 比如；所述数据依赖关系确定所述数据库的空缺数据中的可推断数据确定待填充 到所述数据库中的所有空缺数据中的第一可推断数据组和第一待检索数据组；根据所述数 据依赖关系推断并填充所述第一可推断数据组中的数据，从所述数据库的外部资源中检索 并填充所述第一待检索数据组中的数据，并确定所述数据库中的第一剩余空缺数据；根据 所述数据依赖关系，确定所述第一剩余空缺数据中的第二可推断数据组和第二待检索数据 组；根据所述数据依赖关系推断并填充所述第二可推断数据组中的数据，从所述数据库的 外部资源中检索并填充所述第二待检索数据组中的数据，并确定所述数据库中的第二剩余 空缺数据；依次类推，直至待填充到所述数据库中的所有空缺数据被填充完毕。
[008引目P;推断并填充所述数据库中的第一组空缺数据，从所述数据库的外部资源中检 索并填充所述数据库中的第二组空缺数据；根据所述已有数据、所述第一组空缺数据和所 述第二组空缺数据，推断并填充所述数据库中的第=组空缺数据，从所述数据库的外部资 源中检索并填充所述数据库中的第四组空缺数据；依次类推，直至待填充到所述数据库中 的空缺数据被填充完毕。
[0089] 下面举例说明：本申请实施例提供的基于质量控制的数据填充方法的交互过程如 图2所示；
[0090] (1)0.8-SDI(注；SDI;StochasticDataImputation为有质量控制的交互式填补的 英文简称，其中的0.8为质量控制阔值，即为本申请实施例中的预设阔值）方法的交互过程 如下图所示；
[0091] (2)第一次推断步骤（图2(a));根据表中已有数据化及图2(b)中的依赖关系，可 W推断出Ti圧]、Ti的、T2巧]的值分别为bi、61、fi，可信度分别为0. 95、0. 95、0. 90。
[009引 做第一次检索步骤（图2化)）；假设检索到Ts巧]、Ts出]的值分别为b2、b3,对应 的可信度分别为0.95、0.95。
[0093] (4)第二次的推断因为阔值0.8的限制，导致不存在可W推测的数据。
[0094] 妨第二次检索步骤（图2(c));检索到T3[C]、Ts脚的值分别为C2、d2,对应的可 信度分别为0.95、0.95。
[0095] (6)第S次推断步骤（图2(d));根据第二次检索到的值W及表的依赖关系，可W 推断TJC]、TJD]的值分别为〇3、ds，对应的可信度分别为0. 95、0. 95。
[0096] (7)第立次检索步骤（图2(e));检索到T4圧]、Ts圧]的值都为62,对应的可信度 都为1(该里省略不写）。
[0097] 做第立次检索步骤（图2讯）；根据第立次检索得到的T4圧]和Ts圧]的值W及 属性E和F的依赖关系，可W推理出T4 [円、Tg[円的值都是f2,对应的可信度都为1 (该里省 略不写）。至此，所有空缺值填充结束。
[009引当一次推断步骤最大程度地填充所有可推断的空缺数据后，接下来的检索步骤可W检索到一系列不可推断的空缺数据，从而使得在下一次推断步骤中一些剩余的空缺数据 可W推断出来。连续重复该两个步骤直到出现结束条件比如没有可W填充的空缺数据 后， 结束对空缺数据的填充。
[0099] 通过推断步骤和检索步骤交替填充数据，可W使得系统的开销较小且数据填充准 确率较高，该样，通过推断和检索的交替执行，可w高效且高质量地实现对于数据集中的空 缺数据的填充，可W实现在较小的系统开销下获得较高的数据填充准确率。因此，本申请实 施例提供的基于质量控制的数据填充方法，能够在数据填充中确定最佳方案，并且通过该 个方案，能够W最小填充代价（系统开销）达到很高的填充精确度和召回率。
[0100] 而且，由于本方法在填充数据时充分考虑了数据依赖关系的依赖可信度，并根据 依赖可信度计算推断的数据的推断可信度和检索的数据的检索可信度，只有在推断可信度 大于预设阔值时才填充推断的数据，在检索可信度大于预设阔值时才填充检索的数据，该 样能够保证填充的数据得到良好的质量控制，使得填充的数据的可信度较高。
[0101] 图3为本申请实施例提供的基于质量控制的数据填充方法的构建简化空缺数据 依赖图的过程的示意图。
[0102] 图5为本申请提供的基于质量控制的数据填充方法的另一种实施例的流程示意 图。
[0103] 参照图5所示，本申请实施例提供的基于质量控制的数据填充方法，所述步骤 S200中的根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据 中的可推断数据和至少一组不可推断数据，包括：
[0104] 步骤S201 ;从所述数据库的空缺数据中，根据所述数据库中的已有数据和所述数 据依赖关系确定与所述数据库中的已有数据存在数据依赖关系的空缺数据，作为所述数据 库的空缺数据中的可推断数据；
[01化]步骤S202 ;根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库 的空缺数据之间的空缺数据依赖关系；
[0106] 步骤S203 所述数据库的各个空缺数据为节点，W各个空缺数据之间的空缺数 据依赖关系作为节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数据依赖图确 定所述数据库的空缺数据中的至少一组不可推断数据。
[0107] 在填充过程当中，TRIP方法最关键的是在检索步骤中选择最少的空缺数据进行检 索，从而使得系统开销最小，得到最佳调度方案。
[0108] 得到最优调度方案的算法如下：
[0109]构建空缺数据依赖图：图3(a)、化）、（C)所示为构建过程。
[0110] 步骤1 ;将所有未填补的空缺数据当做空缺数据依赖图中的节点，如图3(a)所示。
[0111] 步骤2 ;将空缺数据之间所有可能的数据依赖关系当做节点间的有向边，至此，形 成了空缺数据依赖图，如图3(b)所示。
[0112] 在本申请实施例中，根据所述空缺数据依赖图确定所述数据库的空缺数据中的至 少一组不可推断数据，首先要对构建而成的空缺数据依赖图进行简化，然后利用简化空缺 数据依赖图确定所述数据库的空缺数据中的至少一组不可推断数据，简化过程包括：
[0113] 节点合并单元，用于从所述空缺数据依赖图的各个节点中，将存在相同空缺数据 依赖关系且互相之间不存在任何数据依赖关系的节点合并为一个节点，进行节点合并；
[0114] 有向边修剪单元，用于节点合并之后，对于存在从多个节点指向自身的多个有向 边的节点，删除从多个节点指向自身的多个有向边，生成简化空缺数据依赖图；
[0115] 步骤3 ;空缺数据依赖图的简化：
[0116] (1)节点合并：如果某些拥有相同数据依赖关系并且该些节点间不存在任何数据 依赖关系的话，就将该些节点合并成一个节点，如图3 (c)所示，〇5和0e，〇7和0g合并成了一 个节点。
[0117] (2)边修剪：对于节点合并之后的空缺数据依赖图，如果图中存在该样一种依赖 关系，需要多个节点同时满足才能推出另外的一个节点，该时就需要修剪掉该样的依赖关 系边。如图3(b)所示，〇4, 0。，〇eS个节点需要同时满足才能推出Og，并且该S个节点还可 W同时推出〇7和〇8、〇llW及0 12,该时就要修剪掉从〇4, 〇5, 〇e出发指向〇9的边，同样地，指 向〇7和〇8、〇1拟及〇12的边也需要修剪掉。
[0118] 最终形成图3(c)所示的简化空缺数据依赖图。
[0119] 从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节点的有向边的节 点W及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作为所述数据库的 空缺数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。
[0120] 确定待检索数据；待检索数据都是不能推断出来的，共有两类：
[012U (1)如图3(d)所示，为第二次检索步骤的简化空缺数据依赖图，如05,0e该个合并 后的节点，从图中很明显可W看出，没有从其它节点出发指向该节点的边，所W0e，0e是要 检索的。
[012引似不存在外部的节点指向内部节点的有向边的节点集合，也就是说，一个节点集 合被包含在推断死锁中，并且不能从死锁外部的节点推断出该节点集合内的节点，所W可 W认为该样的节点集合中的节点是不可推断的，因此是要检索的点。如图3(c)所示，04和 05,化构成了一个死锁，所W可W选择检索04或者检索05,06,为了确保代价最小即检索个数 最少，因此选择检索04;同理对于0 7, 08和01趨择检索011。
[0123] 在本申请实施例中，根据预设规则从所述至少一组不可推断数据中确定一组待检 索数据，包括：贪屯、算法确定最优检索方案：
[0124] 为了便于理解，我们先假设所有空缺值事先已经知道，然后给出我们的最优解决 方案，然后拓展到空缺值事先不知道真实情况，并给出近似最优解决方案。
[01巧]1.确定近似最优解锁子集
[01%] 给依赖图中的每个节点定义一个解锁分数，解锁分数最大的节点将被贪婪的选入 解锁集合。
[0127] ?解锁单个死锁
[0128] 为实现最优解锁方案，本贪婪算法总是偏向于选择可W带来最少检索次数和最多 推测次数的节点，来解锁其所在的死锁D，并将其加入解锁集合中。我们给每个节点定义一 个解锁分数，用来评估节点A对于打破上面提到死锁的贡献度，A解锁分数可W被定义为：
[0129]S血。ck(AID) =IInfer(A，D，T)I-1A
[0130] 其中Infer (A,化T)表示死锁D中，如果W T为阔值检索A之后，可化填充的所 有数据集合。I，|表示返回集合的大小。开始时，计算每个结点的解锁分数，选择解锁分数 最大的结点加入检索集合，然后更新剩下的节点解锁分数，按照W上规则重新选取解锁分 数最大的节点，直至死锁D中的值或者在检索集合中，或者可W通过检索集合中的值推测 得到。
[0131] ?解锁共享结点的多个死锁
[0132] 上面的贪婪算法加W延伸，可W用来解锁共享从属关系的多个死锁。设D为死锁 中所有值W及其死锁从属，我们计算D中每个节点的解锁分数，然后选择分数最大的节点 加入到解锁集合Ud中，不断更新剩余节点的解锁分数、选择新节点，直到D中所有节点已经 在Ud中，或者可W根据UD中的值推测得到。
[0133] 2.确定最优期望解锁集合
[0134] 上面提到的根据解锁分数确定近似最优解锁集合是基于一个重要的假设；空缺值 事先已经知道，但是现实世界中，空缺值事先并不知道。所W我们根据为每个为空缺值计算 得到的带有概率的期望值，来为每个结果计算期待解锁分数。根据上面的贪屯、算法，我们提 出另一种变种的贪屯、算法，来选取期望解锁分数最大的子集来检索。下面首先介绍如何估 计空缺值的期望值及其概率，然后展示如何计算期望解锁分数。
[01巧]?估算带有概率的期望值
[0136] 假如表中的属性之间没有任何依赖关系，则表R中属性Y上的元素y成为当前属 性上某空缺值得可能性可由W下公式给出：
[0137]Pg(Y=y) =Percent(Y=y|R)
[013引其中Percent (Y=y|R)表示属性Y上值为y的元组所占的百分比。
[0139] 假如表中的属性之间存在依赖关系Xi-Y(i=l，2,3-k)，则该些依赖关系应 当被考虑。我们使用一个长度为k的布尔向量JT表示表中的其他元组r与T在Xi(i= 1, 2, 3"'k)上的关系。并且规定，如果元组T'在属性X;上的值a=a;，则31 [i] =true, 否则JT[i] =false。
[0140] 我们定义一个元组r在Y上的值y'可w成为当前列上的空缺值得权重为：
[0141]
[01创其中T0 )表示JT山=true的所有i集合，F0 )表示JT山=false的i集 合。最终，T[刊=y的概率可由W下公式定义：
[0143]
[0144] 其中0是所有可能的JT的集合，R[n]是集合R中与元组T有JT关系的元组集 合，Percent(Y=y|R[ 31 ])表示在R[JT]的所有元组中Y=y的百分比。
[0145] ?估算期望解锁分数
[0146] 根据计算得到的每个空缺值的期望值，我们计算死锁中的每个解锁子集的解锁分 数，使用下面的公式：
[0147]
[0148]该里=n,C.(K,估算每个y,被填充到第i个空缺Bi处被采纳的概率。 9 = [y。72,…]包含所有可能的yi值填充Bi的情况，Infer (A,化0，T)表示在给定阔值T时，死锁D中的空缺值取0中的某个值时，通过检索A，可W被推测的所有空缺数据子 集。
[0149] 则本申请实施例提供的在T-SDI中的最优期望方案算法为：
[0150] 检索和推断选择性的交互进行，然而，在每一次的检索步骤时，我们根据空缺值， 建立一个阔值为C的推断依赖图。所有不可推断值都直接放入Ri，所有死锁放入死锁集合。 对于每个死锁，我们选出解锁分数最高的推断子集，并放入而，检索而中的值，接着进入下 一步的推断步骤，直到没有空缺值可W被填充。
[0151] 算法；检测T-SDI情况下的最优期望方案
[0152] 输入；一个不完整表，空缺值集合为0
[015引输出；数据填充方案S= <10,R。I。…，R。，I。〉
[0巧4]令i = 0 [0巧5] do
[0156] 1. 11^所有当前可推理到的值
[0157] 2.推理li中的所有值 [0巧引3. i++
[0159] 4.建立一个阔值为T的推理依赖图
[0160] 5.而^ T限制下无法推断的值
[0161] 6. Foreach共享结点的死锁集合D do
[0162] 计算死锁D的每 个解锁子集的解锁分数
[016引RiU解锁分数最大的解锁子集S^iwk_E[0164] 7.检索R冲的所有空缺值
[01化]While
[0166] Return。。，Ri,I。…，R。，I。〉
[0167] 该样就可W在保证所填充的数据的准确性的前提下，使得需要检索的数据量最 小，可W避免在外部资源中进行海量的检索查询，尽量减少检索查询操作，降低系统开销。
[0168] 检索少量的空缺数据能极大的提高基于推断的方法的填充召回率，为了保证在最 小开销下能够获得最高的召回率，应最少的使用检索操作，尽可能多的使用推断操作。
[0169] 下面举例说明本发明的实验效果：
[0170] 一、实验环境、
[017U 操作系统；MacOSX
[0172] 处理器；4核屯、IntelCore巧
[0173]内存；8GB
[0174] 编程语言；Java [017引二、数据集
[0176] 选择4个数据集，其中2个为现实生活中的数据集，另外两个为人工合成的数据 集。
[0177] (1)个人信息表（Personinfo);该张表含有5万个元组，每个元组有9个属性，分 别为姓名、邮箱、头衔、大学、街道、城市、州、国家和邮件地址。该些信息是从美国、英国、加 拿大和澳大利亚的1000所不同大学收集得到的。
[0178] (2)DBLP发表信息表值BLP);该张表含有10万个元组，每个元组有5个属性，分别 为发表的论文的标题、第一作者、会议名称、年份和地点。表中所有的论文信息都是从DBLP 上随机选择的。
[0179](3)合成表格I(Syn-I);我们合成了一张10万元组，每个元组100个属性的表 格，包含1000个随机产生的属性依赖关系，每个依赖关系的可信度为1. 0,表中的第一列属 性为主属性。
[0180] (4)合成表格n(Syn-n);与合成表格（Syn-I)的规模一样，第一列也是主属性。 区别在于属性依赖的可信度为0到1之间的随机数。
[0181] W上的表格为完整的关系表，为了产生实验需要的不完整表，我们随机的移除完 整表中的值，但是保证每个元组至少保留一个主属性。即对于化rsonin化，名字或者邮箱至 少保留一个，对于DBLP，论文标题会被保留，两个合成表的第一列属性会被保留。
[0182]S、实验方法
[0183]对于不同的空缺率（1%，5%，10%，20%，30%，40%，50%，60%)，我们使用不 同的随机种子产生了 5个不完整的表，W下的实验结果为5次实验的平均结果。注意，对于 合成表，我们从原始表中检索数据而非从因特网上，我们记录了检索的次数。
[0184] 四、实验结果对比分析
[01化]在真实数据上，我们选择和目前最先进的基于推断和基于检索的填补方法比较。
[0186] (1)基于推断的方法（Inferring-based);
[0187] InferRules;根据表中完整部分的属性依赖关系来推断空缺值。
[0188]GKNN;采用最先进的空缺定量数据的填补技术，主要是计算空缺值与训练数据间 的距离，然后选择k个最邻近（该里我们选k等于1)。
[0189]似基于检索的方法（Retrieving-based);
[0190] Web化t;该是一般的检索方法，主要是从各种数据集中检索空缺值。
[01W]In化Gather;该个方法了采用最先进的技术，能够从网页列表和报表中检索空缺 值。
[0192] ?准确性
[0193] 将所提出的TRIP方法和上述提到的方法分别在化rsonin化和DBLP数据集上进 行准确性比较，主要比较3个方面；（1)精确度（Precision);，所有已被填补数据的正确 填补的比率（2)召回率巧ecall);所有空缺值中正确填补的比率（3)F1;是precision和 recall的结合估量标准，计算公式为 2*precision*recall/(precision+recall)。
[0194] 图6和图7分别为TRIP方法与已有的4种填补方法在化rsoninfo和DBLP的准 确性比较。从该2张表中可W观察到，在填补数据方面，InferRules方法的精确度很高，大 约在90 %左右，但是它的召回率却很低；G脚W方法的精确度在60 %~70 %，不是很高，该是 因为GK順主要针对定量数据的填补，而我们实验的数据集都是非定量数据；In化Gather和 WebPut方法该2中基于检索的方法的精确度和召回率明显比基于推断的方法InferRules、 GKNN要高，并且WebPut具有更高达召回率；而TRIP方法能够达到相对很高的精确度和召 回率。
[0195] 图8为在不同的数据空缺率（MissingRatio)!%~60%下，该5种方法的F1该个 度量指标的变化。从图中可W观察到，WebPut和TRIP方法明显高于其它的方法，而且TRIP 方法只比WebPut方法低一点点。
[0196] 因此，从图6、图7和图8显示的实验结果中，我们可W明确得出TRIP在数据填补 方面具有很高的精确度和召回率。
[0197] ?代价
[0198] 分别在化rsonin化和DBLP数据集上，将TRIP和纯粹的基于检索的方法（Web化t) 和纯粹的基于推断的方法（InferRules)比较它们的代价，主要是2个方面；（1)时间代价 (Timecost);在一次填补过程中所花费的精确时间（2)查询（#Queries);产生的查询次数 (T= 0. 7)。
[0199] 图9为在数据集化rsoninfo和DBLP上，数据空缺率（MissingRatio) 1 %~ 60 %之间，TRIP方法和基于检索的方法化etrieving-based)、基于推断的方法 (Inferring-based)间时间花费的比较。从图中可W看出，基于推断的方法的时间花费非常 低，而基于检索的方法的时间花费却非常高，并且明显地观察到TRIP的时间效率将近是基 于检索的方法的10倍。
[0200] 图10为在数据集化rsoninfo和DBLP上，数据空缺率（MissingRatio)l%~60% 之间，TRIP方法和基于检索的方法化etrieving-based)间查询次数的比较。从图中可W 明显观察到，TRIP方法的检索查询次数明显比基于检索的方法少很多。
[020U因此，从图9和图10显示的实验结果中，我们可W明确得出TRIP在时间花费和查 询次数方面都具有很大的优势。
[0202] ?T的选择
[0203] 在数据集Syn-n上，我们设置缺失率为0. 4来评估最优期望方案在不同阔值T 的情况。
[0204] 由图11所示，随T的值由0增长到0.7,F1的值由0.4上升到0.9,但是随着T 由0. 7增长到1，F1的值快速下降。该是因为空缺值可W根据不同的近似属性依赖，使用不 同的推断方式得到可信度不同的值。因此，阔值限制的严或者太松都不会产生很好的填充 值。相应的，填充的代价随着T由0增长到0.7也由36*105增加到最大值62*10 5,因为更 高的T导致更多的值不能被推断出来，所W需要检索更多的值。然而，随着由0.7增长到 1，代价快速减少到26*1〇5,因为可使用的检索规则和推断规则随着T的增加会越来越少。
[0205] 对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但 是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某 些步骤可W采用其他顺序或者同时进行。
[0206] 本发明上述公开了一种基于质量控制的数据填充方法，相应的，本发明还公开了 应用上述基于质量控制的数据填充方法的基于质量控制的数据填充系统。
[0207] 图12为本申请提供的基于质量控制的数据填充系统的一种实施例的结构示意 图。
[020引参照图12所示，本申请实施例提供的一种基于质量控制的数据填充系统，包括：
[0209]构建模块1，用于根据数据库中的已有数据确定所述数据库的空缺数据，构建所述 数据库的数据依赖关系并确定所述数据依赖关系的依赖可信度；
[0210] 填充模块2,用于重复执行W下步骤，直至所述数据库的空缺数据被填充完毕：
[0211] 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据 中的可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据 中确定一组待检索数据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推 断数据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阔值时填充所 述可推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计 算检索可信度，在所述检索可信度大于所述预设阔值时填充所述待检索数据。
[0212]图13为本申请提供的基于质量控制的数据填充系统的另一种实施例的结构示意 图。
[0213]在本申请实施例中，参照图12所示，所述填充模块2,包括：
[0214] 第一确定模块21，用于从所述数据库的空缺数据中，根据所述数据库中的已有数 据和所述数据依赖关系确定与所述数据库中的已有数据存在数据依赖关系的空缺数据，作 为所述数据库的空缺数据中的可推断数据；
[0215]第二确定模块22,用于根据所述数据库中的已有数据和所述数据依赖关系确定所 述数据库的空缺数据之间的空缺数据依赖关系；
[0216] 第立确定模块23,用于W所述数据库的各个空缺数据为节点，W各个空缺数据之 间的空缺数据依赖关系作为节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数 据依赖图确定所述数据库的空缺数据中的至少一组不可推断数据。
[0217] 其中，所述第=确定模块23,包括：
[0218] 节点合并单元，用于从所述空缺数据依赖图的各个节点中，将存在相同空缺数据 依赖关系且互相之间不存在任何数据依赖关系的节点合并为一个节点，进行节点合并；
[0219]有向边修剪单元，用于节点合并之后，对于存在从多个节点指向自身的多个有向 边的节点，删除从多个节点指向自身的多个有向边，生成简化空缺数据依赖图；
[0220] 查找单元，用于从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节 点的有向边的节点W及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作 为所述数据库的空缺数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。
[0221] 所述根据预设规则从所述至少一组不可推断数据中确定一组 待检索数据的填充 模块2,用于；计算所述数据库中的每个空缺数据的期望值；所述期望值是所述数据库中的 每个数据成为空缺数据的概率；
[0222] 根据计算得到的所述数据库中的每个空缺数据的期望值，计算所述不可推断数据 中的每个空缺数据的解锁分数；所述解锁分数用于评估所述不可推断数据中的每个空缺数 据与所述不可推断数据中的其它空缺数据之间的数据依赖关系的大小；
[0223] 按照所述解锁分数由大到小的顺序依次选择所述不可推断数据中的空缺数据加 入检索集合，直至所述不可推断数据中的空缺数据或者在检索集合中，或者通过检索集合 中的空缺数据推断得到时，将所述检索集合中的空缺数据作为所述待检索数据。
[0224]所述外部资源包括互联网资源。
[02巧]需要说明的是，本实施例的基于质量控制的数据填充系统可W采用上述方法实施 例中的基于质量控制的数据填充方法，可W用于实现上述方法实施例中的全部技术方案， 其各个功能模块的功能可W根据上述方法实施例中的方法具体实现，其具体实现过程可参 照上述实施例中的相关描述，此处不再寶述。
[0226] 需要说明的是，本说明书中的各个实施例均采用递进的方式描述，每个实施例重 点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。 对于装置类实施例而言，由于其与方法实施例基本相似，所W描述的比较简单，相关之处参 见方法实施例的部分说明即可。
[0227] 专业人员还可W进一步意识到，结合本文中所公开的实施例描述的各示例的单元 及算法步骤，能够w电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和 软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。该些 功能究竟W硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业 技术人员可W对每个特定的应用来使用不同方法来实现所描述的功能，但是该种实现不应 认为超出本发明的范围。
[022引结合本文中所公开的实施例描述的方法或算法的步骤可W直接用硬件、处理器执 行的软件模块，或者二者的结合来实施。软件模块可W置于随机存储器（RAM)、内存、只读存 储器（ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术 领域内所公知的任意其它形式的存储介质中。
[0229] 最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将 一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示该些实体或操作 之间存在任何该种实际的关系或者顺序。而且，术语"包括"、"包含"或者其任何其他变体 意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括 那些要素，而且还包括没有明确列出的其他要素，或者是还包括为该种过程、方法、物品或 者设备所固有的要素。在没有更多限制的情况下，由语句"包括一个……"限定的要素，并 不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0230] W上对本发明所提供的方案进行了详细介绍，本文中应用了具体个例对本发明的 原理及实施方式进行了阐述，W上实施例的说明只是用于帮助理解本发明的方法及其核屯、 思想；同时，对于本领域的一般技术人员，依据本发明的思想，在【具体实施方式】及应用范围 上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。
【主权项】
1. 一种基于质量控制的数据填充方法，其特征在于，包括： 根据数据库中的已有数据确定所述数据库的空缺数据，构建所述数据库的数据依赖关 系并确定所述数据依赖关系的依赖可信度，重复执行以下步骤，直至所述数据库的空缺数 据被填充完毕： 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据中的 可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据中确 定一组待检索数据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推断数 据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阈值时填充所述可 推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计算检 索可信度，在所述检索可信度大于所述预设阈值时填充所述待检索数据。2. 根据权利要求1所述的方法，其特征在于，所述根据所述数据库中的已有数据和所 述数据依赖关系确定所述数据库的空缺数据中的可推断数据和至少一组不可推断数据，包 括： 从所述数据库的空缺数据中，根据所述数据库中的已有数据和所述数据依赖关系确定 与所述数据库中的已有数据存在数据依赖关系的空缺数据，作为所述数据库的空缺数据中 的可推断数据； 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据之间 的空缺数据依赖关系； 以所述数据库的各个空缺数据为节点，以各个空缺数据之间的空缺数据依赖关系作为 节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数据依赖图确定所述数据库的 空缺数据中的至少一组不可推断数据。3. 根据权利要求2所述的方法，其特征在于，所述根据所述空缺数据依赖图确定所述 数据库的空缺数据中的至少一组不可推断数据，包括： 从所述空缺数据依赖图的各个节点中，将存在相同空缺数据依赖关系且互相之间不存 在任何数据依赖关系的节点合并为一个节点，进行节点合并； 节点合并之后，对于存在从多个节点指向自身的多个有向边的节点，删除从多个节点 指向自身的多个有向边，生成简化空缺数据依赖图； 从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节点的有向边的节点以 及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作为所述数据库的空缺 数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。4. 根据权利要求1所述的方法，其特征在于，所述根据预设规则从所述至少一组不可 推断数据中确定一组待检索数据，包括： 计算所述数据库中的每个空缺数据的期望值；所述期望值是所述数据库中的每个数据 成为空缺数据的概率； 根据计算得到的所述数据库中的每个空缺数据的期望值，计算所述不可推断数据中的 每个空缺数据的解锁分数；所述解锁分数用于评估所述不可推断数据中的每个空缺数据与 所述不可推断数据中的其它空缺数据之间的数据依赖关系的大小； 按照所述解锁分数由大到小的顺序依次选择所述不可推断数据中的空缺数据加入检 索集合，直至所述不可推断数据中的空缺数据或者在检索集合中，或者通过检索集合中的 空缺数据推断得到时，将所述检索集合中的空缺数据作为所述待检索数据。5. 根据权利要求1所述的方法，其特征在于，所述外部资源包括互联网资源。6. -种基于质量控制的数据填充系统，其特征在于，包括： 构建模块，用于根据数据库中的已有数据确定所述数据库的空缺数据，构建所述数据 库的数据依赖关系并确定所述数据依赖关系的依赖可信度； 填充模块，用于重复执行以下步骤，直至所述数据库的空缺数据被填充完毕： 根据所述数据库中的已有数据和所述数据依赖关系确定所述数据库的空缺数据中的 可推断数据和至少一组不可推断数据，并根据预设规则从所述至少一组不可推断数据中确 定一组待检索数据，根据所述数据库中的已有数据和所述数据依赖关系推断所述可推断数 据并根据所述依赖可信度计算推断可信度，在所述推断可信度大于预设阈值时填充所述可 推断数据，从所述数据库的外部资源中检索所述待检索数据并根据所述依赖可信度计算检 索可信度，在所述检索可信度大于所述预设阈值时填充所述待检索数据。7. 根据权利要求6所述的系统，其特征在于，所述填充模块，包括： 第一确定模块，用于从所述数据库的空缺数据中，根据所述数据库中的已有数据和所 述数据依赖关系确定与所述数据库中的已有数据存在数据依赖关系的空缺数据，作为所述 数据库的空缺数据中的可推断数据； 第二确定模块，用于根据所述数据库中的已有数据和所述数据依赖关系确定所述数据 库的空缺数据之间的空缺数据依赖关系； 第三确定模块，用于以所述数据库的各个空缺数据为节点，以各个空缺数据之间的空 缺数据依赖关系作为节点之间的有向边，构建空缺数据依赖图，并根据所述空缺数据依赖 图确定所述数据库的空缺数据中的至少一组不可推断数据。8. 根据权利要求7所述的系统，其特征在于，所述第三确定模块，包括： 节点合并单元，用于从所述空缺数据依赖图的各个节点中，将存在相同空缺数据依赖 关系且互相之间不存在任何数据依赖关系的节点合并为一个节点，进行节点合并； 有向边修剪单元，用于节点合并之后，对于存在从多个节点指向自身的多个有向边的 节点，删除从多个节点指向自身的多个有向边，生成简化空缺数据依赖图； 查找单元，用于从所述简化空缺数据依赖图中，将只具有从自身出发指向其它节点的 有向边的节点以及与其它节点之间不存在任何有向边的节点集合对应的空缺数据作为所 述数据库的空缺数据中的至少一组不可推断数据；所述节点集合包括至少两个节点。9. 根据权利要求6所述的系统，其特征在于，所述根据预设规则从所述至少一组不可 推断数据中确定一组待检索数据的填充模块，用于：计算所述数据库中的每个空缺数据的 期望值；所述期望值是所述数据库中的每个数据成为空缺数据的概率； 根据计算得到的所述数据库中的每个空缺数据的期望值，计算所述不可推断数据中的 每个空缺数据的解锁分数；所述解锁分数用于评估所述不可推断数据中的每个空缺数据与 所述不可推断数据中的其它空缺数据之间的数据依赖关系的大小； 按照所述解锁分数由大到小的顺序依次选择所述不可推断数据中的空缺数据加入检 索集合，直至所述不可推断数据中的空缺数据或者在检索集合中，或者通过检索集合中的 空缺数据推断得到时，将所述检索集合中的空缺数据作为所述待检索数据。10. 根据权利要求6所述的系统，其特征在于，所述外部资源包括互联网资源。
【专利摘要】本申请公开了一种基于质量控制的数据填充方法，根据数据库中的已有数据确定空缺数据，构建数据库的数据依赖关系并确定数据依赖关系的依赖可信度，根据已有数据和数据依赖关系确定空缺数据中的可推断数据和至少一组不可推断数据，并根据预设规则从至少一组不可推断数据中确定一组待检索数据，根据已有数据和数据依赖关系推断可推断数据并根据依赖可信度计算推断可信度，推断可信度大于预设阈值时填充可推断数据，从外部资源中检索待检索数据并根据依赖可信度计算检索可信度，检索可信度大于预设阈值时填充待检索数据。推断和检索交替执行能在较小的开销下保证较高的填充准确率，且考虑了数据依赖关系的依赖可信度能够使填充的数据的可信度较高。
【IPC分类】G06F17/24, G06F17/30
【公开号】CN104881487
【申请号】CN201510304863
【发明人】李直旭, 周剑, 杨强, 李洋
【申请人】苏州大学张家港工业技术研究院
【公开日】2015年9月2日
【申请日】2015年6月4日