一種對(duì)滑動(dòng)窗口數(shù)據(jù)流聚類算法的混合差分研究

高瑞華　申海燕

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

關(guān)鍵詞 滑動(dòng)窗口 數(shù)據(jù)流 混合差分進(jìn)化 聚類

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

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

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

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

（1）算法思想。

從時(shí)序滑動(dòng)窗口數(shù)據(jù)集的定義來(lái)看，，樣本類別數(shù)為c，類別標(biāo)識(shí)符為，則當(dāng)前數(shù)據(jù)流為DB；假設(shè)時(shí)序窗口快照的數(shù)據(jù)集為，則待識(shí)別樣本為，則滿足兩個(gè)過(guò)程：一是窗口快照中的數(shù)據(jù)為，則記作A[i]，其中包含（n+1）個(gè)數(shù)據(jù)元組；二是時(shí)序窗口更新所涉及的快照數(shù)據(jù)，其存儲(chǔ)和失效數(shù)據(jù)的刪除滿足；當(dāng)快照數(shù)據(jù)流被處理完后將對(duì)A[n+1]元組進(jìn)行刪除，令A(yù)[j]=A[j+1]，則快照窗口的數(shù)據(jù)存儲(chǔ)于A[j]。可見，對(duì)于混合差分算法下的滑動(dòng)窗口數(shù)據(jù)流聚集算法的應(yīng)用，主要從在線和離線兩種過(guò)程中來(lái)完成。在不同數(shù)據(jù)流流速下，在線聚類是結(jié)合時(shí)序滑動(dòng)窗口、快照窗口來(lái)對(duì)數(shù)據(jù)流的粒度和流速進(jìn)行微簇特征向量存儲(chǔ)，而離線聚類是對(duì)微簇特征向量的數(shù)據(jù)流粒度進(jìn)行優(yōu)化聚類。

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

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

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

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

（4）差分進(jìn)化算法研究。

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

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

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

三、結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2]劉燕馳，高學(xué)東，國(guó)宏偉，武森.應(yīng)用分類方法進(jìn)行聚類評(píng)價(jià)[J].計(jì)算機(jī)應(yīng)用研究，2011（10） .

[3]吳學(xué)雁，黃道平.基于形態(tài)特征的數(shù)據(jù)流聚類方法研究[J].計(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].自動(dòng)化學(xué)報(bào)，2012（06）.

（作者單位：河南財(cái)政稅務(wù)高等專科學(xué)校）