数据仓库下基于学习的并行实体解析算法研究
刘叶+吴晟+吴兴蛟+周海河+李英娜+张晶
摘 要：為了改善传统实体解析算法在单机环境下采用人为方式设定属性权值及阈值难以对海量数据进行快速有效处理的缺点，基于Hadoop框架使用MapReduce计算模型，在多节点分布式环境下，通过不断调整网络学习属性之间的内在关系以及属性权值、阈值等参数后，再将模型放在Hive数据仓库中的真实数据集上进行有效性验证。分别使用5 000及9 000条数据进行实验，实验结果表明，基于学习的并行实体解析算法准确率、召回率和F1值较高。因此，基于学习的并行实体解析算法对于海量数据不仅能进行快速有效的处理，而且能有效降低人工经验中存在的误差，同时也能提高识别结果的准确度，提升识别效率。
关键词：数据仓库；数据质量；实体解析；自主学习；并行计算
DOIDOI：10.11907/rjdk.172274
中图分类号：TP312
文献标识码：A 文章编号：1672-7800（2018）002-0019-04
0 引言
目前实体解析的研究工作主要包括概率、规则、聚类、学习以及集体等多种方法[1-4]。基于概率的方法是最早应用于实体解析的技术，然而该模型需要在先验概率情况下，对条件概率分布进行独立性假设，因此很难在实际应用中进行实践。基于阈值的实体解析是传统的实体匹配方法，也是目前应用最广泛的实体匹配技术。然而由于元组相似度和属性相似度之间是一种非线性映射关系，所以这种方法往往不能取得较好的识别效果。近年来，基于统计学和机器学习的实体解析匹配技术被提出并实现，如何获取训练数据集以及如何对数据进行处理是整个算法性能的关键。本文为了提高实体解析的效率及准确率，降低识别处理时间，同时实现高效地解析数据仓库中的海量数据实体，提出了基于学习的并行实体解析算法。
1 算法理论
1.1 实体解析概念
首先给出实体解析在本文的部分基本模型概念[5]：
实体：对应现实存在的数据对象。
元组：对实体的描述。
实体对：描述实体的两个元组的组合。
属性：对实体某一特征或性质的描述。
关键属性：描述在同一实体中，具有相同或相似属性特征的不同元组。
1.2 基于学习的实体解析算法设计
基于学习的实体解析算法设计如图1所示。
对实体解析算法的研究主要抽象为实体分块、元组对比较和实体匹配3个方面[6]。算法步骤如下：
Step1-Step4（实体分块）：对实体进行分块。通过一定规则，把指代不同实体的元组对划分到不同集合中，降低元组对比较的复杂度。
Step5-Step9（元组对比较）：对元组对进行比较。通过实体分块后形成相似元组对集合，计算元组词特征相似度，提取元组对的特征向量。通过设定的相似度比较函数，计算元组之间的相似程度，为进一步识别不同元组是否代表相同实体提供依据。
Step10（实体匹配）：对实体进行匹配。为识别它们是否代表同一实体，需要对数据集中相似的元组对进行匹配。
1.3 基于Hadoop的并行实体解析算法设计
将算法运用于并行环境下，基于Hadoop框架实现基于学习的实体解析模型的并行处理[7-8]，算法具体实现步骤如下：
Step1：并行环境下实体分块。
Map（）：
CV=[]
CV=random（CS）
While CS is not null
DV=random（CS）
Canopy（set）={（CV，DV）：
DV in CS and Sim（CV，DV）>=T1}
Merge（CV，DV）
Canopy（set）={（CV，DV）：
DV in CS and S （CV，DV）>=T2}
CS=CS-{DV}
return CV
Reduce（）：
While CV is not null
Sim（CV，CV）>=T1
Merge（CV，CV）
Step2：并行环境下实体相似度计算。
Map（）：
Input：
Output：
Output：
Reduce（）：
Input：
Input：
Output：
Output：
Step3：并行环境下实体匹配。
Map（）：
random（L_i）
for i in range（nmax）
for j in range（M）
selectPher （qmax）
updatePher （q）
calcTransprob（）
Output（key，value）
Reduce（）：
for T in range（tmax）
for Et>emin
for each data in ω[i]
getBackweight（self）
updateWeight（b_w，l_r，t）
calcWeight（key=ω[i]，value=∑ni=1Δω/n）
Output（key=ω，value=∑ni=1Δω/n）
2 实验及结果分析
本文利用某烟草集团数据中心的数据源，在基于学习的并行实体解析算法理论指导下进行了仿真验证，如图2所示。
2.1 实验数据来源
实验数据源包括集团不同下属分厂以及部门提供的62 122条供应商数据，利用本文所述模型及算法对其进行实验评价。
不同来源的数据按照一定规则，通过ETL抽取到数据仓库中，使大部分的数据质量问题得到解决，但是表示同一实体的数据冗余问题还有待进一步解决，如图3所示。
图中具体数据含义如表1所示。
集成后有质量问题的数据如表2所示。
2.2 评价标准
为了评价模型，本文针对计算方法、处理框架、实体解析模型提出以下评价标准：
（1）性能指标。本实验采用了信息处理和统计分类领域中常用的准确率、召回率和F1值指标体系对实验结果进行性能评价[9-11]。一般令真实结果为S，实验结果为R。
准确率计算为所有“正确被检索的”占所有“实际被检索到的”数据的比例，其计算公式可表示为：
召回率计算的是所有“正确被检索的”占所有“应该检索到的”数据的比例，其计算公式可表示为：
F1值表示准确率和召回率的调和平均值，其计算公式可表示为：
（2）并行处理效率。加速比是指在单处理器系统和并行处理器系统中，同一任务运行消耗的时间比率。
以SP表示加速比，其计算公式可表示为：
其中，T1为单机环境下处理时间，TP为P个并行节点下的处理时间。
2.3 实验环境
本文基于Hadoop框架搭建分布式计算环境。其部分软硬件环境如表3所示。
2.4 实验结果分析
2.4.1 算法精确度分析
实验数据使用供应商名称、供应商简称、供应商类型、城市、通讯地址等属性，在数据量分别为5 000与9 000条的环境下进行对比。其中冗余元组对有1 658条。
利用所述算法对数据集进行验证[12]。首先以属性4作为关键属性，结合Python分词库算法，分别对数据集和属性值进行初步的分块处理和分词处理，同时利用TF-IDF算法，获取属性中每个单词的权重信息。计算元组对的余弦相似度和属性值的位置编码相似度，并使用神经网络进行训练。其中设置神经网络期望输出值：当输出为1时代表元组对匹配，输出为0时代表元组对不匹配。
设置目标函数的误差为0.01，学习率为0.2，设置输入节点为5个，输出节点为2个，隐含层单元为6层，最大迭代次数为500，训练样本占2/3，其余为测试样本，蚂蚁数目定义为20。随机赋予初始权值阈值进行训练。
计算后部分元组对属性相似度值如表4所示。
根据计算，发现在进行阈值规则识别、人工分配各属性权值时，属性1、2及5所占权重较大，属性4对识别结果几乎无影响。基于此分别采用两种算法进行识别计算。
两种算法的3种评价指标具体实验结果如表5所示。
由此可见，基于学习算法的3种评价指标的平均值都明显优于基于阈值规则算法。
两种算法的F1值具体实验结果如表6所示。
由表6可以看出，自主学习的F1值比阈值规则的F1值高，而且随着元组对象数据量的增大，自主学习的F1值下降平缓，阈值规则的F1值则下降明显。由此可见，基于学习算法优于基于阈值规则算法。
2.4.2 并行处理效率分析
首先对基于单机环境和并行环境下处理不同规模的数据集进行试验，采用运行时间作为评价标准进行分析。
选择一个节点作为单机环境，分析5个不同数量的实体对象运行时间，再选择两个节点作为并行环境，采用1个主节点和4个计算节点对相似元组对进行实体解析实验。运行时间分别如图6所示。
两种环境下具体运行时间如表7所示。
由此可见，在单机环境下，随着数据集合中数据量的增大，识别相似元组对所花费的时间也会明显增加，同时识别每一个相似元组对花费的平均时间明显减少。在并行环境下，当数据量较小时，单机环境和并行环境下的运行时间差别相对较小，计算效率没有明显提高；随着数据量不断增大，单机环境下的运行时间明显增加。
针对基于单节点和多节点模式下处理相同规模的数据集进行实验，采用加速比衡量实体解析结果的性能和效果。实验结果如图7所示。
纵坐标分别为计算时间和加速比，横坐标为节点个数，元组对象为50 000个数据。
不同节点个数下计算时间和加速比的具体实验结果如表8所示。
因此可见，计算时间随着节点数目的增加而不断减少，当节点数目为1时，即为单机环境下的运行时间。当节点数目增大时，计算时间减少相对明显；但是当节点数成倍地参与计算时，其计算时间并没有减小到一半，这可能是因为数据不均匀分布以及节点交互需要消耗一定的处理时间。因此，可以在多节点模型下充分利用分布式处理的扩展性优势，调动多个节点对任务的并行计算，提高计算的性能和效率。
3 结语
基于学习的实体解析算法在实体解析中降低了人工经验存在的误差，减少了识别结果对人工经验的依赖，具有较高的准确性；基于Hadoop的并行实体解析算法，能够对海量数据进行快速有效的处理；基于学习的并行实体解析算法以提高识别精度、減小计算时间为目标，克服了传统实体解析算法中对于人工经验的依赖，同时改善了传统算法对数据仓库中海量数据不能快速有效地进行处理等问题，使在对海量数据进行快速有效处理的同时，还能取得较高的准确性和良好的时间效率。
参考文献：
[1] NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vital records[J]. Science，1959，130（3381）：954-959.
[2] FELLEGI I P， SUNTER A B. A Theory for record linkage[J]. Journal of the American Statistical Association，1969，64（328）：1183-1210.
[3] WANG Y R， MADNICK S E. The inter-database instance identification problem in integrating autonomous systems[C].International Conference on Data Engineering，1989.Proceedings.IEEE，1989：46-55.
[4] BAMFORD R， BUTLER D， KLOTS B， et al. Architecture of oracle parallel server[C].International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1998：669-670.
[5] 王超文.面向结构化数据的实体解析方法[D].哈尔滨：哈尔滨工程大学，2014.
[6] 何峰权，李建中.基于属性模式的实体识别框架[J].智能计算机与应用，2014，4（1）：65-68.
[7] 湛文红.数据仓库与数据挖掘实例分析[J].软件导刊，2013（2）：99-102.
[8] 刘栋，王黎峰，张怀锋.基于大数据的统计分析模型设计[J].软件导刊，2016（7）：28-30.
[9] 燕彩蓉，张洋舜，徐光伟.支持隐私保护的众包实体解析[J].计算机科学与探索，2014，8（7）：802-811.
[10] 黄敏.大数据下基于块依赖的实体解析方法[D].北京：北京交通大学，2015.
[11] 甄灵敏，杨晓春，王斌，等.基于属性权重的实体解析技术[J].计算机研究与发展，2013，50（S1）：281-289.
[12] 黎玲利.實体识别关键技术的研究[D].哈尔滨：哈尔滨工业大学，2015.
摘 要：為了改善传统实体解析算法在单机环境下采用人为方式设定属性权值及阈值难以对海量数据进行快速有效处理的缺点，基于Hadoop框架使用MapReduce计算模型，在多节点分布式环境下，通过不断调整网络学习属性之间的内在关系以及属性权值、阈值等参数后，再将模型放在Hive数据仓库中的真实数据集上进行有效性验证。分别使用5 000及9 000条数据进行实验，实验结果表明，基于学习的并行实体解析算法准确率、召回率和F1值较高。因此，基于学习的并行实体解析算法对于海量数据不仅能进行快速有效的处理，而且能有效降低人工经验中存在的误差，同时也能提高识别结果的准确度，提升识别效率。
关键词：数据仓库；数据质量；实体解析；自主学习；并行计算
DOIDOI：10.11907/rjdk.172274
中图分类号：TP312
文献标识码：A 文章编号：1672-7800（2018）002-0019-04
0 引言
目前实体解析的研究工作主要包括概率、规则、聚类、学习以及集体等多种方法[1-4]。基于概率的方法是最早应用于实体解析的技术，然而该模型需要在先验概率情况下，对条件概率分布进行独立性假设，因此很难在实际应用中进行实践。基于阈值的实体解析是传统的实体匹配方法，也是目前应用最广泛的实体匹配技术。然而由于元组相似度和属性相似度之间是一种非线性映射关系，所以这种方法往往不能取得较好的识别效果。近年来，基于统计学和机器学习的实体解析匹配技术被提出并实现，如何获取训练数据集以及如何对数据进行处理是整个算法性能的关键。本文为了提高实体解析的效率及准确率，降低识别处理时间，同时实现高效地解析数据仓库中的海量数据实体，提出了基于学习的并行实体解析算法。
1 算法理论
1.1 实体解析概念
首先给出实体解析在本文的部分基本模型概念[5]：
实体：对应现实存在的数据对象。
元组：对实体的描述。
实体对：描述实体的两个元组的组合。
属性：对实体某一特征或性质的描述。
关键属性：描述在同一实体中，具有相同或相似属性特征的不同元组。
1.2 基于学习的实体解析算法设计
基于学习的实体解析算法设计如图1所示。
对实体解析算法的研究主要抽象为实体分块、元组对比较和实体匹配3个方面[6]。算法步骤如下：
Step1-Step4（实体分块）：对实体进行分块。通过一定规则，把指代不同实体的元组对划分到不同集合中，降低元组对比较的复杂度。
Step5-Step9（元组对比较）：对元组对进行比较。通过实体分块后形成相似元组对集合，计算元组词特征相似度，提取元组对的特征向量。通过设定的相似度比较函数，计算元组之间的相似程度，为进一步识别不同元组是否代表相同实体提供依据。
Step10（实体匹配）：对实体进行匹配。为识别它们是否代表同一实体，需要对数据集中相似的元组对进行匹配。
1.3 基于Hadoop的并行实体解析算法设计
将算法运用于并行环境下，基于Hadoop框架实现基于学习的实体解析模型的并行处理[7-8]，算法具体实现步骤如下：
Step1：并行环境下实体分块。
Map（）：
CV=[]
CV=random（CS）
While CS is not null
DV=random（CS）
Canopy（set）={（CV，DV）：
DV in CS and Sim（CV，DV）>=T1}
Merge（CV，DV）
Canopy（set）={（CV，DV）：
DV in CS and S （CV，DV）>=T2}
CS=CS-{DV}
return CV
Reduce（）：
While CV is not null
Sim（CV，CV）>=T1
Merge（CV，CV）
Step2：并行环境下实体相似度计算。
Map（）：
Input：
Output：
Output：
Reduce（）：
Input：
Input：
Output：
Output：
Step3：并行环境下实体匹配。
Map（）：
random（L_i）
for i in range（nmax）
for j in range（M）
selectPher （qmax）
updatePher （q）
calcTransprob（）
Output（key，value）
Reduce（）：
for T in range（tmax）
for Et>emin
for each data in ω[i]
getBackweight（self）
updateWeight（b_w，l_r，t）
calcWeight（key=ω[i]，value=∑ni=1Δω/n）
Output（key=ω，value=∑ni=1Δω/n）
2 实验及结果分析
本文利用某烟草集团数据中心的数据源，在基于学习的并行实体解析算法理论指导下进行了仿真验证，如图2所示。
2.1 实验数据来源
实验数据源包括集团不同下属分厂以及部门提供的62 122条供应商数据，利用本文所述模型及算法对其进行实验评价。
不同来源的数据按照一定规则，通过ETL抽取到数据仓库中，使大部分的数据质量问题得到解决，但是表示同一实体的数据冗余问题还有待进一步解决，如图3所示。
图中具体数据含义如表1所示。
集成后有质量问题的数据如表2所示。
2.2 评价标准
为了评价模型，本文针对计算方法、处理框架、实体解析模型提出以下评价标准：
（1）性能指标。本实验采用了信息处理和统计分类领域中常用的准确率、召回率和F1值指标体系对实验结果进行性能评价[9-11]。一般令真实结果为S，实验结果为R。
准确率计算为所有“正确被检索的”占所有“实际被检索到的”数据的比例，其计算公式可表示为：
召回率计算的是所有“正确被检索的”占所有“应该检索到的”数据的比例，其计算公式可表示为：
F1值表示准确率和召回率的调和平均值，其计算公式可表示为：
（2）并行处理效率。加速比是指在单处理器系统和并行处理器系统中，同一任务运行消耗的时间比率。
以SP表示加速比，其计算公式可表示为：
其中，T1为单机环境下处理时间，TP为P个并行节点下的处理时间。
2.3 实验环境
本文基于Hadoop框架搭建分布式计算环境。其部分软硬件环境如表3所示。
2.4 实验结果分析
2.4.1 算法精确度分析
实验数据使用供应商名称、供应商简称、供应商类型、城市、通讯地址等属性，在数据量分别为5 000与9 000条的环境下进行对比。其中冗余元组对有1 658条。
利用所述算法对数据集进行验证[12]。首先以属性4作为关键属性，结合Python分词库算法，分别对数据集和属性值进行初步的分块处理和分词处理，同时利用TF-IDF算法，获取属性中每个单词的权重信息。计算元组对的余弦相似度和属性值的位置编码相似度，并使用神经网络进行训练。其中设置神经网络期望输出值：当输出为1时代表元组对匹配，输出为0时代表元组对不匹配。
设置目标函数的误差为0.01，学习率为0.2，设置输入节点为5个，输出节点为2个，隐含层单元为6层，最大迭代次数为500，训练样本占2/3，其余为测试样本，蚂蚁数目定义为20。随机赋予初始权值阈值进行训练。
计算后部分元组对属性相似度值如表4所示。
根据计算，发现在进行阈值规则识别、人工分配各属性权值时，属性1、2及5所占权重较大，属性4对识别结果几乎无影响。基于此分别采用两种算法进行识别计算。
两种算法的3种评价指标具体实验结果如表5所示。
由此可见，基于学习算法的3种评价指标的平均值都明显优于基于阈值规则算法。
两种算法的F1值具体实验结果如表6所示。
由表6可以看出，自主学习的F1值比阈值规则的F1值高，而且随着元组对象数据量的增大，自主学习的F1值下降平缓，阈值规则的F1值则下降明显。由此可见，基于学习算法优于基于阈值规则算法。
2.4.2 并行处理效率分析
首先对基于单机环境和并行环境下处理不同规模的数据集进行试验，采用运行时间作为评价标准进行分析。
选择一个节点作为单机环境，分析5个不同数量的实体对象运行时间，再选择两个节点作为并行环境，采用1个主节点和4个计算节点对相似元组对进行实体解析实验。运行时间分别如图6所示。
两种环境下具体运行时间如表7所示。
由此可见，在单机环境下，随着数据集合中数据量的增大，识别相似元组对所花费的时间也会明显增加，同时识别每一个相似元组对花费的平均时间明显减少。在并行环境下，当数据量较小时，单机环境和并行环境下的运行时间差别相对较小，计算效率没有明显提高；随着数据量不断增大，单机环境下的运行时间明显增加。
针对基于单节点和多节点模式下处理相同规模的数据集进行实验，采用加速比衡量实体解析结果的性能和效果。实验结果如图7所示。
纵坐标分别为计算时间和加速比，横坐标为节点个数，元组对象为50 000个数据。
不同节点个数下计算时间和加速比的具体实验结果如表8所示。
因此可见，计算时间随着节点数目的增加而不断减少，当节点数目为1时，即为单机环境下的运行时间。当节点数目增大时，计算时间减少相对明显；但是当节点数成倍地参与计算时，其计算时间并没有减小到一半，这可能是因为数据不均匀分布以及节点交互需要消耗一定的处理时间。因此，可以在多节点模型下充分利用分布式处理的扩展性优势，调动多个节点对任务的并行计算，提高计算的性能和效率。
3 结语
基于学习的实体解析算法在实体解析中降低了人工经验存在的误差，减少了识别结果对人工经验的依赖，具有较高的准确性；基于Hadoop的并行实体解析算法，能够对海量数据进行快速有效的处理；基于学习的并行实体解析算法以提高识别精度、減小计算时间为目标，克服了传统实体解析算法中对于人工经验的依赖，同时改善了传统算法对数据仓库中海量数据不能快速有效地进行处理等问题，使在对海量数据进行快速有效处理的同时，还能取得较高的准确性和良好的时间效率。
参考文献：
[1] NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vital records[J]. Science，1959，130（3381）：954-959.
[2] FELLEGI I P， SUNTER A B. A Theory for record linkage[J]. Journal of the American Statistical Association，1969，64（328）：1183-1210.
[3] WANG Y R， MADNICK S E. The inter-database instance identification problem in integrating autonomous systems[C].International Conference on Data Engineering，1989.Proceedings.IEEE，1989：46-55.
[4] BAMFORD R， BUTLER D， KLOTS B， et al. Architecture of oracle parallel server[C].International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc，1998：669-670.
[5] 王超文.面向结构化数据的实体解析方法[D].哈尔滨：哈尔滨工程大学，2014.
[6] 何峰权，李建中.基于属性模式的实体识别框架[J].智能计算机与应用，2014，4（1）：65-68.
[7] 湛文红.数据仓库与数据挖掘实例分析[J].软件导刊，2013（2）：99-102.
[8] 刘栋，王黎峰，张怀锋.基于大数据的统计分析模型设计[J].软件导刊，2016（7）：28-30.
[9] 燕彩蓉，张洋舜，徐光伟.支持隐私保护的众包实体解析[J].计算机科学与探索，2014，8（7）：802-811.
[10] 黄敏.大数据下基于块依赖的实体解析方法[D].北京：北京交通大学，2015.
[11] 甄灵敏，杨晓春，王斌，等.基于属性权重的实体解析技术[J].计算机研究与发展，2013，50（S1）：281-289.
[12] 黎玲利.實体识别关键技术的研究[D].哈尔滨：哈尔滨工业大学，2015.
