加權光滑投影孿生支持向量回歸算法

徐奔業，顧斌杰，潘豐，熊偉麗

（江南大學 物聯網工程學院，江蘇 無錫 214122）

0 概述

支持向量機（Support Vector Machine，SVM）是20世紀90 年代由VAPNIK［1-2］提出的一種機器學習算法。與傳統的以降低經驗風險為目標的神經網絡相比，SVM的主要思想是最小化結構風險，這使得SVM 具有良好的泛化性能［3-4］。目前，SVM在入侵檢測［5］、圖像處理［6］、故障診斷［7］、干擾識別［8］等領域得到廣泛應用。然而，SVM 在訓練大規模數據集時，存在時間復雜度高導致訓練速度慢的問題［9］。KHEMCHANDANI等［10］提出孿生支持向量機（Twin Support Vector Machine，TSVM）。與SVM 相比，TSVM 僅需求解兩個較小規模的二次規劃問題，因此訓練時間僅為SVM 的1/4 左右。CHEN等［11］提出投影孿生支持向量機（Projection Twin Support Vector Machine，PTSVM）。PTSVM 通過為每個類尋找一個最優投影軸使投影點類內方差最小化，構建分類模型。

PENG［12］把TSVM 的思想用于回歸領域，提出孿生支持向量回歸（Twin Support Vector Regression，TSVR）算法。TSVR 通過求解兩個較小規模的二次規劃問題尋求回歸函數，與傳統SVR 相比，TSVR 具有更好的泛化性能和更快的訓練速度。CHEN等［13］引入Sigmoid光滑函數，對TSVR 的目標函數進行光滑處理，提出光滑孿生支持向量回歸（Smooth Twin Support Vector Regression，STSVR）算法。STSVR 通過求解一對無約束優化問題，獲得了比TSVR 更快的訓練速度。PENG等［14］基于PTSVM 的思想，提出投影孿生支持向量回歸（Projection Twin Support Vector Regression，PTSVR）算法，包括雙邊移位投影孿生支持向量回歸（Pair-shifted PTSVR，PPTSVR）算法和單邊移位投影孿生支持向量回歸（Single-shifted PTSVR，SPTSVR）算法。PTSVR將訓練集中的每個訓練點進行上下移位得到兩個新的移位集，從而利用PTSVM 的思想求解兩個最優超平面的法向量。PPTSVR 和SPTSVR 的主要區別在于，PPTSVR 在兩個移位集上構建回歸函數，而SPTSVR 則是在原始集和一個移位集上構建回歸函數。實驗結果表明，PTSVR 有著比TSVR 更好的預測性能。

然而，PPTSVR 在尋找最優超平面的過程中，將所有訓練樣本對超平面的作用視為相同，沒有反映數據在空間中的分布情況，當訓練樣本中存在異常點時，會削弱算法的擬合性能。本文采用孤立森林法賦予每個訓練樣本不同的權值，通過賦予潛在的異常點很小的權值，削弱異常點對超平面構造的影響，從而提高算法的擬合性能。同時，為了避免在對偶空間中求解二次規劃問題，引入正號函數，將有約束優化問題轉化為不光滑的無約束優化問題，并采用Sigmoid 光滑函數進行光滑處理，提出一種加權光滑投影孿生支持向量回歸（Weighted Smooth Projection Twin Support Vector Regression，WSPTSVR）算法，以證明其任意階光滑且全局收斂的特性，并采用牛頓迭代法進行求解。

1 WSPTSVR 算法

本節首先采用孤立森林法判斷樣本中的潛在異常點，并通過異常分數機制賦予每個樣本不同的權值；其次引入Sigmoid 光滑函數，提出WSPTSVR 算法，并證明其具有全局唯一最優解；最后在原空間中使用牛頓迭代法進行求解。

1.1 基于孤立森林法的加權系數確定

孤立森林法能夠有效地檢測出樣本中的潛在異常點，即使樣本中沒有異常點，也能夠根據異常分數賦予每個樣本相應的權值，從而提高算法的擬合性能［15-17］。孤立森林法首先遞歸地分割給定樣本集，直到每個樣本都被單獨分離出來，然后根據每個樣本分離的路徑長度計算其異常分數，根據異常分數大小判斷樣本是否為異常點并賦予每個樣本點相應的權值。通過孤立森林法確定加權系數共分為以下3 個步驟：

1）通過訓練樣本的子集構建t棵孤立樹，建立孤立森林。

2）在訓練后的孤立森林中，根據每個樣本點分離所需的路徑長度賦予其相應的異常分數Si，Si的取值范圍為0～1，且取值越大，該點為異常點的可能性越大，異常分數Si計算如下：

其中：h(i)為樣本i的路徑長度，即從根節點到葉子節點的邊數，而異常點更容易被孤立，因此h(i)較?。籈(h(i))為樣本i在一組孤立森林中路徑長度的均值；c(n)是樣本數為n時路徑長度的均值，用來標準化樣本i的路徑長度h(i)。c(n)計算如下：

其中：H(n-1)=ln(n-1)+0.577 215 664 9 為調和數。

3）通過孤立森林法中的異常分數機制為每個樣本點賦予相應的權值：

其中：ρi表示第i個樣本的權值。

文獻［15］的研究表明，當樣本點的異常分數Si>0.60 時，即視該樣本點為潛在異常點，應賦予很小的權值，則樣本點的權值矩陣可表示為對角矩陣：

1.2 線性情況

假設訓練集用D={(xi；yi)，i∈Ι={1，2，…，n}}表示，其中，xi∈Rm為輸入，yi∈R為輸出，I為指標集，n為樣本個數，m為樣本特征數。為了后續表示簡單起見，分別用矩陣X=[x1，x2，…，xn]T∈Rn×m和向量Y=[y1，y2，…，yn]T∈Rn表示輸入和輸出，用矩陣J=[X，Y]∈Rn×(m+1)表示訓練樣本，分別用矩陣Aε=[X，Y+εe]和Bε=[X，Y-εe]∈Rn×(m+1)表示上移和下移訓練樣本，其中ε>0 為不敏感因子，e為全1 的列向量。

在雙邊移位投影孿生支持向量回歸算法的目標函數中引入權值矩陣Wij，構造如下最優化問題：

然而，式（5）和式（6）需要在對偶空間中求解二次規劃問題，訓練速度較慢。為了加快訓練速度，采用正號函數將其轉化為無約束優化問題，在原空間中直接進行求解。

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

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

定理1［18］無約束優化問題式（9）和式（10）連續但不光滑。

定理1 表明式（9）和式（10）不光滑，因此無法使用牛頓迭代法等梯度優化方法求解。為此，采用Sigmoid 光滑函數逼近正號函數(x1)+和(x2)+。

Sigmoid 光滑函數p(x，α)定義如下：

其中：α為正常數。

據此可得正號函數(x1)+和(x2)+的Sigmoid 光滑函數分別如下：

將式（12）和式（13）分別代入式（9）和式（10），得到線性情況下加權光滑投影孿生支持向量回歸算法的兩個無約束優化問題，如式（14）、式（15）所示：

引理1［19］若矩陣A∈Rn×n是實對稱矩陣，則A是正定矩陣當且僅當存在矩陣B∈Rm×n使得A=BTB。

定理2式（14）中的P1和式（15）中的P2是嚴格凸函數。

證明對任意的正常數α，P1顯然是連續可微的，以下證明其是嚴格凸函數：

考慮到權值矩陣和對角矩陣都是正定陣，兩者可以分別分解為PTP和QTQ的形式，其中P和Q分別為兩者的平方根矩陣。因此，?2P1(u1)可以分解如下：

其中：C1，C3和α都是正標量；I為正定矩陣。由 引理1 可得?2P1(u1)是正定的，因此P1是嚴格凸函數。同理可證P2也是連續可微的嚴格凸函數。

式（14）和式（15）二階可微，因此可以使用具有快速收斂能力的牛頓迭代法進行求解［20-21］。由定理2 可知式（14）和式（15）是嚴格凸的，因此使用牛頓迭代法求解可以全局收斂，并得到唯一最優解。牛頓迭代法可表示如下：

然后，通過求解式（23）和式（24）兩個無約束最小化問題，可得兩個最優超平面的偏置分別如式（25）、式（26）所示：

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

最終，可得回歸函數如下：

1.3 非線性情況

在非線性情況下，利用核技巧，構造加權光滑投影孿生支持向量回歸算法的兩個無約束優化問題如下：

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

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

1.4 算法步驟

在線性情況下，采用牛頓迭代法訓練加權光滑投影孿生支持向量回歸算法的過程如下：

輸入懲罰參數C1和C2，正則化參數C3和C4，不敏感損失參數ε，精度ttol，最大迭代次數imax和訓練數據集矩陣J

輸出回歸函數f(x)

步驟1通過式（4）計算權值矩陣Wij。

步驟2給定任意初始點和，并令迭代步驟i=0。

步驟3基于和，通過式（19）和式（20）分別計算和直到imax，并通過式（25）和式（26）分別計算偏置b1和b2。

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

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

1.5 時間復雜度分析

本節將WSPTSVR 算法的時間復雜度與TSVR［12］、STSVR［13］、PTSVR［14］以及快速聚類加權孿生支持向量回歸（Fast Clustering-based Weighted Twin Support Vector Regression，FCWTSVR）算法［9］進行對比。由于加法的時間復雜度遠小于乘法的時間復雜度，因此本文只考慮矩陣乘法運算的次數。另外，核矩陣的求解是所有算法都不可避免的，因此也不作考慮。

PPTSVR、SPTSVR 與TSVR一樣，在對偶空間中求解二次規劃問題，其時間復雜度為O(n3)。而WSPTSVR 與STSVR 一樣，在原空間中采用牛頓迭代法進行求解，由于迭代過程中均為對角矩陣相乘和對角矩陣求逆，因此一次迭代的時間復雜度為O(n)，而牛頓迭代法具有快速收斂能力，因此STSVR與WSPTSVR 算法的時間復雜度要小于TSVR及PPTSVR。另外，由于WSPTSVR 算法在目標函數中加入了加權項，因此時間復雜度比STSVR 稍大。對于FCWTSVR，其時間復雜度雖然也為O(n3)，但是還采用了快速聚類的方法剔除異常點，因此時間復雜度要大于PPTSVR、SPTSVR 和TSVR。

2 實驗結果與分析

2.1 實驗設計與參數選擇

為了驗證WSPTSVR 算法的有效性，將其與TSVR、STSVR、PPTSVR、SPTSVR 以及FCWTSVR分別在基準測試數據集和人工測試函數上進行比較。首先對數據集進行歸一化處理，然后采用標準的五折交叉驗證法將數據集劃分為訓練集和測試集。采用RMSE、MAE、ET 這3 個性能指標來綜合評價回歸算法的性能：

通常地，RMSE 的值越小，算法的預測性能越好；MSE 的值越小，算法的預測誤差越?。籈T 的值越小，表明預測值與真實值的一致性越好。一個好的回歸算法應該綜合考量RMSE、MAE 和ET 的值。

此外，還分別統計了各算法的CPU 運行時間。所有實驗都是在MATLAB 2019a 平臺上用Intel i5-9400F@2.90 GHz 處理器、16 GB 內存的計算機完成的，并且所有的實驗結果均取20 次獨立運行結果的平均值。

參數選擇與算法性能密切相關，實驗采用網格搜索法選取最優參數。由于ε1和ε2的設置對預測性能不會產生很大影響［13，22-23］，因此將ε1和ε2的值都設置為0.01。在TSVR 中，令C1=C2并且在集合{2i|i=-8，…，0，…，8}中進行尋優。為了保證算法對比的公平性［9，24］，令STSVR、PPTSVR、SPTSVR 和WSPTSVR 算法中C1=C2、C3=C4，且在集合{2i|i=-8，…，0，…，8}中進行尋優。此外，在STSVR 和WSPTSVR 算法中，設置精度ttol=10-6，最大迭代次數imax=50。在非線性實驗中，核函數統一采用高斯徑向基函數K(xi，xj)=參數σ在集合{2i|i=-5，…，0，…，5}中進行尋優。

2.2 基準測試數據集

為了對比各個算法的綜合性能，將其在7 個基準測試數據集上進行測試，使用的基準測試數據集如表1 所示，其中樣本數最小為103，最大為9 568，它們可以從UCI 機器學習庫下載。

表1 實驗中使用的7 個基準測試數據集Table 1 Seven benchmark datasets used in the experiments

表2 統計了各個算法在7 個基準測試數據集上的實驗結果，為了清楚起見，最優結果加粗表示。

由表2 可以看出：1）與PPTSVR 相比，WSPTSVR算法在大多數數據集上有著相似或者更小的RMSE、MAE 和ET，這是由于WSPTSVR 算法采用孤立森林法賦予樣本中的異常點很小的權值，并通過異常分數賦予每個樣本點不同的權值，能夠有效地降低潛在噪聲或異常點對回歸超平面的影響，從而提升算法的預測性能；2）與采用聚類方法去除異常點的FCWTSVR 相比，WSPTSVR 算法在4 個數據集上的RMSE 值最優，在3個數據集上的MAE值最優，而FCWTSVR的RMSE、MAE 和ET 值均在3 個數據集上最優，表明WSPTSVR算法的預測性能與當前提出的回歸算法相比具有可比性。

在算法的訓練時間方面，WSPTSVR 算法的時間復雜度要小于TSVR、PPTSVR 以及SPTSVR，實驗結果也表明，WSPTSVR 算法的訓練速度快于TSVR、PPTSVR 以及SPTSVR。但是由于WSPTSVR 算法在目標函數中引入了權值矩陣，因此與STSVR 相比，訓練速度稍慢。而FCWTSVR 由于采用了快速聚類算法剔除異常點，其時間復雜度在6 種算法中是最大的，實驗結果也表明，FCWTSVR 的訓練速度最慢。

2.3 人工測試函數

為了進一步驗證WSPTSVR 算法在非線性情況下的擬合性能，在sinc(x)函數上進行實驗，并且人為添加兩種不同類型的噪聲。sinc(x)函數的具體形式如下：

其中：xi表示輸入；yi表示對應于xi的輸出；ni表示噪聲。兩種不同類型噪聲的具體形式如下：

其中：U[-0.1，0.1]表示在閉區間[-0.1，0.1]內服從均勻分布；N[0，0.12]表示服從均值為0、方差為0.12的高斯分布。

隨機生成47 個混入噪聲的獨立樣本作為訓練樣本和150 個混入噪聲的獨立樣本作為測試樣本。另外，在訓練樣本中人為加入3 個異常點。

表3 給出了2 種不同類型噪聲下6 種回歸算法的平均RMSE、MAE、ET 以及CPU 運行時間，最優結果加粗表示。

表3 6 種回歸算法在人工測試函數上的實驗結果Table 3 Experimental results of six regression algorithms on artificial test function

從表3 可以看出：當樣本中沒有異常點時，FCWTSVR 和WSPTSVR 的RMSE、MAE 以及ET 值要小于其他4 種回歸算法，表明FCWTSVR 和WSPTSVR 算法具備更好的預測性能和抗噪聲能力；當樣本中存在異常點時，WSPTSVR 算法的RMSE、MAE 和ET 值均明顯小于PPTSVR，以RMSE為例，WSPTSVR 算法比PPTSVR 平均約小44.2%，表明本文算法在樣本中存在異常點時，有著更好的預測性能。這是由于本文算法采用孤立森林法賦予異常點很小的權值，因此受異常點的影響較小。另外，FCWTSVR 采用聚類的方法剔除樣本中的異常點，同樣獲得了較好的預測性能。在訓練時間方面，由于WSPTSVR 算法直接在原空間中采用牛頓迭代法進行求解，訓練速度比TSVR、PPTSVR 和SPTSVR 更快，而與STSVR 相比，由于目標函數中添加了權值矩陣，因此訓練速度稍慢。

圖1 給出了高斯分布噪聲下不同回歸算法在sinc(x)函數上的擬合曲線。從圖1 可以看出，與PPTSVR 相比，WSPTSVR 算法在噪聲和異常點的干擾下更接近真實曲線，擬合效果更好。這是由于WSPTSVR 算法采用孤立森林法判斷樣本中的異常點，并利用樣本的異常分數賦予噪聲和異常點很小的權值，從而獲得較好的擬合效果。反觀TSVR、STSVR、PPTSVR 和SPTSVR 在異常點處的擬合曲線扭曲較為明顯，受異常點的影響較大，擬合效果較差。原因是這4 種回歸算法賦予所有樣本點相同的權值，而異常點的存在迫使擬合曲線偏向異常點，從而使得擬合效果變差。另外，FCWTSVR 采用聚類的方法確定并剔除異常點，因此在異常點處也獲得了較好的擬合效果。

圖1 高斯分布噪聲下6 種回歸算法的擬合曲線Fig.1 Fitting curves of six regression algorithms under noise with Gaussian distribution

4 結束語

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