用模擬退火方法研究支持向量機(jī)的參數(shù)決定

1、基于模擬退火方法的支持向量機(jī)參數(shù)確定及特征選擇Shih-Wei Lin a,b,*, Zne-Jung Leeb, Shih-Chieh Chen c , Tsung-Yuan Tseng ba Department of Information Management, Chang Gung University, No. 259 Wen- Hwa 1st Road, Kwei-Shan Tao-Yuan 333, Taiwan, ROCb Department of Information Management, Huafan University, No. 1 Huafan Road, T

2、aipei, Taiwan, ROCc Department of Industrial Management, National Taiwan University of Science and Technology, No. 43 Keelung Road, Sec. 4, Taipei, Taiwan, ROCReceived 31 January 2007; received in revised form 6 October 2007; accepted 21 October 2007Available online 26 October 2007摘要支持向量機(jī)是一種新穎的分類法方法

3、，它在許多應(yīng)用中都極具價(jià)值。在支持向量機(jī)的訓(xùn)練過程 中，核參數(shù)設(shè)置及特征選擇對分類準(zhǔn)確率具有顯著的影響。該研究的目的是找到最優(yōu)參數(shù)值， 同時(shí)尋找一個(gè)不會(huì)降低支持向量機(jī)分類準(zhǔn)確率的特征子集。本研究提出了一種用于支持向量機(jī) 中確定參數(shù)和特征選擇的模擬退火方法，命名為SA-SVM為了衡量所提的 SA - SVM方法，從UCI機(jī)器學(xué)習(xí)庫中選用了一些數(shù)據(jù)集，用于計(jì)算分類準(zhǔn)確 率。將所提方法與用于參數(shù)設(shè)置的傳統(tǒng)格搜索方法及其他多種方法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，所提方法的分類準(zhǔn)確率超過了格搜索方法和其他方法。因此， JSA-SVM在支持向量機(jī)的參 數(shù)測定和特征選擇中很有用。關(guān)鍵詞：支持向量機(jī)；模擬退火；參數(shù)

4、測定；特征選擇1引言對分類問題已經(jīng)有了廣泛研究。對于一個(gè)給定的模型參數(shù)值的選擇，像數(shù)據(jù)不完整等眾 多因素可能會(huì)影響分類的成果。以前的分類問題通常是用統(tǒng)計(jì)方法，如物流，回歸或判別分 析等來處理。技術(shù)進(jìn)步導(dǎo)致了解決分類問題的新技術(shù)，包括決策樹，BP神經(jīng)網(wǎng)絡(luò)，粗糙集理論和支持向量機(jī)（SVM）的產(chǎn)生。支持向量機(jī)是首先被Vapnik1開發(fā)的一個(gè)新興的數(shù)據(jù)分類技術(shù)，并已在最近的分類問題 2-9廣泛的應(yīng)用于各個(gè)領(lǐng)域。在支持向量機(jī)中，采用抽樣成本在訓(xùn)練階段產(chǎn)生分類模式。然后，分類是基于訓(xùn)練模式的基礎(chǔ) 上完成的。在建立支持向量機(jī)模型中最大的困難是選擇核函數(shù)及其參數(shù)值。如果參數(shù)值設(shè)置的 不合適，那么分類的Z果將不

5、是最優(yōu)的10。利用分化與整合，低收入和高通過率和數(shù)據(jù)庫的光譜數(shù)據(jù)，對原始數(shù)據(jù)及預(yù)處理的數(shù)據(jù)進(jìn)行分類，得到軸承條件。在復(fù)雜的分類領(lǐng)域，某些功 能可能含有虛假相關(guān)性，它們阻礙數(shù)據(jù)的處理。此外，一些功能可能是多余的，因?yàn)樗麄冄a(bǔ)充 的信息包含在其他功能里。冗余功能會(huì)延長計(jì)算時(shí)間，影響分類精度。因此，在分類過程中必須用最少的功能且快速，準(zhǔn)確，這時(shí)通過使用特征選擇實(shí)現(xiàn)目標(biāo)。特征選擇已用于提高分類性 能，并減少數(shù)據(jù)噪聲11-13。如果沒有特征選擇而采用支持向量機(jī)，那么輸入的空間維數(shù)大，且數(shù)據(jù)不干凈，就會(huì)降 低支持向量機(jī)的功能。因此，需要一個(gè)支持向量機(jī)擁有高效，穩(wěn)定的特征選擇方法，它忽略 嘈雜的，不相關(guān)和冗余

6、數(shù)據(jù)，同時(shí)仍保留判別數(shù)據(jù)的權(quán)力。特征提取采用原始數(shù)據(jù)，以在支 持向量機(jī)分類器中輸入。本研究整合了模擬退火（SA）為基礎(chǔ)支持向量機(jī)的方式來確定最優(yōu)的分類結(jié)果，被稱為 I 模擬退火-支持向量機(jī)（SA-SVM ）,以上提出的的 SA-SVM方法不僅僅可以得到更好的 SVM 參數(shù)值，也找到了特定問題的功能子集，從而最大限度地提高了SVM分類準(zhǔn)確率。這使兩個(gè)分離的最優(yōu)超平面既可采用線性，又可采用非線性分類。|本文的其余部分組織如下：第二部分回顧關(guān)于支持向量機(jī)和特征選擇的相關(guān)文獻(xiàn)，第三 部分對以上提出的模擬退火 -支持向量機(jī)（SA-SVM ）進(jìn)行介紹，旨在改進(jìn)有或者無特征選擇的(3)IM *其中%且對于所

7、有的;=，“用都成立，并有J "（4）二次規(guī)劃可用來解決這個(gè)最大化問題。給定一個(gè)方程滿足最大化方程（3）,則超平面中可以寫成以下形式：其中支持向量點(diǎn)必須滿足等式（2）和。當(dāng)考慮到在約束等式（4）中的擴(kuò)張，超平面 的函數(shù)式可以寫成如下：/ W詞 力&（6）大部分情況下，數(shù)據(jù)是不可線性分離的，因此被映射到更高維的特征空間中。這就意味 著如果數(shù)據(jù)不能在現(xiàn)有的維數(shù)空間中被嚴(yán)格的分離，那么支持向量機(jī)就要把數(shù)據(jù)映射到更高維 的空間中進(jìn)行分離。通過繪制一條非線性曲線，將輸入數(shù)據(jù)映射到高維空間。然后在特征空間中建立這個(gè)超 平面。特征空間向量 工v是建立在核k評價(jià)輸入模式的X ' ,其

8、中）I':/o核函數(shù)之所以可以被應(yīng)用是因?yàn)樗械奶卣飨蛄績H僅產(chǎn)生于點(diǎn)產(chǎn)品中。權(quán)重向量，成為 功能空間的一個(gè)擴(kuò)展，因此不再單獨(dú)對應(yīng)一個(gè)輸入空間向量。這個(gè)決定函數(shù)描述如下：/ jhy咯口 E %、何力中+ ®lxi=sgn1 y 3*小 一t h 獷，” . 這個(gè)二次規(guī)劃方程為：一（8）其中 且對于所有的 都成立，并有（9）在尋找最優(yōu)方法中，幾個(gè)核函數(shù)幫助了支持向量。最常用的函數(shù)是多項(xiàng)式核，徑向基核 和基礎(chǔ)放射核（RBF 17 T9。一般情況下，RBF最常用，因此它可以分類多維數(shù)據(jù)，而不像線 性核函數(shù)那樣。此外，RBF比多項(xiàng)式核有更少的參數(shù)?？傮w來說，RBF與其他核函數(shù)沒有明顯區(qū)

9、別，因此，對于核函數(shù)，RBF是一個(gè)很好的選擇。所以，本研究是在支持向量機(jī)中采用徑向基函數(shù)尋求最優(yōu)解。適應(yīng)于徑向基支持向量的兩個(gè)參數(shù)c和y必須設(shè)置合理，參數(shù)c是懲罰因子，該參數(shù)c的值影響分類結(jié)果。如果 C過大，則在訓(xùn)練階段的分類準(zhǔn)確率非常高，而在試驗(yàn)階段的分類準(zhǔn) 確率則很低；如果c過小，那么分類的準(zhǔn)確率很低，使得模型沒有用處。相比參數(shù)c參數(shù)y在分類結(jié)果上有更大的影響力，因?yàn)樗闹涤绊懺谔卣骺臻g劃分結(jié)果。對于參數(shù)y過多的值將會(huì)導(dǎo)致過度擬合，而不成比例的小值又會(huì)使得擬合結(jié)果偏小20。網(wǎng)絡(luò)搜索13,21是確定參數(shù)C和，的最簡單方法。在搜索中通過對參數(shù)C和參數(shù)y設(shè)置上限和下限，或是跳躍間隔都可以使得搜索

10、的準(zhǔn)確率達(dá)到很高。然而，這種搜索只是本地搜 索，很有可能產(chǎn)生一個(gè)局部最優(yōu)。此外，如何設(shè)置搜索間隔也是一個(gè)問題。太大的搜索間隔會(huì) 浪費(fèi)計(jì)算能力，太小的搜索間隔可能得不到滿意的結(jié)果。為獲得最佳的方法，在支持向量機(jī)中 的參數(shù)目前還在研究之中。除了普遍采用的網(wǎng)絡(luò)搜索技術(shù)，其他的應(yīng)用在支持向量機(jī)中的用于選擇一個(gè)合適的參數(shù) 的方法也在進(jìn)一步提高被改進(jìn)的可能性。這種F-評分方法采用I型和n型的誤差概念統(tǒng)計(jì)方法以及隨機(jī)森林（RF 22。Pai and Hong 23提出了一種結(jié)合遺傳算法（GA和支持向量機(jī)的方法， 他們的模型模仿他們的染色體編碼遺傳算法產(chǎn)生的參數(shù)值設(shè)置為支持向量機(jī)。Pai and Hong24

11、,25還提出了一個(gè)遺傳算法用來得到支持向量機(jī)，并將其應(yīng)用到了實(shí)際的數(shù)據(jù)。然而他們的 做法并不具有地址選擇功能，因此可能會(huì)排除最好的結(jié)果。2.2特征選擇支持向量機(jī)的分類準(zhǔn)確率不僅僅由參數(shù)c和參數(shù)/決定，其他的因素包括特征數(shù)據(jù)集的質(zhì)量也會(huì)有影響。例如，特征之間的相關(guān)性影響分類的結(jié)果；意外的重要特征的消除可能影響 分類的準(zhǔn)確率。此外，一些數(shù)據(jù)集的某些特征可能一點(diǎn)影響也沒有，或者包含一個(gè)高級別的噪 音。祛除這些功能可能提高搜索的準(zhǔn)確率。特征選擇方法可分為過濾器模型和包裝模型26,篩選模型26在調(diào)查其他間接表現(xiàn)的措施上利用統(tǒng)計(jì)技術(shù)，如主成分分析（PCA,因子分析（FA,獨(dú)立成分分析（ICA和判別分析（D

12、A等，這些技術(shù)大部分是基于距離和信息的措施。Chen and Hsieh 27提出了潛在語義分析（LSA和網(wǎng)頁特征選擇（WPFA,這是與支持向量機(jī)技術(shù)相結(jié)合的屏幕特征。Gold et 28等人發(fā)明了貝葉斯支持向量分類器，它為了確定不相關(guān)功能的參數(shù)標(biāo)準(zhǔn)采用超參數(shù)值。Chapelle et 29等人研發(fā)了一種自動(dòng)調(diào)整多個(gè)參數(shù)，并應(yīng)用到主成分獲得支持向量機(jī)的功能。支持向量機(jī)是應(yīng)用在 癌癥基因選擇分類中的一種牛!征選擇方法，這是被Guyon et 30等人稱作的支持向量機(jī)特征消除（SVM-RFE。因此，他們提出了應(yīng)用相關(guān)的方法來消除多余的功能，以提高支持向量機(jī)的特 征消除RFE。擬議的方法不僅減少了分

13、類的數(shù)量，還保持了分類的精度。盡管過濾模型的分類 速度很快，但它可能不會(huì)產(chǎn)生最優(yōu)特征子集26。特征選擇的最簡單形式是包裝模型，它按照表現(xiàn)的準(zhǔn)確率進(jìn)行分類。一些研究者認(rèn)為， 如果最高的預(yù)測精度得到了最大限度的減少錯(cuò)誤率和分類均衡的所有功能，包裝模型最合適不 過了。分類器的最大目的是最大化的提高分類的準(zhǔn)確性。通過分類的特征應(yīng)用選擇最優(yōu)的特 征。該包裝模型通常使用元啟發(fā)式辦法幫助尋找最優(yōu)特征子集。雖然元啟發(fā)式的方法是緩慢 的，但是它能夠找到附近最優(yōu)的特征子集。Neumaan33等人觀察到特征選擇是監(jiān)督模式分類問題上的一個(gè)顯著的組合優(yōu)化問題。并 在不同的凸函數(shù)基礎(chǔ)上提出了額外的正規(guī)化和嵌入式非線性選擇

14、方法，這是對于非凸不斷優(yōu)化問題的一個(gè)框架。Jack and Nandi 34 and Shon 35在篩選數(shù)據(jù)集的特征中應(yīng)用了遺傳算法，這 個(gè)選擇數(shù)據(jù)集的特征被應(yīng)用到了支持向量機(jī)中的分類測試。Zhang 16等人提出了一種基于遺傳算法的方法來獲得一個(gè)在支持向量機(jī)監(jiān)測狀態(tài)的有利子集。然而，他們的方法沒有解決支持 向量機(jī)的參數(shù)設(shè)置問題，因此可能會(huì)排除最優(yōu)的結(jié)果。Samanta36等人研發(fā)了一種遺傳算法用來改變支持向量機(jī)特征選擇中的徑向?qū)挾然鶇?shù)，不過，由于他們的方法只搜索支持向量機(jī)的 徑向基寬度，它也可能排除最佳參數(shù)的設(shè)定。據(jù)我們所知，很少有人能夠同時(shí)考慮到支持向量 機(jī)中特征選擇和最佳參數(shù)的設(shè)定。

15、3支持向量機(jī)-模擬退火方法模擬退火算法（SA是一個(gè)全局搜索算法，它首先是被Metropolis 37等人提出的，稍后又被Kirkpatrick 38等人推廣。模擬退火算法借助于最基本的冶金技術(shù)。隨著溫度的逐漸減少，分子慢慢結(jié)晶成低能量狀態(tài)。只要金屬能夠加熱到足夠高的初始溫度，而且它的冷卻速 度足夠的慢，所有的晶粒就能夠達(dá)到最低的溫度。由 Metropolis 37等人提出的模擬退火算法 不僅能改善搜索的結(jié)果，而且能避免得到局部最優(yōu)結(jié)果。類似于金屬的冷卻，它的冷卻過程 使得模擬退火銜接搜索結(jié)果，進(jìn)而達(dá)到最優(yōu)解。本研究提出的“隱藏和尋求-模擬退火”算法，首先是被 Romeijn 39,40等人研發(fā)

16、的， 主要用于搜尋支持向量機(jī)的參數(shù)值，并確定相應(yīng)的功能子集?！半[藏和尋求-模擬退火”算法，可以處理連續(xù)變量，使其能在可行界的范圍內(nèi)和收斂范圍內(nèi)找到最優(yōu)的解決方案?！半[藏和尋求-模擬退火”算法比傳統(tǒng)的模擬退火算法使用更少的參數(shù)。這些約束和目標(biāo)函數(shù)可以 是不可微的，且可行域可以是凸的，甚至可以是斷開的。該算法是目前唯一的一個(gè)解決算 法。通過一個(gè)隨機(jī)向量，它選擇一個(gè)可行域內(nèi)的點(diǎn)作為搜索過程的下一個(gè)迭代點(diǎn)，“隱藏和尋求-模擬退火”算法不同于傳統(tǒng)的模擬退火迭代算法，因?yàn)樗a(chǎn)生的下一個(gè)迭代數(shù)據(jù)是在所 有的解決方案地區(qū)之中，而傳統(tǒng)的迭代方法產(chǎn)生的下一個(gè)迭代數(shù)據(jù)是在臨區(qū)域?！半[藏和尋求-模擬退火”算法要求Me

17、tropolis為下一解決方案選擇驗(yàn)收規(guī)則和一個(gè)合適的模擬退火過 程。不管如何使溫度迅速下降到零，當(dāng)前的解決方案總是可能得到一個(gè)最近的全局最優(yōu)解。 “隱藏和尋求-模擬退火”算法與傳統(tǒng)的模擬退火算法最大的不同在于每當(dāng)找到一個(gè)解決方案 時(shí)，前者總是立即執(zhí)行模擬退火，而不必等待電流退火周期的結(jié)束。但是在傳統(tǒng)的模擬退火 算法中，它會(huì)減少跳躍退火的次數(shù)，而是在每一個(gè)退火周期中會(huì)隨著溫度慢慢降低，通過逐 漸減少跳躍周期，慢慢收斂到全局最優(yōu)解。因此“隱藏和尋求-模擬退火”算法比傳統(tǒng)的模擬退火算法能夠更迅速的得到全局最優(yōu)解。圖 1展示了 “隱藏和尋求-模擬退火”算法。X Current solutionFea

18、sible regionPossible chosen solution圖1隱藏和尋求-模擬退火”算法。本研究提出了一種基于模擬退火的算法來尋找支持向量機(jī)中的待定參數(shù)和特征選擇。稱為支持 向量-模擬退火。為了尋找支持向量機(jī)中的最佳參數(shù)，支持向量機(jī)-模擬退火算法的目標(biāo)函數(shù)是為了最大化的提高對檢測數(shù)據(jù)集的搜索精確率。這相當(dāng)于尋求一個(gè)最大解決方案的優(yōu)化問題。在解決最大化的問題時(shí)，如果下一個(gè)解決方案提高了目標(biāo)函數(shù)的值，那么它就可接受作為當(dāng)前 可行的解決方案，并作為下一個(gè)解決方案是搜索出發(fā)點(diǎn)。如果下一個(gè)解決方案比當(dāng)前的解決方 案的分類精確率低，那么就應(yīng)用 Metropolis規(guī)則來決定是否采用下一個(gè)解決

19、方案。在沒有特征選擇的情況下，兩個(gè)基本的決策變量C和y是必要的。對于特征選擇，如果要決定n個(gè)特征，那么要建立 2 + n個(gè)決策變量。每個(gè)參數(shù)的值賦為0或是1.如果一個(gè)參數(shù)的值為0,那么相當(dāng)于它的功能沒有被選擇，相反，如果一個(gè)參數(shù)的值為1,則相當(dāng)于選擇了它的功能。圖2描述了此解決方案。122+12+依gc gr gfl的gcE"g丁gHi: Fea hire n is selecied or notFig. 2. Solution representation.如圖3所示，支持向量機(jī)-模擬退火算法的程序可簡述如下。首先，將當(dāng)前的溫度T設(shè)為T口，這是一個(gè)很大的數(shù)。最初的解決方案中，X是隨

20、即產(chǎn)生的。在每次迭代中，以 X為出發(fā)點(diǎn)，產(chǎn)生一個(gè)隨機(jī)向量作為下一個(gè)可行方案丫。讓目標(biāo)X作為X的目標(biāo)函數(shù)的值（例如，可以采用支持向量分類準(zhǔn)確率的值給定X） ,代表目標(biāo)X和目標(biāo)Y之間的差值，即A£= r-1。如果a£<0, X是當(dāng)前的解決方案，Y是下一個(gè)解決方案，那么用 Y代替X的概 率取決于e't T o這個(gè)概率的獲得是通過生成一個(gè)隨機(jī)數(shù)7 E恒小，如果Y < 就用Y代替x；如果 g 0則用y代替x的概率為i ；如果目標(biāo)A 一七"，就讓,平 ，之后溫度立即 下降。支持向量 一模擬退火的終止迭代次數(shù)就達(dá)到了。對于支持向量的最優(yōu)參數(shù)和最有益的功 能子

21、集，就由力決定。Stcpl. Emd an initial feasible solution A'D - the number of decision variables;7'0- INFINITY； T-Tdenom 1.0/(0 9 °)-1.0;，a.2,+加2 the 99 percentile point of the 比 distribution with D degive of freedom,Step?. Repeat/hmea L - Generate a random direction at current iteration point A*

22、;K= Find an feasible point on tine segmentL by random;AB- obj(r)-objCV)if CAE <0) accp = e7/r;(accp 1,0;Generate a random variable u nnifniTnly distributed in ，1);if (uaeep) x-y,if(0bjW>obj(At) 口皿%。,衣1 - objW./cmp -A： 1 g 一穴2y癡M,r= 2yg5)由 2,% =X, Stqj3. Output Ihe uplimHl圖3支持向量-模擬退火的過程支持向量-模擬退

23、火需要一個(gè)初始可行的解決方案。如果初始的解決方案產(chǎn)生于一個(gè)隨機(jī)方式，那么以后的迭代方案要進(jìn)一步完善，因?yàn)槌跏嫉慕鉀Q方案并不是很好。為了避免這種問題，我們的研究采用了貪婪方法的概念。參數(shù) c和y的值區(qū)域分為六個(gè)區(qū)域。區(qū)域的邊界作為初始方案的可能解決方案，產(chǎn)生的49個(gè)可能方案的測試如圖 4所示。在這49個(gè)解決方案總最好的作為支持向量一模擬退火的初始解決方案。如果不同的解決方案有相同的分類準(zhǔn)確率，那 么選擇參數(shù)值c最小的，作為初始解決方案，如果c的值再相同，那么就選擇y的值最小的。圖4貪婪算法4實(shí)驗(yàn)結(jié)果以上提出的支持向量一模才比退火算法實(shí)在具有IV 3.0 GHz CPU, 512 MB RAM ,

24、和XP操作系統(tǒng)的英特爾奔騰筆記本上，通過VC+6.0軟件實(shí)現(xiàn)的。下面的數(shù)據(jù)集，是取自于 UCI機(jī)器學(xué)習(xí)庫，被用來評估以上提出的支持向量一模擬退火算法的表現(xiàn)。具體因素有Bupa live ,Cleveland heart, Pima, Ionosphere, , Breast cancer , Boston housing, , Australian , Sonar, , Vowel, Vehicle and Glass 41,圖表1描述了這些數(shù)據(jù)集的特征。Table 1Dataset from ihc UCT reptilianDaktselNunibtr ul classes Number

25、H inniiceE Niituber of leaturesBupii live7 b-3456Clcvcl mid bcitrl229613Pi in u2768*Ionosphere35134Bruitsi LLinccr76831。Bobbin hiHisinji101213Aus Lrali lid265315Sonin220860Vo*-E1152810,chick484618自2"9縮放功能是用來阻止在小的數(shù)據(jù)范圍內(nèi)產(chǎn)生大的數(shù)據(jù)變化，以及避免計(jì)算過程中的困難。實(shí)驗(yàn)結(jié)果表明，縮放后的特征值提高了支持向量的準(zhǔn)確性。每個(gè)特征值的范圍可以通過公式（10）擴(kuò)展到線性范圍-I。或者

26、是0 +11,其中V表示原始值，I表示換算值，I'代表 了特征值的上界，卬代表了特征值的下界。本研究規(guī)模特征值的范圍是。Atl.V. - ,W/(10)由Salzberg提出的K倍方法被用在此實(shí)驗(yàn)中，其中 K=1042,43。圖5說明了系統(tǒng)構(gòu) 架。因?yàn)橐陨咸岢龅闹С窒蛄?模擬退火算法是不確定的，該解決方案可能不等同于獲得了相同的數(shù)據(jù)，因此，擬議的支持向量-模擬退火算法要對每個(gè)數(shù)據(jù)集執(zhí)行五次來計(jì)算平均分類準(zhǔn)確率。在沒有特征選擇的原始實(shí)3擬議的支持向量-模擬退火算法的參數(shù)值設(shè)置如下：Liter=300;為一個(gè)足夠大的數(shù)，C = 1,35 000,7二0.0001,32。在有特征選擇時(shí)，被應(yīng)

27、用的特征選擇的數(shù)量是通過支持向量-模擬退火算法得到的。盡管 c和y的值是不變的，但是由于選擇的特征不同，那么得到的準(zhǔn)確率也是不同的。因此貪婪算法不能被用來搜索初始解， 初始解是通過隨機(jī)產(chǎn)生的。由于該解決方案的空間是由特征的數(shù)量決定的，因此它比無特征選 擇時(shí)大很多，迭代次數(shù)也必須要增加用來尋找更多的解決方案。所以 Liter要增加到1000。沒有特征選擇的擬議的支持向量-模擬退火算法所彳#到的結(jié)果與Fung和Mangasarian 44通過幾個(gè)數(shù)據(jù)集提出的結(jié)果進(jìn)行了比較。他們采用牛頓支持向量機(jī)，常規(guī)的支持向量機(jī)，和沒 有特征選擇的拉格朗日支持向量機(jī)測試數(shù)據(jù)集。表2對他們的結(jié)果進(jìn)行了比較。擬議的支

28、持向量-模擬退火算法結(jié)果中的5個(gè)平均準(zhǔn)確率超過了Fung和Mangasarian提出的算法準(zhǔn)確率。該擬議的支持向量-模擬退火算法似乎彳#到了最相應(yīng)的C和丫的值，在不同的數(shù)據(jù)集中產(chǎn)生了最高的數(shù)據(jù)分類準(zhǔn)確率。Table 2Classification accuracy rales obtained by S/X-SVM without feature selection, NSVM. SVM. and LSVM approaches 44Data seiSA-SVMNSVMSVMLSVMIonosphere97.50a89.8088.3089.80Bupa liver80.8 la70.2069.

29、3070.20Cleveland heart87.97a86.3085.9086.30PimaSOW77.0077.1()77.00Boston housing99.90a86.6085.8086.60a The highest classification accuracy rate among approaches.圖5基于模擬退火的算法來尋找支持向量機(jī)中的待定參數(shù)和特征選擇的系統(tǒng)構(gòu)架此外，沒有特征選擇的擬議的支持向量-模擬退火算法還與 Liao 17等人提出的在支持向 量機(jī)中應(yīng)用三個(gè)核函數(shù)，一個(gè)高斯核函數(shù)，一個(gè)多項(xiàng)式核函數(shù)，一個(gè)乙狀結(jié)腸核函數(shù)來測試從UCI中得到的幾個(gè)數(shù)據(jù)集進(jìn)行了比較。表

30、3對這些結(jié)果進(jìn)行了展示，寸I示擬議的支持向量-模擬退火算法得到的結(jié)果優(yōu)于Liao 17等人提出的算法得到的結(jié)果。Table 3Classificaiion uccurac rates obtained bv SA*SVM without feature selection and appmuchusLiao ci uL 17Dai asciSA-SVMGaussian kc me 1Po vtiLHiiialkernelSigmoid kumelIonosphere97.5(r93.1292 J 594.37Bupa liver80.8P71.3572.S573.17Cleveland hea

31、rt8Z97tt85.1 84 E 785J7cancer97,95963796.3796.23The highest classification accuracy rate aniDQg approaches.沒有特征選擇的擬議的支持向量-模擬退火算法之后和來自UCI的11個(gè)數(shù)據(jù)集的表現(xiàn)進(jìn)行了比較，實(shí)驗(yàn)結(jié)果與網(wǎng)格搜索13,21的結(jié)果相比如表4所示。沒有特征選擇的擬議的支持向量-模擬退火算法在所有情況的檢測中都優(yōu)于網(wǎng)格搜索。每個(gè)分類的數(shù)據(jù)準(zhǔn)確率在具有特征選 擇后都有了明顯的改善。這個(gè)結(jié)果揭示了在具有較少的特征時(shí)，好的搜索結(jié)果也是可以得到 的，這就意味著，有些特征在搜索中是多余的或微不足道的。

32、顯然，在不降低分類精度的情況 下，支持向量-模擬退火算法可以同時(shí)找到最優(yōu)參數(shù)和一個(gè)功能子集。為了驗(yàn)證擬議的支持向量-模擬退火算法的有效性，我們用一對測試數(shù)據(jù)t來比較擬議的支持向量-模擬退火算法（有特征選擇和沒有特征選擇）與網(wǎng)格搜索算法。如表 4所示，只有 一個(gè)數(shù)據(jù)集中，沒有特征選擇的擬議的支持向量-模擬退火算法的表現(xiàn)沒有明顯的好于網(wǎng)格搜索。而帶有特征選擇的擬議的支持向量-模擬退火算法在所有的數(shù)據(jù)集中的表現(xiàn)都明顯好于網(wǎng)格搜索，因?yàn)樗械臄?shù)據(jù)集中的P值都小于0.05.表5比較了有特征選擇和沒有特征選擇的支持向量-模擬退火算法的準(zhǔn)確率。由于所有數(shù)據(jù)集中的顯著性差異得來的P值都小于0.05,顯然，有特

33、征選擇的支持向量-模擬退火算法要優(yōu)于沒有特征選擇的支持向量 -模擬退火算法。表 5同時(shí)還展示了有特征選擇和沒有特征選擇 的支持向量一模擬退火算法的計(jì)算時(shí)間。有特征選擇的支持向量-模擬退火算法的Liter的值大于沒有特征選擇的支持向量 -模擬退火算法的，所以前者的計(jì)算時(shí)間要大于后者的。為了展示支持向量-模擬退火算法選擇了多少特征，以及哪些特征被選擇了，表 6展示了 為Bupa live and Vowel數(shù)據(jù)集所選擇的 10個(gè)特征。在 Bupa live and Vowel數(shù)據(jù)集中原始的特 征的數(shù)量是6和10,分析結(jié)果表明，并非所有的特征在特征選擇后都被用到支持向量-模擬退火算法模型中。此外，就

34、像表 5所示，特征選擇提高了分類準(zhǔn)確率。Table 6Feature selecied for Bupa live and Vowel daiasel by SA-SVM approachNo.Selected features forSelected featuresBupa live datasetfor Vowel dataset1234567891()123,4,51,235.6,8,9123,4,512356.9234,5124,5,6,9123,4,5123.4.7.8,9123,4,5123,4,5,6,7123,4,5124,5,6,7,8,91,23,4,51,3,4,5,6

35、,7,891.234,5123.4,6,81,34,51,3,4,5,6,7,89123,4,5123,4,5,6,8,9Table 4Experinienlal result of the proposed SA-SVM and grid searchDataset SA-SVM with feature selection(2) SA-SVM without feature selection(3se;Breast cancer99.38,97.9596Cleveland heart93.33a87.9781Boston housing100.00a99.9099Ionosphere99.

36、07*97.5093Australian92.19.88.34X4Bupa live83.13*80.8171Pima82.22-80.1976Sonar95.99需91.8587Vowell(M).00a99.2798Vehicle90.1個(gè)88.7684Glass8Z93978.387()* The highest classincaiion accuracy rate anx)ng approaches. Confidcncc level a =0.05.Table 5CuiiLpuLatioinil re Mil csf the proposed SA-SVM m ith and y

37、iU】jul fedture m: led ionDansylWith femure selectionNuiiiber(>nriginul kdiurvsNumber ofsek'ck'd feaimsAveideLilfuracy nn< 1% ITime iBrvasl cancerW4.90 ± 1 233993g ± 0.520461Ckveland Cait139.34 ± 2.6269333 士 4.674皿Husion IlULJMEL!136 62 ±0.835UMkOO i 0WOloDLiphcn?342

38、2.36 ±5.01799.07 ± 0.7309 二ustru Juin15106( ±2.45792J9± 3229UU7JBuplive64.50 ± 133383.13 ± 6.5022155/Pinm85.86 ± 1.17082.22 士 3.5474038。Sorur804«. IS ± 5.534V5.99 ± 3 X9912/Vowel106.4() ±0.990HX).00 ± 0.00060 1VehicleIS153fl ±216790J4&

39、#177;22101236JGlass95.76 ±1.118X7.93 ± 7.309C)n(idence level a = ().05. 士 denotes the standurcl dcviylit>nr5結(jié)論和未來研究工作本研究提出了一種基于模擬退火方法，它可以對連續(xù)決策變量進(jìn)行搜索，以優(yōu)化支持向 量機(jī)的參數(shù)值，并獲得有用的特征子集。然后，該最優(yōu)特征子集被用于訓(xùn)練和測試，以取得分 類的最優(yōu)輸出。所取得結(jié)果與其他方法所得結(jié)果對比表明，所提 SA-SVM方法提高了分類準(zhǔn) 確率。通過在實(shí)驗(yàn)中應(yīng)用特征選擇，SA-SVM方法被用于剔除無用的或不顯著的特征，從而有效地

40、尋找更好的參數(shù)值。反過來，該過程改善了分類的總體輸出效果。本研究的實(shí)驗(yàn)結(jié)果是在徑向基核函數(shù)基礎(chǔ)上取得的。然而，其他核參數(shù)也可以通過同樣 的方法加以優(yōu)化。實(shí)驗(yàn)結(jié)果是在UCI數(shù)據(jù)集上得到的，其他的公共數(shù)據(jù)集和實(shí)際問題在將來也可以用于對該方法進(jìn)行驗(yàn)證和推廣。NSC96-2416-H-211-002 。致謝作者感謝中國國家科學(xué)臺(tái)灣委員會(huì)對本研究的支持，合同號是 參考文獻(xiàn)1 V.N. Vapnik, The Nature of Statistical Learning Theory, Springer, New York, 1995.2 L.J. Cao, F.E.H. Tay, Support vec

41、tor machine with adaptive parameters in financial time series forecasting, IEEE Trans. Neural Netw. 14 (6 (2003 15061518.3 J. Diederich, A. Al-Ajmi, P. Yellowlees, Ex-ray: data mining and mental health, Appl. Soft Comput. 7 (2007 923 C28.4 I. Ko kai, A. LO rincz, Fast adapting value estimation-based

42、 hybrid architecture for searching the world-wide web, Appl. Soft Comput. 2 (2002 1123.5 J.-Z. Liang, SVM multi-classifier and web document classification, in: Proceedings of the Third International Conference on Machine Learning and Cybernetics, vol. 3, 2004, pp. 1347 V351.6 V. Mitra, C.-J. Wang, S

43、. Banerjee, Text classification: a least square support vector machine approach, Appl. Soft Comput. 7(2007 908 414.7 J. Ng, S. Gong, Composite support vector machines for detection of faces across views and pose estimation, Image Vision Comput. 20 (2002359368.8 8 K.-S. Shin, T.-S. Lee, H.-J. Kim, An

44、 application of support vector machines in bankruptcy prediction model, Expert Syst. Appl. 28(2005 127135.9 G. Valentini, Gene expression data analysis of human lymphoma using support vector machines and output coding ensembles, Artif. Intell. Med. 26 (2002 281W04.10 S.S. Keerthi, C.-J. Lin, Asympto

45、tic behaviors of support vector machines with Gaussian kernel, Neural Comput. 15 (2003 1667 1689.11 K. Lee, V. Estivill-Castro, Feature extraction and gating techniques for ultrasonic shaft signal classification, Appl. Soft Comput. 7 (2007 156165.12 G. Valentini, M. Muselli, F. Ruffino, Cancer recog

46、nition with bagged ensembles of support vector machines, Neurocomputing 56 (2004 461W66.13 J. Wang, X. Wu, C. Zhang, Support vector machines based on k-means clustering for real-time business intelligence systems, Int. J. Business Intell. Data Mining 1 (2005 5444.14 C.J.C. Burgers, A tutorial on sup

47、port vector machines for pattern recognition, Data Mining Knowledge Discov. 2 (1998 121 V67.15 B. SchO lk opf, A.J. Smola, Learning with Kernels, MIT, London, 2002.16 L. Zhang, L.B. Jack, A.K. Nandi, Fault detection using genetic programming, Mech. Syst. Signal Process. 19 (2005 271 289.17 Y. Liao,

48、S.-C. Fang, H.L.W. Nuttle, A neural network model with bounded-weights for pattern classification, Comput. Operat. Res. 31 (2004 14111426.18 H.-T. Lin, C.-J. Lin, A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods, Technical Report, University of National Taiw

49、an, Department of Computer Science and Information Engineering, March 2003, pp. 1W2.19 K.R. Mu ller, S. Mike, G. Ra tsch, KTsuda, B. Scho lkopf, An introduction to kernel-based learning algorithms, IEEE Trans. Neural Netw. 12 (2001181201.20 M. Pardo, G. Sberveglieri, Classification of electronic nos

50、e data with support vector machines, Sens. Actuators B: Chem. 107 (2005 730 737.21 C.-W. Hsu, C.-C. Chang, C.-J. Lin, A practical guide to support vector classification. Technical Report, University of National Taiwan, Department of Computer Science and Information Engineering, July 2003, pp. 112.22

51、 Y. Wei, C.-J. Lin, Feature Extraction, Foundations and Applications, Springer, 2005.23 P.-F. Pai, W.-C. Hong, Forecasting regional electricity load based on recurrent support vector machines with genetic algorithms, Electric Power Syst. Res. 74 (2005 417Y25.24 P.-F. Pai, W.-C. Hong, Support vector

52、machines with simulated annealing algorithms in electricity load forecasting, Energy Conversion Manage. 46 (2005 26692688.25 P.-F. Pai, W.-C. Hong, Software reliability forecasting by support vector machines with simulated annealing algorithms, J. Syst. Softw. 79 (2006747755.26 H. Liu, H. Motoda, Fe

53、ature Selection for Knowledge Discovery and Data Mining, Kluwer Academic, Boston, 1998.27 R.-C. Chen, C.-H. Hsieh, Web page classification based on a support vector machine using a weighed vote schema, Expert Syst. Appl. 31 (2006 427 W35.28 C. Gold, A. Holub, P. Sollich, Bayesian approach to feature

54、 selection and parameter tuning for support vector machine classifiers, Neural Netw. 18(2005 693701.29 O. Chapelle, V. Vapnik, O. Bousquet, S. Mukherjee, Choosing multiple parameters for support vector machines, Mach. Learn. 46 (2002 131159.30 I. Guyon, J. Weston, S. Barnhill, V. Vapnik, Gene select

55、ion for cancer classification using support vector machines, Mach. Learn. 46 (2002 389 Y22.31 Z.-X. Xie, Q.-H. Hu, D.-R. Yu, Improved feature selection algorithm based on SVM and correlation, Lecture Notes Comput. Sci. 3971 (2006 1373 T380.32 R. Kohavi, G.H. John, Wrappers for feature subset selecti

56、on, Artif. Intell. 97 (1997 273W24.33 J. Neumann, C. Schnorr, G. Steidl, Combined SVM-based feature selection and classification, Mach. Learn. 61 (2005 129 150.34 L.B. Jack, A.K. Nandi, Fault detection using support vector machines and artificial neural networks, augmented by genetic algorithms, Mech. Syst. Signal Process. 16 (2002 373390.35 T. Shon, Y. Kim, C. Lee, J. Moon, A machine learning framework for network anomaly detection usi