楊濤 張紅梅 王家樂 周卓潔 杜宏

摘 要：隨著IT技術(shù)的不斷提升和完善，不管是在PC端，還是在移動端，人們借助互聯(lián)網(wǎng)工具來實現(xiàn)的各種服務(wù)，都以數(shù)據(jù)的形式被記錄下來，而這些數(shù)據(jù)不僅體量龐大、變化迅速，而且還呈現(xiàn)出一定的時序性。傳統(tǒng)的數(shù)據(jù)分析已經(jīng)不能適應(yīng)如今龐大的數(shù)據(jù)流，同時不同的算法，最終所得到的處理結(jié)果也是不一樣的，此時利用數(shù)據(jù)流相關(guān)的技術(shù)得到了重視和大規(guī)模的開發(fā)應(yīng)用。鑒于此，文中通過明確數(shù)據(jù)流的概念和特點，并列舉了常用的數(shù)據(jù)流聚類算法。充分考慮時間權(quán)值對數(shù)據(jù)流聚類的影響，在微簇中心點引入了時間衰減函數(shù)，提出F-Stream算法，分別對在線微聚類算法、離線宏聚類算法和數(shù)據(jù)流全局化緩存結(jié)構(gòu)進行了優(yōu)化設(shè)計。通過和CluStream算法進行時間效率、聚類質(zhì)量和敏感參數(shù)的對比實驗，發(fā)現(xiàn)F-Stream算法的整體性能更優(yōu)，具有很好的聚類效果。

關(guān)鍵詞：大數(shù)據(jù);數(shù)據(jù)流;聚類;挖掘算法;時間衰減;F-Stream算法

中圖分類號：TP274文獻標識碼：A文章編號：2095-1302（2019）08-00-03

0 引 言

不論是在地質(zhì)測量、氣象、天文觀測等方面，還是在互聯(lián)網(wǎng)數(shù)據(jù)監(jiān)控、無線網(wǎng)絡(luò)信息傳輸?shù)阮I(lǐng)域，數(shù)據(jù)流都發(fā)揮著越來越大的作用。由于數(shù)據(jù)流在時間上的積累，無法實現(xiàn)對海量數(shù)據(jù)進行隨機訪問，因此需要利用算法對數(shù)據(jù)進行“一次性掃描”。流數(shù)據(jù)聚類算法對新收到數(shù)據(jù)進行掃描，經(jīng)過具體處理后，根據(jù)數(shù)據(jù)價值或人為設(shè)定對數(shù)據(jù)進行儲存或者銷毀。

特殊的數(shù)據(jù)處理方式使得流數(shù)據(jù)挖掘的研究及其應(yīng)用越來越被關(guān)注，尤其是面向數(shù)據(jù)流的聚類分析、分類技術(shù)和頻繁項集挖掘技術(shù)都具有非常重要的意義。

1 數(shù)據(jù)流概述

1.1 數(shù)據(jù)流的定義及其特點

數(shù)據(jù)流是一種具有順序的數(shù)據(jù)序列，具有明確的起始與終止字節(jié)。在傳輸過程中保持實時高速地持續(xù)傳輸，其規(guī)模一般無法預(yù)知。當任意數(shù)據(jù)X1，X2，…，Xn，在時間序列T1，T2，…，Tn上依次到達，數(shù)據(jù)則視為具有時間屬性的集合。實際處理過程中，通過對數(shù)據(jù)的時間屬性進行限制，在特定的時間段對數(shù)據(jù)進行挖掘，也被稱為在時間窗口內(nèi)進行數(shù)據(jù)挖掘。常見的時間窗口分為：衰減窗口模型、滑動窗口模型、有界窗口模型等。實際中不同的模型對于數(shù)據(jù)挖掘結(jié)果有著重要的意義。

數(shù)據(jù)流中的數(shù)據(jù)和傳統(tǒng)的存儲在數(shù)據(jù)庫中的數(shù)據(jù)有許多不同點：

（1）時序性。數(shù)據(jù)流中的數(shù)據(jù)是實時達到的，而且這些數(shù)據(jù)都是高速生成的，數(shù)據(jù)變化非常快。

（2）不可再現(xiàn)性。數(shù)據(jù)流中的數(shù)據(jù)變化非?？欤瑫r這些數(shù)據(jù)又是高速實時到達的。

（3）無限性。在數(shù)據(jù)流中，陸續(xù)有新數(shù)據(jù)加入數(shù)據(jù)流中，理論上來說數(shù)據(jù)流的數(shù)據(jù)量是無限的。

1.2 數(shù)據(jù)流聚類算法

數(shù)據(jù)流挖掘是研究在數(shù)據(jù)流環(huán)境下對流數(shù)據(jù)進行數(shù)據(jù)挖掘。不同于對傳統(tǒng)數(shù)據(jù)進行挖掘，數(shù)據(jù)流中的數(shù)據(jù)是隨時間依次到達的而且是潛在無限的，因此不能被完整地保存下

來[1-2]。基于數(shù)據(jù)流挖掘的特點，要求面向流數(shù)據(jù)的挖掘算法只能一次或者有限幾次訪問數(shù)據(jù)，傳統(tǒng)挖掘算法直接應(yīng)用到流數(shù)據(jù)的挖掘效果會很差。

2 數(shù)據(jù)流聚類挖掘算法優(yōu)化

本文提出的F-Stream算法是針對實際應(yīng)用中人們對離當前時間最近一段時間內(nèi)新到達的數(shù)據(jù)更加有研究興趣的事實，對數(shù)據(jù)流中數(shù)據(jù)到達后形成的微簇賦予權(quán)值，充分考慮了時間權(quán)值對數(shù)據(jù)流聚類的影響，該算法主要包括兩個階段，即在線微聚類階段和離線宏聚類階段。

2.1 在線微聚類算法優(yōu)化

在線微聚類算法對數(shù)據(jù)流進行聚類生成用于離線宏聚類的微簇，先給出微簇緩沖區(qū)內(nèi)可以存放的最大微簇數(shù)N和初始微簇數(shù)量q（q≤N），即最多可以保留N個微簇在微簇緩沖區(qū)內(nèi)。

以下為具體的算法描述。

輸入：微簇緩沖區(qū)內(nèi)可以存放的最大微簇數(shù)N，初始微簇數(shù)量q，具有時標T1，T2，…，Tn，…的數(shù)據(jù)流S=（X1，X2，…，Xn，…）;

輸出：以金字塔時間框架方式存儲的微簇。

（1）初始化微簇緩沖區(qū)為空。

（2）獲取數(shù)據(jù)流S中第一批數(shù)據(jù)，然后利用K-means聚類算法對這些數(shù)據(jù)聚類成q個微簇（初始微簇數(shù)量q小于等于N），初始化這q個聚類微簇，并創(chuàng)建它們的微簇聚類特征MCF。

（3）讀取數(shù)據(jù)流S中當前新到達的數(shù)據(jù)點Xi。

（4）按照公式

計算數(shù)據(jù)點Xi與微簇緩沖區(qū)中的每個聚類微簇的相似度，并將最大相似度記為S（Xi- ）。

（5）按照公式

計算微簇緩沖區(qū)中的聚類微簇與聚類微簇之間的相似度，并將最大相似度記為S（，）;

（6）如果S（Xi-）≥S（，），那么把數(shù)據(jù)點Xi加入到微簇Ci中，同時更新MCFi，否則轉(zhuǎn)向步驟（7）。

//S（Xi-）≥S（，）表示數(shù)據(jù)點Xi與微簇Ci的

相似度大于微簇緩沖區(qū)內(nèi)任意兩個微簇之間的相似

度，所以不需要創(chuàng)建一個只包含數(shù)據(jù)點Xi的新的微簇

（7）如果微簇緩沖區(qū)已滿，那么合并兩個相似度最大的聚類微簇和同時更新微簇聚類特征MCF，并在微簇緩沖區(qū)中創(chuàng)建一個只包含數(shù)據(jù)點Xi的新的微簇，為其創(chuàng)建微簇聚類特征MCF;否則直接在微簇緩沖區(qū)中為數(shù)據(jù)點Xi單獨創(chuàng)建一個新的微簇并為其創(chuàng)建微簇聚類特征MCFi。

（8）如果出現(xiàn)離線聚類請求，那么結(jié)束算法進入離線宏聚類階段;否則轉(zhuǎn)向步驟（3）。在線微聚類算法是數(shù)據(jù)流聚類算法的基礎(chǔ)，在整個數(shù)據(jù)流聚類階段中起著關(guān)鍵性作用。

2.2 離線宏聚類算法優(yōu)化

在離線宏聚類算法中，把在線微聚類階段產(chǎn)生的每個微簇Ci（i=1，2，…，N）看作一個數(shù)據(jù)點Pi，并且這個數(shù)據(jù)點具有時間權(quán)值wi，其中數(shù)據(jù)點的時間權(quán)值wi與對應(yīng)微簇Ci的微簇中心點權(quán)值相等，然后利用相對密度的聚類算法進行聚類。

在介紹算法前，先假設(shè)D=（P1，P2，…，PN），數(shù)據(jù)點X，Y是集合D內(nèi)的元素，wx和wy是數(shù)據(jù)點X與Y的時間權(quán)值，xi和yi是數(shù)據(jù)點X，Y的第i維屬性值（i=1，2，…，d），并給出如下定義：

（1）數(shù)據(jù)點X與Y的相異度計算公式為：

（2）數(shù)據(jù)點X的k近鄰集合Nk（X）={X1，X2，…，Xd}，即X到D-{X}中每一點Xi的相異度d（Xi，X）按非遞減方式排序得到集合。

（3）數(shù)據(jù)點X的k近鄰密度計算公式為：

（4）數(shù)據(jù)點X關(guān)于其k近鄰集合Nk（X）的相對密度，簡稱為X的k近鄰相對密度，其計算公式為：

（5）核心對象。假設(shè)閾值ε（0<ε<1），X∈D，如果|rdk（X）-1|<ε，那么稱數(shù)據(jù)點X是核心對象。

（6）直接密度可達。如果X，Y∈D，X是核心對象，同時Y∈Nk（X），那么有對象Y關(guān)于核心對象X是直接密度可達的。

（7）密度可達。給定集合D，閾值ε（0<ε<1），當存在一個對象鏈X1，X2，…，Xn，X=X1，Y=Xn，對于任意一個Xi（i=1，2，…，n-1），如果存在Xi～Xi+1直接密度可達的，那么稱X關(guān)于Y是密度可達的。

以下為詳細算法步驟。

輸入：數(shù)據(jù)集D、近鄰個數(shù)k和閾值ε（0<ε<1）;

輸出：主要是基于相對密度的聚類C={C1，C2，…，Cr}。

（1）初始化聚類C為空。

（2）從數(shù)據(jù)集D中抽取一個未處理過的點Xv。

（3）如果Xv是核心對象，且Xv不在聚類C的任何簇中，那么將Xv初始化成簇Cv，并將從Xv出發(fā)密度可達的所有對象歸入簇Cv中;否則，跳轉(zhuǎn)至步驟（2）。

（4）處理完D中所有對象。

（5）輸出聚類C={C1，C2，…，Cr}。

3 實驗結(jié)果與分析

通過F-Stream算法與經(jīng)典數(shù)據(jù)流聚類算法CluStream進行對比，來驗證F-Stream算法的性能。

3.1 實驗數(shù)據(jù)集

在算法評價過程中，采用來自美國空軍和與美國植被覆蓋率有關(guān)的KDD-CUP99網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集（數(shù)據(jù)集1）和Forest Cover Type森林覆蓋數(shù)據(jù)集（數(shù)據(jù)集2）。

其中，數(shù)據(jù)集1由500萬條左右的TCP連接記錄組成，是一個模擬美國空軍局域網(wǎng)采集的數(shù)據(jù)，時間窗口為9周，數(shù)據(jù)具有4個標志類型，9個特征。從數(shù)據(jù)集中選擇10%作為聚類測試樣本數(shù)據(jù)。

數(shù)據(jù)集2由58.1萬條記錄組成，由關(guān)于植被覆蓋的真實數(shù)據(jù)組成，內(nèi)涵關(guān)于土地的54個特征，其中的數(shù)據(jù)分為7種，雖然不是真正的大數(shù)據(jù)，但在實際使用中效果很好。測試中將數(shù)據(jù)集順序輸入，不改變其儲存順序。

3.2 實驗數(shù)據(jù)對比

實驗選取聚類時間效率、聚類質(zhì)量、敏感參數(shù)三個重要指標作為對比的主要依據(jù)。通過聚類純度評價聚類質(zhì)量，利用圖標直觀對比。

式中：K表示簇的數(shù)量;|Cid|是在簇Ci中類標簽占支配地位的數(shù)據(jù)點的個數(shù);Ci表示簇Ci中數(shù)據(jù)點的總個數(shù)。純度越大表明簇內(nèi)的點越相似，聚類的結(jié)果也就越好。

采取聚類純度和聚類時間速率作為對比的主要依據(jù)，分別對兩個數(shù)據(jù)集利用兩種算法進行處理。

在數(shù)據(jù)集1和數(shù)據(jù)集2上進行CluStream算法和F-Stream算法，在聚類純度和聚類時間兩個關(guān)鍵方面進行比較。

圖1和圖2是采用算法CluStream和F-Stream在2個數(shù)據(jù)集上所得聚類純度，橫軸表示數(shù)據(jù)流中的數(shù)據(jù)量，縱軸表示聚類純度。從圖中可以發(fā)現(xiàn)F-Stream算法比CluStream算法具有較高的聚類準確性。圖3和圖4體現(xiàn)了算法CluStream和F-Stream在2個數(shù)據(jù)集上的聚類時間方面的實際情況，縱軸表示算法處理數(shù)據(jù)流所消耗的時間，處理時間越短，代表聚類算法的時間效率越高、聚類速率越快。從圖中可以看出F-Stream算法比CluStream算法具有更好的聚類時間效率。

本節(jié)主要介紹一種基于時間衰減的數(shù)據(jù)流聚類算法，該算法引入了時間衰減函數(shù)，降低了數(shù)據(jù)流中過往數(shù)據(jù)對聚類的影響，并且其影響因子隨著時間推移持續(xù)降低。

4 結(jié) 語

本文提出一種影響因子隨時間降低的數(shù)據(jù)流聚類算法F-Stream。該算法針對傳統(tǒng)的聚類算法并沒有充分考慮時間權(quán)值對聚類的影響，但是實際應(yīng)用中人們對離當前時間最近一段時間內(nèi)新到達的數(shù)據(jù)更加有研究興趣，在算法中引入了時間衰減函數(shù)使數(shù)據(jù)流中時間較久遠的處理結(jié)果對數(shù)據(jù)流聚類的影響程度得到削弱。但是，還有很多的不足之處，仍然有一些問題需要做進一步的研究：F-Stream算法需要通過人工調(diào)整參數(shù)來對數(shù)據(jù)流實現(xiàn)良好的聚類效果;離線宏聚類階段采用相對密度的方法來聚類，使得算法的時間復(fù)雜度較高，所以還需要改進。

參 考 文 獻

[1]杜航原，王文劍，白亮.一種基于優(yōu)化模型的演化數(shù)據(jù)流聚類方法[J].中國科學(xué)：信息科學(xué)，2017，47（11）：1464-1482.

[2]莫徽忠.基于數(shù)據(jù)流聚類算法的網(wǎng)絡(luò)異常檢測系統(tǒng)設(shè)計[J].柳州職業(yè)技術(shù)學(xué)院學(xué)報，2017，17（3）：99-103.

[3]李芬田.基于滑動窗口的數(shù)據(jù)流頻繁項集挖掘算法研究[D].長春：長春工業(yè)大學(xué)，2018.

[4]石秀金，蔡藝松.一種基于滑動窗口模型的數(shù)據(jù)流加權(quán)頻繁模式挖掘方法[J].智能計算機與應(yīng)用，2018，8（2）：63-67.

[5]郭世明，高宏.基于滑動窗口挖掘數(shù)據(jù)流高效用項集的有效算法[J].哈爾濱工程大學(xué)學(xué)報，2018，39（4）：721-729.

[6]樊超，李宏偉.利用優(yōu)化的DenStream算法進行空間數(shù)據(jù)流聚類

[J].測繪與空間地理信息，2017，40（4）：73-77.

[7]傅坦坦.數(shù)據(jù)流處理系統(tǒng)中優(yōu)化調(diào)度算法研究與實現(xiàn)[D].成都：電子科技大學(xué)，2017.

[8]孫宏.基于數(shù)據(jù)流的模糊聚類算法分析與優(yōu)化[D].鎮(zhèn)江：江蘇科技大學(xué)，2017.

[9]周虹，富春巖，支援，等.基于硬件預(yù)處理的數(shù)據(jù)流并發(fā)連接查詢優(yōu)化算法[J].電腦知識與技術(shù)，2016，12（33）：25-26.

[10]馬可.基于Storm的流數(shù)據(jù)聚類挖掘算法的研究[D].南京：南京郵電大學(xué)，2016.

[11]李彥.數(shù)據(jù)流程序優(yōu)化與可視化編程環(huán)境研究[D].武漢：華中科技大學(xué)，2015.