大数据下的实体识别算法研究

张风荣

摘 要： 大数据下的实体识别是提高数据实体同一性的关键步骤。本文概述了实体识别问题，介绍了不同类型的实体识别算法，重点分析了复杂数据类型的大数据实体识别算法，最后对实体识别算法的相关研究进行了展望。

关键词： 数据质量 数据清洗 实体识别

1.引言

在现实信息应用系统中如：多媒体、社交网络、物联网等诸多领域每天都积累了ZB级的大数据，这些数据具有规模庞大、涌现的速度快、可挖掘的价值大等特点，但同时有大量劣质数据存在，这些数据具有重复性、不完整性、陈旧性等特点。有关大数据质量的系列问题已经引起产业界和学术界的关注和重视。劣质数据降低了信息的可用性，给用户提供错误的信息，误导用户做出错误的决策，从而给用户造成损失。统计数据显示，50%以上的数据仓库项目由于数据质量问题而不得不取消或延迟。在典型的信息系统项目中，时间和成本预算的30%～80%实际用于清理数据而非系统开发。专家估算目前数据质量问题平均给每个企业增加的成本是企业收入的10%～20%。

目前，并没有统一的数据质量的定义形式。有关文献从六个维度阐述了数据质量的定义标准，包括：精确性（accuracy）、完整性（completeness）、时效性（timeliness）、一致性（consistency）、实体同一性（entityidentity）及相关性（relevancy）。其中，实体同一性指的是数据同应用需求的契合程度，描述同一个现实世界事物的数据冗余程度。实体识别在数据质量管理中有重要作用，是数据质量管理的主流研究方向之一。本文主要从针对各种数据模型总结数据质量中实体识别的算法的相关工作，并就其中的相关算法展开论述。

2.实体识别问题

大数据中的实体识别是指在给定的大数据集中准确发现属于同一实体的不同记录并将其聚类，使得每个实体簇在现实世界中表示同一对象的过程。实体识别是提高数据实体同一性方面质量的关键步骤。从形式化角度定义实体统一性：给定一个数据实体的集合D和一个物理实体集合O，求解一个集合D的划分P（其中P是由一系列D的不相交子集合构成，且P中所有集合并的结果与D相同）及P与O之间的一一对应关系。在实际应用中，数据实体D很容易获得，而物理实体集合O很难获得。因此在数据量大的情况下评价给定实体解析算法的优劣非常困难。也就是说，只要求将表示同一物理实体的数据实体放入一个集合，而不要求建立P与O之间的关系，该问题则称为实体识别问题。因此，根据实际具体的需求，借助不同的方法学，针对适合的问题定义，给出系统的解决方案。

在不同的应用领域，有不同的方法描述实体识别的过程。在单数据源中，内部实体使用唯一标识符或特征属性精确匹配来区别。在分布式系统中，由于不同的设计目的和角度，现实世界中的同一个实体也不可能有相同的标识符或者是相同的特征属性，因此，必须采样合适的方法实现实体识别。

3.实体识别过程

实体识别包括预处理阶段、特征向量的选取、比较函数的选取、搜索空间的优化、决策模型的选取和结果评估六个阶段。

预处理阶段是实体识别过程的关键阶段，在该阶段中要实现数据的标准化处理包括空格处理、字符大小写转换、复杂数据结构的解析和格式转换、上下文异构的消除等。隐马尔科夫模型是在该过程中对数据进行标准化处理的常用方法。

特征向量是指能够识别实体的属性的集合。特征向量的选取方法包括领域专家手工指定和机器学习方法。决策模型是在搜索空间中进行特征向量比较中判断实体是否匹配的决策模型的选取。一种是概率模型如Fellegiandsunter模型，另一种是基于经验的模型，根据领域专家的经验设置门限值。

评估结果有匹配、不匹配和可能匹配。不能确定的匹配结果需要人工进行评审，对评审过程中发现的问题进行调整或者改进决策模型，以期获得更高精度的实体识别效果。

4.实体识别相关研究

早期的实体识别算法主要是利用记录之间的相似性进行比较，运用规则的方法和阈值确定两条记录是否为同一个实体。在机器学习方法中动态生成相似性函数获取一个分类器，有效结合多个属性的相似性并且较准确地判定每对记录是否能被匹配为同一实体。基于规则的方法是根据规则确定不同记录是否描述同一实体。有学者提出了一个基于Map-Reduce框架的大数据实体识别算法，该算法首先通过属性值计算记录间的相似程度，而后基于图聚类的方法实现实体识别。

复杂数据是指在现实应用中产生的如XML数据、图数据和网络数据等。同一实体具有不同的复杂的数据描述方式，为了有效对这些数据实施质量管理，必须对复杂数据进行快速有效的实体识别。复杂数据上的实体识别可以分为成对识别和成组识别。根据识别对象的不同，复杂数据的实体识别分为XML数据实体识别、图结构数据实体识别和复杂网络中节点的实体识别。

5.大数据下的实体识别算法展望

单数据源的实体识别算法已经趋于成熟，但在大数据环境下的实体识别技术还是比较少。同时，针对大数据环境下的复杂结构数据的研究刚刚起步，海量复杂数据上的实体识别技术，特别是图数据上的实体识别技术的研究还处于初级阶段，大规模图集合上的数据实体识别的工作尚未开展。

需要支持更新复杂数据上的实体识别技术，不断更新互联网、社会网信息要求设计更新纷繁复杂数据上的增量实体识别技术，为更新的数据确定其所描述的实体。

6.结语

多类型的复杂数据要求设计实体识别技术。对互联网信息、进行有效的查询、集成和分析需要多类型复杂数据的实体识别技术。

参考文献：

[1]王宏志，樊文飞.复杂数据上的实体识别技术研究[J].计算机学报，2011，34（10）：1843-1852.

[2]霍然，王宏志，等.基于Map-Reduce的大数据实体识别算法[J].计算机研究与发展2013，11：170-179.

[3]刘显敏，李建中.实体识别问题的相关研究[J].智能计算机与应用，2013，2（3）：2-4.

[4]李明达，王宏志，张佳程，等.PEIF：基于并行机群的大数据实体识别算法[J].2013，11：211-220.

[5]张建中，方正，等.对基于SNM数据清洗算法的优化[J].华南大学学报：自然科学版，2010，41（6）：2240-2245.

基金项目：山东省科技计划（J15ln78），院级课题：2015LG001。