周 勝， 劉三民

(安徽工程大學計算機與信息學院， 安徽 蕪湖 241000)

引 言

隨著大數據技術的不斷發(fā)展，數據流挖掘在許多領域得到了廣泛應用，如天氣預報、金融預測、電子商務等。在這些應用領域中，每時每刻都有大量的數據產生，因此需要對這些數據進行實時分類，從而在這些不斷產生的數據流中挖掘有價值的信息。傳統(tǒng)的數據流分類方法需要大量的標簽樣本訓練分類模型，這種方法實時性低，無法有效解決數據流中的概念漂移和噪聲問題。

目前，遷移學習受到了廣泛的關注和研究。遷移學習是指運用已存有的知識對不同但相關領域問題進行求解的一種新的機器學習方法[1]，能夠解決目標域標注樣本不足的問題。遷移學習根據源領域個數可分為單源遷移和多源遷移。單源遷移學習使用一個與目標領域較為相似的源領域進行知識遷移，如Dai等[2]建立一種基于樣本遷移的TrAdaBoost遷移學習算法，通過Boosting方法增加有效數據權重的同時降低無效數據的權重，解決源領域和目標域數據不匹配的問題。文獻[3]為了顯著地減少域分布之間的距離，提出一種降維框架。Zhao等[4-5]設計基于集成學習策略的方案來解決同構域上的單源遷移學習問題，實驗結果顯示該方法具有較高的準確率。當前絕大多數單源遷移學習算法都有先決條件，即是必須獲得與目標領域較為相似的源領域才能進行知識遷移，但是在現實環(huán)境中，獲得與目標領域較為相似的源領域比較困難。針對單源遷移學習方法的不足，眾多國內外學者提出使用多個源領域進行遷移的多源遷移學習算法。Ge等[6]建立一種多源遷移學習算法OMS-TL，根據二部圖實現對目標領域樣本的預測，通過對數據樣本進行重用來進行遷移學習。針對概念漂移數據流分類中的概念重現問題，一種重現概念漂移數據流分類算法RC-OTL被提出[7]，算法根據領域相似度挑選最適合的源領域分類器，實驗結果證明該方法能夠有效克服“負遷移”。文獻[8]構建一種多源迭代自適應算法MSIDA，根據貪婪思想實現最佳源領域的選擇，同時通過創(chuàng)建額外的偽標記實例解決樣本標注問題。文獻[9]設計算法OTLMS，提出將集成源領域分類器和目標領域分類器組合在一起構建預測分類器的方案，解決與目標學習任務無關的噪聲源數據影響分類精度的問題。文獻[10]通過將目標特征空間分成源領域的同構和異構兩個部分，將基分類器加權組合獲得多個源領域分類器，并將多個源領域分類器組合成一個集成模型來解決多源異構遷移學習問題。Yan等[11]構建算法OHTWC，通過計算異構域中同現數據的異構相似性，解決異構域上的數據流分類問題。文獻[12]通過求解每個源領域對應的權值向量，并用對應的權值向量來表示源領域和目標領域之間的相似度，顯著地提高遷移學習效率以及分類性能。文獻[13]設計一種基于自適應棄權策略的數據流分類方法，該方法通過將每個源領域分類器對新到樣本的確定性與給定閾值進行比較，從而選擇合適的源領域分類器參與集成決策，該方法能夠對源領域分類器集成的多樣性進行選擇性控制。文獻[14]通過調整每個源領域分類器對應的權重，同時用目標領域分類器更換權重最大的源領域分類器，該方法能夠在出現概念漂移后快速地恢復集成分類器的分類準確率，從而改善集成分類器的分類性能。

綜上可知，數據流分類采用多源遷移學習技術具有明顯優(yōu)勢，而在遷移學習過程中如何從多個源領域分類器中挑選最合適的源領域分類器，是本文關注點所在。本文基于互近鄰的動態(tài)分類器選擇方法設計出一種局部分類精度計算方案能夠有效地挑選出最合適的源領域分類器，從而有效解決數據流中的概念漂移和噪聲問題。

1 基本概念

K近鄰算法[15]通過計算新到樣本xt和樣本集合中訓練樣本之間的距離，挑選與新到樣本xt距離最近的K個樣本構造新到樣本xt的鄰域，然后基于鄰域的類別信息，根據投票的準則對新到樣本進行分類。

定義1K-近鄰指與新到樣本xt距離最近的K個樣本集合，記Nk(xt)。

然而，K近鄰算法僅通過度量樣本之間的距離(忽略了樣本之間是否互為近鄰)來預測新到樣本的類別標簽，會導致偽近鄰現象的產生。偽近鄰現象如圖1所示，如N3(x1)={x2,x3,x4}表示x1的3個近鄰，N3(x6)={x7,x8,x9}表示x6的3個近鄰，N3(x7)={x6,x8,x9}表示x7的3個近鄰，N3(x5)={x1,x6,x7} 表示x5的3個近鄰，但x5卻不在x1、x6、x7的近鄰中，原因是x1、x6、x7實際上距離x5很遠。

圖1 樣本x5的3-近鄰分布圖

定義2K-互近鄰指互相作為對方的K近鄰，令Nk(xt)表示xt的K個近鄰，Nk(xi)表示xi的K個近鄰，Mk(xt)表示xt的K-互近鄰，可記為Mk(xt)={xi|xi∈Nk(xt)∩xt∈Nk(xi)}。

用互近鄰進行數據流分類可以防止偽近鄰現象產生，提高分類的準確率，這也是本文的出發(fā)點之一。

2 局部分類精度

根據聚類的思想，相鄰樣本間的樣本相似度較大，如果基分類器對新到樣本周圍區(qū)域內的數據樣本分類準確率較高，那么基分類器對新到樣本的類別預測也會比較準確。基于此，本文提出一種局部分類精度計算方法，利用該方法來挑選最合適的源領域分類器。

基于局部分類精度[16]的動態(tài)分類器選擇方法，假設基分類器在新到樣本周圍區(qū)域的分類精度不同，從而通過局部分類精度方法挑選局部分類精度最高的基分類器，并用局部分類精度最高的基分類器的輸出結果作為分類器集合的輸出。局部分類精度計算方法可以分為兩類：基于類別無關的方法和基于類別相關的方法，本文提出的局部分類精度計算方法是基于類別相關的方法，其公式如下：

(1)

其中，K為鄰域的樣本個數，xt為目標領域數據塊中的樣本，Mk(xt)為目標領域數據塊中每個樣本的互近鄰樣本集合，yi為目標領域數據塊中每個樣本的互近鄰樣本的真實類別，fsj(Mk(xt))為源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本的預測類別，dis(Mk(xt),xt)為目標領域數據塊中每個樣本與目標領域數據塊中每個樣本的互近鄰樣本之間的距離，本文采用的是歐式距離。I(x)為示性函數，其定義如下：

(2)

若某源領域分類器能夠正確預測目標領域數據塊中每個樣本的互近鄰樣本的類別，那么示性函數的值為1，否則，示性函數的值為0。

在目標領域數據塊中挑選與目標領域數據塊中每個樣本互為近鄰的K個樣本構造其鄰域，從而將訓練得到的多源領域分類器在目標領域數據塊中每個樣本的K-互近鄰樣本集合Mk(xt)計算局部分類精度LCA。

3 算法描述

在上述互近鄰思想和局部分類精度計算方法基礎上，給出基于互近鄰的多源遷移學習算法(Multi-source Transfer Learning based on Mutual Nearest Neighbor，MNNTL)描述。算法利用互近鄰思想求得目標領域數據塊中每個樣本的互近鄰樣本集合Mk(xt)，然后計算各源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本集合Mk(xt)的局部分類精度，最后將局部分類精度最高的源領域分類器fs與目標領域分類器ft加權集成對目標領域數據塊進行分類，并更新分類器對應的權重以及目標領域分類器。

MNNTL算法的輸入包括目標域數據流DS、源領域分類器集合CS、近鄰樣本數量K；輸出為集成分類模型對目標領域數據塊的分類準確率。其詳細過程為：

step 1參數初始化K，緩存兩個規(guī)模大小相等的數據塊，并分別在數據塊上訓練源領域分類器。

step 2Forj=1,2,...,20，對后續(xù)數據塊Dj依次循環(huán)處理。

step 3基于目標領域數據塊Dj構建目標領域分類器ftj。

step 4計算目標領域數據塊Dj中樣本之間的距離。

step 5在目標領域數據塊Dj中求每個樣本的K-近鄰樣本集合Nk(xt)。

step 6在每個樣本的K-近鄰樣本集合Nk(xt)中求每個樣本的K-互近鄰樣本集合Mk(xt)。

step 7計算各源領域分類器對每個樣本的K-互近鄰樣本集合Mk(xt)的局部分類精度LCAj：

step 8將局部分類精度最高的源領域分類器fs與目標領域分類器ftj加權組合成分類器f對目標領域數據塊Dj進行分類：

其中：xt為目標領域樣本；ωs和ωt分別為源領域分類器和目標領域分類器對應的權值向量；α1,t和α2,t分別為源領域分類器和目標領域分類器對應的權重，初始化

為映射函數[4]。

step 9更新分類器權重α1,t和α2,t：

其中：st(u)=exp{-ηl*(Π(uTxt),Π(yt))}，η=0.5，?u∈Rm；分類器損失函數l*(z,y)=(z-y)2；xt為目標領域樣本，yt為目標領域樣本的真實類別。

step 10更新目標領域分類器ftj。

step 11End For.

算法過程中：step 1表示算法初始化，初始化參數K以及初始化源領域分類器；step 3表示基于目標領域數據塊構建目標領域分類器；step 4～step 6表示求目標領域數據塊中每個樣本的互近鄰樣本集合；step 7表示計算各源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本集合的局部分類精度；step 8表示選取局部分類精度最高的源領域分類器與目標領域分類器加權集成對目標領域數據塊進行分類；step 9表示分類器權重的更新；step 10表示目標領域分類器的更新。這里，step 8使用的分類方法和step 9使用的分類器權重調整方案與文獻[4]提出的分類方法和分類器權重調整方案類似。

4 仿真實驗與結果分析

4.1 仿真數據集

4.2 實驗方案及結果分析

為驗證研究目標，本文把所提方法與現有文獻采用基于K-近鄰思想計算局部分類精度的多源在線遷移學習方法(Multi-source Online Transfer Learning based on K-nearest Neighbor，KNNOTL)進行對比。實驗采用Bayes分類器作為基分類器，采用批處理模式訓練生成，其中源領域數據塊大小為5000，源領域數據塊個數為2，訓練2個源領域分類器，同時基于目標域數據流DS形成20個數據塊，數據塊大小設為500，求得各源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本集合Mk(xt)的局部分類精度，將局部分類精度最高的源領域分類器fs與目標領域分類器ft加權集成對目標領域數據塊進行分類。

實驗1驗證近鄰樣本數量參數影響

為驗證近鄰樣本數量對算法的影響，本文選擇三個近鄰樣本數值通過平均準確率和標準差統(tǒng)計量來說明它們之間的關系，見表1。

表1 MNNTL與近鄰樣本數量間的關系

從表1可以看出，當近鄰樣本數值為7時，此時平均準確率和標準差統(tǒng)計量是最好的。當近鄰樣本數值較大時，每次迭代求得的近鄰樣本與目標領域數據塊中的樣本差異性較大，而近鄰樣本數值較小時，會使得計算出來的各源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本集合的局部分類精度差異性較小。顯然，近鄰樣本數值較大或較小都會影響局部分類精度的計算，導致無法挑選出最合適的源領域分類器。

實驗2驗證MNNTL分類能力

無噪聲環(huán)境下的實驗現象如圖2所示。在無噪聲的情況下，隨著數據塊數量的增加，兩種方法的分類準確率都在不斷地提升。這是由于兩種方法在挑選最優(yōu)源領域分類器的同時，在對目標領域樣本完成分類后，都對目標領域分類器進行了更新，因此能夠更快地適應新到概念。同時相對于KNNOTL，MNNTL的分類準確率沒有明顯的提高，這是由于在無噪聲的情況下，MNNTL使用互近鄰思想求得的互近鄰樣本集合與KNNOTL使用K近鄰思想求得的近鄰樣本集合幾乎相等，導致大多數情況下挑選出來的源領域分類器相同，因此分類準確率差別不大。

圖2 數據集D1實驗結果

噪聲環(huán)境下的實驗現象如圖3與圖4所示。從圖3和圖4可以看出，在分類初期MNNTL和KNNOTL的分類準確率均較低，這是因為在分類初期能獲得的目標領域數據塊較少。在有噪聲的情況下，不僅MNNTL的分類準確率要優(yōu)于KNNOTL，尤其在分類的初始階段優(yōu)勢明顯，而且隨著數據塊的增加，MNNTL分類準確率比KNNOTL增長的幅度要快，這是由于相對于KNNOTL只使用K近鄰思想求近鄰樣本集合，MNNTL使用了互近鄰思想求互近鄰樣本集合，其策略消除了噪聲數據的影響，因此能夠更快地適應概念漂移，使分類模型面對概念漂移具有更好的泛化能力。

圖3 數據集D2實驗結果

圖4 數據集D3實驗結果

綜上分析可知，MNNTL數據流分類方法是可行的，分類準確率優(yōu)于基于K近鄰的數據流分類方法。這是由于MNNTL方法在目標領域數據塊中每個樣本的K近鄰樣本集合的基礎上求得互近鄰樣本集合，避免了偽近鄰現象的產生，即排除了近鄰樣本集合中存在噪聲數據的可能，提高了分類模型的預測精度，同時MNNTL方法是基于類別相關的方法求局部分類精度，能夠從近鄰樣本中挑選出與目標領域數據塊中每個樣本類別相同的樣本，能夠更準確地求得各源領域分類器對目標領域數據塊中每個樣本的互近鄰樣本集合的局部分類精度，從而更準確地挑選出最合適的源領域分類器。兩種方法的平均準確率與標準差統(tǒng)計見表2。

表2 平均準確率和標準差統(tǒng)計量

分析表2中的統(tǒng)計數據可知，MNNTL算法明顯優(yōu)于KNNOTL算法，平均準確率約高出9%，在噪聲環(huán)境下仍然具有較高的準確率，說明MNNTL算法能夠有效地處理數據流中的噪聲，能夠更快地適應概念漂移現象。隨著噪聲數據的增加，MNNTL方法的分類準確率下降程度明顯小于KNNOTL方法，說明MNNTL方法面對噪聲數據流時具有更好的穩(wěn)定性和更強的抗噪性。同時MNNTL方法的標準差明顯大于KNNOTL方法，說明MNNTL方法的分類準確率比KNNOTL方法增長的幅度要快，MNNTL方法能夠更快地適應噪聲數據流。這是因為MNNTL算法利用互近鄰思想求得目標領域數據塊中每個樣本的互近鄰樣本集合，能夠有效避免偽近鄰現象的產生，使分類模型保持較高的分類精度以及較好的穩(wěn)定性。綜上所述，基于互近鄰的多源遷移學習方法是可行的，能夠從K近鄰樣本集合中進一步挑選出互近鄰樣本集合，能夠有效解決數據流中的概念漂移和噪聲問題。

5 結束語

本文結合互近鄰思想和局部分類精度計算方法，提出了一種新的多源遷移數據流分類學習方法。該方法能夠有效利用互近鄰思想，從目標領域數據塊中挑選合適的樣本作為目標領域數據塊中每個樣本的真近鄰，同時構建出局部分類精度計算方法從源領域分類器集合中挑選最合適的源領域分類器與目標領域分類器加權集成。實驗結果表明所設計的方案能夠排除近鄰樣本集合中存在噪聲數據的可能，有效消除噪聲數據的影響。本文研究表明，遷移學習方法能夠解決數據流中概念變化和樣本標注的難題。