大數據下數據流聚類挖掘算法的優化分析

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

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

關鍵詞：大數據;數據流;聚類;挖掘算法;時間衰減;F-Stream算法

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

0 引 言

不論是在地質測量、氣象、天文觀測等方面，還是在互聯網數據監控、無線網絡信息傳輸等領域，數據流都發揮著越來越大的作用。由于數據流在時間上的積累，無法實現對海量數據進行隨機訪問，因此需要利用算法對數據進行“一次性掃描”。流數據聚類算法對新收到數據進行掃描，經過具體處理后，根據數據價值或人為設定對數據進行儲存或者銷毀。

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

1 數據流概述

1.1 數據流的定義及其特點

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

數據流中的數據和傳統的存儲在數據庫中的數據有許多不同點：

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

（2）不可再現性。數據流中的數據變化非常快，同時這些數據又是高速實時到達的。

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

1.2 數據流聚類算法

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

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

2 數據流聚類挖掘算法優化

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

2.1 在線微聚類算法優化

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

以下為具體的算法描述。

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

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

（1）初始化微簇緩沖區為空。

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

（3）讀取數據流S中當前新到達的數據點Xi。

（4）按照公式

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

（5）按照公式

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

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

//S（Xi-）≥S（，）表示數據點Xi與微簇Ci的

相似度大于微簇緩沖區內任意兩個微簇之間的相似

度，所以不需要創建一個只包含數據點Xi的新的微簇

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

（8）如果出現離線聚類請求，那么結束算法進入離線宏聚類階段;否則轉向步驟（3）。在線微聚類算法是數據流聚類算法的基礎，在整個數據流聚類階段中起著關鍵性作用。

2.2 離線宏聚類算法優化

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

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

（1）數據點X與Y的相異度計算公式為：

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

（3）數據點X的k近鄰密度計算公式為：

（4）數據點X關于其k近鄰集合Nk（X）的相對密度，簡稱為X的k近鄰相對密度，其計算公式為：

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

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

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

以下為詳細算法步驟。

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

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

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

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

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

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

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

3 實驗結果與分析

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

3.1 實驗數據集

在算法評價過程中，采用來自美國空軍和與美國植被覆蓋率有關的KDD-CUP99網絡入侵檢測數據集（數據集1）和Forest Cover Type森林覆蓋數據集（數據集2）。

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

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

3.2 實驗數據對比

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

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

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

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

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

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

4 結 語

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

參 考 文 獻

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

[2]莫徽忠.基于數據流聚類算法的網絡異常檢測系統設計[J].柳州職業技術學院學報，2017，17（3）：99-103.

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

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

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

[6]樊超，李宏偉.利用優化的DenStream算法進行空間數據流聚類

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

[7]傅坦坦.數據流處理系統中優化調度算法研究與實現[D].成都：電子科技大學，2017.

[8]孫宏.基于數據流的模糊聚類算法分析與優化[D].鎮江：江蘇科技大學，2017.

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

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

[11]李彥.數據流程序優化與可視化編程環境研究[D].武漢：華中科技大學，2015.