（華中科技大學(xué)無錫研究院，江蘇 無錫 214100）

SVM是機(jī)器學(xué)習(xí)中經(jīng)典分類器之一，常被用于解決低維數(shù)據(jù)線性不可分問題，通過核函數(shù)將低維數(shù)據(jù)映射到高維空間，因此在模式識別、小樣本等問題中，SVM有著不可比擬的優(yōu)勢。然而，SVM本身是一個二類分類器，對于多類分類問題，可以通過兩種方法進(jìn)行問題推廣：①通過二次優(yōu)化來描述整個問題；②將一個問題分成多個問題，如：1-a-1、1-a-r、DAGSVM以及SVMDT。

張先武等人分別詳細(xì)闡述了1-a-1、1-a-r、DAGSVM的基本思路：1-a-1是通過投票方法決策，在票數(shù)相同的情況下，存在不可分區(qū)域；1-a-r將N類問題分成N個分類器，在分類過程，分類速度較快，但每次構(gòu)造分類器都要將整個工作集作為訓(xùn)練樣本，訓(xùn)練速度會變慢；DAGSVM是在1-a-1的基礎(chǔ)上提出來的，在分類階段只需要使用N-1個分類器，分類速度比1-a-1和1-a-r都要快，但該方法的泛化能力與有向無環(huán)圖中的位置有關(guān)。Kumar和Jair Cervantes等人在傳統(tǒng)SVM的基礎(chǔ)上，提出使用DT算法在SVM決策邊界上劃分3個類節(jié)點(diǎn)，通過使用參數(shù)來確定數(shù)據(jù)屬于哪類。Anish Jindal等人將SVMDT方法引入到工業(yè)能源分類問題中，準(zhǔn)確率有了很大提高。然而引入來搭建樹結(jié)構(gòu)時存在一個問題，當(dāng)樹根節(jié)點(diǎn)出現(xiàn)分類誤差時，誤差會隨著樹的層數(shù)的增加而積累越多，最終分類結(jié)果與實際結(jié)果之間相差甚遠(yuǎn)。王道明和Shih-Wei Lin等人在此基礎(chǔ)上提出了基于自變異粒子群（PSO）聚類的決策樹SVM的算法，在每個SVM訓(xùn)練前針對每個子節(jié)點(diǎn)通過PSO聚類算法進(jìn)行二分類劃分，確定各子分類器的位置以及訓(xùn)練樣本，該方法以增加訓(xùn)練樣本時間來換取優(yōu)良的分類性能。

雖然通過引入粒子群算法優(yōu)化樹結(jié)構(gòu)，但仍然存在缺陷，PSO算法容易陷入局部最優(yōu)。基于此本文引入模擬退火算法，既保障粒子群算法的全局尋優(yōu)能力，也避免了粒子群算法易陷入局部最優(yōu)，使得模型的訓(xùn)練效果達(dá)到最優(yōu)。

1 支持向量機(jī)決策樹

1．1 支持向量機(jī)

SVM是機(jī)器學(xué)習(xí)中較為常見的方法之一，被廣泛應(yīng)用于分類和回歸問題，它的核心思想就是在正、負(fù)樣本之間尋找最優(yōu)分類超平面。

假設(shè)訓(xùn)練集樣本為(xi, yi)，xi為第i 個樣本數(shù)據(jù)，i = 1,2,...,I ，I為樣本數(shù)，xi∈Rq(R為實數(shù)域，q為輸入數(shù)據(jù)的維度)；yi為第i 個樣本數(shù)據(jù)的類標(biāo)簽，yi∈{- 1 ,+1}。

當(dāng)樣本集線性不可分類時，引入松弛變量ξi(ξi>0)，i = 1,2,...,I ，利用式(1)和(2)求解最優(yōu)分類面。

其約束條件為：

式中：C為懲罰因子，表示目標(biāo)函數(shù)的損失情況；C越大，損失越大。

在以上基礎(chǔ)上引入Lagrange函數(shù)L(w,b,a)為：

式中：a為Lagrange因子。

在低維空間，樣本無法進(jìn)行線性分類時，SVM通過核函數(shù)K(xi, xj)將樣本數(shù)據(jù)xi從低維空間映射到高維空間進(jìn)行線性分類，根據(jù)Mercer條件得到最優(yōu)決策函數(shù)F(xi)：

式中：aj表示a的其中第j個解。

在本文中，選取高斯核函數(shù)K(xi, xj)為：

式中：σ為寬度參數(shù)，控制取值范圍。

1．2 支持向量機(jī)決策樹

SVMDT的核心思想是將多分類問題分解為多個二分類問題，通過比較不同類之間的歐氏距離進(jìn)行分類，距離越大越容易分。將整個樣本集有選擇的分為正樣本集和負(fù)樣本集，分別記為C1和C2，N1和N2分別為C1和C2的類別個數(shù)；N=N1+N2為所有節(jié)點(diǎn)需要劃分的總類別數(shù)；Zn表示第n類樣本，n= 1,2,...,N；Zn的樣本數(shù)為ln。分類器的建立過程如下：

（1）利用式(6)計算出N個類中每個類的樣本中心An為：

式中：zu為Zn中第u個樣本向量。

（2）同樣計算出正、負(fù)樣本集C1和C2的中心e1和e2，并利用式(7)計算C1、C2之間的歐氏距離為：

（3）利用式(8)計算正樣本集中每個類的樣本中心到正樣本集中心e1的平均距離為，負(fù)樣本集中每個類的樣本中心到負(fù)樣本集中心e2的平均距離為，如下式：

式中：Zn∈C1表示Zn是正樣本集中的樣本，則利用式(8)上式計算；否則利用式(8)下式計算。

（4）利用式(9)計算最大距離值d，以此來劃分出類：

（5）重復(fù)上面2到4步，知道所有的類分出來為止。

2 粒子群優(yōu)化的支持向量機(jī)決策樹

SVMDT雖然縮短了訓(xùn)練和分類的時間，提高了分類精度，但在構(gòu)建樹結(jié)構(gòu)時，若根節(jié)點(diǎn)出現(xiàn)分類錯誤，會順著子節(jié)點(diǎn)的延續(xù)而往下積累，最終導(dǎo)致與實際結(jié)果相差很大?；诖耍ㄟ^引入PSO聚類算法來優(yōu)化樹結(jié)構(gòu)，可將數(shù)據(jù)集進(jìn)行最優(yōu)劃分。

2．1 PSO 算法

PSO源于鳥群捕食行為的研究，核心思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。PSO算法需要預(yù)設(shè)類簇個數(shù)，每個粒子代表各類簇的類中心，粒子Xi以及速度Vi如下:

式中：Cij表示第i個粒子所代表的第j個類中心。Vij表示第i個粒子第j類的速度。PSO算法具體流程如下：

（1）設(shè)定進(jìn)化次數(shù)以及種群規(guī)模，初始粒子和速度。

（2）根據(jù)粒子適應(yīng)度函數(shù)f計算每個粒子的適應(yīng)度值，更新個體極值，如式(11)；

式中：je為類內(nèi)離散度之和，N為類的個數(shù)，Pm屬于Cij所在的類。

（3）尋找全局極值和全局極值位置。

（4）根據(jù)式(12)和式(13)更新粒子的位置及速度。

（5）若達(dá)到結(jié)束條件，則輸出最優(yōu)解位置；否則返回2。

2．2 PSO-SVMDT 算法

通過PSO將訓(xùn)練樣本進(jìn)行二分類，生成最優(yōu)決策樹以實現(xiàn)最大樣本分離?；赑SO的SVMDT具體生成步驟如下：

Step1：將整個訓(xùn)練樣本作為初始根節(jié)點(diǎn)，利用PSO算法將初始根節(jié)點(diǎn)劃分為兩類，形成兩個子類點(diǎn)。

Step2：判斷子節(jié)點(diǎn)是都包含一個類，若是轉(zhuǎn)向Step4，否則跳至Step3。

Step3：調(diào)用PSO算法再將節(jié)點(diǎn)劃分為兩個子節(jié)點(diǎn)，跳回Step2。

Step4：節(jié)點(diǎn)為葉子節(jié)點(diǎn)，算法結(jié)束。

3 基于模擬退火的粒子群優(yōu)化的支持向量機(jī)決策樹

3．1 模擬退火算法的原理

模擬退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983年,S.Kirkpatrick等人成功地將退火思想引入組合優(yōu)化領(lǐng)域。它是基于蒙特卡洛迭代求解策略的一種隨機(jī)尋優(yōu)算法[10]。具體算法如下：

Step1：初始化參數(shù)，如Metropolis步長因子、初始溫度、終止溫度、Boltzmann常數(shù)。

Step2：在當(dāng)前解Xi和新的解Xi+1可接受度(P)定義如下：

式中：f表示目標(biāo)方程。Δf=f(Xi+1) -f(Xi)；T是溫度。依照min(P) >R[0,1]，則接受Xi+1。其中R[0,1]表示0到1之間的隨機(jī)數(shù)。

式中：C表示0到1之間的衰減因子。如果滿足收斂條件，則算法結(jié)束，否則返回Step2。

由于有退火溫度T控制著最優(yōu)值的優(yōu)化問題，并且同時以e-Δf/T來接受解。

3．2 基于模擬退火的粒子群優(yōu)化算法

算法的具體步驟如圖1所示。

圖1 SA-PSO算法流程圖

4 實驗驗證與分析

4．1 實驗數(shù)據(jù)選擇

本文實驗所用數(shù)據(jù)參數(shù)包括：時間、速度、電壓、電流、頻率以及當(dāng)前樓層，由于電梯中使用變頻控制，并且每臺電梯在出廠后，運(yùn)行速度曲線都是預(yù)設(shè)好的，而當(dāng)前樓層只是顯示電梯轎廂的位置，因此，通過可視化已有數(shù)據(jù)后發(fā)現(xiàn)不同載重下的電壓不相同，如圖2所示。

圖2 不同載重時上升過程電壓變化曲線

圖3 不同載重時下降過程電壓變化曲線

圖2和圖3中，共五種載重情況，0kg對應(yīng)電梯空載情況，150kg對應(yīng)電梯25%額定載重情況，275kg對應(yīng)電梯50%額定載重情況（半載），380kg對應(yīng)于電梯75%載重情況，550kg對應(yīng)滿載情況。

顯然，不同載重情況可以通過變化曲線反映出來，因此可以通過分離不同電壓變化情況來區(qū)分不同載重情況。選取處理好并已知載重情況的數(shù)據(jù)對本文所提出的改進(jìn)分類算法進(jìn)行驗證。

4．2 實驗仿真

本次仿真是在matlab軟件下進(jìn)行，電腦內(nèi)存6G，CPU2.10GHz，操作系統(tǒng)Win10。測試樣本中載重情況共五類：空載、輕載、半載、重載以及滿載。本文通過對比基于粒子群算法(PSO)、模擬退火算法(SA)、遺傳算法(GA)的分類精度，來驗證本文所提方法在所測數(shù)據(jù)集中的分類效果。

本文所選用SVM核函數(shù)為高斯核函數(shù)，參數(shù)C=100，σ=10。PSO算法的c1=c2=1.5，粒子群的規(guī)模為20，迭代次數(shù)為300，SA初始溫度設(shè)為900℃，終止溫度設(shè)為0.001℃，衰減因子為0.85。將SA-PSO與GA、SA和PSO優(yōu)化算法進(jìn)行對比，結(jié)果如圖4所示。

從圖中可以發(fā)現(xiàn)，SA-PSO優(yōu)化后的算法不僅收斂速度比其它三種優(yōu)化算法的快，而且迭代次數(shù)也是四種算法中最少的，分類精度也高于其他算法，SA-PSO的收斂性能更好。實驗結(jié)果如表1所示。

圖4 PSO與SA-PSO的分類精度比較圖

表1 不同改進(jìn)算法分類結(jié)果比較

由于在實際電梯運(yùn)行過程中，空載運(yùn)行次數(shù)相比于其他四種載重情況的運(yùn)行次數(shù)要多，因此，實驗中以空載情況的分類正確率作為整個算法的分類精度。在表中可以發(fā)現(xiàn)，基于GA算法的分類精度比PSO優(yōu)化算法要高，但訓(xùn)練時間比較長，基于SA算法的訓(xùn)練時間雖然最短，但分類精度較低。本文所提算法所耗時間較短，相比SA和PSO優(yōu)化算法，分類精度有了較大的提高，這也證明了本文所提改進(jìn)算法的可行性。

5 結(jié)語

本文基于粒子群算法尋找全局最優(yōu)能力強(qiáng)以及易陷入局部最優(yōu)的缺陷，提出了一種基于模擬退火的粒子群優(yōu)化算法，相比一些傳統(tǒng)的優(yōu)化算法，在分類精度上有了一定的提高。