徐奔業(yè)，顧斌杰，潘豐，熊偉麗

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122）

0 概述

支持向量機(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ì)無約束優(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)化為不光滑的無約束優(yōu)化問題，并采用Sigmoid 光滑函數(shù)進(jìn)行光滑處理，提出一種加權(quán)光滑投影孿生支持向量回歸（Weighted Smooth Projection Twin Support Vector Regression，WSPTSVR）算法，以證明其任意階光滑且全局收斂的特性，并采用牛頓迭代法進(jìn)行求解。

1 WSPTSVR 算法

本節(jié)首先采用孤立森林法判斷樣本中的潛在異常點(diǎn)，并通過異常分?jǐn)?shù)機(jī)制賦予每個(gè)樣本不同的權(quán)值；其次引入Sigmoid 光滑函數(shù)，提出WSPTSVR 算法，并證明其具有全局唯一最優(yōu)解；最后在原空間中使用牛頓迭代法進(jìn)行求解。

1.1 基于孤立森林法的加權(quán)系數(shù)確定

孤立森林法能夠有效地檢測(cè)出樣本中的潛在異常點(diǎn)，即使樣本中沒有異常點(diǎn)，也能夠根據(jù)異常分?jǐn)?shù)賦予每個(gè)樣本相應(yīng)的權(quán)值，從而提高算法的擬合性能［15-17］。孤立森林法首先遞歸地分割給定樣本集，直到每個(gè)樣本都被單獨(dú)分離出來，然后根據(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)較??；E(h(i))為樣本i在一組孤立森林中路徑長(zhǎng)度的均值；c(n)是樣本數(shù)為n時(shí)路徑長(zhǎng)度的均值，用來標(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ì)角矩陣：

1.2 線性情況

假設(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)化為無約束優(yōu)化問題，在原空間中直接進(jìn)行求解。

由Karush-Kuhn-Tucker（KKT）條件可得：

式（5）和式（6）可改寫為如下無約束優(yōu)化問題：

定理1［18］無約束優(yōu)化問題式（9）和式（10）連續(xù)但不光滑。

定理1 表明式（9）和式（10）不光滑，因此無法使用牛頓迭代法等梯度優(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è)無約束優(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è)無約束最小化問題，可得兩個(gè)最優(yōu)超平面的偏置分別如式（25）、式（26）所示：

在通常情況下，δ1，δ2≠0［14，21］，可得移位函數(shù)f1(x)=-(+b1)/δ1和f2(x)=-(+b2)/δ2。

最終，可得回歸函數(shù)如下：

1.3 非線性情況

在非線性情況下，利用核技巧，構(gòu)造加權(quán)光滑投影孿生支持向量回歸算法的兩個(gè)無約束優(yōu)化問題如下：

其中：φ(·)表示從實(shí)空間R到核特征空間H的映射。

定理2 同樣適用于非線性加權(quán)光滑投影孿生支持向量回歸算法，即式（28）和式（29）是連續(xù)可微的嚴(yán)格凸函數(shù)，亦可采用具有快速收斂能力的牛頓迭代法進(jìn)行求解。

1.4 算法步驟

在線性情況下，采用牛頓迭代法訓(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ì)算和直到imax，并通過式（25）和式（26）分別計(jì)算偏置b1和b2。

步驟4通過式（27）計(jì)算f(x)。

非線性情況跟線性情況類似，此處省略。

1.5 時(shí)間復(fù)雜度分析

本節(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。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)設(shè)計(jì)與參數(shù)選擇

為了驗(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)來綜合評(píng)價(jià)回歸算法的性能：

通常地，RMSE 的值越小，算法的預(yù)測(cè)性能越好；MSE 的值越小，算法的預(yù)測(cè)誤差越?。籈T 的值越小，表明預(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)。

2.2 基準(zhǔn)測(cè)試數(shù)據(jù)集

為了對(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)練速度最慢。

2.3 人工測(cè)試函數(shù)

為了進(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

4 結(jié)束語

本文提出一種加權(quán)光滑投影孿生支持向量回歸算法。采用孤立森林法判斷樣本中潛在的異常點(diǎn)，并通過賦予潛在的異常點(diǎn)很小的權(quán)值，有效地削弱了其對(duì)超平面構(gòu)造的影響。引入Sigmoid 光滑函數(shù)，通過在原空間中采用牛頓迭代法求解無約束優(yōu)化問題，獲得了比雙邊移位投影孿生支持向量回歸算法更快的訓(xùn)練速度。實(shí)驗(yàn)結(jié)果表明，與其他代表性回歸算法相比，該算法受異常點(diǎn)的影響更小，擬合效果更佳。下一步將從尋找逼近能力更優(yōu)的光滑函數(shù)入手，使WSPTSVR 算法獲得更好的擬合性能。