基于FCM與KKT條件的增量學(xué)習(xí)方法

張國(guó)兵，郎榮玲

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

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

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

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

1 模糊聚類方法

1.1 FCM

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

FCM在聚類過(guò)程中要求所聚得的簇能使得指示性價(jià)值函數(shù)達(dá)到最小值。當(dāng)選擇歐幾里德距離度量?jī)牲c(diǎn)之間的距離時(shí)示性函數(shù)定義為：

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

1.2 樣本篩選

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

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

2 KKT條件

KKT最優(yōu)化條件是Karush[1939]以及Kuhn和Tucker[1951]先后獨(dú)立發(fā)表出來(lái)的，這組最優(yōu)化條件在Kuhn和Tucker發(fā)表之后才逐漸受到重視，KTT條件是指在滿足一些有規(guī)則的條件下，一個(gè)非線性規(guī)劃（Nonlinear Programming）問(wèn)題能有最優(yōu)化解法的一個(gè)必要和充分條件?？梢缘玫街С窒蛄繖C(jī)的KKT條件表達(dá)式如下：

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

3 增量學(xué)習(xí)過(guò)程

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

增量學(xué)習(xí)實(shí)現(xiàn)過(guò)程如圖2所示。

圖2 增量學(xué)習(xí)實(shí)現(xiàn)過(guò)程Fig.2 Incremental learning implementation process

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

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

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

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

4）對(duì)集合X0或者Xnew0進(jìn)行支持向量機(jī)訓(xùn)練得到支持向量集合S，若U=0，說(shuō)明新增樣本集中沒(méi)有新的信息，不需要增量學(xué)習(xí)，將S0作為最終的支持向量集合，否則S作為最終的支持向量集合；

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

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

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

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

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

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

5 結(jié) 論

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

[1]曹杰，劉志鏡.基于支持向量機(jī)的增量學(xué)習(xí)算法[J].計(jì)算機(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]馮國(guó)瑜，肖懷鐵.一種適于在線學(xué)習(xí)的增量支持向量數(shù)據(jù)描述方法[J].信號(hào)處理，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增量學(xué)習(xí)算法研究[J].電腦知識(shí)與技術(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ī)增量學(xué)習(xí)算法[J].運(yùn)籌與管理，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ī)模訓(xùn)練數(shù)據(jù)的支持向量機(jī)學(xué)習(xí)新方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，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]朱方，顧軍華，楊欣偉，等.一種新的支持向量機(jī)大規(guī)模訓(xùn)練樣本集縮減策略[J].計(jì)算機(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.