馮 哲, 陳云鳳, 周 宇, 云 挺, 鄧玉和

(1.南京林業(yè)大學 信息科學技術學院, 江蘇 南京 210037)(2.南京林業(yè)大學 材料科學與工程學院,江蘇 南京 210037)

基于改進的NCSPSO-AFSA對SVM參數(shù)的優(yōu)化及其應用

馮 哲1, 陳云鳳1, 周 宇1, 云 挺1, 鄧玉和2

(1.南京林業(yè)大學 信息科學技術學院, 江蘇 南京 210037)(2.南京林業(yè)大學 材料科學與工程學院,江蘇 南京 210037)

為了找到支持向量機(SVM)最佳的分類參數(shù),用以構建適合紋理圖像分割的SVM分類器,文中是將基于小生境和交叉選擇算子的粒子群算法(NCSPSO)引入變異算子和族外競爭機制加以改進后與人工魚群算法(AFSA)混合,提出了一種改進的NCSPSO-AFSA混合算法優(yōu)化支持向量機參數(shù),并分別與AFSA算法,粒子群算法(PSO),NCSPSO算法在圖像分割準確率、參數(shù)尋優(yōu)時間、圖像分割時間等方面進行對比和分析,實驗表明文中算法能夠更好地獲得適用于紋理圖像分割的SVM參數(shù),在縮短圖像分割時間的同時提高了圖像分割準確率,相比較其他算法,文中算法穩(wěn)健性更好.將此方法應用于電鏡及超聲紋理圖像分割中能較好地提取出目標區(qū)域,圖像邊緣部分的分類也很清晰.

NCSPSO算法; 人工魚群算法; 支持向量機; 圖像分割

圖像分割是圖像處理與計算機視覺領域中最為基礎和重要的問題之一,圖像分割的效果將直接影響到后續(xù)分析、識別和解釋等處理.而紋理是圖像的重要特征,普遍存在于各類圖像當中,由于紋理圖像自身的復雜性,使得紋理圖像的分割顯得尤為困難.

支持向量機[1](support vector machine, SVM)是一種基于統(tǒng)計學習理論的機器學習方法,能較好地解決小樣本、非線性等實際問題.實踐表明,SVM的性能與核函數(shù)的參數(shù)及懲罰系數(shù)C有很大關系.文中在基于小生境和交叉選擇算子的粒子群算法中加入變異算子和族外競爭機制,再將其與人工魚群算法混合,提出了改進的NCSPSO-AFSA混合算法.該算法有利于提高紋理圖像分割的速度和精度.

1 SVM分類器

對于給定的線性可分數(shù)據(jù)集{xi,yi},i=1,…,l,yi∈{-1,+1},xi∈Rn,滿足

yi[w·xi+b]-1≥0;i=1,…,l

(1)

利用Lagrange乘子法并滿足KKT(Karush-kuhn-Tucher)條件,最后可得到解上述問題的最優(yōu)分類函數(shù)為:

f(x)=sgn{w*·x+b*}=

(2)

式中：α*,b*為確定最優(yōu)劃分超平面的參數(shù),(xi·x)為兩個向量的點積.

對于線性不可分情況,通過在約束條件中引入松弛變量,在目標函數(shù)中加入懲罰函數(shù)來解決這一問題.這時廣義最優(yōu)分類面問題可以進一步演化為求取下列函數(shù)的極小值:

(3)

式中:C為懲罰系數(shù),用于控制錯分樣本懲罰的程度.

支持向量機引入核函數(shù),避免了高維空間的向量內(nèi)積而造成大量運算.徑向基核函數(shù)是目前應用最廣泛的核函數(shù),文中采用的就是這一核函數(shù),形式如下:

K(xi,xj)=exp(-γ‖xi-xj‖2),γ>0

(4)

式中:參數(shù)γ是核函數(shù)中的重要參數(shù),影響著SVM分類算法的復雜程度.

綜上所述,懲罰參數(shù)C和核函數(shù)參數(shù)γ是影響SVM分類器性能的關鍵參數(shù),所以文中以(C,γ)作為尋優(yōu)變量.

2 基于改進的NCSPSO-AFSA優(yōu)化SVM的紋理圖像分割方法

2.1 現(xiàn)有NCSPSO算法

針對粒子群算法容易陷入局部最優(yōu),出現(xiàn)早熟現(xiàn)象,池元成等人[2]2010年結合小生境和交叉選擇算子提出了一種改進粒子群優(yōu)化算法(NCSPSO).該算法通過對當前代個體歷史最好位置的多樣化處理,增強了粒子搜索復雜未知空間的能力.

首先,根據(jù)小生境數(shù)[3-4]確定孤立點.假設當前代個體歷史最好位置的集合為CP={Pi=(pi1,pi2,…,piD) |i=1,2,…,N},計算該集合所有元素之間的距離

(5)

其中,i=1,2,…,N,j=1,2,…,N,且i≠j.相應的共享函數(shù)值

(6)

其中,σshare為給定的小生境半徑.在此基礎上,計算每個元素的小生境數(shù)

(7)

其中,i=1,2,…,N,且i≠j.經(jīng)過比較,小生境數(shù)最小的元素就是當前代個體歷史最好位置中的孤立點Q=(q1,q2,…,qD).

然后對所有個體歷史最好值劣于孤立點值的粒子使用交叉和選擇算子進行更新.

2.2 人工魚群算法

人工魚群算法(artificial fish-swarm algorithm,AFSA) 是李曉磊等人[5]于2002年提出的一種基于模擬魚群行為的隨機搜索優(yōu)化算法.它是說在一片水域中,魚往往能自行或尾隨其它魚找到營養(yǎng)物質(zhì)多的地方,因而魚生存數(shù)目最多的地方一般就是本水域中營養(yǎng)物質(zhì)最多的地方.人工魚群算法就是根據(jù)仿生學特點,通過構造人工魚來模仿魚群的覓食、聚群及追尾行為,從而實現(xiàn)尋優(yōu)[6-7].人工魚在移動中有3個典型的行為:

1)覓食行為 魚在水中自由地游動,發(fā)現(xiàn)食物時,會向著食物逐漸增多的方向迅速游去.

2)聚群行為 魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群.魚聚群時所遵守的規(guī)則有3條:① 避免與伙伴過于擁擠;② 盡量與伙伴的平均方向一致;③ 盡量朝伙伴的中心移動.

3)追尾行為 當發(fā)現(xiàn)食物時,魚會尾隨其臨近的伙伴快速到達食物點.

2.3 NCSPSO算法的改進

2.3.1 引入變異算子

NCSPSO算法對當前代個體歷史最好位置進行了多樣化處理,但由于個體沒有變異機制,一旦陷入局部最優(yōu)時需要借助其他個體跳出局部最優(yōu)的環(huán)境.由于文中改進的算法最終是應用于SVM參數(shù)優(yōu)化,并應用到兩類紋理圖像分割,因此適應度值很重要.鑒于此,對變異算子做出了相應的改進:

(8)

根據(jù)變異因子,文中對于適應度值劣于孤立點適應度值的個體采用如下的變異方式:

(9)

1)固定取值的變異算子,以FG1=0.2,FG2=0.9為例.

2)傳統(tǒng)的動態(tài)變異算子:FG=FG1+rand(0,1)·(FG2-FG1).

3)改進變異算子,取值方式如式(8).以4種變異算子的取值為例,將荻草圖像和超聲圖像作為分割對象,進行分割測試.

采用兩類紋理圖像作為分割對象,其中荻草細胞圖來自國家科學自然基金項目(30871973),超聲圖像是醫(yī)院實際所用超聲圖像[8].圖像紋理特征的提取方法參考文獻[9],采用結合灰度共生矩陣Curvelet變換的特征提取方法.

表1列舉了不同的變異算子FG的取值對荻草圖像和超聲圖像的分割效果.其中:圖像分割時間為獲得C和γ后建立的分類模型對兩類紋理圖像進行分割所用時間.從表1可以看出引入變異算子,尤其是經(jīng)過文中改進的變異算子的取值方式使得兩類圖像的分割準確率均略高于其他方式,所用的圖像分割時間也少.

表1 選擇不同變異算子時的訓練結果Table 1 Training results with different mutation operator

2.3.2 引入族外競爭機制

NCSPSO算法的選擇操作是在同一個種群中不同的小生境之間形成的競爭,就是意義上的內(nèi)部競爭.為了增加個體之間的競爭壓力,將個體的直接的競爭擴大到不同種群之間,將進化種群中的最優(yōu)解的個體與隨機組成的種群的最優(yōu)解形成競爭.族內(nèi)競爭使個體易于局部最優(yōu),而族外競爭使目標函數(shù)值向全局最優(yōu)解快速收斂.

將初始種群稱作主群,根據(jù)隔離機制的小生境的基本思想,將主群任意分為若干子群,每個子群是由主群的一部分和其他子群的全局最優(yōu)值構成的.而在整個算法的迭代過程中,主群的進化更新與子群的進化更新相互獨立.

2.4 改進NCSPSO-AFSA優(yōu)化的SVM分類模型

1) 樣本數(shù)據(jù)初始化

樣本數(shù)據(jù)大小為100×136,并進行[0,1]區(qū)間歸一化.

2) 人工魚群算法設置

Step1:設定魚群的參數(shù),包括魚群規(guī)模m,最大迭代次數(shù)gen,最大嘗試次數(shù)trynum,最大移動步長step,擁擠度因子δ等;

Step2:計算初始適應度值,把最優(yōu)值放入公告板中;

Step3:計算出追尾行為、群聚行為的值,選擇最優(yōu)的行為作為魚的前進方向,同時與公告板中的值進行比較,如果優(yōu)于公告板上的值則更新公告板;

Step4:判斷是否達到最大迭代次數(shù),若已經(jīng)達到則終止尋優(yōu),輸出公告板上的最優(yōu)值;否則,返回到Step2,繼續(xù)運行.

3) 改進的NCSPSO算法設置

Step1:初始化進化主種群,包括最大種群數(shù)、最大迭代次數(shù)、個體的位置和速度、計算主種群初始的適應度值.

Step2:根據(jù)隔離機制的小生境的基本思想,將主種群分為了子群1和子群2,子群1的一部分是從主群中任意選出,另外一部分是由子群2的全局最優(yōu)值構成.子群2同樣由此構成.

Step3:更新進化種群

①比較子群1和子群2的全局最優(yōu)值是否優(yōu)于主群的最優(yōu)解,如果優(yōu)于主群的最優(yōu)解,使用子群1和子群2的最優(yōu)解替換主群中的任意一行,進行族外競爭.

②根據(jù)公式(5～7)確定主群中的孤立點.

③對適應度值劣于孤立點適應度值的個體進行交叉操作.

④根據(jù)公式(8～9)對適應度值劣于孤立點適應度值的個體進行變異操作.

⑤對上面兩步產(chǎn)生的新個體進行選擇競爭操作.

Step4:使用標準粒子群算法更新子群1和子群2的個體[10],與主種群的進化相互獨立.

Step5:判斷是否達到最大迭代次數(shù),若已經(jīng)達到則終止尋優(yōu),輸出主群全局最優(yōu)解;否則,返回到Step2,繼續(xù)運行.

4) 比較兩種算法所取得的C和γ的值,取最佳組合(C,γ).

3 實驗結果與分析

3.1 SVM參數(shù)的選取

根據(jù)SVM理論,核函數(shù)的不同影響分類器的性能的好壞,所以核函數(shù)及相關參數(shù)選擇的好壞直接影響到SVM的性能.對于選定的核函數(shù)來說,選擇合適的懲罰系數(shù)C和γ是非常關鍵的.下面將運用PSO算法、NCSPSO算法、AFSA算法和文中的算法分別選擇較為合適的參數(shù)，如表2.

表2 4種方法的參數(shù)值對比Table 2 Parameters of four methods

3.2 訓練樣本的選取

文中實驗軟件平臺為MATLAB R2011a,運行環(huán)境為雙CPU PC機,CPU是主頻為3.2G的Intel Pentium 4多線程處理器,內(nèi)存為2G,硬盤大小為250G,操作系統(tǒng)是Windows XP Professional SP3.

表3,4是以荻草圖像和超聲圖像做的對比試驗,在種群規(guī)模大小相同,迭代次數(shù)相同的情況下,隨機選取不同大小的訓練樣本,使用改進的NCSPSO-AFSA混合算法所取得的尋優(yōu)時間和分割準確率.其中樣本1大小為100×136的矩陣,樣本2大小為200×136的矩陣,樣本3大小為300×136的矩陣,樣本4大小為400×136的矩陣,樣本5大小為500×136的矩陣.

表3 樣本大小不同情況下兩類圖像尋優(yōu)時間比較Table 3 Optimization time of texture image withdifferent sample size s

表4 樣本大小不同情況下兩類圖像分割準確率比較Table 4 Segmentation accuracy of texture image withdifferent sample size %

從表3，4可以看出,不論是荻草圖像還是超聲圖像,隨著訓練樣本的逐漸增大,整個算法的尋優(yōu)時間成倍的增長,但是平均分割準確率不僅沒有明顯的增長,還略有下降的趨勢.超聲圖像樣本1的平均尋優(yōu)時間只有樣本5的1/15,甚至更少,平均分割準確率卻比樣本5高出7%,甚至更多.這說明了樣本大小的選取對于整個算法性能的穩(wěn)定有很大的影響,樣本1大小更加適合改進的NCSPSO-AFSA混合算法,通過樣本1找到的C和γ建立的分類模型更好.

3.3 圖像分割效果

為了對比,將改進的NCSPSO-AFSA混合算法與PSO,NCSPSO,AFSA算法優(yōu)化SVM建立的分類模型對荻草圖像a1)和一組超聲圖像a2)～a8)做了分割實驗.圖中a1)～a8)為原圖,b1)～b8)、c1)～c8)、d1)～d8)分別為PSO算法、NCSPSO算法和AFSA算法優(yōu)化SVM后的分割效果圖,e1)～e8) 為改進的NCSPSO-AFSA混合算法的分割效果圖.

圖1實驗結果
Fig.1Segmentationresults

從分割效果圖1可以看出:文中方法對荻草細胞圖像和超聲圖像均達到了很好的分割效果.相比PSO算法、AFSA算法,改進的NCSPSO-AFSA混合算法的紋理分割區(qū)域的邊緣輪廓更加完整、更加精確.而與NCSPSO算法相比,改進的NCSPSO-AFSA混合算法穩(wěn)健性更好.

3.4 訓練結果比對

在種群規(guī)模大小相同,尋優(yōu)迭代次數(shù)相同的情況下,對以上4種算法每次取得最優(yōu)解的時間,即收斂代數(shù)做了比較.從圖2中可以看出,改進的NCSPSO-AFSA混合算法均在迭代3～5次之間就能獲取最優(yōu)解,而且適應度值均高于95%.這表明改進的NCSPSO-AFSA混合算法所找到的C和γ更加適合用于建立SVM紋理圖像分割模型.

圖24種方法的訓練結果對比
Fig.2Comparativeresultsoffourmethods

4種方法的分割結果見表5,從表5可以看出:采用改進的NCSPSO-AFSA混合算法尋找到的C和γ,建立SVM分類模型,不論是對兩類或多類的紋理圖像分割,都取得了很高的分割準確率.對比AFSA算法,文中方法的尋優(yōu)時間較長于AFSA算法,但是分割準確率比AFSA算法平均高出1%.對比NCSPSO算法,文中方法的分割準確率平均提高了0.5%.對比PSO的方法,文中方法尋找最佳C和γ所用時間是其1/3,分割準確率平均提高1%,圖像分割時間是其1/2.

表5 4種方法的分割結果對比Table 5 Segmentation results of four methods

4 結論

文中提出了基于改進的NCSPSO-AFSA混合算法對SVM參數(shù)優(yōu)化,以荻草圖像和超聲圖像作為實例,分別采用PSO算法、NCSPSO算法、AFSA算法和文中的算法進行比較分析,結果表明文中的算法所找到的參數(shù)C和γ對紋理圖像分割取得了很高的分割準確率,同時縮短了圖像分割時間,在算法穩(wěn)健性上有一定的優(yōu)勢.應用到電鏡及超聲紋理圖像的分割建模,取得了較好的效果.

References)

[1] Vapnik V, Levin E, Cun Y L. Measuring the VC-dimension of learning machines[J].NeuralComputation,1994, 6(5): 851-876.

[2] 池元成,方杰,魏鑫,等. 基于小生境和交叉選擇算子的改進粒子群優(yōu)化算法[J]. 系 統(tǒng) 仿 真 學報, 2010, 22(1):111-114. Chi Yuancheng, Fang Jie, Wei Xin,et al. Improved particle swarm optimization algorithm based on niche, crossover and selection operators[J].JournalofSystemSimulation,2010, 22(1):111-114.(in Chinese)

[3] 朱寧,馮志剛,王祁. 基于小生境遺傳算法的支持向量機分類器參數(shù)優(yōu)化[J]. 南京理工大學學報:自然科學版, 2009, 33(1): 16-20. Zhu Ning, Feng Zhigang, Wang Qi. Parameter optimization of support vector machine for classification using niche genetic algorithm[J].JournalofNanjingUniversityofScienceandTechnology:NatureScience,2009, 33(1): 16-20. (in Chinese)

[4] 李雋穎,樓曉俊. 基于小生境遺傳算法的分類優(yōu)化方法[J]. 計算機應用研究, 2012, 29(5): 1787-1790. Li Junying,Lou Xiaojun. Classifier optimization method using niche genetic algorithm[J].ApplicationResearchofComputers,2012, 29(5): 1787-1790. (in Chinese)

[5] 李曉磊,邵之江,錢積新. 一種基于動物自治體的尋優(yōu)模式:魚群算法[J]. 系統(tǒng)工程理論與實踐, 2002, 22: 32-38. Li Xiaolei,Shao Zhijiang,Qian Jixin.An optimizing method based on autonomous animats: fish-swarmalgorithm[J].SystemsEngineering:Theory&Practice,2002, 22: 32-38. (in Chinese)

[6] 楊利紅. 基于AFSA的SVM參數(shù)優(yōu)化及其應用[D]. 山西太原: 太原理工大學, 2012.

[7] 施秋紅. 人工魚群算法的改進及應用研究[D]. 甘肅蘭州: 甘肅農(nóng)業(yè)大學, 2010.

[8] 曹琳,云挺,舒華忠. 基于曲線波的超聲圖像分割[J]. 東南大學學報:自然科學版, 2012, 42(3): 419-423. Cao Lin，Yun Ting，Shu Huazhong. Ultrasound image segmentation based on curvelet[J].JournalofSoutheastUniversity:NaturalScienceEdition,2012, 42(3): 419-423. (in Chinese)

[9] 王嫻,周宇,云挺,等. 基于Curvelet變換的荻草細胞圖像分割[J]. 計算機科學, 2012, 39(11): 277-279. Wang Xian, Zhou Yu, Yun Ting,et al. Miscanthus Sacchariflorus Cells Image Segmentation Based on Curvelet Transformation[J].ComputerScience,2012, 39(11): 277-279.(in Chinese)

[10] 陳云鳳,云挺,周宇,等. 基于PSO優(yōu)化SVM的紋理圖像分割[J]. 計算機應用與軟件, 2014, 31(4): 214-218. Chen Yunfeng, Yun Ting, Zhou Yu, et al. Texture image segmentation based on pso optimising svm[J].ComputerApplicationsandSoftware,2014, 31(4): 214-218.(in Chinese)

(責任編輯：顧 琳)

ParameteroptimizationandapplicationofSVMbasedonimprovedNCSPSOandAFSA

Feng Zhe1, Chen Yunfeng1, Zhou Yu1, Yun Ting1, Deng Yuhe2

(1.College of Information Science and Technology, Nanjing Forestry University, Nanjing Jiangsu 210037, China)(2.College of Materials Science and Engineering, Nanjing Forestry University, Nanjing Jiangsu 210037, China)

To find the best parameters of SVM and construct the SVM Classifier which is suitable to be applied to texture image segmentation, the paper improves niche and cross-selection operator PSO where mutation mechanism and group competition mechanism are introduced and combined with artificial fish-swarm algorithm (AFSA). The parameter optimization algorithm for support vector machine (SVM) is proposed. Compared with AFSA, particle swarm optimization and NCSPSO algorithm in accuracy and time of image segmentation and parameter optimization time, it turns out that the proposed algorithm can effectively find the parameters of SVM, cut time and improve accuracy of image segmentation, at the same time, its stability is better than other algorithms. When applied to the electron microscope image and ultrasonic image segmentation, the method it can extract the target area and the image edges are classified quite clearly.

NCSPSO; AFSA; support vector machine; image segmentation

10.3969/j.issn.1673-4807.2014.04.018

2014-08-03

國家自然科學基金資助項目(31300472)；國家自然科學基金資助項目(30871973)；江蘇省自然科學基金資助項目(BK2012418)

馮 哲(1992—)，女，研究方向為模式識別與圖像處理.E-mail:535716987@qq.com

周 宇(1972—)，女，副教授，研究方向為圖像數(shù)理、數(shù)據(jù)融合.E-mail:zhouyu@shanghaitech.edu.cn

TN911.73

A

1673-4807(2014)04-0395-08