高瑞華　申海燕

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

關鍵詞 滑動窗口 數(shù)據(jù)流 混合差分進化 聚類

數(shù)據(jù)聚類分析是數(shù)據(jù)挖掘中的重要課題，也是通過對數(shù)據(jù)進行層次化模型分析，對指數(shù)級數(shù)據(jù)增長下的傳統(tǒng)聚類算法的優(yōu)化，以滿足數(shù)據(jù)流處理的實時要求。比較經(jīng)典的算法有CluStream，將數(shù)據(jù)流看作時序讀取過程，在數(shù)據(jù)處理周期內(nèi)完成聚類。數(shù)據(jù)流聚類算法是基于聚類半徑的增長，數(shù)據(jù)聚類精度的提升對內(nèi)存消耗過大而采用的優(yōu)化算法，其優(yōu)勢在于構(gòu)建數(shù)據(jù)流聚類在線、離線框架，滿足數(shù)據(jù)入點、流出點之間數(shù)據(jù)流處理需要，但由于數(shù)據(jù)快照窗口的失效數(shù)據(jù)為實時更新，導致計算機負載過大。基于滑動窗口的數(shù)據(jù)流聚類算法，能夠在占用窗口大小的次線性內(nèi)存空間中，對數(shù)據(jù)記錄分部展開進行聚類分析.

一、數(shù)據(jù)流聚類算法基礎概念明確

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

二、混合差分滑動窗口數(shù)據(jù)流聚類算法

（1）算法思想。

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

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

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

（3）離線下數(shù)據(jù)流聚類優(yōu)化研究。

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

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

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

（5）混合差分進化聚類算法優(yōu)化。

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

三、結(jié)語

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

參考文獻：

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

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

[3]吳學雁，黃道平.基于形態(tài)特征的數(shù)據(jù)流聚類方法研究[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]于彥偉，王沁，鄺俊，何杰.一種基于密度的空間數(shù)據(jù)流在線聚類算法[J].自動化學報，2012（06）.

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