基于模擬退火算法特征選擇軟件的設(shè)計與實(shí)現(xiàn)

王晗，劉維生，李輝，王輝＊

（1.盤錦高級技工學(xué)校，遼寧 盤錦 124000；2.盤錦職業(yè)技術(shù)學(xué)院，遼寧 盤錦 124000）

0 引言

特征選擇是人工智能、模式識別和數(shù)據(jù)挖掘等領(lǐng)域的重要研究問題，在數(shù)字圖像分類、數(shù)字圖像檢索、客戶關(guān)系管理、入侵檢測和基因分析等方面已經(jīng)得到了廣泛應(yīng)用。一般情況下，樣本數(shù)量是有限的，用大量特征來構(gòu)建分類器是不合時宜，此外，特征向量和模式分類器的性能之間并不是線性關(guān)系，當(dāng)特征向量維數(shù)超過一定限度時，將會導(dǎo)致分類器范化能力反而降低，從而正確有效地進(jìn)行特征選擇便成為模式識別中亟待解決的問題，因此，本文設(shè)計了一種基于模擬退火算法特征選擇軟件。

1 特征選擇和模擬退火算法

特征選擇問題主要需要解決兩個方面，一方面是確定特征選擇算法，在允許的時間內(nèi)，以能夠接受的代價找出最小的、最能表達(dá)類別特征的特征參數(shù)組合。另一方面是確定特征評價標(biāo)準(zhǔn)，衡量特征組合是否最優(yōu)，以便確定特征選擇操作的停止條件[1-2]，其算法的基本結(jié)構(gòu)如圖1所示。

圖1 特征選擇算法的基本結(jié)構(gòu)

模擬退火算法（Simulated Annealing Algorithm，簡稱SA）是80年代發(fā)展起來的一種用于求解大規(guī)模優(yōu)化問題的隨機(jī)搜索算法。利用Metropolis準(zhǔn)則并適當(dāng)?shù)乜刂茰囟鹊南陆颠^程實(shí)現(xiàn)模擬退火過程，從而達(dá)到在多項(xiàng)式時間內(nèi)求解近似全局優(yōu)化問題的目標(biāo)。本文將最近鄰分類器的整體識別率作為子集評價函數(shù)，給出了一種基于模擬退火算法與最近鄰分類器識別率的特征選擇方法軟件MATLAB實(shí)現(xiàn)方法。實(shí)踐證明本文算法具有較強(qiáng)的特征參數(shù)篩選能力，能在多項(xiàng)式時間內(nèi)給出問題的近似最優(yōu)解[3-4]。本文特征選擇算法的偽代碼流程圖如圖2所示。

圖2 本文特征選擇算法的偽代碼流程圖

2 基于模擬退火算法特征選擇軟件的MATLAB程序設(shè)計

2.1 函數(shù)程序和軟件使用方法

軟件主函數(shù)為function [MAX_OPT_VALUE,MAX_OPT_POS]=main(Y0,data_sort)，函數(shù)返回值為MAX_OPT_VALUE,MAX_OPT_POS，其中，最優(yōu)組合為MAX_OPT_VALUE，最優(yōu)值為MAX_OPT_POS。Y0代表原始數(shù)據(jù)集合，data_sort代表數(shù)據(jù)類型，可根據(jù)實(shí)際需要自行設(shè)定，或默認(rèn)。軟件子函數(shù)：（1）function Yxin=neighbor2(Yuan,n)為2變換鄰域程序，產(chǎn)生一種鄰域結(jié)構(gòu)；（2）function Yxin=neighbor3(Yuan,n) 為3變換鄰域程序，產(chǎn)生一種鄰域結(jié)構(gòu)；（3）function T0= Setting_initial_temp(Yuan,X0,n,data_sort)為設(shè)置初始溫度函數(shù)，設(shè)置初始溫度T0，n是參數(shù)的總個數(shù)，也稱為問題的規(guī)模，X0是初始接受率。（4）function [MAX_K_CLASS_END1,CLASS_END_MIN1]= K_neigbor_Final (test_para,data_sort)為最近鄰分類器函數(shù)[5-6]。

軟件使用方法如下：（1）將文件置于MATLAB軟件默認(rèn)調(diào)用函數(shù)目錄中；（2）打開MATLAB程序，在命令窗口中，分別給Y0和data_sort賦初始值；（3）在命令窗口中，輸入“[MAX_OPT_VALUE, MAX_OPT_POS]=main(Y0,data_sort)；”即可運(yùn)行程序。待彈出窗口后，程序結(jié)束，在命令窗口中，顯示程序運(yùn)行時間、最優(yōu)組合為MAX_OPT_VALUE、最優(yōu)值為MAX_OPT_POS、起始溫度和終止溫度等程序運(yùn)行結(jié)果信息[7-8]。

2.2 主函數(shù)程序程序代碼

3 結(jié)語

本文使用MATLAB語言設(shè)計了基于模擬退火算法和和最近鄰類器整體識別率特征選擇軟件，給出了軟件算法在MATLAB開發(fā)平臺上程序的源代碼。該軟件可應(yīng)用于人工智能、模式識別、智能控制等相關(guān)研究領(lǐng)域，對于給定的樣本數(shù)據(jù)集合，該軟件能夠直接應(yīng)用特征度量中的準(zhǔn)確性度量(分類器整體識別率)，能夠較直接地評價特征參數(shù)組合的優(yōu)劣，再通過結(jié)合優(yōu)化的模擬退火算法使用，能夠確保該軟件最終收斂到近似全局最優(yōu)解。技術(shù)特點(diǎn)：該程序用戶使用方便靈活，輸入樣本數(shù)據(jù)格式兼容范圍廣，輸出為最優(yōu)組合和最優(yōu)值及其他相關(guān)參數(shù)。較同類軟件，該程序運(yùn)行速度較快、移植性、開放性好，程序執(zhí)行效率較高，調(diào)試方便，并預(yù)留了程序升級接口，能夠解決人工智能和模式識別特征分析問題的需求，同時能夠滿足電子信息技術(shù)類專業(yè)課程與科研實(shí)驗(yàn)的需要。實(shí)踐表明，該軟件所求解的質(zhì)量優(yōu)于模式識別中傳統(tǒng)的特征選擇方法，具備良好的噪聲容忍性，具有一定的工程實(shí)用價值。