何 麗，韓克平，劉 穎

天津財(cái)經(jīng)大學(xué) 理工學(xué)院，天津 300222

1 引言

隨著現(xiàn)代計(jì)算機(jī)和信息技術(shù)的發(fā)展，數(shù)字信息爆炸式增長(zhǎng)。為了滿足用戶快速準(zhǔn)確的信息查詢需求，分類已經(jīng)成為智能信息檢索的關(guān)鍵技術(shù)之一，且在模式識(shí)別、圖像處理和自然語(yǔ)言處理等領(lǐng)域得到了廣泛應(yīng)用。SVM（support vector machine）算法具有較高的分類準(zhǔn)確率和較好的魯棒性，被廣泛應(yīng)用于解決分類問(wèn)題[1-2]。為了獲得最佳的數(shù)據(jù)分布估計(jì)，傳統(tǒng)SVM算法需要將全部待學(xué)習(xí)數(shù)據(jù)作為訓(xùn)練樣本一起訓(xùn)練。但是，隨著數(shù)據(jù)規(guī)模的指數(shù)級(jí)增長(zhǎng)，實(shí)際應(yīng)用中逐漸增加的數(shù)據(jù)會(huì)產(chǎn)生新的分類需求，傳統(tǒng)SVM分類算法難以滿足這些新的分類需求。增量學(xué)習(xí)方法是解決這些問(wèn)題的有效方法之一。增量學(xué)習(xí)一方面可以根據(jù)增量樣本的特征分布來(lái)動(dòng)態(tài)調(diào)整分類決策函數(shù)，從而保持較高的分類準(zhǔn)確率；另一方面，相較于重新訓(xùn)練一個(gè)系統(tǒng)的時(shí)間成本更低。

SVM訓(xùn)練的最終目的是根據(jù)訓(xùn)練集樣本在特征空間的分布來(lái)確定最優(yōu)超平面，確定最終超平面的樣本被稱為支持向量。在SVM增量學(xué)習(xí)過(guò)程中，最優(yōu)超平面會(huì)隨著訓(xùn)練集中樣本特征空間分布的變化而被動(dòng)態(tài)調(diào)整。因此，如何將最有可能成為新支持向量的樣本加入到增量訓(xùn)練集中是SVM增量學(xué)習(xí)的關(guān)鍵。目前，大多數(shù)基于SVM的增量學(xué)習(xí)算法通過(guò)將更多對(duì)超平面劃分有影響的樣本加入到新訓(xùn)練集中的方法來(lái)改進(jìn)SVM增量訓(xùn)練過(guò)程。Syed等人最早提出了基于SVM的增量學(xué)習(xí)算法[3]，該算法僅保留支持向量樣本，舍棄所有非支持向量的樣本。當(dāng)新樣本加入訓(xùn)練時(shí)，將原支持向量集與新增樣本集合并形成新的訓(xùn)練集。該算法充分考慮了新增樣本對(duì)分類結(jié)果的影響，但是忽略了原訓(xùn)練集中的非支持向量與新增樣本在特征空間分布上可能存在差異，在某些情況下會(huì)導(dǎo)致分類器最終性能下降。文獻(xiàn)[4-5]通過(guò)判斷KKT（Karush-Kuhn-Tucker）條件的方法調(diào)整訓(xùn)練集，在增量學(xué)習(xí)過(guò)程中僅使用不滿足KKT條件的新樣本，忽略了新樣本加入時(shí)最優(yōu)超平面的變化，可能會(huì)造成分類知識(shí)的丟失，導(dǎo)致分類準(zhǔn)確率下降。文獻(xiàn)[6-7]以入侵檢測(cè)為背景，用環(huán)形區(qū)域選擇法和half-partition選擇法構(gòu)建保留集來(lái)選擇初始樣本并進(jìn)行增量訓(xùn)練，但是這種方法會(huì)使加入保留集的樣本存在冗余或漏選的現(xiàn)象。李妍坊等人[8]在文獻(xiàn)[6-7]的基礎(chǔ)上，提出了基于縮放平移選擇法構(gòu)建保留集的方法，同時(shí)將部分新增樣本加入到保留集中，該算法縮小了保留集的選取范圍，但是仍未解決保留集冗余的問(wèn)題。Zheng等人[9]提出了一種基于學(xué)習(xí)原型和支持向量的在線增量SVM算法，該算法不僅支持樣本增量學(xué)習(xí)，而且支持類別增量學(xué)習(xí)。劉國(guó)欣[10]通過(guò)將增量樣本的邊界向量與原樣本的邊界向量進(jìn)行合并，形成增量學(xué)習(xí)的訓(xùn)練集，該算法在提取邊界向量時(shí)重復(fù)計(jì)算不同類別樣本之間的距離，導(dǎo)致時(shí)間復(fù)雜度較高。Li等人[11]提出了一種基于超平面距離的SVM增量學(xué)習(xí)算法，該算法根據(jù)支持向量的幾何特征，利用超平面距離提取樣本，選擇最有可能成為支持向量的樣本形成邊界向量集，但是該算法沒有考慮到新增樣本和原始樣本在增量學(xué)習(xí)訓(xùn)練中對(duì)模型影響的差異性。

上述這些SVM增量學(xué)習(xí)算法雖然獲得了較好的分類性能，但是存在樣本冗余和信息缺失等問(wèn)題，可能造成分類器性能不穩(wěn)定或者訓(xùn)練時(shí)間效率較低。本文根據(jù)SVM結(jié)構(gòu)化風(fēng)險(xiǎn)最小的優(yōu)化目標(biāo)，提出了一種基于超平面幾何距離的自適應(yīng)SVM增量學(xué)習(xí)算法，該算法根據(jù)樣本到超平面的幾何距離，以不同的權(quán)重篩選出新增樣本和原始樣本集中包含分類知識(shí)的樣本。該算法能夠在保持較好分類準(zhǔn)確率和魯棒性的前提下，有效控制參與增量訓(xùn)練的樣本規(guī)模，從而減少SVM增量學(xué)習(xí)的訓(xùn)練時(shí)間。

2 SVM理論基礎(chǔ)

SVM分類器訓(xùn)練目標(biāo)是在特征空間中找到一個(gè)最優(yōu)超平面，使訓(xùn)練樣本的分類間隔最大[1]。假設(shè)給定訓(xùn)練數(shù)據(jù)集為 {(xi,yi)},i=1,2,…,n,xi∈Rm,yi∈{+1,-1}。則設(shè)超平面方程為：

在實(shí)際問(wèn)題中有些數(shù)據(jù)會(huì)存在噪聲，出現(xiàn)離群點(diǎn)，為了降低離群點(diǎn)對(duì)分類模型的影響，引入“松弛變量”ξi≥0，用以表征樣本點(diǎn)xi偏離函數(shù)間隔的程度。同時(shí)，為了最大化間隔同時(shí)保證誤分點(diǎn)個(gè)數(shù)最少，引入一個(gè)常數(shù)C＞0作為懲罰參數(shù)，可將優(yōu)化問(wèn)題描述為：

其對(duì)偶問(wèn)題為：

其中，αi為拉格朗日乘子。通過(guò)求對(duì)偶問(wèn)題的最優(yōu)解α=[α1α2…αn]，使得每個(gè)樣本都滿足優(yōu)化問(wèn)題的KKT條件：

從KKT條件的定義可以看出，αi=0時(shí)，其樣本對(duì)決策函數(shù)沒有影響；αi＞0時(shí)，對(duì)應(yīng)的樣本為支持向量。

由此可知，只有訓(xùn)練集中的支持向量對(duì)分類超平面有影響，因此，在訓(xùn)練集不變的情況下，支持向量集和訓(xùn)練集是等價(jià)的。但是，新增樣本加入時(shí)，可能會(huì)導(dǎo)致這種等價(jià)關(guān)系的破裂。根據(jù)文獻(xiàn)[12]的研究結(jié)果，當(dāng)新增樣本全部滿足KKT條件時(shí)，新增樣本的加入不會(huì)影響當(dāng)前的支持向量集，分類器的決策函數(shù)不會(huì)發(fā)生改變；若存在不滿足KKT條件的新增樣本時(shí)，支持向量集會(huì)發(fā)生改變，當(dāng)前分類器的決策函數(shù)也會(huì)隨之發(fā)生變化。文獻(xiàn)[13]也提出，當(dāng)新增樣本中存在違背當(dāng)前分類器KKT條件的樣本時(shí)，原始樣本集中的非支持向量有可能在增量訓(xùn)練中轉(zhuǎn)化為支持向量。

圖1中用S0表示原始訓(xùn)練集，S1表示新增樣本集，原樣本集中靠近超平面1/3處的樣本用黑色圓圈標(biāo)出，用與分類超平面平行的紅色直線劃出距離超平面1/3處樣本與超平面之間的樣本。其中，（a）表示新增樣本集與原始樣本集分布基本一致時(shí)的分類超平面的變化，（b）表示新樣本集與原始樣本集的數(shù)據(jù)分布變化較大時(shí)的分類超平面的變化情況。從圖中可以看出，新增樣本的數(shù)據(jù)分布對(duì)原模型的分類超平面有直接影響。

Fig.1 New samples influence on SVM classification圖1 新增樣本對(duì)SVM分類面的影響

在圖（a）中，由于新樣本集中不滿足原模型KKT條件的樣本較少，因此在新樣本集S1加入后，分類超平面的偏轉(zhuǎn)較小，并且，原模型訓(xùn)練集S0中距離超平面較近的部分非支持向量變成了支持向量。

在圖（b）中，新樣本集S1加入后，由于新樣本集的數(shù)據(jù)分布變化較大，使得分類超平面的偏轉(zhuǎn)較大。并且，從圖中可以看出，新樣本集中滿足原模型KKT條件的部分樣本也變成了新模型的支持向量。

同時(shí)，從圖1中可以看出，在增量過(guò)程中，樣本成為新支持向量的可能性與其到超平面的幾何距離有關(guān)。在超平面發(fā)生偏轉(zhuǎn)后，原模型非支持向量集中轉(zhuǎn)化為新模型支持向量的樣本，大都位于原樣本集中靠近超平面1/3處的樣本與分類超平面之間。

3 自適應(yīng)的SVM增量學(xué)習(xí)算法

根據(jù)樣本的空間分布特征以及支持向量集的變化規(guī)律，本文提出了一種自適應(yīng)的SVM增量學(xué)習(xí)算法（self-adaptive incremental support vector machine，SD-ISVM）。該算法以增量樣本和新增樣本空間分布的相似性為調(diào)整系數(shù)，分別為原訓(xùn)練集和增量樣本集設(shè)置不同的篩選閾值，并根據(jù)樣本到超平面的幾何距離確定邊界向量。

定義1（幾何距離） 給定樣本集D={(xi,yi),i=1,2,…,n},xi∈Rm,yi∈{+1,-1}和超平面 (w,b)，樣本點(diǎn) (xi,yi)到超平面(w,b)的幾何距離γi的計(jì)算方法如式（5）。

3.1 原模型保留集構(gòu)建方法

在現(xiàn)有的增量SVM算法中，許多學(xué)者在進(jìn)行增量學(xué)習(xí)時(shí)，都會(huì)考慮到原模型中非支持向量樣本，但是大部分算法沒有考慮增量情況的不同，而且保留方法比較復(fù)雜，從而造成算法效率偏低。實(shí)際上，當(dāng)原始樣本集與新增樣本集的分布相似時(shí)，原樣本集中的邊界向量在新模型支持向量中占比較高；反之，原始樣本集中的邊界向量在新模型支持向量中占比較低。在增量過(guò)程中，原模型中非支持向量成為新模型支持向量的可能性與其到超平面的幾何距離的大小有關(guān)，并且從圖1的支持向量變化情況分析可知，原始樣本集中的邊界向量大都在距離超平面幾何距離1/3處的樣本與原模型的分類超平面之間。為此，本文選擇樣本到超平面的幾何距離作為篩選條件來(lái)構(gòu)建原模型保留集。在設(shè)定原模型保留集的篩選閾值時(shí)，根據(jù)原樣本集和新增樣本集的分布變化情況，使用sim函數(shù)來(lái)實(shí)現(xiàn)閾值的動(dòng)態(tài)變化，以減少原樣本保留集的冗余。

為方便表達(dá)，令原始樣本集中正例樣本到超平面幾何距離的集合為，原樣本集中負(fù)例樣本到超平面幾何距離的集合為，且集合中樣本按γi的升序排列，D0為的并集。同樣地，新增樣本集中正例樣本到超平面幾何距離的集合為，新增樣本集中負(fù)例樣本到超平面幾何距離的集合為，且集合中樣本均按γi值升序排列，D1為的并集，m和n分別為集合中樣本的總數(shù)，。為了適應(yīng)樣本空間分布的變化，引入了自適應(yīng)閾值θold，計(jì)算方法如式（6）。

其中，σ0和σ1分別為D0和D1上的樣本總體方差；sim()是新舊樣本在特征空間分布的相似度計(jì)算函數(shù)，定義如下：

當(dāng)增量樣本中出現(xiàn)不滿足KKT條件的樣本時(shí)，從原模型的非支持向量集中保留距離超平面幾何距離小于等于θold的樣本，加入到原模型的保留集中。

當(dāng)篩選閾值設(shè)定的距離過(guò)大時(shí)，會(huì)造成保留集中樣本冗余，而設(shè)定的距離過(guò)小時(shí)，則可能丟失有用的分類知識(shí)。根據(jù)前面的分析，這里分別使用集合中靠近超平面1/3處的樣本與對(duì)應(yīng)集合中最靠近超平面的樣本之間差值的平均來(lái)計(jì)算θold。其中，sim函數(shù)根據(jù)特征空間分布相似性來(lái)控制θold。為保持分類器的穩(wěn)定性，當(dāng)sim函數(shù)的值越大時(shí)，需要從原模型中保留的樣本數(shù)量就會(huì)越多；反之，當(dāng)原樣本和新樣本在特征空間的相似度越高，即sim函數(shù)的值越小時(shí)，需要保留的樣本數(shù)量就會(huì)減少。

3.2 新增樣本保留集構(gòu)建

目前流行的增量SVM算法在增量訓(xùn)練時(shí)大多選擇舍棄新增樣本中滿足KKT條件的樣本，但是，從圖1的分析可知，當(dāng)新增樣本中存在不滿足原模型KKT條件的樣本時(shí)，當(dāng)前的SVM決策超平面和支持向量集都會(huì)受到影響，新增樣本中滿足原模型KKT條件的樣本也可能會(huì)成為新模型的支持向量。文獻(xiàn)[6]雖然考慮了這部分樣本的保留問(wèn)題，但是沒有根據(jù)新增樣本滿足原模型KKT條件的具體情況進(jìn)行討論，并且這些文獻(xiàn)中大都使用固定閾值進(jìn)行樣本篩選，這樣可能會(huì)造成新增樣本保留集的過(guò)度冗余，從而影響模型的泛化性能和效率。同時(shí)，當(dāng)新增樣本中滿足原模型KKT條件的比例不同時(shí)，分類超平面的偏轉(zhuǎn)情況也是不同的。針對(duì)這一情況，本文在確定新樣本保留集時(shí)，設(shè)置了動(dòng)態(tài)的新樣本篩選閾值θinc，以適應(yīng)不同增量特征分布的變化情況，θinc的計(jì)算方法如式（8）。

其中，σ0和σ1分別為D0和D1上的樣本總體方差；λ為基于當(dāng)前模型分類準(zhǔn)確率的調(diào)整系數(shù)，定義為：

式中，r為增量樣本中符合原模型KKT條件的樣本數(shù)占增量樣本總數(shù)的比例，表示增量樣本被正確分類的比例，l和k分別為集合中樣本的總數(shù)，。

考慮到新增樣本是首次參與SVM訓(xùn)練，相比于原模型樣本保留集的構(gòu)造，對(duì)新增樣本保留集的構(gòu)建，分別使用集合中靠近超平面3/4處的樣本與對(duì)應(yīng)集合中最靠近超平面的樣本之間差值的平均來(lái)計(jì)算θinc。

當(dāng)增量樣本中出現(xiàn)不滿足KKT條件的樣本時(shí)，保留增量樣本集中滿足KKT條件且超平面幾何距離小于等于閾值θinc的樣本。

由圖1可以看出，增量樣本中滿足KKT條件的樣本越多，即r越大，新模型的分類超平面發(fā)生的偏轉(zhuǎn)越小，增量樣本中包含新分類知識(shí)的樣本就越少，因此，需要保留的樣本就越少；反之，增量樣本中滿足KKT條件的樣本越少，即r越小，新模型的分類超平面發(fā)生的偏轉(zhuǎn)越大，增量樣本中包含新分類知識(shí)的樣本就越多，最后需要保留的樣本就越多。為適應(yīng)r的變化，這里使用λ動(dòng)態(tài)調(diào)整篩選閾值θinc，當(dāng)r變大時(shí)，λ減小，θinc也隨之減小，使得保留的樣本數(shù)減少；反之，增大λ，使保留的樣本數(shù)增加。

3.3 自適應(yīng)的SVM增量學(xué)習(xí)算法

本文根據(jù)特征空間分布的相似性和樣本到超平面的距離，同時(shí)保留原樣本集和新增樣本集中滿足KKT條件的樣本蘊(yùn)含的分類知識(shí)，提出了一種新的SVM增量學(xué)習(xí)算法SD-ISVM。SD-ISVM的算法描述如下：

輸入：原樣本集X0，新增樣本X1，當(dāng)前原分類模型Ω0。

輸出：增量學(xué)習(xí)后的模型Ω。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文提出算法的可行性和有效性，使用了4個(gè)不同領(lǐng)域的開放數(shù)據(jù)集：APS、Mushroom、Bank和KDD Cup。實(shí)驗(yàn)中將每個(gè)訓(xùn)練集隨機(jī)分為10份，將其中的1份作為原始訓(xùn)練集，其余作為新增樣本集1～9進(jìn)行增量，并對(duì)每一次增量訓(xùn)練產(chǎn)生的分類模型在測(cè)試集上進(jìn)行測(cè)試。各數(shù)據(jù)集的訓(xùn)練樣本、測(cè)試樣本個(gè)數(shù)和特征維度、正負(fù)樣本比例和各增量數(shù)據(jù)集與訓(xùn)練數(shù)據(jù)集正、負(fù)類特征中心距離的均值如表1所示。

Table 1 Experimental datasets表1 實(shí)驗(yàn)數(shù)據(jù)集

由表1可知，各個(gè)數(shù)據(jù)集上，新增樣本集與訓(xùn)練數(shù)據(jù)集的特征分布存在一定的差異，尤其是APS的正、負(fù)類樣本比例與特征空間分布都表現(xiàn)出明顯的不平衡性，且正類增量樣本在特征分布上的變化較大。為驗(yàn)證SD-ISVM算法的有效性和泛化性能，本文使用上述幾種不同特性的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，同時(shí)使用KKT-ISVM（Karush Kuhn Tucher-incremental support vector machine）[4]、CRS-ISVM（combined reserved set-incremental support vector machine）[8]、HD-ISVM（hyperplane distance-incremental support vector machine）[11]算法作為對(duì)比實(shí)驗(yàn)項(xiàng)。實(shí)驗(yàn)環(huán)境為24 GHz的Xeon e5-2630處理器，16 GB內(nèi)存，軟件環(huán)境采用python 2.7.13。

4.2 性能評(píng)估

分類器的性能度量是對(duì)分類器的分類性能和泛化能力的評(píng)估，常用的評(píng)價(jià)指標(biāo)主要包括：正確率、召回率、敏感性、特異性等。AUC（area under curve）是一種結(jié)合敏感性和特異性的性能評(píng)價(jià)指標(biāo)。PACBayes（probably approximately correct learning-Bayes）邊界是分類器上最緊的泛化邊界，能夠用來(lái)評(píng)價(jià)學(xué)習(xí)算法的泛化性能[14-18]。本文使用PAC-Bayes邊界和AUC對(duì)SVM增量學(xué)習(xí)過(guò)程中產(chǎn)生的分類器泛化性能進(jìn)行驗(yàn)證和分析。

4.2.1 準(zhǔn)確率和AUC

準(zhǔn)確率表示被正確分類的樣本占總樣本的百分比。準(zhǔn)確率越高，分類器的性能越好。正確率評(píng)價(jià)指標(biāo)ACC的計(jì)算方法如式（10）。

其中，TP、FP、TN和FN分別表示真陽(yáng)性、假陽(yáng)性、真陰性和假陰性的樣本數(shù)量。

AUC表示“受試者工程特征”（receiver operating characteristic，ROC）曲線下方的面積。AUC的值越大，分類器的性能越好。假定ROC曲線是由坐標(biāo)為{(x1,y1),(x2,y2),…,(xm,ym)}的點(diǎn)按序連接而形成的(x1=0,xm=1)，則AUC計(jì)算方法如式（11）。

4.2.2 泛化誤差邊界

PAC-Bayes理論融合了Bayes定理和隨機(jī)分類器的優(yōu)勢(shì)，能夠?yàn)楦鞣N學(xué)習(xí)算法提供最緊的泛化誤差邊界[14]。根據(jù)文獻(xiàn)[14]的PAC-Bayes定理，PAC-Bayes邊界越低，分類器的真實(shí)誤差越小，分類器的泛化性能會(huì)越好。因此，本文使用PAC-Bayes邊界來(lái)衡量SVM增量學(xué)習(xí)模型的泛化風(fēng)險(xiǎn)邊界。

4.3 實(shí)驗(yàn)結(jié)果及分析

4.3.1 穩(wěn)定性對(duì)比

圖2描述了不同算法在不斷加入增量樣本后AUC的變化情況，曲線的波動(dòng)越大，表示算法的性能越不穩(wěn)定；反之，說(shuō)明穩(wěn)定性越好。從圖2中可以看出，相比于其他3個(gè)數(shù)據(jù)集的AUC值能夠快速穩(wěn)定在較好的水平，APS數(shù)據(jù)集在前4次增量訓(xùn)練過(guò)程中出現(xiàn)了明顯波動(dòng)。造成這種波動(dòng)的原因是，APS數(shù)據(jù)集中的正負(fù)樣本比例和增量樣本特征空間分布均處于極不平衡狀態(tài)。即使在這種極不平衡的情況下，本文提出的SD-ISVM算法仍然能得到一個(gè)穩(wěn)定且分類性能良好的超平面，這是其他幾種對(duì)比算法不能達(dá)到的。

Fig.2 Contrast ofAUC圖2 AUC對(duì)比

對(duì)比各種算法在4個(gè)數(shù)據(jù)集上的AUC曲線可以發(fā)現(xiàn)，SD-ISVM算法在每個(gè)數(shù)據(jù)集上的AUC值總體上表現(xiàn)最好。分析原因主要是因?yàn)镾D-ISVM算法在樣本保留的過(guò)程中，使用了支持向量的空間特征和增量過(guò)程中超平面的變化情況，盡可能地保留了新舊樣本中對(duì)分類決策函數(shù)有貢獻(xiàn)的樣本，彌補(bǔ)了其他算法在增量過(guò)程中分類知識(shí)丟失的問(wèn)題，從而獲得了較好的穩(wěn)定性。這說(shuō)明本文提出的SD-ISVM算法具有更好的分類性能。

4.3.2 泛化能力對(duì)比

表2為各種算法在不同數(shù)據(jù)集上增量學(xué)習(xí)得到的模型PAC-Bayes最優(yōu)邊界值和分類準(zhǔn)確率，PBB（PAC-Bayes bound）表示PAC-Bayes最優(yōu)邊界。分類準(zhǔn)確率和PAC-Bayes邊界有很高的負(fù)相關(guān)性，即分類準(zhǔn)確率越高，PAC-Bayes邊界會(huì)越低。對(duì)SVM算法來(lái)說(shuō)，PAC-Bayes邊界越低，算法的分類邊界會(huì)越緊，分類器的泛化性能越好。分類準(zhǔn)確率與PACBayes邊界的和越接近1，模型的分類效果越好。從表2中可以看出，在大部分?jǐn)?shù)據(jù)集上，各算法的分類準(zhǔn)確率與PBB之和均接近于1。在分類準(zhǔn)確率相同時(shí)，CRS-ISVM、KKT-ISVM和HD-ISVM算法的PACBayes最優(yōu)邊界都稍大于SD-ISVM算法。以上說(shuō)明，SD-ISVM算法的模型泛化性能與其他算法基本保持一致，甚至?xí)谀承?shù)據(jù)集上高于其他算法。

Table 2 Contrast of classification accuracy and PBB表2 分類準(zhǔn)確率和PBB對(duì)比

4.3.3 訓(xùn)練時(shí)間對(duì)比

圖3描述不同算法在各個(gè)數(shù)據(jù)集上增量訓(xùn)練時(shí)間對(duì)比情況。從圖中可以看出，在APS和Bank數(shù)據(jù)集上分類時(shí)間最長(zhǎng)的算法是KKT-ISVM，這是由于KKT-ISVM算法在進(jìn)行增量時(shí)需要多次訓(xùn)練分類器；在Mushroom和KDD Cup數(shù)據(jù)集上CRS-ISVM算法分類耗時(shí)最多，是其他算法的2～3倍，這是因?yàn)镃RSISVM算法計(jì)算保留集的時(shí)間復(fù)雜度不會(huì)隨著數(shù)據(jù)集的復(fù)雜度降低而減少。同時(shí)可以看出，在大多數(shù)數(shù)據(jù)集上，本文提出的SD-ISVM算法都獲得了較好的結(jié)果。SD-ISVM在增量學(xué)習(xí)訓(xùn)練集構(gòu)建時(shí)，可以根據(jù)新舊數(shù)據(jù)集在特征空間分布的相似度變化自動(dòng)調(diào)整新舊樣本的篩選閾值，適應(yīng)增量樣本在特征空間分布的變化，從而有效地控制增量學(xué)習(xí)訓(xùn)練的規(guī)模，提高分類器訓(xùn)練的速度。

從上述的實(shí)驗(yàn)結(jié)果對(duì)比可以看出，在所有實(shí)驗(yàn)數(shù)據(jù)集上，相比于其他三種典型的SVM增量學(xué)習(xí)算法，本文提出的SD-ISVM算法在模型的穩(wěn)定性、泛化能力和訓(xùn)練時(shí)間上總體上保持了較明顯的優(yōu)勢(shì)。相比于其他幾種算法，SD-ISVM算法不僅解決了有貢獻(xiàn)樣本丟失問(wèn)題，還有效減少了樣本冗余，加快了增量學(xué)習(xí)的速度。

5 總結(jié)

針對(duì)現(xiàn)有的SVM增量學(xué)習(xí)算法在增量過(guò)程中分類知識(shí)丟失以及時(shí)間效率偏低的問(wèn)題，提出了一種基于特征空間分布的SD-ISVM算法，該算法不僅保留了原始樣本集和增量樣本集中滿足KKT條件的邊界樣本，還根據(jù)新舊樣本在特征空間分布的變化情況，從新舊樣本集中篩選出滿足KKT條件但可能在增量學(xué)習(xí)過(guò)程中轉(zhuǎn)變?yōu)橹С窒蛄康臉颖緟⑴c訓(xùn)練，以減少新增樣本加入時(shí)分類知識(shí)的丟失，并控制參與增量學(xué)習(xí)的邊界樣本數(shù)量，來(lái)提高分類速度。實(shí)驗(yàn)結(jié)果表明，本文提出的SD-ISVM算法能夠在保持較好分類準(zhǔn)確率的前提下，獲得更好的穩(wěn)定性和SVM增量學(xué)習(xí)的訓(xùn)練速度。

Fig.3 Contrast of training time圖3 訓(xùn)練時(shí)間對(duì)比