一種對滑動窗口數據流聚類算法的混合差分研究

高瑞華　申海燕

摘 要 傳統的滑動窗口數據流聚類算法在執行中存在聚類質量較差、效率較低的缺點，而基于混合差分進化的算法，將滑動窗口數據流聚類過程進行劃分，一類是在線的時序窗口數據流特征向量生成，另一類是離線的聚類優化。對于在線式滑動窗口，其數據表現為微簇聚合更新與維護，可以通過粒子群算法，以離線微簇數據進行適應度計算，并將種群劃分為優勢子種群和普通子種群，利用個體適應度值和平均適應度值來進行最優選擇，采用迭代法來對個體進行進化，輸出最優適應度值的聚類集合。

關鍵詞 滑動窗口 數據流 混合差分進化 聚類

數據聚類分析是數據挖掘中的重要課題，也是通過對數據進行層次化模型分析，對指數級數據增長下的傳統聚類算法的優化，以滿足數據流處理的實時要求。比較經典的算法有CluStream，將數據流看作時序讀取過程，在數據處理周期內完成聚類。數據流聚類算法是基于聚類半徑的增長，數據聚類精度的提升對內存消耗過大而采用的優化算法，其優勢在于構建數據流聚類在線、離線框架，滿足數據入點、流出點之間數據流處理需要，但由于數據快照窗口的失效數據為實時更新，導致計算機負載過大?；诨瑒哟翱诘臄祿骶垲愃惴?，能夠在占用窗口大小的次線性內存空間中，對數據記錄分部展開進行聚類分析.

一、數據流聚類算法基礎概念明確

對于混合差分進化下的滑動窗口數據流聚類算法的研究，主要通過在線過程的微簇生成和離線下的混合差分進化算法來實現。需要對相關概念進行界定。一是窗口快照。以某t時刻數據窗口跨度為P，在[t-p，p]時刻內的數據流為DBi為窗口B的一個快照，記作。對于時序滑動窗口，以快照窗口的數據流為順序構成時序數據流，記為SB，則某時序i的時序滑塊窗口數據為：，如果窗口數為n，則時間跨度。對于時序衰減權系數的設定，假設某時刻t的時序窗口衰減權因子為%^，則，時序衰減權系數W（t）記作：；其中，v為數據流速，為當前滑動窗口時間。對于數據流微簇的設定，將當前時序滑動窗口的微簇計作CF，則，對于數據集，（F，Q）表示為樣本屬性的一階、二階矩陣，流簇樣本總數為n，則數據流達到時間為RT1，失效時間為RT2，滑動窗口大小為RW，則：；對于樣本聚類權重系數的設定，當某時序數據流為SB，則待識別樣本Y，隸屬于類別的近鄰樣本總數為k，則當前樣本總數為m，第j個近鄰樣本進行聚類時，樣本聚類權重系數記作l（j），則：，其中%Z表示為冪指數。對于聚類類別的判定函數，假設某數據集樣本類別為，則待識別數據為Y，數據集近鄰中屬于類別的樣本為，近鄰樣本總數為N，隸屬于 的近鄰樣本數為，待識別數據Y的第j個近鄰樣本的類別判別函數表示為：。

二、混合差分滑動窗口數據流聚類算法

（1）算法思想。

從時序滑動窗口數據集的定義來看，，樣本類別數為c，類別標識符為，則當前數據流為DB；假設時序窗口快照的數據集為，則待識別樣本為，則滿足兩個過程：一是窗口快照中的數據為，則記作A[i]，其中包含（n+1）個數據元組；二是時序窗口更新所涉及的快照數據，其存儲和失效數據的刪除滿足；當快照數據流被處理完后將對A[n+1]元組進行刪除，令A[j]=A[j+1]，則快照窗口的數據存儲于A[j]?？梢姡瑢τ诨旌喜罘炙惴ㄏ碌幕瑒哟翱跀祿骶奂惴ǖ膽茫饕獜脑诰€和離線兩種過程中來完成。在不同數據流流速下，在線聚類是結合時序滑動窗口、快照窗口來對數據流的粒度和流速進行微簇特征向量存儲，而離線聚類是對微簇特征向量的數據流粒度進行優化聚類。

（2）在線聚類算法研究。

對于微簇特征向量的生成主要依據DBSCAN算法來實現微簇的集合，其方法如下：一是對微簇變量設置并初始化num=0；利用DBSCAN算法，假設對象p的簇半徑r

（3）離線下數據流聚類優化研究。

離線下的微簇數據集聚類優化，主要采用混合差分進化算法來提升可執行性。先以粒子群算法為例，就進化算法進行改進。粒子群算法是粒子在空間維度下以特定速度飛行，其位置是動態調整的。假設某粒子群規模為M，空間維度為D，則第i個粒子在第d維空間的位置集合表示為：；粒子速度集合為：；個體位置優化集合：；種群全局位置優化集合為：；則粒子i在第（t+1）時刻的速度及位置更新策略為：；對于表示為粒子的加速系數，對于表示為[0，1]區間內的隨機數。從粒子群算法中進行全局最優迭代計算時，因計算量較大，粒子變化趨勢變化趨緩，導致粒子活動降低，出現計算收斂難度；利用慣性系數來導入粒子群算法，從全局最優調節中來提升算法效率，其粒子速度更新機制為；利用最優算法，主要是滿足對粒子速度求解是否最優進行判定，當前適應度函數值與上一時刻進行比較，若趨于更優則對當前數值進行更新；利用粒子慣性函數進行賦值，若為線性遞減，則極限點未必是真正的動態極限點，從而對當前粒子速度帶來偏離影響，需要從粒子權值上進行改進。

（4）差分進化算法研究。

從粒子群算法來進行數據聚類應用，僅僅是從權系數上來調整，因本身算法的局限，無法避免適應度值的最終趨向一致的結果。盡管在種群活性上進行改進，但由于更新機制中受到個體學習認知能力制約，仍然存在局部極值點缺陷問題。為此，混合差分進化算法，將差分進化算法作為基礎，并從遺傳算法中借助于單純行算法進行差分變異算子，使其獲得更優的性能和穩定性。在探討混合差分進化算法之前，需要對差分進化算子進行說明，差分進化算子主要有變異、交叉和選擇，用DE/x/y/z來標記。對于式中的x表示為基向量類型；y表示為變異操作差分向量個數；z表示為交叉操作類型。在本文中對混合差分進化算法的運用，首先是利用粒子群算法來進行種群分析，依照不同個體的平均適應度值進行劃分，對于適應度低的子種群采用粒子群算法進行優化；對于適應度值高的個體采用差分進化算法，即：

（5）混合差分進化聚類算法優化。

從離線下聚類算法的優化主要采用混合差分進化算法，其實施步驟為：首先讀取內存中的微簇數據；然后對微簇mc半徑內的特征向量進行隨機初始化，并計算其位置和速度；再次對待識別的數據對象進行計算，包括微簇中粒子對應的聚類中心距離，計算粒子環境權系數，以進行粒子速度、粒距分類；然后對各粒距聚集度權重進行計算并更新；對各種群進行適應度值計算，依據；對于表示為第i個聚類中心，對于表示為聚類間距的調整權重；通過計算各平均適應度值，對種群進行分類，對于大于平均適應度值的個體采用差分進化算法優化；對于小于平均適應度值的個體，采用粒子群算法進行優化；最后根據個體適應度值的比較來進行個體極值、全局極值的更新，保存最新解，依次迭代進行聚類優化獲得最終聚類集合。

三、結語

通過對數據流聚類算法的研究，對于滑動窗口下數據信息進行混合差分進化算法優化，主要集中在離線階段，而對于在線階段，以數據流微簇特征向量和粒度信息微簇生成、更新和存儲即可。通過對滑動窗口模型的分段劃分，避免了數據流規模較大時帶來的執行效率問題；同時，利用混合差分進化算法，在一定程度上改進了算法能力，也對聚類算法提升了執行效率，減少了對內存的過度依賴，確保每次迭代算法中實現最優的搜索能力。

參考文獻：

[1]朱琳，劉曉東，朱參世.基于衰減滑動窗口數據流聚類算法研究[J]. 計算機工程與設計，2012（07）.

[2]劉燕馳，高學東，國宏偉，武森.應用分類方法進行聚類評價[J].計算機應用研究，2011（10） .

[3]吳學雁，黃道平.基于形態特征的數據流聚類方法研究[J].計算機工程， 2011（13）.

[4] Lisa M. Sweeney，Ann Parker，Lynne T. Haber，C. Lang Tran，Eileen D. Kuempel.Application of Markov chain Monte Carlo analysis to biomathematical modeling of respirable dust in US and UK coal miners[J]. Regulatory Toxicology and Pharmacology ， 2013 （1）.

[5]于彥偉，王沁，鄺俊，何杰.一種基于密度的空間數據流在線聚類算法[J].自動化學報，2012（06）.

（作者單位：河南財政稅務高等?？茖W校）