大数据实体识别相关技术研究

来源:用户上传      作者:

　　摘 要：爆炸式增长的信息量带来严重的数据质量问题。实体识别是数据清洗的一项关键技术，用以识别存在不同形式的同一对象，或区分同一形式的不同对象。介绍了实体识别相关技术，阐述了实体识别技术过程与方法，并对面向大数据的实体识别技术进行了展望。
　　关键词：大数据;数据质量;实体识别
　　DOI：10. 11907/rjdk. 191621
　　中图分类号：TP301   文献标识码：A                 文章编号：1672-7800（2020）003-0125-03
　　Research on Related Technologies for Big Data Entity Identification
　　SHA Ren1， LIANG Qiong-fang1， LI Chang-ming2， ZHANG Jia-xin1
　　（1. College of Information Science and Technology，Northeast Normal University;
　　2. Changchun Guanghua University， Changchun 130000， China）
　　Abstract： Data quality problems are particularly serious due to the explosive growth of information. Entity recognition is a key technology for data cleaning to identify different objects in different forms or to distinguish different objects in the same form. This paper outlines the problem of entity recognition， summarizes the technology of entity recognition and looks forward to the entity recognition technology for big data.
　　Key Words：big data; data quality; entity recognition
　　0 引言
　　隨着信息时代的来临，数据量爆发式增长，这些规模庞大的数据具有巨大的挖掘价值，但也存在大量数据质量问题，如重复数据、缺失数据、陈旧数据等，劣质数据导致可用性大打折扣，数据清洗引起广泛关注。实体识别（Entity Identification）是数据清洗的一项关键技术，其主要目的就是准确识别出同一实体，将数据对象与现实世界的真实实体一一对应，即对数据库中元组对是否指代同一实体进行判别，以此达到去除冗余、消解不一致的数据清洗效果。本文主要根据大数据实体识别过程总结相关技术工作并展开讨论。
　　1 实体识别
　　数据质量可从6个维度定义：①精确性（Accuracy），指数据描述现实事物的接近程度;②完整性（Completeness），指数据集的完整程度;③时效性（Timeliness），描述数据的新旧程度;④一致性（Consistency），描述数据内部的矛盾程度;⑤相关性（Relevancy），描述数据与应用需求的契合程度;⑥实体同一性（Entity identity），指数据描述同一个现实世界事物数据的冗余程度[1]。
　　实体同一性（Entity identity）是数据质量的重要标准之一，描述同一个现实世界中事物的数据冗余程度。例如同一实体的不同表现形式，或命名相同但并不是同一现实事物。不同文献对于实体识别有不同的名称，比如对象识别（Object Identification）、记录链接（Record Linkage）以及实体解析（Entity Resolution）等等[2]。因此，大数据实体识别的主要任务就是在海量数据中寻找描述同一事物的若干元祖。
　　下面对实体识别的常用概念进行形式化定义说明实体识别问题：
　　定义1  复杂数据集合D{d1，d2，…，d|D|};
　　定义2  真实世界的物理实体集合E{e1，e2，…，e|E|};
　　定义3  数据集中记录集合R{r1，r2，…，r|R|};
　　定义4  记录R的属性集合A{a1，a2，…，a|A|};
　　定义5  A的属性值集合V{v1，v2，…，v|V|}，且满足？ vi∈V，？rj∈R，aq∈A的情况下rj.aq=vi。
　　根据以上形式化定义，实体识别问题可以阐述为将数据源集合D的记录集合R划分为[R′]， [R′]中的每个集合与集合E中的物理实体一一对应。因此实体识别算法的输入是R，输出是经过解析的记录集合[R′]{r1，r2，…，r|E|}（[R′]是E的不相交子集集合，[R′]所有集合的并集为E）。
　　2 大数据实体识别过程
　　大数据实体识别过程为：首先对大数据进行分块预处理，以提高识别效率。然后对分块处理后的数据进行相似关系计算并匹配，匹配成功的数据为同一实体。实体识别过程如图1所示。
　　2.1 预处理阶段
　　预处理阶段是实体识别过程的关键阶段。在实体识别过程中，一般将实体对逐一比较。假设有大小为x和y的两个数据集需要匹配，则要进行x*y次元组比较。但在大数据环境下，这样比较非常耗时，计算代价高。因此，在实体对比较之前，为避免进行笛卡尔级别运算，提高实体识别效率 ，根据某种知识或规则将数据分成规模更小的数据块（Block），只在块内进行数据比较，这种方法统称为分块技术（Block Technique）[3]。 　　2.1.1 固定分块方法
　　最早的分块方法是固定分块方法（Fixed-Sized Partition）[4]，按照固定大小将数据分块，每个元组只能插入到一个块中。固定分块方法大大提高了数据处理效率，但缺点也非常明显：容易造成数据浪费及相关信息缺失。
　　2.1.2 相邻排序方法
　　为弥补固定分块缺陷，Hernandez & Stolfo[5-6]提出了相邻排序分块方法（Sorted Neighborhood），将元组进行排序，然后采用固定长度滑动窗口方式进行分块，如图2所示。但固定大小的滑动窗口会导致不相近的相似元组不能分到一个块中，因此Yan等[7]提出了根据元组相似度改变滑动窗口大小的分块方法。根据相似元组多少改变滑动窗口大小，这样保证了每个块中包含全部的相似度高的元组。
　　2.1.3 Canopy聚类方法
　　数据分块可以看作是將相似元组聚类到一起，因此可使用聚类算法进行分块。大多数聚类算法复杂度高，但分块方法需要低计算复杂度且高速的聚类方法。因此，针对分块特点，Han等[8]提出了Canopy聚类算法：首先将数据集中的每条记录都映射到空间中，通过距离函数distance（x，y）快速计算键值距离，任取记录中的一点并建立新的块，将与该点距离小于一定阈值的并入到块中，删除距离远的点。通过不断迭代重复，将元组插入到不同块中，直到距离大于一定的阈值，但该聚类方法对聚类中心的选取依赖性较高。
　　2.1.4 基于映射的分块方法
　　Jin等[9]提出了一种基于映射的分块方法，其基本思想是利用String Map算法将数据字符串映射到多维空间上，这样可以保留字符串之间的原始相似度，然后将相似度大的对象插入到相同类中生成块[10]。这种方法计算复杂度较高，因此在该算法的基础上提出了基于double-embedding的索引技术[11]，将映射到多维空间的对象通过FastMap算法映射到更低维度的空间，最后利用KD-tree和近邻相似度方法结合抽取对象从而生成块。
　　2.2 相似匹配阶段
　　实体进行分块后，便对块中数据进行实体匹配以达到识别效果。数据通过相似匹配方法将元组对分为匹配和不匹配，匹配的元组代表同一实体，不匹配的为不同实体，相关技术介绍如下。
　　2.2.1 基于阈值方法
　　基础的实体识别方法是设定阈值，将元组对比较向量中的每个相似度值简单相加得到总的相似度，再与设定的阈值进行比较，根据比较结果判定元组对是否匹配。该方法缺陷显而易见，首先是属性值的简单求和并没有考虑到属性的重要度，因此有很多根据属性重要度设定权重计算相似度大小的改进方法;其次是求和过程中每个单独相似性信息丢失了，因此研究出复杂的实体分类器，通过单个相似度进行实体识别，这种方法对阈值设定的专业度有很强的依赖性。
　　2.2.2 基于概率方法
　　通过概率方法可将实体识别问题作为贝叶斯推理问题[12]。设定不匹配U类和匹配M类，x为比较向量，通过判定规则将x划分到U或M类中。当每个类的密度函数是已知时，x在U类和M类中的密度函数是不同的，这样实体识别问题就成为一个贝叶斯推理问题。
　　判定规则描述如下：
　　x为元组对<r1，r2>的一个比较向量，如果匹配类M的概率大于U的概率，则x被分到M中，否则分到U中。
　　利用贝叶斯定理可表示为
　　其比例[lx=p（x|M）p（x|U）]是似然率。这种判定规则称为最小错误的贝叶斯测试（the Bayes test for minimum error），可保证错误的最小概率，是一个最优的分类器。但是这种方法很难应用于现实生活中，因为需要已知[p（x|M）]，[p（x|U）]的分布和先验概率[p（U）]和[p（M）]。但该方法假设独立，即当[i≠j]时，概率[p（xi|M）]和概率[p（xj|M）]独立。
　　2.2.3 有监督分类方法
　　通过机器学习方法进行实体识别需要将一部分有标记的匹配元组对作为训练集，训练出分类器，再用分类器进行分类。比如一种基于SVM的自动分类算法，首先从训练集中挑选出明显是M类和U类的比较向量集合，用它们作为训练集生成一个最初的SVM，再利用该SVM对剩下的比较向量进行分类，找到离SVM判定边界最远的比较向量加入训练集，再得到第二个SVM，如此循环迭代直到满足终止条件。
　　2.2.3 主动学习方法
　　有监督的分类算法需要依赖训练集，对训练集的要求较高，训练集必须尽可能代表整个数据库中的元祖特征，训练集的质量决定最后实体识别算法的优劣。为解决这个问题，提出了主动学习的方法。该方法初始只需要小的训练集，然后建立一个交互式分类模型，通过向专家用户提问的方式获取训练样本。主动学习的实体识别方法可以在保证尽可能减少样本数量的同时精确性依然很高，但显而易见，该方法对专家用户的依赖性比较高。
　　2.2.3 基于聚类的方法
　　目前很多实体识别方法都是通过聚类进行的。例如根据某个相似度对元组进行排序，再使用一个优先队列存放最近生成的类。将排序好的元组同优先队列的元组进行比较，相似便插入其中，并将该类移到优先队列的最顶端。若未成功匹配则建立新的类。
　　另一种聚类方法是基于图的聚类，比如著名的CENTER聚类算法，首先将数据元组对生成图，然后对图进行聚类，聚类后的每个子图为一个实体。CENTER聚类算法首先找到每个子图的中心，然后将元组插入到距离最近的中心所代表的类里。这种聚类方式使得类中心的选取非常重要，会极大影响最终的分类结果，因此改进方法之一是若类的中心相似度高便合并两个类。同时，还有基于密度的聚类，匹配元组密度大，不匹配的密度小。这种方法的好处是不需要根据全局阈值，只根据邻居数量和密度就可达到聚类效果。 　　面对大数据的实体识别，目前主要通过分布式平台并使用基于阈值、基于聚类以及两者或多种技术相结合的方法达到大数据实体识别的目的，如李明达等使用Hyracks作为并行处理平台，将n-Gram算法进行并行优化实现了面向大数据的实体识别;霍然等使用Map-Reduce并行框架，通过图聚类的方法进行大数据实体识别;李鹏等使用Map-Reduce框架在Hadoop平台上将基于机器学习的算法并行，使其应用于大数据实体识别;胡志刚等将数据分块后建立超图模型，在Hadoop平台上进行超图聚类，等等。
　　3 结语
　　实体识别技术已经相对成熟，但大数据实体识别技术刚开始引起重视。由于分块技术主要用于提高实体识别算法效率，因此分块技术计算复杂度低、耗时短，以及部分精确度较高的分块技术并不适用，同时缺少针对实体识别的分块技术;在数据方面，大多是对于简单数据的实体识别，对于复杂结构的数据处理较少，特别是对图数据的处理工作并不多;目前多为针对静态数据的处理，而现今社会更需要大数据的实时识别，这些都是未来大数据实体识别技术的重点发展方向。
　　参考文献：
　　[1]刘显敏， 李建中. 实体识别问题的相关研究[J]. 智能计算机与应用， 2013， 3（2）：1-5.
　　[2]朱灿，曹健. 实体解析技术综述与展望[J]. 计算机科学， 2015，42（3）： 13-17， 23.
　　[3]FISHER J，CHRISTEN P，WANG Q， et al. A clustering-based framework to control block sizes for entity resolution[C]. the 21th ACM  SIGKDD Int’l Conference on Knowledge Discovery and Data Mining，2015：279-288.
　　[4]FELLEGI I P， SUNTER A B. A theory for record linkage[J]. Journal of the AmericanStatistical Association， 1969， 64（328）：1183-1210.
　　[5]HERN M A， STOLFO S J. The merge/purge problem for large databases[J]. ACM SIGMOD Record. 1995（24）：127-138.
　　[6]HERN M A，STOLFO S  J. Real-world data is dirty： data cleansing and themerge/purge problem[J]. Data mining and knowledge discovery，1998，2（1）：9-37.
　　[7]YAN S，LEE D，KAN M Y， et al. Adaptive sorted neighborhood methods for efficient record linkage[C]. Proceedings of the 7th ACM/IEEE-CS joint conferenceon Digital libraries，2007：185-194.
　　[8]HAN J，MICHELINE K. Data mining： concepts and techniques[J]. San Francisco，CA， itd： Morgan Kaufmann， 2001（5）：52-59.
　　[9]JIN L，LI C， MEHROTRA S. Efficient record linkage in large data sets[C]. Eighth International Conference on Database Systems for Advanced Applications， 2003.
　　[10]FALOUTSOS C，LIN K I. Fastmap： a fast algorithm for indexing， data-mining andvisualization of traditional and multimedia datasets[M]. ACM， 1995.
　　[11]ADLY N. E？cient record linkage using a double embeddingscheme.[C]. DMIN，2009：274-281.
　　[12]NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vitalRecords[EB/OL]. http：//xueshu.baidu.com/usercenter/paper/show？paperid=09504bb66585863508df8b826e57445a.
　　（責任编辑：杜能钢）
　　收稿日期：2019-04-28
　　作者简介：莎仁（1993-），女，东北师范大学信息科学与技术学院硕士研究生，研究方向为教育大数据;梁琼芳（1993-），女，东北师范大学信息科学与技术学院硕士研究生，研究方向为教育支撑软件;李长明（1990-），男，硕士，长春光华学院助教，研究方向为大数据;张家鑫（1992-），男，东北师范大学信息科学与技术学院硕士研究生，研究方向为教育大数据。本文通讯作者：李长明。
转载注明来源:https://www.xzbu.com/8/view-15217857.htm