基于DELM的不確定數(shù)據(jù)流分類算法

劉俊杰，張 昕，楊 樂，韓東紅

(1.山西工程技術(shù)學(xué)院 信息工程與自動化系，山西 陽泉 045000；2.東北大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，遼寧 沈陽 110819)

0 引 言

隨著計算機(jī)及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，實(shí)際應(yīng)用中產(chǎn)生了大量不確定數(shù)據(jù)流，面向不確定數(shù)據(jù)流環(huán)境的分類處理具有重要的應(yīng)用前景。基于此，研究并實(shí)現(xiàn)高效的不確定數(shù)據(jù)流的分類算法十分必要。受最小二乘回歸法的啟發(fā)，Bi等[1]提出了基于支持向量機(jī)的全支持向量分類算法(TSVC)。對有噪音的不確定數(shù)據(jù)分類問題，為提高分類準(zhǔn)確率，一些學(xué)者采用集成分類器的方法。文獻(xiàn)[2]提出一種基于SVM的集成分類器，采用OC-SVM方法處理不確定性，同時調(diào)整每個基分類器的權(quán)重以處理概念漂移。文獻(xiàn)[3]提出的WE-DELM算法使用ELM技術(shù)訓(xùn)練基分類器并動態(tài)改變基分類器權(quán)重來跟蹤不斷演進(jìn)的數(shù)據(jù)流。文獻(xiàn)[4]提出UELM-MapReduce算法，即利用ELM算法對每個不確定數(shù)據(jù)流塊并行訓(xùn)練基分類器，根據(jù)基分類器在最新的測數(shù)據(jù)集上的均方差值對相應(yīng)的權(quán)重進(jìn)行調(diào)整，同時替換準(zhǔn)確率最低的分類器。

J Ma等[5]開發(fā)了有效的周期模式識別和特征提取技術(shù)，提出了一個新的處理框架來細(xì)化數(shù)據(jù)流，支持不確定數(shù)據(jù)流中的異常檢測。Shajib B U等[6]設(shè)計了一種有效的數(shù)據(jù)結(jié)構(gòu)，稱為不確定流樹以存儲最近的元數(shù)據(jù)。Zhou等[7]對不確定數(shù)據(jù)流挖掘過程中top-k查詢、ER-Topk查詢、稀疏性估計、集合相似性和聚類進(jìn)行了研究，提出了一種新的DSUF-mine算法來挖掘頻繁的不確定性流。呂艷霞等[8]提出一種基于VFDT算法的WBVFDTu算法。Wang等[9]在MEME(multiple expectation-maximization for motif elicitation)的基礎(chǔ)上，提出了一種多屬性不確定數(shù)據(jù)流的基元發(fā)現(xiàn)算法。

文獻(xiàn)[10]認(rèn)為不確定數(shù)據(jù)流中產(chǎn)生了周期性概念往復(fù)。所謂周期性的概念往復(fù)，是指相同的概念可能會以相同時間間隔出現(xiàn)。劉志軍等[11]提出一種基于自適應(yīng)快速決策樹的算法，實(shí)現(xiàn)對不確定數(shù)據(jù)流的有效分類。曹科研[12]提出了一種障礙空間中不確定數(shù)據(jù)聚類算法(OBS-UK-means)，實(shí)驗表明該算法能有效提高不確定數(shù)據(jù)流的聚類效率。張晨等[13]提出了EMicro算法,以解決不確定數(shù)據(jù)流上的聚類問題。

綜上所述，面向不確定數(shù)據(jù)流的分類處理主要面臨以下挑戰(zhàn)：適應(yīng)高速無限的數(shù)據(jù)流環(huán)境；檢測并處理概念漂移及概念往復(fù)；處理數(shù)據(jù)的不確定性。

對此，文中提出一種將不確定數(shù)據(jù)向確定數(shù)據(jù)轉(zhuǎn)換的方法，并且在極限學(xué)習(xí)機(jī)的基礎(chǔ)上提出基于分塊矩陣的并行極限學(xué)習(xí)機(jī)，以應(yīng)對大規(guī)模的流數(shù)據(jù)；針對實(shí)際應(yīng)用中不確定數(shù)據(jù)流蘊(yùn)含的概念存在往復(fù)出現(xiàn)的特點(diǎn)，基于WE-DELM算法[14]提出基于概念緩沖的加權(quán)集成分布式極限學(xué)習(xí)機(jī)算法(CBWE-DELM)，可以在新概念發(fā)生時模型并不需要每次都重新學(xué)習(xí)，更適用于有概念往復(fù)現(xiàn)象的不確定數(shù)據(jù)流的分類問題。

1 面向不確定數(shù)據(jù)流的基于概念緩沖的加權(quán)集成分布式極限學(xué)習(xí)機(jī)算法

1.1 相關(guān)定義

定義1(不確定數(shù)據(jù)元組和實(shí)例)：給定一個不確定數(shù)據(jù)元組xi共有個m實(shí)例，設(shè)xi的j個實(shí)例為每個不確定數(shù)據(jù)實(shí)例的概率，則有：

(1)

定義3(不確定數(shù)據(jù)實(shí)例的分類)：給定類別標(biāo)簽共L個，即可將實(shí)例進(jìn)行分類，得到不確定數(shù)據(jù)實(shí)例屬于某個類別Cl(1≤l≤L)。

(2)

即所有不確定實(shí)例屬于類別的概率和。

1.2 基于概念緩沖的CBWE-DELM算法思想及框架模型的實(shí)現(xiàn)

根據(jù)數(shù)據(jù)到達(dá)時間，將數(shù)據(jù)流分割成不相交的塊，每個包含相同數(shù)量的元組；利用DELM在這n個不確定數(shù)據(jù)塊上訓(xùn)練基分類器。為了更新集成分類模型，需要維護(hù)一個類分布表群，即所有基分類器單獨(dú)保存一個類分布表，表中記錄各個對應(yīng)分類器的分布器概率。分類器Ej的類分布表如下：Ej,{JCl,jpcl},1≤l≤L。其中JCl為類別標(biāo)簽，jpcl為類別JCl出現(xiàn)的概率，計算方法見定義3及定義5。

在分類器更新和剪枝階段，根據(jù)當(dāng)前樣本更新和縮減集合分類器，但舊的分類器被裁剪之后不會被立即刪除。為了做到類似刪除效果，文中設(shè)計了一個用于放置緩存的模型，用來保存舊的分類器已經(jīng)出現(xiàn)的舊概念。然后用提出的方法來更新緩沖區(qū)管理的概念，具體方法如下：

數(shù)據(jù)塊到達(dá)時，如果數(shù)據(jù)流中存在新概念，則需要更新集成分類器中的基分類器；若數(shù)據(jù)流中沒出現(xiàn)新概念，則不需要更新。

第一步是測量緩沖區(qū)中的類分布表與新概念的類分布表之間的差異Djk，計算方式如下：

(3)

其中，jpcl為新概念的類分布表；kpcl為緩沖區(qū)中的類分布表。

CBWE-DELM算法的模型框架如圖1所示，它能夠?qū)崟r檢測隨時間演化的數(shù)據(jù)漂移的同時記憶學(xué)習(xí)到的歷史概念。在第Sn+1個數(shù)據(jù)塊到達(dá)時，將當(dāng)前數(shù)據(jù)塊中所有元組單獨(dú)分類，其分類結(jié)果由集成分類模型中每個基分類器投票產(chǎn)生。

圖1 CBWE-DELM算法的模型框架

(4)

根據(jù)式5得出Ej對應(yīng)的預(yù)期均方差值：

(5)

MSEr表示在數(shù)據(jù)塊Sn+1上將樣本xi分類為C的概率等于Ci的類分布。作隨機(jī)性預(yù)測時分類器均方誤差度量：

(6)

其中，P(c)(P(c)∈(0,1))表示Sn+1中每個類的占比值。

每個基分類器對第n+1個數(shù)據(jù)塊Sn+1中元組xi分類完成后，首先得出Ej的預(yù)測均方差值MSEj，接著將Ej的權(quán)值設(shè)定為：WEj=MSEr-MSEj。

如果WEj≤0，建立新的基分類器E0，設(shè)其權(quán)值為WE0，用數(shù)據(jù)塊Sn+1重新訓(xùn)練，得出E_errj和MSEj；否則認(rèn)為現(xiàn)集成分類器對當(dāng)前數(shù)據(jù)流的概念不匹配。

CBWE-DELM算法的偽代碼如算法1所示。

2 實(shí)驗及結(jié)果分析

2.1 實(shí)驗環(huán)境

分布式環(huán)境下的實(shí)驗具體設(shè)置為：Hadoop集群(版本號：0.20.2)共有8臺機(jī)器，主節(jié)點(diǎn)設(shè)置一臺，數(shù)據(jù)節(jié)點(diǎn)共有7臺PC，所有節(jié)點(diǎn)均使用Linux5.6系統(tǒng)、Intel Quad Core 2.66GHz處理器、內(nèi)存的大小設(shè)置為4 GB。

在單機(jī)環(huán)境下進(jìn)行的實(shí)驗中，機(jī)器使用Windows 7系統(tǒng)配置了Intel(R) Core(TM) i5-2450M @2.50 GHz的處理器，4 GB內(nèi)存。

2.2 數(shù)據(jù)集

HyperPlane數(shù)據(jù)集常用在數(shù)據(jù)流仿真實(shí)驗中，是非常好的一種模擬數(shù)據(jù)流的方法，并且可以通過改變超平面的一些特性來模擬數(shù)據(jù)流的概念漂移。

已知隨機(jī)生成每個樣本中服從均勻分布在區(qū)間值為0到1中的屬性值xi，可以根據(jù)式7定義一個m維的超平面：

(7)

數(shù)據(jù)生成過程的第一步要隨機(jī)生成xi的權(quán)重ai(1≤i≤m)，其中ai∈[0,1]，且a0滿足如下公式：

(8)

隨機(jī)樣本中被標(biāo)記為正樣例的元素會滿足式9，反之將其標(biāo)記為負(fù)樣例。

(9)

下面介紹如何模擬數(shù)據(jù)的概念漂移。首先定義三個變量：樣本的權(quán)值、權(quán)值變化范圍、權(quán)值改變方向，分別用α、β、γ表示，其中γi={-1,1}。根據(jù)α、β、γ控制概念漂移的產(chǎn)生過程，即據(jù)此改變固定數(shù)量的樣本，每次更改都需要重新度量a0的值以創(chuàng)建一個新的超平面。

此外，為了驗證CBWE-DELM算法對具有往復(fù)的概念漂移不確定數(shù)據(jù)流的適應(yīng)性和高效性，需要使用對應(yīng)數(shù)據(jù)集。周期地改變上述三個變量，形成具有概念往復(fù)的不確定數(shù)據(jù)流。對實(shí)驗中的4 000 000條數(shù)據(jù)，將周期設(shè)置為500 000條，也就是說每過一次周期，改變α、β、γ的值。隨機(jī)改變5次，即具有5個不同的屬性權(quán)值的超平面。

設(shè)類別A、B、C、D分別對應(yīng)上述周期內(nèi)數(shù)據(jù)，那么實(shí)例X=(x0,x1,…,xn)根據(jù)以下情況進(jìn)行類別判定：根據(jù)判定條件，可以得到10個互不相同的區(qū)間分隔500 000條實(shí)驗數(shù)據(jù)。每隔500 000條記錄便重復(fù)上述操作一次，確?？倲?shù)據(jù)周期相同。

2.3 概念往復(fù)不確定數(shù)據(jù)流環(huán)境下的算法對比

實(shí)驗結(jié)果如圖2和圖3所示?？梢钥闯?，當(dāng)數(shù)據(jù)集較小時，準(zhǔn)確率上兩算法相近，沒有太大差別。但是WE-DELM算法的準(zhǔn)確率在數(shù)據(jù)集增加時顯著降低，CBWE-DELM有較好的表現(xiàn)。從圖3可以看出，在沒有概念往復(fù)的小規(guī)模數(shù)據(jù)集上，由于CBWE-DELM需要建立緩沖區(qū)，所以在速度上略低于WE-DELM。然而當(dāng)數(shù)據(jù)集的規(guī)模開始增大時，CBWE-DELM算法可在跟蹤時間推移的數(shù)據(jù)漂移的同時記憶學(xué)習(xí)到歷史概念，而WE-DELM算法不斷更新的時間消耗遠(yuǎn)超過CBWE-DELM在緩沖區(qū)上消耗的時間，所以CBWE-DELM在速度上遠(yuǎn)高于WE-DELM。

圖3 訓(xùn)練時間曲線

3 結(jié)束語

提出的CBWE-DELM算法解決了具有概念漂移的不確定數(shù)據(jù)流的分類問題和不確定數(shù)據(jù)流的概念往復(fù)問題。在高速不確定數(shù)據(jù)流的環(huán)境下，通過在WE-DELM算法上加入可以保存歷史數(shù)據(jù)的緩沖區(qū)，優(yōu)化了算法性能。經(jīng)實(shí)驗證明，CBWE-DELM算法在性能上有著良好的提升。