張國兵，郎榮玲

（北京航空航天大學 電子信息工程學院，北京 100191）

增量學習方法（incremental learning approach）是一種得到廣泛應(yīng)用的智能化數(shù)據(jù)挖掘與知識學習方法。其思想是當樣本逐步積累時，能夠不斷地吸收新的知識，從而使精度也隨之提高[1]。在學習過程中，大部分方法都是通過相應(yīng)的手段和算法，丟棄大量無效的樣本點，減少算法的計算時間和樣本的存儲空間，在保證機器學習的效率和精度的條件下，解決了大量樣本訓練時間長和存儲空間不足，以及在線實時增量學習的問題[2]。

在丟棄大量無效樣本點過程中，不同算法采用的方式和方法各不相同，目的都是為了最大限度地減少參與訓練的樣本數(shù)量和算法的計算量。但是刪減無關(guān)樣本點稍有不當，就會影響到機器學習的效率和精度，例如Syed等提出的增量學習算法，增量訓練由支持向量樣本和新樣本組成，再訓練只需要進行一次即可完成，所有的非支持向量樣本點都被拋棄，這種方法極有可能丟失原有的信息[3]；郭雪松提出的基于超球結(jié)構(gòu)的支持向量機增量學習算法，利用超球結(jié)構(gòu)，完成對增量學習中訓練樣本的選取，進而完成分類器的重構(gòu)，但是該方法的參數(shù)值很難確定，導(dǎo)致樣本選取覆蓋面過大，就會失去原有增量學習的意義，覆蓋范圍過小，又會遺漏可能成為支持向量的樣本點[4]。還有其他學者提出的增量學習方法，都是從不同角度對歷史樣本點或者新增量樣本點進行篩選，提高增量學習的效率和精度。因此，選擇合適的樣本篩選方法對增量學習起著至關(guān)重要的作用。

文中提出了利用模糊聚類方法對歷史樣本集合進行篩選，最大限度地保留原有的信息量，丟棄無效的樣本點[5-6]；并利用 KKT（Karush-Kuhn-Tucker）條件對新增樣本集進行篩選，保留違背KKT條件的樣本點，并將它們篩選后的樣本集結(jié)合進行增量學習，以便提高機器學習的效率和精度。

1 模糊聚類方法

1.1 FCM

FCM算法的思想就是使得被劃分到同一簇的樣本間距離最小，而不同簇之間的距離最大。設(shè)X={x1，x2，…xn}，xi∈Rh，其中xi為第i個樣本，h為樣本的特征維數(shù)。FCM是把X={x1，x2，…xn}分為 L（2

FCM在聚類過程中要求所聚得的簇能使得指示性價值函數(shù)達到最小值。當選擇歐幾里德距離度量兩點之間的距離時示性函數(shù)定義為：

其中dij=‖ci-xj‖為第i個簇中心與樣本xj間的歐氏距離，m∈[1，∞）是一個加權(quán)指數(shù)，通常取m=2。

1.2 樣本篩選

假設(shè)樣本[9]集合為 X0={x1，x2，…，xn}，訓練得到的支持向量集合為S0。利用FCM對樣本數(shù)據(jù)集X0進行聚類時，可以得到L個數(shù)據(jù)簇，一般L≈2*SV/3比較合適。其中包括混合類簇（含有不同類樣本點）和單一類簇（只含有同一類樣本點）。首先將混合類簇的樣本點保留下來，而單一類簇的樣本點需要與支持向量集合S0中的樣本點進行比較，如果單一類簇中含有支持向量樣本點，則該簇中的樣本點將被保留，否則該簇中的所有樣本點都丟棄。最后將保留的樣本集合作為增量學習訓練集合的一部分。其樣本篩選過程如圖1所示：圖（a）中表示的是利用random函數(shù)仿真的一個兩維數(shù)據(jù)樣本的分布圖，共分為兩類，作為篩選前的數(shù)據(jù)；圖（b）中表示的是篩選后的數(shù)據(jù)分布圖。可見，利用FCM進行樣本篩選后，明顯有大量無效的樣本被淘汰掉，并且能夠保留可能成為支持向量的樣本點。

圖1 數(shù)據(jù)過濾示意圖Fig.1 Data filtering schemes

2 KKT條件

KKT最優(yōu)化條件是Karush[1939]以及Kuhn和Tucker[1951]先后獨立發(fā)表出來的，這組最優(yōu)化條件在Kuhn和Tucker發(fā)表之后才逐漸受到重視，KTT條件是指在滿足一些有規(guī)則的條件下，一個非線性規(guī)劃（Nonlinear Programming）問題能有最優(yōu)化解法的一個必要和充分條件。可以得到支持向量機的KKT條件表達式如下：

根據(jù)KKT條件，可以將訓練樣本點劃分為3部分：位于正確劃分區(qū)間隔邊界上的樣本點集合S（0≤αi≤C）；在間隔內(nèi)的錯誤支持向量集合E（gi<0）；其余的樣本點被劃分到一個集合 R（gi>0）。

3 增量學習過程

假設(shè)歷史樣本集合為 X0={（x1，y1），（xi，yi），…，（xn，yn）}，xi∈Rh，yi∈Y，歷史樣本集訓練得到的支持向量集合為 S0，新增樣本集合為 X′={（x1，y1），（xl，yl），…，（xm，ym）}，xl∈Rh，yl∈Y，其中h為樣本的特征維數(shù)，Y為樣本的類數(shù)。新增樣本集中違背KKT條件的樣本集合記為U，歷史樣本集合X0經(jīng)FCM篩選后的樣本集合記為Xnew0，增量學習后的支持向量集合為S。

增量學習實現(xiàn)過程如圖2所示。

圖2 增量學習實現(xiàn)過程Fig.2 Incremental learning implementation process

根據(jù)增量學習實現(xiàn)的過程，可以推導(dǎo)出該增量學習方法的具體步驟：

1）確保X0≠Φ，利用SMO算法對歷史樣本集合X0進行訓練得到支持向量集合S0和KKT條件；

2）利用KKT條件對新增樣本集合X′進行判斷，將違背KKT條件的樣本集合U并入到集合X0；

3）對集合 X0中的樣本總數(shù)n進行判斷，如果n>500（值的大小根據(jù)實際需求設(shè)置），就利用FCM算法對集合X0進行樣本篩選，去掉大量無關(guān)的樣本點，形成樣本集合Xnew0，否則直接進行下一步驟；

4）對集合X0或者Xnew0進行支持向量機訓練得到支持向量集合S，若U=0，說明新增樣本集中沒有新的信息，不需要增量學習，將S0作為最終的支持向量集合，否則S作為最終的支持向量集合；

5）只要有新的樣本集增加，就反復(fù)重復(fù)2）至4）步驟，完成每一階段的增量學習。

4 實驗分析

從理論上分析增量學習的結(jié)果都會優(yōu)于非增量訓練，而劣于全數(shù)據(jù)的訓練。為了驗證模糊聚類與KKT條件結(jié)合的增量學習方法的有效性和準確度，本部分從UCI標準數(shù)據(jù)庫中選取4組標準數(shù)據(jù)進行實驗，并且與非增量、全數(shù)據(jù)訓練進行比較分，分析本文的增量學習方法的優(yōu)勢。實驗條件為：1:1:1，非增量的訓練樣本不增加，全數(shù)據(jù)的訓練樣本每次增加100。選取的4組實驗數(shù)據(jù)如表1所示，測試結(jié)果圖3所示。

表1 數(shù)據(jù)類型Tab.1 Data classes

從實驗結(jié)果分析，從圖3中可以看出增量學習結(jié)果具有分類精度較高、穩(wěn)定性好；與全數(shù)據(jù)訓練的分類準確度相比，基本上與全數(shù)據(jù)訓練的分類準確度相等，并且在magic數(shù)據(jù)中甚至有的測試超過了全數(shù)據(jù)訓練的分類準確度，在訓練時間上明顯少于全數(shù)據(jù)的訓練時間。因此，模糊聚類與KKT條件結(jié)合的增量學習方法具有很好的增量學習效果。

圖3 增量學習的結(jié)果Fig.3 Incremental learning results

5 結(jié) 論

文中提出的增量學習方法從歷史樣本和新增樣本兩個部分對參訓樣本數(shù)據(jù)進行篩選，提高了訓練速度和節(jié)省了存儲空間。該算法與增量學習結(jié)果的上下邊界進行了比較，實驗結(jié)果證明增量學習的結(jié)果幾乎與上邊界全數(shù)據(jù)訓練的結(jié)果擬合，因此模糊聚類與KKT條件結(jié)合的增量學習方法是一種非常有效的增量學習方法。

[1]曹杰，劉志鏡.基于支持向量機的增量學習算法[J].計算機應(yīng)用研究，2007（8）:50-52.CAO Jie，LIU Zhi-jing.Incremental learning algorithm based on SVM[J].Application Research of Computers，2007（8）:50-52.

[2]馮國瑜，肖懷鐵.一種適于在線學習的增量支持向量數(shù)據(jù)描述方法[J].信號處理，2012（2）:186-192.FENG Guo-yu，XIAO Huai-tie.An incrementalsupport vector data description method for online learning[J].Signal Processing，2012（2）:186-192.

[3]唐小力，呂宏偉.SVM增量學習算法研究[J].電腦知識與技術(shù)，2005（12）:160-162.TANG Xiao-li，LU Hong-wei.The research of SVM incremental learning[J].Computer Knowledge and Technology，2005（12）:160-162.

[4]郭雪松，孫林巖，徐晟.基于超球結(jié)構(gòu)的支持向量機增量學習算法[J].運籌與管理，2007（8）:45-49.GUO Xue-song，SUN Lin-yan，XU Sheng.Incremental SVM learning algorithm based on hyper-sphere structure[J].Operations Research and Management Science，2007（8）:45-49.

[5]鄭智洵，楊建剛.大規(guī)模訓練數(shù)據(jù)的支持向量機學習新方法[J].計算機工程與設(shè)計，2006，27（13）：2425-2431.ZHENG Zhi-xun，YANG Jian-gang.New method of SVM learning with large scale training data[J].Computer Engineering and Design，2006，27（13）：2425-2431.

[6]朱方，顧軍華，楊欣偉，等.一種新的支持向量機大規(guī)模訓練樣本集縮減策略[J].計算機應(yīng)用，2009，29（10）：2736-2740.ZHU Fang，GU Jun-hua，YANG Xin-wei，et al.New reduction strategy of large-scale training sample set for SVM[J].Journal of Computer Applications，2009，29（10）：2736-2740.