卞桂龍, 丁 毅, 沈海斌

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

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

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

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

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

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

0 引 言

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

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

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

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

1 殼向量

1.1 殼向量簡(jiǎn)介

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

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

對(duì)于一個(gè)二分類(lèi)問(wèn)題，求取殼向量的算法步驟如下：

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

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

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

1.2 殼向量分析

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

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

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

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

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

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

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

輸入：

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

基分類(lèi)器SVM;

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

訓(xùn)練階段：

fork=1toKdo

將每個(gè)訓(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)練基分類(lèi)器SVM，并得到假設(shè)(分類(lèi)器)ht:X→Y;

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

通過(guò)以上算法步驟流程可知，對(duì)于有著高錯(cuò)誤率的樣本，從嚴(yán)格意義上來(lái)說(shuō)可能是屬于新類(lèi)或者之前一直未曾用來(lái)訓(xùn)練基分類(lèi)器。這些被錯(cuò)分的樣本有著很高的權(quán)值，在下次循環(huán)和所有之后的循環(huán)中，會(huì)有很高的可能性被重新取樣。而獲取的新基分類(lèi)器都是建立在這些重新加權(quán)過(guò)的樣本集上，并且這些新基分類(lèi)器也會(huì)更專注于對(duì)這些錯(cuò)分的樣本進(jìn)行正確分類(lèi)，然后再根據(jù)這些新基分類(lèi)器的分類(lèi)結(jié)果相應(yīng)地增加或者減小這些樣本的權(quán)值。所以,利用Learn++算法集成后的SVM分類(lèi)器可以有效地進(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ù)庫(kù)中的Iris數(shù)據(jù)集有150個(gè)樣本，分三類(lèi)，將Setosa類(lèi)作為正類(lèi)，其它兩類(lèi)作為負(fù)類(lèi)。隨機(jī)選取120個(gè)樣本作為訓(xùn)練集，剩余的30個(gè)樣本作為測(cè)試集。

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

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

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

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

為了進(jìn)行比較，對(duì)3種不同的算法進(jìn)行了仿真實(shí)驗(yàn)。算法1采用標(biāo)準(zhǔn)的SVM方法，即利用所有的樣本進(jìn)行SVM訓(xùn)練，沒(méi)有增量學(xué)習(xí)的過(guò)程，記為SVM；算法2是直接對(duì)SVM基分類(lèi)器采用Learn++集成，記為L(zhǎng)SVM；算法3則是本文所提的基于殼向量的SVM集成方法，記為QLSVM。算法2和算法3的增量學(xué)習(xí)的過(guò)程分別記為L(zhǎng)SVM(1),LSVM(2),LSVM(3)和QLSVM(1),QLSVM(2),QLSVM(3)，其集成規(guī)模均設(shè)為4。3種算法各實(shí)驗(yàn)10次取平均值，結(jié)果如表1和表2所示。

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

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

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

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

4 結(jié) 論

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

[1] 張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào),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é)報(bào):自然科學(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] 吳崇明,王曉丹,白冬嬰,等.基于類(lèi)邊界殼向量的快速 SVM 增量學(xué)習(xí)算法[J].計(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] 薛貞霞,劉三陽(yáng),齊小剛.基于殼向量和中心向量的支持向量機(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] 李東暉,杜樹(shù)新,吳鐵軍.基于殼向量的線性支持向量機(jī)快速增量學(xué)習(xí)算法[J].浙江大學(xué)學(xué)報(bào):工學(xué)版,2006,40(2):202-206.

[16] 張宏達(dá),王曉丹,白冬嬰,等.一種基于凸殼算法的SVM集成方法[J].計(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è)計(jì)。