杜 恒 楊俊成

(河南工業(yè)職業(yè)技術(shù)學(xué)院電子信息工程學(xué)院 河南 南陽 473000)

0 引 言

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

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

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

1 數(shù)據(jù)流分類的問題模型

設(shè)分類器模型為Ψ，通過支持度函數(shù)決定分類結(jié)果，每個分類的支持度表示為：

F={F1,F2,…,FM}

(1)

Ψ通過最大化以下規(guī)則產(chǎn)生決策：

(2)

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

(3)

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

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

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

數(shù)據(jù)流以序列的形式到達，每一批數(shù)據(jù)流的樣本順序?qū)Ψ诸惼鞯男阅芫哂杏绊懀栽陬A(yù)處理步驟將每批數(shù)據(jù)流的樣本隨機化處理。設(shè)置閾值參數(shù)負責(zé)篩選樣本，如果支持度差值低于閾值，則重新訓(xùn)練分類器。算法1是數(shù)據(jù)流分類的總體算法，其中函數(shù)floor()表示向下取整運算。

算法1數(shù)據(jù)流分類的總體流程

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

輸出：數(shù)據(jù)流分類結(jié)果

1.i=0;

2.forj=0tomdo

3. 查詢xj的標記;

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

5.endfor

6.budget=floor(n×budget);

7. 采集一批數(shù)據(jù)流DSi={xi1,xi2,…,xin};

8. 將DSi的樣本隨機化;

9.forj=0tondo

10.ifRSDF(x)

11.ifbudget>0then

12. 查詢xj的標記;

/*訓(xùn)練分類器*/

13.classifier()

=class_training(xj,label(xj));

budget=budget-1;

14.endif

15.endif

16.endfor

2 最優(yōu)實驗設(shè)計理論

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

OED學(xué)習(xí)以下的線性函數(shù)：

y=xβ+ε

(4)

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

(5)

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

(6)

(7)

(8)

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

通過近鄰圖建模輸入空間的流形結(jié)構(gòu)。設(shè)樣本xi的最近鄰為xj，xi和xj的相似性矩陣W定義為：

(9)

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

(10)

(11)

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

(12)

最優(yōu)解f′計算為：

(13)

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

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

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

(14)

根據(jù)目標函數(shù)推導(dǎo)出最優(yōu)解：

(15)

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

(16)

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

3 主動學(xué)習(xí)機制設(shè)計

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

3.1 基于聚類的代表性規(guī)則和多樣性規(guī)則

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

步驟1計算樣本x和最優(yōu)神經(jīng)元wx,bmn的標準距離：

(17)

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

(18)

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

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

(19)

(20)

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

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

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

(21)

3.2 基于主動學(xué)習(xí)選擇訓(xùn)練樣本

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

(22)

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

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

(23)

(24)

設(shè)選擇的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是訓(xùn)練樣本選擇算法的主要流程。首先，通過主動學(xué)習(xí)選擇滿足以下3個規(guī)則的樣本集：最大化樣本的分類代表性，最大化樣本的分類多樣性，最小化LapRLS模型的方差。算法考慮了3個約束規(guī)則：① 樣本越接近類的中心且類的規(guī)模越大，則樣本的分類多樣性越大；② 樣本和標記樣本的余弦相似性越大，則樣本的分類多樣性越大；③ LapRLS參數(shù)的置信區(qū)間越小，則LapRLS模型的方差越小。結(jié)合了3個規(guī)則在標記樣本較少的情況下實現(xiàn)了較高的預(yù)測準確率。

算法2訓(xùn)練樣本選擇算法

輸入：樣本集χ={x1,…,xN}，選擇的樣本數(shù)量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 基于共生特征的概念漂移方案

動態(tài)數(shù)據(jù)流為非獨立同分布，所以會產(chǎn)生概念漂移的現(xiàn)象。概念漂移導(dǎo)致基于舊數(shù)據(jù)流建立的模型無法適用于新數(shù)據(jù)流，所以應(yīng)當(dāng)使學(xué)習(xí)模型支持概念漂移的情況。目前主要有兩種概念漂移的解決方案：滑動窗口方案和衰減函數(shù)方案[16]?；瑒哟翱诜桨副Ａ艋瑒哟翱诘慕跇颖荆雎耘f樣本。衰減函數(shù)方案通過加權(quán)方式強化樣本時間屬性的重要性，即新樣本的重要性高于舊樣本。本文采用衰減函數(shù)方案處理概念漂移的問題，共生特征的衰減更新方程為：

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

(29)

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

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

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

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

(30)

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

使用式(29)和式(30)的衰減方案，修改共生特性關(guān)于時間的相關(guān)性和聯(lián)合分布?；诠采卣鞯母拍钇扑惴ㄈ缢惴?所示。

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

Foreach樣本xindo

N=N+1;

算法1預(yù)測x的類標記；

算法2更新學(xué)習(xí)模型；

Foreachi=1tokdo

Foreachj=i+1tokdo

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

Endfor

Foreach特征do

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

Endfor

Endfor

更新數(shù)據(jù)流的分類結(jié)果；

Endfor

3.5 貝葉斯數(shù)據(jù)流分類器

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

(31)

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

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

(32)

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

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

(33)

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

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

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

Step5重復(fù)Step 1-Step 4。

4 仿真實驗和結(jié)果分析

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

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

表1 實驗數(shù)據(jù)集的屬性

4.2 實驗方法

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

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

4.3 性能評價指標

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

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

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

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

(a) 基于采樣的F1指標

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

(c) 微平均F1指標

(d) 宏平均F1指標

(f) 排序損失指標圖3 不同閾值關(guān)于6個數(shù)據(jù)流的結(jié)果

閾值影響分類器模型的更新頻率，所以影響數(shù)據(jù)流分類的效果。如果閾值過小，分類器保持舊的模型參數(shù)，導(dǎo)致模型對新到達數(shù)據(jù)流的分類準確率降低。如果閾值過大，更新分類器模型，導(dǎo)致分類器的穩(wěn)定性降低。根據(jù)圖3的實驗結(jié)果，后續(xù)的實驗將閾值設(shè)為定值0.1。

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

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

(a) 基于采樣的F1指標

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

(c) 微平均F1指標

(d) 宏平均F1指標

(e) 平均準確率指標

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

4.5 時間效率分析

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

圖5 不同數(shù)據(jù)集的模型更新時間和分類時間

5 結(jié) 語

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

分類器的閾值選擇對模型的性能具有重要的影響，目前通過預(yù)處理實驗決定閾值，未來將引入環(huán)境學(xué)習(xí)機制，自適應(yīng)地根據(jù)應(yīng)用場景決定閾值。