试论用于特征子集选择的异步并行微粒群优化方法

2017-11-02胡滢

赤峰学院学报·自然科学版 2017年19期

关键词：子集微粒优点

胡滢

（铜陵学院电气工程学院，安徽铜陵 244061）

试论用于特征子集选择的异步并行微粒群优化方法

胡滢

（铜陵学院电气工程学院，安徽铜陵 244061）

特征子集的选择是数据挖掘与模式分类的重要方法.本文主要从微粒编码、比较微粒适应值、更新微粒引导者、一致混沌变异和计算步骤五个方面对用于特征子集选择的异步并行微粒群优化方法进行分析，通过实验比对，可以发现这种方法具有良好的效果.

特征子集选择；异步并行方式；微粒群优化

最优化问题指的是在有限或无限决策中挑选最优的决策，而微粒群优化（Particle Swarm Optimizer,PSO）算法是一种基于群智能方法的演化计算方法，是将微粒进行初始化随机处理，然后利用迭代寻找最优解的方法.目前，这种方法已经广泛应用到神经网络训练、预测控制及函数优化领域.

1 用于特征子集选择的异步并行微粒群优化方法

1.1 微粒编码

用于特征子集选择的异步并行微粒群优化首先需要对微粒进行编码处理.在具体操作中，应将每一个问题的特征都当作是微粒的一维二进制变量，所有特征加在一起的数量之和就是微粒变量的长度.也就是说在第i位是1的情况下，会选择第i个特征；如果不是，那么这个特征就会屏蔽.

1.2 比较微粒适应值

为了所选择的特征子集能够以少量特征起到良好的分类作用，本文认为应该从两方面着手对其适应值进行比较和评价[1].一是微粒子集包含的特征数量，二是所确定分类器的准确度.所有的特征子集中都包含着或多或少的特征，在两个特征子集准确度保持一致的情况下，可以认定数量较少的子集胜出.和最优值进行比较，如果该特征子集的准确率很低，可包含的特征数量不大，那么我们可以认定这两个特征子集和最优的特征子集十分接近，那么就可以增加算法的方式得到最优的特征子集，也就是说，尽管这种特有子集相对于最优值来说准确率并不高，可是对于准确率较高的特征子集来说，它们所包含的特征数量得到了显著的降低.可以利用上述特征完成微粒适应值的比较工作.

现假设η是分类器的准确率，λ是特征子集中所包含的特征数量，在给定任意两个微粒xi、xj和大于零的常数ε的情况下，可以得出微粒适应值比较的ε支配关系.

在λ（xi）=λ（xj），同时满足η（xi）=η（xj）的情况下，那么我们可以认定xi与xj是一种等价关系.

在λ（xi）＜λ（xj），同时满足η（xi）≥η（xj）-ε的情况下，或在λ（xi）=λ（xj），同时满足η（xi）＞η（xj）的情况下，可以认定xi对于x→j起到了支配的作用.也就是说，分类器准确度和常数的取值应该成反比关系.

1.3 更新微粒引导者

微粒引导者包含个两个方面，即个体最优点和全局最优点.

1.3.1 个体最优点的更新

前者可以看做是微粒记忆，指的是微粒从最开始到现在的迭代次数得到的最优位置.可以通过实例进行论述，假如pi(t)是微粒xi(t)的个体最优点，而xi(t+1)是第t+1代的新生微粒.那么在pi(t)和xi(t+1)处于等价关系的时候，可以在xi(t+1)与pi(t)之间进行随机挑选，挑选结果可作为微粒个体最优点；xi(t+1)ε 对 pi(t)起到支配作用的条件下，可以取x→i(t+1)代替个体最优点pi(t+1).如果二者关系都不是，那么pi(t+1)可以直接取pi(t).

1.3.2 全局最优点的判断

全局最优点的判断指的是在所有微粒群中对最佳位置完成所有工作，如上文所说，采用ε支配关系的比较方法可以得出个体最优点，个体最优点所在的微粒群就可以认定为全局最优点.

1.4 一致混沌变异

混沌属于非线性现象，本身有着随机性和遍历性等特点，依照自身的规律，它可以在一定条件内对所有状态作出遍历，且没有重复，依照这些特性，结合本文所说算法，可以起到增强全局搜索效果的作用[2].

这种通过结合而来的混沌变异算子在国内已经有人提出，即利用Zaslavskii映射函数可以得到混沌变量，然后对此混沌变量完成混沌空间→决策空间的转化，进而能够实现微粒飞行速度的变异.设速度上下界是Bround，算法终止代数*//是Tmax,决策变量维数是n.

为确保Zaslavskii映射可以展现出完全馄饨状态，需要进行合理的取值，设r=3，v=400，a=12.6695.可以观察其混沌状态，通过观察可以发现变异算子会对微粒飞行速度造成影响，且对于全局的探索来说，在初始阶段效果较好.变异算子的影响效果和迭代次数之间是呈反比例的关系.需要额外注意的是，在变异后，如果微粒的速度已经在允许范围之外，那么取值应该是速度变量的下界或上界.

1.5 算法步骤

异步并行的方法可以缩短微粒群优化的时间，进而达到提高效率的作用.该一部并行微粒群优化算法的步骤可以概括为：循环分解——消息发送——算法操作.

可以对其步骤进行简单分析，第一，需要在决策空间内完成微粒群随机初始化的工作；第二，需要利用主处理器把需要评价的微粒xj和个体最优点传送到没有处于工作状态的附属处理器；第三，附属处理器会进行分类器准确率的确定工作，利用ε的支配关系，可以完成个体最优点pi的更新工作，进而将结果反馈给主处理器；进而由主处理器依据结果完成决策评价的工作，将全局最优点找出，进而根据公式，和一致混沌变异算子对微粒位置进行更新.在具体操作中，需要对主处理器的优化参数、算法以及微粒速度等条件进行设定，需要对微粒评价的处理完成排序[3]；而对于附属处理器，需要结合微粒现有特点对SVM分类器进行训练，且在准确率方面，需要结合10阶交叉验证的结果进行分析.

设迭代次数为t，学习因子是c1和c2，惯性全值为w，在[0,1]之间的随机数是r1和r2.其调整位置的公式为：

而利用二进制微粒群优化算法，微粒xi中的分量xij取值在[0,1]之间，那么对其更新微粒位置可以利用逻辑函数转化的方法，其转化公式为：

2 实验及性能分析

2.1 实验流程

对于优化性能进行分析，需要利用学习数据库，测试问题包含了Class、Vowel等数据集.具体信息可见表1.

表1 测试问题数据集

如表1所示数据，可以采用SFS（前向选择）算法、BPSO算法和HGA（混杂遗传）算法等五种算法对数据问题优化20次，可以得出结果，进而完成比较.

2.2 性能分析

以Class为例，其结果如表2所示.

表2 多种算法结果示例表

通过分析结果，可以发现BPSO的平均准确率要低于AP-PSO与MDPSO，且SFS平均准确率要低于HGA，如果测试问题较少，如Class与Vowel，呢么SFS与HGA效果可以达标，而特征数目较多的时候，AP-PSO的性能更好.

对于AP-PSO算法并行性能进行分析，可以利用Satellite的数据集，利用三个方法进行性能测度.一是效率Ep等于加速比Sp和处理器数量p的比值；二是加速比Sp等于串行算法最劣条件下运行时间Ts与并行算法最劣条件下运行时间Tp的比值；三是并行算法中扩展性的一个指示器

据此进行计算分析，可以得出结果，即同步并行方式与异步并行方式的计算速度都和处理器数目成正比，二者相比，异步并行方式速度增加的幅度更大；依据不同数目下的处理器进行比较，可以发现无论数目为多少，异步并行方式的速度都更快；在多个处理器之中，存在一个性能劣质的处理器时，异步并行方式所受影响更小.因为这种性能优势，这种方法可以在多个领域存在强大的发展空间，如物流车辆路径问题的解决等.