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

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

數據聚類分析是數據挖掘中的重要課題，也是通過對數據進行層次化模型分析，對指數級數據增長下的傳統聚類算法的優化，以滿足數據流處理的實時要求。比較經典的算法有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表