主題：如果訓練模型 經(jīng)過多次迭代后，需要進一步精簡

學習算法是否具有增量學習能力是衡量其是否適合于解決現(xiàn)實問題的一個重要方面。增量學習使學習算法的時間和空間資源消耗保持在可以管理和控制的水平 ,已被廣泛應(yīng)用于解決大規(guī)模數(shù)據(jù)集問題燕垃。因此，在隨著樣本信息的不斷更新井联，原有的訓練集模型會包含過多錯誤的卜壕、過時的分類信息，不利于分類邊界的劃分的情況下低矮，需要進行一定的修剪數(shù)據(jù)集印叁。

本文中介紹3種增量學習算法和這些算法中的修剪策略：

第一種，C2EV-KNNMODEL算法军掂，根據(jù)訓練樣本的每個特征參數(shù)對樣本的分類貢獻度和樣本的貢獻有限度來判斷是否需要修剪轮蜕。修剪后可以減少計算量和提高模型精度，能夠有效地降低增量訓練集模型的復
雜度，解決KNN在無窮增量環(huán)境下欠气，分類精度低晨汹、不平穩(wěn)，且健壯性差汇竭，泛化性能低的缺陷。

第二種穴张，在IKNNMODEL增量學習方法细燎，通過合并和刪除模型鏃的方法對它進行修剪, 降低了模型的復雜度, 增加了泛化能力, 提高了預(yù)測效率.該算法更好的適用于實際領(lǐng)域中.

第三種，基于推拉策略中心法的增量學習模型ICCDP皂甘，設(shè)置好必要的參數(shù)玻驻，若樣本分類錯誤，則用推拉公式修正正確類與錯誤類的中心向量 ,并重新計算這兩個類的歸一化中心偿枕。該算法易于實現(xiàn) ,訓練和分類速度快 ,而且該算法的分類性能接近一次性學習算法的性能璧瞬。

1、C2EV-KNNMODEL的修剪算法

增量學習的效果直接影響到KNN的效率和準確率渐夸。提出基于分類貢獻有效值的增量KNN修剪模型（C2EV-KNNMODEL）嗤锉，將特征參數(shù)的分類貢獻度與KNN增量學習結(jié)合起來，定義一種新的訓練樣本的貢獻有效值墓塌，并根據(jù)此定義制定訓練集模型的修剪策略瘟忱。理論和實驗表明奥额，C2EV-KNNMODEL的適用性較強，能夠使分類器的分類性能得到極大的提高酷誓。

1.1引言

KNN是一種典型的非參數(shù)的披坏、有效惰性學習方法，是數(shù)據(jù)挖掘盐数、機器學習和模式識別研究中的重點技術(shù)[1]棒拂。但KNN 自身并不具備增量學習的特性，是一種靜態(tài)的學習方法玫氢，對于一些數(shù)據(jù)每天都在增加帚屉、變化的應(yīng)用領(lǐng)域，如股市漾峡、氣象預(yù)測攻旦、網(wǎng)絡(luò)入侵、電力生逸、銀行等牢屋，無論是分類精度，還是分類效率槽袄，適用性都較差烙无。因此，如何設(shè)置KNN增量學習的方法遍尺，使KNN訓練集模型在增量過程中保持較高的有效分類信息量的條件下截酷，控制訓練集模型的樣本數(shù)量，成為國內(nèi)外學者研究的熱點乾戏。在下面就提出了KNN增量學習算法和一種基于分類貢獻有效值的增量KNN修剪模型（ClassificationContributionEffective Value迂苛，C2EV-KNNMODEL）

1.2 KNN增量學習算法簡介

KNNMODEL提出了簇優(yōu)化訓練樣本集的概念，在原始訓練樣本集上構(gòu)建多個簇鼓择，由于產(chǎn)生的簇的數(shù)量遠低于訓練集樣本的數(shù)量三幻，因此可提高KNN的分類效率，且每個簇的大小可根據(jù)訓練集的分布情況動生成呐能，從而減少對參數(shù)K的依賴念搬。
IKNNMODEL 是基于 KNNMODEL 常用的增量學習方法。它通過對訓練集樣本模型簇引進“層”的概念催跪，對新增數(shù)據(jù)建立不同“層”的新模型簇的方式對原有訓練集樣本模型進行優(yōu)化，達到增量學習的效果夷野，其具體學習算法參見文獻[4]懊蒸。隨著樣本信息的不斷更新，原有的訓練集模型會包含過多錯誤的悯搔、過時的分類信息骑丸，不利于分類邊界的劃分。IKNNMODEL在原始訓練集樣本模型的基礎(chǔ)上構(gòu)建新的模型簇，使得新增模型與原始訓練集模型的交叉區(qū)域更加準確通危，并賦予新的模型簇更高的層值铸豁，使其能覆蓋舊訓練集模型的錯分區(qū)域，通過增量學習不斷地進行修正菊碟。

1.3 C2EV-KNNMODEL的修剪算法

KNN類別判斷是一種典型的节芥、基于案例的學習，其過程必然與訓練樣本自身的類別特征有關(guān)逆害。因此头镊，如何確定訓練樣本針對類別的貢獻程度頗為重要。首先給出特征參數(shù)分類貢獻度的定義魄幕，并對其可行性進行了分析相艇，然后在此基礎(chǔ)上定義樣本的貢獻有效值，驗證其有效性和準確性
下圖就對分類貢獻度和貢獻有效值進行了定義：

1.4 C2EV-KNNMODEL修剪的實現(xiàn)

針對增量KNN模型修剪的準確性和效率問題纯陨，在上述算法有效性及精度分析的基礎(chǔ)上坛芽，給出C2EV-KNNMODEL修剪模型在學習階段的基本步驟，其核心思想是：借助式（1）確定每個特征參數(shù)對樣本類別判斷的影響程度翼抠；根據(jù)式（5）確定原始訓練集和增量集中各個樣本的分類貢獻有效值咙轩，分別取其均值作為兩個數(shù)據(jù)集彼此修剪的判斷依據(jù)；循環(huán)執(zhí)行机久，直至增量集不再增加臭墨。具體執(zhí)行過程如下：

輸入：原始KNN訓練集S，樣本個數(shù)為m膘盖；若干z個增量步訓練集胧弛，每個增量步訓練集的樣本數(shù)為mz個
輸出：修剪后的KNN訓練集模型。

**步驟1 根據(jù)特征參數(shù)分類貢獻度的定義侠畔，由式（1）對訓練集S中所有不同的结缚、還未計算過的特征參數(shù)進行分類貢獻度的特征轉(zhuǎn)換。

步驟 2 根據(jù)貢獻有效值的定義软棺，由式（5）計算訓練集 S中 各樣本的 W(xi)红竭，并計算 S 的平均貢獻有效值，并設(shè)置該平均貢獻有效值為增量訓練集 z1 的修剪閥值茵宪。閥值。

步驟3 根據(jù)特征參數(shù)分類貢獻度的定義瘦棋，由式（1）對 z1 增量步訓練集中所有不同的特征參數(shù)進行分類貢獻度的特征轉(zhuǎn)換稀火。

步驟4 根據(jù)貢獻有效值的定義，由式（5）計算增量步訓練
集 z1 中各樣本的W(xi)赌朋，并計算 z1 的平均貢獻有效值凰狞，并設(shè)置該平均貢獻有效值為訓練集 S 的修剪閥值篇裁。

步驟5 對訓練集S進行修剪
for i=0 to m
if W(xi) < ----- W(z1) then W(xi) 對應(yīng)的刪除強度值加1
if W(xi) 對應(yīng)的刪除強度在一段時間內(nèi)大于k（文獻[6]中的生存期），即W(xi) 均連續(xù)小于k個增量步訓練集的平均貢獻有效值then樣本 xi 對于分類所起的作用已失效赡若，刪除掉 xi 樣本达布；

步驟6 對 z1 增量步訓練集進行修剪
for i=0 to m′
if W(xi) ≥ ------ W(S) then W(xi) 對應(yīng)的添加強度值加1；
if W(xi) 對應(yīng)的添加強度在一段時間內(nèi)大于k逾冬，即W(xi) 均連續(xù)大于k個增量步訓練集修剪后的訓練集S的平均貢獻有效值then樣本xi 對于分類所起的正面作用越來越大黍聂，將 xi 添加入訓練集S；

步驟7 用修剪后的訓練集模型替換原始訓練集S粉渠，跳回步驟1分冈，繼續(xù)執(zhí)行下一個增量步訓練集的修剪工作

1.6 總結(jié)

修剪機制的設(shè)置是增量KNN算法的重點。通過對特征參數(shù)分類貢獻度和貢獻有效值兩個方面的研究霸株，提出基于分類貢獻有效值的增量 KNN 修剪模型（C2EV-KNNMODEL）雕沉。

實驗表明，CEV-KNNMODEL 性能優(yōu)于文獻[1]去件、文獻[2]及傳統(tǒng)IKNNMODEL等算法坡椒，能夠有效地降低增量訓練集模型的復雜度，解決KNN在無窮增量環(huán)境下尤溜，分類精度低倔叼、不平穩(wěn)，且健壯性差宫莱，泛化性能低的缺陷丈攒。下一步改進的重點有：（1）特征參數(shù)分類貢獻度 e(tij)、貢獻有效值W(xi) 計算所需的索引結(jié)構(gòu)及搜索技術(shù)是制約C2EV-KNNMODEL分類效率的瓶頸授霸；（2）貢獻有效值 W(xi) 的生存周期巡验，即 k 值的計算。改進后碘耳，C2EVKNNMODEL的準確率和訓練集樣本數(shù)量規(guī)模應(yīng)該有進一步提升的空間显设。

2、增量KNN模型的修剪策略研究

KNN模型是 k-近鄰算法的一種改進版本, IKNNModel算法實現(xiàn)了基于 KNNModel的增量學習.然而隨著增量步數(shù)的增加, IKNNModel算法生成模型簇的數(shù)量也在不斷地增加, 從而導致模型過于復雜, 也增大了預(yù)測的時間花銷.提出一種新穎的模型簇修剪策略, 在增量學習過程中通過有效合并和刪除多余的模型簇, 在保證精度的同時降低了模型簇的數(shù)量, 從而縮短了算法的預(yù)測時間.在一些公共數(shù)據(jù)集上的實驗結(jié)果驗證了本方法的有效性.

2.1 引言

KNN模型算法(簡記 KNNModel)是 Guo[ 1]等人提出的一種改進的 KNN算法.它克服了傳統(tǒng) KNN分類算法參數(shù) k難以確定以及分類新數(shù)據(jù)時間耗費大的兩個缺陷.KNNModel通過有監(jiān)督地構(gòu)建數(shù)據(jù)的多個 KNN模型簇, 以此代替原始數(shù)據(jù)集作為分類的基礎(chǔ) .傳統(tǒng)的 KNNModel算法是靜態(tài)的學習算法, IKNNModel算法 [ 2] 則是基于 KNNModel的增量學習算法.IKNNModel算法通過對模型簇引進"層"的概念, 達到增量學習的效果, 使得 KNNModel算法能夠適用于一些數(shù)據(jù)每天都在增加的應(yīng)用領(lǐng)域, 如網(wǎng)絡(luò)入侵, 股市分析, 電力, 銀行等.然而, 隨著增量步數(shù)的增加, 算法生成模型簇的數(shù)量也會同時增加, 從而嚴重地影響了預(yù)測時間.而在這些實際應(yīng)用領(lǐng)域中, 增量步數(shù)可以看成是無限大的,因此辛辨，需要控制模型簇的數(shù)量成了亟需解決的問題.

2.2 KNNMODEL算法

KNN模型算法(簡記 KNNModel)是 Guo[ 1]等人提出的一種改進的 KNN算法, 它改進了傳統(tǒng) KNN分類算法前述的兩個缺陷.KNNModel在數(shù)據(jù)集上構(gòu)建多個 KNN模型簇, 以此代替原數(shù)據(jù)集作為分類的基礎(chǔ), 由于產(chǎn)生的模型簇的數(shù)量遠遠小于訓練集中的樣本個數(shù), 因此提高了分類的效率;而每個模型簇的大小由 KNNModel算法根據(jù)數(shù)據(jù)集的分布情況自動形成, 從而減少了對參數(shù) k的依賴, 并在一定程度上提高了分類的精度.

2.3 IKNNModel算法

圖 2.3.1：1 IKNNModel利用新增數(shù)據(jù)對 KNNModel模型的修正

圖 2.3.1中有方形和三角形兩類新樣本點, 原有的模型簇 old中包含了過多的錯分點, 顯然在邊界處不夠準確.而在新樣本基礎(chǔ)上構(gòu)建的新模型簇 new在交叉區(qū)域則更加準確.因此我們賦予新模型簇更高的層值, 使其能覆蓋舊模型簇的錯分區(qū)域, 這樣就使得原有模型能夠通過增量學習不斷地得到修正.

2.4 增量 KNNModel的修剪策略

在 IKNNModel增量算法中, 由于訓練樣本不是一次性到達, 算法在不同層次建立了多個模型簇.在多個增量步后IKNNModel算法建立的模型簇數(shù)量將比用 KNNModel算法直接在整個訓練集上建立的模型簇數(shù)量來得多.而在金融, 入侵檢測等實際應(yīng)用領(lǐng)域中, 增量的步數(shù)可以看成是無窮大的.這樣, 隨著增量步數(shù)的不斷增加, 過多的模型簇將對預(yù)測時間產(chǎn)生嚴重的影響, 而并非所有的模型簇都對預(yù)測樣本產(chǎn)生正面的作用.因此, 在 IKNNModel算法中對模型簇進行修剪是很有必要的.

本文通過合并和刪除兩種方法對 IKNNModel算法進行修剪.其中, 我們通過合并的修剪方法, 將同層中同類模型簇合并成一個新的模型簇, 并用這個新的模型簇取代原有的同類模型簇.這樣, 在減少了模型簇的數(shù)量的同時提高了算法的泛化能力.另外, 利用刪除的修剪方法刪除掉多余的模型簇.有些模型簇因為發(fā)生了概念漂移而無法正確反映當前的數(shù)據(jù)分布情況, 有些模型簇由于被其他高層異類的模型簇所覆蓋, 而在預(yù)測新樣本時不起作用.這些模型簇的存在對預(yù)測樣本無法起到正面的作用, 因此, 我們需要刪除這些模型簇.這樣, 在減少模型簇數(shù)量的同時, 使得算法能夠更加適應(yīng)增量過程中數(shù)據(jù)的概念變化[ 11] .

2.5 IKNNModel修剪方法

2.5.1 模型簇的合并操作

圖 2.5.1 實驗產(chǎn)生的兩個模型簇 1和 2

圖 2.5.1中模型簇 1和 2的類別相同 , 層值相同 , 若模型簇new中不包含其它類別的數(shù)據(jù)點, 則可用模型簇 new<Cls(dnew), Sim(dnew), Num(dnew), Rep(dnew), Layer(dnew)>代替模型簇 1, 2.圖 2.5.2中新模型簇的類別 Cls(dnew)為:

圖2.5.2 覆蓋模型簇 1和 2的新模型簇 new

2.5.2模型簇的刪除操作

根據(jù)文獻[ 2] 中預(yù)測階段的敘述, 可以認為在預(yù)測新數(shù)據(jù)樣本時, 對一個新數(shù)據(jù)樣本的類別真正起決定作用的只是某一個模型簇.如圖 4例子所示, 假設(shè)模型簇 A的層值大于模型簇 B的層值.由于在預(yù)測階段, 當一個樣本被多個模型簇覆蓋時, 選擇層值高的模型簇的類別 [ 2] .因此, 實際上對新數(shù)據(jù)樣本t1,t2的類別起決定作用的都是模型簇 A.圖中 t2雖然同時被模型簇 A, B所覆蓋, 但模型簇 B由于層值小于 A, 所以對于 t2類別的預(yù)測是不起作用的.

圖2.5.3 實驗產(chǎn)生的兩個模型簇 A和 B

在每次增量步中, IKNNModel算法先對新的一批訓練樣本進行預(yù)測.假設(shè)在預(yù)測過程中模型簇 i對 n個被正確分類的新樣本類別起決定作用, 則模型簇 i的有效值為 n;而當模型簇 i對錯誤分類的新樣本起到?jīng)Q定作用時, 則不增加其有效值.當某個模型簇在一段時間內(nèi) (或者說 k次增量步中)的有效值都為 0, 那么認為這種模型簇已經(jīng)失效了.如果一個模型簇是無效的, 說明這個模型簇或者由于發(fā)生了概念漂移, 或者由于被其它高層的模型簇所覆蓋, 而在預(yù)測中無法起到作用.這些模型簇的存在對預(yù)測新樣本沒有正面的作用, 反而增加了預(yù)測時間, 因此, 需要將這樣的模型簇刪除.

2.6 帶修剪的 IKNNModel算法實現(xiàn)

帶修剪的 IKNNModel算法在學習階段的基本步驟如下:

輸入:n個新的訓練樣本和已有的 IKNNModel模型, 參數(shù) k;

輸出:修剪后的 IKNNModel模型

Step1.用已有的 IKNNModel模型對每個新訓練樣本進行分類, 并計算每個模型簇的有效值;

Step2.利用 IKNNModel算法對已有模型進行更新[ 2] ;

Step3.刪除 在連 續(xù) k次 增量 步中有 效值 都為 0的 模
型簇;

Step4.遍歷所有模型簇, 若存在能夠合并的模型簇, 則通過公式(1)-(5)對模型簇進行合并;

Step5.輸出更新后的模型簇.其中, 參數(shù) k類似于文獻[ 10] 中的生存期, k值越小算法對過去樣本的"遺忘 "率則越高 [ 7] .Step1中, 由于在新樣本到達時 IKNNModel算法都要先對其進行分類, 然后對正確分類和錯分兩種情況分別做處理 [ 2], 因此可以在分類時計算每個模型簇的有效值.

2.7 結(jié) 論

本文提出了一種增量 KNN模型的修剪策略.通過合并和刪除模型簇, 降低了模型的復雜度, 增加了泛化能力, 提高了預(yù)測效率.

KDDCUP′99入侵檢測數(shù)據(jù)

移動超平面數(shù)據(jù)集

在 UCI機器學習公共數(shù)據(jù)集, KDDCUP′99入侵檢測數(shù)據(jù)集以及移動超平面數(shù)據(jù)集上的實驗結(jié)果表明, 通過修剪, IKNNModel能更好的適用于實際領(lǐng)域中.

3捕捂、基于推拉策略的文本分類增量學習研究

學習算法是否具有增量學習能力是衡量其是否適合于解決現(xiàn)實問題的一個重要方面。增量學習使學習算法的時間和空間資源消耗保持在可以管理和控制的水平 ,已被廣泛應(yīng)用于解決大規(guī)模數(shù)據(jù)集問題斗搞。針對文本分類問題 ,本文提出了增量學習算法的一般性問題指攒。基于推拉策略的基本思想 ,本文提出了文本分類的增量學習算法ICCDP ,并使用該算法對提出的一般性問題進行了分析僻焚。實驗表明 ,該算法訓練速度快 ,分類精度高 ,具有較高的實用價值允悦。

3.1 引言

傳統(tǒng)的文本分類方法 ,即非增量學習算法 ,或者稱為一次性學習算法 ,根據(jù)當前所獲得的所有訓練樣本計算得到文本分類模型 ,如中心法、樸素貝葉斯(NB) 溅呢、K最近鄰方法 ( KNN) 澡屡、支持向量機 (SVM) 、決策樹方法(Decision Tree) 等咐旧。然而它們并不總是有效驶鹉，原因：(1) 訓練樣本很難一次性獲得。(2) 內(nèi)存限制铣墨。
在這種情況下 ,我們需要根據(jù)已經(jīng)獲得的分類器模型 ,增量學習新的訓練樣本 ,并更新現(xiàn)有的分類器模型室埋。其中 ,對每一批樣本進行增量學習得到一個新的模型 ,稱為經(jīng)過一個增量步。增量學習使得一種學習算法更適合于現(xiàn)實應(yīng)用伊约。它使學習算法的時間和空間資源消耗保持在可以管理和控制的水平 ;或者用于訓練數(shù)據(jù)不足時需要做出分類決定的情形 ,比如在線環(huán)境中姚淆。

3.2 相關(guān)工作

3.2.1 推拉策略

文獻[ 9 ,10 ]將推拉策略引入到中心法 ,使得中心法的性能顯著提高 ,分類精度接近 SVM ,但訓練速度遠快于 SVM。推拉策略的基本思想是利用錯分樣本對誤分入的類別中心和所屬中心同時做出修正 ,推遠錯誤中心 ,拉近正確中心屡律。這樣既保證了錯誤修正的一致性 ,又能很快達到高水平的性能平衡點腌逢。經(jīng)過“推拉”操作之后 ,樣本被正確分類的可能性大大提高。該策略對全部訓練樣本進行分類 ,對每一個錯分樣本都要進行“推拉”操作超埋。推拉操作僅需重復執(zhí)行少量次數(shù)就能達到穩(wěn)定的性能搏讶。經(jīng)證明 ,在線性可分情況下 ,推拉策略在訓練集上是收斂的。

3.3 基于推拉策略的增量學習模型

3.3.1 模型描述
中心分類法將已學習過的訓練樣本壓縮為各個類的中心來表示 ,而且更新中心法模型的代價較小霍殴。這兩種屬性使得中心法特別適合于增量學習媒惕。將推拉策略引入到中心法得到的文本分類器訓練速度快 ,分類精度高。因此 ,我們提出了一種基于推拉策略中 心 法 的 增 量 學 習 模 型 ICCDP ( Incremental Centroid Classifier based on Dragp ushing) 来庭。

ICCDP 的算法描述如下 :

3.4 結(jié)論和下一步工作

當訓練樣本需要分批處理時 ,傳統(tǒng)的文本分類方法并不總是有效妒蔚。增量學習算法作為一種解決方案引起廣泛關(guān)注。本文重點對增量學習算法設(shè)計和研究中的一般問題進行研究月弛。同時 ,提出一種增量學習算法 ICCDP肴盏。該算法易于實現(xiàn) ,訓練和分類速度快 ,而且該算法的分類性能接近一次性學習算法的性能。我們利用 ICCDP 進行了一系列實驗 ,對增量學習中的一般問題做進一步的探討尊搬。得出的結(jié)論是 ,該算法對參數(shù)不敏感叁鉴、對樣本輸入順序輕微敏感 ,而且該算法是一個高效的增量學習算法。
增量學習與一次性學習一個很大的區(qū)別是 : 增量學習面對的是一個開放的環(huán)境 ,可以不斷地接收新的訓練樣本 ;而一次性學習處在一個封閉的環(huán)境中 ,一次學習完所有樣本佛寿。這種區(qū)別就使得增量學習面臨以下問題 : 隨著增量步數(shù)的增加 ,可能發(fā)生概念漂移 ,如何早一些檢測到概念漂移 ,并自適應(yīng)地調(diào)整分類器模型 ,就顯得非常重要幌墓。

總結(jié)

因為訓練樣本很難一次性獲得等等的原因，所以增量學習模型適用于現(xiàn)實中大多數(shù)情況冀泻。那么當訓練模型迭代訓練多次時常侣，就需要對訓練集和增量集或訓練的模型進行一定的修剪策略來提高最終模型的精確度和降低計算量。因此需要看情況來進行相應(yīng)的修剪策略來達到上述所說目的弹渔。

參考文獻：
【1】周 靖胳施，劉晉勝， 基于分類貢獻有效值的增量KNN模型修剪研究
【2】黃 杰 , 郭躬德 , 陳黎飛肢专，增量 KNN模型的修剪策略研究
【3】羅長升,段建國,郭 莉舞肆，基于推拉策略的文本分類增量學習研究