李静

摘 要： 针对传统遗传算法在数据特征分类过程中容易陷入局部最佳解，分类结果识别率以及准确率较低的问题，提出基于改进遗传算法的数据特征分类方法。采用模拟退火法对遗传算法实施改进，遗传算法经过设置参数、适应度函数的设计、选择策略、交叉策略以及终止条件等过程得到粗糙数据特征分类结果。采用模拟退火算法通过概率突跳特性在温度下降时随机获取目标函数的全局最优解，基于Meteopolis准则提高算法局部寻优效率，通过模拟退火算法对遗传算法的交叉概率与变异概率的选择过程实施改进，获取高精度的数据特征分类结果。实验结果表明，所提方法数据特征分类识别率以及准确率高，分类耗时低。

关键词： 改进遗传算法； 数据特征分类； 模拟退火； 局部寻优； Meteopolis准则； 概率突跳特性

中图分类号： TN911?34； TP391 文献标识码： A 文章编号： 1004?373X（2018）14?0166?04

Data feature classification based on improved genetic algorithm

LI Jing1，2

（1. Chongqing Institute of Engineering， Chongqing 400056， China；

2. Chongqing Engineering Technology Research Center of Digital Film & Television and New Media， Chongqing 400056， China）

Abstract： As the traditional genetic algorithms may easily fall into the local optimal solution， and has low recognition rate and accuracy rate of classification results during the process of data feature classification， a method of data feature classification based on improved genetic algorithm is proposed. The simulated annealing method is adopted to improve the genetic algorithm which experiences the processes such as parameter setting， fitness function design， selection strategy， crossover strategy， and termination condition， so as to obtain the rough classification result of data features. The simulated annealing algorithm is adopted to randomly obtain the global optimal solution of the objective function by using the probability abrupt?jump feature when the temperature falls， the local optimizing efficiency of the algorithm is improved based on the Meteopolis criterion， and the selection process for crossover probability and mutation probability of the genetic algorithm is improved by means of the simulated annealing algorithm， so as to obtain high?accurate classification result of data features. The experimental results show that the proposed method has high recognition rate and accuracy rate of data feature classification and low classification time consumption.

Keywords： improved genetic algorithm； data feature classification； simulated annealing； local optimization； Meteopolis criterion； probability abrupt?jump feature

0 引 言

伴随信息时代的到来，社会各领域、各行业的数据规模增长迅速。数据大规模的扩张造成数据冗余、无效的状况，一定程度上降低了相关行业的工作效率，数据集快速有效的进行分类提取成为研究的重点议题[1]。因此大量的数据特征分类算法应运而生。传统遗传算法进行数据特征分类过程中容易陷入局部最佳解，在准确获取数据特征方面能力较差、且存在时间复杂度较高的缺陷。因此，提出基于改进遗传算法的数据特征分类方法，其采用模拟退火算法对遗传算法实施改进，提高数据特征分类的精度以及效果。

1 基于改进遗传算法的数据特征分类

1.1 编码与解码

令数据集以个体的形式存在，并代表一个特征子集，经过编码获取到包含401个实数值元素的向量，各个实数值表示相应的基因，原始特征集的索引就是由各个基因组成。编码的逆向过程被称作解码，这一过程是基于索引重组最佳个体特征子集[2]。编码的选择极大程度上决定了算法的性能与效率，主要原因是在编码机制相应的码空间上实施遗传算法的优化步骤。

1.2 适应度函数的设计

基于数据特征选择问题通过类可分离性判据计算出个体的适应度函数，用获取的函数衡量个体的优劣。最佳数据特征子集的选取主要决定性因素是适度函数的设计，其选取结果对分类器的运行时间和分类起到一定的决定作用。

基本遗传算法对数据特征子集质量的评价是通过线性判别式分析器的经验分类错误率与后验概率的线性组合[ec+ep]实现的[3?4]。适应度表示如下：

[f=ec+ep] （1）

式中：线性判别式分析分类器的经验分类错误率用[ec]表示；后验概率用[ep]表示。

2 基于模拟退火遗传算法的数据特征选择方法

2.1 模拟退火算法

模拟退火算法的主要内容是：

1） 搜索空间[Ω]。即状态空间，搜索空间由可行解的集合组成，一个可行解用一个状态[X]表示。

2） 能量函数[fX]。需要实施优化计算的目标函数就是能量函数[fX]，想要获取的最优解就是该函数的最低点[5]。

3） 冷却进度表[Tt]。[T0]表示特定的高温状态，从这一温度逐渐向低温转变过程的降温管理表即冷却进度表。若[Tt]代表时刻[t]的温度，那么式（2）描述了经典模拟退火算法的降温方式：

[Tt=T0lg1+t] （2）

经过该公式的计算可以确保模拟退火算法收敛与全局最低点。

若获取的新解更优则采用新解作为当前解；若获取的新解较差，通过概率[p]采用较差的解转换成新的当前解。这两点好处都要归功于Meteopolis准则。在Meteopolis准则的支持下，既可以保证模拟退火算法局部寻优的效率[6]，又能阻止陷入局部最优的状况。

2.2 数据特征选择

各个个体通过二进制的编码方式处理数据特征选择问题。当个体长度[l=10]时，则表示存在10个原始特征，个体中的不同基因与相应次序的特征是对应关系[7?8]，也就是某个基因对应的特征被采纳时该基因是1；若相应的特征未被采纳时基因是0。

模拟退火遗传算法实施数据特征选择过程是：

1） 规划初始参数：设置数据特征种群数量以及最高繁殖代数是[n]和[Tmax]，设置[Pc]，[Pm]表示交叉概率和变异概率，[T0]，[k]表示开始发生退火的温度和温度降低系数[9?10]。设置[T0=200]，[k=0.97]，[Pc=0.4]，[Pm=0.015]。

2） 获取种群中不同的个体的适应度值，通过存储最优解的方式对个体实施适应度拉伸，具体操作是：

[f′=expf-fmaxTi] （3）

式中，拉伸后的适应度值用[f′]描述。通过轮盘采集手段采集最佳个体，再对个体实施随机配对[9]。

3） 实施循环运算时依据[t=0]模拟退火遗传算法完成相关分析，对模拟退火算法中的最少新解接收次数进行设置，即该遗传算法中的退火代数。

4） 若当前繁殖代数符合[T

3 实验分析

3.1 实验数据准备

实验采用KDD99数据集，其包含模拟美国空军局域网中获取的9个星期的网络连接数据，7个星期、[5×106]条左右连接記录构成了训练数据集，2个星期、[2×106]条左右连接记录构成测试数据集，每一记录具有41个特征。由于KDD99数据集包含海量数据，给该实验造成一定难度，通过对数据及实施取样的做法删减数据量，缓解了算法验证的难度。基于这一方式对数量庞大的训练数据集、测试数据集实施随机删减操作，将最后留下的数据重新组合，获取最终实验所用的包含11 927条数据的训练数据子集，以及包含24 015条数据的测试数据子集。

3.2 实验结果分析

为了验证本文方法存在较高数据特征分类准确率和效率，采用三种方法分别对训练集和测试集实施分类过程中的特征选择时间以及分类准确率进行统计，结果如表1所示。

分析表1可得，在分类准确率方面，对于训练集与测试集本文方法获取的特征子集作为分类样本的正确率分别达到97.1%，97.7%，远超于其他两种方法的准确率；在特征选择时间方面，对于训练集与测试集本文方法获取的特征子集的时间分别是0.21 s与0.37 s，明显比其他两种方法花费的时间短，同时获取全局最优解的情况下所需的时间较少。实验结果表明，本文方法在数据特征分类方面具有较高的正确率且在选择时间方面存在优势。

为了验证本文方法分类后的数据特征的识别率和分类效果，分别采用本文方法、基本遗传方法以及Relife方法对实验设置的训练数据子集实施数据特征分类，获取不同数据特征数量情况。三种方法分类的数据特征识别率情况如图1所示。

分析图1可得，由于采用Relife方法获取的数据特征分类结果相似性较大，存在分类不明显的状况以及识别率低的问题，获取的数据特征子集保留了冗余特征，导致其分类结果最差。从图1中曲线走向可以看出，采用基本遗传方法获取的数据特征分类结果识别率比Relife方法高，且采用本文方法获取的数据特征分类结果识别率比遗传方法高。实验结果表明，本文方法的数据特征分类结果具有较高的识别率，数据特征分类性能较高。

为验证本文方法对非平衡数据集的分类性能，实验引入10个具有代表性的非平衡数据集展开研究。该非平衡数据集的详细信息如表2所示。其介绍了数据集名称（Dataset）、样本数量（#Ex.）、属性个数（#Atts.）、少数类以及多数类占全部样本的比重（%min，%maj）和不平衡率（IR）等信息。

分析图2可得，本文方法的折线均在其他两种算法之上，从少数分类的性能方面分析，本文方法在10个数据上均获得了最大的[F-measure]值，平均结果比Borderline?SMOTE+C4.5方法提高3.1%，比SMOTE+C4.5方法平均提高6.8%。分析图3可得，从整体非均衡数据的分类性能方面来看，本文方法在9个数据集上均取得了获取了最大的[G-mean]值，平均结果比Borderline?SMOTE+C4.5方法提高2.3%，比SMOTE+C4.5方法平均提高5.6%。实验结果表明，本文方法对于非均衡数据集的少数分类与整体分类均具有较高的分类性能。

4 结 论

本文提出的基于改进遗传算法的数据特征分类方法，在数据特征分类方面具有准确率高、花费时间少等优势，取得了令人满意的效果。

参考文献

[1] 高雪笛，周丽娟，张树东，等.基于改进遗传算法的测试数据自动生成的研究[J].计算机科学，2017，44（3）：209?214.

GAO Xuedi， ZHOU Lijuan， ZHANG Shudong， et al. Research on test data automatic generation based on improved genetic algorithm [J]. Computer science， 2017， 44（3）： 209?214.

[2] 李彦广，史维峰.改进遗传算法与文化基因多标记聚类研究[J].控制工程，2016，23（8）：1221?1228.

LI Yanguang， SHI Weifeng. Improved genetic algorithm and memetic algorithm based multi?label clustering approach [J]. Control engineering of China， 2016， 23（8）： 1221?1228.

[3] DEVI B R， RAO K N， SETTY S P. Towards better classification using improved genetic algorithm and decision tree for dengue datasets [J]. International journal of applied engineering research， 2015， 10（8）： 20313?20326.

[4] 顾键萍，张明敏，王梅亮.基于改进遗传算法的路径选择算法及仿真实现[J].系统仿真学报，2016，28（8）：1805?1811.

GU Jianping， ZHANG Mingmin， WANG Meiliang. Improved genetic algorithm?based network game path selection and simulation [J]. Journal of system simulation， 2016， 28（8）： 1805?1811.

[5] 陈国彬，张广泉.基于改进遗传算法的快速自动组卷算法研究[J].计算机应用研究，2015，32（10）：2996?2998.

CHEN Guobin， ZHANG Guangquan. New algorithm for intelligent test paper composition based on improved genetic algorithm [J]. Application research of computers， 2015， 32（10）： 2996?2998.

[6] 蒙秋男，娄剑，白雪.基于改进遗传算法的实际成本结转方法[J].管理评论，2016，28（1）：179?190.

MENG Qiunan， LOU Jian， BAI Xue. Carryover for actual cost based on improved genetic algorithm [J]. Management review， 2016， 28（1）： 179?190.

[7] 杨景明，顾佳琪，闫晓莹，等.基于改进遗传算法优化BP网络的轧制力预测研究[J].矿冶工程，2015，35（1）：111?115.

YANG Jingming， GU Jiaqi， YAN Xiaoying， et al. Rolling force prediction based on BP network optimized by an improved genetic algorithm [J]. Mining and metallurgical engineering， 2015， 35（1）： 111?115.

[8] 柴良勇，殷礼胜，甘敏，等.基于改进遗传算法的交通流量小波网络预测[J].合肥工业大学学报（自然科学版），2016，39（7）：900?905.

CHAI Liangyong， YIN Lisheng， GAN Min， et al. Prediction of traffic flow with wavelet network based on improved genetic algorithm [J]. Journal of Hefei University of Technology （Natural science）， 2016， 39（7）： 900?905.

[9] 丁汉卿，王旭阳，葛彤.基于改进遗传算法的ROV推进器伺服系统辨识[J].哈尔滨工程大学学报，2017，38（2）：168?174.

DING Hanqing， WANG Xuyang， GE Tong. Parameter identification of variable displacement of an remote operated vehicle hydraulic thruster based on an improved genetic algorithm [J]. Journal of Harbin Engineering University， 2017， 38（2）： 168?174.

[10] JIANG K， LU J， XIA K. A novel algorithm for imbalance data classification based on genetic algorithm improved SMOTE [J]. Arabian journal for science & engineering， 2016， 41（8）： 3255?3266.