鄭曉月

（商丘師范學(xué)院計(jì)算機(jī)科學(xué)系,河南商丘 476000）

模擬退火是受金屬加熱后冷卻過程啟發(fā)得來的一種迭代搜索算法,這種算法能多次考察搜索空間從而找到問題的全局優(yōu)化解[1]。搜索過程中算法依賴一種稱為“溫度”的參數(shù),冷卻進(jìn)度表則用來控制溫度使之逐漸降低,當(dāng)溫度高時(shí),算法的執(zhí)行方式類似于隨機(jī)搜索。當(dāng)溫度達(dá)到零點(diǎn)時(shí)算法的執(zhí)行方式類似于貪婪爬山算法。如果這個(gè)過程獲得足夠的搜索時(shí)間,將會(huì)有很高的概率得到一個(gè)全局優(yōu)化解。在數(shù)據(jù)挖掘中,模擬退火（SA）被用于特征選取、分類和分簇。利用模擬退火元啟發(fā)式搜索策略開發(fā)出一個(gè)模糊分類器對新的實(shí)例進(jìn)行分類。模擬退火算法力圖利用SA元啟發(fā)式搜索策略在分類問題中抽取模糊分類規(guī)則并找到模糊if-then規(guī)則中的優(yōu)化集。這種基于模擬退火的模糊分類系統(tǒng)叫做SAFCS。

1 模式分類的基礎(chǔ)——模糊規(guī)則

設(shè)模式分類問題在n維模式空間中是一個(gè)具有連續(xù)屬性值的c-類問題,并給定c-類問題m個(gè)實(shí)矢量xp=（xp1,xp2,…,xpn）,p=1,2,…,m作為這c個(gè)類的訓(xùn)練模式空間。由于樣本空間為[0,1]n,所以每種模式的屬性值都有 xpi∈[0,1],其中i=1,2,…,n。在計(jì)算機(jī)模擬過程中,將每個(gè)數(shù)據(jù)集的屬性值規(guī)格化在單位閉區(qū)間[0,1]內(nèi)。并使用下面的模糊if-then規(guī)則:

規(guī)則 Rj:若 x1屬于 Aj1,x2屬于 Aj2,…,xn屬于Ajn,則類 Cj有CF=CFj。

其中Rj代表第j個(gè)if-then規(guī)則,Aj1,…,Ajn是單位閉區(qū)間[0,1]上的前件模糊集。Cj是后件類,CFj是ifthen規(guī)則 Rj的確定級別,Cj和CFj的確定在參考文獻(xiàn)[2]中有詳細(xì)的論述。在 n維模式分類問題中if-then規(guī)則總共有6n個(gè)。模糊分類器系統(tǒng)是利用較高的分類性能尋找具有較小規(guī)模的模糊if-then規(guī)則集。模糊分類器如圖1所示,模糊分類系統(tǒng)的任務(wù)是生成前件模糊集的組合,從而產(chǎn)生具有高分類性能的規(guī)則集S。當(dāng)規(guī)則集S確定時(shí),它的優(yōu)勝規(guī)則Rj*會(huì)分離出輸入模式xp=（xp1,xp2,…,xpn）,這個(gè)模式由下式?jīng)Q定:

也就是說,這個(gè)優(yōu)勝規(guī)則具有兼容性和確定級別的最大乘積。同時(shí),如果沒有模糊if-then規(guī)則與輸入樣本 xp兼容,則分類無效。

SAFCS算法由c個(gè)分類器構(gòu)成,每個(gè)分類器包含一個(gè)具有相同標(biāo)志的規(guī)則子集,且其性能的改善有利于提高整體分類率。算法的核心是了解每個(gè)類從而提高主分類器的整體精確度。所以在分類問題中,針對其中一個(gè)類SAFCS會(huì)迭代多次。

圖1 目標(biāo)分類器結(jié)構(gòu)

2 基于模擬退火的模糊分類系統(tǒng)

總的來說,基于SA的模糊分類算法的步驟為:初始化;評估;微擾;接受;迭代;降溫;終止。

圖2左框給出了具體算法程序。這個(gè)模糊分類器系統(tǒng)的每一步都可以如下描述:

圖2 SAFCS過程和Metropolis過程

（1）初始化。Ninit表示初始集中模糊規(guī)則的個(gè)數(shù)。為產(chǎn)生初始規(guī)則集,可通過某種方法隨機(jī)指定每個(gè)模糊規(guī)則的前件模糊集,產(chǎn)生Ninit個(gè)模糊規(guī)則。在生成作為初始化規(guī)則集Sinit的Ninit個(gè)模糊規(guī)則后,通過參考文獻(xiàn)[2]描述的方法從訓(xùn)練空間中指明每個(gè)規(guī)則的結(jié)果類和確定級別。模糊if-then規(guī)則的適應(yīng)度可通過下面的適應(yīng)度函數(shù)得到:

其中NCP（Rj）是通過模糊if-then規(guī)則 Rj正確分類的訓(xùn)練模式的個(gè)數(shù)。

（3）微擾。規(guī)則集的微擾過程使用3個(gè)函數(shù):更改、刪除和生成保證了SAFCS算法在狀態(tài)空間中向好的（或者說優(yōu)的）方向變化。這3個(gè)函數(shù)具體描述如下:

更改:規(guī)則集中的某一個(gè)規(guī)則是被隨機(jī)選取的,該規(guī)則通過改變其前件的一個(gè)或多個(gè)語言值獲得修改。由于問題的搜索空間比較復(fù)雜,改變過多語言值可能導(dǎo)致偏離全局優(yōu)化的方向。因此,將選定規(guī)則語言值的變化概率設(shè)定為一個(gè)較小的全特征百分比。若新規(guī)則的結(jié)果類等于原規(guī)則的結(jié)果類,則用新規(guī)則替換選定的規(guī)則,否則重復(fù)運(yùn)行更改函數(shù)。

刪除:類的某個(gè)if-then規(guī)則是從當(dāng)前規(guī)則集中抽取出來的,被抽取的概率由下式?jīng)Q定:

其中 fitnessmax（SClassh）和 fitnessmin（SClassh）分別是類Class h規(guī)則集中具有最大和最小適切值的if-then規(guī)則,具有較小適切值的if-then規(guī)則被抽取的概率較高。如果某規(guī)則被抽取,則相應(yīng)將其從規(guī)則集中刪除。

生成:為了產(chǎn)生一個(gè)新的規(guī)則,從類的當(dāng)前規(guī)則集中抽取出一個(gè)模糊if-then規(guī)則,隨機(jī)改變其前件的某些語言值。這里,比“更改”函數(shù)中修改的語言值的個(gè)數(shù)多。若新規(guī)則的結(jié)果類等于被抽取規(guī)則的結(jié)果類,則將新規(guī)則添加進(jìn)規(guī)則集中,否則重新運(yùn)行生成函數(shù)。

算法的核心是在溫度 T狀態(tài)下模擬退火的Metropolis過程,每次調(diào)用這個(gè)過程,以上3種函數(shù)之一會(huì)被隨機(jī)選擇并在原來規(guī)則集Scurrent的基礎(chǔ)上生成新的規(guī)則集Snew。

（4）接受。如果新規(guī)則集的評估函數(shù)值小于當(dāng)前規(guī)則集Scurrent的評估函數(shù)值,則通過設(shè)置Snew=Scurrent接受這個(gè)新規(guī)則集。如果新規(guī)則集的評估函數(shù)值小于最佳規(guī)則集Sbest,同樣用Snew替換Sbest。反之,如果新規(guī)則集的評估函數(shù)值大于當(dāng)前規(guī)則集的評估函數(shù)值,Metropolis過程會(huì)基于某個(gè)隨機(jī)概率接受這個(gè)新規(guī)則集（圖2右框4-7行）。隨機(jī)數(shù)產(chǎn)生范圍為0-1。如果隨機(jī)數(shù)小于公式（1）給定的值則立刻接受新規(guī)則集。

（5）迭代。在每個(gè)溫度值Metropolis過程都被調(diào)用k次,k為常數(shù)。當(dāng)然如果修改算法,調(diào)用次數(shù)在每個(gè)溫度值也可以動(dòng)態(tài)改變。高溫度時(shí),迭代次數(shù)少;低溫度時(shí)要進(jìn)行多次迭代從而使局部優(yōu)化進(jìn)行得更徹底。這一點(diǎn)由參數(shù) β控制,β設(shè)置為1（圖2左框第11行）。

（6）冷卻。冷卻速度參數(shù)α用來更新溫度值。溫度應(yīng)該慢慢降低,這樣算法可以徹底探索規(guī)則集的狀態(tài)空間。用計(jì)算機(jī)模擬時(shí),α取值為0.9（圖2左框第12行）。

（7）終止。當(dāng)溫度降到最低時(shí),算法終止。用計(jì)算機(jī)模擬時(shí),設(shè)置 Tmin為0.01。

3 試驗(yàn)結(jié)果

為了評估算法的性能,抽取了某校機(jī)器學(xué)習(xí)知識庫中的8個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),這6個(gè)數(shù)據(jù)集是:酒類識別數(shù)據(jù)（wine）、鳶尾屬植物數(shù)據(jù)庫（iris）、信用許可（cra）、某地區(qū)工業(yè)中勞動(dòng)談判的最終結(jié)果（lab）、某地區(qū)糖尿病數(shù)據(jù)庫（pima）、波形（wave）。

在計(jì)算機(jī)模擬過程中,數(shù)據(jù)集中的所有屬性值都被線性轉(zhuǎn)換成單位區(qū)間。那樣,就能象對待在 n維單位立方[0,1]n中的模式分類問題一樣處理每一個(gè)數(shù)據(jù)集。將10折交叉驗(yàn)證技術(shù)（10-CV）[4]在每個(gè)數(shù)據(jù)集的不同部分上應(yīng)用10次。這樣在10-CV中數(shù)據(jù)集就被分成了大小相等的10個(gè)子集。其中9個(gè)子集用來作為訓(xùn)練樣本,1個(gè)作為測試樣本。

在訓(xùn)練和測試模式下分別運(yùn)行10折交叉驗(yàn)證技術(shù)10次后,計(jì)算SAFCS算法的平均分類率,即SAFCS算法在兩種模式下都執(zhí)行了100次（10×10-CV）。并將結(jié)果與C4.5、IBk、Na?ve Bayes、LIBSVM 、XCS、GAssist 6個(gè)著名分類算法的運(yùn)行結(jié)果進(jìn)行比較。

表1列出了不同分類算法在6個(gè)數(shù)據(jù)集上的分類結(jié)果,每行的上下部分分別表示訓(xùn)練集上的分類精度和測試集上的分類精度,其他幾個(gè)分類算法的運(yùn)行結(jié)果來自于參考文獻(xiàn)[5]。

SAFCS算法在尋找優(yōu)化規(guī)則集時(shí)有2個(gè)主要特征:在分類問題的狀態(tài)空間中探索和研究新的和未知的ifthen規(guī)則集;從計(jì)算過程的中間解中開發(fā)使用先前已發(fā)現(xiàn)的知識,尋找更好的規(guī)則集。這兩個(gè)特征由溫度參數(shù)控制,幫助SAFCS在高維分類問題中獲得良好的結(jié)果。

表1 7種算法關(guān)于6個(gè)UCI數(shù)據(jù)集在訓(xùn)練和測試模式下的分類精度

4 結(jié)束語

基于SAFCS的一個(gè)重要特性是其主分類器包含若干分屬不同類的c-分類器。算法能深入了解每個(gè)類的特點(diǎn),從而考慮整體分類率。因此,基于模糊算法的模擬退火法在分類問題上對于每個(gè)類都會(huì)進(jìn)行重復(fù)操作。

算法的初始化過程用來生成模糊if-then規(guī)則。SAFCS的微擾函數(shù)保證能生成有效的規(guī)則集。為了做到這一點(diǎn),更改和生成操作結(jié)束后,每個(gè)規(guī)則集的結(jié)果類就會(huì)被確定下來。如果這個(gè)類和父類相同則接收生成的規(guī)則,否則重復(fù)微擾函數(shù)。試驗(yàn)結(jié)果顯示,SAFCS對測試樣本數(shù)據(jù)操作時(shí)結(jié)果更好。原因是經(jīng)過充分的初始化、微擾、評估和接收合適的中間結(jié)果,SAFCS有效地探索了分類問題的搜索空間,并盡量擺脫局部優(yōu)化的桎梏,收斂為全局優(yōu)化。

[1] 劉偉民,鄭愛云.模擬退火K均值聚類算法及其應(yīng)用研究[J].微計(jì)算機(jī)信息,2008,（7）:182-184.

[2] H Ishibuchi,K Nozaki,H Tanaka.Distributed representation of fuzzy rules and its application to pattern classification[J].Fuzzy Sets Syst,1992,52（1）:21-32.

[3] H Youssef,S M Sait,H Adiche.Evolutionary algorithms,simulated annealing and tabu search:a comparative study[J].Eng.Appl.Artif.Intell,2001,14（2）:167-181.

[4] S M Weiss.Computer Systems that Learn[M].San Mateo:Morgan Kaufmann Publishers,1991.

[5] J Bacardit.Pittsburgh Genetics-Based Machine Learning in the Data Mining era:Representation,Generalization,and Run-time[D].Barcelona:Ramon Llull University,2004.