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

卞桂龍, 丁 毅, 沈海斌

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

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

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

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

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

傳感器； 支持向量機(jī)； 殼向量； Learn++算法； 增量學(xué)習(xí)

0 引 言

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

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

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

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

1 殼向量

1.1 殼向量簡介

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

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

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

設(shè)有訓(xùn)練樣本集L(分L+和L-兩類)。

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

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

1.2 殼向量分析

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

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

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

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

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

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

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

輸入：

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

基分類器SVM;

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

訓(xùn)練階段：

fork=1toKdo

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

fort=1toTkdo

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

6)設(shè)Bt=Et/(1-Et)，修改訓(xùn)練樣本集中樣本的權(quán)值

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)設(shè)置

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

為了進(jìn)行比較，對3種不同的算法進(jìn)行了仿真實(shí)驗(yàn)。算法1采用標(biāo)準(zhǔn)的SVM方法，即利用所有的樣本進(jìn)行SVM訓(xùn)練，沒有增量學(xué)習(xí)的過程，記為SVM；算法2是直接對SVM基分類器采用Learn++集成，記為LSVM；算法3則是本文所提的基于殼向量的SVM集成方法，記為QLSVM。算法2和算法3的增量學(xué)習(xí)的過程分別記為LSVM(1),LSVM(2),LSVM(3)和QLSVM(1),QLSVM(2),QLSVM(3)，其集成規(guī)模均設(shè)為4。3種算法各實(shí)驗(yàn)10次取平均值，結(jié)果如表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)隨著增量學(xué)習(xí)的不斷深入，LSVM和QLSVM的分類精度均能得到明顯地提高，有效地證明了采用Learn++算法集成的SVM基分類器具有增量學(xué)習(xí)的能力。2) LSVM在完成所有增量學(xué)習(xí)的過程后其分類精度均優(yōu)于標(biāo)準(zhǔn)的SVM方法，說明采用Learn++集成的SVM基分類器可以通過對訓(xùn)練樣本集的改變來間接地提高基分類器的多樣性，從而起到改善集成分類器分類精度的作用。3) QLSVM的分類精度依賴于樣本集的分布，對于Iris數(shù)據(jù)集和Bupa數(shù)據(jù)集，LSVM和QLSVM的分類精度相當(dāng)；對于Balance數(shù)據(jù)集，QLSVM的分類精度則有所下降。

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

4 結(jié) 論

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

[1] 張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機(jī)[J].自動化學(xué)報,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 增量學(xué)習(xí)算法[J].南京大學(xué)學(xué)報:自然科學(xué)版,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 增量學(xué)習(xí)算法[J].計算機(jī)工程與應(yīng)用,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ī)[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ī)快速增量學(xué)習(xí)算法[J].浙江大學(xué)學(xué)報:工學(xué)版,2006,40(2):202-206.

[16] 張宏達(dá),王曉丹,白冬嬰,等.一種基于凸殼算法的SVM集成方法[J].計算機(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-)，男，江蘇泰州人，碩士研究生，研究方向?yàn)橹悄馨踩c芯片設(shè)計。