一種增量式極端隨機(jī)森林分類器

一種增量式極端隨機(jī)森林分類器

傳統(tǒng)的機(jī)械學(xué)習(xí)通常采用批處理學(xué)習(xí)的方法。換言之，在所有訓(xùn)練樣本都完成后，學(xué)習(xí)過程將不再繼續(xù)。然而，在實踐中，當(dāng)所有訓(xùn)練樣本被轉(zhuǎn)換成預(yù)測的空間學(xué)習(xí)時，它們可以繼續(xù)學(xué)習(xí)現(xiàn)有的模型本身的識別能力，從而減少重復(fù)學(xué)習(xí)的空間學(xué)習(xí)的擴(kuò)展學(xué)習(xí)方法。目前，它沒有嚴(yán)格的定義可以單獨確定新樣本，但主要特點是可以將新樣本添加到現(xiàn)有的知識系統(tǒng)。基本知識系統(tǒng)可以逐步發(fā)展為復(fù)雜系統(tǒng)，有許多方法可以同時使用。根據(jù)分類器的類型，可以采用基于支持向量機(jī)的體積檢測算法、基于鄰居方法的體積檢測算法、基于權(quán)重提升的體積檢測算法[8.9、10、11、12、13、14、15、16]的漸進(jìn)式學(xué)習(xí)算法和基于rbf網(wǎng)絡(luò)的體積檢測算法。基于決策樹的方法目前已被廣泛用于增量學(xué)習(xí),一是由于決策樹本身簡單、快速,決策樹模型易于理解,通過決策樹的工作過程可以直觀理解問題的求解過程.二是由于決策樹能夠?qū)V泛的問題給出準(zhǔn)確的解.決策樹通常將多維數(shù)據(jù)迭代的劃分為若干更小維數(shù)的數(shù)據(jù)進(jìn)行處理,這種分治策略(divide-and-conquer)適用于諸多問題的求解.三是由于決策樹的構(gòu)造效率很高.對于n個樣本和m個屬性,文獻(xiàn)證明了忽略數(shù)值屬性等復(fù)雜因素,決策數(shù)的平均構(gòu)造開銷是O(m?n?logn).按照樹模型來劃分,當(dāng)前增量決策樹算法研究可分為兩個主要方向:第1類是采用貪婪算法重構(gòu)決策樹,例如ID5R,ITI及其改進(jìn)方法.這類方法將新樣本加入到?jīng)Q策樹以后,需要重新確定分類路徑上每個決策節(jié)點的決策屬性,以確保該決策屬性是最適合該節(jié)點的.若選擇的最優(yōu)屬性不在當(dāng)前決策節(jié)點上,則要將其從葉節(jié)點提升(pullup)上來,并迭代地為其子樹上所有決策節(jié)點確定最優(yōu)屬性.由于每新加入一個樣本都需要對樹進(jìn)行變換重構(gòu),因此當(dāng)問題規(guī)模達(dá)到一定程度后,這類方法的計算時間開銷非常大.第2類方法是通過維護(hù)一些必要的統(tǒng)計量來完成決策樹的增量構(gòu)造,例如VFDT,IADEM,StreamingRandomForest,ImprovingHoeffdingTrees以及相應(yīng)的改進(jìn)方法.這些方法采用概率統(tǒng)計量,例如Hoeffding邊界(也被稱為Chernoff邊界),主要用于確定當(dāng)前葉節(jié)點是否需要分裂成為決策節(jié)點.新樣本到達(dá)葉節(jié)點后不被存儲,而是更新該葉節(jié)點上的統(tǒng)計信息,當(dāng)有足夠多的樣本到達(dá)該節(jié)點后,根據(jù)統(tǒng)計信息可以判定是否需要將該葉節(jié)點分裂為決策節(jié)點.當(dāng)葉節(jié)點分裂為決策節(jié)點后,統(tǒng)計信息會傳遞到后繼子節(jié)點,決策節(jié)點僅保留最佳決策屬性.這類方法無須存儲訓(xùn)練樣本,因而可耗費低時空開銷來處理海量數(shù)據(jù),但是只有當(dāng)接收足夠多的樣本信息后,才能有充分的統(tǒng)計證據(jù)確定是否進(jìn)行節(jié)點分裂.對于采用Hoeffding邊界作為統(tǒng)計量的方法來說,針對二值分類問題,平均需要5×106個樣本來構(gòu)造一棵決策樹,而針對多類分類問題例如C-類分類問題,構(gòu)造一棵決策樹通常需要(5×106)/2×C個樣本.雖然具有很好的增量學(xué)習(xí)性能,但第2類方法不適合小樣本數(shù)據(jù)流的應(yīng)用.在實際應(yīng)用中,小樣本數(shù)據(jù)流的問題很普遍,例如在線視頻跟蹤問題.當(dāng)前視頻跟蹤常作為分類問題進(jìn)行解決,在線學(xué)習(xí)的分類器對于目標(biāo)物體外觀的改變和復(fù)雜的環(huán)境具有很好的適應(yīng)性.增量學(xué)習(xí)分類器可以很自然地應(yīng)用于在線學(xué)習(xí)的應(yīng)用.Feng采用增量學(xué)習(xí)SVM方法,結(jié)合半指導(dǎo)學(xué)習(xí)理論,利用視頻圖像中大量的無標(biāo)記樣本完成分類器的在線學(xué)習(xí),得到了穩(wěn)定可靠的跟蹤結(jié)果.但文中的算法不能處理多目標(biāo)識別跟蹤,并且目標(biāo)物體大尺度和大方向的變化情況也不能進(jìn)行有效地跟蹤.為此,本文提出了一種增量式極端隨機(jī)森林(incrementalextremelyrandomforest,簡稱IERF)分類器,能夠有效解決小樣本數(shù)據(jù)流的在線學(xué)習(xí)問題,并在視頻、在線跟蹤(包含多目標(biāo)跟蹤)等應(yīng)用上的得到了實驗驗證.本文研究做出貢獻(xiàn)如下:1)設(shè)計了一種支持在線學(xué)習(xí)的IERF分類器,在給定有限數(shù)量的樣本特別是小樣本的情況下,本文提出的算法能夠?qū)Ψ诸惼鬟M(jìn)行快速有效的擴(kuò)展,并能達(dá)到與離線批量學(xué)習(xí)的極端隨機(jī)森林(extremelyrandomforest,簡稱ERF)分類器相當(dāng)甚至更優(yōu)的性能,在時間開銷和分類正確率等方面優(yōu)于當(dāng)前貪婪決策樹重構(gòu)算法和其他幾種主要的增量學(xué)習(xí)算法.2)將本文提出的IERF算法應(yīng)用于解決小樣本數(shù)據(jù)流的一個應(yīng)用——視頻在線跟蹤問題,本文提出的基于IERF分類器的在線視頻跟蹤算法,能夠在目標(biāo)外形發(fā)生大尺度變化以及復(fù)雜背景等情況下,實現(xiàn)對目標(biāo)穩(wěn)定可靠的跟蹤,并且具有多目標(biāo)跟蹤的能力.1作為鋼架的“樹集成”分類器相對于單棵決策樹而言,隨機(jī)森林可以避免過擬合問題,分類精度高,穩(wěn)定性好;隨機(jī)森林保留了多值分類的特性,適合處理多值分類問題;相比boosting和其他集成方法,隨機(jī)森林方法對于數(shù)據(jù)噪聲更穩(wěn)定.極端隨機(jī)森林同樣是一種多棵決策樹集成(ensemble)的分類器.與隨機(jī)森林分類器相比,主要有兩點不同:一是不采用bootstrap采樣替換策略,而是直接采用原始的訓(xùn)練樣本,目的在于減少偏差(bias);二是在每棵決策樹的決策節(jié)點上,分裂測試的閾值是隨機(jī)選擇的.假設(shè)決策節(jié)點上的分裂測試表達(dá)為為待分類的樣本,為測試函數(shù),在隨機(jī)森林分類器中,θ通?；跇颖镜哪骋惶卣鬟M(jìn)行設(shè)定,而在極端隨機(jī)森林分類器中,θ則是隨機(jī)選擇的.極端隨機(jī)森林分類器在分類精度和訓(xùn)練時間開銷等方面的性能,都要優(yōu)于隨機(jī)森林分類器.但極端隨機(jī)森林分類器只能支持離線訓(xùn)練的方式,不支持增量式學(xué)習(xí).為此,本文主要針對解決有限樣本的數(shù)據(jù)流在線學(xué)習(xí)問題,充分利用極端隨機(jī)森林分類器的特性,提出了一種支持在線學(xué)習(xí)的增量式極端隨機(jī)森林分類器.2增量超樹算法首先介紹增量式極端隨機(jī)森林算法的動機(jī)和算法描述,再給出算法中重要的分裂閾值參數(shù)的相關(guān)定理及證明,最后對增量式極端森林分類器的構(gòu)造開銷做出分析.本文提出的IERF算法主要基于以下3點考慮:1)利用統(tǒng)計量進(jìn)行增量學(xué)習(xí)的算法往往不存儲樣本,而是通過對海量數(shù)據(jù)進(jìn)行相關(guān)的數(shù)據(jù)統(tǒng)計分析來獲取分類器擴(kuò)展的必要信息,統(tǒng)計完的樣本即被丟棄不再使用,因此在處理小樣本數(shù)據(jù)時,由于不能提供足夠的統(tǒng)計信息而使增量學(xué)習(xí)失敗.為此,我們考慮采用存儲樣本的方式進(jìn)行增量學(xué)習(xí),在后續(xù)增量學(xué)習(xí)過程中仍然能夠重復(fù)利用歷史信息,這樣即便對于小樣本數(shù)據(jù)流仍然能夠進(jìn)行穩(wěn)定的增量學(xué)習(xí).2)傳統(tǒng)的基于單棵決策樹的增量學(xué)習(xí)方法需要保證決策樹上所有的決策屬性是最優(yōu)的,而分類器集成(ensemble)的方法,例如極端隨機(jī)森林算法等,則不需要每棵決策樹上所有的決策屬性最優(yōu),因此利用集成方法可以避免每棵決策樹的貪婪重構(gòu).同時單棵決策樹存在過擬合問題,而集成方法則可以有效地避免此類問題,并能夠減少偏差(bias)與方差(variance),同時還能夠保持計算的高效性.因此,我們采用分類器集成的方法進(jìn)行增量學(xué)習(xí).3)根據(jù)樣本集合的混亂程度進(jìn)行節(jié)點的分裂,既可以控制樹的生長速度,又可以降低對數(shù)據(jù)噪聲的敏感度.IERF分類器同ERF分類器一樣,構(gòu)造了一個包含多棵決策樹的集合,ERF分類器中每棵決策樹稱為超樹(extra-tree),在IERF分類器中,每棵決策樹則稱為增量超樹(incrementalextra-tree).每棵增量超樹采用ERF分類器的思想,基于原始的訓(xùn)練樣本集合,采用傳統(tǒng)的自上而下的方式進(jìn)行構(gòu)造,相對bootstrap采樣替換策略,這種方法可以減小偏差(bias).構(gòu)造單棵增量超樹的算法見算法1.算法1.構(gòu)造增量超樹(s,i).增量超樹中的每個葉節(jié)點都維護(hù)一個樣本列表,用來存儲分類到該葉節(jié)點上的樣本,同時統(tǒng)計當(dāng)前該葉節(jié)點上所有樣本標(biāo)記值的數(shù)量分布.當(dāng)一個新的訓(xùn)練樣本到達(dá)時,首先經(jīng)過當(dāng)前的增量超樹分類,到達(dá)某一葉節(jié)點后被存儲到該葉節(jié)點上的樣本列表中,同時該樣本對應(yīng)的類別標(biāo)記總數(shù)加1.選擇存儲樣本的原因是在后續(xù)過程中可以重復(fù)利用這些已獲知的樣本,用來進(jìn)行增量超樹的構(gòu)造和擴(kuò)展,即便是在獲得很少樣本的情況下仍然可以有效地構(gòu)造增量超樹,同時也避免了計算需要大量樣本的Hoeffding邊界.當(dāng)葉節(jié)點上存儲的樣本集合到達(dá)一定的混亂程度后,即對當(dāng)前葉節(jié)點進(jìn)行分裂,構(gòu)造新的決策節(jié)點和相應(yīng)的后繼葉節(jié)點,從而達(dá)到擴(kuò)展生長整個增量超樹的目的.所有增量超樹的構(gòu)造和擴(kuò)展都是相互獨立的.判斷葉節(jié)點何時轉(zhuǎn)變成決策節(jié)點,我們考慮采用Gini系數(shù),它是度量樣本集合純度的一個量(對樣本集合純度度量方法的討論見第2.2節(jié)).針對一個樣本空間D,其中包含有n個樣本,共k個類別,則其中,pi是類別為i的樣本在全部樣本中所占的比例.當(dāng)某葉節(jié)點上的Gini系數(shù)超過了設(shè)定的閾值Δ時,我們即認(rèn)為當(dāng)前葉節(jié)點上的樣本集合達(dá)不到要求的純度,或被認(rèn)為樣本集合的混亂程度達(dá)到給定的上限,這時需要分裂當(dāng)前葉節(jié)點,利用存儲的樣本構(gòu)造新的子增量超樹.子增量超樹構(gòu)造過程見算法2.當(dāng)有新的葉節(jié)點生成時,在當(dāng)前葉節(jié)點上構(gòu)造一個樣本列表,統(tǒng)計并存儲樣本信息.當(dāng)一個葉節(jié)點分裂時,按照文獻(xiàn)的方法來選擇一個決策屬性和分裂測試,同時構(gòu)造一個新的決策節(jié)點并生成兩個相應(yīng)的后繼葉節(jié)點.分裂前的葉節(jié)點上存儲的樣本按照相應(yīng)的決策屬性和分裂測試進(jìn)行劃分,得到相應(yīng)的兩個樣本集合,分別存儲到對應(yīng)的兩個新生后繼葉節(jié)點上,同時對類別標(biāo)記的數(shù)量重新統(tǒng)計.隨著時間推移,葉節(jié)點上存儲的樣本會逐漸增多,這樣既會造成過重的空間負(fù)載,又會存在分類器對數(shù)據(jù)描述不夠準(zhǔn)確的隱患.為此,我們采用Least-Recent-Used替換策略來減少陳舊的樣本,著重關(guān)注當(dāng)前的樣本.在算法的實現(xiàn)過程中,每個樣本被賦予一個時間戳,當(dāng)樣本的時間戳小于給定時刻,即被丟棄.算法2.構(gòu)造子增量超樹(S).輸入:訓(xùn)練樣本集合S.2.2基于dini系數(shù)度量的分裂閾值參數(shù)我們定義一個樣本集合是純的,當(dāng)且僅當(dāng)該樣本集合中大部分元素為同一類樣本;定義一個樣本集合是不純的,當(dāng)且僅當(dāng)該集合中包含了很多其他類別的樣本.如何對樣本集合的純度進(jìn)行量化度量,常見的方法有3種:Entropy,Gini系數(shù),以及Classificationerror.合中每個類別樣本所占的比例pj(對任意的j都存在0≤pj≤1).相對于Classificationerror而言,Gini系數(shù)考慮了所有類別樣本的比例關(guān)系,能夠反映不同類別樣本的比例變化,而Classificationerror只考慮了集合中比例最大的樣本,對各類別樣本的比例變化有時不能夠準(zhǔn)確反映.例如,假設(shè)樣本集合中共含3種類別的樣本,每種類別樣本的比例分別為0.3,0.4,0.3,當(dāng)樣本集合中各個類別的數(shù)量發(fā)生了變化,其比例分別變?yōu)?.4,0.2,0.4,則此時Gini系數(shù)的變化量為ΔGini=(0.42-0.32)+(0.22-0.42)+(0.42-0.32)=0.02>0,而Classificationerror的變化量則為0.基于以上的比較和討論,我們選擇Gini系數(shù)作為本文算法中樣本集合純度的度量方法.本文采用Gini系數(shù)度量樣本集合的混亂程度,當(dāng)葉節(jié)點的Gini系數(shù)超過了給定閾值時,即對該葉節(jié)點進(jìn)行分裂.如何選擇合適的閾值參數(shù),在這里給出詳細(xì)的討論.首先引入一個用于度量樣本集合中各類別樣本比例關(guān)系的量——樣本混合比α,α為葉節(jié)點上非數(shù)量最多的樣本相對于數(shù)量最多的某一類樣本的比例.對葉節(jié)點分裂閾值參數(shù)的討論如下:當(dāng)α＞1時,在僅存兩類樣本的情況下,另一類樣本的數(shù)量一定大于Lm的數(shù)量;而在多于兩類樣本的情況下,則不一定能夠保證存在其他某類樣本,其數(shù)量大于Lm的數(shù)量.因此,本文在0≤α≤1中選擇分裂閾值參數(shù),相當(dāng)于適度提早了葉節(jié)點的分裂操作,目的在于保證分類器能夠更及時反映數(shù)據(jù)流中樣本的特征,增強分類器的判別性能,第3.1.2節(jié)對此進(jìn)行了實驗證明.第3.1.2節(jié)分別采用了兩種葉節(jié)點分裂判別條件進(jìn)行對比實驗,一種是本文算法采用的在0≤α≤1中選擇得到的閾值參數(shù)Δ,另一種是采用等待出現(xiàn)非Lm的某類樣本,其數(shù)量大于等于Lm樣本數(shù)量.結(jié)果證明,本文的方法能夠保證葉節(jié)點及時分裂,提高了分類器的判別能力,具有更高的分類正確率和可靠性.2.4erf算法與ierf算法的計算開裂IERF模型構(gòu)造開銷在這里考慮兩方面的因素:一是對樣本進(jìn)行遍歷統(tǒng)計需要的計算費用,稱為實例開銷(instance-countadditions);另一個是選擇決策節(jié)點分裂屬性時需要的熵信息計算費用(e-scorecalculations),這種方法需要計算多個屬性的信息熵,選擇信息熵最大的屬性作為分裂屬性.給定n個訓(xùn)練樣本,其中包含m個類別(不妨假設(shè)n>m),每個樣本包含d個屬性(這里假設(shè)所有屬性為連續(xù)的數(shù)值屬性).下面對ERF算法和IERF算法的計算開銷進(jìn)行比較(以單棵決策樹為研究對象進(jìn)行討論).SERF受決策樹的高度D、樣本屬性d以及熵信息的計算方法三方面因素的影響.(2)假設(shè)n個訓(xùn)練樣本按照時間順序依次到來,IERF算法每個時刻處理一個樣本.新增一個樣本時,IERF算法無須重新學(xué)習(xí)以往所有樣本,而在已有模型基礎(chǔ)上進(jìn)行增量學(xué)習(xí)即可.新樣本首先通過決策樹分類(此處時間開銷非常小),最終落到某個葉節(jié)點l上,假設(shè)該葉節(jié)點l已包含nl-1個樣本.3算法性能分析本節(jié)基于機(jī)器學(xué)習(xí)數(shù)據(jù)集進(jìn)行實驗,共分3部分:首先,第3.1節(jié)通過實驗確定樣本混合比α與IERF性能的關(guān)系,從而選擇合適的葉節(jié)點分裂閾值參數(shù)Δ;其次,第3.2節(jié)在分類正確率、模型復(fù)雜度以及訓(xùn)練時間開銷等方面,對增量學(xué)習(xí)的IERF算法和離線批量學(xué)習(xí)的ERF算法進(jìn)行比較,以驗證IERF算法的正確性;最后,第3.3節(jié)在適度規(guī)模的數(shù)據(jù)集上,將IERF算法與其他主要的增量學(xué)習(xí)算法進(jìn)行對比分析,檢驗IERF算法的性能.本節(jié)實驗采用的機(jī)器學(xué)習(xí)數(shù)據(jù)集,除了USPS來自LIBSVM數(shù)據(jù)集以外,其余均來自UCI數(shù)據(jù)集.表1包括6個數(shù)據(jù)集,用于第3.1節(jié)分裂閾值參數(shù)的選擇實驗;表2包括7個數(shù)據(jù)集,用于第3.2節(jié)和第3.3節(jié)的對比實驗.表1和表2中的數(shù)據(jù)集、樣本類別包括二值也包括多值,樣本屬性的范圍也較為寬泛,兩表中加*的數(shù)據(jù)集為小訓(xùn)練樣本數(shù)據(jù)集,未加*的為大訓(xùn)練樣本數(shù)據(jù)集,所有的訓(xùn)練樣本集規(guī)模適度.表1中Waveform2數(shù)據(jù)帶有噪聲,其余數(shù)據(jù)集中的數(shù)據(jù)不含噪聲.為了模擬適度規(guī)模的樣本數(shù)據(jù)流,所有UCI數(shù)據(jù)實驗每次均從訓(xùn)練數(shù)據(jù)集中隨機(jī)抽取(不放回)一個訓(xùn)練樣本供IERF算法學(xué)習(xí),直到所有訓(xùn)練樣本全部學(xué)習(xí)完畢.本節(jié)實驗中,IERF算法不遺忘訓(xùn)練樣本.實驗在2.3GHz,1GBPC上進(jìn)行.3.1限制參數(shù)的選擇3.1.1數(shù)據(jù)集實驗結(jié)果葉節(jié)點分裂閾值參數(shù)Δ影響IERF算法的性能,合適的閾值Δ可以保證IERF算法具有高的分類正確率和低的時空開銷.由前面所述,分裂閾值參數(shù)Δ的選擇與樣本混合比α大小有關(guān),且α取值在內(nèi),為此我們將樣本混合比α按照0,0.1,…,1.0進(jìn)行取值,對不同α取值下的IERF算法(采用50棵樹)分別統(tǒng)計分類錯誤率、模型復(fù)雜度(葉節(jié)點數(shù)量)和訓(xùn)練時間開銷,最后綜合考慮各方面因素從而確定合適的閾值參數(shù)Δ.不同α取值下的IERF算法在小訓(xùn)練樣本數(shù)據(jù)集上運行50次,在大訓(xùn)練樣本數(shù)據(jù)集上運行10次.選擇表1中的6個數(shù)據(jù)集進(jìn)行實驗.算法每次運行時,每個數(shù)據(jù)集都被隨機(jī)劃分為一個訓(xùn)練集和一個測試集,各自集合的樣本數(shù)量劃分見表1.IERF算法在不同α取值下的分類錯誤率如圖1所示,當(dāng)α∈[0,0.2]時,所有數(shù)據(jù)集上的分類錯誤率低且穩(wěn)定,當(dāng)α>0.2時,部分?jǐn)?shù)據(jù)集的分類錯誤率開始變大,當(dāng)α>0.5時,所有數(shù)據(jù)集的分類錯誤率顯著變壞.這是由于α過大導(dǎo)致葉節(jié)點分裂遲滯,以至于整體分類能力下降,特別在數(shù)據(jù)集Waveform2,Wine以及Iris上,α逼近1時分類器已經(jīng)完全失效.IERF算法模型復(fù)雜度(葉節(jié)點的數(shù)量)和訓(xùn)練時間開銷與樣本混合比α的關(guān)系,分別如圖2和圖3所示.由實驗結(jié)果可以看出,當(dāng)樣本混合比α接近0時,IERF算法生成的葉節(jié)點數(shù)量增多,模型復(fù)雜度變大,并且總的訓(xùn)練時間開銷增大,這是由于隨著α減小,每個葉節(jié)點的分裂次數(shù)會逐漸增多,從而導(dǎo)致IERF算法生成的葉節(jié)點數(shù)量增多,并且總訓(xùn)練時間變大.當(dāng)α>0.5時,由圖2可以看出,不同數(shù)據(jù)集下的IERF模型嚴(yán)重變壞,特別是圖2中的Waveform2,Wine以及Iris,這也解釋了為何分類器在α逼近1時完全失效.綜合考慮IERF算法的分類錯誤率、模型復(fù)雜度以及訓(xùn)練時間開銷等因素,我們選擇樣本混合比α=0.2,介于0~0.5之間,使IERF算法既具有高的分類正確率,又保持了適當(dāng)?shù)哪Ｐ蛷?fù)雜度和低訓(xùn)練時間開銷.α=0.2對應(yīng)的分裂閾值參數(shù)Δ=0.31,我們將此參數(shù)作為IERF算法使用的默認(rèn)參數(shù).3.1.2兩種規(guī)則的對比第2.3節(jié)討論中指出,在0≤α≤1中選擇分裂閾值參數(shù),相當(dāng)于適度提早了葉節(jié)點的分裂操作,其目的在于保證分類器能夠更及時的反應(yīng)數(shù)據(jù)流中樣本的特征,增強分類器的判別性能.我們在此對α取值范圍的合理性進(jìn)行實驗驗證.這里分別采用兩種葉節(jié)點分裂判別條件進(jìn)行對比實驗,一是采用在0≤α≤1中確定的默認(rèn)參數(shù)Δ=0.31作為葉節(jié)點分裂判斷依據(jù),稱為本文規(guī)則(ourrule);二是采用等待出現(xiàn)某類非Lm的樣本(Lm為葉節(jié)點分裂前數(shù)量最多的某類樣本),其數(shù)量大于等于Lm樣本數(shù)量,作為葉節(jié)點分裂判斷依據(jù),稱為對比規(guī)則(contrastrule).按照兩種不同的分裂規(guī)則,IERF算法分別在表1的小訓(xùn)練樣本數(shù)據(jù)集上運行50次,在大訓(xùn)練樣本數(shù)據(jù)集上運行10次,訓(xùn)練集和測試集劃分等配置同第3.1.1節(jié).我們對兩種規(guī)則下單棵樹平均的葉節(jié)點分裂次數(shù)、平均的葉節(jié)點數(shù)量、葉節(jié)點上平均存儲的樣本數(shù)量以及整個分類器的分類錯誤率分別進(jìn)行了統(tǒng)計,見表3.從表3可以看出,采用對比規(guī)則的IERF算法,平均分裂次數(shù)遠(yuǎn)遠(yuǎn)小于采用本文規(guī)則算法.分裂次數(shù)的減少,直接導(dǎo)致了每個葉節(jié)點上存儲的樣本數(shù)量增多,葉節(jié)點的判別力下降;同時,分裂次數(shù)的減少也導(dǎo)致了單棵樹葉節(jié)點數(shù)量的減少,使得整個分類器模型的復(fù)雜度變小,整體的分類能力降低.表3中還可以看出,采用對比規(guī)則的算法,分類錯誤率大大高于采用本文規(guī)則的算法,特別是在Wine數(shù)據(jù)集上,對比規(guī)則的算法,在根節(jié)點上分裂條件始終得不到滿足,以至于根節(jié)點的分裂操作一再被延遲,最終導(dǎo)致分類器完全失效.綜上所述,本文在0≤α≤1中選擇分裂閾值參數(shù)是正確有效的.為驗證IERF算法的正確性,本節(jié)將增量學(xué)習(xí)的IERF算法和批量學(xué)習(xí)的ERF算法,在表2的Spam,IonosphereWaveform,Vehicle,Satellite,Segment和Vowel這7個UCI數(shù)據(jù)集上進(jìn)行對比實驗,分別比較兩者的分類正確率、模型復(fù)雜度以及訓(xùn)練時間開銷;對第2.4節(jié)中給出的IERF算法和ERF算法的部分性能參數(shù)進(jìn)行了統(tǒng)計;最后,在噪聲數(shù)據(jù)的敏感性方面對二者進(jìn)行了比較.兩種算法在小訓(xùn)練樣本數(shù)據(jù)集上運行50次,大訓(xùn)練樣本數(shù)據(jù)集上運行10次.訓(xùn)練集和測試集的劃分見表2.兩種算法各使用100棵樹.IERF算法分裂閾值參數(shù)Δ=0.31,且不遺忘樣本,ERF算法使用文獻(xiàn)中的默認(rèn)參數(shù).從表4可以看出,IERF算法的分類正確率與離線批量學(xué)習(xí)的ERF算法相當(dāng),甚至在有些數(shù)據(jù)集上優(yōu)于ERF算法,例如在Ionosphere數(shù)據(jù)集.由于是增量學(xué)習(xí),IERF算法生成的葉節(jié)點數(shù)量比ERF算法的多,但在相同大小的訓(xùn)練數(shù)據(jù)集上,IERF算法總的訓(xùn)練時間開銷要比ERF算法的小.本文第2.4節(jié)對IERF算法和ERF算法的時間開銷進(jìn)行了比較分析,這里給出有關(guān)性能參數(shù)的數(shù)據(jù)統(tǒng)計,見表5表中每組數(shù)據(jù)都是兩個算法運行10次后的平均值,每個參數(shù)的含義見第2.4節(jié).從表5可以看出,?mean的值很小,說明IERF分類器葉節(jié)點上存儲的樣本數(shù)量較少,由此新生成子樹的高度也很小,故二者乘積的均值?mean很小.此外,相對于樣本總數(shù)n,IERF算法的葉節(jié)點分裂次數(shù)p有限,因此第2.4節(jié)中給出的約束條件能夠得到滿足,為此IERF算法的時間開銷通常要小于ERF算法.3.2.2噪聲實驗檢驗ERF算法對于數(shù)據(jù)噪聲具有良好的穩(wěn)定性,為了測試IERF算法對于噪聲的敏感性,這里將IERF算法和ERF算法在加入了噪聲的數(shù)據(jù)集上分別進(jìn)行了實驗.表2中隨機(jī)選擇3個測試數(shù)據(jù)集:Vehicle,Waveform和Ionosphere.實驗按照噪聲級別從0,0.1,…,0.5的順序,依次給3個數(shù)據(jù)集的所有樣本加入噪聲.這里將噪聲級別定義為樣本屬性被噪聲干擾的概率.噪聲按照如下方法添加:計算數(shù)據(jù)集上相應(yīng)屬性的標(biāo)準(zhǔn)導(dǎo)數(shù)σ,產(chǎn)生滿足N(0,σ)分布的隨機(jī)數(shù)疊加到樣本數(shù)據(jù)對應(yīng)的屬性值上,同時保持樣本數(shù)據(jù)的類別標(biāo)記值不變.噪聲實驗結(jié)果如圖4所示,從結(jié)果可以看出,隨著噪聲級別的增加,IERF算法的分類錯誤率保持穩(wěn)定,在Vehicle和Waveform數(shù)據(jù)集上分類準(zhǔn)確度逼近ERF算法,在Ionosphere數(shù)據(jù)集上甚至優(yōu)于ERF算法.實驗證明,IERF算法保持了對數(shù)據(jù)噪聲具有良好穩(wěn)定性的這一性質(zhì).3.3在線增量學(xué)習(xí)算法為檢驗本文提出IERF算法的性能,我們選擇了當(dāng)前幾種主要的在線增量學(xué)習(xí)算法與其比較,包括ITI算法、OnlineAdaboost算法和OnlineSVM算法.其中,ITI算法、以決策樹作為弱分類器的OnlineAdaboost算法和IERF算法都具有相似的樹狀結(jié)構(gòu).4種在線增量學(xué)習(xí)算法在表2的7個數(shù)據(jù)集上分別進(jìn)行了實驗.3.3.1基于iti算法的弱分類器ITI算法是單棵決策樹的增量學(xué)習(xí)算法.每當(dāng)新的訓(xùn)練樣本加入到?jīng)Q策樹后,ITI算法都要檢測并修改決策樹的決策屬性,以確保每個決策節(jié)點上決策屬性是最優(yōu)的.修改決策屬性的方法在文獻(xiàn)中稱為屬性提升.頻繁的屬性提升操作對于模型復(fù)雜度高的決策樹來說將是非常耗時的操作.ITI算法采用C代碼實現(xiàn).OnlineAdaboost算法采用廣泛使用的Oza中OnlineAdaboost.M1算法.Oza將數(shù)據(jù)流按照泊松分布建模,即每個樣本數(shù)據(jù)的到來滿足泊松分布.對每次到來的樣本數(shù)據(jù),每個弱分類器更新K次,K是根據(jù)泊松分布Poisson(λ)產(chǎn)生的隨機(jī)數(shù).根據(jù)新到來的一個樣本數(shù)據(jù)的分類情況來增大或減小泊松分布的參數(shù)λ,進(jìn)而改變每個弱分類器的更新.為了與IERF算法對比,我們選擇100棵決策樹作為弱分類器,決策樹更新算法采用ITI算法來實現(xiàn),整個OnlineAdaboost.M1算法采用C++代碼實現(xiàn).基于SVM的在線增量學(xué)習(xí)算法有很多,但多數(shù)算法只能處理二值分類.ITI算法、OnlineAdaboost.M1算法以及本文提出的IERF算法都可以處理多類別分類.為了便于比較,我們這里選擇文獻(xiàn)中給出的可處理多類別分類的MCSVM算法.文獻(xiàn)中采用迭代的錯誤邊界模型,每次迭代時接收一個新樣本,并給出該樣本的分類結(jié)果,然后根據(jù)樣本真實標(biāo)記值更新分類規(guī)則.算法使用C代碼實現(xiàn),并選擇高斯核(sigma=2).本文提出的IERF算法使用100棵樹,分裂閾值參數(shù)Δ=0.31,采用無優(yōu)化的C++代碼實現(xiàn).實驗使用表2中全部7個數(shù)據(jù)集,所有算法在小訓(xùn)練樣本數(shù)據(jù)集上運行50次,在大訓(xùn)練樣本數(shù)據(jù)集上運行10次.運行時,每個數(shù)據(jù)集都被隨機(jī)劃分為一個訓(xùn)練集和一個測試集,訓(xùn)練集和測試集的劃分見表2.所有算法都采取如下方法進(jìn)行訓(xùn)練:每次從訓(xùn)練數(shù)據(jù)集中隨機(jī)抽取(不放回)一個訓(xùn)練樣本進(jìn)行學(xué)習(xí),直到所有訓(xùn)練樣本全部學(xué)習(xí)完畢.所有算法均不遺忘訓(xùn)練樣本.分類正確率和訓(xùn)練時間開銷的結(jié)果見表6和表7.從表中可以看出,IERF算法分類正確率多數(shù)情況優(yōu)于其他算法,并且具有低訓(xùn)練時間開銷;以決策樹作為弱分類器的OnlineAdaboost算法分類性能要優(yōu)于單棵決策樹的ITI算法,但訓(xùn)練時間開銷非常大,例如表6和表7中OlineAdaboost在大訓(xùn)練樣本數(shù)據(jù)集Spam和Satellite上運算時間過大,以至于沒有給出實驗數(shù)據(jù),這主要是由于ITI算法中單棵決策樹的本身運算代價比較大,多棵決策樹的更新開銷則更顯昂貴;OnlineMulti-SVM算法可以快速處理多類數(shù)據(jù)分類的增量學(xué)習(xí),時間開銷在4種算法中最小,但在多數(shù)數(shù)據(jù)集上分類正確率不高,例如Spam,Ionosphere,Vehicle,Segment和Vowel等數(shù)據(jù)集上的分類正確率明顯低于其他算法.4跟蹤算法實現(xiàn)多目標(biāo)跟蹤IERF算法可以自然應(yīng)用于解決在線視頻跟蹤問題.在視頻跟蹤實驗中,每幀視頻圖像上用于分類器增量學(xué)習(xí)的樣本數(shù)量往往很少,因此,本文提出的IERF算法正好適用于這樣的小規(guī)模數(shù)據(jù)流的應(yīng)用.本節(jié)基于真實的視頻序列的跟蹤實驗可以證明,基于IERF算法的在線視頻跟蹤算法,在復(fù)雜環(huán)境下能夠穩(wěn)定地跟蹤目標(biāo)物體,并且具備多目標(biāo)物體跟蹤的能力.首先介紹基于IERF的在線視頻跟蹤算法,然后給出該算法應(yīng)用于真實視頻序列的實驗結(jié)果.我們將IERF算法和協(xié)同訓(xùn)練框架結(jié)合起來,以實現(xiàn)視頻目標(biāo)的在線跟蹤,同時得益于IERF分類器的多類別分類特性,本文的跟蹤算法可實現(xiàn)多目標(biāo)跟蹤.具體步驟如下:(1)初始化階段.在第1幀視頻圖像上選擇目標(biāo)區(qū)域,提取正負(fù)樣本訓(xùn)練IERF分類器.目標(biāo)區(qū)域的選擇可以由用戶手動標(biāo)注完成,也可以通過物體識別算法自動識別完成.包含目標(biāo)物體的矩形區(qū)域作為正樣本區(qū)域,之外的部分被視為負(fù)樣本區(qū)域.大小規(guī)則的圖像塊作為樣本進(jìn)行處理,相對于單個像素點而言,圖像塊包含更豐富的信息,并且能夠使IERF分類器具有快速的學(xué)習(xí)和識別速度.在初始化階段,為了給IERF分類器提供足夠的訓(xùn)練樣本,我們在正樣本區(qū)域和負(fù)樣本區(qū)域內(nèi)隨機(jī)產(chǎn)生大量子窗口,這些子窗口可以相互重疊,且位置隨機(jī),每個子窗口從9×9像素大小到整幅圖像大小中隨機(jī)產(chǎn)生.子窗口對應(yīng)的圖像塊即可作為樣本進(jìn)行處理,第1幀上100個左右的隨機(jī)子窗口采樣得到的圖像塊即可有效完成分類器的初始化.(2)在線增量學(xué)習(xí)階段.采用半指導(dǎo)學(xué)習(xí)理論中的協(xié)同訓(xùn)練框架,為IERF分類器提供大量無標(biāo)記樣本以完成增量學(xué)習(xí).本文采用顏色直方圖和梯度方向直方圖(HoG)分別作為兩個特征空間(可替換為其他類型的特征),在兩個特征空間下分別訓(xùn)練兩個IERF分類器.利用滑動窗口方法,這兩個分類器分別對同一幀視頻圖像進(jìn)行分類識別.顏色空間的分類器提交一部分自身置信度高的樣本交給HoG空間的分類器進(jìn)行增量學(xué)習(xí),同時HoG空間的分類器也提交一部分自身置信度高的樣本給顏色空間分類器進(jìn)行增量學(xué)習(xí).(3)目標(biāo)跟蹤階段.兩個特征空間的IERF分類器各自產(chǎn)生一幅置信圖,兩幅置信圖基于兩個分類器的權(quán)值進(jìn)行疊加整合,最終得到一幀置信圖.通過整合的置信圖,利用camshift算法最終可確定目標(biāo)物體的位置.4.2系統(tǒng)調(diào)度分析本節(jié)給出不同視頻序列下的跟蹤結(jié)果.IERF分類器處理的樣本采用9×9像素大小的圖像塊.每個圖像塊上提取8個方向的HSL顏色直方圖作為顏色特征,同時提取包含9個方向bins的HoG特征.每個特征空間下的IERF分類器各自包含30棵樹.為了釋放不斷增長的存儲空間,IERF算法選擇樣本丟棄,這里采用最近使用策略,T時刻之前的幀數(shù)據(jù)被丟棄,根據(jù)目標(biāo)物體和環(huán)境的變化情況,T選擇10~50.圖5的視頻序列來自PETS2001,結(jié)果證明了本文方法具有多目標(biāo)跟蹤的能力.圖6、圖7為fragrtrack方法和本文方法的對比結(jié)果.圖6中的視頻序列RotatingGirl來自StanBirchfield的頭部視頻數(shù)據(jù)集,視頻中人物頭部快速頻繁地轉(zhuǎn)動,導(dǎo)致目標(biāo)外觀快速頻繁的變化;圖7中的視頻序列Sylvester來自DavidRoss的跟蹤視頻數(shù)據(jù)集由于受到環(huán)境光照強烈的影響,以及目標(biāo)物體大尺度的運動,目標(biāo)外觀發(fā)生了顯著變化.由圖6、圖7可見,在上述復(fù)雜情況下,fragrtrack方法對跟蹤目標(biāo)的更新不夠準(zhǔn)確,從而導(dǎo)致跟蹤失敗;而本文方法能夠及時學(xué)習(xí)并更新對目標(biāo)物體的描述,因此能夠準(zhǔn)確跟蹤.表8中給出了上述3個視頻測試序列下方法和本文方法的統(tǒng)計結(jié)果,正確跟蹤的幀數(shù)由手工統(tǒng)計完成.如果被目標(biāo)物體有25%