劉俊杰，張 昕，楊 樂(lè)，韓東紅

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

0 引 言

隨著計(jì)算機(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)。對(duì)有噪音的不確定數(shù)據(jù)分類問(wèn)題，為提高分類準(zhǔn)確率，一些學(xué)者采用集成分類器的方法。文獻(xiàn)[2]提出一種基于SVM的集成分類器，采用OC-SVM方法處理不確定性，同時(shí)調(diào)整每個(gè)基分類器的權(quán)重以處理概念漂移。文獻(xiàn)[3]提出的WE-DELM算法使用ELM技術(shù)訓(xùn)練基分類器并動(dòng)態(tài)改變基分類器權(quán)重來(lái)跟蹤不斷演進(jìn)的數(shù)據(jù)流。文獻(xiàn)[4]提出UELM-MapReduce算法，即利用ELM算法對(duì)每個(gè)不確定數(shù)據(jù)流塊并行訓(xùn)練基分類器，根據(jù)基分類器在最新的測(cè)數(shù)據(jù)集上的均方差值對(duì)相應(yīng)的權(quán)重進(jìn)行調(diào)整，同時(shí)替換準(zhǔn)確率最低的分類器。

J Ma等[5]開(kāi)發(fā)了有效的周期模式識(shí)別和特征提取技術(shù)，提出了一個(gè)新的處理框架來(lái)細(xì)化數(shù)據(jù)流，支持不確定數(shù)據(jù)流中的異常檢測(cè)。Shajib B U等[6]設(shè)計(jì)了一種有效的數(shù)據(jù)結(jié)構(gòu)，稱為不確定流樹(shù)以存儲(chǔ)最近的元數(shù)據(jù)。Zhou等[7]對(duì)不確定數(shù)據(jù)流挖掘過(guò)程中top-k查詢、ER-Topk查詢、稀疏性估計(jì)、集合相似性和聚類進(jìn)行了研究，提出了一種新的DSUF-mine算法來(lái)挖掘頻繁的不確定性流。呂艷霞等[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ù)，是指相同的概念可能會(huì)以相同時(shí)間間隔出現(xiàn)。劉志軍等[11]提出一種基于自適應(yīng)快速?zèng)Q策樹(shù)的算法，實(shí)現(xiàn)對(duì)不確定數(shù)據(jù)流的有效分類。曹科研[12]提出了一種障礙空間中不確定數(shù)據(jù)聚類算法(OBS-UK-means)，實(shí)驗(yàn)表明該算法能有效提高不確定數(shù)據(jù)流的聚類效率。張晨等[13]提出了EMicro算法,以解決不確定數(shù)據(jù)流上的聚類問(wèn)題。

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

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

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

1.1 相關(guān)定義

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

(1)

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

(2)

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

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

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

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

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

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

(3)

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

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

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

(4)

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

(5)

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

(6)

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

每個(gè)基分類器對(duì)第n+1個(gè)數(shù)據(jù)塊Sn+1中元組xi分類完成后，首先得出Ej的預(yù)測(cè)均方差值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)集成分類器對(duì)當(dāng)前數(shù)據(jù)流的概念不匹配。

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

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

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

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

在單機(jī)環(huán)境下進(jìn)行的實(shí)驗(yàn)中，機(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í)驗(yàn)中，是非常好的一種模擬數(shù)據(jù)流的方法，并且可以通過(guò)改變超平面的一些特性來(lái)模擬數(shù)據(jù)流的概念漂移。

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

(7)

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

(8)

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

(9)

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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