粒子群和遺傳算法優化支持向量機的破產預測

楊鐘瑾

YANG Zhongjin

廣東財經大學 信息學院，廣州 510320

School of Information Science and Technology,Guangdong University of Finance and Economics,Guangzhou 510320,China

1 引言

破產預測能讓人類做出理性的決策，從而最小化風險造成的損失。破產預測廣泛應用于各行各業，尤其在學術界和商界備受關注。但是，現實世界所面對的破產預測問題經常是復雜多變和難于捉摸。由于統計模型方法固有的缺陷，因此難于勝任破產預測。與傳統的統計模型方法相比，雖然神經網絡[1]對破產預測的效果有所改進，但是神經網絡具有以下的缺點：（1）難以構建合適的預測模型；（2）常常陷入局部極小值；（3）經驗風險最小化原則的運用不能確保良好的推廣能力；（4）不容易正確選定訓練集的大小。

支持向量機[2]是一種新型的破產預測智能技術，不僅備受矚目，而且日益盛行。支持向量機以統計學習理論為基礎，與神經網絡明顯不同之處在于運用結構風險最小化原理，克服了神經網絡容易陷入局部極小值的問題，提高了推廣能力。同時，在運用支持向量機構建預測模型時，在正確選定了核函數[3]的基礎上，只需選擇最優參數。因此，相對神經網絡而言，支持向量機更簡易快捷。目前，啟發式優化技術[4-5]得到眾多研究者的追捧，其中粒子群優化[6]和遺傳算法[7]等最為流行，它們都具有并行處理的特征。與其他的優化技術相比，粒子群優化有許多優點：減少內存、快速運算、容易與其他優化技術集成和易于實現。同樣，遺傳算法也具有以下優點：有效地掃描和探測復雜空間、避免陷入局部極小值、出色地平衡效果與效率之間的關系和不乏靈活性。

Shin等人運用支持向量機預測公司破產，所得預測準確率超過神經網絡與其他統計預測方法[8]。Min和Lee采用柵格搜索技術尋找支持向量機最優的核函數參數值，并在此基礎上構建破產預測模型，實驗結果顯示支持向量機的預測準確率高于神經網絡與其他統計預測方法[9]。Min等人集成遺傳算法與支持向量機來預測破產，采用遺傳算法優化特征子集和支持向量機的參數，預測結果表明這種方法優于其他沒有優化方法[10]。楊和蒙采用支持向量機在商業銀行構建破產預測模型，并將結果與BP神經網絡相比，研究結果表明支持向量機優于BP神經網絡[11]。Wu等人采用真值遺傳算法優化支持向量機的參數，同時構建優化的破產預測模型，實驗結果顯示這種模型的預測準確率強于神經網絡和常規支持向量機[12]。魯和徐建立基于支持向量機的企業破產分析預測系統模型，實證表明該模型具有良好的預測能力和較強的實用性[13]。Gao等人揉合K-最近鄰與支持向量機對公司破產進行預測，這種預測方法比傳統支持向量機有更好的分類性能[14]。Zhong等人運用支持向量機構建破產預測模型，實驗結果顯示該種模型性能優于傳統統計模型[15]。Yoon和Kwon運用柵格搜索方法尋找支持向量機的最優參數，并建立模型預測小企業的破產，這種引薦模型的預測性能優于其他模型[16]。Chaudhuri和De運用模糊支持向量機預測上市大公司的破產，與其他方法相比，這種方法改進了預測準確率[17]。Moradi等人運用支持向量機預測上市公司的破產，結果顯示該方法的平均預測準確率高于辨別分析方法[18]。

預測準確率取決于支持向量機的推廣能力，支持向量機的推廣能力又深受相關參數選擇所左右。在很多情況下，為某一個問題而選擇最優參數是藝術多于科學，而且這其中經常涉及大量的嘗試和失敗。因此，預測模型的優化經常導致昂貴的過程。本研究將運用粒子群算法和遺傳算法優化支持向量機的參數，構建優化的支持向量機預測模型，采用來自UCI機器學習數據庫[19]的樣本數據并進行歸一化數據預處理，將這些引薦方法與隨意選擇相關參數方法進行比較研究，同時與輸入未經預處理的樣本原值數據方法比較，由此提出有效優化支持向量機的方法，進而加快支持向量機的學習速度和提高支持向量機的推廣性能，從此提高破產預測準確率。

2 支持向量機

支持向量機和核函數方法日愈流行，二者珠聯璧合成為核函數支持向量機[20]，同時成功地在預測領域應用。在模式分類與回歸分析方面，支持向量機基于統計學習理論和運用VC維思想。支持向量機的基本思想是構造一個超平面作為決策面，由此最大化兩類樣本的間隔。核函數具有平滑和相似性度量的作用，支持向量機主要由核函數確定。在特征空間中，選擇不同形式的核函數就會構成不同的支持向量機，因而也構造出不同的超平面。

在預測領域，徑向基核函數是一種常用的核函數，該核函數的表達式如下：

其中，γ是核參數。

在支持向量機的學習過程中，破產公司和非破產公司的樣本數據連續地被輸入，這些輸入數據通過非線性核函數映射到特征空間。在高維特征空間中尋找破產公司和非破產公司樣本之間的最大間隔，由此構造超平面的一個最優分界來增強分類性能。因此，可以運用支持向量機預測破產。

圖1 運用支持向量機和歸一化輸入數據預測破產模型

運用支持向量機預測破產模型如圖1，預測模型從混合樣本數據集中讀取數據，接著歸一化預處理這些數據，隨后已預處理數據被送進輸入空間并轉換為輸入向量。輸入向量經由核函數映射到高維特征空間，在高維特征空間中，通過優化獲得一個超平面來分離破產公司和非破產公司的樣本，從而實現破產預測功能。

3 粒子群算法和遺傳算法

3.1 粒子群算法

粒子群算法是一種新穎且有效的優化智能技術，算法思想來自由個體組成的群體與周邊環境以及個體之間互動行為的啟示。

在求解優化問題時，個體不僅在搜索空間里有確定的位置，而且具有一定的運動速度，這些個體被稱為粒子。根據粒子本身具有最佳性能時所處位置與鄰近全局最優粒子的位置，粒子動態地調整它的狀態。這個迭代過程直到尋獲最優解或是超出了計算限值才終止。在搜索空間里，每個粒子都是一個潛在解，而粒子適應度是評價這些解優劣的標準。粒子適應度計算公式如下：

在此，f(t)為第t回合迭代時當前粒子的適應度，y(t)表示第t回合迭代時當前粒子的實際輸出，d(t)代表第t回合迭代時當前粒子的期望輸出。

3.2 遺傳算法

遺傳算法是一種具有隨機全局搜索性能的優化智能技術，它模擬自然生物進化原理——適者生存，優勝劣汰。遺傳算法根據這個進化原理，將優化問題的求解表示為個體在種群里優勝劣汰的過程，通過對個體進行選擇、交叉和變異等遺傳操作，實現種群中個體一代接一代地進化，最終獲得問題的最優解或滿意解。

選擇操作確定了新個體基因的來源，在每一代中，選擇操作根據種群里個體適應度的評價水平選出優良個體。交叉操作是新個體產生的主要途徑，并且決定遺傳算法的全局搜索性能，交叉操作是將來自父母代的不同個體基因進行交換和重組，由此產生下一代的新個體。變異操作增加了種群變化的途徑，決定局部搜索性能并促進遺傳算法收斂于全局最優。變異操作是依據存在于染色體中某個體基因的變異概率而改變這個基因的值，由此產生新的個體。

4 粒子群算法和遺傳算法優化支持向量機

正則化參數C和核參數γ是支持向量機的重要參數，這兩個參數對支持向量機的預測性能具有深遠的影響。在本研究中，將分別運用粒子群算法和遺傳算法優化正則化參數C和核參數γ，然后運用優化參數的支持向量機預測破產。

4.1 支持向量機參數

參數選擇對支持向量機的推廣能力至關重要，因此錯誤選定參數將極大減弱支持向量機的推廣能力。優化支持向量機模型是指為增強推廣能力而選定最優參數的過程，決定支持向量機模型性能的參數主要是正則化參數C和核參數γ。正則化參數C協調最小學習誤差與最小模型復雜度之間的關系，如果參數C賦值過小，那么就會因為模型過于簡單而引起實踐風險過高；如果參數C賦值過大，那么就會因為模型過于復雜而過度學習。核參數γ隱式定義了從輸入空間到高維特征空間的非線性映射，通常也將這個高水平參數稱為超參數，如果參數γ取值過小，那么就會對上界域產生過大影響。雖然支持向量機目前發展得很好，但其目前尚缺乏結構化方法來實現參數的最優選擇[21]。在實際應用中，這些最優參數的選擇缺乏堅實的理論指導，往往經過多次實驗和錯誤后才能選定。在此，分別通過粒子群算法和遺傳算法優化這些參數。

4.2 粒子群算法優化支持向量機過程

粒子群算法依據以下公式調整每個粒子的速度和位置：

其中，i=1，2，…，m ，d=1，2，…，D ；w 為慣性因子；c1，c2是取值為正的學習因子；r1，r2是取值范圍為[0，1]的隨機數；vid(t+1)和vid(t)分別代表在第(t+1)回合和第t回合迭代時，第i個粒子在第d維度的速度；xid(t+1)和 xid(t)分別代表在第(t+1)回合和第t回合迭代時，第i個粒子在第d維度的位置；pibd(t)表示第t回合迭代時，第i個粒子在第d維度的最佳位置；pgbd(t)表示第t回合迭代時，整個粒子群在第d維度的最佳位置。

運用粒子群算法優化支持向量機參數過程的概要如圖2。

4.3 遺傳算法優化支持向量機過程

圖3描繪了運用遺傳算法優化支持向量機參數過程的概要。

4.4 性能評價

采用預測準確率作為評價支持向量機預測模型性能的指標，同時運用7重交叉校驗方法計算和評價模型的預測準確率，這種校驗方法確保樣本數據集中的每個樣本數據都做并且只做一次檢驗，因此最低程度地減少了因特別選擇訓練子集和檢驗子集所帶來的結果偏差。在此，PCR表示預測準確率，TQ是指檢驗樣本總數，CQ代表被正確預測的檢驗樣本個數。預測準確率的計算公式如下：

5 結果和討論

利用Matlab編寫程序和進行仿真，相關方法在運行Windows XP的個人計算機（AMD Athlon 64 3200+2 GHz processor；4 GB RAM）上實施與測試。

圖2 粒子群優化支持向量機參數算法流程圖

實驗仿真數據源自UCI機器學習數據庫的澳大利亞信用數據集，實驗仿真數據集由383個破產樣本數據與307個非破產樣本數據所構成，這個混合數據集共包含690個樣本數據。在支持向量機的7重交叉校驗仿真實驗中，分別從混合數據集中選取370個破產樣本數據和295個非破產樣本數據作為測試樣本數據，這665個樣本數據首先隨機地分成各自含有95個樣本數據的7個子集。每一重交叉校驗仿真實驗都選取7個子集中的一個子集作為檢驗集，剩下的6個子集共同構成訓練集。最后所得預測準確率是7重交叉校驗預測準確率的平均值。

圖3 遺傳算法優化支持向量機參數算法流程圖

在此，粒子群算法和遺傳算法的相關參數值是根據預測對象與所獲得實驗結果而選擇設置。在運用粒子群算法優化支持向量機參數過程中，粒子維度設置為2，目標粒子適應度設置為0.001，最大迭代回合設置為3，粒子群數目設置為15，學習因子c1與學習因子c2都設置為1.48，最小慣性因子與最大慣性因子分別設置為0.4和0.9。在運用遺傳算法優化支持向量機參數過程中，通過Genetic Algorithm（GA）Toolbox[22]應用軟件解決優化問題。采用二進制字符串編碼形式，遺傳算法的主要參數分別設置為：個體數目等于20，最大代數等于10，變量維數等于2，變量二進制位數等于20，代溝等于0.9。采用隨機全體采樣選擇操作方法，同時采用單點交叉操作方法，并將交叉概率設置為0.7。

在破產預測過程中，預測模型運用二進制支持向量機并通過STPRtool[23]應用軟件實現，這些支持向量機由SVMlight[24]軟件包（5.00版本）[25]所構建，SVMlight軟件包是處理復雜問題的強大優化工具[26]。預測模型的支持向量機采用徑向基核函數。表1給出了每一個預測模型的模型名稱（MN）、輸入數據類型（IDT）、輸入向量個數（IVN）、正則化參數（C）、核參數（γ）和輸出向量個數（OVN），同時該表也分別列出了各個預測模型的預測準確率（PCR）與平均每一回合模型優化時間（TIME）。

表1 性能比較

從表1可以得到以下觀點：

（1）采用經歸一化預處理數據時，運用粒子群算法優化支持向量機參數所獲得的預測模型PSOPDSVM的預測準確率是86.616 5%，平均每一回合模型優化時間為1 253.896 s；運用遺傳算法優化支持向量機參數所獲得的預測模型GAOPDSVM的預測準確率是86.315 8%，平均每一回合模型優化時間為3 026.719 s；而隨意設置支持向量機參數所獲得的預測模型CSOPDSVM的預測準確率僅是79.548 9%。

（2）采用原值數據時，運用粒子群算法優化支持向量機參數所獲得的預測模型PSOODSVM的預測準確率是84.360 9%，平均每一回合模型優化時間為7 991.406 3 s；運用遺傳算法優化支持向量機參數所獲得的預測模型GAOODSVM的預測準確率是74.887 2%，平均每一回合模型優化時間為11 852.156 s；而隨意設置支持向量機參數所獲得的預測模型CSOODSVM的預測準確率只是69.172 9%。

（3）當采用經歸一化預處理數據時，模型PSOPDSVM的預測準確率比模型GAOPDSVM和模型CSOPDSVM的預測準確率分別高出0.300 7%和7.067 6%，模型GAOPDSVM比模型CSOPDSVM的預測準確率高出6.766 9%。模型PSOPDSVM的平均每一回合模型優化時間比模型GAOPDSVM的平均每一回合模型優化時間約少1.4倍。

（4）當采用原值數據時，模型PSOODSVM的預測準確率比模型GAOODSVM和模型CSOODSVM的預測準確率分別高出9.473 7%和15.188%，模型GAOODSVM比模型CSOODSVM的預測準確率高出5.714 3%。模型PSOODSVM的平均每一回合模型優化時間比模型GAOODSVM的平均每一回合模型優化時間約少0.5倍。

（5）預測模型PSOPDSVM的預測準確率比預測模型PSOODSVM的預測準確率高2.255 6%，預測模型GAOPDSVM的預測準確率比預測模型GAOODSVM的預測準確率高11.428 6%，預測模型CSOPDSVM的預測準確率比預測模型CSOODSVM的預測準確率高10.376%。模型PSOODSVM的平均每一回合模型優化時間比模型PSOPDSVM的平均每一回合模型優化時間約多5.4倍，模型GAOODSVM的平均每一回合模型優化時間比模型GAOPDSVM的平均每一回合模型優化時間約多2.9倍。

（6）在預測準確率方面，運用粒子群算法優化支持向量機參數所獲得的預測模型比運用遺傳算法優化支持向量機參數與隨意設置支持向量機參數所獲得的預測模型高，運用遺傳算法優化支持向量機參數所獲得的預測模型比隨意設置支持向量機參數所獲得的預測模型高，采用經歸一化預處理數據比采用原值數據高。

（7）在模型優化時間方面，運用粒子群算法優化支持向量機參數比運用遺傳算法優化支持向量機參數少，采用經歸一化預處理數據比采用原值數據少。

6 結論和未來研究

本文介紹了運用粒子群算法和遺傳算法優化支持向量機參數的研究。此外，針對破產預測構建了二進制支持向量機，采用源自UCI機器學習數據庫的破產和非破產混合樣本數據集，分別輸入未經預處理的原值數據和經歸一化預處理的數據進行仿真實驗，運用7重交叉校驗方法計算和客觀地評價模型的預測準確率。仿真實驗證明，運用粒子群算法和遺傳算法優化支持向量機參數有效地加速學習和提高推廣性能，從而進一步提高破產預測準確率。同時，采用經歸一化預處理數據可以進一步提高破產預測準確率。實驗結果比較分析表明，在支持向量機預測模型優化方面，無論是預測準確率或模型優化時間，粒子群算法都強于遺傳算法。

支持向量機由于不同核函數的構造和選擇而各異，核函數的合理構造與正確選擇是支持向量機執行學習過程的重要一步，并且對支持向量機性能有至深的影響。為特定問題而構造和選擇核函數是一個耗時與耗力的過程，因此，如何構造與如何選擇最優核函數是亟需有待進一步研究的重要問題。

[1]Haykin S.Neural networks：a comprehensive foundation[M].Upper Saddle River，NJ，USA：Prentice Hall，1998.

[2]Vapnik V.The nature of statistical learning theory[M].New York：Springer-Verlag，1995.

[3]Schoelkopf B，Smola A.Learning with kernels[M].Cambridge，Massachusetts：The MIT Press，2002.

[4]Jiao Licheng，Li Yangyang，Gong Maoguo，et al.Quantum-inspired immune clonal algorithm for global optimization[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B（Cybernetics），2008，38（5）：1234-1253.

[5]Karaboga D，Basturk B.On the performance of artificial bee colony algorithm[J].Applied Soft Computing，2008，8（1）：687-697.

[6]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

[7]Goldberg D E.Genetic algorithms in search，optimization and machine learning[M].New York：Addison-Wesley，1989.

[8]Shin K，Lee T S，Kim H.An application of support vector machines in bankruptcy prediction model[J].Expert Systems with Applications，2005，28（1）：127-135.

[9]Min J H，Lee Y.Bankruptcy prediction using support vector machine with optimal choice of kernel function parameters[J].Expert Systems with Applications，2005，28（4）：603-614.

[10]Min S，Lee J，Han I.Hybrid genetic algorithms and support vector machines for bankruptcy prediction[J].Expert Systems with Applications，2006，31（3）：652-660.

[11]楊毓，蒙肖蓮.用支持向量機（SVM）構建企業破產預測模型[J].金融研究，2006（10）：65-75.

[12]Wu C，Tzeng G，Goo Y，et al.A real-valued genetic algorithm to optimize the parameters of support vector machine for predicting bankruptcy[J].Expert Systems with Applications，2007，32（2）：397-408.

[13]魯海波，徐云.基于支持向量機的企業破產分析[J].數學的實踐與認識，2007，37（12）：13-18.

[14]Gao Zhong，Cui Meng，Po Laiman.Enterprise bankruptcy prediction using noisy-tolerant Support Vector Machine[C]//2008 International Seminar on Future Information Technology and Management Engineering.Leicestershire：IEEE Press，2008：153-156.

[15]Zhong Ping，Xi Bin，Cen Yong.Support Vector Machines modeling for prediction[J].International Journal of Systems and Control，2008，1：42-47.

[16]Yoon J S，Kwon Y S.A practical approach to bankruptcy prediction for small businesses：substituting the unavailable financial data for credit card sales information[J].Expert Systems with Applications，2010，37（5）：3624-3629.

[17]Chaudhuri A，De K.Fuzzy Support Vector Machine for bankruptcy prediction[J].Applied Soft Computing，2011，11（2）：2472-2486.

[18]Moradi M，Sardasht M S，Ebrahimpou M.An application of Support Vector Machines in bankruptcy prediction evidence from Iran[J].World Applied Sciences Journal，2012，17（6）：710-717.

[19]Asuncion A，Newman D J.UCI machine learning repository[EB/OL].[2012-03-14].http：//archive.ics.uci.edu/ml/datasets.html.

[20]楊鐘瑾.核函數支持向量機[J].計算機工程與應用，2008，44（33）：1-6.

[21]顧亞祥，丁世飛.支持向量機研究進展[J].計算機科學，2011，38（2）：14-17.

[22]Andrew C，Peter F，Hartmut P，et al.Genetic Algorithm toolbox user’s guide[R].Sheffield：University of Sheffield，1994.

[23]Franc V，Hlava V.STPRtool[EB/OL].（2004-12-14）.http：//cmp.felk.cvut.cz/cmp/cmp software.html.

[24]Joachims T.Making large-scale SVM learning practical[C]//Advances in Kernel Methods—Support Vector Learning.Cambridge，MA：MIT Press，1999：169-184.

[25]Joachims T.SVMlight software[EB/OL].（2002-03-14）.http：//svmlight.joachims.org/.

[26]Franc V，Hlava V.Statistical pattern recognition toolbox for Matlab user’s guide[EB/OL].（2004-06-24）.ftp：//cmp.felk.cvut.cz/pub/cmp/articles/.