一种乱序数据流中基于误差反向传播的模板匹配方法

摘要

一种乱序数据流中基于误差反向传播的模板匹配算法，针对大数据中乱序数据流难以在短时间内获取有价值的信息的问题，提出了一个改进型匹配模型，对数据进行预处理；提出了动态自适应调整机制，重新定义了性能均方差函数、输出层节点误差项、隐层节点误差项、阈值、连接权值、学习指数。根据匹配模型未知的乱序数据流以及用户的不同需求，确定所需的匹配模板，并对数据流进行预处理，同时加入遗忘因子，动态调整匹配模板。设定好匹配模板之后，同时运用自适应调整机制修正阈值、连接权值和学习指数。仿真结果表明，算法在精度以及运行速度上有着明显的提升，并具有较好的稳定性。

说明书

技术领域

本发明是一种在乱序数据流中基于误差反向传播的模板匹配方法，属于大数据的模板匹配算法领域。

背景技术

大数据其所涉及的数据量规模巨大，无法通过目前主流软件工具在合理时间内获得乱序数据中用户所需的有价值信息。传统的数据处理模式将采集到的数据先存储起来，然后用户主动进行查询，得到最终答案，而对于乱序数据流这种方式并不合适。因此，为了对数据及时的进行存储和计算，模板匹配机制被广泛运用于乱序数据流中。但目前大部分模板匹配机制是根据事件发生的先后顺序进行匹配，这就使得来自不同数据源的事件由于网络质量不稳定等原因而导致事件不按照时间顺序到达处理节点，进而造成模板匹配的精确度不高，无法应用于实时性较高的场合，并给缓存单元带来极大的计算压力。

误差反向传播（Error Back Propagation，BP）算法是一种有效的学习匹配算法，能进行大规模并行信息处理，并用数据代表简单事件，进行匹配操作，能在短时间内获得较高的算法收敛效率。但传统BP算法的学习模板往往是固定不变的，在数据量增加的情况下，算法性能会变差，这样就使得算法的运行速度和稳定性之间产生很大的矛盾。

发明内容

技术问题：本发明针对上述问题，提出一种乱序数据流中基于误差反向传播的模板匹配方法，该方法对BP算法的隐层与输出层的连接权值进行了修正，同时利用梯度比值改进学习指数。将改进后的BP算法运用到模板匹配机制中，来加速匹配过程中的算法速度和精度，并提高算法的稳定性。

技术方案：本发明的一种乱序数据流中基于误差反向传播的模板匹配方法为：

基本思想：本发明针对大数据中乱序数据流难以在短时间内获取有价值的信息的问题，提出了一个改进型匹配模型，对数据进行预处理；提出了动态自适应调整机制，重新定义了性能均方差函数、输出层节点误差项、隐层节点误差项、阈值、连接权值、学习指数。根据匹配模型未知的乱序数据流以及用户的不同需求，确定所需的匹配模板，并对数据流进行预处理，同时加入遗忘因子，动态调整匹配模板。设定好匹配模板之后，同时运用自适应调整机制修正阈值、连接权值和学习指数。

模型定义:

定义1：模板匹配模型：BP网络的非线性映射特性适用于乱序数据流的非结构性映射，而且可以利用算法自学习功能，通过对样本的分析辨识出有价值的数值序列。在乱序数据流中，我们可利用数值来代替事件，以此给BP网络的参数修正和自适应匹配创造条件。而网络的模型是影响网络学习性能的主要因素之一，通常根据经验人工获取。对于匹配模型未知的乱序数据流序列，数据是随时间而不断变化的，使用静态匹配模板显然不能完全满足用户的不同时刻段的不同需求，因此将输入层样本输入设为(x₁,x₂x₃,…,x_k,1≤k≤n)，n为输入层节点个数，输出层样本输出为其中f(x_k)表示网络的输出函数。网络通过对样本学习训练，调整各神经元之间的连接权值来实现对模型参数的逼近，同时加入遗忘因子，使得网络在连接权值调整的同时也进行网络结构的学习，从而实现对模板的动态建模和参数辩识。在改进型模型中我们在网络输入层对输入样本作了预处理，对乱序数据流进行归一化操作，并用公式(1)事先计算好误差项。隐层误差计算采用的Sigmoid作用函数，在闭区间[0，1]上的S型函数（Sigmoid函数）表达式及其导数定义为公式(2)。其中λ决定Sigmoid函数的压缩程度，为避免陷入局部最小一般取1。

$>e_k=x_k-{\hat{x}}_k---\left(1\right)$>

$>\left(\begin{array}{c}f\left(x\right)=\frac{1}{(1+e^{-\mathrm{\lambda x}})}\\ f^{\prime }\left(x\right)=\mathrm{\lambda f}\left(x\right)[1-f\left(x\right)]\end{array}\right)---\left(2\right)$>

假设网络中第j个节点输出为将其表示为公式(3)。

$>{\hat{x}}_k\left(j\right)=\underset{i=1}{\overset{n}{\Sigma }}{\omega }_{\mathrm{ij}}h\left(s_i\right),j=\mathrm{0,1},...,n---\left(3\right)$>

式中ω_ij为连接权值；式中h(s_i)为隐层的第i个神经元的输出，其中s_i为其输入和，表示为公式(4)。

$>s_i=\underset{i=1}{\overset{n}{\Sigma }}{a}_{\mathrm{ni}}*x_k+\underset{m=1}{\overset{n}{\Sigma }}{b}_{\mathrm{mi}}*e_k---\left(4\right)$>

式中a_ni为输入单元与隐层的连接权值，b_mi为隐层与输出单元的连接权值。上述定义使得隐层的每个神经元节点仅接受自身单元的反馈，由于遗忘因子的加入，使得各个节点之间不存在反馈联系。

基于上述定义，我们提出了一个改进型匹配模型，如图1所示。

定义2：自适应调整机制：网络学习模型随着神经元数量的变化而变化，但网络中参数的初始值是根据统计学理论随即选择的。尽管这种方法有助于增加获取全局最优值的可能性，但这种方法有其盲目性和随意性，为此本文提出一个自适应调整机制来避免这个问题。

在自适应调整机制中，将学习样本输入至已确定的网络匹配模型中，进行迭代计算。在计算过程中，运用公式（5）来计算隐层节点性能均方差，并将训练的结果误差值传播至输出层，在输出层中继续利用公式（6）来计算各节点误差值；将所计算出的误差反向传播至隐层，利用公式（7）继续迭代，直到满足预设条件。

$>e\left(p\right)=\frac{1}{2}\underset{p\in \mathrm{output}}{\Sigma }{(t_p-x_p)}^2---\left(5\right)$>

其中，t_p(p=l,2,…,n)是样本的期望输出值，x_p是输出层中第p个节点的实际输出值。

$>{\hat{e}}_p=e\left(p\right)(1-x_p)(t_p^{\prime }-x_p)---\left(6\right)$>

其中，(p=l,2,…,n)是输出层的期望输出值。

$>{\hat{e}}_p^{\prime }={\hat{e}}_p(1-x_p)\underset{p\in \mathrm{output}}{\Sigma }{\omega }_{\mathrm{ij}}{\delta }_p---\left(7\right)$>

其中，δ_p为输出层与隐层间的阈值(Threshold)。由于阈值的选取直接导致各误差的传播速度，因此，我们需要一个自适应变化的阈值来加快传播速度。为此，我们利用公式（8）来对阈值进行修正。

δ_p＝α(E（p）+βω_ij)           （8）

其中，E(p)为第p个节点的梯度，利用Sigmoid函数计算一阶导数。α,β为(0,1)开区间的随机值。利用修正后的阈值，再计算各节点误差值，对比学习停止条件，若误差精度达到设定要求，则一轮迭代结束，输出层输出结果。若未满足，则通过公式（9）修正连接权值(Connecting Weight)，以此来加快各层间连接响应速度。

ω_ij＝η(p)δ_px_ij      （9）

其中，x_ij是节点i到节点j的输出，η(p)是初始学习指数。训练开始阶段，要求连接权值较大以加快学习速度。而当学习接近优化区时，连接权值就必须相应的变小，否则将产生振荡而不收敛，进而影响网络的稳定性。每一层连接权值的修正都与BP网络的学习速率有关，因此在改变连接权值的同时保证学习指数随其变化，使得神经网络学习传播模型能自适应变化，以适应数据量的增加，而不会坠入局部最小值。于是我们利用公式（10）来自适应调整学习指数(Learning Rate)。

$>\eta (p+1)=\eta \left(p\right)*\frac{E\left(p\right)}{E(p-1)}---\left(10\right)$>

其中下一个节点的学习指数η(p+1)是通过当前学习指数η(p)乘以当前梯度与前一个节点的梯度之比来优化，可使算法获得更加稳定的收敛性，并能明显减少学习次数。

通过上述定义，我们可以得知，当网络匹配模型以及各层神经元数量确定之后，运用自适应调整机制来优化网络中的参数，以使得网络在匹配过程中能有更好的准确性及稳定性。乱序数据流中基于误差反向传播的模板匹配算法的基本步骤如下所示：

1)利用随机发生器产生乱序数据流，在输入层读取数据，并在隐层中设定可接受误差范围。

2)动态设定匹配模板，初始化各层参数，在输入层对数据流进行预处理。

3)进行模板匹配，计算各节点误差。若数据在误差范围之内则视为匹配成功，直接输出结果。若不在误差范围之内，则视为此次匹配失败，修正连接权值、阈值及学习指数，来进行下次匹配，再反向传播至隐层进行迭代计算。

4)匹配结束后，输出输出层的匹配结果。

本发明的一种乱序数据流中基于误差反向传播的模板匹配方法为：对误差反向传播进行改进修正，并将改进后的BP算法运用到模板匹配机制中，提出一个改进型匹配模型，对数据进行预处理；提出神经元优化机制，重新定义神经元计算公式，加入相关系数和离散度；提出动态自适应调整机制，重新定义性能均方差函数、输出层节点误差项、隐层节点误差项、阈值、连接权值、学习指数；根据匹配模型未知的乱序数据流以及用户的不同需求，确定所需的匹配模板，并对数据流进行预处理，同时加入遗忘因子，动态调整匹配模板；设定好匹配模板之后，运用神经元优化机制，动态调整神经元个数，自动删除无效冗余节点；同时运用自适应调整机制修正阈值、连接权值和学习指数；其具体步骤如下：

1）利用随机发生器产生乱序数据流，在输入层读取数据，并在隐层中设定可接受误差范围；

2）动态设定匹配模板，初始化各层参数，在输入层对数据流进行预处理；

3）进行模板匹配，计算各节点误差；若数据在误差范围之内则视为匹配成功，直接输出结果；若不在误差范围之内，则视为此次匹配失败，修正连接权值、阈值及学习指数，来进行下次匹配，再反向传播至隐层进行迭代计算；

4）匹配结束后，输出输出层的匹配结果。

提出一个改进型匹配模型，对数据进行预处理，具体描述如下：

BP网络的非线性映射特性适用于乱序数据流的非结构性映射，而且可以利用算法自学习功能，通过对样本的分析辨识出有价值的数值序列；在乱序数据流中，利用数值来代替事件，以此给BP网络的参数修正和自适应匹配创造条件；而网络的模型是影响网络学习性能的主要因素之一，通常根据经验人工获取；对于匹配模型未知的乱序数据流序列，数据是随时间而不断变化的，使用静态匹配模板显然不能完全满足用户的不同时刻段的不同需求，因此将输入层样本输入设为(x₁,x₂x₃,…,x_k,1≤k≤n)，n为输入层节点个数，输出层样本输出为其中f(x_k)表示网络的输出函数，网络通过对样本学习训练，调整各神经元之间的连接权值来实现对模型参数的逼近，同时加入遗忘因子，使得网络在连接权值调整的同时也进行网络结构的学习，从而实现对模板的动态建模和参数辩识；在改进型模型中在网络输入层对输入样本作了预处理，对乱序数据流进行归一化操作，并用公式(1)事先计算好误差项，隐层误差计算采用的Sigmoid作用函数，在闭区间[0，1]上的Sigmoid函数表达式及其导数定义为公式(2)，其中λ决定Sigmoid函数的压缩程度，为避免陷入局部最小一般取1

$>e_k=x_k-{\hat{x}}_k---\left(1\right)$>

$>\left(\begin{array}{c}f\left(x\right)=\frac{1}{(1+e^{-\mathrm{\lambda x}})}\\ f^{\prime }\left(x\right)=\mathrm{\lambda f}\left(x\right)[1-f\left(x\right)]\end{array}\right)---\left(2\right)$>

假设网络中第j个节点输出为将其表示为公式(3)

$>{\hat{x}}_k\left(j\right)=\underset{i=1}{\overset{n}{\Sigma }}{\omega }_{\mathrm{ij}}h\left(s_i\right),j=\mathrm{0,1},...,n---\left(3\right)$>

式中ω_ij为连接权值；式中h(s_i)为隐层的第i个神经元的输出，其中s_i为其输入和，表示为公式(4)

$>s_i=\underset{i=1}{\overset{n}{\Sigma }}{a}_{\mathrm{ni}}*x_k+\underset{m=1}{\overset{n}{\Sigma }}{b}_{\mathrm{mi}}*e_k---\left(4\right)$>

式中a_ni为输入单元与隐层的连接权值，b_mi为隐层与输出单元的连接权值，上述定义使得隐层的每个神经元节点仅接受自身单元的反馈，由于遗忘因子的加入，使得各个节点之间不存在反馈联系。

提出动态自适应调整机制，具体描述如下：

在自适应调整机制中，将学习样本输入至已确定的网络匹配模型中，进行迭代计算，在计算过程中，计算隐层节点性能均方差，并将训练的结果误差值传播至输出层，在输出层中继续计算各节点误差值；将所计算出的误差反向传播至隐层，利用公式（5）继续迭代，直到满足预设条件

$>{\hat{e}}_p^{\prime }={\hat{e}}_p(1-x_p)\underset{p\in \mathrm{output}}{\Sigma }{\omega }_{\mathrm{ij}}{\delta }_p---\left(5\right)$>

其中，δ_p为输出层与隐层间的阈值(Threshold)，ω_ij为连接权值，x_p是输出层中第p个节点的实际输出值，为隐层节点性能均方差，e为节点误差值，由于阈值的选取直接导致各误差的传播速度，因此，需要一个自适应变化的阈值来加快传播速度。为此，利用公式（6）来对阈值进行修正

δ_p＝α(E（p）+βω_ij)      （6）

其中，E(p)为第p个节点的梯度，利用Sigmoid函数计算一阶导数，α,β为(0,1)开区间的随机值，利用修正后的阈值，再计算各节点误差值，对比学习停止条件，若误差精度达到设定要求，则一轮迭代结束，输出层输出结果；若未满足，则通过公式（7）修正连接权值Connecting Weight，以此来加快各层间连接响应速度

ω_ij＝η(p)δ_px_ij     （7）

其中，x_ij是节点i到节点j的输出，η(p)是初始学习指数，训练开始阶段，要求连接权值较大以加快学习速度，而当学习接近优化区时，连接权值就必须相应的变小，否则将产生振荡而不收敛，进而影响网络的稳定性，每一层连接权值的修正都与BP网络的学习速率有关，因此在改变连接权值的同时保证学习指数随其变化，使得神经网络学习传播模型能自适应变化，以适应数据量的增加，而不会坠入局部最小值；利用公式（8）来自适应调整学习指数Learning Rate:

$>\eta (p+1)=\eta \left(p\right)*\frac{E\left(p\right)}{E(p-1)}---\left(8\right)$>

其中下一个节点的学习指数η(p+1)是通过当前学习指数η(p)乘以当前梯度与前一个节点的梯度之比来优化，可使算法获得更加稳定的收敛性，并能明显减少学习次数。

有益成果：本发明对大数据中乱序数据流的模板匹配算法进行了研究，提出了一种基于BP的模板匹配算法，算法中运用了动态模板匹配机制、动态自适应调整机制，旨在数据量较大时加快匹配速度、提高匹配精度。仿真实验表明，在多次运行改进型算法后，选取收敛次数多而稳定的时刻的参数值，作为算法的最忧参数；而后，将最优值运用于乱序数据流中的模板匹配中，来使得算法能较好的适应乱序数据流，并进一步改善模板匹配精度，提升运行时间，以及算法稳定性。

附图说明

图1基于BP的匹配模型；

图2MMA-IBP算法流程图；

图3阈值与收敛次数关系图；

图4连接权值与收敛次数关系图；

图5学习指数与收敛次数关系图；

图6收敛次数与迭代次数的关系；

图7学习次数与迭代次数的关系；

图8匹配正确率与迭代次数的关系；

图9漏警概率与迭代次数的关系；

图10虚警概率与迭代次数的关系；

图11运行时间与迭代次数的关系。

具体实施方式

在Matlab7.0仿真平台上对MMA-IBP进行仿真分析，并与传统模板匹配算法AEM进行对比实验。

仿真分析的实验环境为一台主频3.2G，4G内存的PC，软件环境基于JAVA、Matlab7.0来编程实现算法功能。BP算法的结构设置为10-30-1(输入层-隐层-输出层)，对于每个样本，初始阈值在[1,2]之间随机变化，连接权值在[2.5,3.5]之间随机变化，学习指数在[0.5,1.5]之间随机变化。通过对10000组数据的多次学习，找出算法结构的最优阈值、连接权值及学习指数，并将最优解运用于模板匹配中。

用算法的收敛次数、学习次数、匹配正确率和运行时间作为算法的性能评价指标。当乱序数据流中的一组数据经过一次匹配，即称之为一次迭代，若误差在设定范围之内，即判定为一次收敛，相同条件下收敛次数越多算法精确性越高，获得一次最优解则称为一次学习，在同样算法运行次数下学习次数越少算法效率越高。在数据量相同的情况下，匹配正确率等于匹配正确个数与匹配个数之比，其值越高则精确度越高。

此外，为了验证算法模板匹配的效率，引入漏警概率（Missing Alarm，MA）定义为可匹配数据流因为缺失过多有价值信息而被误判为不可匹配概率，虚警概率(False Alarm，FA)则是可匹配事件因为缺失事件较少而被系统视为不可匹配事件的概率。设总共有P个类别为1的样本(可以匹配的子集)，N个类别为0的样本(无法匹配的子集)，经过处理后，有TP个类别为1的样本被正确判定为类别1，FN个类别为1的样本被系统误判定为类别0，显然有P=TP+FN；有FP个类别为0的样本被系统误判断定为类别1，TN个类别为0的样本被系统正确判为类别0，显然有N=FP+TN。由此得到漏警概率和虚警概率的计算公式：

MA＝FN/(TP+FN)    （16）

FA＝FP/(TP+FP)    （17）

为了分析出改进型算法对数据分析的性能，我们对随机产生的10000组数据进行实验。

针对随机产生的10000组数据，在给定初始阈值、连接权值、学习指数下通过公式13、14、15对这些变量进行动态调整，多次运行改进型算法，观察算法实验的平均收敛次数，得到如图3-5仿真结果。

图3为当阈值在[1,2]之间随机变化时，算法在经过10次运行之后得到的平均收敛次数。随着阈值的不断变化，在区间[1,1.4]上算法已能获得较好的收敛次数，但仍存在小幅波动，而在阈值为1.5时刻，算法能获得最大的收敛次数，随后呈现逐步下降趋势。因此，当阈值为1.5时，MMA-IBP获得的平均收敛次数相比于其他时刻有较大的优势，为此，我们选取最优阈值为1.5。

图4为当连接权值在[2.5,3.5]之间随机变化时，算法在经过10次运行之后得到的平均收敛次数。随着连接权值的不断变化，在区间[2.5,2.9]上算法可以稳定获得15次以上的收敛次数，但仍存在小幅波动，而在连接权值为3时刻，算法能获得最大的收敛次数，随后收敛次数并不随着连接权值的变大而增多。因此，当连接权值为3时，MMA-IBP获得的平均收敛次数相比于其他时刻有较大的优势，为此，我们选取最优连接权值为3。

图5为当学习指数在[0.5,1.5]之间随机变化时，算法在经过10次运行之后得到的平均收敛次数。随着学习指数的不断变化，在区间[0.5,1]上算法的收敛次数起伏波动较为明显，并且不能获得一个较大的收敛次数值，但在学习指数为1.1时刻，算法能获得最大的收敛次数，并且有较好的稳定性，随后收敛次数逐步下降。因此，当学习指数为1.1时，MMA-IBP获得的平均收敛次数相比于其他时刻有较大的优势，为此，我们选取最优学习指数为1.1。

针对随机产生的数据，在最优的阈值为1.5、连接权值为3、学习指数为1.1下，运用动态匹配模板对乱序数据流进行运行模板匹配，观察算法的性能指标，得到如图6-11仿真结果。

在图6中，在数据量不断增加的情况下，由于遗忘因子的加入，使得算法在匹配过程中并不记忆之前的训练，使得算法收敛次数能维持在一个较稳定的水平上，并不随着网络负荷的增加而减少。相比于AEM，本文提出的改进型算法不仅能获得比较多的收敛次数，而且在数据负荷增加的情况下依然能保证算法的稳定性和可靠性。

在图7中，在数据量不断增加的情况下，AEM的学习次数存在较大的波动。而改进型算法由于删除了冗余神经元，因此能在较少的学习次数下就能满足原始设定的误差范围。

在图8中，改进型算法由于确定了一个最优学习指数，使得算法不会坠入局部最小值，因此能稳定获得85%以上的正确率，很大程度上改进了匹配准确性，而且相比于AEM算法具有较好的稳定性，即正确率浮动变化范围不大。

在图9中，改进型算法在迭代次数很少的情况下，漏警概率与AEM的漏警概率相差并无明显优势。随着数据量的不断增加，缺失元素逐渐增加，漏警概率逐步上升，相比于AEM的改进型算法漏警概率较低。

在图10中，改进型算法在迭代次数很少的情况下，虚警概率与AEM的虚警概率相差并无明显优势。随着数据量的不断增加，缺失元素逐渐增加，虚警概率逐步上升，相比于AEM的改进型算法虚警概率较低。

从漏警概率和虚警概率随着数据量增长而变化的趋势可以看出：数据量越大，系统出现漏判的概率在降低，而误判的概率升高。因为随着数据量的增多系统将更多的判为可以匹配，并且发现迭代次数少时，差别不大，因为缺失元素较少，发生错误匹配的概率并不高。当迟到事件增多时，改进型算法精确度方面有着更好的性能，而AEM的漏警和虚警概率将显著增大。因为AEM模板长度非常有限，因此不能很好的应对大数据，也不能很好的支持较长的模板。相比之下改进型算法只保存匹配可能性较高的数据，从而保证了匹配精度。在图11中，随着数据量的增大，AEM算法由于搜索表长度在不断增长，而匹配的冗余节点并没有相应的减少，因此使得匹配时间一直维持在较高水平。而改进型算法运用了神经元优化机制，使得匹配速度大大提高。