適用于智能傳感器系統(tǒng)的SVM集成研究

卞桂龍, 丁 毅, 沈海斌

(1.浙江大學 超大規(guī)模集成電路設計研究所，浙江 杭州 310027；2.西湖電子集團有限公司，浙江 杭州 310012)

適用于智能傳感器系統(tǒng)的SVM集成研究

卞桂龍1, 丁 毅2, 沈海斌1

(1.浙江大學 超大規(guī)模集成電路設計研究所，浙江 杭州 310027；2.西湖電子集團有限公司，浙江 杭州 310012)

以支持向量機(SVM)為代表的人工智能技術在智能傳感器系統(tǒng)中得到了廣泛的應用，但傳統(tǒng)的SVM有“災難性遺忘”現(xiàn)象，即會遺忘以前學過的知識，并且不能增量學習新的數(shù)據(jù)，這已無法滿足智能傳感器系統(tǒng)實時性的要求。而Learn++算法能夠增量地學習新來的數(shù)據(jù)，即使新來數(shù)據(jù)屬于新的類，也不會遺忘已經學習到的舊知識。為了解決上述問題，提出了一種基于殼向量算法的Learn++集成方法。實驗結果表明：該算法不但具有增量學習的能力，而且在保證分類精度的同時，提高了訓練速度，減小了存儲規(guī)模，可以滿足當下智能傳感器系統(tǒng)在線學習的需求。

傳感器； 支持向量機； 殼向量； Learn++算法； 增量學習

0 引 言

隨著科學技術的發(fā)展，傳感技術得到了迅猛發(fā)展，無論是工業(yè)領域還是日常生活，都應用到了各式各樣的傳感器。傳感器是自動控制系統(tǒng)和智能控制系統(tǒng)的重要器件，自動化和智能化的水平越高，對傳感器的依賴程度也就越高，但傳統(tǒng)的傳感器在性能、可靠性和穩(wěn)定性等方面的瓶頸已經越發(fā)不能滿足工業(yè)生產技術進一步的需求。在20世紀末逐漸成熟起來的以支持向量機(support vector machine,SVM)為代表的人工智能技術為新一代的智能傳感器的發(fā)展指明了方向。Vapnik等人根據(jù)統(tǒng)計學理論提出的SVM學習方法[1]，近年來受到了國內外學術界的廣泛重視，并且已經廣泛應用于智能傳感器系統(tǒng)。如同其他分類器，SVM的性能和精度依賴于訓練數(shù)據(jù)集是否具有典型性。但在現(xiàn)實應用中，獲取這樣典型的數(shù)據(jù)集往往代價昂貴并且費時，因此,得到的數(shù)據(jù)集通常都是來自不同時間段的小的分批量的數(shù)據(jù)集。在這種情況下，典型做法是利用新的數(shù)據(jù)集和先前所有的數(shù)據(jù)集，重新訓練一個新的分類器。換句話說，重新訓練的分類器在從新數(shù)據(jù)那學習新知識時也不能忘記從先前數(shù)據(jù)那獲取的舊知識。但是,學習新知識同時也不能遺忘先前所學過的知識，就會帶來“穩(wěn)定性/可塑性(stability/plasticity)”困境。性能完全穩(wěn)定的分類器可以保留舊知識，但不能學習新知識，而性能完全可塑的分類器可即時學習新知識，但不能保留以前的知識。目前普遍做法是丟棄現(xiàn)有分類器，將舊數(shù)據(jù)集和新數(shù)據(jù)集匯總，利用匯總后的數(shù)據(jù)集訓練一個新的分類器，但是，這種做法就會帶來“災難性遺忘(catastrophic forgetting)”[2]問題，即SVM在保留已有知識的基礎上無法再學習新類，這就會影響智能傳感器系統(tǒng)的穩(wěn)定性。

解決上述問題最好的方法是增量學習。增量學習[3～5]是指在新數(shù)據(jù)可用之時，系統(tǒng)能夠在已有知識的基礎上進行學習，從而快速地獲取新知識并且不丟失已有的有用知識。Learn++算法是由國外學者Polikar R[6]提出的一種用于解決分類問題和監(jiān)督學習的集成式增量學習算法。它能夠增量地學習新來的數(shù)據(jù)，即使新來數(shù)據(jù)屬于新的類，也不會忘記已經學習到的舊知識，較好地解決了“穩(wěn)定性/可塑性”難題。

SVM本質是根據(jù)訓練樣本集構造出最優(yōu)分類超平面，使得樣本集可以被該超平面盡可能正確地分開，并使離超平面最近的向量與超平面之間的距離最大，因此，SVM是無法進行增量學習的，這種特性顯然是不滿足智能傳感器系統(tǒng)實時性要求。其次，SVM是性能穩(wěn)定的分類器，有“災難性遺忘”現(xiàn)象。對于上述問題，國內外學者提出了各種方法用于SVM的增量學習[7～9]。與此同時，不少文獻提出利用分類器集成來實現(xiàn)對SVM分類性能和精度的進一步改進，如Boosting算法和Bagging算法[10～12]。

本文對SVM基分類器采用了Learn++集成，使得集成后的SVM分類器具有增量學習能力，滿足了智能傳感器系統(tǒng)的實時性和穩(wěn)定性。其次，為了提高SVM集成的訓練速度，把殼向量引入到基分類器SVM的訓練過程中，即將殼向量集作為新的訓練樣本集，不但提高了智能傳感器系統(tǒng)的響應速度，而且也減小了智能傳感器系統(tǒng)的存儲規(guī)模。

1 殼向量

1.1 殼向量簡介

SVM的訓練速度主要是由訓練樣本數(shù)量決定的，樣本數(shù)量越多，其訓練速度也就越慢。事實上，訓練樣本集中通常只有很少一部分可能成為支持向量，大多數(shù)訓練樣本都無法成為支持向量，然而這些樣本卻占用了大部分的訓練時間。所以,如果能夠只對那些最有可能成為支持向量的訓練樣本進行訓練，不僅可以提高訓練速度，而且大大減小了訓練樣本集規(guī)模，并且對算法的性能也無太大影響。

訓練樣本集的凸殼是指包含某一類訓練樣本集的最小凸集(一般為多面體)，而殼向量則是該訓練樣本集的凸頂點[13]。殼向量包含了所有的支持向量，而并非所有的殼向量都是支持向量，但支持向量一定是殼向量。如圖1所示， □和○均是訓練樣本集L不同類別的殼向量，支持向量是在殼向量中產生的，不可能是樣本集凸殼內部的樣本點。所以,只要求得殼向量集，并在此樣本集上進行SVM訓練，就可大大縮短訓練時間。

對于一個二分類問題，求取殼向量的算法步驟如下：

設有訓練樣本集L(分L+和L-兩類)。

1)訓練樣本集有線性可分和線性不可分2種情況。若訓練樣本集為線性可分，則直接跳轉到步驟(2)；若訓練樣本集為線性不可分，則通過核函數(shù)將其映射到一個線性可分的特征空間；

3)在此樣本集上進行SVM的訓練，得到SVMVH，并以此構造出最優(yōu)決策函數(shù)。

1.2 殼向量分析

設有訓練樣本集L，維數(shù)為k，樣本個數(shù)為n，則其殼向量個數(shù)mk和樣本數(shù)n之間關系如下[15]：

1)當n→∞ 時，k維球體中均勻獨立地隨機分布n個點，其殼向量個數(shù)mk為O(n(k-1)/(k+1))；

2)當n→∞ 時，若訓練樣本集是呈k維正態(tài)分布的，那么,殼向量個數(shù)mk為O((logn)(k-1)/2) ；

3)當n→∞ 時，若k維空間中的n個樣本點是獨立地從任意連續(xù)分布的集合中隨機選取的，那么,殼向量個數(shù)mk為O((logn)k-1)。

2 基于殼向量的Learn++集成

Learn++算法[6]是一種基于Boosting思想的集成式增量學習算法，它有效地克服了傳統(tǒng)分類算法難以避免的“災難性遺忘”問題。當有新的樣本集加入時，該算法會生成新的基分類器，而最終決策則是利用權重投票方式由所有集成分類器共同完成。為了更好地適應于增量學習，Learn++算法在訓練單個基分類器時，更新樣本權重和賦予分類器權值中使用的都是整個集成分類器的加權預測錯誤，而不是采用當前基分類器的預測錯誤。其次Learn++算法在訓練樣本集上引入了一定的隨機性，從而間接地提高了基分類器的多樣性，使得它不必依賴于特定的基分類器算法。這也就意味著本身不支持增量學習的基分類器可以通過Learn++集成具備增量學習的能力，如SVM。

基于殼向量的Learn++集成是基于以下思路：Learn++算法將初始訓練樣本集D分成了K個訓練樣本子集S(k)，根據(jù)權重分布Dt從當前訓練樣本子集S(k)中隨機選擇訓練集TRt和測試集TEt。利用Qhull算法求取訓練集TRt的殼向量集TRtHV，并將其作為新的樣本集來訓練SVM。每個訓練樣本集S(k)產生Tk個SVM基分類器，最后將所有的SVM基分類器通過權重投票的方式獲得最終集成的SVM。對于一個二分類問題，基于殼向量的Learn++集成方法步驟如下：

輸入：

將初始訓練樣本集D分成K個訓練樣本子集S(k)，其中,k=1,2,…,K。每個訓練樣本子集包含m個訓練樣本，S(k) = [(x1,y1),(x2,y2),……,(xm,ym)];

基分類器SVM;

每個訓練樣本子集S(k)對應的迭代次數(shù)Tk。

訓練階段：

fork=1toKdo

將每個訓練樣本的權值進行初始化，權值w1(i)=D1(i)=1/m，i= 1,2,…,m。其中,w1(i)代表樣本i的權重，m代表樣本集的樣本數(shù)量。

fort=1toTkdo

3)在訓練集TRtHV上訓練基分類器SVM，并得到假設(分類器)ht:X→Y;

6)設Bt=Et/(1-Et)，修改訓練樣本集中樣本的權值

通過以上算法步驟流程可知，對于有著高錯誤率的樣本，從嚴格意義上來說可能是屬于新類或者之前一直未曾用來訓練基分類器。這些被錯分的樣本有著很高的權值，在下次循環(huán)和所有之后的循環(huán)中，會有很高的可能性被重新取樣。而獲取的新基分類器都是建立在這些重新加權過的樣本集上，并且這些新基分類器也會更專注于對這些錯分的樣本進行正確分類，然后再根據(jù)這些新基分類器的分類結果相應地增加或者減小這些樣本的權值。所以,利用Learn++算法集成后的SVM分類器可以有效地進行增量學習，避免了“災難性遺忘”現(xiàn)象的產生。

3 實驗與分析

3.1 實驗數(shù)據(jù)設置

1)UCI數(shù)據(jù)庫中的Iris數(shù)據(jù)集有150個樣本，分三類，將Setosa類作為正類，其它兩類作為負類。隨機選取120個樣本作為訓練集，剩余的30個樣本作為測試集。

2)UCI數(shù)據(jù)庫中的Bupa數(shù)據(jù)集有345個樣本，共兩類。隨機選取294個樣本作為訓練集，剩余的51個樣本作為測試集。

3)UCI數(shù)據(jù)庫中的Balance-scale數(shù)據(jù)集有625個樣本，分三類，將Left類作為正類，其他類作為負類。隨機選取510個樣本作為訓練集，剩余的125個樣本作為測試集。

為了驗證本文所提算法的可行性和有效性，將訓練集隨機平均分成3個訓練樣本子集，其中,Iris3組樣本子集數(shù)目為40,40,40；Bupa3組樣本子集數(shù)目為98,98,98；Balance3組樣本子集數(shù)目為190,190,190。第1組訓練樣本子集作為初始樣本集，其余2組分別作為新增樣本集，每次增量學習完成后用測試集來檢驗分類性能。所有的實驗都是在酷睿雙核 (1.5GHz)，2G內存，Matlab2012b的環(huán)境下進行的。

3.2 實驗結果

為了進行比較，對3種不同的算法進行了仿真實驗。算法1采用標準的SVM方法，即利用所有的樣本進行SVM訓練，沒有增量學習的過程，記為SVM；算法2是直接對SVM基分類器采用Learn++集成，記為LSVM；算法3則是本文所提的基于殼向量的SVM集成方法，記為QLSVM。算法2和算法3的增量學習的過程分別記為LSVM(1),LSVM(2),LSVM(3)和QLSVM(1),QLSVM(2),QLSVM(3)，其集成規(guī)模均設為4。3種算法各實驗10次取平均值，結果如表1和表2所示。

表1 3種算法性能對比Tab 1 Comparison of performance of three kinds of algorithms

表2 LSVM和QLSVM支持向量總數(shù)對比Tab 2 Comparison of total numbers of LSVM and QLSVM

從表1可以看出：1)隨著增量學習的不斷深入，LSVM和QLSVM的分類精度均能得到明顯地提高，有效地證明了采用Learn++算法集成的SVM基分類器具有增量學習的能力。2) LSVM在完成所有增量學習的過程后其分類精度均優(yōu)于標準的SVM方法，說明采用Learn++集成的SVM基分類器可以通過對訓練樣本集的改變來間接地提高基分類器的多樣性，從而起到改善集成分類器分類精度的作用。3) QLSVM的分類精度依賴于樣本集的分布，對于Iris數(shù)據(jù)集和Bupa數(shù)據(jù)集，LSVM和QLSVM的分類精度相當；對于Balance數(shù)據(jù)集，QLSVM的分類精度則有所下降。

從表2可以看出:QLSVM支持向量總數(shù)比LSVM減少了20 %～30 %左右，因此,在分類精度相當?shù)那闆r下其分類決策速度更快，不但加快了訓練速度而且也縮小了訓練集規(guī)模。因此，本文提出的方法是非常有效的。

4 結 論

本文將SVM基分類器利用Learn++算法進行集成，使得集成后的SVM分類器具有增量學習的能力，避免了“災難性遺忘”現(xiàn)象的產生，滿足了智能傳感器系統(tǒng)的穩(wěn)定性和實時性需求。同時將殼向量引入到SVM基分類器的訓練過程，在精度相當?shù)那闆r下，大大提高了集成訓練與分類速度，不但減小了其在智能傳感器系統(tǒng)的存儲規(guī)模，而且也提高了系統(tǒng)的響應速度。另一方面，在增量學習的過程中，Learn++集成分類器規(guī)模是不斷增大的，但集成分類精度并不會一直隨著基分類器數(shù)目的增加而提高，這就牽涉到選擇性集成的問題，關于這方面還需以后的進一步研究。

[1] 張學工.關于統(tǒng)計學習理論與支持向量機[J].自動化學報,2000,26(1):32-42.

[2] French R M. Catastrophic forgetting in connectionist networks[J].Trends in Cognitive Sciences,1999,3(4):128-135.

[3] Giraud-Carrier C.A note on the utility of incremental learning[J].AI Communications,2000,13(4):215-223.

[4] Bouchachia A,Gabrys B,Sahel Z.Overview of some incremental learning algorithms[C]∥2007 IEEE International Fuzzy Systems Conference,IEEE,2007:1-6.

[5] Godin R,Missaoui R.An incremental concept formation approach for learning from databases[J].Theoretical Computer Science,1994,133(2):387-419.

[6] Polikar R,Upda L,Upda S S,et al.Learn++:An incremental learning algorithm for supervised neural networks[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2001,31(4):497-508.

[7] 蕭 嶸,王繼成,孫正興,等.一種 SVM 增量學習算法[J].南京大學學報:自然科學版,2002,38(2):152-157.

[8] Xiao R,Wang J,Zhang F.An approach to incremental SVM learning algorithm[C]∥Proceedings of 2000 12th IEEE International Conference on Tools with Artificial Intelligence,ICTAI 2000.IEEE,2000:268-273.

[9] 吳崇明,王曉丹,白冬嬰,等.基于類邊界殼向量的快速 SVM 增量學習算法[J].計算機工程與應用,2010,46(23):185-187.

[10] Valentini G,Muselli M,Ruffino F.Bagged ensembles of support vector machines for gene expression data analysis[C]∥Procee-dings of the International Joint Conference on Neural Networks, IEEE,2003:1844-1849.

[11] Valentini G,Muselli M,Ruffino F.Cancer recognition with bagged ensembles of support vector machines[J].Neurocompu-ting,2004,56:461-466.

[12] Pavlov D,Mao J,Dom B.Scaling-up support vector machines using boosting algorithm[C]∥Proceedings of 2000 15th International Conference on Pattern Recognition,IEEE,2000:219-222.

[13] 薛貞霞,劉三陽,齊小剛.基于殼向量和中心向量的支持向量機[J].數(shù)據(jù)采集與處理,2009,24(3):328-334.

[14] Barber C B,Dobkin D P,Huhdanpaa H.The quickhull algorithm for convex hulls[J].ACM Transactions on Mathematical Software (TOMS),1996,22(4):469-483.

[15] 李東暉,杜樹新,吳鐵軍.基于殼向量的線性支持向量機快速增量學習算法[J].浙江大學學報:工學版,2006,40(2):202-206.

[16] 張宏達,王曉丹,白冬嬰,等.一種基于凸殼算法的SVM集成方法[J].計算機工程,2008,34(17):28-30.

Research on SVM integration for intelligent sensor system

BIAN Gui-long1， DING Yi2， SHEN Hai-bin1

(1.Institute of VLSI Design,Zhejiang University,Hangzhou 310027,China;2.Westlake Electronics Group Company Limited,Hangzhou 310012,China)

Support vector machine (SVM) as the representative of artificial intelligent techniques has been widely used in the intelligent sensor system,however,traditional SVM suffers from the catastrophic forgetting phenomenon,which results in loss of previously learned information,so it is unable to meet the requirements of real-time intelligent sensor system.The strength of Learn++ lies in its ability to learn new data without forgetting previously acquired knowledge,even when the new data introduce new classes.In order to solve the above problem,a Learn++ integration method based on hull vectors is proposed.Experimental results show that the algorithm not only has the ability of incremental learning,improve training speed and reduce the storage size,but also can ensure the classification precision,which meets the current demand of intelligent sensor systems for online learning.

sensor; support vector machine(SVM); hull vector; Learn++ algorithm; incremental learning

10.13873/J.1000—9787(2014)08—0044—04

2014—01—06

TP 212;TP 18

A

1000—9787(2014)08—0044—04

卞桂龍(1988-)，男，江蘇泰州人，碩士研究生，研究方向為智能安全與芯片設計。