基于改进的NCSPSO-AFSA对SVM参数的优化及其应用

冯 哲, 陈云凤, 周 宇, 云 挺, 邓玉和

(1.南京林业大学 信息科学技术学院, 江苏 南京 210037)(2.南京林业大学 材料科学与工程学院,江苏 南京 210037)

基于改进的NCSPSO-AFSA对SVM参数的优化及其应用

冯 哲1, 陈云凤1, 周 宇1, 云 挺1, 邓玉和2

(1.南京林业大学 信息科学技术学院, 江苏 南京 210037)(2.南京林业大学 材料科学与工程学院,江苏 南京 210037)

为了找到支持向量机(SVM)最佳的分类参数,用以构建适合纹理图像分割的SVM分类器,文中是将基于小生境和交叉选择算子的粒子群算法(NCSPSO)引入变异算子和族外竞争机制加以改进后与人工鱼群算法(AFSA)混合,提出了一种改进的NCSPSO-AFSA混合算法优化支持向量机参数,并分别与AFSA算法,粒子群算法(PSO),NCSPSO算法在图像分割准确率、参数寻优时间、图像分割时间等方面进行对比和分析,实验表明文中算法能够更好地获得适用于纹理图像分割的SVM参数,在缩短图像分割时间的同时提高了图像分割准确率,相比较其他算法,文中算法稳健性更好.将此方法应用于电镜及超声纹理图像分割中能较好地提取出目标区域,图像边缘部分的分类也很清晰.

NCSPSO算法; 人工鱼群算法; 支持向量机; 图像分割

图像分割是图像处理与计算机视觉领域中最为基础和重要的问题之一,图像分割的效果将直接影响到后续分析、识别和解释等处理.而纹理是图像的重要特征,普遍存在于各类图像当中,由于纹理图像自身的复杂性,使得纹理图像的分割显得尤为困难.

支持向量机[1](support vector machine, SVM)是一种基于统计学习理论的机器学习方法,能较好地解决小样本、非线性等实际问题.实践表明,SVM的性能与核函数的参数及惩罚系数C有很大关系.文中在基于小生境和交叉选择算子的粒子群算法中加入变异算子和族外竞争机制,再将其与人工鱼群算法混合,提出了改进的NCSPSO-AFSA混合算法.该算法有利于提高纹理图像分割的速度和精度.

1 SVM分类器

对于给定的线性可分数据集{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)条件,最后可得到解上述问题的最优分类函数为:

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

(2)

式中：α*,b*为确定最优划分超平面的参数,(xi·x)为两个向量的点积.

对于线性不可分情况,通过在约束条件中引入松弛变量,在目标函数中加入惩罚函数来解决这一问题.这时广义最优分类面问题可以进一步演化为求取下列函数的极小值:

(3)

式中:C为惩罚系数,用于控制错分样本惩罚的程度.

支持向量机引入核函数,避免了高维空间的向量内积而造成大量运算.径向基核函数是目前应用最广泛的核函数,文中采用的就是这一核函数,形式如下:

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

(4)

式中:参数γ是核函数中的重要参数,影响着SVM分类算法的复杂程度.

综上所述,惩罚参数C和核函数参数γ是影响SVM分类器性能的关键参数,所以文中以(C,γ)作为寻优变量.

2 基于改进的NCSPSO-AFSA优化SVM的纹理图像分割方法

2.1 现有NCSPSO算法

针对粒子群算法容易陷入局部最优,出现早熟现象,池元成等人[2]2010年结合小生境和交叉选择算子提出了一种改进粒子群优化算法(NCSPSO).该算法通过对当前代个体历史最好位置的多样化处理,增强了粒子搜索复杂未知空间的能力.

首先,根据小生境数[3-4]确定孤立点.假设当前代个体历史最好位置的集合为CP={Pi=(pi1,pi2,…,piD) |i=1,2,…,N},计算该集合所有元素之间的距离

(5)

其中,i=1,2,…,N,j=1,2,…,N,且i≠j.相应的共享函数值

(6)

其中,σshare为给定的小生境半径.在此基础上,计算每个元素的小生境数

(7)

其中,i=1,2,…,N,且i≠j.经过比较,小生境数最小的元素就是当前代个体历史最好位置中的孤立点Q=(q1,q2,…,qD).

然后对所有个体历史最好值劣于孤立点值的粒子使用交叉和选择算子进行更新.

2.2 人工鱼群算法

人工鱼群算法(artificial fish-swarm algorithm,AFSA) 是李晓磊等人[5]于2002年提出的一种基于模拟鱼群行为的随机搜索优化算法.它是说在一片水域中,鱼往往能自行或尾随其它鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方.人工鱼群算法就是根据仿生学特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现寻优[6-7].人工鱼在移动中有3个典型的行为:

1)觅食行为 鱼在水中自由地游动,发现食物时,会向着食物逐渐增多的方向迅速游去.

2)聚群行为 鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群.鱼聚群时所遵守的规则有3条:① 避免与伙伴过于拥挤;② 尽量与伙伴的平均方向一致;③ 尽量朝伙伴的中心移动.

3)追尾行为 当发现食物时,鱼会尾随其临近的伙伴快速到达食物点.

2.3 NCSPSO算法的改进

2.3.1 引入变异算子

NCSPSO算法对当前代个体历史最好位置进行了多样化处理,但由于个体没有变异机制,一旦陷入局部最优时需要借助其他个体跳出局部最优的环境.由于文中改进的算法最终是应用于SVM参数优化,并应用到两类纹理图像分割,因此适应度值很重要.鉴于此,对变异算子做出了相应的改进:

(8)

根据变异因子,文中对于适应度值劣于孤立点适应度值的个体采用如下的变异方式:

(9)

1)固定取值的变异算子,以FG1=0.2,FG2=0.9为例.

2)传统的动态变异算子:FG=FG1+rand(0,1)·(FG2-FG1).

3)改进变异算子,取值方式如式(8).以4种变异算子的取值为例,将荻草图像和超声图像作为分割对象,进行分割测试.

采用两类纹理图像作为分割对象,其中荻草细胞图来自国家科学自然基金项目(30871973),超声图像是医院实际所用超声图像[8].图像纹理特征的提取方法参考文献[9],采用结合灰度共生矩阵Curvelet变换的特征提取方法.

表1列举了不同的变异算子FG的取值对荻草图像和超声图像的分割效果.其中:图像分割时间为获得C和γ后建立的分类模型对两类纹理图像进行分割所用时间.从表1可以看出引入变异算子,尤其是经过文中改进的变异算子的取值方式使得两类图像的分割准确率均略高于其他方式,所用的图像分割时间也少.

表1 选择不同变异算子时的训练结果Table 1 Training results with different mutation operator

2.3.2 引入族外竞争机制

NCSPSO算法的选择操作是在同一个种群中不同的小生境之间形成的竞争,就是意义上的内部竞争.为了增加个体之间的竞争压力,将个体的直接的竞争扩大到不同种群之间,将进化种群中的最优解的个体与随机组成的种群的最优解形成竞争.族内竞争使个体易于局部最优,而族外竞争使目标函数值向全局最优解快速收敛.

将初始种群称作主群,根据隔离机制的小生境的基本思想,将主群任意分为若干子群,每个子群是由主群的一部分和其他子群的全局最优值构成的.而在整个算法的迭代过程中,主群的进化更新与子群的进化更新相互独立.

2.4 改进NCSPSO-AFSA优化的SVM分类模型

1) 样本数据初始化

样本数据大小为100×136,并进行[0,1]区间归一化.

2) 人工鱼群算法设置

Step1:设定鱼群的参数,包括鱼群规模m,最大迭代次数gen,最大尝试次数trynum,最大移动步长step,拥挤度因子δ等;

Step2:计算初始适应度值,把最优值放入公告板中;

Step3:计算出追尾行为、群聚行为的值,选择最优的行为作为鱼的前进方向,同时与公告板中的值进行比较,如果优于公告板上的值则更新公告板;

Step4:判断是否达到最大迭代次数,若已经达到则终止寻优,输出公告板上的最优值;否则,返回到Step2,继续运行.

3) 改进的NCSPSO算法设置

Step1:初始化进化主种群,包括最大种群数、最大迭代次数、个体的位置和速度、计算主种群初始的适应度值.

Step2:根据隔离机制的小生境的基本思想,将主种群分为了子群1和子群2,子群1的一部分是从主群中任意选出,另外一部分是由子群2的全局最优值构成.子群2同样由此构成.

Step3:更新进化种群

①比较子群1和子群2的全局最优值是否优于主群的最优解,如果优于主群的最优解,使用子群1和子群2的最优解替换主群中的任意一行,进行族外竞争.

②根据公式(5～7)确定主群中的孤立点.

③对适应度值劣于孤立点适应度值的个体进行交叉操作.

④根据公式(8～9)对适应度值劣于孤立点适应度值的个体进行变异操作.

⑤对上面两步产生的新个体进行选择竞争操作.

Step4:使用标准粒子群算法更新子群1和子群2的个体[10],与主种群的进化相互独立.

Step5:判断是否达到最大迭代次数,若已经达到则终止寻优,输出主群全局最优解;否则,返回到Step2,继续运行.

4) 比较两种算法所取得的C和γ的值,取最佳组合(C,γ).

3 实验结果与分析

3.1 SVM参数的选取

根据SVM理论,核函数的不同影响分类器的性能的好坏,所以核函数及相关参数选择的好坏直接影响到SVM的性能.对于选定的核函数来说,选择合适的惩罚系数C和γ是非常关键的.下面将运用PSO算法、NCSPSO算法、AFSA算法和文中的算法分别选择较为合适的参数，如表2.

表2 4种方法的参数值对比Table 2 Parameters of four methods

3.2 训练样本的选取

文中实验软件平台为MATLAB R2011a,运行环境为双CPU PC机,CPU是主频为3.2G的Intel Pentium 4多线程处理器,内存为2G,硬盘大小为250G,操作系统是Windows XP Professional SP3.

表3,4是以荻草图像和超声图像做的对比试验,在种群规模大小相同,迭代次数相同的情况下,随机选取不同大小的训练样本,使用改进的NCSPSO-AFSA混合算法所取得的寻优时间和分割准确率.其中样本1大小为100×136的矩阵,样本2大小为200×136的矩阵,样本3大小为300×136的矩阵,样本4大小为400×136的矩阵,样本5大小为500×136的矩阵.

表3 样本大小不同情况下两类图像寻优时间比较Table 3 Optimization time of texture image withdifferent sample size s

表4 样本大小不同情况下两类图像分割准确率比较Table 4 Segmentation accuracy of texture image withdifferent sample size %

从表3，4可以看出,不论是荻草图像还是超声图像,随着训练样本的逐渐增大,整个算法的寻优时间成倍的增长,但是平均分割准确率不仅没有明显的增长,还略有下降的趋势.超声图像样本1的平均寻优时间只有样本5的1/15,甚至更少,平均分割准确率却比样本5高出7%,甚至更多.这说明了样本大小的选取对于整个算法性能的稳定有很大的影响,样本1大小更加适合改进的NCSPSO-AFSA混合算法,通过样本1找到的C和γ建立的分类模型更好.

3.3 图像分割效果

为了对比,将改进的NCSPSO-AFSA混合算法与PSO,NCSPSO,AFSA算法优化SVM建立的分类模型对荻草图像a1)和一组超声图像a2)～a8)做了分割实验.图中a1)～a8)为原图,b1)～b8)、c1)～c8)、d1)～d8)分别为PSO算法、NCSPSO算法和AFSA算法优化SVM后的分割效果图,e1)～e8) 为改进的NCSPSO-AFSA混合算法的分割效果图.

图1实验结果
Fig.1Segmentationresults

从分割效果图1可以看出:文中方法对荻草细胞图像和超声图像均达到了很好的分割效果.相比PSO算法、AFSA算法,改进的NCSPSO-AFSA混合算法的纹理分割区域的边缘轮廓更加完整、更加精确.而与NCSPSO算法相比,改进的NCSPSO-AFSA混合算法稳健性更好.

3.4 训练结果比对

在种群规模大小相同,寻优迭代次数相同的情况下,对以上4种算法每次取得最优解的时间,即收敛代数做了比较.从图2中可以看出,改进的NCSPSO-AFSA混合算法均在迭代3～5次之间就能获取最优解,而且适应度值均高于95%.这表明改进的NCSPSO-AFSA混合算法所找到的C和γ更加适合用于建立SVM纹理图像分割模型.

图24种方法的训练结果对比
Fig.2Comparativeresultsoffourmethods

4种方法的分割结果见表5,从表5可以看出:采用改进的NCSPSO-AFSA混合算法寻找到的C和γ,建立SVM分类模型,不论是对两类或多类的纹理图像分割,都取得了很高的分割准确率.对比AFSA算法,文中方法的寻优时间较长于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参数优化,以荻草图像和超声图像作为实例,分别采用PSO算法、NCSPSO算法、AFSA算法和文中的算法进行比较分析,结果表明文中的算法所找到的参数C和γ对纹理图像分割取得了很高的分割准确率,同时缩短了图像分割时间,在算法稳健性上有一定的优势.应用到电镜及超声纹理图像的分割建模,取得了较好的效果.

References)

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

[2] 池元成,方杰,魏鑫,等. 基于小生境和交叉选择算子的改进粒子群优化算法[J]. 系 统 仿 真 学报, 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] 朱宁,冯志刚,王祁. 基于小生境遗传算法的支持向量机分类器参数优化[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] 李隽颖,楼晓俊. 基于小生境遗传算法的分类优化方法[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] 李晓磊,邵之江,钱积新. 一种基于动物自治体的寻优模式:鱼群算法[J]. 系统工程理论与实践, 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参数优化及其应用[D]. 山西太原: 太原理工大学, 2012.

[7] 施秋红. 人工鱼群算法的改进及应用研究[D]. 甘肃兰州: 甘肃农业大学, 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优化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—)，女，副教授，研究方向为图像数理、数据融合.E-mail:zhouyu@shanghaitech.edu.cn

TN911.73

A

1673-4807(2014)04-0395-08