基于改進(jìn)的差異演化算法求解SVM反問(wèn)題的研究

樊永生+熊焰明+余紅英

摘 要： 針對(duì)求解支持向量機(jī)反問(wèn)題的效率較低，算法復(fù)雜度高以及運(yùn)用傳統(tǒng)方法求解該問(wèn)題容易陷入局部最優(yōu)出現(xiàn)早熟收斂的問(wèn)題，提出一種基于改進(jìn)差異的差異演化算法。該算法在標(biāo)準(zhǔn)差異演化算法的基礎(chǔ)上利用種群分類機(jī)制對(duì)算法進(jìn)行改進(jìn)，對(duì)改進(jìn)后的算法與標(biāo)準(zhǔn)差異演化算法和K?means聚類算法進(jìn)行實(shí)驗(yàn)設(shè)計(jì)，并對(duì)算法最終實(shí)驗(yàn)結(jié)果進(jìn)行分析，改進(jìn)的差異演化算法除在運(yùn)行時(shí)間外，結(jié)果對(duì)比以及最大間隔次數(shù)比都有明顯的提升，有效地保護(hù)處于最優(yōu)解區(qū)域但是適應(yīng)值低的個(gè)體，能夠提高算法局部搜索能力，有助于算法實(shí)現(xiàn)全局收斂。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的差異演化算法在求解SVM反問(wèn)題上能有明顯的提升。

關(guān)鍵詞： 支持向量機(jī)； 局部最優(yōu)； 差異演化算法； 全局收斂； 種群分類機(jī)制； IRIS數(shù)據(jù)庫(kù)

中圖分類號(hào)： TN911?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）06?0141?04

Abstract： Since the traditional algorithm has the problems of low efficiency of support vector machine （SVM） inverse problem solving and high algorithm complexity， is easily to fall into local optimum， and is prone to the premature convergence， a new differential evolutionary algorithm based on improved difference is proposed. On the basis of normative differential evolution algorithm， the population classification mechanism is used to improve the algorithm. The experimental design was carried out for the improved algorithm， normative differential evolution algorithm and K?means clustering algorithm. The final experimental results of the algorithm are analyzed. The maximum interval numbers and average interval numbers of the changed differential evolution （CDE） algorithm beyond operation time are improved greatly. The algorithm can effectively protect the individual within the optimum solution region but with low adaptive value， improve the local search ability of the algorithm， and is conductive to the realization of global convergence. The experimental results show that the performance of the CDE algorithm is improved obviously for SVM inverse problem solving.

Keywords： support vector machine； local optimum； differential evolution algorithm； global convergence； population classification mechanism； IRIS database

0 引 言

支持向量機(jī)（Support Vector Machine，SVM）是機(jī)器學(xué)習(xí)領(lǐng)域中一個(gè)重要的研究熱點(diǎn)，因其具有優(yōu)秀的泛化能力和學(xué)習(xí)能力被廣泛地應(yīng)用在模式識(shí)別、文本分類、信號(hào)處理、回歸分析等領(lǐng)域[1?3]。SVM是在統(tǒng)計(jì)學(xué)習(xí)理論的基礎(chǔ)上，提出最優(yōu)超平面間隔理論。該理論結(jié)合結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理，將原始訓(xùn)練樣本進(jìn)行提取壓縮，得到支持向量集合，通過(guò)這些支持向量子集學(xué)習(xí)新的知識(shí)。SVM出發(fā)點(diǎn)是根據(jù)已經(jīng)給定的正負(fù)標(biāo)簽的類別信息，尋找兩類樣本之間的最優(yōu)超平面。在尋找過(guò)程中，靠近當(dāng)前最優(yōu)超平面最近的樣本點(diǎn)到超平面的距離盡可能的大，不同類別的樣本之間的間距也會(huì)越大，分類器的泛化能力也就越強(qiáng)。所以，SVM是一個(gè)在訓(xùn)練樣本訓(xùn)練之前賦予其標(biāo)簽信息的典型監(jiān)督學(xué)習(xí)問(wèn)題。

然而，如果訓(xùn)練之前沒有已給定的任何類別信息，根據(jù)上述的SVM問(wèn)題難以快速找到最優(yōu)超平面，為此，出現(xiàn)了SVM反問(wèn)題，即無(wú)監(jiān)督學(xué)習(xí)。SVM反問(wèn)題是一種訓(xùn)練樣本在訓(xùn)練之前不含有任何類別信息的無(wú)監(jiān)督學(xué)習(xí)問(wèn)題，通過(guò)尋找樣本之間的最大間距（margin），完成學(xué)習(xí)[4?7]。差分演化算法是解決研究無(wú)監(jiān)督學(xué)習(xí)這一問(wèn)題的最先進(jìn)的算法之一[8?9]，本文提出應(yīng)用改進(jìn)的差異演化算法與聚類算法及標(biāo)準(zhǔn)差異演化算法進(jìn)行實(shí)驗(yàn)分析，結(jié)果表明，所提出的算法在總體上優(yōu)于其他最先進(jìn)的進(jìn)化算法。

1 算法設(shè)計(jì)

1.1 概 述

定義1 （SVM反問(wèn)題） 假設(shè)存在數(shù)據(jù)集合[S=x1，x2，…，xn，]并且[xi∈Rni=1，2…，N，][Ω=][ff是從S到 [-1，1] 的映射函數(shù)]。給定函數(shù)[f∈Ω]，數(shù)據(jù)集分為兩個(gè)子類，然后計(jì)算間隔（margin）。用margin（f）表示某個(gè)分類方法的類間隔[10]，SVM反問(wèn)題為：[maxf∈Ωmarginf]。endprint