熊 霖，唐萬梅

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

1 引言

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

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

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

2 局部敏感哈希（LSH）

對于海量高維的數(shù)據(jù)流，數(shù)據(jù)流中有很多近似重復記錄，可以采用將相似度很高的數(shù)據(jù)進行剔除，壓縮數(shù)據(jù)得到數(shù)據(jù)流分布的梗概。以往的算法查找待測樣本的近鄰多是采用直接計算每個訓練樣本與待測樣本間的歐氏距離[7，11]，這種方法會花費大量的時間，可以采用類似索引技術來加快查找過程。在提出的IHCE 算法中，采用LSH[21]的方式來剔除數(shù)據(jù)流中近似重復數(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算法

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

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

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

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

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

3.2 更新投票權重和訓練基分類器

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

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

圖1 IHCE算法示意圖

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

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

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

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

3.4 算法實現(xiàn)

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

圖3 IHCE算法流程圖

IHCE算法描述：

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

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

訓練過程：

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

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

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

預測樣本x：

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

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

3.5 算法時間復雜度

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

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

4 實驗結果與分析

本文選擇了4 種增量學習算法作為對比算法，在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 實驗設置

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

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

4.3 實驗結果與分析

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

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

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

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

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

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

5 結論

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

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

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