蚁群BP神经网络实体解析匹配研究

刘叶　吴晟　吴兴蛟

摘要：

为了改进BP神经网络收敛速度慢、不能得到全局最优解的缺点，选择具有全局优化、支持并行且具有自适应特性的蚁群算法，优化神经网络初始权重和阈值。将算法运用于实体解析元组对的匹配加以验证，结果表明：在相同最大迭代次數下，BP神经网络迭代490次可寻找到最优解，其均方误差为0.078，ACOBP神经网络同样迭代487次可寻找到最优解，均方误差为0.013，相对来说均方误差更小，训练效果更接近于目标值，表明蚁群优化的神经网络算法可以改善传统BP神经网络收敛速度慢、学习效率低和易陷入局部最优等缺点。

关键词：数据仓库；数据质量；实体解析；BP神经网络；蚁群算法

DOIDOI：10.11907/rjdk.172415

中图分类号：TP301

文献标识码：A文章编号文章编号：16727800（2018）003003704

英文摘要Abstract：In order to improve BP neutral network for its slow convergence rate and incapability for getting global optimal solution. Thus we can choose ant colony algorithm with global optimal solution， parallelism support and adaptive feature to optimize the initial weight and threshold of neutral network and utilize the algorithm in tuple matching of entity analysis.The verify result shows under the same maximum number of iterations， BP neural network has found the optimal result after iterating for 490 times with mean square error 0.078， while ACOBP neural network got the result 487 times with mean square error 0.013， relatively speaking， closer to the target value. Thus we can draw the conclusion that ant colony optimization neural network algorithm can improve the disadvantages of traditional BP neural network， i.e. slower convergence rate， lower learning efficiency and easier local optimum.

英文关键词Key Words：data warehouse； data quality； entity analysis； BP neutral network； ant colony algorithm

0引言

人工神经网络是人工智能中一种极为重要的算法，通过调节组成各节点的互联反馈关系实现复杂信息并行处理。这是一种依赖于系统复杂程度的网络拓扑理论分布式处理模型，其中尤以BP神经网络研究应用最为广泛。该模型在理论以及实际运用方面都比较成熟。但是，BP神经网络存在学习效率较低、收敛速度慢、容易陷入局部最优解的缺陷。

为解决这一问题，尝试使用一种能够进行启发式的全局优化进化算法。考虑到算法应该具有全局优化、并行以及自适应特性，因此采用能寻找优化路径大概率型算法——蚁群算法，该算法具有正反馈特点[14]。

基于以上考虑，本文使用蚁群算法优化BP神经网络，并提出一种蚁群优化神经网络（ACOBP）算法。将算法运用于实体解析的元组对匹配进行验证。蚁群算法可以找到一组解空间中的最优解，找到之后使用神经网络进行优化。该算法不仅解决了BP容易陷入局部解的问题，同时算法收敛速度也得到了提升。

1蚁群改进BP神经网络基本原理

1.1BP神经网络算法原理

BP是一种前馈多层网络学习算法[5]，其结构如图1所示。

输入、隐含以及输出3个神经元层是BP神经网络特有的标志[6]。其中隐单元作为隐含层中的神经元状态，影响着输入以及输出层关系，不与外界联系。但隐单元在一定程度上决定着整个多层神经网络的性能，通过改变其系数就可以决定多层神经网络的作用。

对于一个m层的神经网络，样本X被添加到输入层。多层神经网络表述如下：

Xki=f（Uki）（1）

Uki=∑WijXk-1j（2）

U＼+k＼-i：第k层的i神经元的输入总和；X＼+k＼-i：输出；Wij：第k—1层的第j个神经元到第k层的第i个神经元的权系数；f：每个神经元的加权函数。

BP神经网络有两个重要特征[78]：

（1）正向信息传播：输入样本通过隐含层逐层传播到输出层。每一层的传播总是由上一层神经元状态影响下一层状态，同时在每一层输出过程中总是将数据与上层得到的数据进行比较，如果和预期不符就进入误差传播。

（2）逆向误差传播：按照正向传播的反向路径进行回传，并且在回传过程中修改隐含层权重系数，用来矫正模型。

1.2蚁群算法基本原理

蚁群算法原理：在蚂蚁搜索食物过程中会留下一种叫做信息素的东西，而且信息素的产生是随着蚂蚁寻找食物路径的加长而减弱的，也就是说，信息素随着离蚂蚁巢穴越远越少。蚂蚁寻找食物就是基于信息素浓度选择的，但信息素具有一定挥发性[911]。大致可以归纳为以下方式描述蚂蚁的寻找原则：①如果蚂蚁没有收到信息素信息，蚂蚁随机选择找食路径；②如果周围有多个信息素信息，蚂蚁根据信息素浓度选择路径；③蚂蚁会在找食过程中使用不同信息进行交换，例如从家出去留下信息A，找到食物后留下信息B；④随着时间的推进，老的信息素挥发。

1.3蚁群算法与BP神经网络相结合

BP神经网络有一个缺点：由于其阈值与权值是随机生成的，这就使得初始值的选择很大程度上决定了算法的收敛程度。如果初始值选择不好，就会导致得不到全局最优解。產生的原因是由于出现修改网络权值或阈值的振荡，使算法不收敛或者收敛缓慢，这使得网络性能下降，学习速度慢。BP神经网络采用梯度下降算法找到解，也是其易陷入局部最优解的原因。为了解决这一问题，就不得不找到一种具有全局最优解的搜索优化算法。使用鲁棒性较好的蚁群算法对BP神经网络的阈值以及权值进行训练，就可克服BP神经网络的缺点。

2蚁群与改进BP神经网络算法设计

为了获得理想的学习效果和更有效的收敛速度，神经网络的初始权重应该尽可能地靠近全局最小值。然而，通常该值是随机选择的，且在神经网络的学习训练中会反向传播误差信息，不断地动态调整，导致难以保持合理状态。本文利用神经网络具有数据融合和易于与其它算法相结合的特点，利用蚁群算法的全局优化功能，优化神经网络的初始权重和阈值。

全局信息素更新机制是优化过程中必不可少的机制[1213]，具体思想如下：

首先给出神经网络的权重和初始阈值。利用蚁群算法查找和构建阈值的最优值，从而使网络权值由于误差反向传播而易陷入局部最优的问题得以解决；然后以蚁群算法构建的较优解输入神经网络作进一步寻优训练，寻找网络权值阈值最优解。上述方式不仅可以提高神经网络收敛的速度，提高学习效率，而且可以提高学习精度。引入网络梯度信息也避免了蚁群算法在短时间内难以找到阈值最优解的问题。算法流程如下：

（1）训练样本。使用期望输出对蚁群参数进行初始化。神经网络参数pi（1≤i≤n）为N个非0的随机数值，并且构建集合Ipi。集合Ipi中第j个元素Pj（Ipi）的信息量可以表示为τj（Ipi）。迭代次数为Nc，时间设定为t，约定初始时刻为0。最大迭代次数为Ncmax，集合中所有元素的信息素浓度相等，且τj（Ipi）=C，Δτj（Ipi）表示元素j包含的信息素浓度的增量，Δτj（Ipi）=0设为初始值，Δτj（Ipi）=0表示在运动过程中蚂蚁k残留在元素j上的信息素浓度。随机放置所有蚂蚁在神经网络参数上。

（2）启动所有蚂蚁。选择蚂蚁开始运动，并从集合Ipi中随机选择路径。路径选择使用状态转移概率以及信息元素浓度作为参考，同时将选择的元素集合作为神经网络权重。蚂蚁k在集合Ipi中的状态转移概率计算如下：

Pj（τkj（IPi））=[τj（Ipi）]α×[ηj（Ipi）]β∑s∈allowedk[τs（Ipi）]α×[ηs（Ipi）]β，if j∈allowedk

0，else

（3）

设置ηj（Ipi）=1ek为启发函数，ek表示网络实际输出与期望输出的误差，主要含义为当第k只蚂蚁所选择的权值、阈值作为神经网络的权值、阈值时，产生的值间偏差记为ek=|out实际-out期望|。误差ek与包含的信息浓度成正比。

（3）更新信息素。伴随着蚂蚁运动的结束，迭代次数也会完成，即t←t+m；Nc←Nc+1。将蚂蚁运行集合中选择的权值以及阈值放入神经网络，作为最优解进行实际输出以及误差计算，对路径上信息素浓度进行更新：

τj（Ipi）（t+m）=（1-ρ）τj（Ipi）（t）+Δτj（Ipi）（4）

Δτj（Ipi）=∑hk=1Δτkj（Ipi）（5）

Δτkj（Ipi）=Qek，k→Pj（Ipi）

0，else（6）

ρ表示信息素挥发系数，Q表示信息素浓度。

（4）当Nc=Ncmax时，说明所有蚂蚁收敛到了相同路径，也就是说迭代到了最大次数，终止计算，并保存求解结果。否则重复步骤（2）、步骤（3）。

（5）利用学习获得的神经网络对测试数据进行识别计算。

蚁群神经网络算法训练流程见图2。

蚂蚁的数目在蚁群神经网络中通过对N和N2的计算得到，也就是计算初始连接权值以及阈值总数。

3算法验证

通常，数据仓库中一个元组包含多个属性，在计算元组对的相似性时，需要比较所有属性的相似度值。因为不同属性对所属元组有不同程度的影响，属性相似度和元组相似度是一个非线性映射关系[14]，因此，需要用一个非线性分类器识别元组对是否指代同一个实体。通过网络学习属性间的内在关系调整阈值、权值等参数。利用神经网络能以任意情况以及任意精度逼近非线函数的特性，采用优化后的算法判断实体匹配是否完成。算法的提出在一定程度上弥补了传统实体匹配方法中根据属性相似度的加权求和缺点，改进了用人工阈值的比较来判断元组对是否属于同一实体的不足。

本文运用神经网络对非线性函数的特征进行准确近似，通过网络研究动态实现权重、阈值等参数属性之间的内在关系，调整实体，以判断实体是否匹配。由于缺乏神经网络训练过程，故采用蚁群算法进行优化。

比较传统BP神经网络算法和蚁群优化神经网络算法的权值训练误差。设置训练误差精度为0.01，学习率为0.2，最大迭代次数为500。利用某烟草集团数据中心供应商数据集，计算得到属性相似度特征向量，以Matlab编程对两种算法进行实验验证对比，结果如图3所示。

在相同的最大迭代次数下，BP神经网络在迭代490次寻找到最优解，其均方误差为0.078，ACOBP神经网络同样在487次迭代寻找到最优解，均方误差为0.013，见表1。相对来说，均方误差更小，训练效果更接近于目标值。由于传统的BP算法在优化过程中陷入局部最优解，使得收敛效果不及优化后的算法。因此，ACOBP算法在训练效果和收敛速度上都有着更好的性能和效率，能够达到较小的均方误差值，极大程度上节约了训练时间。

本实验采用准确率、召回率两个指标体系对实验结果进行性能评价[1517]。

本文针对传统BP神经网络和蚁群优化神经网络进行准确率、召回率对比实验，分6组数据集对两种算法进行比较，训练及测试相同属性的相似度值，实验结果如图4所示。当数据量较小时，两种识别模型的性能指标值差别不大，当数据为1 000个元组时，BP和ACOBP算法的准确度分别为0.94和0.95。随着数据量的增加，两种模型的准确率和召回率都有所降低。当数据为50 000个元组对象时，BP和ACOBP算法的准确度分别为0.76和0.84，但ACOBP算法的识别准确率高于传统BP神经网络，下降速度慢于传统BP神经网络，这主要是因为蚁群算法获得了更优的神经网络权值和阈值，实体解析的准确性相应得到了提高。

同样，随着数据规模的增加，两种算法的运行时间也不断增加，但蚁群优化神经网络的运行时间相对更短，如图5所示。对比结果表明，蚁群优化神经网络提高了实体解析的效率，较好地满足了海量数据的实体解析性能要求。

经过实验仿真，优化后的算法在训练效果及测试集上有着更好的性能，表明蚁群优化算法可以改善传统BP神经网络收敛速度慢、学习效率低和易陷入局部最优等缺点。

4结语

本文针对神经网络算法训练时间较长、收敛速度较慢以及易于陷入局部最优解的问题，使用蚁群算法进行弥补，结合蚁群算法的全局最优解搜索及具有较强鲁棒性优点，建立蚁群优化神经网络模型。详细阐述了基于蚁群算法，采用全局信息素的更新机制优化BP网络的连接权值和阈值方法。实验仿真表明，优化后的算法在训练效果及测试集上有着更好的性能，表明蚁群优化算法可以改善传统BP神经网络收敛速度慢、学习效率低和易陷入局部最优等不足。

参考文献参考文献：

[1]RANDALL M，LEWIS A.A parallel implementation of ant colony optimization[J].Journal of Parallel and Distributed Computing，2002，62（9）：14211432.

[2]BEMD B，GABRIEL E K，CHRISTINE S.Parallelization Strategies for the Ant System[M].Vienna，Austria：University of Vienna，1997.

[3]MANFRIN M，BIRATTARI M，STUTZLE T，et a1.Parallel ant colony optimization for the Traveling Salesman Problem[R].Universite Libre de BmxeUes，Belgium，Technical Report：TR/IRIDIAJ 2006007，2006.

[4]DORIGO M，MANIEZZO V，COLORNI A.The ant system：optimization by a colony of cooperating agents[J].IEEE Transcations on Systems，Man and Cybernetics，1996，26（1）：2941.

[5]徐紅艳，党晓婉，冯勇，等.基于BP神经网络的Deep Web实体识别方法[J].计算机应用，2013，33（3）：776779.

[6]沈花玉，王兆霞，高成耀，等.BP神经网络隐含层单元数的确定[J].天津理工大学学报，2008，24（5）：1315.

[7]马锐.人工神经网络原理[M].北京：机械工业出版社，2010.

[8]强保华，陈凌，余建桥，等.基于BP神经网络的属性匹配方法研究[J].计算机科学，2006，33（1）：249251.

[9]段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[10]王磊，曹菡，王长缨.蚁群算法的三种并行模型分析[J].计算机工程，2011，37（12）：170172.

[11]柏建普，吴强.蚁群混合遗传算法的研究及应用[J].电子科技，2011，24（4）：2023.

[12]黄美玲.蚁群优化算法的研究及其应用[D].南昌：南昌大学，2007：1213.

[13]白磊.蚁群算法的改进及其应用研究[D].合肥：安徽大学，2015：2224.

[14]韩柯，李德毅.元组统计相似性知识的提取与应用[J].计算机研究与发展，1997（1）：312316.

[15]JIN L， LI C， MEHROTRA S. Efficient record linkage in large data sets[C]. Eighth International Conference on Database Systems for Advanced Applications. IEEE， 2003：137146.

[16]KIRSTEN T， KOLB L， HARTUNG M， et al. Data partitioning for parallel entity matching[J]. Computer Science， 2010（1）：12541266.

[17]T F SMITH， M S WATERMAN. Identification of common molecular subsequences[J]. Journal of molecular biology， 1981，147（1）：195197.

责任编辑（责任编辑：杜能钢）