基于拉普拉斯回歸主動學習的大數據流分類算法

杜 恒 楊俊成

(河南工業職業技術學院電子信息工程學院 河南 南陽 473000)

0 引 言

在社會生活的許多領域中，每天產生海量的連續數據流[1]，例如：購物網絡的成交記錄、交通監控系統的數據流、新聞報道的數據流等。數據流具有實時到達、連續多變及海量無限等特點[2]，針對這些特點挖掘出有效的知識，已成為數據挖掘領域的難點之一。在線學習[3]和主動學習是解決數據流分類挖掘的有效手段，學習模型的采樣方法是決定分類質量的關鍵點[4]。

極限學習機是解決實時數據流分類問題的一類重要方案。文獻[5]利用加密數據和非加密數據，或者不同類型加密數據0-1分布的隨機性特性作為分類特征，利用訓練好的極限學習機對未知數據流進行識別，實現對不同類型數據的自動識別。文獻[6]針對數據流的概念漂移問題，設計了動態的極限學習機實時地調節模型，利用在線學習機制訓練雙隱層結構的極限學習機。極限學習機的隱層節點參數無需調整，學習過程僅需計算輸出權重，因此許多研究人員利用其模型簡單的特點，針對動態數據流實時地訓練分類器[7-8]。另外，文獻[9]采用決策樹和霍夫定界理論學習增量的特征子集和樣本集，采用增量樣本訓練加權貝葉斯分類器，為增量數據設置較大的權重值。當前主流的數據流分類方法[10-11]大多利用學習算法提取數據流的標記樣本和特征子集，再將數據集輸入分類器進行實時訓練，獲得合適的分類器。在動態數據流中標記樣本所占的比例極低，當前的在線學習算法大多學習標記樣本，再通過相似性度量技術選出其他具有判別力的無標記樣本，將擴展后的數據集作為分類器的訓練集，提高分類器的分類準確率。

為了解決數據流中標記樣本所占比例較低的問題，設計了基于拉普拉斯回歸模型的主動學習機制，以經典的最優實驗設計評估標記樣本的最小二乘誤差。然后，將多個約束規則引入主動學習機制中，主動學習程序從無標記樣本集選擇信息量最豐富的樣本集，迭代地擴展標記樣本集。此外，設計了相對支持度差異函數作為分類器的決策函數。最終基于不同維度的數據流進行了仿真實驗，結果表明，本算法不同程度地提高了數據流分類的性能，并且實現了較快的處理速度。

1 數據流分類的問題模型

設分類器模型為Ψ，通過支持度函數決定分類結果，每個分類的支持度表示為：

F={F1,F2,…,FM}

(1)

Ψ通過最大化以下規則產生決策：

(2)

支持度較高的決策難以再提高分類器模型的性能，其重要性應該較低，所以支持度越高說明誤分類率越低，如果支持度的差值越低，那么決策的不確定性越大。提出相對支持度差異函數(Relative Support Difference Function,RSDF)評估x最大支持度和其他類支持度的差異：

(3)

圖1為RSDF的示意圖，普通的支持度方法將數據點劃分區域，RSDF方法則為數據點劃分界限。因為相鄰數據流之間的相似性一般較大，而RSDF為支持度差值大的情況產生新的決策，否則保持當前的分類器模型，以此可大幅度減少分類器的訓練次數，提高系統的總體效率。

(a) 普通支持度分類實例(2個類) (b) RSDF的分類實例(2個類)

(c) 普通支持度分類實例(3個類) (d) RSDF的分類實例(3個類)圖1 相對支持度差值函數的示意圖

數據流以序列的形式到達，每一批數據流的樣本順序對分類器的性能具有影響，所以在預處理步驟將每批數據流的樣本隨機化處理。設置閾值參數負責篩選樣本，如果支持度差值低于閾值，則重新訓練分類器。算法1是數據流分類的總體算法，其中函數floor()表示向下取整運算。

算法1數據流分類的總體流程

輸入：數據流DS，批的大小n，類數量M，分類器訓練程序class_training()，標記函數label()，分類器classifier()，支持度函數FM()，分類器所需的樣本數量m，無標記樣本量budget

輸出：數據流分類結果

1.i=0;

2.forj=0tomdo

3. 查詢xj的標記;

4.classifier()=class_training(xj,label(xj));

5.endfor

6.budget=floor(n×budget);

7. 采集一批數據流DSi={xi1,xi2,…,xin};

8. 將DSi的樣本隨機化;

9.forj=0tondo

10.ifRSDF(x)

11.ifbudget>0then

12. 查詢xj的標記;

/*訓練分類器*/

13.classifier()

=class_training(xj,label(xj));

budget=budget-1;

14.endif

15.endif

16.endfor

2 最優實驗設計理論

采集數據流的標記樣本復雜且耗時，引入主動學習技術減少數據的采集成本。以經典的最優實驗設計(Optimal Experimental Design,OED)[12]為模型，設計了拉普拉斯最小二乘回歸模型的主動學習機制。

OED學習以下的線性函數：

y=xβ+ε

(4)

式中：x和y分別為輸入變量和輸出變量；β為權重向量；ε為0均值的未知誤差。假設不同觀察的誤差獨立，但方差相等，記為σ2。給定輸入x和權重向量β，學習的輸出為f(x)=xβ。假設存在一個標記樣本集(z1,k1),(z2,k2)，…,(zm,km)，其中ki為zi的標記，使用z表示特征向量，x為樣本。通過最小化均方誤差之和計算權重β：

(5)

通過式(6)可簡單估計出β：

(6)

(7)

(8)

式中：ki為zi的標記；λ1和λ2均為正則化參數。λ1為平滑度懲罰項，負責維護輸入空間的流形結構，λ2控制回歸模型的稀疏性。若要分離相鄰點xi和xj，應為式(8)的損失函數分配低權重值Wij(Wij=Wji)。

通過近鄰圖建模輸入空間的流形結構。設樣本xi的最近鄰為xj，xi和xj的相似性矩陣W定義為：

(9)

基于相似性矩陣的拉普拉斯定義為L=D-W，D為對角矩陣，Dii=∑Wij。式(8)的最優解表示為：

(10)

(11)

拉普拉斯正則化OED主要針對線性模型，對于非線性模型的效果較差，本文利用核函數將線性系統擴展至非線性系統。設H表示重生核Hilbert空間(Reproducing Kernel Hilbert Space,RKHS)[14]，核函數為K，將式(8)的優化問題重寫為RKHS問題：

(12)

最優解f′計算為：

(13)

式中：K()為正定Mercer核(Positive Definite Mercer Kernel,PDMK);αi為決策變量。

將式(13)的f′(x)代入式(12)，可獲得如下凸可微性質的目標函數：

arg minα(y-KZXα)T(y-KZXα)+λ2αTKZXα+

(14)

根據目標函數推導出最優解：

(15)

σ2M-1(M-Λ)M-1=σ2(M-1-M-1ΛM-1)

(16)

采用拉普拉斯正則模型改善了OED的效果，但依然忽略了一個關鍵問題：在標記樣本所占比例較低的情況下，高密度區域的無標記樣本對分類器準確率的影響力高于低密度區域的樣本，高密度區域的無標記樣本對回歸模型的特征空間具有代表性作用。

3 主動學習機制設計

本文提出基于約束規則的半監督主動學習算法，主動學習算法從無標記樣本集選擇信息量最豐富的樣本，迭代地擴展標記樣本，再使用LapRLS回歸作為半監督回歸模型。

3.1 基于聚類的代表性規則和多樣性規則

將接近分類中心的樣本選為代表樣本。同一類的樣本為相似樣本，不同類的樣本為多樣性樣本，利用該性質度量樣本的代表性和多樣性。采用自組織映射算法(Self Organizing Map, SOM)對樣本進行非線性聚類處理，SOM[15]將每個分類中心作為一個神經元。樣本x的代表性定義為樣本x和分類中心的相似性，通過以下兩步計算代表性值。

步驟1計算樣本x和最優神經元wx,bmn的標準距離：

(17)

步驟2將rx歸一化為[0,1]，再轉化為相似性評分，相似性評分定義為：

(18)

式中:N為SOM的神經元數量；|wx,bmn|為分配到wx,bmn的樣本數量；|wj|為分配到第j個神經元的樣本數量。

選擇的樣本應當具有較大的多樣性，使用余弦相似性度量樣本的多樣性，樣本xi和xj間的相似性為：

(19)

(20)

樣本x和標記樣本集間的余弦相似性越小，則多樣性越大。余弦多樣性僅僅考慮了樣本和標記樣本間的冗余，所以余弦相似性無法評價全部數據集的多樣性。圖2是余弦多樣性度量無標記樣本的示意圖，圖中樣本1和樣本2的余弦多樣性相等s1=s2，而無標記樣本2可以代表全部的數據集，無標記樣本1僅能代表小規模的數據集，所以選擇類2的中心樣本作為代表樣本。

圖2 余弦相似性度量類簇的示意圖

圖2的分類1已經被標記樣本解釋，所以選擇無標記樣本1作為代表性樣本。而類2的標記樣本比例小于類1，所以需要更多的樣本才能解釋全部數據集，選擇無標記樣本2有助于采樣多樣化的區域。最終的多樣性度量定義為：

(21)

3.2 基于主動學習選擇訓練樣本

為了同時利用分類的代表性和多樣性，最小化LapRLS模型的方差，最終的樣本選擇策略定義為：

(22)

式中:z1,z2,…,zm為從{x1,x2,…,xn}選擇的樣本;M={KXZKZX+λ1KXXLKXX+λ2KXX}；γ為RZ的權重參數。tr{M-1}為核拉普拉斯正則化A最優OED的規則，簡稱為LRAD；det{M-1}為核拉普拉斯正則化D最優OED的規則，簡稱為LRDD。

采用順序優化算法求解以下問題，選擇第一個樣本集z：

(23)

(24)

設選擇的k個樣本集為Zk={z1,z2,…,zk}∈{x1,x2,…,xn}，通過求解以下問題決定是否選擇第(k+1)個樣本zk+1：

zk+1=minz∈χzk{1-(γRz+(1-γ)cdivz)}×

(25)

zk+1=minz∈χzk{1-(γRz+(1-γ)cdivz)}×

(26)

式(25)-式(26)的計算量主要是計算矩陣的逆(kzkzT+Mk)-1，使用SMW(Shermen-Morrison-Woodbury，SMW)公式加速矩陣計算，給定一個矩陣M和兩個列向量u和v，SMW公式為：

(27)

基于SMW公式更新Mk+1的逆：

(28)

3.3 樣本選擇算法

算法2是訓練樣本選擇算法的主要流程。首先，通過主動學習選擇滿足以下3個規則的樣本集：最大化樣本的分類代表性，最大化樣本的分類多樣性，最小化LapRLS模型的方差。算法考慮了3個約束規則：① 樣本越接近類的中心且類的規模越大，則樣本的分類多樣性越大；② 樣本和標記樣本的余弦相似性越大，則樣本的分類多樣性越大；③ LapRLS參數的置信區間越小，則LapRLS模型的方差越小。結合了3個規則在標記樣本較少的情況下實現了較高的預測準確率。

算法2訓練樣本選擇算法

輸入：樣本集χ={x1,…,xN}，選擇的樣本數量S

輸出：信息量豐富的樣本集z={z1,z2,…,zM}?χ

Fork=0,1，…,S-1do

Fori=1,2,…,N

Ifxi∈χthen

infor(xi)={1-(γRxi+(1-γ)cdivxi)}·

Endif

Endfor

zk+1argminX∈χInfor(X);

z=z∪{zk+1};

endfor

returnz;

3.4 基于共生特征的概念漂移方案

動態數據流為非獨立同分布，所以會產生概念漂移的現象。概念漂移導致基于舊數據流建立的模型無法適用于新數據流，所以應當使學習模型支持概念漂移的情況。目前主要有兩種概念漂移的解決方案：滑動窗口方案和衰減函數方案[16]。滑動窗口方案保留滑動窗口的近期樣本，忽略舊樣本。衰減函數方案通過加權方式強化樣本時間屬性的重要性，即新樣本的重要性高于舊樣本。本文采用衰減函數方案處理概念漂移的問題，共生特征的衰減更新方程為：

F(ki,kj)=α×F(ki,kj)+Ⅱ[ki=km,kj=kt,km,kt∈k]

(29)

式中：Ⅱ[·]為指示函數；0<α<1為衰減因子。設兩個共生特征為(km,kt)，如果ki=km,kj=kt,km,kt∈k，那么Ⅱ=1。頻率F(ym,yt)能夠加強標記間的依賴性，共生特征的頻率越低，衰減度越大。

將式(29)擴展為關于“標記-特征-樣本”的聯合分布，定義為：

F(k,xi，xj)=β×F(k,xi，xj)+Ⅱ[k=km,

km∈k,xi=vi,xj=vj]

(30)

式中:k為特征;x為樣本;β為衰減因子;指示函數Ⅱ[y=ym,ym∈Y,xi=vi,xj=vj]=1。

使用式(29)和式(30)的衰減方案，修改共生特性關于時間的相關性和聯合分布。基于共生特征的概念漂移算法如算法3所示。

算法3基于共生特征的概念漂移算法

Foreach樣本xindo

N=N+1;

算法1預測x的類標記；

算法2更新學習模型；

Foreachi=1tokdo

Foreachj=i+1tokdo

(27)式更新F(ki,kj);

Endfor

Foreach特征do

(28)式更新“標簽-特征-值”表；

Endfor

Endfor

更新數據流的分類結果；

Endfor

3.5 貝葉斯數據流分類器

考慮穩定數據流，即X(t)=X,C(t)=C,pk(t)=pk，假設訓練集共有n個標記樣本，(x1,c1),(x2,c2),…,(xn,cn)。

(31)

式中：I(A)為指示函數，如果A為真，返回1，如果A為假，返回0。

假設一個新樣本x0到達，且f(x|k)分布和pk均未知，分類器訓練的方法是將x0分為類k，類k的均值與x0最為接近：

(32)

使用式(3)的相對支持度差異度量樣本和類的距離。

(2) 概念漂移數據流的貝葉斯分類器。每次新數據流到達，基于類標記更新估計的平均值，更新方法為：

(33)

對于s≤t，其他類估計的均值保持不變。

假設到達一個新樣本x(t+1)，使用t時訓練的貝葉斯分類器將x(t+1)分類，更新貝葉斯分類器的步驟為：

Step3使用t+1的模型將x(t+2)分類。

Step5重復Step 1-Step 4。

4 仿真實驗和結果分析

4.1 實驗數據集

選擇6個多標記公開數據集作為benchmark數據集[17]，使用MOA(Massive Online Analysis, MOA)[18]合成1個概念漂移數據集，合成方法為：① 采用隨機樹產生器(Random Tree Generator, RTG)創建一個決策樹，隨機選擇樣本屬性，每個葉節點隨機分配一個類標記。② 為屬性分配均勻隨機數，作為決策樹的類標記，樹的深度為5。對ENRON數據集的1 702個樣本做概念漂移處理，漂移點分別定位至數據流的1/4、1/2和3/4時間點，RTG樹的標記數為28，標記基數為4，標記間的依賴率為0.25。實驗數據集的基本信息如表1所示。

表1 實驗數據集的屬性

4.2 實驗方法

主要存在兩個常用的數據流實驗和評價方法，分別為：維持評價方法和預測序列方法。維持評價方法運用當前的分類模型處理獨立的測試集；預測序列方法首先預測每個到達樣本的標記，再使用該樣本更新學習模型。采用預測序列方法[17]測試數據流分類器的準確率，對每個到達樣本x的處理步驟為：

Step2更新分類器模型：如果可獲得x的正定標記Y，則基于樣本x和正定標記Y更新分類器模型。

4.3 性能評價指標

采用6個性能評價指標從3個角度評價數據流分類器的性能：基于采樣的度量準確率和F1，評估分類器對于不同采樣的優劣；基于標記的度量微平均F1和宏平均F1，評估分類器對于不同標記的優劣；基于排名的度量平均準確率和排序損失，評估多標記分類器的總體分類性能。此外，評估了模型的更新時間和預測時間，綜合評估算法的時間效率。

4.4 實驗結果與分析

(1) 相對支持度差異的閾值實驗。測試算法1中RSDF閾值對算法性能的影響，實驗將閾值分別設為{0.005,0.01,0.02,0.05,0.1,0.2,0.3}，觀察不同閾值的分類性能結果。

圖3是不同閾值關于6個數據流的結果，圖中顯示20NG、OHSUMED、IMDB和TMC2007數據集的性能幾乎保持穩定。SLASHDOT數據集的結果顯示，閾值對SLASHDOT數據集的性能存在一定的影響。ENRON數據集為概念漂移處理的數據集，其結果顯示，閾值高于0.1的分類器性能較高，并且較為穩定。

(a) 基于采樣的F1指標

(b) 基于采樣的準確率指標

(c) 微平均F1指標

(d) 宏平均F1指標

(f) 排序損失指標圖3 不同閾值關于6個數據流的結果

閾值影響分類器模型的更新頻率，所以影響數據流分類的效果。如果閾值過小，分類器保持舊的模型參數，導致模型對新到達數據流的分類準確率降低。如果閾值過大，更新分類器模型，導致分類器的穩定性降低。根據圖3的實驗結果，后續的實驗將閾值設為定值0.1。

(2) 對比實驗分析。選擇4個近期的數據流分類算法作為對比算法，橫向評估本算法的性能，采用的對比算法分別為：基于自適應隨機森林分類算法(ARForest)[19]，多樣性評估的分類器(NDM)[20]，針對概念漂移問題的分類器(DUaCD)[10]以及基于動態極限學習機的分類器(DELM)[6]。選擇這4個算法的原因如下：ARForest和DELM均為基于主動學習機制的預測分類方案，而本算法也包含了主動學習機制。DUaCD和DELM均針對概念漂移問題設計了解決方案，本算法也考慮了概念漂移問題。NDM提出了新的多樣性評估方法，本算法則采用了相對支持度差異評估方法。

圖4是5個數據流分類器對于6個數據流的分類結果。總體而言，本算法對于DELM、OHSUMED、SLASHDOT和TMC2007數據集實現了明顯的提高效果。5個算法對于概念漂移的ENORN數據流分類準確率均較低，但本算法依然取得了較好的結果。5個算法對于IMDB數據流的分類準確率最低，主要因為IMDB的樣本量最多(120 919)，而表計量僅為28，所以難以獲得較高的分類準確率。

(a) 基于采樣的F1指標

(b) 基于采樣的準確率指標

(c) 微平均F1指標

(d) 宏平均F1指標

(e) 平均準確率指標

(f) 排序損失指標圖4 數據流分類算法的實驗結果

4.5 時間效率分析

統計了本算法對于每個數據集的平均模型更新時間和評價分類處理時間。實驗環境為CPU型號為core i7 8700, CPU主頻為3.2 GHz, 內存為16 GB。如圖5所示，本算法對于6個數據流的平均模型更新時間在0.6秒到0.95秒之間，現在的大多數數據流分類方案一般將窗口設為若干秒，所以本算法的模型更新時間足以滿足實時性需求。此外，本算法的平均分類時間在0.4秒以下，也實現了較好的實時性。

圖5 不同數據集的模型更新時間和分類時間

5 結 語

本文設計了新的主動學習機制，以期解決數據流中標記樣本所占比例較低的問題。采用基于拉普拉斯回歸模型的主動學習機制，以經典的最優實驗設計評估標記樣本的最小二乘誤差。主動學習程序從無標記樣本集選擇信息量最豐富的樣本集。仿真實驗結果顯示，本算法有效地提高了數據流分類的性能，并且實現了理想的處理速度。

分類器的閾值選擇對模型的性能具有重要的影響，目前通過預處理實驗決定閾值，未來將引入環境學習機制，自適應地根據應用場景決定閾值。