楊濤 張紅梅 王家樂(lè) 周卓潔 杜宏

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

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

中圖分類號(hào)：TP274文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2019）08-00-03

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以下為具體的算法描述。

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

輸出：以金字塔時(shí)間框架方式存儲(chǔ)的微簇。

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

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

（3）讀取數(shù)據(jù)流S中當(dāng)前新到達(dá)的數(shù)據(jù)點(diǎn)Xi。

（4）按照公式

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

（5）按照公式

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

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

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

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

度，所以不需要?jiǎng)?chuàng)建一個(gè)只包含數(shù)據(jù)點(diǎn)Xi的新的微簇

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

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

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

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

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

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

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

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

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

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

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

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

以下為詳細(xì)算法步驟。

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

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

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

（2）從數(shù)據(jù)集D中抽取一個(gè)未處理過(guò)的點(diǎn)Xv。

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

（4）處理完D中所有對(duì)象。

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

3 實(shí)驗(yàn)結(jié)果與分析

通過(guò)F-Stream算法與經(jīng)典數(shù)據(jù)流聚類算法CluStream進(jìn)行對(duì)比，來(lái)驗(yàn)證F-Stream算法的性能。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

3.2 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

實(shí)驗(yàn)選取聚類時(shí)間效率、聚類質(zhì)量、敏感參數(shù)三個(gè)重要指標(biāo)作為對(duì)比的主要依據(jù)。通過(guò)聚類純度評(píng)價(jià)聚類質(zhì)量，利用圖標(biāo)直觀對(duì)比。

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

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

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

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

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

4 結(jié) 語(yǔ)

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

參 考 文 獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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