一種基于Tsallis熵的最小二乘支持向量機(jī)稀疏算法*

張昌宏，陳 元，曹書豪，程思嘉

（海軍工程大學(xué)，武漢 430033）

一種基于Tsallis熵的最小二乘支持向量機(jī)稀疏算法*

張昌宏，陳 元*，曹書豪，程思嘉

（海軍工程大學(xué)，武漢 430033）

最小二乘支持向量機(jī)（Least Squares Support Vector Machine，LS-SVM）算法是一種優(yōu)化的支持向量機(jī)（Support Vector Machine，SVM）算法，針對該算法稀疏性差，支持向量過多的問題，提出了一種基于Tsallis熵的稀疏算法。分析了最小二乘支持向量機(jī)算法的訓(xùn)練過程，提出了增量算法和Tsallis熵的概念，以此為基礎(chǔ)提出了一種解決算法稀疏性的改進(jìn)算法；最后對算法進(jìn)行了仿真。仿真結(jié)果表明，該改進(jìn)算法相比于傳統(tǒng)算法稀疏性更強(qiáng)，適用于大樣本集的系統(tǒng)辨識。

最小二乘支持向量機(jī)，增量算法，稀疏性，Tsallis熵

0 引言

支持向量機(jī)回歸算法在系統(tǒng)的辨識建模上得到了很好的應(yīng)用，很好地解決了小樣本數(shù)據(jù)辨識問題［1］。但是，在工程上往往需要處理大樣本的實(shí)驗(yàn)集，傳統(tǒng)的支持向量機(jī)算法需要解二次規(guī)劃問題，對于大尺度問題，會面臨維數(shù)災(zāi)難，計(jì)算時(shí)間增長，學(xué)習(xí)速度無法滿足用戶的需求。

為了提高回歸型支持向量機(jī)的訓(xùn)練速度可以從兩方面入手。一個(gè)是改進(jìn)支持向量機(jī)的算法；另一個(gè)是將支持向量機(jī)的訓(xùn)練集先并行處理得到子集的支持向量，再通過規(guī)約的方法求出整個(gè)系統(tǒng)的決策函數(shù)。本文采用第一種方法，引入了最小二乘支持向量回歸算法［2］。

最小二乘支持向量回歸算法（LS-SVR）是采用最小二乘支持向量機(jī)實(shí)現(xiàn)回歸問題的一類算法，該方法可描述為［3］：

其中，φ（x）將數(shù)據(jù)映射到高維空間，以方便解決非線性問題。這里通過f（x）的估計(jì)值來近似實(shí)際輸出y。

最小二乘支持向量回歸算法的優(yōu)化問題如下：

等式約束為

該式對偶問題的Lagrange方程為

其中αk為Lagrange乘子。由KTT優(yōu)化條件得

上式可以改寫成如下線性方程組

可以得到只有b、α的方程組

又因?yàn)樵谑剑?）中

將式（1）代入式（11），得到?jīng)Q策函數(shù)

上述即為最小二乘支持向量回歸算法，決策函數(shù)在輸入下的取值可以作為系統(tǒng)辨識的預(yù)測輸出。采用該算法可以避免求傳統(tǒng)算法中的二次規(guī)劃問題，降低了支持向量機(jī)的計(jì)算復(fù)雜度［4］。

Suykens提出最小二乘支持向量機(jī)算法至今，得益于該算法的運(yùn)算高效性，在各領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用［5-6］。但是隨著大數(shù)據(jù)時(shí)代的來臨，數(shù)據(jù)集規(guī)模和蘊(yùn)含的知識量不斷增長，最小二乘支持向量機(jī)不具有稀疏性的缺點(diǎn)給其應(yīng)用帶來了瓶頸［7］。學(xué)界一直致力于最小二乘法的稀疏性研究，取得了一定的研究成果。Suykens提出了一種修剪算法［6］，通過計(jì)算對結(jié)果的貢獻(xiàn)程度來篩選較大的樣本作為支持向量。該方法要遍歷整個(gè)訓(xùn)練集，開銷很大。Wu等提出了自適應(yīng)算法，通過增量學(xué)習(xí)確定支持向量，減少了稀疏樣本個(gè)數(shù)［8］。Espinoza采用先給定支持向量規(guī)模，然后選擇適當(dāng)?shù)墓ぷ骷牟呗?，提出了相?yīng)算法，并實(shí)現(xiàn)了應(yīng)用［9-10］。本文在此基礎(chǔ)上引入了先增量后減量的篩選方法，實(shí)現(xiàn)了稀疏性的進(jìn)一步將強(qiáng)，實(shí)驗(yàn)效果顯示，該算法決策函數(shù)的預(yù)測準(zhǔn)確率得到了進(jìn)一步的提升。

1 最小二乘支持向量回歸機(jī)增量算法

在最小二乘支持向量回歸機(jī)的回歸決策函數(shù)中，主要的目標(biāo)是求解α和b，求解結(jié)果由式可知

在這其中求解問題就轉(zhuǎn)化為求Φ-1的問題。該問題也可以看作是求解A-1的問題。當(dāng)樣本較小時(shí)，求解A-1較簡單。隨著樣本數(shù)不斷增加，求解A-1的難度不斷增大，導(dǎo)致算法的計(jì)算時(shí)間增加。文獻(xiàn)［11］給出了一種增量式的算法，解決了A-1的求解難題，減少了求解的運(yùn)算量。算法的原理如下：

由式（9）、式（10）可知

可得決策函數(shù)

當(dāng)工作集中增加一個(gè)樣本單元時(shí)，即將（xN+1，yN+1）加入到工作集WN中，新工作集記為WN+1，WN+1為WN的增量集。容易得到

這時(shí)決策函數(shù)為

在這里將該方法稱為增量法。增量法先將樣本集拆分為工作集和非工作集，工作集先進(jìn)行支持向量機(jī)訓(xùn)練，訓(xùn)練后將非工作集中的樣本逐一加入得到新的決策函數(shù)。在新的增量集WN+1中，要得到?jīng)Q策函數(shù)f（x），需要求解，即求解AN+1-1。文獻(xiàn)［12］中提出的引理在這里可以建立和之間的函數(shù)關(guān)系，從而簡化了的求解程序。

由引理可知

由上式可知在求AN+1-1的過程中，只需利用AN-1就可求解，不用重新開始迭代算法，這樣就減少了最小二乘向量機(jī)訓(xùn)練時(shí)間。

2 Tsallis熵

熵（entropy）是一個(gè)用來衡量體系混亂程度的概念［13］。后來香農(nóng)創(chuàng)建了信息論，并將熵的概念引入信息論當(dāng)中，用來研究信息在信道中的傳輸。在信息論中，信息是由一個(gè)所謂的信息源輸出的，（其中P（A）表示事件A發(fā)生的概率）用來度量事件A給出的信息量，則可表示為事件A的自信息量。假設(shè)信息源輸出相互獨(dú)立的消息，每個(gè)消息出現(xiàn)的概率為時(shí)，可以用來度量一個(gè)消息所涵蓋的信息量，則整個(gè)事件的平均信息量是：

H稱為香農(nóng)熵或信息熵。當(dāng)所有狀態(tài)都相同時(shí)，H最大，事件對應(yīng)系統(tǒng)隨機(jī)性最高。當(dāng)某個(gè)狀態(tài)i出現(xiàn)概率為pi=1時(shí)，熵為零，系統(tǒng)為確定性系統(tǒng)。

1957年E.T.Jaynes提出了最大熵的概念，最大熵的主要思想是在一個(gè)未知的分布狀態(tài)下，部分信息已知，要實(shí)現(xiàn)最大的隨機(jī)性，應(yīng)該選取符合信息規(guī)律并且熵最大的模型［14］。以信息熵最大為條件，在其他約束的前提下，可以得到著名的高斯分布。這表明，最大熵是認(rèn)識客觀事物的一個(gè)新角度。

最大熵在問題的實(shí)際應(yīng)用中較為抽象，通過最大熵的特點(diǎn)可以提煉出最大熵的應(yīng)用方法。在實(shí)際問題的研究中首先要把其與信息熵聯(lián)系起來，在把信息熵最大作為研究的有益假設(shè)，以此來獲取想要的問題結(jié)論。這種方法得到的結(jié)果往往更切合實(shí)際。

巴西物理學(xué)家Tsallis提出了一種香農(nóng)熵的廣義形式將概率密度函數(shù)p（x）的q階Tsallis熵［15］定義為

由于Tsallis熵在解決非廣延問題上的優(yōu)勢，本文采取Tsallis熵作為支持向量機(jī)樣本熵的一種評價(jià)標(biāo)準(zhǔn)。以此來度量樣本對于樣本集的貢獻(xiàn)程度，也可以稱為影響程度。

本文根據(jù)實(shí)際問題的需求采用二次Tsallis熵，其表達(dá)式可以表示為

3 基于Tsallis熵的最小二乘回歸向量機(jī)稀疏算法

最大化樣本集的Tsallis熵可以為樣本提供更好的預(yù)測精度，同樣也可以通過最大化Tsallis熵來選取樣本。首先提出一種通過Tsallis熵選取增量樣本作為支持向量的情況：

根據(jù)增量算法，首先將訓(xùn)練集

分為工作集W和增量集Z，其中

劃分訓(xùn)練集之后，利用最小二乘支持向量回歸機(jī)對工作集W進(jìn)行訓(xùn)練，訓(xùn)練后得到?jīng)Q策函數(shù)

在上式中對于所有的αk都有，即所有的樣本都看作支持向量，同時(shí)在增量集中也應(yīng)該有一部分對于決策貢獻(xiàn)較大的支持向量，這里利用Tsallis熵度量這種貢獻(xiàn)度?？梢圆扇∪缦路椒ㄌ崛≡隽考械闹С窒蛄浚?/p>

將增量集中的向量分別加入到工作集中構(gòu)成（n-k）個(gè)臨時(shí)工作集

在上述迭代中，為了減少訓(xùn)練時(shí)間需要設(shè)置停止條件，這里設(shè)置的停止條件和目標(biāo)函數(shù)有關(guān)，目標(biāo)函數(shù)如下

若兩次迭代算法的目標(biāo)函數(shù)值滿足以下條件，則停止迭代。

其中，Qcurrent是本次迭代得到的目標(biāo)函數(shù)值，Qlast是上次迭代得到的目標(biāo)函數(shù)值，ε1是預(yù)先給定的增量停止精度，停止精度可以調(diào)節(jié)支持向量個(gè)數(shù)和精準(zhǔn)度之間的關(guān)系。

在上述方法中最后停止迭代后，工作集W中包含的樣本就是支持向量，通過這種方法極大地增強(qiáng)了算法的稀疏性，但是從中可以看到，在給定的初始化工作集W中，由于其中樣本是隨機(jī)選取，有些樣本可能對工作集的貢獻(xiàn)度較小，不適宜作為支持向量，如果能去掉這一部分樣本，可以使算法的稀疏性更強(qiáng)，這里給出了一種減量算法解決上述問題。

其中，Qcurrent是本次迭代得到的目標(biāo)函數(shù)值，Qlast是上次迭代得到的目標(biāo)函數(shù)值，ε2是預(yù)先給定的減量停止精度。這樣通過減量算法又可以進(jìn)一步增強(qiáng)算法的稀疏性。

綜上所述，本文提出的稀疏性算法流程如下：

Step 1將訓(xùn)練集S分為工作集W和增量集（非工作集）Z；

Step 2采用最小二乘支持向量回歸機(jī)對工作集進(jìn)行訓(xùn)練，得到?jīng)Q策函數(shù)

Step 3將增量集中的每一個(gè)樣本加入工作集中，構(gòu)成臨時(shí)工作集

Step 6通過增量算法的公式可以計(jì)算出新工作集的逆矩陣，得到新的決策函數(shù)

Step 7若算法滿足停止條件則進(jìn)入Step 8，若算法不滿足停止條件，則返回Step 3；

Step 8取工作集W，將工作集中的樣本依次取出，得到l個(gè)減量臨時(shí)工作集

Step 11若算法滿足停止條件，則整個(gè)訓(xùn)練過程結(jié)束，若不滿足停止條件則返回Step 8；

Step 12綜合Step 11所得的支持向量可以得到新的決策函數(shù)

4 方案可行性分析

在本文中為了驗(yàn)證方案的可行性，選擇了傳統(tǒng)最小二乘支持向量機(jī)算法（LS-SVR）、Wu等提出的增量算法（WU-SVR）和本文算法（TS-SVR）進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)運(yùn)行在聯(lián)想Idea Centre K450計(jì)算機(jī)上，內(nèi)存容量8 GB，Intel酷睿i5處理器。實(shí)驗(yàn)中采用C++進(jìn)行編程，在實(shí)驗(yàn)中采用了支持向量機(jī)工具箱svm，作者是Steve Gunn［16］。為了檢驗(yàn)算法的有效性和直觀性，本文采用了3類初等函數(shù)進(jìn)行仿真實(shí)驗(yàn)，分別是：

在本文中核函數(shù)取徑向基核函數(shù)

表1給出了實(shí)驗(yàn)中所用各項(xiàng)參數(shù)的設(shè)定值，θ是相對誤差閾值，實(shí)驗(yàn)相對誤差表示如下：

其中，f（x）代表實(shí)驗(yàn)的結(jié)果，y代表理論上的函數(shù)值。如果e＞θ，則認(rèn)為實(shí)驗(yàn)結(jié)果錯(cuò)誤，反之則認(rèn)為實(shí)驗(yàn)結(jié)果正確。

ε的值決定了系統(tǒng)的終止條件，取值太小影響實(shí)驗(yàn)的精確度，取值過大，實(shí)驗(yàn)的迭代次數(shù)過多，影響實(shí)驗(yàn)的時(shí)間和效率，因此，在實(shí)驗(yàn)中要根據(jù)具體需求設(shè)定取值，這里取ε=0.001。表2給出了各項(xiàng)實(shí)驗(yàn)所得到的數(shù)據(jù)值，并對3種算法進(jìn)行了對比。從第3列可以看出TS-SVR的支持向量個(gè)數(shù)明顯減小，優(yōu)于WU-SVR算法。第4列是實(shí)驗(yàn)的訓(xùn)練時(shí)間數(shù)據(jù)，可以看出WU-SVR的訓(xùn)練時(shí)間最短，TS-SVR由于增減量算法消耗時(shí)間，所以時(shí)間略大于WU-SVR算法，符合實(shí)驗(yàn)預(yù)期。第5列描述了實(shí)驗(yàn)的準(zhǔn)確率，LS-SVR準(zhǔn)確率最高，WU-SVR其次，TS-SVR的準(zhǔn)確率最差，經(jīng)過分析得知，TS-SVR算法由于Tsllias熵的度量方法存在誤差，有一部分支持向量被扔掉，使得算法的決策值受到了損失。最后一列描述了訓(xùn)練的相對誤差，3種算法的相對誤差符合預(yù)期。

表1 實(shí)驗(yàn)參數(shù)設(shè)定值

表2 實(shí)驗(yàn)各項(xiàng)數(shù)據(jù)值

綜上所述，TS-SVR算法增強(qiáng)了最小二乘支持向量回歸機(jī)的稀疏性，訓(xùn)練時(shí)間上增加較小，效率較高，但是決策函數(shù)的準(zhǔn)確率較低。

5 結(jié)論

本文針對最小二乘支持向量機(jī)稀疏性差的問題提出了一種改進(jìn)算法，方案中采用了基于增量算法和減量算法的訓(xùn)練方法，以Tsallis熵為度量，實(shí)現(xiàn)了稀疏性的增強(qiáng)，仿真結(jié)果表明該方案有很好的效果。但在本文的研究中可以看出算法的準(zhǔn)確率較低，不利于該算法的擴(kuò)展，下一步的研究需要著力提高算法的準(zhǔn)確性。

［1］FRANK P M.Fault diagnosis in dynamic systems using analytical and knowledge–based redundancy–a survey and some new results［J］.Automatics，1990，26（3），459-474.

［2］SUYKENS J A K，VANDEWALLE J.Least squares support vector machine classifiers ［J］.Neural Processing Letters，1999，9（3）：293-300.

［3］杜樹新，吳鐵軍.用于回歸估計(jì)的支持向量機(jī)方法［J］.系統(tǒng)仿真學(xué)報(bào)，2004，15（11）：1580-1585.

［4］許建華，張學(xué)工，李衍達(dá).支持向量機(jī)的新發(fā)展［J］.控制與決策，2004，19（5）：481-484.

［5］SUYKENS J A K，De Brabanter J，GESEL T V.Least squares support vector machines［M］.Singaprore：World Scientific，2002.

［6］SUYKENS J A K，De Brabanter J，LUCAS L，et al.Weighted least squares support vector machines：robustness and sparse approximation［J］.Neurocomputing，2002，48（1）：85-105.

［7］ZHAO X H，WANG G，ZHAO K K，et al.On-line least squares support vector machine algorithm in gas prediction［J］.Mining Science and Technology（China），2009，19（2）：194-198.

［8］吳春國.廣義染色體遺傳算法與迭代式最小二乘支持向量機(jī)回歸算法研究［D］.長春：吉林大學(xué)，2006.

［9］ESPINOZA M，SUYKENS J A K，MOOR B D.Load forecasting using fixed-size least squares support vector machines［M］.Berlin：Springer Berlin Heidelberg，2005：1018-1026.

［10］ESPINOZA M，SUYKENS J A K，MOOR B D.Fixed-size least squares support vector machines：a large scale application in electrical load forecasting［J］.Computational Management Science，2006，3（2）：113-129.

［11］張浩然，汪曉東.回歸最小二乘支持向量機(jī)的增量和在線式學(xué)習(xí)算法［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（3）：400-406.

［12］DIAMANTARAS K I，KUNG S Y.Principal component neural networks：theory and applications［M］.New York：John Wiley and Sons，1996.

［13］陳運(yùn).信息論與編碼［M］.北京：電子工業(yè)出版社，2007.

［14］李素建，劉群，楊志峰.基于最大熵模型的組塊分析［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（12）：1722-1727.

［15］TSALLIS C.Possible generalization of Boltzmann-Gibbs statistics［J］.Journal of Statistical Physics，1988，52（1-2）：479-487.

［16］胡良謀，曹克強(qiáng)，徐浩軍，等.支持向量機(jī)故障檢測及控制技術(shù)［M］.北京：國防工業(yè)出版社，2011.

A Sparse Algorithm Based on Tsallis Entropy for Least Squares Support Vector Machine

ZHANG Chang-hong，CHEN Yuan，CAO Shu-hao，Cheng Si-jia，WANG Hui-ping
（Naval University of Engineering，Wuhan 430033，China）

Least squares support vector machine algorithm is an optimizational support vector machine algorithm.Aiming at the poor sparsity of this algorithm，and the problem of too many support vector，a sparse algorithm based on Tsallis entropy is proposed.Firstly，the training process of the least squares support vector machine algorithm is analyzed.And then the concept of incremental algorithm and Tsallis entropy are put forward.Based on this a solution to solve the sparsity of the algorithm is proposed.Finally，the solution is simulated.The simulation results show that，the improved algorithm has more sparse compared to the traditional algorithm，suitable for system identification in large sample sets.

least squares support vector machines，incremental algorithm，sparsity，tsallis entropy

1002-0640（2017）10-0073-06

TP301.6

A

10.3969/j.issn.1002-0640.2017.10.016

2016-08-01

2016-10-26

全軍軍事類研究生課題（2013JY430）；湖北省自然科學(xué)基金資助項(xiàng)目（2015CFA066）

張昌宏（1964- ），男，江蘇揚(yáng)州人，碩士，副教授。研究方向：裝備管理與保障、云計(jì)算存儲技術(shù)。

*通信作者：陳 元（1993- ），男，山東濟(jì)寧人，碩士研究生。研究方向：云儲存安全、密文檢索。