基于異構(gòu)分類器集成的增量學(xué)習(xí)算法

熊 霖，唐萬梅

重慶師范大學(xué) 計算機與信息科學(xué)學(xué)院，重慶401331

1 引言

機器學(xué)習(xí)是人工智能領(lǐng)域的主要研究方向之一，目前的大多數(shù)算法均采用批量學(xué)習(xí)的方式[1]，若對新的數(shù)據(jù)進行學(xué)習(xí)，需要丟棄已經(jīng)訓(xùn)練好的模型，將新數(shù)據(jù)加入原有的數(shù)據(jù)集之中重新訓(xùn)練新模型。近年來物聯(lián)網(wǎng)、社交媒體、互聯(lián)網(wǎng)以及移動通信等領(lǐng)域高速發(fā)展，數(shù)據(jù)流逐漸成為數(shù)據(jù)分析與挖掘的主角，其主要特點有無限性、實時性、易失性與動態(tài)變化性[2]。批量學(xué)習(xí)方式處理動態(tài)數(shù)據(jù)流會面臨如下幾個問題：（1）訓(xùn)練樣本不能一次性獲得，若新數(shù)據(jù)加入后都重新訓(xùn)練模型，則需要消耗大量的時間。在現(xiàn)實生活中，網(wǎng)站點擊量分析、個性化推薦及電力、銀行等行業(yè)每時每刻都產(chǎn)生著龐大的數(shù)據(jù)，如果每次獲得新數(shù)據(jù)就重新訓(xùn)練模型是不切實際的。（2）產(chǎn)生數(shù)據(jù)的環(huán)境是變化的，數(shù)據(jù)流中數(shù)據(jù)的分布或隱含的知識也發(fā)生著變化，可能導(dǎo)致以前訓(xùn)練的模型不再適用于當前的數(shù)據(jù)。（3）數(shù)據(jù)流潛在的海量性導(dǎo)致數(shù)據(jù)無法一次性載入內(nèi)存，從而無法進行完整的批量式學(xué)習(xí)。

1962 年，Coppock 和Freund 在Science 上提出了增量學(xué)習(xí)[3]方法。增量學(xué)習(xí)與人腦學(xué)習(xí)相似，是指在保留以前學(xué)到的知識的情況下不斷學(xué)習(xí)來自環(huán)境的新知識。在學(xué)習(xí)過程中，由于新增加的數(shù)據(jù)相對于原累積的數(shù)據(jù)來說較少，可以用新數(shù)據(jù)對原模型進行微調(diào)以獲得和批量學(xué)習(xí)相似的效果。然而設(shè)計增量學(xué)習(xí)算法必定會面對穩(wěn)定-可塑性難題[4]：穩(wěn)定性是指模型必須要保存已經(jīng)學(xué)過的知識，意味著模型的參數(shù)和結(jié)構(gòu)不能改變；而可塑性是指為了學(xué)習(xí)新知識需要對模型的參數(shù)與結(jié)構(gòu)進行調(diào)整。增量學(xué)習(xí)根據(jù)所用分類器的多少可以分為單分類器增量學(xué)習(xí)和集成式增量學(xué)習(xí)。單分類器增量學(xué)習(xí)指在學(xué)習(xí)過程中只用一個模型，模型會根據(jù)新樣本調(diào)整其內(nèi)部結(jié)構(gòu)或者參數(shù)以適應(yīng)數(shù)據(jù)的變化，具有很好的可塑性，但穩(wěn)定性不高。有代表性的單分類器模型有Hoeffding樹[5]、在線被動攻擊算法[6]等，這需要所使用的基分類器本身具備增量學(xué)習(xí)能力。經(jīng)大量實驗表明：集成學(xué)習(xí)可以提高增量學(xué)習(xí)算法的穩(wěn)定性和預(yù)測準確率[7]，集成式增量學(xué)習(xí)以Learn++算法[8]、SEA算法[9]為代表，使用多個分類器對數(shù)據(jù)進行增量學(xué)習(xí)，對所用的分類器是否具備增量學(xué)習(xí)能力沒有要求，這種方法具有很好的穩(wěn)定性，但其可塑性低，難以應(yīng)對數(shù)據(jù)產(chǎn)生突變或者漸變等情況。文獻[10-12]對當前流行的多種增量學(xué)習(xí)算法進行了比較和歸納，可以看出近幾年提出的集成式增量學(xué)習(xí)算法如wESVM[13]、Learn++.CDS[14]、OAUE[15]、WEOB[16]等大多是集成多個同質(zhì)分類器，采用加權(quán)投票的方式對分類器進行結(jié)合的。為應(yīng)對集成模型可塑性差的問題，多數(shù)算法采用動態(tài)權(quán)重的方式對分類器進行結(jié)合，如文獻[16-20]，在計算動態(tài)權(quán)重過程中，查找待測樣本的近鄰時會計算整個數(shù)據(jù)集中的數(shù)據(jù)與待測樣本的距離，這樣的方式極為耗時。尤其對于數(shù)據(jù)流，大量數(shù)據(jù)的存儲與計算將會產(chǎn)生巨大的時空開銷。

針對以往集成式增量學(xué)習(xí)中沒有很好的權(quán)衡穩(wěn)定-可塑性問題和計算動態(tài)權(quán)重耗時問題，本文提出了一種異構(gòu)分類器集成的增量學(xué)習(xí)算法（Incremental learning algorithm based on Heterogeneous Classifier Ensemble，IHCE），在保證算法穩(wěn)定性的前提下，兼顧算法對動態(tài)數(shù)據(jù)的適應(yīng)性，獲得快速而準確的增量學(xué)習(xí)模型。主要采用局部敏感哈希（Locality-Sensitive Hashing，LSH）來保存數(shù)據(jù)分布的梗概，用異構(gòu)的分類器集成模型對不斷變化的數(shù)據(jù)流進行增量學(xué)習(xí)。在對待測樣本做預(yù)測時，根據(jù)待測樣本與基分類器的適應(yīng)性，調(diào)整基分類器的投票權(quán)重，以應(yīng)對數(shù)據(jù)發(fā)生變化等情況。

2 局部敏感哈希（LSH）

對于海量高維的數(shù)據(jù)流，數(shù)據(jù)流中有很多近似重復(fù)記錄，可以采用將相似度很高的數(shù)據(jù)進行剔除，壓縮數(shù)據(jù)得到數(shù)據(jù)流分布的梗概。以往的算法查找待測樣本的近鄰多是采用直接計算每個訓(xùn)練樣本與待測樣本間的歐氏距離[7，11]，這種方法會花費大量的時間，可以采用類似索引技術(shù)來加快查找過程。在提出的IHCE 算法中，采用LSH[21]的方式來剔除數(shù)據(jù)流中近似重復(fù)數(shù)據(jù)和查找待測樣本的近鄰。LSH 是一種高維空間最近鄰搜索算法，其基本思想是：通過hash 函數(shù)把數(shù)據(jù)從高維空間映射到低維空間中，使得高維空間的相似數(shù)據(jù)在低維空間相似概率很高；而在高維空間不相識的數(shù)據(jù)在低維空間相似概率很低，其形式化定義如下。

定義1（局部敏感哈希函數(shù)簇）對于Hash函數(shù)簇H中每個函數(shù)h，如果任意兩點p、q 滿足以下條件，則認為H 是（dist1,dist2,P1,P2）-sensitive的：

（1）若d(p,q)≤dist1,則PrH[h(p)=h(q)]≥P1；

（2）若d(p,q)≥dist2,則PrH[h(p)=h(q)]≤P2。

其中，dist1＜dist2,1 ≥P1＞P2≥0,d(p,q)為p、q 兩點的距離，PrH[ ]表示p、q 兩點的哈希值相同的概率。條件（1）保證兩個相似點以高概率被映射進同一個哈希桶；條件（2）保證兩個不相似的點以低概率映射進同一個哈希桶。

局部敏感哈希常用的距離度量有漢明距離、歐式距離和余弦距離，通常較高維的數(shù)據(jù)采用余弦距離度量較好，給定n 維的兩個樣本點p 和q，兩者的相似性為：

公式（1）表示p、q 兩點向量之間的夾角余弦值，值越大，則兩點越相似。

3 IHCE算法

集成式增量學(xué)習(xí)在訓(xùn)練階段，通常是用新獲得的數(shù)據(jù)塊訓(xùn)練一個或者多個基分類器加入到集成分類器中。如何將基分類器進行結(jié)合是集成式增量學(xué)習(xí)最為關(guān)鍵的一步，在以往的大多數(shù)研究中，多采用加權(quán)投票的方式進行結(jié)合，基分類器權(quán)重來源于該分類器在當時訓(xùn)練集上的分類能力，也就是說基分類器一旦訓(xùn)練完成，分類器的權(quán)重在預(yù)測不同的待測樣本時是不變的。有可能基分類器當時在訓(xùn)練集上分類能力好，獲得較高的權(quán)重，但對預(yù)測數(shù)據(jù)的分類能力差。這在數(shù)據(jù)流中尤為常見，所以針對實時的數(shù)據(jù)調(diào)整基分類器投票權(quán)重顯得非常重要。

IHCE算法主要從三方面入手：（1）采用異構(gòu)的方式構(gòu)建集成模型。對于新獲得的數(shù)據(jù)，采用不同的分類算法分別訓(xùn)練分類器可提高基分類器之間差異性。（2）用實時的數(shù)據(jù)調(diào)整基分類器的投票權(quán)重，以適應(yīng)數(shù)據(jù)的變化。（3）在分類器的預(yù)測階段，兼顧基分類器的歷史表現(xiàn)和對待測樣本的適應(yīng)性，得到分類器對當前待測樣本更合理的投票權(quán)重。算法基本框架如圖1所示。

3.1 LSH保存數(shù)據(jù)分布梗概

IHCE 算法在算法訓(xùn)練之初建立一張空的哈希表，針對每個時間段獲得的數(shù)據(jù)塊，將數(shù)據(jù)分別映射到表中多個固定容量的哈希桶中，若一個桶中的數(shù)據(jù)超過其容量，則用新數(shù)據(jù)替換最舊的數(shù)據(jù)。通過對多個數(shù)據(jù)塊的處理，建立一張保存了數(shù)據(jù)分布梗概的哈希表。

如圖2所示，以三維數(shù)據(jù)為例，用包含4個哈希桶的LSH 對3 個數(shù)據(jù)塊進行處理。假設(shè)B 區(qū)域數(shù)據(jù)經(jīng)哈希映射落入桶2、桶3中，因該區(qū)域數(shù)據(jù)相對于其他區(qū)域數(shù)據(jù)較多且分布廣，所以桶2和桶3中的數(shù)據(jù)更新非?？?，這樣可以快速適應(yīng)數(shù)據(jù)動態(tài)的變化；而對于數(shù)據(jù)分布較少的A 區(qū)域，桶1 中完整地保存3 個數(shù)據(jù)塊中A 區(qū)域的數(shù)據(jù)，這樣可以很好保存數(shù)據(jù)分布的梗概。

3.2 更新投票權(quán)重和訓(xùn)練基分類器

IHCE 算法訓(xùn)練階段，首先會用當前數(shù)據(jù)塊對集成分類器中的每個基分類器進行測試，用該分類器對應(yīng)的分類準確率更新其投票權(quán)重α，更新公式如下：

式中，acc 是第k 個數(shù)據(jù)塊上訓(xùn)練的第j 個基分類器的分類準確率，是第j 個基分類器在第k-1 個數(shù)據(jù)塊上的投票權(quán)重。

圖1 IHCE算法示意圖

圖2 LSH保存數(shù)據(jù)分布梗概

IHCE 算法用異構(gòu)的方式組建集成模型，對于新獲得的數(shù)據(jù)塊，為提高基分類器之間的差異性，用多種不同的分類算法在數(shù)據(jù)塊上分別訓(xùn)練一個基分類器，將訓(xùn)練完成的多個基分類器加入到集成模型中。

3.3 針對待測樣本計算基分類器動態(tài)權(quán)重

IHCE 算法預(yù)測階段，加入了能度量待測樣本與基分類器適應(yīng)性的動態(tài)權(quán)重。算法先從哈希表的桶中找出與待測樣本相似的a 個訓(xùn)練樣本，用每個基分類器對這a 個點進行分類，分類準確率就是該基分類器針對待測樣本的動態(tài)權(quán)重，計算公式如下：

3.4 算法實現(xiàn)

IHCE算法在訓(xùn)練階段，獲得新數(shù)據(jù)塊后，算法主要有三步：（1）用數(shù)據(jù)對集成模型中的每個基分類器進行測試，用分類準確率更新基分類器的投票權(quán)重。（2）將數(shù)據(jù)塊中的數(shù)據(jù)映射進敏感哈希表的某個桶中，如果該桶已滿，則用最新數(shù)據(jù)替換最舊的數(shù)據(jù)。（3）用多種不同的分類算法在該數(shù)據(jù)塊上訓(xùn)練多個基分類器，加入到集成模型中。預(yù)測階段由三部分組成：（1）將待測樣本映射進某個哈希桶中，可認為該桶中的數(shù)據(jù)與待測樣本是相似的。（2）用這些相似數(shù)據(jù)去評估基分類器與待測樣本的適應(yīng)性，得到每個基分類器針對待測樣本的動態(tài)權(quán)重β。（3）將基分類器的投票權(quán)重α 與針對待測樣本所獲得的動態(tài)權(quán)重β 結(jié)合得到該基分類器綜合權(quán)重，用多個基分類器綜合權(quán)重加權(quán)投票判定待測樣本的類別。算法流程如圖3所示。

圖3 IHCE算法流程圖

IHCE算法描述：

輸入：數(shù)據(jù)流DS={D1,D2,…,Dk}，m 種分類算法{A1,A2,…,Am}，測試樣本x，哈希桶數(shù)量c 及容量s。

輸出：帶投票權(quán)重的基分類器集合Ec，保存數(shù)據(jù)流梗概的哈希表HT。

訓(xùn)練過程：

步驟1（1）創(chuàng)建一張包含了c 個桶，每個桶容量為s的空哈希表HT。（2）在數(shù)據(jù)塊D1上，用分類算法{A1,A2,…,Am}訓(xùn)練得到m 個基分類器加入集成分類器Ec。（3）將D1數(shù)據(jù)映射到哈希表HT 中。

步驟2（1）用Dk測試Ec中的基分類器，使用公式（1）更新基分類器的投票權(quán)重。（2）將Dk中的數(shù)據(jù)通過哈希函數(shù)映射到哈希表HT 某個哈希桶中，如果桶容量已滿，用最新數(shù)據(jù)代替最舊的。（3）用{A1,A2,…,Am}在Dk上學(xué)習(xí)得到m 個基分類器，加入集成模型Ec。

步驟3 讀入下一數(shù)據(jù)塊，如果數(shù)據(jù)塊為空，結(jié)束訓(xùn)練過程；否則回到步驟2。

預(yù)測樣本x：

步驟4 將x 通過哈希函數(shù)映射到HT 中，找出與待測樣本x 相似的多個數(shù)據(jù)組成臨時測試集Ds。

步驟5 對于Ec中k×m 個基分類器：

3.5 算法時間復(fù)雜度

設(shè)k 為學(xué)習(xí)次數(shù)，n 為獲得的數(shù)據(jù)塊大小，有m 種分類算法。IHCE 算法訓(xùn)練階段的耗時分析：（1）用m種分類算法在數(shù)據(jù)塊上訓(xùn)練分類器所需時間是O(mn)。（2）將數(shù)據(jù)塊中數(shù)據(jù)映射到哈希表所需時間為O(n)。（3）更新(k-1)×m 個基分類器的權(quán)重所需時間為O(n×(k-1)×m)。

預(yù)測樣本所需時間由兩部分組成：首先找待測樣本的近鄰時間為O(1)，計算基分類器在a 個近鄰數(shù)據(jù)上的準確率時間為O(k-1)×m×a)，n ?a，m 一般情況下較?。?10）。綜上所述，當獲得一個數(shù)據(jù)塊，IHCE 算法處理的時間近似于O(n×k×m)。

4 實驗結(jié)果與分析

本文選擇了4 種增量學(xué)習(xí)算法作為對比算法，在9個數(shù)據(jù)集上做了仿真實驗，以驗證IHCE 算法的有效性。所有實驗均在Inter?Core?i5-4590S@3.00 GHz，Windows 7操作系統(tǒng)上采用Python2.7實現(xiàn)。

4.1 實驗數(shù)據(jù)集

本文實驗數(shù)據(jù)集來源于UCI 數(shù)據(jù)庫中9 個真實的數(shù)據(jù)集。每個數(shù)據(jù)集中都僅包含兩類數(shù)據(jù)，將數(shù)據(jù)類標簽統(tǒng)一成{+1，-1}兩類，將每個數(shù)據(jù)集等量分成10個數(shù)據(jù)塊，基本信息描述見表1。

表1 實驗數(shù)據(jù)集信息

4.2 實驗設(shè)置

本文選擇了4 個常見的增量學(xué)習(xí)算法作為對比算法：增量Passive-Aggressive算法[6]（IPA）、Learn++算法[8]、Adaptive Budget Perceptron[22]（ABP）和增量SGD算法[23]（ISGD）。集成模型中的基分類算法統(tǒng)一選用決策樹，由于IHCE 算法是異構(gòu)的，因此還加入支持向量機和AdaBoost 兩種算法。對比算法的參數(shù)來源于原文獻的實驗參數(shù)。IHCE 算法中的另外兩個主要參數(shù)分別是：哈希桶的個數(shù)和桶容量，增加桶的數(shù)量和容量可以提升算法的性能，但會增加存儲空間。為了兼顧算法的分類精度和空間開銷，經(jīng)多次實驗后，設(shè)置哈希桶個數(shù)c=10，桶容量設(shè)置為：數(shù)據(jù)塊中樣本數(shù)量/100。

每個數(shù)據(jù)集分成等量的10塊，每種算法依次在前9個數(shù)據(jù)塊上進行增量學(xué)習(xí)，最后1塊僅用作分類器每次學(xué)習(xí)后的測試集。為了使得實驗數(shù)據(jù)更加可靠，重復(fù)進行實驗5次，并計算分類準確率的平均值。

4.3 實驗結(jié)果與分析

如圖4展示了5種算法訓(xùn)練的分類器隨著訓(xùn)練樣本的增多在測試集上分類準確率的變化趨勢，用折線表示每個分類器對新增數(shù)據(jù)學(xué)習(xí)后在測試集上的分類準確率的變化情況。子圖中橫坐標代表參加訓(xùn)練的數(shù)據(jù)占整個實驗數(shù)據(jù)集的百分比，縱坐標則是各分類器在測試集上的分類準確率。表2 給出了每個實驗數(shù)據(jù)集上，5種分類算法8次增量學(xué)習(xí)完成后，在測試數(shù)據(jù)集上的分類準確率（平均值±標準差）。

從圖4 可以看到，在數(shù)據(jù)集banknote、svmguide 和Diabetic 上，5 種分類算法訓(xùn)練的分類器隨著訓(xùn)練集增加，分類準確率都沒有太大的提升，主要是因為增加的訓(xùn)練數(shù)據(jù)和建立初始模型的數(shù)據(jù)相似。其余數(shù)據(jù)集上，IPA 和ISGD 算法分類準確率有一定的波動，這是因為前后加入訓(xùn)練的數(shù)據(jù)隱含的類邊界發(fā)生了較大的改變，這兩種算法可塑性高，對數(shù)據(jù)的變化非常靈敏。而相比之下，IHCE分類器和Learn++分類器由于保留了大量先前學(xué)到的知識，用新增訓(xùn)練數(shù)據(jù)對模型進行微調(diào)，從而分類準確率穩(wěn)步上升。

從總體上看，IHCE 算法從最初分類器的建立一直到整個學(xué)習(xí)過程完成，其分類準確率均比對比算法要高，這是因為該算法在學(xué)習(xí)過程中不僅保留了所學(xué)到的知識，而且根據(jù)新增數(shù)據(jù)實時調(diào)整基分類器的投票權(quán)重，使得集成分類器能適應(yīng)數(shù)據(jù)的變化。用哈希表來保存數(shù)據(jù)流的梗概，在算法預(yù)測階段，能通過哈希表非常迅速的找到與待測樣本相似的數(shù)據(jù)，針對待測樣本加入動態(tài)權(quán)重，動態(tài)地調(diào)整每個基分類器的綜合權(quán)重，使集成模型能很好地應(yīng)對數(shù)據(jù)分布發(fā)生突變等情況。對于數(shù)據(jù)塊之間沒有發(fā)生明顯分布變化的數(shù)據(jù)集banknote、svmguide、Diabetic，IHCE 算法和對比算法相比分類準確率稍高；對于前后發(fā)生明顯變化的另6 個數(shù)據(jù)集，IHCE算法比對比算法有更加顯著的分類效果。

綜合圖4 和表2 的結(jié)果可知：當完成9 個數(shù)據(jù)塊的增量學(xué)習(xí)后，本文提出的IHEC 算法在8 個數(shù)據(jù)集上的分類準確性都比其他算法要高，其中在biodeg、Crowdsourced 和sonar 數(shù)據(jù)集上表現(xiàn)的非常明顯，本文算法能較好地兼顧增量學(xué)習(xí)中的穩(wěn)定與可塑性，有一定的通用性。

IHCE算法由于在訓(xùn)練階段會對基分類器權(quán)重做實時更新，理論上要比4種對比算法耗時更多。實驗過程中發(fā)現(xiàn)：ABP、IPA 和ISGD 算法用時明顯少于IHCE 和Learn++算法，但IHCE算法在有些數(shù)據(jù)集上運行所花費的時間甚至比Learn++算法要短。這是因為Learn++算法在訓(xùn)練分類器的過程中，對帶權(quán)重的樣本隨機采樣用于基分類器的訓(xùn)練，如果訓(xùn)練的基分類器誤分類樣本權(quán)重之和大于0.5，則舍去該基分類器。這就導(dǎo)致Learn++算法需要反復(fù)取樣來訓(xùn)練基分類器，以達到用戶設(shè)定的基分類器數(shù)量。

綜上所述，本文提出的IHCE 算法在保留了以前學(xué)到的知識的情況下，還能很好地應(yīng)對數(shù)據(jù)發(fā)生變化等情況。在9 個實驗數(shù)據(jù)集上顯示：IHCE 算法分類準確率通常高于常用的4 種增量學(xué)習(xí)算法[6，8，22-23]，而且學(xué)習(xí)過程更加穩(wěn)定，說明了本文提出的IHCE算法是有效的。

5 結(jié)論

圖4 5種算法在9個數(shù)據(jù)集上增量學(xué)習(xí)表現(xiàn)

表2 5種算法在9個數(shù)據(jù)集上學(xué)習(xí)表現(xiàn)對比%

增量學(xué)習(xí)模型應(yīng)盡量多保存已經(jīng)學(xué)到的知識，還能很好地應(yīng)對數(shù)據(jù)的變化。針對以往集成式增量學(xué)習(xí)算法的不足，提出了基于多分類器異構(gòu)的集成式增量學(xué)習(xí)算法（IHCE）。通過多分類器異構(gòu)的方式增加了基分類器之間的差異性，用LSH表和多個分類器保留了所學(xué)到的知識，實時更新基分類投票權(quán)重，并在預(yù)測階段加入針對待測樣本的動態(tài)權(quán)重，以調(diào)整基分類器的綜合權(quán)重，使得模型適應(yīng)數(shù)據(jù)動態(tài)的變化，在多個數(shù)據(jù)集上的仿真實驗證明了該算法能較好地應(yīng)對增量學(xué)習(xí)中穩(wěn)定-可塑性難題，是有效的。但IHCE 算法和大多數(shù)集成式增量學(xué)習(xí)算法一樣，隨著學(xué)習(xí)的進行，模型規(guī)模會變得比較龐大。今后，在提高分類準確率的同時提高算法運行速率還需要進一步研究。