基于自適應微簇的任意形狀概念漂移數據流聚類

韋 潔 華

(廣州南洋理工職業學院通識教育學院 廣東 廣州 510925)

0 引 言

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

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

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

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

1 數據流的概念漂移問題

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

2 最優路徑森林分類器

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

OPF分類器構建一個完全圖，每個節點為一個微簇，同一個類別的微簇組成一棵最優路徑樹(宏簇)。文中微簇為球形，但是宏簇為任意形狀。完全圖中每條路徑都有一個代價值，計算從原型到每個樣本的最小代價路徑，每處理完一個樣本，該樣本則獲得一個標簽和最小代價值。

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

代價函數fmax定義為：

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

(1)

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

OPF包括訓練階段和分類階段，訓練程序基于fmax和S建立最優路徑森林，分類程序將測試樣本分類。訓練階段搜索所有樣本s∈Z1的最優路徑P*(s)，建立最優路徑森林P。設R(s)∈S為P*(s)的根節點，OPF計算P*(s)每個s的代價C(s)，設s的標簽為L(s)=λ(R(s))，s的前繼節點為P(s)。分類階段將測試樣本t∈Z2和最優路徑森林連接，尋找代價最小的樹，代價最小的計算方法為：

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

(2)

式中：節點p∈Z1為最小化C(t)的節點。圖1和圖2分別為OPF訓練和測試的實例。

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

(c) 設定原型樣本 (d) 兩棵最優路徑樹圖1 最優路徑樹的訓練程序例子

(a) 測試樣本和所有節點連接 (b) 選擇其中的最優路徑圖2 最優路徑樹的測試程序例子

3 數據流在線分類器

DSCAMC的目標是提高數據流的聚類質量，降低存儲成本和時間成本，并且具備概念漂移的能力。

3.1 數據結構設計

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

(a) 微簇的結構

(b) 重疊的微簇

(c) 分簇的圖圖3 基于密度的微簇結構示意圖

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

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

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

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

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

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

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

3.2 DSCAMC算法設計

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

(1) 初始化微簇。

(2) 搜索目標微簇。

(3) 更新微簇。

(4) 弱微簇移入緩存。

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

(6) 更新簇圖。

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

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

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

MCpot=MCpot∪MCnew

(3)

新微簇的宏簇ID設為M=0。

2) 搜索目標微簇。每當一個數據點到達，DSCAMC計算數據點和每個微簇中心的歐氏距離d，如果距離d小于微簇的半徑，該微簇即為數據點的目標微簇。方法定義為：

d(Xi,C)

(4)

目標微簇可能為以下三種情況：

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

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

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

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

圖4 搜索目標微簇的流程

Nt+1=Nt+1

(5)

圖5 更新微簇的流程

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

(6)

微簇半徑不會超過最大值Rmax，僅當新數據點位于邊緣區域，才會更新微簇的中心點Ct+1，該機制可以減小微簇的更新頻率。如果新數據點出現在邊緣區域，通過式(7)和式(8)分別更新N′t+1和微簇中心Ct+1。

N′t+1=N′t+1

(7)

(8)

式中：k=1,2,…,D，D為數據點的維度。

借鑒重引力搜索算法的思想評估微簇的密集程度，為每個微簇定義能量函數，微簇的能量增益跟數據點和微簇中心的距離成反比例關系，核心微簇的能量更新方法為：

(9)

如果是弱微簇，那么它的能量Et+1設為1；如果是潛在微簇，且密度Nt+1≥Thden，那么它的能量Et+1也設為1。在圖5中，如果目標微簇T是潛在微簇，局部密度Nt+1達到閾值Thden，那么將T轉化為核心微簇，加入核心微簇集MCcore內。

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

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

圖6 清除緩存微簇的流程

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

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

(2) 弱微簇包含當前的數據點，轉化為核心微簇。

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

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

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

(10)

如果邊緣列表EL發生變化，基于新的EL更新宏簇的數量。對于第(3)、第(4)種情況，刪除簇圖中對應的頂點，將目標頂點和相關連接從簇圖中刪除，更新簇圖中宏簇的信息。

7) 更新最優路徑森林。基于第2節的模型更新最優路徑森林OPF，采用當前時間t的OPF聚類t+1的數據流。

4 實 驗

4.1 實驗環境和對比方法

實驗環境為PC機：Intel Core i5- 4690處理器，16 GB內存，Windows 10操作系統。基于MATLAB R2014A實現實驗的算法，從開源軟件管理平臺github(https://github.com/jppbsi/LibOPF)獲取最優路徑森林OPF的源代碼，然后基于文中每個聚類步驟的程序實現總體的DSCAMC數據流聚類算法。

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

圖7 DSCAMC和DSCAMC_MEM的差異示意圖

4.2 實驗方法和benchmark數據流

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

表1 合成數據集的基本屬性

上述數據集均為穩態數據集，而本文算法是一種完全在線的聚類算法，數據點在聚類之后立刻從內存中刪除，所以需要對實驗數據集進行處理。采用Mackey-Glass時間序列生成方法處理：

(11)

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

4.3 性能評價指標

精度acc能夠評估不平衡數據集的分類性能，因此采用acc作為性能評價指標：

(12)

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

4.4 真實數據流實驗

(1) 參數敏感性實驗。基于KDD CUP 99數據流測試本文算法的參數敏感性，本文算法包含密度閾值Thden和微簇范圍Rmin～Rmax兩個參數，通過實驗評估算法性能對參數的敏感性。將Thden從1增加至6，觀察算法性能的變化情況，Dede=1 000，Rmin=0.06，Rmax=0.12。圖8是不同Thden的實驗結果，在大部分時間的聚類準確率均接近100%，在150 s時因為數據發生劇烈的變化，準確率出現明顯的降低，在350 s之后數據點也發生明顯的變化，導致聚類準確率降低。總體而言，Thden=3時取得最好的效果。

圖8 Thden參數的敏感性實驗

Rmin分別設為0.04、0.05、0.06、0.07、0.08，分別測試最大半徑0.08～0.14的聚類性能，結果如圖9所示。可以看出，微簇半徑的范圍對于聚類性能的影響較小，其中Rmin=0.06、Rmax=0.12時取得最好的聚類性能。

圖9 微簇范圍的敏感性實驗

(2) 對比實驗。圖10為6個數據流聚類算法對網絡入侵數據集KDD CUP 99的準確率結果。可以看出，DSCAMC_MEM由于采用所有可用的數據集訓練分類器，所以獲得最高的聚類準確率。ACSC是基于密度和人工蟻群優化算法的數據流聚類算法，該算法通過人工蟻群優化算法對微簇的密度進行優化處理，也取得十分理想的準確率結果。DSCAMC則和ACSC的結果接近，相較于DSCAMC_MEM則存在明顯的衰減，但DSCAMC的準確率好于Clustream、EHCD和ARF算法。

圖10 6個數據流聚類算法對真實數據集的準確率結果

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

圖11 6個數據流聚類算法對真實數據集的處理時間結果

4.5 合成數據流實驗

概念漂移是進化數據流的一個重要問題，采用合成數據集進行實驗，便于觀察本文算法對概念漂移問題的處理效果。因為ACSC、Clustream和ARF三個算法不支持概念漂移的檢測處理，所以將DSCAMC_MEM、DSCAMC和EHCD三個算法進行比較。圖12(a)和12 (b)分別是3個算法對于Hyperplane數據集和SEA數據集的實驗結果。圖中DSCAMC_MEM的結果依然略好于DSCAMC算法，但本文算法也對概念漂移的情況表現出較為理想的響應，在發生漂移的數據點，分類的準確率出現明顯的衰減，但是在短時間內即可恢復到較高的準確率。雖然EHCD也成功檢測出概念漂移的發生，但是需要很長的時間才能恢復到穩定的狀態。

(a) Hyperplane數據集

(b) SEA數據集圖12 合成數據集的聚類結果

5 結 語

本文提出基于自適應微簇的任意形狀進化數據流聚類算法，設計遞歸的微簇半徑更新機制，自適應地搜索微簇半徑的局部最優值。采用最優路徑森林組織宏簇的完全圖，將能量值最高的微簇作為最優路徑樹的根節點，根據最優路徑將新到達的數據分類。本文算法實現對于進化數據流的完全在線聚類處理方案，對于任意形狀的數據集均具有較好的聚類準確率，并且實現了理想的處理效率。

為了保持較高的聚類準確率，防止一些時域相關的微簇被過早地刪除，本文通過緩存機制保留一些當前空間域不相關的微簇。未來將深入研究結合計算機的體系架構實現快速且規模小的緩存方案，提高緩存的命中率和匹配速度。