利用并行惯性权重OOL-FA的大数据分类

钟章生，陈世炉，陈志龙

(1.南昌理工学院 计算机信息工程学院，江西 南昌 330013；2.中国船舶总公司 第六三五四研究所，江西 九江 332000；3.南昌理工学院 电子与信息学院，江西 南昌 330013)

0 引 言

在数字化时代，深入挖掘海量数据内部蕴藏的有用信息来指导具体的工程问题，而在基于MapReduce范式的技术体系中，数据特征选择与数据分类是两项非常重要且复杂的工作[1-3]。

针对特征选择问题，部分文献提出针对高维数据的轻量级特征选择方法，采用加速粒子群优化对数据特征进行群搜索，在加快处理时间的同时提高了分析精度，但并未完全解决粒子群算法的局部最优问题[4-7]。针对数据分类问题，部分文献提出了基于在线打包集成的高效分类器，通过在训练实例上引入在线重采样机制和基于纠错输出码的鲁棒编码方法，减少了分类器之间相关性的影响，同时采用基于分类性能的动态更新模型减少不必要的更新操作，提高了分类效率。然而，并未解决分类精度与数据规模的矛盾，在分类精确性上仍需改进[8-11]。

为了有效提高数据选择与分类算法的速度与精度，在借鉴已有方法的基础上，提出基于惯性权重正交反向学习(orthogonal opposition learning，OOL)——萤火虫算法(firefly algorithm，FA)的数据特征选择算法：利用萤火虫算法实现数据特征的全局寻优，通过引入惯性权重来提高收敛速度，借助正交反向学习来提高选择精度，从而在特征选择过程的速度与精度上实现有效权衡。在此基础上，提出基于结构感知卷积神经网络(structure-aware convolutional neural network，SACNN)算法的数据分类方法，利用SACNN较强的非线性学习能力实现大数据的精准分类。在Spark框架下对所提方法进行实验分析，结果验证了所提方法的有效性和优越性。

1 利用IWOF算法的大数据特征选择

高维数据特征选择的目标是通过寻找特征最小子集来建立精确的数据预测模型。随着数据维数的指数级增长，现有的批量学习[12]和在线学习[13]方法已经很难满足特征选择对于快速性和可伸缩性的要求。为了解决这一问题，提出一种融合正交反向学习和萤火虫算法的新型数据特征选择算法，并利用惯性权重技术提升算法的收敛速度。首先，在映射阶段将原始大数据集分解为数据块；其次，基于正交反向学习和萤火虫算法选择大数据集特征；最后，将得到的部分结果合并到归约阶段的最终特征向量中。

1.1 问题描述

(1)

为了在实现在线数据特征选择的同时尽可能地减小选择错误，考虑

(2)

1.2 MapReduce概述

MapReduce[14]是在大数据处理中应用最广泛的编程范式之一，是计算机集群化应用中的重要技术手段。MapReduce分为两个阶段：映射和归约。映射阶段的作用是对输入数据集进行处理，得到一些中间结果，并对这些结果进行合并，以便在归约阶段生成最终的输出。

MapReduce模式依赖于一个基本数据结构，其定义为

k,v

(3)

map(k1,v1)→{(k2,v2),…,(kn,vn)}

(4)

reduce(k2,v2)→(k2,v3)

(5)

图1描述了MapReduce的流程图。

图1 映射归约MapReduce模式流程

1.3 基于惯性权重OOL-FA算法的特征选择

萤火虫算法(FA)全局搜索能力强，可用于求解多目标优化问题[15]。为了弥补FA算法在局部搜索能力和收敛速度上的不足，将正交反向学习(orthogonal opposition learning，OOL)引入FA，以深入挖掘并保存个体和反向个体中的有用信息。由此形成了一种新的启发式特征选择算法，即混合多目标OOL-FA算法，即IWOF。

在具体介绍IWOF算法之前，需要先对经映射、规约后的数据进行编码和初始化，以形成可供IWOF算法使用的输入数据。

1.3.1 编码与初始化

编码方法：反映大数据集样本矩阵特征的编码方法可以充分保证启发式算法的性能。采用的编码技术由两部分组成，首先是原始大数据集样本矩阵的映射。Mapij矩阵表示大数据集样本矩阵Map的对角线。TempMap表示临时大数据集样本矩阵，TempMapij表示矩阵对角线，通过该矩阵的每一行显示与该行对应的机器上的数据集样本序列，而矩阵的每一列都显示大数据集样本分类或预测过程中特征的总和。

初始化：大数据集样本矩阵Map对角线上的每个单元格取100，即Mapij=100，表示每个数据中心都在内部维护其100%的特性选择。

1.3.2 基于萤火虫算法的最优特征集选择

在上述编码方案的基础上，利用小邻域结构和大邻域结构两种不同的邻域搜索结构来寻找最优特征集。在建立第一个搜索结构的邻域的同时，利用萤火虫算法的移动算子选择下一个最优特征集。此外，为了建立第二个搜索结构的邻域，在特征选择问题中引入交换、插入、逆3个常用运算符。通过左移操作符，将特性集中的临时特性Ftemp移动到当前特性集中Fcurrent。在萤火虫算法中，通过后续关系确定最优特征i向最具吸引力(或更亮)的另一个特征j的方向运动，其变化过程描述为

(6)

利用笛卡尔距离计算方法，可以得到两个萤火虫i和j之间的距离

(7)

式中：xik为第i个萤火虫的第k个组成部分。

通过计算两个特征矩阵之间的距离，即可得到TempMap，然后就可以利用分类指标(查全率、精确度、准确度)计算新的适应度值。一般来说，准确度是指正样例和负样例的总量占总数据量的比例，适应度值的计算方法为

(8)

式中：TP为正样例，FN为漏报，TN为负样例，FP为误报，η为适应度值。

更新过程为：如果新的适应度值低于当前适应度值，则固定新的位置，且初始Fcurrent被更新为与当前特征矩阵Ftemp等价；否则(即Fcurrent≥Ftemp,F∈[0,1])，在区间[0,1]内产生随机数r，当r

为了建立第二搜索结构的邻域，对经典的插入算子和逆算子进行了改进。在这些运算符中，首先，随机选择一个特征矩阵，并使用相应的数据集矩阵；然后，在相同的概率下，考虑数据集样本，并在选定的特征集上实现算子。在交换运算符的情况下，随机选择两个位置，并相对于所有数据集样本，将两个现有数据集样本特征矩阵的位置互换；对于插入运算符，随机选择一个特征和一个位置，并将所选特征插入整个数据集矩阵中所选的位置；在逆算子的情况下，随机选择序列的两个点，并将这两个特征之间的数据中心位置反演到整个数据集矩阵中；如果r≥F，则否定该解。在每个迭代过程中，算法从数据集样本矩阵、映射中任意选择一行和一列，并临时将选择的单元格设置为零(如果对角线上没有相等的单元格)。

1.3.3 萤火虫算法的改进

为了提高萤火虫算法的收敛速度，引入惯性权重算法。此外，为了解决萤火虫算法的收敛精度，引入正交反向学习算法。通过上述算法的改进，即实现了萤火虫算法在寻优、速度和精度上的综合优化。

为了改善萤火虫算法的收敛速度，需要在萤火虫位置更新公式中引入惯性权重，其表达式为

(9)

式中：w为惯性权重。

为了避免陷入局部最优，需要对w进行如下设计

(10)

式中：l为实时迭代次数，L为迭代次数最大值。由上式可知，当l<0.5L时，w取值较大，由于ε为均匀分布的随机数，因此w服从较大的均匀分布；反之，w服从较大的均匀分布。

反向学习的核心思想是同时评估当前点和其反向点，择优使用，以此来提高搜索精度，反向学习的基本定义见文献[15]。

为了充分利用群体搜索信息，需要借助重心反向，并以群体重心为参考点计算反向点，具体定义如下。

定义1 设di∈R是带有单位质量的点，i=1,…,K，则K个点的重心Gj定义为

(11)

(12)

G为反向点重心，基于正交表的正交反向学习算法的具体算法流程见文献[15]，此处不再赘述。

1.3.4 并行化IWOF算法

利用MapReduce模型实现IWOF算法的并行化。假设T是一个训练集，m是映射任务的数量。首先，映射归约分割方法将T分割成m个不相交的实例子集。其次，每个子集Ti，i∈{1,…,m}由等价映射函数处理，由于这个分区是依次执行的，每个子集的实例数量大致相同，因此T文件的随机化保证了类的平衡。

特征选择算法包含每个Ti的映射阶段，因此二元向量si={si1,…,}表示IWOF算法选择了哪些特征。每一个二进制向量在归约阶段取平均值，得到一个式(13)所定义的向量x，其中xj被称为在线特征选择应用程序在其结果中包含特征j的比率，该向量被称为完整在线特征选择学习的结果，用于构造用于附加机器学习原则的缩减数据集

(13)

式中：N为特征数量。

为了在计算特征向量x时以可伸缩的方式尽快从原始数据集中消除不重要的特征，需要采用映射归约模式。通过阈值θ实现矢量x的二值化，即

S={s1,…,sN}

(14)

(15)

式中：S为简化数据集选择的特性向量。

1.3.5 IWOF算法流程

(1) 输入特征F从原始数据集X=(x1j,…,xnj)；

(2) 计算适应度函数f(x)，其等于分类精度

(3) 从数据集样本中生成萤火虫初始种群

xi,(i=1,2,…,n)(n=100)

(4) 利用适应度函数f(x)确定xi处的光强li；

(5) 定义光吸收系数γ：

(6) Whilet<100

(7) Fori=1：n

(8) Forj=1：i

(9) If (Ij>Ii) && (Fcurrent≥Ftemp)

萤火虫I在d维方向上沿j方向前进；

吸引力随距离r通过e-γr发散；

(10) Else 执行交换、插入和逆运算符；

(11) 转到步骤(9)；

(12) End Forj；

(13) End Fori；

(14)对萤火虫进行分类并定位当前的适应度值；

(15)如果某些特性直到t小于最大进化代数时才被选中

执行正交反向学习

(16) End While；

(17) 处理结果和可视化。

2 利用SACNN的数据分类

传统的分类算法难以处理大量的数据。因此，采用IWOF算法进行在线特征选择，然后选择分类器对所得特征进行分类。卷积神经网络(convolutional neural network，CNN)分类精度高，是一种应用十分广泛的深度神经网络。它的权值共享网络结构使之更类似于生物神经网络，降低了网络模型的复杂度，减少了权值的数量。

经典的CNN算法以较小的计算量对数据进行学习，具有稳定的学习效果，但其非线性处理能力较弱，因此在处理复杂数据时能力稍显不足。

针对CNN存在的问题，选择图2所示的结构感知卷积神经网络[18]算法实现特征数据的精确分类。图中：x∈Rn×c为输入，y∈Rn为输出，f(·)为功能滤波器，rji为第j个顶点与第i个顶点之间的关系值，M∈Rc×c为衡量局部顶点之间关系的矢量矩阵，T(·)为tanh函数，xj、xi代表输入x的第j行、第i行的行向量。

图2 SACNN结构

SACNN的输出为

(16)

式中：εji代表第i个顶点的第j个临近点；E为这些点组成的集合；hk(·)为切比雪夫多项式；vk为多项式中的系数；K为多项式的阶数。

通过将传统CNN中的卷积运算替换为结构识别卷积运算，使得SACNN具有非常高的模型学习能力。当将其应用到数据分类中时，可以充分发挥其精确建模能力。图2给出了SACNN应用的关键步骤及对应的算法，即：将数据集输入SACNN后，先计算这些数据之间的关系值，然后再对这些关系值进行滤波处理，最后再利用输入数据和滤波后的关系值计算最终的输出值。

3 实验结果与分析

在Spark框架下，为了检验IWOF算法的有效性，使用二分类数据集进行数据特征选择与分类实验。数据集选为包含2000个数值特征的，数据量为50万个样本集合的Epsilon。此外，包含631个特征，数据量为6600万个样本的ECBDL14数据集。表1概述了这些数据集的主要特征。除了属性的数量外，用于训练和测试集的样本数量也在验证IWOF算法时进行了描述。在数据样本中，75%的样本用于培训，25%的样本用于测试。

表1 数据集概述

在应用映射归约模式支持的IWOF算法后，在上述数据集上，分别使用Spark中实现的SACNN、文献[9]和文献[10]这3种不同的分类算法对数据集进行分类实验验证。

3.1 评估指标

在处理分类问题时，必须将一个类标记为正类，另一个类标记为负类，分别考虑p个阳性样本和n个阴性样本的测试集。任何分类器的任务都是为每个样本分配一个类，此外，某些任务可能是不正确的。为了评估分类器的性能，在正样例、负样例、误报和漏报样品的基础上，统计并设计了一个融合矩阵，见表2。

表2 融合矩阵

利用表2可以推导出用于不平衡学习的性能指标，包括：精度P、查全率R、测度FM和几何平均GM，如下所示：

(1)精度P定义为检索到的相关实例的百分比，其表达式为

(2)查全率R定义为检索到的相关实例的比例，其表达式为

(3)测度FM定义为准确度与查全率相结合的测度，即准确度与查全率的调和平均值，其表达式为

(4)几何平均GM用来评估不平衡数据集上的分类器，几何平均指定了主流和少数类的分类性能之间的平衡，该指标考虑了敏感性和特异性，敏感性即为查全率，特异性SP和几何平均的表达式分别为

3.2 与其它方法的对比和分析

图3给出了3种分类算法在实验数据集分类实验中的精度和查全率结果。与文献[9]和文献[10]中的两类分类算法相比，提出的基于IWOF算法的SACNN分类算法的分类精度是最高的，其准确率约为94%，与文献[9]和文献[10]相比，提出的SACNN分类算法的准确率分别提高了5%和8%。由此可见，提出的算法很好地解决了高维数据集问题，这表明所采用的映射归约模式解决了并行处理的需求。然而，在查全率方面，提出的基于IWOF的SACNN分类算法虽然高于文献[9]，但明显低于文献[10]，这表明所提算法很难保证数据的学习覆盖率，即其在算法的通用性方面略差于文献[10]。

图3 3种分类算法的精度与查全率对比

图4给出了3种分类算法在实验数据集分类实验中的测度和几何平均结果。与文献[9]和文献[10]中的两类分类算法相比，提出的基于IWOF算法的SACNN分类算法的测度和几何平均结果均是最大的，这表明所提算法在大数据分类中的平均化性能指标方面具有明显的优势，且所提算法在收敛精度上高于文献[9]，但略低于文献[10]。

图4 3种分类算法的测度与几何平均对比

图5给出了3种分类算法在实验数据集分类实验中的准确率和错误率结果。与文献[9]和文献[10]中的两类分类算法相比，提出的基于IWOF算法的SACNN分类算法的精度是最高的，相应的其错误率则是三者中最低的。由此可见，提出的分类算法的分类准确率是可以得到充分保证的。

图5 3种分类算法的准确率和错误率对比

表3给出了以上3个实验的具体指标。

表3 不同分类器的评价指标%

为了进一步验证所提算法与文献[9]、文献[10]中的分类算法在大数据分类速度上的对比结果，图6给出了大数据集的训练运行时间，训练运行时间定义为用于训练或构造分类器的时间(以秒为单位)。

图6显示了针对3个不同分类器绘制的训练运行时间比较结果。文献[9]和文献[10]中的两类分类算法相比，提出的基于IWOF算法的SACNN分类算法的训练运行时间并不是最低的，即提出的IWOF算法的收敛速度介于文献[9]、文献[10]中的算法之间。由此可见，本文所提算法是以牺牲一部分快速性来换取分类准确率的。

图6 3种分类算法的训练运行时间对比

4 结束语

高维数据的特征选择与分类对于很多实际的工程问题来说非常重要，提出一种基于惯性权重OOL-FA算法的大数据特征选择算法，在此基础上利用SACNN算法实现了大数据的精确分类。在实际数据集上进行的实验结果表明了所提算法在准确率、测度、几何平均等方面的优越性。但实验结果也表明，所提大数据分类算法在动态性能和查全率上并不是最优的，这说明所提算法还有一定的提升空间。下一步的研究应该在保证分类精度的基础上，进一步提升分类算法的快速性。