基于全局代表指標(biāo)的LSSVM最優(yōu)稀疏化算法

張世榮 童 博

(武漢大學(xué) 電氣與自動(dòng)化學(xué)院,武漢430072)

目前,人工智能(artificial intelligence,AI)已成為全球一大研究熱點(diǎn),正為社會(huì)發(fā)展帶來更多可能性.機(jī)器學(xué)習(xí)作為人工智能的關(guān)鍵環(huán)節(jié),也因統(tǒng)計(jì)學(xué)的堅(jiān)實(shí)基礎(chǔ)而獲得了迅速發(fā)展,眾多機(jī)器學(xué)習(xí)算法正被廣泛應(yīng)用于各種各樣的場景.最小二乘支持向量機(jī)(least square support vector machine,LSSVM)是一種典型的機(jī)器學(xué)習(xí)算法[1].不同于支持向量機(jī)(support vector machine,SVM)[2],LSSVM將SVM中的不等式約束轉(zhuǎn)換為等式約束,一方面使得建模過程的計(jì)算大大簡化；另一方面,等式約束導(dǎo)致其缺失了SVM與生俱來的稀疏性.稀疏化對(duì)于LSSVM有著重要的意義,是LSSVM 算法研究的一個(gè)重要分支.自LSSVM算法發(fā)表以來,對(duì)于LSSVM稀疏化的研究便從未停止,涌現(xiàn)了一些可行的稀疏化方法[3-10],大部分算法均源于模型樣本剪枝的基本理念.文獻(xiàn)[5]也采用樣本剪枝思想,但將LSSVM的稀疏化轉(zhuǎn)化為最優(yōu)化問題來進(jìn)行求解.其優(yōu)化問題以樣本支持值的絕對(duì)值|αk|為指標(biāo),以樣本剪切率為優(yōu)化變量對(duì)訓(xùn)練樣本進(jìn)行剪切,以獲得最小泛化誤差.文獻(xiàn)[10]定義了LSSVM 訓(xùn)練樣本空間中的全局代表指標(biāo)(global representative indicator,GRI),并以GRI為指標(biāo)對(duì)LSSVM 模型進(jìn)行了稀疏化,用試算結(jié)果證明了GRI指標(biāo)的有效性.文獻(xiàn)[10]中采用的GRI完全不同于大多數(shù)LSSVM剪枝稀化算法所采用的|αk|指標(biāo),為LSSVM模型稀疏化提供了另外一條可行路徑.

本文將對(duì)GRI進(jìn)行完善與發(fā)展,并基于GRI建立LSSVM最優(yōu)稀疏化問題,尋求LSSVM模型稀疏化的一套科學(xué)方法.本文的稀疏化算法以校驗(yàn)誤差最小化為優(yōu)化目標(biāo),以GRI為指標(biāo)擇選LSSVM的最優(yōu)支持向量集.鑒于此優(yōu)化問題的復(fù)雜性,無法采用線性規(guī)劃、二次規(guī)劃等常規(guī)方法進(jìn)行優(yōu)化求解.利用粒子群優(yōu)化算法(particle swarm optimization,PSO)來求解此LSSVM模型的最優(yōu)稀疏化問題,并針對(duì)一個(gè)典型的函數(shù)模型給出最優(yōu)稀疏化結(jié)果,驗(yàn)證本文提出的最優(yōu)稀疏化算法的有效性.

1 樣本GRI指標(biāo)

LSSVM模型稀疏化的實(shí)質(zhì)是從原始訓(xùn)練樣本集中挑選合適的樣本構(gòu)成樣本數(shù)更少的訓(xùn)練樣本集,并滿足某一(或某些)預(yù)定指標(biāo).可見,樣本的挑選依據(jù)是模型稀疏化的關(guān)鍵.以往LSSVM剪枝稀疏化算法中,大多數(shù)以|αk|為指標(biāo),認(rèn)為具有較大|αk|的樣本具有更大的權(quán)重,更應(yīng)該保留到訓(xùn)練樣本集.剪枝稀疏化采用迭代方法,在每次迭代中刪除具有較小|αk|的訓(xùn)練樣本,此類方法在工程中獲得了廣泛應(yīng)用,由于評(píng)價(jià)指標(biāo)的非單調(diào)性,使得剪枝算法難以獲得最佳的訓(xùn)練樣本集[5].本文采用GRI指標(biāo)來對(duì)訓(xùn)練樣本進(jìn)行擇選,GRI是一個(gè)混合指標(biāo),由樣本密度和離散度綜合而成.

1.1 密度

在特征空間中,兩個(gè)樣本之間的距離表示為

式中:K(xi,xj)為核函數(shù),采用與LSSVM模型中相同的函數(shù)形式.特征空間中任一數(shù)據(jù)點(diǎn)xi的密度可以用數(shù)據(jù)點(diǎn)特定鄰域內(nèi)點(diǎn)的個(gè)數(shù)來衡量；直觀而言,樣本密度代表鄰域內(nèi)其它樣本的聚集程度.定義樣本密度為ρ(xi),領(lǐng)域大小為θ,則密度可表達(dá)為

其中,n為樣本個(gè)數(shù),且

可見,樣本密度為鄰域θ 內(nèi)樣本點(diǎn)的個(gè)數(shù),是描述樣本聚合度的一種指標(biāo),體現(xiàn)了樣本空間的局部性特征.

1.2 離散度

樣本集中,離散度ζ(xi)是樣本xi的另一個(gè)指標(biāo),定義為該點(diǎn)到比該點(diǎn)密度更大的其他點(diǎn)的最小距離:

式中:X為全體可用樣本的集合；D為樣本之間距離值的集合.樣本離散度也是基于樣本距離來定義.計(jì)算某一樣本xi的離散度時(shí),先將所有密度比xi密度大的樣本取出來計(jì)算,構(gòu)成一個(gè)距離值集合,再取該集合中的最小值,即各樣本與xi的最小距離,作為xi的離散度.但該定義中存在一個(gè)例外,若xi是樣本集中密度最大的樣本,則將其離散度置為樣本集中樣本的最大離散度,如式(4)所示.

1.3 GRI

從密度和離散度的定義可以看出樣本密度具有局部性特征,而離散度具有全局性特征.將高密度點(diǎn)作為LSSVM支持向量可以使得類中心超平面的定位更具有精確性；但是,若僅考慮樣本密度,LSSVM支持向量將集中在某個(gè)高密度區(qū)域,使得訓(xùn)練樣本集喪失全局性.在LSSVM樣本稀疏化中需要綜合考慮局部性和全局性.以下所采用的樣本全局代表指標(biāo)GRI就是一種基于密度和離散度的綜合指標(biāo),采用以下乘積方案實(shí)現(xiàn)指標(biāo)綜合

式中:λ(xi)表示樣本xi的GRI.由于式(5)中ρ(xi)和ζ(xi)在數(shù)值上可能有不同的數(shù)量級(jí),在進(jìn)行乘積綜合處理前需要對(duì)密度和離散度分別進(jìn)行歸一化.顯然,GRI是綜合考慮樣本局部代表性與全局代表性的綜合指標(biāo),GRI值更大的樣本能更好地代表整個(gè)樣本集,應(yīng)該被選作LSSVM模型的支持向量.

1.4 鄰域

樣本密度定義中,鄰域θ 是一個(gè)敏感參數(shù),直接影響著樣本密度和離散度.圖1為2維樣本的示意圖,可見θ越大則密度ρ越大,樣本代表性指標(biāo)GRI作用距離越大,樣本影響范圍也就越大.GRI的大小將直接改變LSSVM 訓(xùn)練樣本的選取結(jié)果,影響稀疏化性能.在本文后續(xù)最優(yōu)稀疏化問題中,鄰域θ 也將作為優(yōu)化變量之一,通過最優(yōu)化算法獲得θ 的合適取值.

2 基于GRI的LSSVM 最優(yōu)優(yōu)化稀疏化

2.1 優(yōu)化問題

根據(jù)LSSVM理論,LSSVM回歸可以表達(dá)為

式中:y(x)為LSSVM回歸輸出；xk(k=1,2,…,N)為支持向量；αk為支持向量的支持值；N為支持向量個(gè)數(shù).LSSVM稀疏化即從原始訓(xùn)練樣本集中挑選合適的N個(gè)樣本構(gòu)成模型的支持向量集.以下將LSSVM稀疏化轉(zhuǎn)化為最優(yōu)化問題進(jìn)行求解.

設(shè)有L+M 個(gè)可用訓(xùn)練樣本,樣本歸一化后被分成兩組:第一組樣本集XL包含L個(gè)樣本,XL=,用于模型訓(xùn)練；第二組樣本集XM包含M 個(gè)樣本,,用于模型校驗(yàn).稀疏化問題以校驗(yàn)樣本輸出與模型預(yù)測輸出的均方根誤差(root-mean-square error,RMSE)為評(píng)價(jià)指標(biāo),RMSE計(jì)算如下:

其中,yj為第j 個(gè)校驗(yàn)樣本的輸出.

設(shè)φ為LSSVM模型的樣本剪切率,θ為鄰域,將它們記作參數(shù)向量ε=[φ,θ].基于GRI的LSSVM稀疏化問題計(jì)算過程如下:先確定鄰域θ,計(jì)算樣本集XL中每個(gè)樣本的密度ρ和離散度ζ,綜合ρ和ζ 獲得樣本的GRI指標(biāo),再按照GRI降序排列,獲得排序后的GRI向量如下:

確定φ,從XL中去除排序末尾φ%的樣本,將剩余N 個(gè)樣本作為LSSVM的訓(xùn)練樣本 集XN[φ,θ],訓(xùn)練樣本個(gè)數(shù)記為:

式(11)中:

取校驗(yàn)樣本輸出與模型預(yù)測輸出的均方根誤差為目標(biāo)函數(shù),取參數(shù)變量ε=[φ,θ]為優(yōu)化變量,則LSSVM的稀疏化過程可以轉(zhuǎn)換為如下最優(yōu)化問題:

2.2基于PSO 的優(yōu)化求解

在最優(yōu)化問題(15)的求解中包含樣本的GRI排序等操作；優(yōu)化變量ε=[φ,θ]與優(yōu)化目標(biāo)RMSE 之間為非線性關(guān)系,且沒有確定的數(shù)學(xué)表達(dá)式.因此,線性規(guī)劃或二次規(guī)劃等經(jīng)典算法無法求解此類優(yōu)化問題.遺傳算法(genetic algorithm,GA)、PSO等智能算法可以作為以上優(yōu)化問題的解決方案.其中,PSO因計(jì)算過程簡單,收斂迅速以及可調(diào)參數(shù)少等優(yōu)點(diǎn),在諸如機(jī)械、化學(xué)、民事、航空航天等眾多領(lǐng)域獲得了廣泛應(yīng)用,PSO 也將用于求解本文提出的優(yōu)化問題.

在使用PSO 算法之前,需要確定適應(yīng)函數(shù).本文將優(yōu)化問題(15)的目標(biāo)函數(shù)作為PSO 算法的適應(yīng)函數(shù).適應(yīng)函數(shù)具體為:

基于PSO 的LSSVM最優(yōu)稀疏化問題的求解流程如圖2所示.

確定適應(yīng)函數(shù)及粒子群規(guī)模p之后,結(jié)合訓(xùn)練樣本集XL和校驗(yàn)樣本集XM,算法進(jìn)入第一次迭代.首先,初始化全部p個(gè)粒子的位置Q1=(Q11,Q21,…,Qp1)和速度V1=(V11,V21,…,Vp1)；其中,Qi1=εi1=[φi1,θi1]表示第一次迭代內(nèi)第i 個(gè)粒子的位置,Vi1=[Δφi1,Δθi1]為第一次迭代內(nèi)第i 個(gè)粒子的速度.初始化完成后,對(duì)于每一個(gè)粒子,算法根據(jù)粒子的θ 值計(jì)算訓(xùn)練樣本集XL中全部樣本的GRI并將樣本按GRI降序排序,獲得排序后樣本集.排序完成后,算法根據(jù)粒子的φ值,剪切去除樣本集末尾φ%的 樣 本,獲 得 支持向量集并用訓(xùn)練LSSVM模型.然后,以校 驗(yàn)樣本集XM中的xj,(j=1,2,…,M)為LSSVM模型輸入,計(jì)算模型預(yù)測值y[φ,θ](xj),結(jié)合樣本校驗(yàn)值yj,(j=1,2,…,M),計(jì)算該粒子的適應(yīng)函數(shù)值RMSE.依次計(jì)算所有粒子的適應(yīng)函數(shù)值,并記錄粒子的個(gè)體最優(yōu)適應(yīng)函數(shù)值i_best及其對(duì)應(yīng)位置Qi_best；記錄并導(dǎo)出所有粒子的全局最優(yōu)適應(yīng)函數(shù)值g_best及其對(duì)應(yīng)位置Qg_best.一次迭代完成后,所有粒子都需要更新位置,更新算法如下:

式中:Vik、Qik分別表示第i 個(gè)粒子在第k個(gè)搜索周期中的 速度和 位置；ω為PSO 算法的慣性權(quán)重；c1、c2為算法的兩個(gè)學(xué)習(xí)因子；r1和r2為[0,1]區(qū)間內(nèi)的隨機(jī)數(shù).所有粒子更新位置后,進(jìn)入下一次迭代,直到滿足搜索結(jié)束條件,PSO 結(jié)束搜索,輸出最終結(jié)果.

3 算法驗(yàn)證

3.1 函數(shù)模型

為了驗(yàn)證以上提出的基于GRI的LSSVM最優(yōu)稀疏化算法,并便于直觀展示算法結(jié)果,選取二維sin c函數(shù)進(jìn)行驗(yàn)證,該函數(shù)表示為:

當(dāng)輸入向量x=[x1,x2]T,在x1∈[-10,0)∪(0,10]且x2∈[-10,0)∪(0,10]范圍內(nèi)取值時(shí),函數(shù)的曲面如圖3所示.

sin c函數(shù)曲面存在較大的波動(dòng),規(guī)律復(fù)雜,是例證支持向量機(jī)回歸模型的合適對(duì)象,在文獻(xiàn)中也獲得了廣泛認(rèn)同.為了使得樣本更加貼近工業(yè)實(shí)際,在sin c函數(shù)值上刻意引入干擾以仿真測量誤差:

其中,μ為隨機(jī)數(shù)且μ∈[0.015,0.02].

3.2 算法結(jié)果

首先,對(duì)樣本進(jìn)行歸一化處理；然后,根據(jù)式(1)計(jì)算樣本集XL中樣本點(diǎn)兩兩之間的距離值,距離值都處于區(qū)間γ=[0.058 9,1.414 2]內(nèi).故在以下計(jì)算中將鄰域值θ的取值范圍限定于區(qū)間γ內(nèi)以縮小PSO 的搜索空間,加快求解速度.在優(yōu)化問題的求解計(jì)算中,LSSVM核函數(shù)設(shè)置為徑向基核函數(shù)(RBF),正規(guī)化參數(shù)c=50,核參數(shù)σ2=10,PSO 粒子群規(guī)模設(shè)置為p=40,慣性權(quán)重ω=0.9,兩個(gè)學(xué)習(xí)因子c1=2,c2=2,粒子最大速度為搜索范圍的30%.PSO 的結(jié)束條件設(shè)置為:當(dāng)適應(yīng)度函數(shù)全局最優(yōu)值g_best在連續(xù)250次迭代中未變化時(shí),停止PSO搜索過程.所有計(jì)算于Matlab 2016b平臺(tái)進(jìn)行,軟件運(yùn)行于一臺(tái)個(gè)人電腦,該電腦搭載頻率為2.30 GHz的Core i5-8300 H CPU.

PSO 迭代過程中,適應(yīng)函數(shù)全局最優(yōu)值g_best的變化趨勢如圖5所示.可見,PSO 在約190次迭代后即取得了適應(yīng)度函數(shù)的最小值0.060 7；此時(shí),PSO粒子聚攏到點(diǎn)[φ*=0.556 6,θ*=1.328 29],該點(diǎn)即為LSSVM 模型稀疏化問題的最優(yōu)解.即,當(dāng)鄰域θ取1.32829且將按GRI降序排序后,切除樣本集XL末尾55個(gè)樣本,保留前45個(gè)樣本作為支持向量時(shí),LSSVM 模型具有最佳性能,可以獲得最小的RMSE.

為了驗(yàn)證基于GRI指標(biāo)擇選LSSVM支持向量的有效性,將XL的100個(gè)訓(xùn)練樣本呈現(xiàn)于圖6.圖6中“+”為訓(xùn)練樣本,“⊕”為經(jīng)過PSO優(yōu)化后選作支持向量的45個(gè)樣本.圖6(a)橫軸為密度縱軸為離散度；圖6(b)增加了GRI維度,將訓(xùn)練樣本呈現(xiàn)在三維坐標(biāo).從圖6中可見,支持向量都具有較大密度或離散度,進(jìn)而具有較大的GRI綜合指標(biāo).當(dāng)LSSVM 模型選用此類樣本為支持向量時(shí),模型在校驗(yàn)樣本集上取得了最小RMSE.以上結(jié)果驗(yàn)證了以GRI為指標(biāo)擇選LSSVM模型支持向量的有效性,且證明了GRI指標(biāo)與樣本重要程度之間存在確定的正相關(guān)關(guān)系.另外,圖6還表明,本文采用最優(yōu)化獲得了支持向量的最佳數(shù)量,為LSSVM模型的稀疏化建立了一種更加科學(xué)的方法.

再將支持向量呈現(xiàn)于sin c函數(shù)的自變量空間.如圖7所示,圖中“+”為訓(xùn)練樣本,“⊕”為經(jīng)過優(yōu)化獲得的45個(gè)支持向量.從圖7 中可以看出LSSVM模型的支持向量在sin c函數(shù)的二維平面上分布均勻,從直觀上看這些支持向量具有更好的全局代表性.在LSSVM剪枝稀化算法中一般以樣本支持值的絕對(duì)值|αk|為指標(biāo),而本文采用GRI為指標(biāo).

為了對(duì)比二者的關(guān)系,將以上支持向量的GRI值和支持值α 陳列于圖8、表1進(jìn)行比對(duì).由圖8、表1可見樣本的GRI指標(biāo)與支持值α并無明顯相關(guān)性,GRI指標(biāo)是一個(gè)完全獨(dú)立于樣本支持值的樣本屬性.

表1 GRI與支持值

續(xù)表1 GRI與支持值

為進(jìn)一步驗(yàn)證采用本文所提稀疏化方法LSSVM模型的泛化能力,本文引用了另外兩種LSSVM稀疏化方法進(jìn)行對(duì)比研究.一種為Suykens提出的經(jīng)典稀疏化方法[3],為了便于敘述,將基于經(jīng)典方法稀疏化處理的模型記為LSSVMclassical.另外一種為文獻(xiàn)[5]提出的基于支持值和PSO 優(yōu)化的稀疏化方法,以下將經(jīng)該方法處理的模型記為LSSVMα+PSO.將本文稀疏化方法處理后的模型記為LSSVMGRI+PSO；另外,還將未經(jīng)處理的原始訓(xùn)練樣本也加入對(duì)比,其模型記為LSSVMorignal.

仍取圖4所示訓(xùn)練樣本和校驗(yàn)樣本為范例開展以下對(duì)比研究,并另外均勻選取100個(gè)樣本構(gòu)成測試樣本集XE,用于測試各模型的泛化能力.所有稀疏化方法從樣本集XL選訓(xùn)練樣本,用樣本集XM做校驗(yàn),用樣本集XE驗(yàn)證泛化能力.

首先,用100個(gè)原始訓(xùn)練樣本XL對(duì)模型進(jìn)行訓(xùn)練,獲得LSSVMorignal模型.再以測試樣本集XE驗(yàn)證LSSVMorignal模型,計(jì)算LSSVMorignal模型在XE上的RMSE,見表2；并將測試樣本的真實(shí)值和預(yù)測值繪制對(duì)比曲線,如圖9(a)所示.然后,用經(jīng)典稀疏化方法對(duì)訓(xùn)練樣本集XL進(jìn)行稀疏化處理.該稀疏化過程采用迭代形式完成,并以樣本支持值絕對(duì)值|αk|為指標(biāo)對(duì)訓(xùn)練樣本進(jìn)行剪切.當(dāng)?shù)^程的RMSE 指標(biāo)劣化時(shí),LSSVM的稀疏化過程結(jié)束.最終,經(jīng)典稀疏化方法保留了80個(gè)樣本作為LSSVMclassical模型的支持向量.以測試樣本集XE驗(yàn)證LSSVMclassical模型,獲得測試樣本集的RMSE,如表2所示.將XE的樣本輸出與LSSVMclassical模型預(yù)測輸出進(jìn)行對(duì)比,結(jié)果如圖9(b)所示.

重復(fù)以上過程,分別以文獻(xiàn)[10]所提的稀疏化方法以及本文所提的最優(yōu)稀疏化方法對(duì)XL進(jìn)行模型稀疏化,分別獲得LSSVMα+PSO模型和LSSVMGRI+PSO模型.此兩個(gè)LSSVM模型的測試指標(biāo)和比對(duì)曲線分別如表2、圖9(c)和圖9(d)所示.

表2訓(xùn)練樣本集對(duì)比

從對(duì)比表2中可以看出,LSSVMGRI+PSO模型具有最大的樣本剪切率,最小的樣本容量,僅保留45個(gè)樣本作為模型支持向量；且在測試樣本集上的RMSE最小0.061 3.本文提出的基于GRI指標(biāo)的LSSVM稀疏化方法,由于采用了最優(yōu)化方法,可以實(shí)現(xiàn)稀疏化性能和校驗(yàn)誤差性能的雙重優(yōu)化.LSSVMα+PSO模型也采用了最優(yōu)化方法,該模型采用|αk|為指標(biāo),而αk必須在LSSVM訓(xùn)練后才能獲得；與之相比GRI指標(biāo)直接源于訓(xùn)練樣本集,無需LSSVM 訓(xùn)練.每次優(yōu)化迭代GRI+PSO 稀疏化方法比α+PSO方法少一次LSSVM模型訓(xùn)練,這可以大大簡化模型的計(jì)算過程.經(jīng)典稀疏化方法在每次迭代中都會(huì)判別性能指標(biāo)是否劣化,并把它作為是否結(jié)束稀疏化的判據(jù).若RMSE指標(biāo)呈現(xiàn)非單調(diào)特性,則此方法就無法獲得較好的稀疏化結(jié)果,這一點(diǎn)在表2中獲得了驗(yàn)證.

圖9的對(duì)比曲線中,紅色實(shí)線代表LSSVM模型的預(yù)測輸出值,藍(lán)色虛線代表校驗(yàn)樣本集XE的真實(shí)值.可以看出,與其余3 個(gè)模型相比,LSSVMGRI+PSO模型的預(yù)測輸出對(duì)測試樣本的跟隨效果更佳,體現(xiàn)出較好的泛化性能.

4 結(jié)論

稀疏化是最小二乘支持向量機(jī)研究的重要環(huán)節(jié),對(duì)其算法的研究具有重要意義.本文在樣本全局代表點(diǎn)的基礎(chǔ)上進(jìn)行了完善,提出全局代表指標(biāo)GRI.基于GRI進(jìn)一步提出了一種LSSVM最優(yōu)稀疏化算法.算法以樣本剪切率和鄰域大小為優(yōu)化變量,以RMSE 為優(yōu)化目標(biāo),將稀疏化問題作為優(yōu)化問題求解,獲得了一種更加科學(xué)的LSSVM模型稀疏化方法.針對(duì)優(yōu)化問題的復(fù)雜性提出了基于PSO的求解方法.取二維sin c函數(shù)為對(duì)象對(duì)算法進(jìn)行了驗(yàn)證,并對(duì)3種方法進(jìn)行了對(duì)比研究.結(jié)果揭示了GRI與樣本重要程度之間的正相關(guān)關(guān)系,且表明GRI與支持值α并無明顯相關(guān)性,是一個(gè)完全獨(dú)立于樣本支持值的樣本屬性.本文提出的基于GRI的LSSVM稀疏化算法采用最優(yōu)方法在3種方法對(duì)比中取得了最佳性能,能同時(shí)獲得最大的樣本剪切率和最小的RMSE指標(biāo).本文的最優(yōu)稀疏化算法實(shí)現(xiàn)簡單,適合LSSVM模型的在線應(yīng)用.