基于实体演化的记录链接算法 刘宏 申德荣 寇月 聂铁铮 于戈 东北大学计算机科学与工程学院 摘 要： 实体识别 (Entity Resolution) 是指判断一个或多个数据源中两个不同记录是否描述相同实体, 它有时也被称作记录连接 (Record Linkage) , 在数据集成中被用于数据清洗 (Data Clean) 、去重 (Deduplication) 和相似连接 (Similarity Joins) 等集成操作中.实体识别技术可被广泛应用于人口普查、引文识别、Web 搜索、数据清洗以及剽窃检验等诸多领域.然而, 在真实世界中, 实体的属性会随着时间的变化而变化, 两条记录的属性值不同不能表明这两条记录对应不同的实体, 具有相同的属性值的两条记录也不能表明对应相同的实体.时间记录链接就是匹配描述同一实体的带有时间戳的记录.已有的解决时间记录链接的方法依赖于时间模型来捕捉实体的演化, 但是已有的时间模型在预测实体的演化时, 实体匹配准确率不高, 而聚类计算复杂度较高.为此提出了更加细致的捕捉实体演化的模型和新的两阶段的快速聚类算法.通过在三个真实数据集上的实验结果表明, 提出的时间模型可以更加细致地捕捉实体的演化, 提出的聚类算法能更快速而准确的聚类描述同一实体的记录, 提高了识别的准确率和效率.关键词： 实体演化; 记录链接; 时间模型; 聚类算法; 作者简介：申德荣, E-mail:shendrmail.neu.edu.cn收稿日期：2017-09-16基金：国家自然科学基金 (61472070, 61672142) A temporal record matching based on entity evolutionLiu Hong Shen Derong Kou Yue Nie Tiezheng Yu Ge School of Computer Science and Engineering, Northeast University; Abstract： Entity resolution, also named as record linkage, is to judge whether two different records in one or more data sources belong to the same entity.In the area of data integration, entity resolution is widely used for data clean, deduplication and similarity joins.Entity resolution can be also widely applied in census, citation recognition, web search, data cleaning, plagiarism and inspection.However, in reality, entity attribute changes over time.That is, the two records with different attributes do not mean the two records belong to different entity.On the contrary, the two records with the same attributes also can not demonstrate the reference to the same entity.Then, the problem of linking temporal record, which aims at linking the records with time stamps, is proposed.Most state-of-the-art methods prefer to present different temporal models to capture the entity evolution.However, these temporal models have a low accuracy and a high computation cost in solving temporal record linkage.In this paper, we firstly present a more novel temporal model for capturing entity evolution.Then, a two-stage fast clustering algorithm are presented.Atlast, experimental results on three real-world datasets demonstrate that our temporal model has better performance in capturing the entity evolution, and our clustering algorithm is more fast and accurate in solving temporal record linkage.Keyword： entity evolution; record linkage; temporal model; clustering algorithm; Received： 2017-09-16记录链接1-4就是匹配描述真实世界同一实体的记录.记录链接被广泛地应用在数据集成、数据融合和个人信息管理中.当前, 传统的记录链接算法5-9都假设记录不带有时间信息, 然而, 实际数据集中的记录常常带有时间戳形式的时间信息, 随着时间的推移, 实体记录的属性值会随着时间的变化而变化, 因此, 考虑记录的时间信息能更好地进行记录链接.目前带有时间戳的记录链接算法10-14主要包括两部分:一是用于捕捉实体演化的时间模型, 是时间记录链接的核心部分;二是基于时间模型的聚类算法, 使得同一个聚类中的记录描述同一实体, 不同聚类中的记录描述不同的实体.用于记录链接的时间模型10-11,14主要基于以下两点:一是实体内属性不一致性, 即随着时间的变化, 属性值不同的两条记录不一定对应不同的实体.例如:作者名为 Xin Dong 的实体在 1991 年的单位是 Rensselaer Polytechnic Institute, 而在 2005 年 XinDong 的单位变为 University of Washington.二是实体间属性一致性, 即随着时间的变化, 属性值相同的两条记录也不一定对应同一实体.例如:不同的实体 Xin Dong 和 Xin Luna Dong 在 2005 年和 2007 年具有相同的单位名 University of Washington.已有的时间模型10-11主要有两种:一种为时间衰减模型10, 通过标签数据集来统计实体属性值的生命周期, 来预测实体的属性在一定的时间段内是否会发生改变.这种方式仅仅能预测实体的某一属性是变或者不变, 并不能很详细地捕捉实体属性值的变化情况.另一种是突变模型11, 通过统计实体的属性值重复出现的概率而评估属性值在某个时间点发生变异的概率.该模型基于对应同一实体 E 的一组记录来预测实体 E 在 r.t 时刻是否会发生突变, r是否为 E 的一个变异的记录.然而, 即使实体 E 发生突变, 那么是否会变为 r.A 的值, 无法确定, 或者说 E 变异为 r.A 的值的概率有多大, 该模型也不能预测.另外, 突变模型主要侧重捕捉实体内的属性值不一致性, 是基于实体内的属性值重现概率来预测实体内属性不一致的情况, 但无法准确预测实体间的属性值的一致性;换句话说, 用捕捉实体内属性不一致性的模型来捕捉实体间属性一致性的情况, 并不合适, 也不准确.当前, 基于时间模型的聚类算法10,12,14主要有基于时间衰减模型的调节约束算法 (Adjusted Binding) 和基于时间衰减模型的快速链接算法.前者由于时间复杂度大, 不能应用于大型的数据集;而后者采用先静态后动态的聚类原则, 能够改善算法的效率, 但由于时间衰减模型的准确率不高, 所以影响了整个算法的准确率.本文针对已有研究存在的不足, 提出了更为准确的捕捉实体内属性不一致性的实体内不一致衰减模型和捕捉实体间属性一致性的实体间一致衰减模型, 并提出了一种新的两阶段快速链接记录算法, 能够快速而准确地匹配对应同一实体的记录.本文的主要贡献点如下:(1) 提出了一种基于属性值转换表的实体内不一致衰减模型, 通过预测实体的属性在某个时间点发生改变的概率来捕捉实体内属性不一致性;提出了一种基于属性值转换表和条件概率的实体间一致衰减模型, 通过计算对应不同实体的属性值共现的概率来捕捉实体间属性一致性.(2) 提出了一种新的两阶段的快速匹配算法, 第一阶段是静态阶段, 思想是考虑实体不发生演化的情况, 聚类对应同一实体的记录, 同时将实体间一致衰减模型应用于相似度计算, 正确区分属性值相同但对应不同实体的记录;第二阶为动态聚类阶段, 思想是应用 Canopy 聚类方法进行聚类, 使得每一次聚类都尽可能的将对应同一实体的记录聚类到同一个聚类中.同时, 通过将本文提出的实体演化模型应用到相似度计算当中, 保证了在不牺牲算法准确率的情况下, 有效地提高了动态阶段聚类的速度.(3) 通过大量在真实数据集上的实验, 说明了本文提出的方法能更快速且准确地进行记录链接.1 相关工作当前, 有关基于实体演化的记录链接研究10-14备受关注.基于实体演化的记录链接算法主要侧重聚类带有时间戳的记录, 使得同一聚类中的记录对应同一实体, 不同聚类中的记录对应不同的实体.目前, 已有基于实体演化的记录链接算法都主要包含如下两部分:时间模型和基于时间模型的聚类算法.Li et al10和 Chiang et al11分别提出了捕捉实体演化的时间模型, 用于时间记录的匹配.Li et al10的时间衰减模型通过实体属性在一定时间间隔内是否发生改变的概率来捕捉实体演化, 通过不同实体有相同的属性值的概率来预测实体间的一致性的情况.Chiang et al11的变异模型通过捕捉实体属性值重现的概率来捕捉实体的演化.上述时间衰减模型和变异模型都侧重捕捉实体内属性不一致的情况, 对于实体间属性一致的情况考虑不足.同时这两种模型也没有考虑到属性值间的复杂的转换情况, 使得这两个模型在准确度方面都存在局限性.Li et al13提出了一种能捕捉更加复杂的属性值转换的模式.通过统计每一对属性值转换的次数来更好地预测实体属性值之间的转化, 这也是最早提出的考虑数据源15-16更新延迟对记录链接的影响的情况.Christen and Gayler14在 Li et al10的基础上, 首次提出了通过条件概率的方式来捕捉实体间属性一致性, 通过计算某个属性值重现的概率来捕捉实体间属性一致的情况.但是, 对于不同的时间间隔, 某一属性值重现的概率是不同的.因此, 如果不考虑时间的因素, 这种方式就不能很准确地预测实体间属性值一致的情况.同时, Christen and Gayler14使用监督学习的方式, 将聚类的结果应用于标签数据集使得训练出的模型更具准确性.基于以上的时间模型, 已提出的几个聚类算法10-14.Li et al10提出了三个聚类算法:Early binding 算法通过计算记录与已有聚类之间的相似度9,17来对记录进行聚类;Late binding 算法计算一个记录与多个聚类的相似度, 最后决定一个记录属于哪一个聚类