实体解析是数据融合和数据清洗的关键步骤,旨在从大量的数据集中找出描述相同实体的记录。当前主要有两种基本的解决思路,一种是穷尽式的实体解析,通过两两比较数据集中的所有记录,然后再合并相似的记录,从而找到描述某一个实体的若干记录集合。然而,该方法的计算复杂度比较高(O(n2),其中 n 表示数据集合的规模),难以处理大型数据集合。另一种思路是基于分块的实体解析,它调用特定的分块函数(如哈希函数、滑动窗口技术等)将集合中较为相似的记录划分到同一个块中,再仅对属于同一块中的记录进行两两比较。这种方法显著降低了运行时间,但会损失部分精度,因为某些描述同一实体的记录可能没有被分到同一个块中。文中提出了一种基于模式的实体解析算法,通过将相似的记录合并成记录集合并尝试生成对应的记录模式,然后进行模式之间的两两比较来产生一个边界值,以确定对应的记录集合是否需要进行进一步的精确比较,从而判断是否属于同一个实体。与第一种方法相比,该方法可有效地过滤部分不可能相似的记录,从而避免了针对所有数据记录进行两两比较,显著地降低了时间复杂度;与第二种方法相比,该方法并不损失任何精度。基于真实和模拟数据集合的实验结果验证了新方法的执行效率和有效性。
数据融合、数据清洗、实体解析、编辑距离、字符串相似度
TP311(计算技术、计算机技术)
国家“九七三”重点基础研究发展规划项目基金2012CB316203;国家自然科学基金61370101,61321064;上海市教委科研创新重点项目14ZZ045资助.This work is supported by the National Basic Research Program973 Programof China project2012CB316203;the National Natural Science Foundation of China under Grant.61370101,61321064;the Innovation Program of Shanghai Municipal Education Commission 14ZZ045.