基于人工蜂群優化的數據流聚類算法①

賈東立, 申 飛, 崔新宇

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

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

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

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

1 相關概念

1.1 動態滑動窗口模型

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

圖1 滑動窗口模型

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

滑動窗口由靜態固定大小W 和動態可調節大小Δw兩 部分組成, 其中W 始終是固定不變的, Δ w是用來動態調節滑動窗口W 大小的.

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

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

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

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

1.2 微簇特征向量

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

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

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

1.3 微簇閾值半徑T

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

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

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

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

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

2 離線部分的數據流聚類優化

2.1 人工蜂群聚類優化算法思想

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

2.2 基本人工蜂群算法

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

2.3 改進的人工蜂群算法

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

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

(2)適應度函數

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

(3)位置更新公式

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

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

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

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

3 人工蜂群優化的數據流聚類算法

3.1 在線算法

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

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

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

3.2 離線算法

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

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

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

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

3.3 算法分析

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

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

4 實驗分析

4.1 實驗數據與參數設置

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

表1 各時間段數據流平均速度

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

4.2 實驗結果與分析

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

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

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

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

圖4 第一時間段內聚類純度對比

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

圖5 不同維度數據運行時間對比

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

5 結論

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

圖6 運行時間隨簇個數的變化