元啟發式搜索策略在構造模糊分類系統中的應用

鄭曉月

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

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

1 模式分類的基礎——模糊規則

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

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

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

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

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

圖1 目標分類器結構

2 基于模擬退火的模糊分類系統

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

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

圖2 SAFCS過程和Metropolis過程

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

其中NCP（Rj）是通過模糊if-then規則 Rj正確分類的訓練模式的個數。

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

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

刪除:類的某個if-then規則是從當前規則集中抽取出來的,被抽取的概率由下式決定:

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

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

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

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

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

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

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

3 試驗結果

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

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

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

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

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

表1 7種算法關于6個UCI數據集在訓練和測試模式下的分類精度

4 結束語

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

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

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