韋 潔 華

(廣州南洋理工職業(yè)學(xué)院通識(shí)教育學(xué)院 廣東 廣州 510925)

0 引 言

隨著移動(dòng)互聯(lián)網(wǎng)的應(yīng)用和普及，視頻流、多媒體流，以及各類實(shí)時(shí)消息流成為了網(wǎng)絡(luò)數(shù)據(jù)的一個(gè)重要組成部分，對(duì)這些實(shí)時(shí)數(shù)據(jù)流進(jìn)行快速、及時(shí)地挖掘和分析是當(dāng)前大數(shù)據(jù)研究領(lǐng)域的一個(gè)重要訴求[1]。數(shù)據(jù)流聚類是數(shù)據(jù)挖掘的一個(gè)重要預(yù)處理步驟，能夠提高后續(xù)數(shù)據(jù)流挖掘分析的效率和效果[2]。由于數(shù)據(jù)流聚類對(duì)效率和準(zhǔn)確率均具有極高的要求，所以近期熱門的深度學(xué)習(xí)技術(shù)難以適用于該情況，而機(jī)器學(xué)習(xí)成為數(shù)據(jù)流聚類領(lǐng)域的重要技術(shù)[3]。在機(jī)器學(xué)習(xí)技術(shù)中，神經(jīng)網(wǎng)絡(luò)具有誤差小、動(dòng)態(tài)性好的優(yōu)點(diǎn)，但收斂速度慢[4]；決策樹分類的速度快、準(zhǔn)確率高且對(duì)高維數(shù)據(jù)性能較好，但對(duì)于不平衡數(shù)據(jù)流性能較弱，且極易過擬合[5]；支持向量機(jī)(Support Vector Machine, SVM)對(duì)二分類問題的處理速度快、準(zhǔn)確性好，但對(duì)大規(guī)模樣本的訓(xùn)練速度很慢，對(duì)多分類問題的效果也較差[6]。

最優(yōu)路徑森林(Optimum Path Forest, OPF)[7]是新出現(xiàn)的一種監(jiān)督學(xué)習(xí)方法，該方法將訓(xùn)練集建模為完全圖，以訓(xùn)練樣本為節(jié)點(diǎn)，以節(jié)點(diǎn)間距離為弧，基于完全圖生成最優(yōu)路徑樹，每棵樹為一個(gè)類別。分類程序計(jì)算樣本和樹的距離，將樣本分類為距離最近的類別樹。OPF不依賴任何參數(shù)，且在訓(xùn)練階段無須參數(shù)優(yōu)化處理，因此其訓(xùn)練和分類均十分快速[8]。OPF的分類精度與SVM接近，且優(yōu)于決策樹、貝葉斯分類器等經(jīng)典的機(jī)器學(xué)習(xí)方法，而其訓(xùn)練速度和分類速度明顯快于SVM，也無須假設(shè)簇的形狀。OPF目前已經(jīng)被研究人員運(yùn)用到許多應(yīng)用領(lǐng)域中，如大數(shù)據(jù)監(jiān)督聚類問題[9]、人臉表情識(shí)別[10]和協(xié)同過濾推薦系統(tǒng)[11]等，并且取得了一定的性能優(yōu)勢(shì)。

在數(shù)據(jù)流的聚類方案中，基于密度的聚類算法是一個(gè)重要的分支，此類算法支持任意形狀的簇。在早期的動(dòng)態(tài)數(shù)據(jù)流聚類算法[12-13]中，大多采用迭代程序或者分治思想對(duì)數(shù)據(jù)流進(jìn)行聚類處理，此類算法只能對(duì)數(shù)據(jù)流進(jìn)行概括，無法反映數(shù)據(jù)流的動(dòng)態(tài)。Clustream[14]是解決數(shù)據(jù)流聚類問題的一個(gè)經(jīng)典框架，該框架在線地對(duì)數(shù)據(jù)流進(jìn)行初級(jí)聚類，并保存初級(jí)聚類的結(jié)果，然后在離線階段由用戶設(shè)定數(shù)據(jù)流的處理措施。Clustream能夠描述數(shù)據(jù)流的動(dòng)態(tài)變化，具有較好的可擴(kuò)展性，許多研究人員對(duì)Clustream框架進(jìn)行了擴(kuò)展，例如：雙層網(wǎng)格和Clustream結(jié)合[15]，二重k近鄰和Clustream結(jié)合[16]。但上述數(shù)據(jù)流聚類算法均為在線和離線混合的處理框架，并且需要用戶輸入一些固定的參數(shù)，如數(shù)據(jù)流維度、微簇半徑等，這些參數(shù)在實(shí)際應(yīng)用中難以確定，如果取值出現(xiàn)偏差，會(huì)導(dǎo)致系統(tǒng)性能產(chǎn)生較大的衰減。

本文設(shè)計(jì)一種基于自適應(yīng)微簇的任意形狀概念漂移數(shù)據(jù)流聚類(Data Stream Clustering based on Adaptive Micro-Clusters, DSCAMC)，該算法支持任意形狀的數(shù)據(jù)流，并且無須預(yù)設(shè)相關(guān)參數(shù)，是一種完全在線的數(shù)據(jù)流聚類算法。本文的貢獻(xiàn)主要有：(1) 開發(fā)遞歸微簇半徑尋優(yōu)機(jī)制，自適應(yīng)地搜索微簇半徑的局部最優(yōu)值。(2) 開發(fā)緩存機(jī)制保留目前暫不相關(guān)的微簇，而這些微簇在未來可能存在相關(guān)性，緩存機(jī)制有助于加快數(shù)據(jù)流的處理。(3) 采用最優(yōu)路徑森林結(jié)構(gòu)組織數(shù)據(jù)流宏簇的完全圖，通過最優(yōu)路徑將新到達(dá)的數(shù)據(jù)分類。借鑒重引力搜索算法的引力機(jī)制，提出微簇的能量函數(shù)，該函數(shù)評(píng)估微簇的空間密集程度，數(shù)據(jù)點(diǎn)越靠近微簇中心，對(duì)能量的貢獻(xiàn)越大。然后將能量最大的微簇作為最優(yōu)路徑樹的根節(jié)點(diǎn)，即代表性節(jié)點(diǎn)(原型)。

1 數(shù)據(jù)流的概念漂移問題

如果一個(gè)目標(biāo)概念隨著時(shí)間變化，此時(shí)發(fā)生概念漂移。設(shè)兩個(gè)目標(biāo)概念為A和B，數(shù)據(jù)流為I={i1,i2,…,in}。假設(shè)在數(shù)據(jù)id之前，目標(biāo)概念固定為A，在數(shù)據(jù)id+1和id+Δx之間發(fā)生概念漂移，目標(biāo)概念A(yù)變?yōu)楦拍頑，其中，Δx為概念漂移的速率。在線的概念漂移分類器在收到一個(gè)數(shù)據(jù)實(shí)例之后，將數(shù)據(jù)流分批，處理數(shù)據(jù)流批的方法主要有三種類型：完全內(nèi)存方法、完全不保存方法和固定窗口方法。本文方法屬于完全不保存和極少量緩存相結(jié)合的方法。

2 最優(yōu)路徑森林分類器

最優(yōu)路徑森林(Optimum Path Forest, OPF)分類器包括一個(gè)監(jiān)督學(xué)習(xí)程序和一個(gè)無監(jiān)督學(xué)習(xí)程序，監(jiān)督學(xué)習(xí)程序主要有完全圖方法和k-NN圖方法，k-NN圖方法需要用戶輸入kmax參數(shù)，該參數(shù)受實(shí)際應(yīng)用的影響較大，所以本文采用完全圖方法?？紤]完全圖的OPF模型，設(shè)Z=Z1∪Z2為一個(gè)標(biāo)記數(shù)據(jù)集，其中Z2和Z2分別為訓(xùn)練集和測(cè)試集。設(shè)λ(s)函數(shù)為樣本s∈Z1∪Z2分配正確的標(biāo)簽，表示為λ(s)∈{1,2,…,c}，s∈Rn。設(shè)S∈Z1為代表性樣本集(原型樣本集)，d(s,t)為樣本s和t間的距離。聚類問題可描述為基于S、d和Z1構(gòu)建最優(yōu)分類器，該分類器可預(yù)測(cè)樣本s∈Z2的標(biāo)簽λ(s)。

OPF分類器構(gòu)建一個(gè)完全圖，每個(gè)節(jié)點(diǎn)為一個(gè)微簇，同一個(gè)類別的微簇組成一棵最優(yōu)路徑樹(宏簇)。文中微簇為球形，但是宏簇為任意形狀。完全圖中每條路徑都有一個(gè)代價(jià)值，計(jì)算從原型到每個(gè)樣本的最小代價(jià)路徑，每處理完一個(gè)樣本，該樣本則獲得一個(gè)標(biāo)簽和最小代價(jià)值。

設(shè)(Z1,A)為一個(gè)完全圖，其中每個(gè)節(jié)點(diǎn)是Z1的一個(gè)微簇，A為邊的集合，每條邊具有一個(gè)權(quán)值。Z1的每個(gè)路徑表示為一組節(jié)點(diǎn)的序列π=，其中(si,si+1)∈A，1≤i≤k-1。每個(gè)路徑π具有一個(gè)路徑成本函數(shù)f()，表示為f(π)。如果對(duì)于任意的路徑τ，均滿足f(π′)≤f(τ)，那么路徑π′定義為最優(yōu)路徑。

代價(jià)函數(shù)fmax定義為：

fmax(π·)=max{fmax(π),d(s,t)}

(1)

式中：fmax(π)為π中相鄰樣本間的最大距離。

OPF包括訓(xùn)練階段和分類階段，訓(xùn)練程序基于fmax和S建立最優(yōu)路徑森林，分類程序?qū)y(cè)試樣本分類。訓(xùn)練階段搜索所有樣本s∈Z1的最優(yōu)路徑P*(s)，建立最優(yōu)路徑森林P。設(shè)R(s)∈S為P*(s)的根節(jié)點(diǎn)，OPF計(jì)算P*(s)每個(gè)s的代價(jià)C(s)，設(shè)s的標(biāo)簽為L(zhǎng)(s)=λ(R(s))，s的前繼節(jié)點(diǎn)為P(s)。分類階段將測(cè)試樣本t∈Z2和最優(yōu)路徑森林連接，尋找代價(jià)最小的樹，代價(jià)最小的計(jì)算方法為：

C(t)=min{max{C(p),d(p,t)}} ?p∈Z1

(2)

式中：節(jié)點(diǎn)p∈Z1為最小化C(t)的節(jié)點(diǎn)。圖1和圖2分別為OPF訓(xùn)練和測(cè)試的實(shí)例。

(a) 數(shù)據(jù)流的完全圖表示 (b) 最小生成樹

(c) 設(shè)定原型樣本 (d) 兩棵最優(yōu)路徑樹圖1 最優(yōu)路徑樹的訓(xùn)練程序例子

(a) 測(cè)試樣本和所有節(jié)點(diǎn)連接 (b) 選擇其中的最優(yōu)路徑圖2 最優(yōu)路徑樹的測(cè)試程序例子

3 數(shù)據(jù)流在線分類器

DSCAMC的目標(biāo)是提高數(shù)據(jù)流的聚類質(zhì)量，降低存儲(chǔ)成本和時(shí)間成本，并且具備概念漂移的能力。

3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

DSCAMC基于密度實(shí)現(xiàn)聚類處理，首先將聚類信息概括為微簇的形式，根據(jù)分簇圖內(nèi)微簇間的隸屬度將微簇連接成宏簇。DSCAMC定義一個(gè)衰減參數(shù)來處理數(shù)據(jù)流的進(jìn)化特性，定義一個(gè)最小密度閾值來區(qū)分微簇和孤立點(diǎn)。衰減參數(shù)定義為在給定時(shí)間區(qū)間到達(dá)的數(shù)據(jù)點(diǎn)總數(shù)量，微簇的最少數(shù)據(jù)點(diǎn)數(shù)量定義為Thden。圖3(a)和圖3(b)分別為一個(gè)微簇的結(jié)構(gòu)和重疊微簇的示意圖，從圖3(b)推理出圖3(c)的分簇圖。

(a) 微簇的結(jié)構(gòu)

(b) 重疊的微簇

(c) 分簇的圖圖3 基于密度的微簇結(jié)構(gòu)示意圖

設(shè)微簇為MC，表示為元組形式：MC(N,N′,C,R,E,EL,M)，其中：C為微簇的中心，定義了微簇在數(shù)據(jù)空間的位置；R為微簇的半徑，定義了微簇的空間范圍，R/2以內(nèi)的區(qū)域稱為核心區(qū)域，R/2～R半徑的區(qū)域稱為邊緣區(qū)域；N為微簇的局部密度，定義為微簇內(nèi)的數(shù)據(jù)點(diǎn)數(shù)量;N′定義為微簇邊緣區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)數(shù)量；E為微簇的能量，每次數(shù)據(jù)點(diǎn)分簇之后均需要更新微簇的能量值E，能量值小于等于0的微簇從分簇圖中刪除；EL為微簇的連接列表，如果一個(gè)微簇的核心區(qū)域和另一個(gè)微簇的核心區(qū)域或者邊緣區(qū)域重疊，則認(rèn)為這兩個(gè)微簇之間連接；M為該微簇所屬的宏簇，宏簇由若干個(gè)連接的微簇組成。

本文算法共維護(hù)4種類型的微簇，分別為核心微簇、潛在微簇、弱微簇和孤立微簇，根據(jù)微簇的密度閾值Thden和能量值E區(qū)分4種微簇類型。

定義1將核心微簇記為MCcore(N,N′,C,R,E,EL,M)，核心微簇應(yīng)滿足以下條件：N≥Thden；N′≤N；Rmin≤R≤Rmax；E>0。

定義2將弱微簇記為MCwea(N,N′,C,R,E,EL,M)，核心微簇應(yīng)滿足以下條件：Thden≤N；N′≤N。

定義3將潛在微簇記為MCpot(N,N′,C,R,E,EL,M)，潛在微簇應(yīng)滿足以下條件：N≤Thden；N′≤N。

定義4將孤立微簇記為MCout(N,N′,C,R,E,EL,M)，孤立微簇應(yīng)滿足以下條件：N

核心微簇和弱微簇的能量都是正值，核心微簇保存于主內(nèi)存，弱微簇保存于緩存。核心微簇主動(dòng)加入簇圖，并且分配了宏簇ID，而弱微簇未被加入簇圖，且未分配宏簇ID。潛在微簇和孤立微簇也未被加入簇圖，且未分配宏簇ID。將孤立微簇視為噪聲數(shù)據(jù)，直接刪除。

3.2 DSCAMC算法設(shè)計(jì)

設(shè)DeDe表示數(shù)據(jù)流每個(gè)單位時(shí)間到達(dá)的數(shù)據(jù)點(diǎn)數(shù)量，該變量描述了數(shù)據(jù)流的速率，設(shè)Rmax和Rmin分別表示微簇的最大半徑和最小半徑，設(shè)Thden表示一個(gè)核心微簇所需的最少數(shù)據(jù)點(diǎn)數(shù)量，設(shè)數(shù)據(jù)流為X={X0,X1,…,Xn}。DSCAMC算法的訓(xùn)練程序包含7個(gè)步驟：

(1) 初始化微簇。

(2) 搜索目標(biāo)微簇。

(3) 更新微簇。

(4) 弱微簇移入緩存。

(5) 清除緩存的弱微簇。

(6) 更新簇圖。

(7) 更新最優(yōu)路徑森林。

DSCAMC聚類程序首先輸入應(yīng)用相關(guān)的聚類參數(shù)(DeDe,Rmax,Rmin,Thden)。當(dāng)數(shù)據(jù)點(diǎn)Xi到達(dá)，計(jì)算Xi和超微簇之間的歐氏距離，搜索其目標(biāo)微簇T。在核心微簇、弱微簇和潛在微簇中搜索目標(biāo)微簇，如果成功找到目標(biāo)微簇T，則提取T的信息；如果未找到，則創(chuàng)建一個(gè)新的潛在微簇。更新每個(gè)微簇的能量，同時(shí)在核心微簇集內(nèi)搜索候選弱微簇，在潛在微簇集內(nèi)搜索候選孤立微簇，在弱微簇集內(nèi)搜索候選死亡微簇。具體搜索方法為：如果核心微簇E≤0，那么該微簇為候選弱微簇；如果一個(gè)弱微簇E≤0，那么該微簇為候選死亡微簇；如果一個(gè)潛在微簇E≤0，那么該微簇為候選孤立微簇。

1) 初始化微簇。將未分簇的數(shù)據(jù)點(diǎn)創(chuàng)建一個(gè)新微簇MCnew，初始化微簇的特征向量，將該數(shù)據(jù)點(diǎn)作為微簇的中心，初始化半徑設(shè)為R=Rmin。局部密度和邊緣區(qū)域的數(shù)據(jù)點(diǎn)數(shù)量均設(shè)為1，即N=N′=1。連接列表EL設(shè)為空集，初始化能量設(shè)為1，即E=1。新生成微簇的局部密度小于密度閾值，所以MCnew的微簇類型為潛在微簇，通過并集運(yùn)算將新創(chuàng)建的微簇加入潛在微簇集中：

MCpot=MCpot∪MCnew

(3)

新微簇的宏簇ID設(shè)為M=0。

2) 搜索目標(biāo)微簇。每當(dāng)一個(gè)數(shù)據(jù)點(diǎn)到達(dá)，DSCAMC計(jì)算數(shù)據(jù)點(diǎn)和每個(gè)微簇中心的歐氏距離d，如果距離d小于微簇的半徑，該微簇即為數(shù)據(jù)點(diǎn)的目標(biāo)微簇。方法定義為：

d(Xi,C)

(4)

目標(biāo)微簇可能為以下三種情況：

(1) 緩存中核心微簇集的一個(gè)弱微簇MCwea。

(2) 潛在微簇集的一個(gè)潛在微簇MCpot。

(3) 核心微簇集的一個(gè)核心微簇MCcore。

圖4是DSCAMC搜索目標(biāo)微簇的流程框圖。首先搜索緩存內(nèi)的弱微簇集，從時(shí)域相關(guān)的微簇集尋找相關(guān)微簇。如果未找到弱微簇，然后搜索潛在微簇集。如果這兩個(gè)步驟均失敗，則在核心微簇集內(nèi)尋找目標(biāo)微簇。

圖4 搜索目標(biāo)微簇的流程

Nt+1=Nt+1

(5)

圖5 更新微簇的流程

如果T是弱微簇MCwea或潛在微簇MCpot，并且局部密度大于閾值Thden，則將T加入核心微簇MCcore內(nèi)。如果T已經(jīng)是一個(gè)核心微簇MCcore，則遞歸地更新它的半徑Rt+1。如果數(shù)據(jù)點(diǎn)在微簇的邊緣區(qū)域，則遞歸地更新微簇的半徑。將數(shù)據(jù)點(diǎn)和微簇邊緣的接近度定義為[{2d(Xt+1,Ct)/R}-1]，更新微簇半徑的方法定義為：

(6)

微簇半徑不會(huì)超過最大值Rmax，僅當(dāng)新數(shù)據(jù)點(diǎn)位于邊緣區(qū)域，才會(huì)更新微簇的中心點(diǎn)Ct+1，該機(jī)制可以減小微簇的更新頻率。如果新數(shù)據(jù)點(diǎn)出現(xiàn)在邊緣區(qū)域，通過式(7)和式(8)分別更新N′t+1和微簇中心Ct+1。

N′t+1=N′t+1

(7)

(8)

式中：k=1,2,…,D，D為數(shù)據(jù)點(diǎn)的維度。

借鑒重引力搜索算法的思想評(píng)估微簇的密集程度，為每個(gè)微簇定義能量函數(shù)，微簇的能量增益跟數(shù)據(jù)點(diǎn)和微簇中心的距離成反比例關(guān)系，核心微簇的能量更新方法為：

(9)

如果是弱微簇，那么它的能量Et+1設(shè)為1；如果是潛在微簇，且密度Nt+1≥Thden，那么它的能量Et+1也設(shè)為1。在圖5中，如果目標(biāo)微簇T是潛在微簇，局部密度Nt+1達(dá)到閾值Thden，那么將T轉(zhuǎn)化為核心微簇，加入核心微簇集MCcore內(nèi)。

4) 弱微簇移入緩存。新數(shù)據(jù)點(diǎn)分簇完成后，減少每個(gè)核心微簇的能量，該機(jī)制和進(jìn)化數(shù)據(jù)流的進(jìn)化屬性吻合，將能量低于0的核心微簇修改為弱微簇。核心微簇T的能量E≤0，說明微簇在時(shí)域不相關(guān)，將此類型的弱微簇移入緩存。將緩存內(nèi)的微簇從簇圖內(nèi)刪除。對(duì)移入緩存的弱微簇作以下處理：(1) 刪除T的邊，EL=?。(2) 刪除T的宏簇，M=0。(3) 從核心微簇集刪除T。(4) 重設(shè)T的死亡能量，E=0.5。(5)T移入緩存的弱微簇集。

5) 清除緩存微簇。如果核心微簇的能量減少，那么緩存的弱微簇能量也隨之減少1/De。將能量小于等于0的弱微簇稱為一個(gè)死亡微簇，從緩存內(nèi)清除。圖6所示是識(shí)別和清除緩存微簇的流程框圖。將能量值小于等于0的弱微簇設(shè)為死亡微簇，從緩存內(nèi)刪除死亡微簇。每個(gè)潛在微簇的能量也逐漸降低，將能量小于等于0的微簇視為孤立微簇，從緩存內(nèi)刪除孤立微簇。

圖6 清除緩存微簇的流程

6) 更新簇圖。在以下4種情況下更新簇圖：

(1) 潛在微簇滿足最小密度閾值，轉(zhuǎn)化為核心微簇。

(2) 弱微簇包含當(dāng)前的數(shù)據(jù)點(diǎn)，轉(zhuǎn)化為核心微簇。

(3) 核心微簇的中心被修改。

(4) 核心微簇被放入緩存，轉(zhuǎn)化為弱微簇。

上述4種情況下微簇的連接列表可能發(fā)生變化，因此需要修改宏簇的數(shù)量。前兩種情況將新頂點(diǎn)加入簇圖，計(jì)算交叉的微簇，然后更新微簇的邊列表EL。如果兩個(gè)核心微簇T和T′的半徑分別為R和R′，那么兩個(gè)微簇的交叉距離d′計(jì)算為：

(10)

如果邊緣列表EL發(fā)生變化，基于新的EL更新宏簇的數(shù)量。對(duì)于第(3)、第(4)種情況，刪除簇圖中對(duì)應(yīng)的頂點(diǎn)，將目標(biāo)頂點(diǎn)和相關(guān)連接從簇圖中刪除，更新簇圖中宏簇的信息。

7) 更新最優(yōu)路徑森林?；诘?節(jié)的模型更新最優(yōu)路徑森林OPF，采用當(dāng)前時(shí)間t的OPF聚類t+1的數(shù)據(jù)流。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境和對(duì)比方法

實(shí)驗(yàn)環(huán)境為PC機(jī)：Intel Core i5- 4690處理器，16 GB內(nèi)存，Windows 10操作系統(tǒng)。基于MATLAB R2014A實(shí)現(xiàn)實(shí)驗(yàn)的算法，從開源軟件管理平臺(tái)github(https://github.com/jppbsi/LibOPF)獲取最優(yōu)路徑森林OPF的源代碼，然后基于文中每個(gè)聚類步驟的程序?qū)崿F(xiàn)總體的DSCAMC數(shù)據(jù)流聚類算法。

本文算法簡(jiǎn)稱為DSCAMC，也是完全在線的數(shù)據(jù)流聚類算法。同時(shí)測(cè)試本文算法在全部?jī)?nèi)存情況下的聚類性能，即對(duì)于每批新到達(dá)的數(shù)據(jù)均基于所有歷史數(shù)據(jù)重新訓(xùn)練分類器，將全部?jī)?nèi)存的方法簡(jiǎn)稱為DSCAMC_MEM，DSCAMC和DSCAMC_MEM的差異如圖7所示。選擇經(jīng)典的Clustream算法[14]作為對(duì)比方案，EHCD[17]作為另一個(gè)對(duì)比方案，EHCD檢測(cè)概念漂移的準(zhǔn)確率較高，并且對(duì)于數(shù)據(jù)流的聚類準(zhǔn)確率也較為理想。選擇ARF[18]作為另一個(gè)對(duì)比方法，ARF基于自適應(yīng)隨機(jī)森林實(shí)現(xiàn)了對(duì)進(jìn)化數(shù)據(jù)流的實(shí)時(shí)聚類，將該算法與本文算法比較，能夠觀察本文最優(yōu)路徑森林的有效性。ACSC[19]是一種基于密度和人工蟻群優(yōu)化算法的數(shù)據(jù)流聚類算法，選擇該算法與本文算法比較，能夠觀察本文算法基于密度聚類的效果。

圖7 DSCAMC和DSCAMC_MEM的差異示意圖

4.2 實(shí)驗(yàn)方法和benchmark數(shù)據(jù)流

實(shí)驗(yàn)采用合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集，合成數(shù)據(jù)集能夠更好地觀察概念漂移的聚類效果。表1是合成數(shù)據(jù)集的主要屬性，Hyperplane數(shù)據(jù)集每隔10 000個(gè)樣本人工加入概念漂移處理，SEA數(shù)據(jù)集每隔15 000個(gè)樣本人工加入概念漂移處理。將每個(gè)數(shù)據(jù)集劃分成30個(gè)等量的批來模擬數(shù)據(jù)流，例如：SEA數(shù)據(jù)集共有60 000個(gè)樣本，每個(gè)批為2 000個(gè)樣本，因?yàn)槊扛?5 000個(gè)樣本發(fā)生概念漂移，所以每隔7.5個(gè)批數(shù)據(jù)流發(fā)生變化。此外采用網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集KDD CUP 99作為真實(shí)benchmark數(shù)據(jù)集，KDD CUP 99是一種不平衡數(shù)據(jù)集，每個(gè)攻擊類型數(shù)據(jù)點(diǎn)的形狀各異，能夠觀察本文算法對(duì)不同形狀數(shù)據(jù)分布是否有效。

表1 合成數(shù)據(jù)集的基本屬性

上述數(shù)據(jù)集均為穩(wěn)態(tài)數(shù)據(jù)集，而本文算法是一種完全在線的聚類算法，數(shù)據(jù)點(diǎn)在聚類之后立刻從內(nèi)存中刪除，所以需要對(duì)實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行處理。采用Mackey-Glass時(shí)間序列生成方法處理：

(11)

采用4階龍格-庫(kù)塔(Runge-Kutta)法計(jì)算式(11)即可產(chǎn)生在線的數(shù)據(jù)流，最終KDD CUP 99共產(chǎn)生了500 s的數(shù)據(jù)流。將進(jìn)化數(shù)據(jù)流的進(jìn)化參數(shù)DeDe設(shè)為1 000個(gè)數(shù)據(jù)點(diǎn)。

4.3 性能評(píng)價(jià)指標(biāo)

精度acc能夠評(píng)估不平衡數(shù)據(jù)集的分類性能，因此采用acc作為性能評(píng)價(jià)指標(biāo)：

(12)

式中：i=1,2,…,c是數(shù)據(jù)集的分類；E(i)是類i的總誤差。

4.4 真實(shí)數(shù)據(jù)流實(shí)驗(yàn)

(1) 參數(shù)敏感性實(shí)驗(yàn)?；贙DD CUP 99數(shù)據(jù)流測(cè)試本文算法的參數(shù)敏感性，本文算法包含密度閾值Thden和微簇范圍Rmin～Rmax兩個(gè)參數(shù)，通過實(shí)驗(yàn)評(píng)估算法性能對(duì)參數(shù)的敏感性。將Thden從1增加至6，觀察算法性能的變化情況，Dede=1 000，Rmin=0.06，Rmax=0.12。圖8是不同Thden的實(shí)驗(yàn)結(jié)果，在大部分時(shí)間的聚類準(zhǔn)確率均接近100%，在150 s時(shí)因?yàn)閿?shù)據(jù)發(fā)生劇烈的變化，準(zhǔn)確率出現(xiàn)明顯的降低，在350 s之后數(shù)據(jù)點(diǎn)也發(fā)生明顯的變化，導(dǎo)致聚類準(zhǔn)確率降低?？傮w而言，Thden=3時(shí)取得最好的效果。

圖8 Thden參數(shù)的敏感性實(shí)驗(yàn)

Rmin分別設(shè)為0.04、0.05、0.06、0.07、0.08，分別測(cè)試最大半徑0.08～0.14的聚類性能，結(jié)果如圖9所示?？梢钥闯?，微簇半徑的范圍對(duì)于聚類性能的影響較小，其中Rmin=0.06、Rmax=0.12時(shí)取得最好的聚類性能。

圖9 微簇范圍的敏感性實(shí)驗(yàn)

(2) 對(duì)比實(shí)驗(yàn)。圖10為6個(gè)數(shù)據(jù)流聚類算法對(duì)網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集KDD CUP 99的準(zhǔn)確率結(jié)果。可以看出，DSCAMC_MEM由于采用所有可用的數(shù)據(jù)集訓(xùn)練分類器，所以獲得最高的聚類準(zhǔn)確率。ACSC是基于密度和人工蟻群優(yōu)化算法的數(shù)據(jù)流聚類算法，該算法通過人工蟻群優(yōu)化算法對(duì)微簇的密度進(jìn)行優(yōu)化處理，也取得十分理想的準(zhǔn)確率結(jié)果。DSCAMC則和ACSC的結(jié)果接近，相較于DSCAMC_MEM則存在明顯的衰減，但DSCAMC的準(zhǔn)確率好于Clustream、EHCD和ARF算法。

圖10 6個(gè)數(shù)據(jù)流聚類算法對(duì)真實(shí)數(shù)據(jù)集的準(zhǔn)確率結(jié)果

圖11為6個(gè)數(shù)據(jù)流聚類算法對(duì)網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)集KDD CUP 99的平均處理時(shí)間結(jié)果。可以看出，DSCAMC_MEM由于采用所有可用的數(shù)據(jù)集訓(xùn)練分類器，所以隨著時(shí)間的推移，其處理時(shí)間也快速提高。ACSC是基于密度和人工蟻群優(yōu)化算法的數(shù)據(jù)流聚類算法，該算法對(duì)每批數(shù)據(jù)均需要采樣人工蟻群優(yōu)化算法對(duì)微簇的密度進(jìn)行優(yōu)化處理，平均每個(gè)樣本的分類時(shí)間也較長(zhǎng)，在數(shù)據(jù)量較大的情況下，其效率較低。本文算法是一種完全在線的數(shù)據(jù)流聚類算法，隨著時(shí)間的推移也始終保持較低的處理時(shí)間。

圖11 6個(gè)數(shù)據(jù)流聚類算法對(duì)真實(shí)數(shù)據(jù)集的處理時(shí)間結(jié)果

4.5 合成數(shù)據(jù)流實(shí)驗(yàn)

概念漂移是進(jìn)化數(shù)據(jù)流的一個(gè)重要問題，采用合成數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，便于觀察本文算法對(duì)概念漂移問題的處理效果。因?yàn)锳CSC、Clustream和ARF三個(gè)算法不支持概念漂移的檢測(cè)處理，所以將DSCAMC_MEM、DSCAMC和EHCD三個(gè)算法進(jìn)行比較。圖12(a)和12 (b)分別是3個(gè)算法對(duì)于Hyperplane數(shù)據(jù)集和SEA數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。圖中DSCAMC_MEM的結(jié)果依然略好于DSCAMC算法，但本文算法也對(duì)概念漂移的情況表現(xiàn)出較為理想的響應(yīng)，在發(fā)生漂移的數(shù)據(jù)點(diǎn)，分類的準(zhǔn)確率出現(xiàn)明顯的衰減，但是在短時(shí)間內(nèi)即可恢復(fù)到較高的準(zhǔn)確率。雖然EHCD也成功檢測(cè)出概念漂移的發(fā)生，但是需要很長(zhǎng)的時(shí)間才能恢復(fù)到穩(wěn)定的狀態(tài)。

(a) Hyperplane數(shù)據(jù)集

(b) SEA數(shù)據(jù)集圖12 合成數(shù)據(jù)集的聚類結(jié)果

5 結(jié) 語

本文提出基于自適應(yīng)微簇的任意形狀進(jìn)化數(shù)據(jù)流聚類算法，設(shè)計(jì)遞歸的微簇半徑更新機(jī)制，自適應(yīng)地搜索微簇半徑的局部最優(yōu)值。采用最優(yōu)路徑森林組織宏簇的完全圖，將能量值最高的微簇作為最優(yōu)路徑樹的根節(jié)點(diǎn)，根據(jù)最優(yōu)路徑將新到達(dá)的數(shù)據(jù)分類。本文算法實(shí)現(xiàn)對(duì)于進(jìn)化數(shù)據(jù)流的完全在線聚類處理方案，對(duì)于任意形狀的數(shù)據(jù)集均具有較好的聚類準(zhǔn)確率，并且實(shí)現(xiàn)了理想的處理效率。

為了保持較高的聚類準(zhǔn)確率，防止一些時(shí)域相關(guān)的微簇被過早地刪除，本文通過緩存機(jī)制保留一些當(dāng)前空間域不相關(guān)的微簇。未來將深入研究結(jié)合計(jì)算機(jī)的體系架構(gòu)實(shí)現(xiàn)快速且規(guī)模小的緩存方案，提高緩存的命中率和匹配速度。