基于改進PSO算法的混合核SVM算法

徐中宇, 蘇明玉, 姚慶安

(長春工業大學 計算機科學與工程學院, 長春 130012)

支持向量機(support vector machine, SVM)[1-2]是一種能在極其有限的信息條件下學習到最優預測結果的算法, 如何確定函數中相關參數對于增強混合核SVM的預測準確率非常重要[3-5]. 粒子群優化(particle swarm optimization, PSO)算法[6-7]是一種基于種群的全局并行優化方法, 具有收斂速度快并易于實現等優點. 本文通過PSO算法對混合核SVM[8]的參數進行尋優. 由于普通粒子群算法在進行優化選擇時具有收斂慢和易陷入局部極小值等缺點, 因此目前已有多種改進粒子群優化算法[9-11]. 本文在粒子群算法的基礎上通過改進并限制其速度和搜索范圍等參數, 得到了性能更好的改進限制范圍粒子群優化(improved limit particle swarm optimization, ILPSO)算法. 結果表明, 該算法能更好地提高粒子的搜索性能, 提升了粒子群的收斂速率, 達到了最優的效果及精確優化混合核SVM參數的目的.

1 方法描述

1.1 混合核函數的SVM分類模型

SVM能對非線性特征進行線性分析[12], 并在該高維空間內建立一個具有最大類間隔[13]的分類超平面, 即最優超平面. 使用混合核函數[14-15]取代單核, 不僅具有兩個單核模型的優勢, 而且有更佳的學習和泛化等能力. 基于單核的優勢把多項式核和徑向基核進行線性組合[16], 構造混合核函數Knew為

Knew=λ1Kpoly+λ2Krbf,

(1)

其中：

λi(i=1,2)為權重系數, 滿足λ1,λ2∈(0,1), 且λ1+λ2=1.

1.2 改進的PSO算法

1.2.1 基本粒子群優化算法 PSO算法用于優化非線性函數, 設粒子群中第i個粒子在空間的位置為Xi, 其相應粒子速度為Vi, 此時局部極值為pbesti, 全局極值為gbesti. 在每次的粒子迭代中, 粒子從一個位置迭代到另一個位置, 每個粒子位置Xi根據不同因素的規則移動, 公式如下：

其中Vi為第i個粒子的速度, 定義為

其中：wmax,wmin分別為初始和最終的權重因子； itermax為最大迭代次數； iter為當前迭代數.

1.2.2 ILPSO算法設計 在PSO算法的實現中, 參數wi0,wi1,wi2,rnd1和rnd2都是該算法收斂的重要影響因子. 雖然普通的PSO算法有較快的收斂速度, 但在后期收斂速度較緩慢. 為使PSO算法加快收斂速度并提高求解質量, 本文通過以下3種策略對PSO算法進行改進.

1) 粒子速度限制.

初始化粒子隨機位置在其限制范圍內, 定義為

(2)

(3)

其中:

2) 減少搜索空間.

減少搜索空間有利于加快收斂速度. 在這種情況下, 搜索空間是動態調整的, 以達到預期的范圍內. 首先, 在粒子i中對控制變量j搜索限制的最小和最大控制變量為

(4)

迭代(k+1)次, 搜索空間限制為

(5)

(6)

其中:Xij,min為粒子的最小位置;Xij,max為粒子的最大位置.

3) 交叉算子.

(7)

且

(8)

其中： randij為一個在[0,1]內的隨機數；CR為交叉概率, 經驗確定的最佳值為0.5.

2 基于ILPSO算法的混合核SVM參數優化

本文的混合核SVM需要提前給定的參數分別為正則化參數C、 相應核參數中的σ及不敏感損失函數參數ε. 通常選取合適的C值有利于避免由誤差而引起的泛化能力減弱；ε用于控制擬合的管道, 有利于避免訓練樣本脫離管道壁;σ幫助SVM調解輸入參數的敏感程度. 因此, 必須為混合核SVM選擇最優的參數[16]. ILPSO算法優化參數的適應值可采用能直接反應SVM性能的均方差函數:

(9)

其中:fi為預測值;yi為實際值;m為樣本個數. 改進的限制性粒子群優化算法對多核SVM的參數選擇流程如圖1所示.

圖1 基于ILPSO對混合核SVM參數尋優的流程Fig.1 Flow chart for optimization of hybrid kernel SVM parameters based on ILPSO

ILPSO算法描述如下.

輸入: 粒子的維數和個數;

輸出: SVM最佳參數組合(C,σ,ε,λ).

2) 用牛頓迭代法求解各個參數, 通過評價各個粒子的目標函數、 穩態罰函數及進行暫態穩定仿真, 評估每個粒子的暫態穩定的罰函數, 并對粒子的當前參數值進行評價.

3) 計算每個粒子的適應度. 重新定位粒子的最新位置為極值ibesti.

4) 重新確定粒子的初始速度和位置, 根據式(9)確定為新的適應度值Ffitness, 令ipresenti=Ffitness.

5) 比較更新后的ipresenti和全局最優位置gbesti. 若ipresenti>gbesti, 則gbesti=ipresenti.

6) 判斷當前是否完全符合迭代終止的要求, 若符合, 則停止迭代, 并輸出最適合的SVM參數組合； 若不符合, 則重新計算粒子的權重、 位置和速度, 并轉2) . 若得到的最優解為多組時, 則取wi最小的一組.

7) 獲得優化后的多核權重參數后, 開始優化多核函數, 并應用于舌象的舌苔、 舌質分割測試集提取中.

8) 計算誤差精度, 并判斷是否符合分割條件, 如果不符合, 則轉7), 直至分割成功為止.

3 實驗結果與分析

選用山西醫科大學第一醫院生物圖像數據庫中的100例舌象樣本作為實驗樣本, 其中80例為訓練樣本, 20例為測試樣本. 實驗環境為CPU主頻2.8 GHz, 內存8 GB的計算機, MATLAB 7.10平臺.

將實驗數據中的測試樣本輸入到構造的SVM中進行性能測試, 以計算得到的均方根誤差函數值Frmse作為預測精度的參考值：

(10)

其中:xi為訓練樣本;yi為xi訓練樣本下的目標值;n為當前實驗中的樣本數量；C,σ,ε,λ為輸入參數.

3.1 不同方法優化混合核SVM的性能比較

為比較不同優化算法對參數優化的效果, 本文實驗中分別運用了十折交叉驗證法、 PSO算法、 CPSO算法和ILPSO算法對混合核SVM參數求最優解, 經過100次實驗, 分別用不同的優化方法對混合核SVM參數(C,σ,λ)進行優選, 其中λ,C和σ分別在[0,1],[0.01,1.1]和[1,1 000]內取值, 所得比較結果列于表1. 由表1可見, 相對于其他幾種優化方法, 改進后PSO算法的平均測試誤差和平均預測誤差均有所降低, 達到了理想的實驗結果.

表1 不同方法優化參數性能比較

3.2 舌苔、 舌質分割的SVM預測模型比較

本文實驗通過不同的PSO算法對混合核SVM參數優化結果進行對比, 從而驗證改進的PSO算法對舌苔、 舌質的分割具有較好的性能.

實驗中的測試樣本如圖2所示. 通過改進的PSO(improved limit PSO)多核SVM算法(ILPSO-SVM)、 ILPSO單核SVM算法(ILPSO-SVM)、 一般的PSO(normal PSO)多核SVM算法(NPSO-SVM)、 一般的PSO單核SVM算法(NPSO-SVM)、 遺傳算法(GA)多核SVM算法(GA-SVM)和普通的SVM算法對舌象的舌苔、 舌質分類進行仿真實驗, 實驗結果列于表2. 由表2可見, 遺傳算法的種群規模與ILPSO算法相同, 交叉概率為0.8, 變異概率為0.037, 代溝為0.9. 在分割實驗中, 本文的ILPSO-SVM多核和單核分割舌苔、 舌質結果如圖3所示.

表2 各種預測方法仿真結果對比

圖2 基于粒子群的混合核SVM舌象分割圖像樣本Fig.2 Hybrid kernel SVM tongue image segmentation image sample based on particle swarm

圖3 ILPSO算法的多種核SVM舌象分割圖像Fig.3 Multiple kernel SVM tongue image segmentation images of ILPSO algorithm

由圖2和圖3可見, ILPSO-SVM多核和單核分割的舌苔和舌質差別較大, 且多核的分割效果更接近于標準結果. 由表2可見, 本文改進的PSO優化多核SVM所生成的預測模型在很大程度上逼近于理想模型, 不僅能獲得較精確的全局最優解, 且具備較高的尋優效率(較短的進化時間)； 遺傳算法(GA)由于進行速度無法滿足要求, 最終收斂到局部極小值, 尋優失敗. 相比其他預測方法, 本文算法的預測準確度有所提升, 且誤差率明顯降低.

綜上所述, 本文算法較好地結合了單核模型的優勢, 運用組合的方式生成多核SVM模型, 并通過改進的PSO算法進行參數選擇, 克服了人工選取參數的主觀性. 實驗結果表明, 在舌象中的舌苔和舌質顏色交錯融合的特性中, 通過本文算法可得到更逼近理想的分割效果, 相比其他優化算法, 優化的核參數對于舌苔和舌質的分割有更高的分割精度和泛化性能.