賈東立, 申 飛, 崔新宇

(河北工程大學 信息與電氣工程學院, 邯鄲 056038)

隨著計算機技術(shù)的發(fā)展, 數(shù)據(jù)挖掘技術(shù)在現(xiàn)實生活中的作用也越來越大.與此同時, 類似各類傳感器、股票交易、境污染監(jiān)控、通信傳輸?shù)雀鱾€領(lǐng)域中的數(shù)據(jù)量有了爆發(fā)式的增長.這種海量的數(shù)據(jù)有維度高、實時性強、變化快和延伸性好的特點.如果按照傳統(tǒng)的聚類方法, 先收集數(shù)據(jù)再進行聚類處理已不適合于大規(guī)模的數(shù)據(jù).傳統(tǒng)的聚類算法適用于對有限的數(shù)據(jù)進行聚類分析, 而面對源源不斷的數(shù)據(jù)難以進行存貯處理, 并且也具有很高的時間復雜度[1].可見, 數(shù)據(jù)流聚類分析是當下和未來數(shù)據(jù)挖掘中的一個研究熱點.

關(guān)于數(shù)據(jù)流聚類算法理論, 先后出現(xiàn)了傳統(tǒng)的BIRCH算法、STREAM 算法、CluStream 算法、HPStream 算法、DenStream 算法和D-Stream 算法, 而2003 年Aggarwal C 等提出的以界標窗口聚類分析算法為代表的CluStream算法[2]成為數(shù)據(jù)流聚類算法研究過程中的重要轉(zhuǎn)折點,標志著增量式處理方式的聚類算法自此出現(xiàn).雖然該算法在很多實際工程中都得到了應用, 但對變速的數(shù)據(jù)流處理卻有一定的劣勢.2015 年陳順生等對基于對數(shù)據(jù)時間點以及速度的占比因素的考慮, 提出了一種動態(tài)可調(diào)滑動窗口數(shù)據(jù)流聚類算法DWSWC[3].該算法發(fā)現(xiàn)并記錄了數(shù)據(jù)流流速與窗口大小之間的關(guān)系, 同時為了減少窗口變化的次數(shù), 引入調(diào)節(jié)因子參數(shù)和變異數(shù)據(jù)流聚類結(jié)構(gòu), 提高了數(shù)據(jù)特征屬性對聚類結(jié)果的影響.但該算法過于注重在線微聚類結(jié)果, 離線處理較為簡單, 降低了聚類質(zhì)量.2018 年Fahy C 等提出一種基于密度聚類的蟻群數(shù)據(jù)流聚類算法[4], 將聚類定義為特征空間由低密度區(qū)域分割的高密度區(qū)域.人工螞蟻根據(jù)局部密度和局部相似度, 通過概率選取和丟棄微簇來對簇進行分類, 提高了聚類質(zhì)量和可擴展性.2011年肖裕權(quán)等提出一種基于群體協(xié)作的粒子群優(yōu)化算法的數(shù)據(jù)流聚類算法CluPSO[5].通過指數(shù)直方圖和粒子群算法對用戶數(shù)據(jù)進行聚類分析, 減少了數(shù)據(jù)信息的缺失, 提高了聚類的準確性.但是忽略了閾值T 對于整體聚類效果的影響.

類似于粒子群算法的智能優(yōu)化算法可以在離線部分發(fā)揮該類算法的優(yōu)勢, 通過動態(tài)迭代來優(yōu)化聚類結(jié)果.因此本文提出了一種基于人工蜂群優(yōu)化的數(shù)據(jù)流聚類算法.通過在線部分動態(tài)滑動窗口和改進的初始化閾值半徑T, 將連續(xù)數(shù)據(jù)生成聚類效果更好的微簇;在離線部分中采用改進的人工蜂群算法來改善聚類性能.整體上提高了聚類質(zhì)量.

1 相關(guān)概念

1.1 動態(tài)滑動窗口模型

滑動窗口模型是指在不同的時刻, 根據(jù)窗口的滑動來處理不同的數(shù)據(jù), 滑動窗口處理最后一個數(shù)據(jù)的時刻則是當前的最新時刻.一般來說, 可以通過時間范圍和窗口內(nèi)的數(shù)據(jù)量來定義窗口大小.滑動窗口自左向右的數(shù)據(jù)流傳輸方向, 如圖1 所示.

圖1 滑動窗口模型

本文算法根據(jù)數(shù)據(jù)流速度不斷變化的實際情況引入了一種動態(tài)滑動窗口[6]來滿足內(nèi)存最大的使用率以及數(shù)據(jù)的最大貢獻率.通過將數(shù)據(jù)進入滑動窗口的時間以及流出滑動窗口的時間添加到微聚類特征中, 來提高時間屬性對聚類產(chǎn)生的影響.

滑動窗口由靜態(tài)固定大小W 和動態(tài)可調(diào)節(jié)大小Δw兩 部分組成, 其中W 始終是固定不變的, Δ w是用來動態(tài)調(diào)節(jié)滑動窗口W 大小的.

在數(shù)據(jù)流速度為勻速時, 滑動窗口大小保持為W 不變.而在實際數(shù)據(jù)流傳輸?shù)倪^程中, 每個數(shù)據(jù)項進入滑動窗口的實際時間為RE, 離開滑動窗口的時間是RL.即數(shù)據(jù)在數(shù)據(jù)流窗口內(nèi)停留的時間為δRT=RL-RE.因此, 有3 種情況:

(1)在數(shù)據(jù)傳送速度較慢時, 實際的數(shù)據(jù)流速度vt小于勻速數(shù)據(jù)流v , 即R W =W-Δw.

(2)在數(shù)據(jù)流的傳送過程中實際速度 vt與均勻速度v相差無幾, 即R W =W.

(3)在數(shù)據(jù)流的傳送過程中實際的速度 vt大于均勻速度v , 即 RW =W+Δw.

1.2 微簇特征向量

聚類過程中采用的距離公式如式(1), 式(2).

樣本點到聚類中心的距離, 如式(1):

聚類中心之間的距離, 如式(2):

1.3 微簇閾值半徑T

在處理大規(guī)模的數(shù)據(jù)時, 借鑒Birch 算法CF 樹中第一階段中的閾值T 的概念.由于微聚類是將源源不斷到來的數(shù)據(jù)通過存儲屬性特征進行壓縮儲存, 這樣極大地節(jié)省了內(nèi)存空間.微簇半徑是通過類內(nèi)平均距離或類間平均距離計算的, 因此閾值半徑的取值直接影響了數(shù)據(jù)分布.所以提出一種閾值半徑取值方法, 步驟如下:

(1)通過隨機抽樣的方法在樣本數(shù)據(jù)集中選取適中規(guī)模的數(shù)據(jù);

(2)對抽樣樣本兩兩隨機為N 對, 并計算每對數(shù)據(jù)間的距離;

(3)計算N 對數(shù)據(jù)間的距離的期望EX 和方差DX;

(4)構(gòu)建閾值半徑T, T=P×(EX+0.25×DX); 其中P 通過統(tǒng)計得出取1/3 時效果最優(yōu).

2 離線部分的數(shù)據(jù)流聚類優(yōu)化

2.1 人工蜂群聚類優(yōu)化算法思想

本文在離線部分處理在線部分產(chǎn)生的微簇時, 將K-means 算法與改進的蜂群算法相結(jié)合通過迭代計算得出最優(yōu)聚類結(jié)果.該算法的優(yōu)勢是采用了迭代記憶機制的方法.

2.2 基本人工蜂群算法

人工蜂群算法是Karaboga D[7]提出的一種類似于粒子群算法的優(yōu)化算法, 它的基本思想受啟發(fā)于蜜蜂可以在不接受外界因素的情況下通過不同的分工合作和信息共享找到最豐富的蜜源.人工蜂群對于求解約束優(yōu)化問題有著天然的優(yōu)勢, 相比于經(jīng)典算法來說更容易找到全局最優(yōu)解.通過與其他優(yōu)化算法相比較發(fā)現(xiàn), 人工蜂群算法具有參數(shù)少, 判斷進化條件單一, 探索能力強的優(yōu)點.

2.3 改進的人工蜂群算法

(1)最大最小距離初始化

對于人工蜂群算法來說, 種群的初始化對求解的質(zhì)量和收斂的速度有很大的影響.隨機性較強的初始化會造成局部收斂能力較弱, 影響全局收斂速度.所以針對這個缺點, 本文參考文獻[8,9]引入一種最大最小距離積法來解決初始化隨機性較高的問題.通過該方法, 初始點在選擇時能夠更有針對性的選擇數(shù)據(jù)分布密度大的數(shù)據(jù)點, 并且增大了初始點的分散度; 在此過程中也可以利用乘積的方式進一步擴大數(shù)據(jù)間的差異,減少了算法迭代次數(shù), 提高了收斂速度和精準度.

(2)適應度函數(shù)

不同的適應度函數(shù)決定著不同的種群求解方向,結(jié)合人工蜂群計算中的迭代過程采用一種適應度函數(shù),如式(3):

(3)位置更新公式

人工蜂群雖然有良好的全局探索性能, 但開發(fā)能力不足, 位置更新速度較慢.對于種群進化來說, 每個個體都應享有整個種群提供的信息.而人工蜂群算法在尋找蜜源過程中沒有考慮到迭代前后的位置比較,只能將當前位置信息與歷史最佳位置信息比較, 缺乏對全局最優(yōu)位置的考慮.針對這個缺點引入一種帶有調(diào)節(jié)因子的位置更新式(4), 該公式通過加入調(diào)節(jié)因子來不斷調(diào)節(jié)位置更新幅度.若當前所在位置與歷史最佳位置相差較大, 則會增加更新幅度, 反之則會降低更新幅度.

其中, vid代表在蜜源 xid附近產(chǎn)生一個新的蜜源; k,m ∈{1,2,···,NP}, k, m, i 是隨機產(chǎn)生的整數(shù)且三者互不相等; θ ∈rand[0,1]表 示調(diào)節(jié)因子; xbest,d代表歷史最優(yōu)位置; φ ∈rand[-1,1]表示蜜源擾動幅度.

2.4 離線過程中采用的計算概率

其中, fiti代表第i 個解的適應度值, Pi代表引領(lǐng)蜂被追隨的概率.

3 人工蜂群優(yōu)化的數(shù)據(jù)流聚類算法

3.1 在線算法

在線微聚類是建立在動態(tài)滑動窗口的基礎(chǔ)上, 利用Birch 算法中的CF 樹概念, 將數(shù)據(jù)樣本按照數(shù)據(jù)屬性特征逐步聚類成適當規(guī)模數(shù)量的微簇.

在線部分程序偽代碼如下:

輸入: 數(shù)據(jù)集樣本D, 時間調(diào)節(jié)因子 σ; 初始化窗口大小W; 初始化閾值半徑T, 微簇數(shù)量K; 調(diào)節(jié)窗口大小 Δw.輸出: 通過動態(tài)滑動窗口生成K 個微簇CF.初始化微簇數(shù)量K=0 For 數(shù)據(jù)集D 的每個Xi For 初始每個聚類特征CFk Dismin根(Xi據(jù),CF式k)(1)計算 Xi 與C Fk的距離, 并找出其最近的距離If( Dis min(Xi,CFk)＞T)If(num＞UB)then{根據(jù)式(2)將距離最近的兩個微簇合并; K←(K+1)}Else{以 Xi建立新的微簇, 并且更新微簇特征中的各項;K←(K+1)}Else{根據(jù)式(1)把 Xi 加入與他距離最小的微簇C F min中}If( δRT -ΔAT＞σ)then { RW ←(W-Δw)} /*調(diào)整窗口大小*/Else if( -σ ≤ΔAT-δRT≤σ)then { RW ←W}Else { RW ←(W+Δw)}End For End For

3.2 離線算法

(1)對微簇集初始化并進行K-means 計算得到聚類中心.(2)通過改進的蜂群算法對聚類中心進行迭代計算得到新的聚類中心并更新蜂群.(3)將K-means 算法與改進的蜂群算法交替計算, 在最大迭代次數(shù)內(nèi)求出最優(yōu)聚類結(jié)果.

離線部分程序偽代碼如下:

輸入: 種群規(guī)模CZ (引領(lǐng)蜂與跟隨蜂數(shù)量均為種群規(guī)模的1/2); 蜜蜂最大迭代次數(shù)maxCycle; 蜜源被開發(fā)最大限制次數(shù)Limit; 初始化迭代次數(shù)Cycle=0, 限制次數(shù)iter=0.輸出: CZ/2 個簇.初始化CF 得到 {Z1 ,Z2,···,ZCZ}個蜂群.DO K-means計算 fit( vid) /*根據(jù)式(3)計算CZ 個蜜蜂的適應度值*/While(Cycle＜=maxCycle) do{Initialize( vid ) /*按式(4)得到新位置 vid*/計算 Maxfit( vi) /*根據(jù)式(3)計算并找到新蜜源的最大適應度值*/Prob( vi) /*根據(jù)式(5)計算概率 Pi */While(i＜CZ/2) do{If( Pi ＞rand(0, 1))then { Initialize ( vid ) }/*跟隨蜂根據(jù)式(4)搜索新位置 vid*/計算 Maxfit( vi) /*根據(jù)式(3)計算并找到新蜜源的最大適應度值*/i←i+1}

If(iter＞Limit)then { Initialize ( vid ) }/*偵查蜂根據(jù)式(4)搜索新位置 vid*/Else {iter←(iter+1)}對鄰域搜索到的點進行一次K-means 聚類, 更新蜂群.Cycle←(Cycle+1)}Output 聚類中心

3.3 算法分析

在線部分: 將源源不斷到來的數(shù)據(jù)轉(zhuǎn)化為內(nèi)含有特征屬性的微簇, 通過一次處理但并不保留數(shù)據(jù)的方式, 極大地節(jié)省了存儲空間, 降低了空間復雜度.在線部分對于數(shù)據(jù)不需要過于細致的處理, 但對于微聚類效率要求更高.

離線部分: 將在線部分產(chǎn)生的微簇通過改進的蜂群算法進行處理得到CZ/2 個簇.該算法對于時間效率要求不高, 對聚類的質(zhì)量有較高的要求.

4 實驗分析

4.1 實驗數(shù)據(jù)與參數(shù)設(shè)置

為了驗證本文算法的有效性, 本文數(shù)據(jù)集將采用KDD-CUP-99 入侵檢測數(shù)據(jù)集來進行算法測試.該數(shù)據(jù)集是由模擬美空軍局域網(wǎng)歷經(jīng)兩個多月的時間所收集的網(wǎng)絡(luò)連接數(shù)據(jù)匯集而成, 在很多文獻中也都有所引用.據(jù)統(tǒng)計, KDD-CUP-99 測試數(shù)據(jù)集涵蓋4.94×105條連接記錄, 每一條連接記錄是由41 個特征屬性和一個決策類屬性構(gòu)成; 41 個特征屬性包括9 個離散型屬性、32 個連續(xù)型屬性[10].該數(shù)據(jù)集具有數(shù)量大、類別多的特點, 經(jīng)常被學術(shù)界運用于檢測數(shù)據(jù)流聚類算法性能和精度.在檢測數(shù)據(jù)流聚類的聚類效果時, 常將聚類純度作為衡量數(shù)據(jù)流聚類質(zhì)量的標準.為了便于數(shù)據(jù)檢測, 將數(shù)據(jù)按到達的時間點分割成4 個時間段, 在實際情況中每個時刻的瞬時速度有所不同, 因此采用4 個時間區(qū)間的平均速度v, 如表1 所示.

表1 各時間段數(shù)據(jù)流平均速度

通過選取中等規(guī)模的數(shù)據(jù)樣本來分析數(shù)據(jù), 設(shè)置參數(shù)如下: 微簇數(shù)量K=50; 初始化窗口大小W=500;Δw 為最新時刻W 的5%; 時間調(diào)節(jié)因子σ =10; 種群個數(shù)CZ=10; 蜂群探索迭代次數(shù)maxCycle=CN×D (D 為數(shù)據(jù)維數(shù)); 蜂群開發(fā)單位蜜源限制次數(shù)Limit=100.

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

在圖2 中, 取表1 不同時間區(qū)間內(nèi)的數(shù)據(jù)和數(shù)據(jù)速度來對本文算法與TEDA[11]算法做聚類純度對比.從圖2 中可以看出在取聚類大小K=100 時, 本文算法的聚類純度在除第二、四個時間區(qū)間內(nèi)優(yōu)勢不明顯,其余2 個時間區(qū)間內(nèi)都明顯高于TEDA 算法, 并且其聚類純度都高于89%.在這4 個時間單元內(nèi), 本文算法的聚類純度波動幅度與TEDA 算法相差無幾.這是因為本文算法不僅對蜂群初始化進行了改進, 克服了其隨機性; 而且在算法中加入了全局的調(diào)節(jié)因子使得使蜜蜂更快的向最優(yōu)位置移動, 提高了全局搜索能力, 進而提高了聚類質(zhì)量.在圖3 中, 取數(shù)據(jù)流速度為v=100, 數(shù)據(jù)量與時間是成正相關(guān), 隨著時間的累加, 數(shù)據(jù)量也不斷增加.聚類質(zhì)量雖有下降但也有不錯的聚類指標, 但是總體高于TEDA 算法.因為在處理規(guī)模較大的數(shù)據(jù)時, 初始化閾值T 會有更顯著的效果.

圖2 不同時間單元聚類純度比較

圖3 不同時間段聚類純度比較

在經(jīng)過圖1、圖2 的實現(xiàn)對比后, 為了更好的顯示出數(shù)據(jù)流的瞬時速度與平均速度對聚類純度的影響,如圖4 將第一時間段中前一半連續(xù)數(shù)據(jù)進行細化處理,選取100 為時間間隔點.數(shù)據(jù)顯示本文算法在各個時間單元內(nèi)的聚類純度均在98%, 整體高于TEDA 算法的聚類純度.實驗結(jié)果表明本文算法在聚類純度、性能和效率優(yōu)化等方面都有提高.

圖4 第一時間段內(nèi)聚類純度對比

為了進一步檢測本文算法的延展性, 本文根據(jù)KDD-CUP-99 真實數(shù)據(jù)集的連續(xù)特征屬性, 合成了人工數(shù)據(jù)集.該數(shù)據(jù)集規(guī)模分為100 K 與200 K 兩組, 分別包含不同的維數(shù).由圖5 可以看出, 不同維度數(shù)據(jù)和算法運行時間是呈線性函數(shù)關(guān)系的, 并且在兩組不同的數(shù)據(jù)規(guī)模中也均有不錯的線性變化.

圖5 不同維度數(shù)據(jù)運行時間對比

在圖6 中可以看出本文算法的運行時間和簇的個數(shù)是呈線性增長的, 并且在經(jīng)過多個維度的測試后表現(xiàn)的比較平穩(wěn), 說明簇數(shù)隨著數(shù)據(jù)量的增大并沒有較大的時間變化幅度.綜上所述, 本文算法在面對不同的數(shù)據(jù)以及簇數(shù)時表現(xiàn)出了較好的延展性和穩(wěn)定性.

5 結(jié)論

通過研讀文獻, 結(jié)合所學知識, 在動態(tài)滑動窗口模型上提出了人工蜂群優(yōu)化的數(shù)據(jù)流聚類算法.該算法通過利用動態(tài)滑動窗口、初始化閾值T 以及離線部分中改進的蜂群算法, 有效的改善了聚類質(zhì)量.最后通過實驗仿真的結(jié)果可以看出本文算法相比于TEDA 算法提高了聚類質(zhì)量, 并有較好的延展性和穩(wěn)定性.

圖6 運行時間隨簇個數(shù)的變化