許穎梅

(商丘師范學(xué)院 計算機(jī)與信息技術(shù)學(xué)院， 河南 商丘 476000)

0 引 言

隨著通信業(yè)的大力發(fā)展，一種被稱之為數(shù)據(jù)流的數(shù)據(jù)應(yīng)運而生。數(shù)據(jù)流具有數(shù)據(jù)連續(xù)、實時到達(dá)、數(shù)據(jù)量大、無限制并且無法預(yù)知的特點[1]。而數(shù)據(jù)流聚類算法作為數(shù)據(jù)流挖掘的工具，具有很好的研究和應(yīng)用前景，也是目前應(yīng)用研究的熱點。聚類就是按一定特征將一個對象的集合分成若干個類。聚類分析指將物理或抽象對象的集合分組成為由類似的對象組成的多個類的分析過程，這些對象與同一簇中的對象彼此相似，與其他簇中的對象相異。

數(shù)據(jù)流聚類正在蓬勃發(fā)展，現(xiàn)在數(shù)據(jù)流聚類算法的研究已經(jīng)成為一個非?；钴S的研究課題，基于K-means(K-平均值)、K-medoids(K-中心點)和其他一些的聚類分析工具已經(jīng)被應(yīng)用到許多領(lǐng)域。Guha等人[2]提出了LOCALSEARCH算法，在有限的空間內(nèi)對數(shù)據(jù)流分門別類，使用一個不斷迭代的過程對不斷到來的流數(shù)據(jù)采取K-means聚類；Callaghan等人[3]在LOCALSEARCH算法的基礎(chǔ)上又提出了Stream算法，STREAM算法采用分級聚類的技術(shù)，對K-Means算法進(jìn)行改進(jìn)，得到較好的性能，但這種算法是基于靜態(tài)數(shù)據(jù)流而言的，不能及時反映數(shù)據(jù)流動態(tài)變化的情況；Aggarwal等人[4]在2003年提出了CLUStream算法，該算法提出一個通用的數(shù)據(jù)流聚類框架，它適應(yīng)范圍很廣，為后來的研究作出了杰出的貢獻(xiàn)，它有效地將數(shù)據(jù)流的聚類分成在線微聚類和離線宏聚類兩個階段；針對高維數(shù)據(jù)流和任意形狀分布的數(shù)據(jù)聚類問題，2006年周曉云等[5]又提出基于Hoeffding界的高維數(shù)據(jù)流的子空間聚類發(fā)現(xiàn)及維護(hù)算法SHStream，它通過迭代逐步得到滿足聚類精度要求的聚類結(jié)果。2007年，楊春宇等人[6]考慮到數(shù)據(jù)流的連續(xù)屬性和標(biāo)稱屬性提出了一種適用于處理混合屬性數(shù)據(jù)流的聚類算法——HCluStream，為混合屬性構(gòu)建新的信息匯總方式及距離度量。2009年，吳楓等人[7]在數(shù)據(jù)流聚類形狀問題上又提出了一種滑動窗口內(nèi)進(jìn)化數(shù)據(jù)流任意形狀聚類算法SWASCStream。

這些算法在一定程度上都較之前有了改進(jìn)，但都各有優(yōu)劣，本文就算法的可行性、效率和內(nèi)存使用情況進(jìn)行研究，提出一種基于滑動窗口的優(yōu)化數(shù)據(jù)分析算法。該算法的特點是：(1)提出一種新的內(nèi)存存儲結(jié)構(gòu)滑動窗口樹，它只需單遍訪問數(shù)據(jù)流，不但能及時更新數(shù)據(jù)流上的模式信息，還能夠周期性地對滑動窗口樹進(jìn)行修剪；(2)滑動窗口大小可以動態(tài)改變，根據(jù)支持度的不同，適當(dāng)調(diào)整窗口大小，解決有限內(nèi)存存儲無限數(shù)據(jù)的可能。

1 預(yù)備知識

1.1 相關(guān)概念

定義1 數(shù)據(jù)流DS={T1,T2,…,Ti,…}為一個不斷變化著的無限大小的數(shù)據(jù)序列，其中Ti為第i個產(chǎn)生的事務(wù)。在數(shù)據(jù)流中每個事務(wù)都有唯一的事務(wù)標(biāo)識tid，在數(shù)據(jù)集中每個事務(wù)中的數(shù)據(jù)元素集合都是數(shù)據(jù)集A={a1,a2,…,am}的一個子集。

定義3 動態(tài)滑動窗口，給定最小支持度閾值δ和誤差因子ε。假設(shè)|W|表示滑動窗口W的寬度，即W中包含的事務(wù)數(shù)。fw(A)表示模式A在滑動窗口中的支持度計數(shù)。對于模式A，如果有fw(A)≥δ|W|，則稱A為滑動窗口W中的微簇；如果有fw(A)≥ε|W|，則稱A為滑動窗口W中的臨界微簇；如果有fw(A)<ε|W|，則稱A為滑動窗口W中的過期微簇。

1.2 時間滑動窗口模型

結(jié)合數(shù)據(jù)流的特點，筆者在提高算法的可行性、效率和節(jié)約內(nèi)存的情況下，采用動態(tài)滑動窗口模型，見圖1。窗口大小會隨著流速的改變而改變，同時考慮到窗口的頻繁變化會影響算法的執(zhí)行效率，定義了時間界定閾值。對不斷到來多維數(shù)據(jù)流進(jìn)入滑動窗口可以這樣定義{Xi,tm,tn}，Xi為在tm時刻到來的樣本數(shù)據(jù)，tm為進(jìn)到滑動窗口的時間點，tn為從滑動窗口流出的時間點。隨著流入的速度不同，滑動窗口大小W可以隨之改變，定義一個時間界定閾值σ，從而靈活地確定滑動窗口的大小。

圖1 時間滑動窗口模型

1.3 滑動窗口樹

SWStream算法采用滑動窗口樹SW.tree的結(jié)構(gòu)來存儲潛在的微簇，一個SW.tree由事務(wù)頭表、根結(jié)點和前綴子樹構(gòu)成。事務(wù)頭表就是由當(dāng)前滑動窗口中的所有臨界微簇按照元組的支持度降序排序而成。事務(wù)頭表的每個表目由事務(wù)名name和結(jié)點鏈頭指針組成，其中結(jié)點鏈頭指針指向樹中具有相同事務(wù)名的第一個結(jié)點。前綴子樹中的每一個結(jié)點由以下幾個域構(gòu)成[8]：①事務(wù)名name；②事務(wù)標(biāo)識tid；③指向孩子結(jié)點的linktable；④指向父結(jié)點的point；⑤指向SW.tree中具有相同事務(wù)名的下一個結(jié)點的指針；⑥數(shù)值域(f,f1,f2,…,fi,…,fn)，fi表示第i個元組中構(gòu)成的各個模式的計數(shù)信息。

1.4 時間衰減機(jī)制

在數(shù)據(jù)流聚類過程中，有數(shù)據(jù)源源不斷地流入，也應(yīng)該有些過期的數(shù)據(jù)淘汰，這就要采用一定的衰減機(jī)制對過期元組進(jìn)行衰減。本文中采用時間衰減模型，在這種模型中，數(shù)據(jù)流中每一個項集都有一個權(quán)重。權(quán)重隨時間改變，新到來的項集對該項集的頻度影響大于原來的項集。在時刻t，每個元組的衰減因子的大小滿足：2-λt<ε(λ>0)，λ值越大，過去數(shù)據(jù)的重要性就會降低。

數(shù)據(jù)流總的權(quán)重：

其中tc表示當(dāng)前時間，v表示數(shù)據(jù)流的流速。

2 算 法

2.1 算法思想

本文緊緊圍繞動態(tài)數(shù)據(jù)流分析這一核心問題，依據(jù)CLUStream雙層聚類框架思想，將挖掘過程分為在線和離線兩個階段：在線階段不斷接收到來的數(shù)據(jù)流摘要信息，利用K-means算法從初始樣本集中挖掘出一定數(shù)量的微簇更新到滑動窗口樹分枝上，其產(chǎn)生的結(jié)果作為挖掘的中間結(jié)果維護(hù)起來。過一定的時間段將這些中間結(jié)果保存到外存中作為離線過程的初始數(shù)據(jù)。離線過程由用戶調(diào)用，針對用戶的查詢得到最終的聚類結(jié)果。通過在線和離線兩個階段不同算法的處理以解決動態(tài)數(shù)據(jù)的快速處理。

2.2 在線層算法

算法SWStream采用了滑動窗口模型對流數(shù)據(jù)進(jìn)行處理，存儲結(jié)構(gòu)使用滑動窗口樹存儲最近到來的模式信息，同時對節(jié)點信息增量更新，根據(jù)時間衰減機(jī)制對過期信息進(jìn)行裁剪，從而減少了內(nèi)存開銷。

算法1 SW.tree的生成和維護(hù)。

該算法生成和維護(hù)一個用于存儲滑動窗口中所有潛在的微簇的SW.tree結(jié)構(gòu)。該算法在第一個元組進(jìn)入滑動窗口后生成一個SW.tree，并在以后每個新元組進(jìn)入滑動窗口后更新該SW.tree，過程分三步：一是根據(jù)更新的f.list對SW.tree進(jìn)行重構(gòu)；二是以ε為最小支持度閾值，調(diào)用傳統(tǒng)的聚類算法對臨界微簇進(jìn)行聚類；三是將這些模式插入到SW.tree中。

SW.tree的生成和維護(hù)算法如下：

Input：newDS，進(jìn)人滑動窗口之前的SW.tree(初始狀態(tài)SW.tree為空)，事務(wù)集排序表f.list，誤差因子ε，滑動窗口W中包含的基本元組數(shù)n；

Output：new SW.tree

(1)構(gòu)造滑動窗口樹(SW.tree，f.list,n)；

(2)以ε為最小支持度閾值，用傳統(tǒng)的聚類算法如K-means對新窗口中的臨界微簇進(jìn)行聚類；

(3)將新的臨界微簇插入到SW.tree中。

算法2 動態(tài)滑動窗口數(shù)據(jù)流在線聚類算法SWStream。

描述如下：

Input：數(shù)據(jù)流DS，窗口大小W,SW.tree；

Output：通過動態(tài)窗口生成的微聚類CF。

Begin

(1)建立微聚類輸出表fo.list;

(2)逆序取SW.tree中項目頭表中的元素ei，得到SW.tree中以ei為葉結(jié)點的分枝；

for each selected itemei。

(3){沿結(jié)點鏈查找各個以ei為葉結(jié)點的分枝，for each取到的分枝；

(4){將由根結(jié)點到葉結(jié)點ei的路徑構(gòu)成所有項目模式及各個子模式插入到fo.list中，各個插入模式的f值等于ei.f；若插入模式已存在于fo.list中，則fo.list中該模式的f值加上ei.f；}

(5)將葉結(jié)點ei從SW.tree中刪除；}

(6)處理完所有元組，刪除SW.tree；

(7)將fo.list按f值降序排序。

(8)輸出所有在fo.list中f值大于δ|W|的模式。

End

2.3 離線層算法

離線層通常分析某時間段的聚類情況，針對用戶的查詢以在線聚類階段形成的微聚類為基礎(chǔ)進(jìn)行離線聚類，利用衰減因子對微聚類進(jìn)行動態(tài)維護(hù)，及時更新和衰減，得到相應(yīng)時間段內(nèi)的宏聚類。

算法實現(xiàn)如下：

input：時刻t1和t2，時間界定閾值ε。

output：t1到t2之間的聚類結(jié)果。

Begin

(1)ift1和t2是兩個合法的時間點；

(2)將t1時刻的概要信息聚類得到的微簇作為中心微簇，并賦予類標(biāo)號；

(3){while在內(nèi)存中存儲的每一個微聚類特征CF；

(5)endw；

(6)采用K-means算法對內(nèi)存中的微聚類特征進(jìn)行聚類，生成k個聚類；

(7)}

End

3 實驗分析

本實驗是在配置為Intel PentiumIV 3.0 GHz、內(nèi)存1 GB的PC機(jī)上實現(xiàn)的，操作系統(tǒng)是Windows XP。所有程序采用Visual C++開發(fā)環(huán)境實現(xiàn)，并與基于界標(biāo)窗口模型的CluStream算法進(jìn)行性能比較。

實驗中所使用的數(shù)據(jù)是網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集KDDCUP99與IBM合成數(shù)據(jù)發(fā)生器產(chǎn)生的數(shù)據(jù)集T1516D1000K。KDDCUP99數(shù)據(jù)集共包含283 490條數(shù)據(jù)記錄，每條數(shù)據(jù)記錄共有41維固定特征屬性，對其中22個連續(xù)型，9個離散型共31個屬性進(jìn)行分析。數(shù)據(jù)集T1516D1000K共包含305 732條數(shù)據(jù)記錄，每條記錄包含50維屬性，其中，數(shù)值屬性44維，分類屬性6維[9]。

首先比較了在相同最小支持度閾值下兩算法對1000K個事務(wù)的平均處理時間，取最小支持度閾值ε=0.5%，圖2給出了SWStream算法與CluStream算法隨事務(wù)到達(dá)的平均處理時間對比。從實驗分析，SWStream算法時間效率明顯高于CluStream算法。

接下來對內(nèi)存使用情況進(jìn)行比較。依然選取兩個數(shù)據(jù)集產(chǎn)生的1000K個事務(wù)，圖3是處理KDDCUP99和T1516D1000K數(shù)據(jù)集的實驗比對結(jié)果。

圖2 相同事務(wù)數(shù)的平均處理時間比較 圖3 內(nèi)存使用情況比較

結(jié)果顯示，隨著數(shù)據(jù)流量的增多，SWStream的內(nèi)存節(jié)省率高于CluStream。說明有效的衰減機(jī)制能夠明顯地節(jié)約內(nèi)存開銷。

4 結(jié) 論

在當(dāng)前網(wǎng)絡(luò)和數(shù)據(jù)庫飛速發(fā)展的大環(huán)境下，數(shù)據(jù)流處理中的聚類分析要求也越來越多。CluStream算法給研究人員提供了在線和離線處理數(shù)據(jù)的框架，是數(shù)據(jù)流聚類方法中常用的一種，但當(dāng)數(shù)據(jù)規(guī)模很大時，它不能有效地解決有限內(nèi)存存儲無限數(shù)據(jù)的可能?；诖?，本文提出了改進(jìn)算法SWStream，它是一種基于滑動窗口的流數(shù)據(jù)聚類算法，采用滑動窗口樹作為概要數(shù)據(jù)結(jié)構(gòu)，采用時間衰減策略有效地對過期微簇進(jìn)行刪除，節(jié)約了存儲空間，提高了處理效率。實驗表明，本文提出的基于滑動窗口的對動態(tài)數(shù)據(jù)流的處理算法，在準(zhǔn)確度和運行效率上都有所提高。

[參考文獻(xiàn)]

[1] 金澈清,錢衛(wèi)寧,周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報,2004,15(8):1172-1181.

[2] GUHA S,MISHRA N,MOTWANI R,et al.Clustering data streams[C]//41stAnnual Symposium on Foundations of Computer Science.Los Alamitos:IEEE Computer Society Press,2000:359-366.

[3] O’CALLAGHAN L,MISHRA N,MEYERSON A,et al.Streaming data algorithms for high-quality clustering[C]//18th Int’l Conf.Data Engineering. Los Alamitos,CA:IEEE Computer Society Press,2002:685-704.

[4] AGGARWAL C C,HAN Jia-wei,WANG Jian-yong,et al.A framework for clustering evolving data streams[C]//Proeedings of the 29th International Conference on Very Large Data Bases.Berlin Germany,2003:81-92.

[5] 周曉云,孫志揮,張柏禮,等.高維數(shù)據(jù)流子空間聚類發(fā)現(xiàn)及維護(hù)算法[J].計算機(jī)研究與發(fā)展,2006,43(5):834-840.

[6] 楊春宇,周杰.一種混合屬性數(shù)據(jù)流聚類算法[J].計算機(jī)學(xué)報,2007,30(8):1364-1371.

[7] 吳楓,仲妍,金鑫,等.滑動窗口內(nèi)進(jìn)化數(shù)據(jù)流任意形狀聚類算法[J].小型微型計算機(jī)系統(tǒng),2009,30(5):887-890.

[8] 孫煥浪,趙法信,鮑玉斌,等.CD-Stream——一種基于空間劃分的流數(shù)據(jù)密度聚類算法[J].計算機(jī)研究與發(fā)展,2004,41(S):289-294.

[9] AGGARWAL C C,HAN Jia-wei,WANG Jian-yong,et al.A framework for projected clustering of high dimensional data streams[C]//Proceedings of the 30th International Conference on Very Large Data Bases.Toronto,Canada,2004:852-863.

[10] 張忠平,王浩,薛偉,等.動態(tài)滑動窗口的數(shù)據(jù)流聚類方法[J]計算機(jī)工程與應(yīng)用,2011(7):135-138.

[11] 李子文,邢長征.滑動窗口內(nèi)基于密度網(wǎng)格的數(shù)據(jù)流聚類算法[J].計算機(jī)應(yīng)用,2010(4):1093-1095.

[12] 林國平,陳磊松.一種網(wǎng)格和分形維數(shù)的數(shù)據(jù)流聚類算法[J].鄭州大學(xué)學(xué)報:理學(xué)版,2009,41(2):24-28.