基于改進(jìn)遺傳算法的數(shù)據(jù)特征分類

李靜

摘 要： 針對傳統(tǒng)遺傳算法在數(shù)據(jù)特征分類過程中容易陷入局部最佳解，分類結(jié)果識別率以及準(zhǔn)確率較低的問題，提出基于改進(jìn)遺傳算法的數(shù)據(jù)特征分類方法。采用模擬退火法對遺傳算法實施改進(jìn)，遺傳算法經(jīng)過設(shè)置參數(shù)、適應(yīng)度函數(shù)的設(shè)計、選擇策略、交叉策略以及終止條件等過程得到粗糙數(shù)據(jù)特征分類結(jié)果。采用模擬退火算法通過概率突跳特性在溫度下降時隨機(jī)獲取目標(biāo)函數(shù)的全局最優(yōu)解，基于Meteopolis準(zhǔn)則提高算法局部尋優(yōu)效率，通過模擬退火算法對遺傳算法的交叉概率與變異概率的選擇過程實施改進(jìn)，獲取高精度的數(shù)據(jù)特征分類結(jié)果。實驗結(jié)果表明，所提方法數(shù)據(jù)特征分類識別率以及準(zhǔn)確率高，分類耗時低。

關(guān)鍵詞： 改進(jìn)遺傳算法； 數(shù)據(jù)特征分類； 模擬退火； 局部尋優(yōu)； Meteopolis準(zhǔn)則； 概率突跳特性

中圖分類號： TN911?34； TP391 文獻(xiàn)標(biāo)識碼： 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 引 言

伴隨信息時代的到來，社會各領(lǐng)域、各行業(yè)的數(shù)據(jù)規(guī)模增長迅速。數(shù)據(jù)大規(guī)模的擴(kuò)張造成數(shù)據(jù)冗余、無效的狀況，一定程度上降低了相關(guān)行業(yè)的工作效率，數(shù)據(jù)集快速有效的進(jìn)行分類提取成為研究的重點議題[1]。因此大量的數(shù)據(jù)特征分類算法應(yīng)運而生。傳統(tǒng)遺傳算法進(jìn)行數(shù)據(jù)特征分類過程中容易陷入局部最佳解，在準(zhǔn)確獲取數(shù)據(jù)特征方面能力較差、且存在時間復(fù)雜度較高的缺陷。因此，提出基于改進(jìn)遺傳算法的數(shù)據(jù)特征分類方法，其采用模擬退火算法對遺傳算法實施改進(jìn)，提高數(shù)據(jù)特征分類的精度以及效果。

1 基于改進(jìn)遺傳算法的數(shù)據(jù)特征分類

1.1 編碼與解碼

令數(shù)據(jù)集以個體的形式存在，并代表一個特征子集，經(jīng)過編碼獲取到包含401個實數(shù)值元素的向量，各個實數(shù)值表示相應(yīng)的基因，原始特征集的索引就是由各個基因組成。編碼的逆向過程被稱作解碼，這一過程是基于索引重組最佳個體特征子集[2]。編碼的選擇極大程度上決定了算法的性能與效率，主要原因是在編碼機(jī)制相應(yīng)的碼空間上實施遺傳算法的優(yōu)化步驟。

1.2 適應(yīng)度函數(shù)的設(shè)計

基于數(shù)據(jù)特征選擇問題通過類可分離性判據(jù)計算出個體的適應(yīng)度函數(shù)，用獲取的函數(shù)衡量個體的優(yōu)劣。最佳數(shù)據(jù)特征子集的選取主要決定性因素是適度函數(shù)的設(shè)計，其選取結(jié)果對分類器的運行時間和分類起到一定的決定作用。

基本遺傳算法對數(shù)據(jù)特征子集質(zhì)量的評價是通過線性判別式分析器的經(jīng)驗分類錯誤率與后驗概率的線性組合[ec+ep]實現(xiàn)的[3?4]。適應(yīng)度表示如下：

[f=ec+ep] （1）

式中：線性判別式分析分類器的經(jīng)驗分類錯誤率用[ec]表示；后驗概率用[ep]表示。

2 基于模擬退火遺傳算法的數(shù)據(jù)特征選擇方法

2.1 模擬退火算法

模擬退火算法的主要內(nèi)容是：

1） 搜索空間[Ω]。即狀態(tài)空間，搜索空間由可行解的集合組成，一個可行解用一個狀態(tài)[X]表示。

2） 能量函數(shù)[fX]。需要實施優(yōu)化計算的目標(biāo)函數(shù)就是能量函數(shù)[fX]，想要獲取的最優(yōu)解就是該函數(shù)的最低點[5]。

3） 冷卻進(jìn)度表[Tt]。[T0]表示特定的高溫狀態(tài)，從這一溫度逐漸向低溫轉(zhuǎn)變過程的降溫管理表即冷卻進(jìn)度表。若[Tt]代表時刻[t]的溫度，那么式（2）描述了經(jīng)典模擬退火算法的降溫方式：

[Tt=T0lg1+t] （2）

經(jīng)過該公式的計算可以確保模擬退火算法收斂與全局最低點。

若獲取的新解更優(yōu)則采用新解作為當(dāng)前解；若獲取的新解較差，通過概率[p]采用較差的解轉(zhuǎn)換成新的當(dāng)前解。這兩點好處都要歸功于Meteopolis準(zhǔn)則。在Meteopolis準(zhǔn)則的支持下，既可以保證模擬退火算法局部尋優(yōu)的效率[6]，又能阻止陷入局部最優(yōu)的狀況。

2.2 數(shù)據(jù)特征選擇

各個個體通過二進(jìn)制的編碼方式處理數(shù)據(jù)特征選擇問題。當(dāng)個體長度[l=10]時，則表示存在10個原始特征，個體中的不同基因與相應(yīng)次序的特征是對應(yīng)關(guān)系[7?8]，也就是某個基因?qū)?yīng)的特征被采納時該基因是1；若相應(yīng)的特征未被采納時基因是0。

模擬退火遺傳算法實施數(shù)據(jù)特征選擇過程是：

1） 規(guī)劃初始參數(shù)：設(shè)置數(shù)據(jù)特征種群數(shù)量以及最高繁殖代數(shù)是[n]和[Tmax]，設(shè)置[Pc]，[Pm]表示交叉概率和變異概率，[T0]，[k]表示開始發(fā)生退火的溫度和溫度降低系數(shù)[9?10]。設(shè)置[T0=200]，[k=0.97]，[Pc=0.4]，[Pm=0.015]。

2） 獲取種群中不同的個體的適應(yīng)度值，通過存儲最優(yōu)解的方式對個體實施適應(yīng)度拉伸，具體操作是：

[f′=expf-fmaxTi] （3）

式中，拉伸后的適應(yīng)度值用[f′]描述。通過輪盤采集手段采集最佳個體，再對個體實施隨機(jī)配對[9]。

3） 實施循環(huán)運算時依據(jù)[t=0]模擬退火遺傳算法完成相關(guān)分析，對模擬退火算法中的最少新解接收次數(shù)進(jìn)行設(shè)置，即該遺傳算法中的退火代數(shù)。

4） 若當(dāng)前繁殖代數(shù)符合[T

3 實驗分析

3.1 實驗數(shù)據(jù)準(zhǔn)備

實驗采用KDD99數(shù)據(jù)集，其包含模擬美國空軍局域網(wǎng)中獲取的9個星期的網(wǎng)絡(luò)連接數(shù)據(jù)，7個星期、[5×106]條左右連接記錄構(gòu)成了訓(xùn)練數(shù)據(jù)集，2個星期、[2×106]條左右連接記錄構(gòu)成測試數(shù)據(jù)集，每一記錄具有41個特征。由于KDD99數(shù)據(jù)集包含海量數(shù)據(jù)，給該實驗造成一定難度，通過對數(shù)據(jù)及實施取樣的做法刪減數(shù)據(jù)量，緩解了算法驗證的難度?；谶@一方式對數(shù)量龐大的訓(xùn)練數(shù)據(jù)集、測試數(shù)據(jù)集實施隨機(jī)刪減操作，將最后留下的數(shù)據(jù)重新組合，獲取最終實驗所用的包含11 927條數(shù)據(jù)的訓(xùn)練數(shù)據(jù)子集，以及包含24 015條數(shù)據(jù)的測試數(shù)據(jù)子集。

3.2 實驗結(jié)果分析

為了驗證本文方法存在較高數(shù)據(jù)特征分類準(zhǔn)確率和效率，采用三種方法分別對訓(xùn)練集和測試集實施分類過程中的特征選擇時間以及分類準(zhǔn)確率進(jìn)行統(tǒng)計，結(jié)果如表1所示。

分析表1可得，在分類準(zhǔn)確率方面，對于訓(xùn)練集與測試集本文方法獲取的特征子集作為分類樣本的正確率分別達(dá)到97.1%，97.7%，遠(yuǎn)超于其他兩種方法的準(zhǔn)確率；在特征選擇時間方面，對于訓(xùn)練集與測試集本文方法獲取的特征子集的時間分別是0.21 s與0.37 s，明顯比其他兩種方法花費的時間短，同時獲取全局最優(yōu)解的情況下所需的時間較少。實驗結(jié)果表明，本文方法在數(shù)據(jù)特征分類方面具有較高的正確率且在選擇時間方面存在優(yōu)勢。

為了驗證本文方法分類后的數(shù)據(jù)特征的識別率和分類效果，分別采用本文方法、基本遺傳方法以及Relife方法對實驗設(shè)置的訓(xùn)練數(shù)據(jù)子集實施數(shù)據(jù)特征分類，獲取不同數(shù)據(jù)特征數(shù)量情況。三種方法分類的數(shù)據(jù)特征識別率情況如圖1所示。

分析圖1可得，由于采用Relife方法獲取的數(shù)據(jù)特征分類結(jié)果相似性較大，存在分類不明顯的狀況以及識別率低的問題，獲取的數(shù)據(jù)特征子集保留了冗余特征，導(dǎo)致其分類結(jié)果最差。從圖1中曲線走向可以看出，采用基本遺傳方法獲取的數(shù)據(jù)特征分類結(jié)果識別率比Relife方法高，且采用本文方法獲取的數(shù)據(jù)特征分類結(jié)果識別率比遺傳方法高。實驗結(jié)果表明，本文方法的數(shù)據(jù)特征分類結(jié)果具有較高的識別率，數(shù)據(jù)特征分類性能較高。

為驗證本文方法對非平衡數(shù)據(jù)集的分類性能，實驗引入10個具有代表性的非平衡數(shù)據(jù)集展開研究。該非平衡數(shù)據(jù)集的詳細(xì)信息如表2所示。其介紹了數(shù)據(jù)集名稱（Dataset）、樣本數(shù)量（#Ex.）、屬性個數(shù)（#Atts.）、少數(shù)類以及多數(shù)類占全部樣本的比重（%min，%maj）和不平衡率（IR）等信息。

分析圖2可得，本文方法的折線均在其他兩種算法之上，從少數(shù)分類的性能方面分析，本文方法在10個數(shù)據(jù)上均獲得了最大的[F-measure]值，平均結(jié)果比Borderline?SMOTE+C4.5方法提高3.1%，比SMOTE+C4.5方法平均提高6.8%。分析圖3可得，從整體非均衡數(shù)據(jù)的分類性能方面來看，本文方法在9個數(shù)據(jù)集上均取得了獲取了最大的[G-mean]值，平均結(jié)果比Borderline?SMOTE+C4.5方法提高2.3%，比SMOTE+C4.5方法平均提高5.6%。實驗結(jié)果表明，本文方法對于非均衡數(shù)據(jù)集的少數(shù)分類與整體分類均具有較高的分類性能。

4 結(jié) 論

本文提出的基于改進(jìn)遺傳算法的數(shù)據(jù)特征分類方法，在數(shù)據(jù)特征分類方面具有準(zhǔn)確率高、花費時間少等優(yōu)勢，取得了令人滿意的效果。

參考文獻(xiàn)

[1] 高雪笛，周麗娟，張樹東，等.基于改進(jìn)遺傳算法的測試數(shù)據(jù)自動生成的研究[J].計算機(jī)科學(xué)，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ìn)遺傳算法與文化基因多標(biāo)記聚類研究[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ìn)遺傳算法的路徑選擇算法及仿真實現(xiàn)[J].系統(tǒng)仿真學(xué)報，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ìn)遺傳算法的快速自動組卷算法研究[J].計算機(jī)應(yīng)用研究，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ìn)遺傳算法的實際成本結(jié)轉(zhuǎn)方法[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] 楊景明，顧佳琪，閆曉瑩，等.基于改進(jìn)遺傳算法優(yōu)化BP網(wǎng)絡(luò)的軋制力預(yù)測研究[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ìn)遺傳算法的交通流量小波網(wǎng)絡(luò)預(yù)測[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），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] 丁漢卿，王旭陽，葛彤.基于改進(jìn)遺傳算法的ROV推進(jìn)器伺服系統(tǒng)辨識[J].哈爾濱工程大學(xué)學(xué)報，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.