徐奔業(yè),顧斌杰,潘豐,熊偉麗
(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,江蘇 無(wú)錫 214122)
支持向量機(jī)(Support Vector Machine,SVM)是20世紀(jì)90 年代由VAPNIK[1-2]提出的一種機(jī)器學(xué)習(xí)算法。與傳統(tǒng)的以降低經(jīng)驗(yàn)風(fēng)險(xiǎn)為目標(biāo)的神經(jīng)網(wǎng)絡(luò)相比,SVM的主要思想是最小化結(jié)構(gòu)風(fēng)險(xiǎn),這使得SVM 具有良好的泛化性能[3-4]。目前,SVM在入侵檢測(cè)[5]、圖像處理[6]、故障診斷[7]、干擾識(shí)別[8]等領(lǐng)域得到廣泛應(yīng)用。然而,SVM 在訓(xùn)練大規(guī)模數(shù)據(jù)集時(shí),存在時(shí)間復(fù)雜度高導(dǎo)致訓(xùn)練速度慢的問題[9]。KHEMCHANDANI等[10]提出孿生支持向量機(jī)(Twin Support Vector Machine,TSVM)。與SVM 相比,TSVM 僅需求解兩個(gè)較小規(guī)模的二次規(guī)劃問題,因此訓(xùn)練時(shí)間僅為SVM 的1/4 左右。CHEN等[11]提出投影孿生支持向量機(jī)(Projection Twin Support Vector Machine,PTSVM)。PTSVM 通過為每個(gè)類尋找一個(gè)最優(yōu)投影軸使投影點(diǎn)類內(nèi)方差最小化,構(gòu)建分類模型。
PENG[12]把TSVM 的思想用于回歸領(lǐng)域,提出孿生支持向量回歸(Twin Support Vector Regression,TSVR)算法。TSVR 通過求解兩個(gè)較小規(guī)模的二次規(guī)劃問題尋求回歸函數(shù),與傳統(tǒng)SVR 相比,TSVR 具有更好的泛化性能和更快的訓(xùn)練速度。CHEN等[13]引入Sigmoid光滑函數(shù),對(duì)TSVR 的目標(biāo)函數(shù)進(jìn)行光滑處理,提出光滑孿生支持向量回歸(Smooth Twin Support Vector Regression,STSVR)算法。STSVR 通過求解一對(duì)無(wú)約束優(yōu)化問題,獲得了比TSVR 更快的訓(xùn)練速度。PENG等[14]基于PTSVM 的思想,提出投影孿生支持向量回歸(Projection Twin Support Vector Regression,PTSVR)算法,包括雙邊移位投影孿生支持向量回歸(Pair-shifted PTSVR,PPTSVR)算法和單邊移位投影孿生支持向量回歸(Single-shifted PTSVR,SPTSVR)算法。PTSVR將訓(xùn)練集中的每個(gè)訓(xùn)練點(diǎn)進(jìn)行上下移位得到兩個(gè)新的移位集,從而利用PTSVM 的思想求解兩個(gè)最優(yōu)超平面的法向量。PPTSVR 和SPTSVR 的主要區(qū)別在于,PPTSVR 在兩個(gè)移位集上構(gòu)建回歸函數(shù),而SPTSVR 則是在原始集和一個(gè)移位集上構(gòu)建回歸函數(shù)。實(shí)驗(yàn)結(jié)果表明,PTSVR 有著比TSVR 更好的預(yù)測(cè)性能。
然而,PPTSVR 在尋找最優(yōu)超平面的過程中,將所有訓(xùn)練樣本對(duì)超平面的作用視為相同,沒有反映數(shù)據(jù)在空間中的分布情況,當(dāng)訓(xùn)練樣本中存在異常點(diǎn)時(shí),會(huì)削弱算法的擬合性能。本文采用孤立森林法賦予每個(gè)訓(xùn)練樣本不同的權(quán)值,通過賦予潛在的異常點(diǎn)很小的權(quán)值,削弱異常點(diǎn)對(duì)超平面構(gòu)造的影響,從而提高算法的擬合性能。同時(shí),為了避免在對(duì)偶空間中求解二次規(guī)劃問題,引入正號(hào)函數(shù),將有約束優(yōu)化問題轉(zhuǎn)化為不光滑的無(wú)約束優(yōu)化問題,并采用Sigmoid 光滑函數(shù)進(jìn)行光滑處理,提出一種加權(quán)光滑投影孿生支持向量回歸(Weighted Smooth Projection Twin Support Vector Regression,WSPTSVR)算法,以證明其任意階光滑且全局收斂的特性,并采用牛頓迭代法進(jìn)行求解。
本節(jié)首先采用孤立森林法判斷樣本中的潛在異常點(diǎn),并通過異常分?jǐn)?shù)機(jī)制賦予每個(gè)樣本不同的權(quán)值;其次引入Sigmoid 光滑函數(shù),提出WSPTSVR 算法,并證明其具有全局唯一最優(yōu)解;最后在原空間中使用牛頓迭代法進(jìn)行求解。
孤立森林法能夠有效地檢測(cè)出樣本中的潛在異常點(diǎn),即使樣本中沒有異常點(diǎn),也能夠根據(jù)異常分?jǐn)?shù)賦予每個(gè)樣本相應(yīng)的權(quán)值,從而提高算法的擬合性能[15-17]。孤立森林法首先遞歸地分割給定樣本集,直到每個(gè)樣本都被單獨(dú)分離出來(lái),然后根據(jù)每個(gè)樣本分離的路徑長(zhǎng)度計(jì)算其異常分?jǐn)?shù),根據(jù)異常分?jǐn)?shù)大小判斷樣本是否為異常點(diǎn)并賦予每個(gè)樣本點(diǎn)相應(yīng)的權(quán)值。通過孤立森林法確定加權(quán)系數(shù)共分為以下3 個(gè)步驟:
1)通過訓(xùn)練樣本的子集構(gòu)建t棵孤立樹,建立孤立森林。
2)在訓(xùn)練后的孤立森林中,根據(jù)每個(gè)樣本點(diǎn)分離所需的路徑長(zhǎng)度賦予其相應(yīng)的異常分?jǐn)?shù)Si,Si的取值范圍為0~1,且取值越大,該點(diǎn)為異常點(diǎn)的可能性越大,異常分?jǐn)?shù)Si計(jì)算如下:
其中:h(i)為樣本i的路徑長(zhǎng)度,即從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的邊數(shù),而異常點(diǎn)更容易被孤立,因此h(i)較?。籈(h(i))為樣本i在一組孤立森林中路徑長(zhǎng)度的均值;c(n)是樣本數(shù)為n時(shí)路徑長(zhǎng)度的均值,用來(lái)標(biāo)準(zhǔn)化樣本i的路徑長(zhǎng)度h(i)。c(n)計(jì)算如下:
其中:H(n-1)=ln(n-1)+0.577 215 664 9 為調(diào)和數(shù)。
3)通過孤立森林法中的異常分?jǐn)?shù)機(jī)制為每個(gè)樣本點(diǎn)賦予相應(yīng)的權(quán)值:
其中:ρi表示第i個(gè)樣本的權(quán)值。
文獻(xiàn)[15]的研究表明,當(dāng)樣本點(diǎn)的異常分?jǐn)?shù)Si>0.60 時(shí),即視該樣本點(diǎn)為潛在異常點(diǎn),應(yīng)賦予很小的權(quán)值,則樣本點(diǎn)的權(quán)值矩陣可表示為對(duì)角矩陣:
假設(shè)訓(xùn)練集用D={(xi;yi),i∈Ι={1,2,…,n}}表示,其中,xi∈Rm為輸入,yi∈R為輸出,I為指標(biāo)集,n為樣本個(gè)數(shù),m為樣本特征數(shù)。為了后續(xù)表示簡(jiǎn)單起見,分別用矩陣X=[x1,x2,…,xn]T∈Rn×m和向量Y=[y1,y2,…,yn]T∈Rn表示輸入和輸出,用矩陣J=[X,Y]∈Rn×(m+1)表示訓(xùn)練樣本,分別用矩陣Aε=[X,Y+εe]和Bε=[X,Y-εe]∈Rn×(m+1)表示上移和下移訓(xùn)練樣本,其中ε>0 為不敏感因子,e為全1 的列向量。
在雙邊移位投影孿生支持向量回歸算法的目標(biāo)函數(shù)中引入權(quán)值矩陣Wij,構(gòu)造如下最優(yōu)化問題:
然而,式(5)和式(6)需要在對(duì)偶空間中求解二次規(guī)劃問題,訓(xùn)練速度較慢。為了加快訓(xùn)練速度,采用正號(hào)函數(shù)將其轉(zhuǎn)化為無(wú)約束優(yōu)化問題,在原空間中直接進(jìn)行求解。
由Karush-Kuhn-Tucker(KKT)條件可得:
式(5)和式(6)可改寫為如下無(wú)約束優(yōu)化問題:
定理1[18]無(wú)約束優(yōu)化問題式(9)和式(10)連續(xù)但不光滑。
定理1 表明式(9)和式(10)不光滑,因此無(wú)法使用牛頓迭代法等梯度優(yōu)化方法求解。為此,采用Sigmoid 光滑函數(shù)逼近正號(hào)函數(shù)(x1)+和(x2)+。
Sigmoid 光滑函數(shù)p(x,α)定義如下:
其中:α為正常數(shù)。
據(jù)此可得正號(hào)函數(shù)(x1)+和(x2)+的Sigmoid 光滑函數(shù)分別如下:
將式(12)和式(13)分別代入式(9)和式(10),得到線性情況下加權(quán)光滑投影孿生支持向量回歸算法的兩個(gè)無(wú)約束優(yōu)化問題,如式(14)、式(15)所示:
引理1[19]若矩陣A∈Rn×n是實(shí)對(duì)稱矩陣,則A是正定矩陣當(dāng)且僅當(dāng)存在矩陣B∈Rm×n使得A=BTB。
定理2式(14)中的P1和式(15)中的P2是嚴(yán)格凸函數(shù)。
證明對(duì)任意的正常數(shù)α,P1顯然是連續(xù)可微的,以下證明其是嚴(yán)格凸函數(shù):
考慮到權(quán)值矩陣和對(duì)角矩陣都是正定陣,兩者可以分別分解為PTP和QTQ的形式,其中P和Q分別為兩者的平方根矩陣。因此,?2P1(u1)可以分解如下:
其中:C1,C3和α都是正標(biāo)量;I為正定矩陣。由 引理1 可得?2P1(u1)是正定的,因此P1是嚴(yán)格凸函數(shù)。同理可證P2也是連續(xù)可微的嚴(yán)格凸函數(shù)。
式(14)和式(15)二階可微,因此可以使用具有快速收斂能力的牛頓迭代法進(jìn)行求解[20-21]。由定理2 可知式(14)和式(15)是嚴(yán)格凸的,因此使用牛頓迭代法求解可以全局收斂,并得到唯一最優(yōu)解。牛頓迭代法可表示如下:
然后,通過求解式(23)和式(24)兩個(gè)無(wú)約束最小化問題,可得兩個(gè)最優(yōu)超平面的偏置分別如式(25)、式(26)所示:
在通常情況下,δ1,δ2≠0[14,21],可得移位函數(shù)f1(x)=-(+b1)/δ1和f2(x)=-(+b2)/δ2。
最終,可得回歸函數(shù)如下:
在非線性情況下,利用核技巧,構(gòu)造加權(quán)光滑投影孿生支持向量回歸算法的兩個(gè)無(wú)約束優(yōu)化問題如下:
其中:φ(·)表示從實(shí)空間R到核特征空間H的映射。
定理2 同樣適用于非線性加權(quán)光滑投影孿生支持向量回歸算法,即式(28)和式(29)是連續(xù)可微的嚴(yán)格凸函數(shù),亦可采用具有快速收斂能力的牛頓迭代法進(jìn)行求解。
在線性情況下,采用牛頓迭代法訓(xùn)練加權(quán)光滑投影孿生支持向量回歸算法的過程如下:
輸入懲罰參數(shù)C1和C2,正則化參數(shù)C3和C4,不敏感損失參數(shù)ε,精度ttol,最大迭代次數(shù)imax和訓(xùn)練數(shù)據(jù)集矩陣J
輸出回歸函數(shù)f(x)
步驟1通過式(4)計(jì)算權(quán)值矩陣Wij。
步驟2給定任意初始點(diǎn)和,并令迭代步驟i=0。
步驟3基于和,通過式(19)和式(20)分別計(jì)算和直到
步驟4通過式(27)計(jì)算f(x)。
非線性情況跟線性情況類似,此處省略。
本節(jié)將WSPTSVR 算法的時(shí)間復(fù)雜度與TSVR[12]、STSVR[13]、PTSVR[14]以及快速聚類加權(quán)孿生支持向量回歸(Fast Clustering-based Weighted Twin Support Vector Regression,F(xiàn)CWTSVR)算法[9]進(jìn)行對(duì)比。由于加法的時(shí)間復(fù)雜度遠(yuǎn)小于乘法的時(shí)間復(fù)雜度,因此本文只考慮矩陣乘法運(yùn)算的次數(shù)。另外,核矩陣的求解是所有算法都不可避免的,因此也不作考慮。
PPTSVR、SPTSVR 與TSVR一樣,在對(duì)偶空間中求解二次規(guī)劃問題,其時(shí)間復(fù)雜度為O(n3)。而WSPTSVR 與STSVR 一樣,在原空間中采用牛頓迭代法進(jìn)行求解,由于迭代過程中均為對(duì)角矩陣相乘和對(duì)角矩陣求逆,因此一次迭代的時(shí)間復(fù)雜度為O(n),而牛頓迭代法具有快速收斂能力,因此STSVR與WSPTSVR 算法的時(shí)間復(fù)雜度要小于TSVR及PPTSVR。另外,由于WSPTSVR 算法在目標(biāo)函數(shù)中加入了加權(quán)項(xiàng),因此時(shí)間復(fù)雜度比STSVR 稍大。對(duì)于FCWTSVR,其時(shí)間復(fù)雜度雖然也為O(n3),但是還采用了快速聚類的方法剔除異常點(diǎn),因此時(shí)間復(fù)雜度要大于PPTSVR、SPTSVR 和TSVR。
為了驗(yàn)證WSPTSVR 算法的有效性,將其與TSVR、STSVR、PPTSVR、SPTSVR 以及FCWTSVR分別在基準(zhǔn)測(cè)試數(shù)據(jù)集和人工測(cè)試函數(shù)上進(jìn)行比較。首先對(duì)數(shù)據(jù)集進(jìn)行歸一化處理,然后采用標(biāo)準(zhǔn)的五折交叉驗(yàn)證法將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集。采用RMSE、MAE、ET 這3 個(gè)性能指標(biāo)來(lái)綜合評(píng)價(jià)回歸算法的性能:
通常地,RMSE 的值越小,算法的預(yù)測(cè)性能越好;MSE 的值越小,算法的預(yù)測(cè)誤差越??;ET 的值越小,表明預(yù)測(cè)值與真實(shí)值的一致性越好。一個(gè)好的回歸算法應(yīng)該綜合考量RMSE、MAE 和ET 的值。
此外,還分別統(tǒng)計(jì)了各算法的CPU 運(yùn)行時(shí)間。所有實(shí)驗(yàn)都是在MATLAB 2019a 平臺(tái)上用Intel i5-9400F@2.90 GHz 處理器、16 GB 內(nèi)存的計(jì)算機(jī)完成的,并且所有的實(shí)驗(yàn)結(jié)果均取20 次獨(dú)立運(yùn)行結(jié)果的平均值。
參數(shù)選擇與算法性能密切相關(guān),實(shí)驗(yàn)采用網(wǎng)格搜索法選取最優(yōu)參數(shù)。由于ε1和ε2的設(shè)置對(duì)預(yù)測(cè)性能不會(huì)產(chǎn)生很大影響[13,22-23],因此將ε1和ε2的值都設(shè)置為0.01。在TSVR 中,令C1=C2并且在集合{2i|i=-8,…,0,…,8}中進(jìn)行尋優(yōu)。為了保證算法對(duì)比的公平性[9,24],令STSVR、PPTSVR、SPTSVR 和WSPTSVR 算法中C1=C2、C3=C4,且在集合{2i|i=-8,…,0,…,8}中進(jìn)行尋優(yōu)。此外,在STSVR 和WSPTSVR 算法中,設(shè)置精度ttol=10-6,最大迭代次數(shù)imax=50。在非線性實(shí)驗(yàn)中,核函數(shù)統(tǒng)一采用高斯徑向基函數(shù)K(xi,xj)=參數(shù)σ在集合{2i|i=-5,…,0,…,5}中進(jìn)行尋優(yōu)。
為了對(duì)比各個(gè)算法的綜合性能,將其在7 個(gè)基準(zhǔn)測(cè)試數(shù)據(jù)集上進(jìn)行測(cè)試,使用的基準(zhǔn)測(cè)試數(shù)據(jù)集如表1 所示,其中樣本數(shù)最小為103,最大為9 568,它們可以從UCI 機(jī)器學(xué)習(xí)庫(kù)下載。
表1 實(shí)驗(yàn)中使用的7 個(gè)基準(zhǔn)測(cè)試數(shù)據(jù)集Table 1 Seven benchmark datasets used in the experiments
表2 統(tǒng)計(jì)了各個(gè)算法在7 個(gè)基準(zhǔn)測(cè)試數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果,為了清楚起見,最優(yōu)結(jié)果加粗表示。
由表2 可以看出:1)與PPTSVR 相比,WSPTSVR算法在大多數(shù)數(shù)據(jù)集上有著相似或者更小的RMSE、MAE 和ET,這是由于WSPTSVR 算法采用孤立森林法賦予樣本中的異常點(diǎn)很小的權(quán)值,并通過異常分?jǐn)?shù)賦予每個(gè)樣本點(diǎn)不同的權(quán)值,能夠有效地降低潛在噪聲或異常點(diǎn)對(duì)回歸超平面的影響,從而提升算法的預(yù)測(cè)性能;2)與采用聚類方法去除異常點(diǎn)的FCWTSVR 相比,WSPTSVR 算法在4 個(gè)數(shù)據(jù)集上的RMSE 值最優(yōu),在3個(gè)數(shù)據(jù)集上的MAE值最優(yōu),而FCWTSVR的RMSE、MAE 和ET 值均在3 個(gè)數(shù)據(jù)集上最優(yōu),表明WSPTSVR算法的預(yù)測(cè)性能與當(dāng)前提出的回歸算法相比具有可比性。
在算法的訓(xùn)練時(shí)間方面,WSPTSVR 算法的時(shí)間復(fù)雜度要小于TSVR、PPTSVR 以及SPTSVR,實(shí)驗(yàn)結(jié)果也表明,WSPTSVR 算法的訓(xùn)練速度快于TSVR、PPTSVR 以及SPTSVR。但是由于WSPTSVR 算法在目標(biāo)函數(shù)中引入了權(quán)值矩陣,因此與STSVR 相比,訓(xùn)練速度稍慢。而FCWTSVR 由于采用了快速聚類算法剔除異常點(diǎn),其時(shí)間復(fù)雜度在6 種算法中是最大的,實(shí)驗(yàn)結(jié)果也表明,F(xiàn)CWTSVR 的訓(xùn)練速度最慢。
為了進(jìn)一步驗(yàn)證WSPTSVR 算法在非線性情況下的擬合性能,在sinc(x)函數(shù)上進(jìn)行實(shí)驗(yàn),并且人為添加兩種不同類型的噪聲。sinc(x)函數(shù)的具體形式如下:
其中:xi表示輸入;yi表示對(duì)應(yīng)于xi的輸出;ni表示噪聲。兩種不同類型噪聲的具體形式如下:
其中:U[-0.1,0.1]表示在閉區(qū)間[-0.1,0.1]內(nèi)服從均勻分布;N[0,0.12]表示服從均值為0、方差為0.12的高斯分布。
隨機(jī)生成47 個(gè)混入噪聲的獨(dú)立樣本作為訓(xùn)練樣本和150 個(gè)混入噪聲的獨(dú)立樣本作為測(cè)試樣本。另外,在訓(xùn)練樣本中人為加入3 個(gè)異常點(diǎn)。
表3 給出了2 種不同類型噪聲下6 種回歸算法的平均RMSE、MAE、ET 以及CPU 運(yùn)行時(shí)間,最優(yōu)結(jié)果加粗表示。
表3 6 種回歸算法在人工測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of six regression algorithms on artificial test function
從表3 可以看出:當(dāng)樣本中沒有異常點(diǎn)時(shí),F(xiàn)CWTSVR 和WSPTSVR 的RMSE、MAE 以及ET 值要小于其他4 種回歸算法,表明FCWTSVR 和WSPTSVR 算法具備更好的預(yù)測(cè)性能和抗噪聲能力;當(dāng)樣本中存在異常點(diǎn)時(shí),WSPTSVR 算法的RMSE、MAE 和ET 值均明顯小于PPTSVR,以RMSE為例,WSPTSVR 算法比PPTSVR 平均約小44.2%,表明本文算法在樣本中存在異常點(diǎn)時(shí),有著更好的預(yù)測(cè)性能。這是由于本文算法采用孤立森林法賦予異常點(diǎn)很小的權(quán)值,因此受異常點(diǎn)的影響較小。另外,F(xiàn)CWTSVR 采用聚類的方法剔除樣本中的異常點(diǎn),同樣獲得了較好的預(yù)測(cè)性能。在訓(xùn)練時(shí)間方面,由于WSPTSVR 算法直接在原空間中采用牛頓迭代法進(jìn)行求解,訓(xùn)練速度比TSVR、PPTSVR 和SPTSVR 更快,而與STSVR 相比,由于目標(biāo)函數(shù)中添加了權(quán)值矩陣,因此訓(xùn)練速度稍慢。
圖1 給出了高斯分布噪聲下不同回歸算法在sinc(x)函數(shù)上的擬合曲線。從圖1 可以看出,與PPTSVR 相比,WSPTSVR 算法在噪聲和異常點(diǎn)的干擾下更接近真實(shí)曲線,擬合效果更好。這是由于WSPTSVR 算法采用孤立森林法判斷樣本中的異常點(diǎn),并利用樣本的異常分?jǐn)?shù)賦予噪聲和異常點(diǎn)很小的權(quán)值,從而獲得較好的擬合效果。反觀TSVR、STSVR、PPTSVR 和SPTSVR 在異常點(diǎn)處的擬合曲線扭曲較為明顯,受異常點(diǎn)的影響較大,擬合效果較差。原因是這4 種回歸算法賦予所有樣本點(diǎn)相同的權(quán)值,而異常點(diǎn)的存在迫使擬合曲線偏向異常點(diǎn),從而使得擬合效果變差。另外,F(xiàn)CWTSVR 采用聚類的方法確定并剔除異常點(diǎn),因此在異常點(diǎn)處也獲得了較好的擬合效果。
圖1 高斯分布噪聲下6 種回歸算法的擬合曲線Fig.1 Fitting curves of six regression algorithms under noise with Gaussian distribution
本文提出一種加權(quán)光滑投影孿生支持向量回歸算法。采用孤立森林法判斷樣本中潛在的異常點(diǎn),并通過賦予潛在的異常點(diǎn)很小的權(quán)值,有效地削弱了其對(duì)超平面構(gòu)造的影響。引入Sigmoid 光滑函數(shù),通過在原空間中采用牛頓迭代法求解無(wú)約束優(yōu)化問題,獲得了比雙邊移位投影孿生支持向量回歸算法更快的訓(xùn)練速度。實(shí)驗(yàn)結(jié)果表明,與其他代表性回歸算法相比,該算法受異常點(diǎn)的影響更小,擬合效果更佳。下一步將從尋找逼近能力更優(yōu)的光滑函數(shù)入手,使WSPTSVR 算法獲得更好的擬合性能。