張世榮 童 博

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

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

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

1 樣本GRI指標

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

1.1 密度

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

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

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

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

1.2 離散度

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

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

1.3 GRI

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

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

1.4 鄰域

樣本密度定義中,鄰域θ 是一個敏感參數(shù),直接影響著樣本密度和離散度.圖1為2維樣本的示意圖,可見θ越大則密度ρ越大,樣本代表性指標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回歸可以表達為

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

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

其中,yj為第j 個校驗樣本的輸出.

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

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

式(11)中:

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

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

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

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

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

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

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

3 算法驗證

3.1 函數(shù)模型

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

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

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

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

3.2 算法結(jié)果

首先,對樣本進行歸一化處理；然后,根據(jù)式(1)計算樣本集XL中樣本點兩兩之間的距離值,距離值都處于區(qū)間γ=[0.058 9,1.414 2]內(nèi).故在以下計算中將鄰域值θ的取值范圍限定于區(qū)間γ內(nèi)以縮小PSO 的搜索空間,加快求解速度.在優(yōu)化問題的求解計算中,LSSVM核函數(shù)設(shè)置為徑向基核函數(shù)(RBF),正規(guī)化參數(shù)c=50,核參數(shù)σ2=10,PSO 粒子群規(guī)模設(shè)置為p=40,慣性權(quán)重ω=0.9,兩個學(xué)習因子c1=2,c2=2,粒子最大速度為搜索范圍的30%.PSO 的結(jié)束條件設(shè)置為:當適應(yīng)度函數(shù)全局最優(yōu)值g_best在連續(xù)250次迭代中未變化時,停止PSO搜索過程.所有計算于Matlab 2016b平臺進行,軟件運行于一臺個人電腦,該電腦搭載頻率為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；此時,PSO粒子聚攏到點[φ*=0.556 6,θ*=1.328 29],該點即為LSSVM 模型稀疏化問題的最優(yōu)解.即,當鄰域θ取1.32829且將按GRI降序排序后,切除樣本集XL末尾55個樣本,保留前45個樣本作為支持向量時,LSSVM 模型具有最佳性能,可以獲得最小的RMSE.

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

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

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

表1 GRI與支持值

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

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

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

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

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

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

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

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

4 結(jié)論

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