元啟發(fā)式搜索策略在構(gòu)造模糊分類系統(tǒng)中的應(yīng)用

鄭曉月

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

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

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

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

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

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

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

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

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

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

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

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

圖2 SAFCS過程和Metropolis過程

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

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

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

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

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

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

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

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

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

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

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

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

3 試驗結(jié)果

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

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

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

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

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

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

4 結(jié)束語

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

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

[1] 劉偉民,鄭愛云.模擬退火K均值聚類算法及其應(yīng)用研究[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.