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

（海軍工程大學，武漢 430033）

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

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

（海軍工程大學，武漢 430033）

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

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

0 引言

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

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

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

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

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

等式約束為

該式對偶問題的Lagrange方程為

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

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

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

又因為在式（5）中

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

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

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

1 最小二乘支持向量回歸機增量算法

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

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

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

可得決策函數(shù)

當工作集中增加一個樣本單元時，即將（xN+1，yN+1）加入到工作集WN中，新工作集記為WN+1，WN+1為WN的增量集。容易得到

這時決策函數(shù)為

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

由引理可知

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

2 Tsallis熵

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

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

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

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

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

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

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

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

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

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

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

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

在上式中對于所有的αk都有，即所有的樣本都看作支持向量，同時在增量集中也應該有一部分對于決策貢獻較大的支持向量，這里利用Tsallis熵度量這種貢獻度。可以采取如下方法提取增量集中的支持向量：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 方案可行性分析

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

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

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

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

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

表1 實驗參數(shù)設定值

表2 實驗各項數(shù)據(jù)值

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

5 結(jié)論

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

［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］.系統(tǒng)仿真學報，2004，15（11）：1580-1585.

［4］許建華，張學工，李衍達.支持向量機的新發(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］吳春國.廣義染色體遺傳算法與迭代式最小二乘支持向量機回歸算法研究［D］.長春：吉林大學，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］.計算機學報，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］陳運.信息論與編碼［M］.北京：電子工業(yè)出版社，2007.

［14］李素建，劉群，楊志峰.基于最大熵模型的組塊分析［J］.計算機學報，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］胡良謀，曹克強，徐浩軍，等.支持向量機故障檢測及控制技術(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）；湖北省自然科學基金資助項目（2015CFA066）

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

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