基于Relief-PGS优化算法的数据分类

张菡玫

（武昌职业学院，湖北 武汉 430000）

0 引言

近年来，不同领域的专家对如何提高图像分类精度进行研究，普遍认为分类精确率的高低取决于图像特征的选择。即需要从输入的p个特征中选择出d（d＜p）个特征，并将这些特征评选为最优特征［1］，以此来进行分类。选择的特征集通常包含冗余特征，当冗余特征过多时，运算复杂度将加大，从而导致图像分类精度下降。为解决这一问题，需要对提取到的纹理特征进行筛选，并根据各个特征和类别的相关性对特征进行选择，从而减少特征数据的维度，提高运算速率。在筛选特征时，常用过滤式［2］特征选择法中的Relief 算法［3］，通过预处理来删除所选数据中的无关特征，缩小特征数据维度，并利用支持向量机［4］和粒子群-遗传优化算法［5］对筛选后的特征数据进行学习，从而提高分类的准确率。

为此，本研究提出Relief-PGS 优化算法，该算法能提高分类的准确率。先使用Relief 算法对特征集进行初步筛选，再将筛选结果和SVM 参数一起编码到粒子群-遗传算法中，对特征子集及SVM 参数进行同步优化。

1 原理及方法

1.1 Relief算法

Relief 算法根据所提供数据的特征和类别间的关联，从而赋予特征不同权重。权重值越大，表示图像的能力越强；权重值越小，表示图像的能力越弱［6］。Relief 算法的具体实现步骤如下。①对样本所有特征权重进行初始化，将其置0。②随机挑选样本xi，从xi的相同类别样本中查找最近邻样本H，从xi的不同类别样本中查找最近邻样本M。计算xi与H、xi与M分别在特征上的距离dist(xi,H)、dist(xi,M)。若dist( )xi,H＜dist(xi,M)，则xi不能有效区分同类别样本和不同类别样本，从而减小特征的权重［7］。反之，则增大特征的权重。③将上一步重复循环m次，最终获得n个特征权重。

1.2 支持向量机

支持向量机（Support Vector Machine，SVM）是一种基于最优化理论来解决机器学习问题的算法，可分为三类，即线性可分、线性不可分、非线性可分［8］。

SVM算法用分离超平面作为分离训练数据的线性函数，可解决线性分类问题［9］。假设训练样本集合为{(xi,yi)|i= 1,2,…,m}，其中，xi∈Rn为训练样本，yi∈{-1,1}为输入样本的类别。通过训练获得一个最优分类面，见式（1）。

式中：x为样本；ω为权向量；b为分类阈值。

根据最优化理论来引入拉格朗日函数，对SVM求取判别函数，见式（2）。

式中：xi、xj为样本；ai*=(a1*,a2*,…,ai*)为最优解，多数样本ai*为零，ai*不为零的样本决定最优分类面；b*为分类阈值，可由任意ai*求得。

1.3 粒子群-遗传算法

遗传算法（Genetic Algorithm，GA）是根据生物界优胜劣汰进化准则衍生出的随机优化搜索算法［10］。GA 在经过有限次迭代后，得到问题的近似最优解，包括三个基本操作，即选择、交叉和变异。

粒子群算法（Particle Swarm Optimization，PSO）是一种基于群体的随机优化算法［11］，PSO 的核心思想是在一个S维的搜索空间中找到m个粒子组成一个群体，S维的向量xi=(xi1,xi2,…,xis),i=1,2,…,m，利用xi对解的最优结果进行判断。

对参数优化问题，GA 有较好的全局搜索能力和种群多样性，但要经历选择、交叉和变异才能得到下代种群，计算效率较低，收敛速度较慢。PSO 只需将粒子当前最优位置与飞行历程中经历的最优位置进行比较，即可得到最优的飞行速度和飞行方向。粒子群-遗传算法（PSO-GA）是将PSO 和GA 联立，利用PSO来代替GA的选择算子，结合算法在初期的收敛速度更快，同时因保留GA 的交叉和变异算子，能提高全局寻优的能力［12］。

1.4 Relief-PGS优化算法

本研究基于Relief算法、PSO-GA和SVM对数据集特征进行选择和分类，即Relief-PGS 优化算法。先利用Relief 算法对获取到的数据特征集进行选择，然后将选择出的特征数据集和SVM 参数一起编码到PSO-GA 的染色体中，通过SVM 来构建适应度函数，并对所选择的特征数据集和SVM 参数进行优化，从而实现用较少的特征数据集和较短的优化时间来获得较高的识别精度，具体流程如图1所示。

图1 Relief-PGS优化算法流程

Relief-PGS 优化算法的具体步骤如下。①使用Relief 算法对图像进行一次特征筛选，得到特征矩阵。②采用PSO-GA 对参数进行初始化操作，种群大小为30，迭代次数为50，算法的终止条件为达到迭代次数或连续十代的适应度值不变。③生成初代种群。由于SVM 的惩罚系数C和核参数σ采用的是实数编码，而对特征的二次筛选是通过0、1 进行的，0 表示没有选择该特征，1 表示选择该特征，采用二进制编码。④将个体的后N位带入样本中，并对特征进行二次筛选。⑤将个体的前两位带入SVM 模型中，结合二次筛选的训练样本，确定SVM 分类模型。⑥将二次筛选出的测试样本放入到确定的SVM中，从而获取分类结果。⑦计算初代种群的适应度值。⑧将初代种群的适应度值输入到PSO 算法中，更新个体的速度和位置。⑨将经过PSO算法更新的种群输入到GA 中，经过交叉算子和变异算子，得到新种群。⑩返回步骤④，计算新种群的适应度值。⑪判断是否满足判定条件，若满足，则输出SVM 参数和特征数；若不满足，则继续对种群进行处理，直至满足判定条件为止，从而得到最终结果。

2 试验过程

为了验证Relief-PGS 算法的有效性，应将特征子集的个数和SVM参数一起编码到PSO-GA染色体中，在对SVM 参数进行优化的同时，对所有特征子集的个数进行同步优化。试验时需要统一对数据和参数进行处理。

2.1 数据预处理

为提高SVM 分类的准确率，对需要分类的数据样本进行归一化处理，将其分为训练样本和测试样本，进行后续的分类处理。

2.2 参数选择方法

对PSO-GA 算法的核参数进行优化，设置算法的迭代次数为50、种群规模为30、个体长度为2，通过适应度值计算得到GA 中交叉和变异的概率，PSO中的ω是基于适应度值自适应计算出的。

统一设置适应度函数，见式（3）。

式中：we1 为训练样本识别结果的权重；we2 为测试样本识别结果的权重（其中，we1+we2=1。样本不平衡可能导致模型的预测能力下降。经多次试验，通过调节样本权重，将we1 分别设为0.10、0.15、0.20、0.30，当we1 为0.15 时，可得到最优结果）；m1为训练样本的总数；m2 为测试样本的总数；nsv1 为训练样本分类正确的结果；nsv2 为测试样本分类正确的结果。fitness越小，表明综合分类的精确度越高。

2.3 模型建立

从每组训练样本中选择优化后的核参数对样本进行新一轮训练，从而获得SVM 分类模型，再通过测试样本来测试模型的分类精度。

Relief-PGS 优化算法主要是为了解决两个问题，即优化后的输入特征子集选择、优化后的核函数参数选择。使用Relief-PGS 优化算法将优化后的征子集个数和SVM 参数一起编码到PSO-GA 染色体中，在对特征子集进行优化的同时，对SVM 参数同步进行优化，最后得到优化后的分类结果。

选取UCI数据库中5种数据集进行试验，所选取数据集的基本信息见表1。

表1 试验数据集的基本信息

利用Relief 算法对获取到的特征数据进行初步筛选，选择与目标类别关联较大的特征，使用PSOGA算法、SVM算法分别对筛选出的特征数据和SVM参数进行优化，从而获得优化后的特征子集。优化的特征子集个数见表2。

表2 优化特征子集个数

利用SVM 分类器对选取的多个优化特征进行分类，并将RBF作为SVM的核函数进行分类。

3 试验结果分析

使用Relief-PGS 优化算法得到分类结果，并将分类结果分别与默认核参数的SVM、使用PSO-GA算法优化参数的SVM（PGS）、使用Relief算法优化特征的SVM（Relief-SVM）这三种不同算法的优化结果进行对比，并评价特征选择方法的优劣，试验结果见表3。

表3 数据集分类结果对比

由表3 可知，Relief-PGS 优化算法的分类准确率最高。通过对这四种算法的分类结果进行对比可知：①对于任意特征数据，使用PGS 优化算法进行参数寻优得到的分类准确率比使用默认参数的SVM 要有所提高，分类准确率平均提高了12%左右。可证明对传统的SVM 中的参数进行寻优，能找到优化后的控制参数，从而提高SVM 分类的准确率；②使用Relief-SVM 优化算法对输入的特征向量进行筛选分类，分类准确率比默认参数的SVM 平均提高了13%左右，从而证明了Relief-SVM 对输入的特征数据集进行筛选和优化，得到优化后的特征子集，可去除一些特征不明显的影响因素，能减少不重要因素对分类结果造成的影响，从而提高分类的准确率；③使用Relief-PGS 优化算法得到的分类准确率最高，分类的准确率基本在85%左右，从而证明了在对特征子集和SVM 参数同步进行优化时，去除不重要的特征，并对参数进行优化，能得到更好的分类效果。

4 结语

本研究提出的Relief-PGS 优化算法可同时优化特征子集和SVM 参数，通过优化特征子集和SVM 参数来提高分类的准确率。与传统的SVM、PGS 算法和Relief-SVM 算法相比，Relief-PGS 算法对图像分类的准确率分别提高了22.53%、6.05%和11.16%，从而证明了图像分类识别的准确性。研究结果证明，Relief-PGS 算法能利用最少特征来获得最高分类精度，能有效提高图像特征选择分类的准确率。