朱穎雯，陳松燦

（1.南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106；2.三江學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210012）

引 言

隨著技術(shù)的發(fā)展，包括傳感器在內(nèi)的越來越多的設(shè)備正在成為互聯(lián)設(shè)備，并不斷地生成數(shù)據(jù)流［1-3］。例如：每天Google 都要處理超過35 億的搜索；NASA 衛(wèi)星產(chǎn)生約4 TB 的圖片；沃爾瑪超市每天產(chǎn)生超過2 000 萬筆交易。數(shù)據(jù)流不事先存放在存儲介質(zhì)中，具有快速、時(shí)序和海量等特征。數(shù)據(jù)流的特性使得傳統(tǒng)數(shù)據(jù)挖掘方法無法用于數(shù)據(jù)流［4］。挖掘數(shù)據(jù)流即從連續(xù)不間斷的流數(shù)據(jù)中提取隱藏的知識/模式的過程，如圖1 所示。數(shù)據(jù)流挖掘包括數(shù)據(jù)流分類、數(shù)據(jù)流聚類和數(shù)據(jù)流上的關(guān)聯(lián)規(guī)則挖掘等［5-7］。其中，數(shù)據(jù)流聚類是將數(shù)據(jù)對象集合中的相似對象劃分為一個(gè)或多個(gè)“簇”的過程［8-18］，劃分后同一簇中元素彼此相似，不同簇中元素彼此相異。

圖1 數(shù)據(jù)流挖掘過程Fig.1 Data stream mining process

不同于傳統(tǒng)靜態(tài)數(shù)據(jù)聚類問題，數(shù)據(jù)流聚類因數(shù)據(jù)本身的特性造成了諸多限制，影響了傳統(tǒng)算法的直接使用。例如：森林中安放了數(shù)千個(gè)傳感器，氣象站從所有傳感器連續(xù)不斷、高速地接收有關(guān)溫度、風(fēng)速、方向、濕度和傳感器位置等天氣狀況信息。由于數(shù)據(jù)流是無界且不斷發(fā)展的，采用傳統(tǒng)聚類算法進(jìn)行批處理不可行。同時(shí)，它也無法全部存儲在內(nèi)存中，而是需要增量存儲并對數(shù)據(jù)進(jìn)行快速處理。此外，現(xiàn)實(shí)場景中，傳感器暴露在各種不同的天氣條件下，極有可能出現(xiàn)故障，如因電池電量不足、無網(wǎng)絡(luò)連接或火災(zāi)引起的數(shù)據(jù)缺失或者數(shù)據(jù)異常。聚類算法應(yīng)能隨著時(shí)間的推移提供有效聚類，并在出現(xiàn)異常需要采取行動時(shí)“突出顯示”這些異常值，如指示更換傳感器、滅火等。故本文認(rèn)為一個(gè)好的數(shù)據(jù)流聚類算法可應(yīng)對以下挑戰(zhàn)：（1）簡潔表示已發(fā)現(xiàn)的簇；（2）增量式且快速處理新到數(shù)據(jù)；（3）可快速檢測孤立點(diǎn)。

近年來，越來越多的數(shù)據(jù)流聚類算法被提出，且由于設(shè)計(jì)出的算法種類繁多，為了方便后續(xù)的追蹤與研究，很多學(xué)者從不同角度對提出的算法進(jìn)行綜述［6，8，12-15］。文獻(xiàn)［6］研究了電網(wǎng)問題的一個(gè)實(shí)例。由電網(wǎng)絡(luò)傳播的大約4 000 個(gè)傳感器連續(xù)生成數(shù)據(jù)流，對電子負(fù)載進(jìn)行每小時(shí)/每日/每周預(yù)測，使用PiD 算法進(jìn)行數(shù)據(jù)預(yù)處理［19］，作用ODAC 聚類算法進(jìn)行內(nèi)部相關(guān)度量［20］，以及用VFDT 進(jìn)行決策樹分類［21］。雖然該研究給出了數(shù)據(jù)流挖掘的實(shí)用性，但缺乏深入的分析，且其使用的算法已經(jīng)過時(shí)。文獻(xiàn)［22］討論了更多的挖掘任務(wù)和實(shí)際應(yīng)用，但仍然沒有對當(dāng)前的數(shù)據(jù)流挖掘方法有足夠的總結(jié)。文獻(xiàn)［8］描述了數(shù)據(jù)流聚類在網(wǎng)絡(luò)入侵檢測等領(lǐng)域的應(yīng)用。文獻(xiàn)［12］對2016 年以前的經(jīng)典數(shù)據(jù)流聚類進(jìn)行了分析。文獻(xiàn)［13］聚焦于數(shù)據(jù)流聚類算法在大數(shù)據(jù)集上的數(shù)據(jù)分析。文獻(xiàn)［14］對2017 年提出的數(shù)據(jù)流算法進(jìn)行分類總結(jié)。文獻(xiàn)［15］對基于距離的數(shù)據(jù)流聚類算法進(jìn)行詳細(xì)綜述。不同于以上綜述，本文引入數(shù)據(jù)流聚類算法的一般框架，并給出有依據(jù)的分類指標(biāo)，對2002 年至今最流行的數(shù)據(jù)流聚類算法進(jìn)行分類分析，同時(shí)給出數(shù)據(jù)流聚類的軟件和工具以及常用數(shù)據(jù)集，為未來算法設(shè)計(jì)提供基礎(chǔ)。

1 問題描述

1.1 數(shù)據(jù)流聚類

設(shè)數(shù)據(jù)流DS={x1，x2，…，xn}（n的取值可以無限大）為1 個(gè)帶有時(shí)間戳的多維數(shù)據(jù)點(diǎn)集合，其中每個(gè)數(shù)據(jù)點(diǎn)是1 個(gè)包含d維的數(shù)據(jù)記錄，其到達(dá)時(shí)間為ti。與傳統(tǒng)靜態(tài)數(shù)據(jù)聚類相比數(shù)據(jù)流聚類具有以下不同。

（1）一遍掃描：數(shù)據(jù)的實(shí)時(shí)到達(dá)產(chǎn)生了巨大的數(shù)據(jù)量，受限于存儲設(shè)備的大小和算法的時(shí)間復(fù)雜度問題，數(shù)據(jù)流聚類應(yīng)是單次掃描，按照流入順序依次讀取數(shù)據(jù)元素，而傳統(tǒng)靜態(tài)數(shù)據(jù)聚類可以掃描數(shù)據(jù)多次。

（2）實(shí)時(shí)響應(yīng)：數(shù)據(jù)流聚類的多數(shù)應(yīng)用要求連續(xù)在線的挖掘且具有較短響應(yīng)時(shí)間，而傳統(tǒng)靜態(tài)數(shù)據(jù)聚類的時(shí)間可以無限。

（3）有限內(nèi)存：數(shù)據(jù)流中的數(shù)據(jù)具有海量特征，內(nèi)存及硬盤無法存儲整個(gè)數(shù)據(jù)流集，而傳統(tǒng)數(shù)據(jù)是靜態(tài)的，數(shù)據(jù)量一般相對較小，可存儲。

（4）概念漂移檢測：數(shù)據(jù)流聚類過程中，因數(shù)據(jù)分布可能隨時(shí)間的推移而發(fā)生變化，故產(chǎn)生概念漂移。概念和概念漂移的定義如下。

定義1概念。產(chǎn)生數(shù)據(jù)流的過程可以被考慮為在隨機(jī)變量Y和X={X1，…，Xn}上的聯(lián)合分布，這里y∈dom(Y)表示類別標(biāo)簽，xi∈dom(Xi)表示屬性值，其中dom(·)表示隨機(jī)變量的域。

數(shù)據(jù)流背景下，概念隨時(shí)間變化，t時(shí)刻的概念可表示為

定義2概念漂移。當(dāng)t時(shí)刻和u時(shí)刻的分布發(fā)生變化，則概念漂移發(fā)生，有

（5）傳統(tǒng)數(shù)據(jù)聚類的結(jié)果通常是精確的，但數(shù)據(jù)流聚類一般只能得到近似結(jié)果。

為了更有效了解數(shù)據(jù)流聚類過程，圖2 給出一個(gè)通用數(shù)據(jù)流聚類框架。當(dāng)數(shù)據(jù)流到達(dá)，使用緩沖區(qū)存儲最新數(shù)據(jù)。隨后使用流聚類引擎讀取緩沖區(qū)中數(shù)據(jù)創(chuàng)建內(nèi)存中數(shù)據(jù)的概要。為了持續(xù)獲得概要，流聚類引擎可以應(yīng)用不同的時(shí)間窗口和計(jì)算方法。接著用戶請求被觸發(fā)，流聚類引擎對概要進(jìn)行處理并輸出近似結(jié)果。其中大多數(shù)數(shù)據(jù)流聚類算法都基于傳統(tǒng)聚類算法。最后應(yīng)用流聚類評估方法對數(shù)據(jù)流聚類算法的性能進(jìn)行評估。

圖2 數(shù)據(jù)流聚類算法的一般框架Fig.2 General frame of data stream clustering algorithm

1.2 時(shí)間窗口

一般來說，數(shù)據(jù)流是無限的，所以某個(gè)時(shí)刻只能處理流的一部分，這里定義為時(shí)間窗口，表示為W[i，j]=(xi，xi+1，…，xj)，其中i＜j。時(shí)間窗口旨在“忘記”舊數(shù)據(jù)，以避免歷史數(shù)據(jù)使分析偏向于過時(shí)的模式。時(shí)間窗口模型主要有4 種：界標(biāo)窗口、滑動窗口、衰減窗口和傾斜時(shí)間窗口，如圖3 所示。

圖3 時(shí)間窗口Fig.3 Time window

（1）界標(biāo)窗口

界標(biāo)窗口根據(jù)事件將數(shù)據(jù)流分割成不連貫的塊。從開始時(shí)刻1 到當(dāng)前時(shí)刻tc的數(shù)據(jù)，記為W[1，tc]，即界標(biāo)到達(dá)后的所有數(shù)據(jù)點(diǎn)都同樣重要，沒有過去和現(xiàn)在之間的差異。每當(dāng)出現(xiàn)新界標(biāo)時(shí)，刪除窗口中的所有數(shù)據(jù)，并捕獲新數(shù)據(jù)。但是，隨著數(shù)據(jù)流的不斷發(fā)展，新數(shù)據(jù)點(diǎn)可能與之前舊數(shù)據(jù)點(diǎn)構(gòu)建的模型出現(xiàn)不一致，故可使用其他3 種窗口模型強(qiáng)調(diào)最近數(shù)據(jù)。

（2）滑動窗口

滑動窗口只對最近的w個(gè)數(shù)據(jù)點(diǎn)感興趣，用W[tc-w+1，tc]表示。其基于先進(jìn)先出原則，即一旦有新數(shù)據(jù)點(diǎn)可用，窗口中最老的數(shù)據(jù)點(diǎn)就會被刪除，這樣減少了對內(nèi)存的需求。但挖掘結(jié)果依賴窗口大小w，如果w太大，可能出現(xiàn)概念漂移，并由于窗口中包含了太多的過時(shí)信息，導(dǎo)致模型的精度下降。如果w太小，窗口可能因數(shù)據(jù)貧乏而導(dǎo)致模型過擬合或者大的方差。之前的工作使用了固定的窗口大小w，而最近的工作開始使用可伸縮的窗口大小w，當(dāng)模型精度較高時(shí)，放大w的值，當(dāng)模型精度較低時(shí)，縮小w的值。

（3）衰減窗口

衰減窗口強(qiáng)調(diào)近期數(shù)據(jù)的重要性，衰減歷史數(shù)據(jù)對計(jì)算結(jié)果的影響。每個(gè)數(shù)據(jù)元素對最終結(jié)果的影響用權(quán)值來表示，并隨著時(shí)間的推移而逐漸減小。每次迭代中，權(quán)重通過1 個(gè)因子（如2-λ）衰減，其中衰減因子λ影響衰減速率。由于每次迭代中衰減權(quán)值的計(jì)算成本很高，所以權(quán)值可以在固定的時(shí)間間隔內(nèi)更新，也可以在更新簇時(shí)更新。如衰減函數(shù)可表示為w(Δt)=2-λΔt，其中Δt表示聚簇上次更新的時(shí)間。

（4）傾斜時(shí)間窗口

傾斜時(shí)間窗口可在不同級別時(shí)間粒度層上進(jìn)行分析和挖掘。通常人們感興趣的是細(xì)粒度層上的當(dāng)前數(shù)據(jù)，而不是粗粒度層上的長期數(shù)據(jù)。為此，傾斜窗口計(jì)算中，在最細(xì)粒度層上記錄和運(yùn)算最近數(shù)據(jù)，在較粗粒度層上記錄和計(jì)算較久遠(yuǎn)數(shù)據(jù)。傾斜窗口在存儲空間和精度上提供了良好的權(quán)衡，近似存儲了整個(gè)數(shù)據(jù)集。但隨著長時(shí)間運(yùn)行，模型穩(wěn)定性仍可能下降。

1.3 計(jì)算方法

數(shù)據(jù)流聚類通常采用以下兩種計(jì)算方法。

（1）增量學(xué)習(xí)。增量學(xué)習(xí)方法中，模型逐漸發(fā)展以適應(yīng)傳入數(shù)據(jù)的更改。增量學(xué)習(xí)方法如圖4（a）所示，可采用按數(shù)據(jù)實(shí)例和窗口兩種方案進(jìn)行更新，具有即時(shí)提供挖掘結(jié)果的優(yōu)勢，但需要更多的計(jì)算資源。

（2）兩階段學(xué)習(xí)。兩階段學(xué)習(xí)，也稱為在線-離線學(xué)習(xí)。第一階段（在線階段），采用實(shí)時(shí)方式更新數(shù)據(jù)概要。第二階段（離線階段），當(dāng)用戶發(fā)送請求時(shí)基于已存儲的概要進(jìn)行挖掘。兩階段學(xué)習(xí)方法如圖4（b）所示。這種方法能夠處理數(shù)據(jù)高速流，但是它的局限性在于用戶必須等到挖掘結(jié)果。

圖4 計(jì)算方法Fig.4 Learning method

1.4 流聚類評估方法

為了對各種數(shù)據(jù)流聚類算法的精度進(jìn)行評估，常用以下3 項(xiàng)評價(jià)指標(biāo)［23］：精確度（Accuracy，Acc）；歸一化互信息（Normalized mutual information，NMI）；蘭德指數(shù)（Rand index，RI）。

（1）精確度Acc［24］

精確度Acc 計(jì)算公式如下

式中：K表示聚簇個(gè)數(shù)；||表示在聚簇i中的樣本點(diǎn)數(shù)；|Ci|表示聚簇i中真實(shí)的樣本個(gè)數(shù)。因此，Acc 度量了聚簇的精度，Acc ∈[0，1]，Acc 越大表明聚類精度越高。

（2）歸一化互信息［25］

歸一化互信息NMI 是量化兩個(gè)分布之間共享統(tǒng)計(jì)信息的對稱策略。當(dāng)聚簇標(biāo)簽和真實(shí)樣本類別一對一映射時(shí)，NMI 值得到最大值1。給定真實(shí)聚簇A={A1，A2，…，Ak} 和某聚類算法得到的聚簇B={B1，B2，…，Bh}，混淆矩陣C中的元素Cij表示既在Ai又在Bj中的樣本個(gè)數(shù)。NMI 計(jì)算如下

式中：CA（CB）表示A（B）中樣本個(gè)數(shù)；Ci.（C.j）表示C中i行元素和；N表示樣本個(gè)數(shù)。

（3）蘭德指數(shù)［26］

RI 比較n×(n-1)/2 個(gè)數(shù)據(jù)對，其中n為數(shù)據(jù)集中樣本個(gè)數(shù)，P1、P2表示兩種聚類算法，n1為數(shù)據(jù)對（xi，xj）在P1、P2中劃分為同一類的數(shù)據(jù)對數(shù)，n00則為（xi，xj）隸屬不同類的數(shù)據(jù)對數(shù)，RI 計(jì)算如下

由式（5）可得RI ∈[0，1]，RI=1 表示P1與P2劃分完全一致。

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

現(xiàn)有數(shù)據(jù)流聚類算法一般由傳統(tǒng)聚類算法擴(kuò)展而來，可將其根據(jù)所擴(kuò)展的傳統(tǒng)算法分為5 類：基于劃分的方法；基于層次的方法；基于密度的方法；基于網(wǎng)格的方法；基于模型的方法。表1 分別針對如下特性對現(xiàn)有方法進(jìn)行總結(jié)：（1）基算法；（2）時(shí)間窗口；（3）計(jì)算方法；（4）聚簇個(gè)數(shù)是否自適應(yīng)；（5）是否可挖掘拓?fù)浣Y(jié)構(gòu)；（6）是否可檢測概念漂移；（7）是否適合高維數(shù)據(jù)。如表1 所示，基于劃分的數(shù)據(jù)流聚類方法易于實(shí)現(xiàn)且相對簡單，但需預(yù)定義聚簇的個(gè)數(shù)。例如，STREAM 算法［27］應(yīng)用K-median 算法，使用中位數(shù)來計(jì)算中心，將聚類問題簡化為數(shù)據(jù)點(diǎn)到最近聚簇的距離代價(jià)最小化問題，即找出代價(jià)最低的聚簇的數(shù)量和位置。文獻(xiàn)［28］基于K-Means 算法聚類數(shù)據(jù)流，克服了基于劃分的聚類算法需要給出聚簇個(gè)數(shù)k及適應(yīng)概念漂移這兩個(gè)問題。FEAC-Stream 算法［29］基于K-Means 算法，使用進(jìn)化算法自動估計(jì)聚簇個(gè)數(shù)k。完全在線時(shí)，F(xiàn)EAC-Stream 不存儲數(shù)據(jù)概要，而是維護(hù)最終的聚類結(jié)果；運(yùn)行時(shí)使用Page-Hinkley 測試跟蹤聚類質(zhì)量，如果質(zhì)量下降，算法自行調(diào)整。

表1 數(shù)據(jù)流聚類算法比較Table 1 Comparison of various data stream clustering algorithms

基于層次的數(shù)據(jù)流聚類方法雖可發(fā)現(xiàn)有意義的聚簇結(jié)構(gòu)，但其具有較高的計(jì)算代價(jià)，而且對流數(shù)據(jù)到達(dá)的順序敏感。例如，CluStream 算法［30］允許在不同的時(shí)間范圍而不是整個(gè)數(shù)據(jù)流上執(zhí)行聚類。它還通過存儲所有時(shí)間戳的線性和以及平方和來擴(kuò)展聚類特征（Clustering feature vector，CF）。為了支持不同的時(shí)間范圍，算法按照金字塔方案定期存儲當(dāng)前微聚簇的快照。雖然有些快照會定期更新，但為了維護(hù)關(guān)于歷史數(shù)據(jù)的信息，有些快照更新得不那么頻繁。通過從存儲的快照中減去當(dāng)前的微聚簇，可以近似地得到數(shù)據(jù)流的期望部分。然后，將提取的微聚簇運(yùn)行K-Means 的變體算法來生成宏觀簇。基于CluStream 算法框架，許多改進(jìn)算法被提出。HPStream［11］引入投影聚類，為每個(gè)聚簇（子空間聚簇）選擇最佳屬性集，獲得了比CluStream 更好的聚類質(zhì)量。SWClustering 算法［31］為滑動窗口創(chuàng)建了時(shí)間聚簇特征解決了當(dāng)微聚簇中心逐漸移動時(shí)，CluStream 以不斷增長的半徑維持該微聚簇，而未將其分裂成許多更小的微聚簇導(dǎo)致的聚類性能下降，在運(yùn)行時(shí)間和內(nèi)存使用方面具有更好的性能。E-Stream 算法［32］將聚簇演化分為5 個(gè)類型：出現(xiàn)、消失、自演化、合并和分裂，并使用衰減模型和簇直方圖來識別簇進(jìn)化的類型。受CHAMELEON 算法啟發(fā)，REPSTREAM 算法［33］是一種基于圖的數(shù)據(jù)流層次聚類方法。為了識別聚簇，REPSTREAM 更新2 個(gè)稀疏圖，這2 個(gè)稀疏圖是通過連接每個(gè)頂點(diǎn)到它的K-近鄰頂點(diǎn)形成的。第1 個(gè)圖捕獲了到達(dá)數(shù)據(jù)點(diǎn)之間的連接關(guān)系，用于選擇1 組代表性的頂點(diǎn)。

第2 個(gè)圖由具有代表性的頂點(diǎn)構(gòu)成，有助于在更高層次上做出聚類決策。REPSTREAM 應(yīng)用衰減窗口減少舊數(shù)據(jù)的影響。REPSTREAM 跟蹤代表性頂點(diǎn)之間的連接性，并根據(jù)它們的連接性進(jìn)行合并或拆分。

基于密度的數(shù)據(jù)流聚類方法可發(fā)現(xiàn)任意形狀的聚簇，但算法預(yù)設(shè)參數(shù)太多是它的弊端。例如，DenStream 算法［24］與CluStream 一樣使用微聚簇捕獲數(shù)據(jù)流的概要信息。在線階段每個(gè)微聚簇都具有一個(gè)由聚類特征向量得到中心和半徑。微聚簇可分為3 種類型：核心微聚簇、潛在微聚簇和孤立點(diǎn)微聚簇。離線階段，在3 種類型的微聚簇上應(yīng)用DBSCAN 算法。ACSC 蟻群流聚類算法［34］提供一種對非平穩(wěn)聚簇進(jìn)行總結(jié)的流聚類方法，同時(shí)解決聚簇個(gè)數(shù)變化問題。使用采樣解決數(shù)據(jù)流聚類的速度要求，點(diǎn)與聚簇的相似性評估僅使用這個(gè)聚簇中的一個(gè)點(diǎn)。隨機(jī)抽樣方法取代了傳統(tǒng)的窮舉搜索每個(gè)點(diǎn)合適的微聚簇，然后搜索每個(gè)微聚簇的最近鄰，使用螞蟻啟發(fā)的排序方法對這些聚簇進(jìn)行細(xì)化。OPTICS-Stream 算法［35］利用OPTICS 算法中的核心距離和可達(dá)距離進(jìn)行聚類。incPre-Decon 算法［36］支持單個(gè)數(shù)據(jù)對象更新和塊更新，可用于處理動態(tài)數(shù)據(jù)流。HDDSTREAM 算法［37］是一個(gè)基于密度的高維數(shù)據(jù)流投影聚類算法。HDDSTREAM 算法提出了一種總結(jié)結(jié)構(gòu)，即投影微聚簇，用于在相關(guān)維度上總結(jié)一組對象。在流環(huán)境中，聚簇很可能會隨著時(shí)間的改變成為離群點(diǎn)，故其提出了不同類型的微聚簇，以便逐步形成真實(shí)的投影微聚簇并安全去除離群點(diǎn)。與HPStream 相反，當(dāng)1 個(gè)新數(shù)據(jù)到來，如果它遠(yuǎn)離所有現(xiàn)有聚簇，則將成為1 個(gè)新聚簇的種子（即使它是1 個(gè)離群點(diǎn)），一些舊聚簇將被刪除，以保持聚簇的總數(shù)量不變。MuDi-Stream［38］是一種在線-離線數(shù)據(jù)流聚類算法。在線階段，以核心微聚簇形式保存多密度數(shù)據(jù)流演進(jìn)的匯總信息；離線階段使用自適應(yīng)的基于密度的聚類算法生成最終的聚簇。基于網(wǎng)格的方法作為離群值緩沖來處理噪聲和多密度數(shù)據(jù)，并減少聚簇合并時(shí)間。CEDAS 算法［39］可聚類演變的概念漂移數(shù)據(jù)流到任意形狀的簇。文獻(xiàn)［40］提出一種基于密度的兩階段算法，適用于任意形狀的聚簇，其主要特點(diǎn)是根據(jù)輸入的數(shù)據(jù)自動調(diào)整閾值。I-HASTREAM 算法［41］也是基于密度的兩階段算法，是HASTREAM 算法的改進(jìn)版本。在線階段，它為數(shù)據(jù)概要創(chuàng)建為微聚簇；離線階段，微聚簇得到最小生成樹，最后采用層次聚類進(jìn)行聚類。

基于網(wǎng)格的數(shù)據(jù)流聚類方法不僅運(yùn)行速度較快，也可發(fā)現(xiàn)任意形狀聚簇，但其聚類質(zhì)量取決于選取的網(wǎng)格粒度。例如，D-Stream 算法［42］采用兩階段學(xué)習(xí)。在線階段中將輸入數(shù)據(jù)點(diǎn)映射到網(wǎng)格，離線階段中計(jì)算網(wǎng)格密度并基于密度對網(wǎng)格進(jìn)行聚類。與其他算法不同，D-Stream 自動、動態(tài)地調(diào)整聚簇，不需要用戶指定目標(biāo)時(shí)間范圍和聚簇個(gè)數(shù)。MR-Stream 算法［43］通過使用單元網(wǎng)格（可以使用樹狀數(shù)據(jù)結(jié)構(gòu)動態(tài)地細(xì)分為更多單元）來促進(jìn)在多種分辨率下發(fā)現(xiàn)聚簇。在線階段，它將新傳入數(shù)據(jù)分配給適當(dāng)?shù)膯卧?，并更新概要信息；離線階段在固定高度h獲得樹的一部分，并在h確定的分辨率級別上執(zhí)行聚類。CellTree 算法［44］首先將數(shù)據(jù)空間劃分為一組互斥的大小相同的單元格。當(dāng)單元格的權(quán)重大于某一閾值時(shí)，采用混合劃分方法即對μ-劃分和σ-劃分進(jìn)行折中，將單元格動態(tài)劃分為2 個(gè)中間單元。μ-劃分通過最大化標(biāo)準(zhǔn)差選擇維度，而σ-劃分選擇標(biāo)準(zhǔn)差最小的維度。

基于模型的數(shù)據(jù)流聚類算法包含了很多領(lǐng)域知識，強(qiáng)依賴于假設(shè)模型，例如：SWEM 算法［45］基于EM 模型，GCPSOM 算法［46］基于SOM 模型，SVStream 算法［47］基于SVM 模 型，G-Stream［23］和RPGStream［41］算法基于生長型神經(jīng)氣（Growing neural gas，GNG）模型。表2 給出了各類算法的優(yōu)缺點(diǎn)比較。圖5 突出顯示了算法之間的關(guān)系，并顯示了隨著時(shí)間的推移，概念是如何被完善和改進(jìn)的。

圖5 數(shù)據(jù)流聚類算法發(fā)展Fig.5 Development of stream clustering algorithms

表2 數(shù)據(jù)流聚類算法優(yōu)缺點(diǎn)比較Table 2 Advantages and disadvantages of partial data stream clustering algorithms

2.1 Adaptive Streaming K-Means 算法

Adaptive Streaming K-Means 通過擴(kuò)展傳統(tǒng)基于劃分的K-Means 算法聚類數(shù)據(jù)流。通常，基于劃分的聚類算法需要給出聚簇個(gè)數(shù)k，且難以適應(yīng)輸入數(shù)據(jù)中的概念漂移。但Adaptive Streaming K-Means克服了這兩個(gè)問題。

Adaptive Streaming K-Means 算法主要分為2 個(gè)階段，即初始化階段和連續(xù)聚類階段。在初始化階段，l個(gè)數(shù)據(jù)點(diǎn)被累積，然后確定候選中心。為了找到聚簇個(gè)數(shù)k并確定候選中心，通過使用核密度估計(jì)（Kernel density estimation，KDE）計(jì)算數(shù)據(jù)的概率密度函數(shù)（Probability density function，PDF）。PDF曲線形狀的所有方向變化都被認(rèn)為是新區(qū)域開始的標(biāo)志。區(qū)域可以定義為PDF 曲線兩個(gè)連續(xù)方向變化之間的區(qū)域，將區(qū)域數(shù)量作為候選k，區(qū)域的中心作為候選初始中心。由于不同的特征通常表現(xiàn)出不同的分布，k值超過1 個(gè)，因此會找到不同的候選中心。對k∈[kmin，kmin+kmax]進(jìn)行聚類，根據(jù)輪廓系數(shù)比較不同k值的聚類結(jié)果，選擇最好的k以及與其對應(yīng)的中心。在連續(xù)聚類階段，先執(zhí)行概念漂移檢查，如果沒有發(fā)生概念漂移，則對輸入數(shù)據(jù)進(jìn)行聚類。如果存在概念漂移，則重新計(jì)算k和中心（重新初始化算法），然后繼續(xù)使用新的k和中心進(jìn)行聚類。對于概念漂移檢測，算法執(zhí)行過程中存儲輸入數(shù)據(jù)的標(biāo)準(zhǔn)差和均值。跟蹤這2 個(gè)值如何隨時(shí)間變化，并根據(jù)變化預(yù)測概念漂移。當(dāng)1 個(gè)概念漂移被預(yù)測時(shí)，當(dāng)前的聚類中心不再有效，并觸發(fā)重新初始化。使用這種機(jī)制，算法捕獲概念漂移并適應(yīng)輸入流。鑒于算法本質(zhì)為K-Means，該算法仍有只能檢測到超球形簇的缺陷。

2.2 CluStream 算法

CluStream 算法通過擴(kuò)展傳統(tǒng)聚類方法BIRCH 聚類數(shù)據(jù)流，使用微聚簇來構(gòu)造數(shù)據(jù)流的總結(jié)信息。該算法擴(kuò)展了BIRCH 的CF，允許在不同時(shí)間范圍而不是整個(gè)數(shù)據(jù)流上執(zhí)行聚類。根據(jù)擴(kuò)展CF定義微聚簇如下。

定義3微聚簇。帶時(shí)間戳的d維數(shù)據(jù)點(diǎn)集，其中。微聚簇被定義為（2·d+3）元組（CF2x，CF1x，CF2t，CF1t，n）。其中，矢量CF2x和CF1x分別表示每維數(shù)據(jù)值的平方和及累加和，如第p維的CF2x和CF1x分別表示為；標(biāo)量CF2t和CF1t分別表示時(shí)間戳的平方和及累加和；n是數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

CluStream 在線階段通過收集數(shù)據(jù)并使用K-Means 算法創(chuàng)建q個(gè)簇進(jìn)行初始化。當(dāng)新的數(shù)據(jù)點(diǎn)到達(dá)，它會被離它最近的微聚簇所吸收，否則創(chuàng)建新的聚簇。為了保持微聚簇的數(shù)量不變，過時(shí)的微聚簇會根據(jù)其平均時(shí)間戳的閾值被移除或者合并兩個(gè)最近的微聚簇。為支持不同的時(shí)間粒度，該算法應(yīng)用傾斜時(shí)間窗口定期存儲當(dāng)前CF 的快照。雖然有些快照會定期更新，但有些快照為維護(hù)歷史數(shù)據(jù)的信息而更新不頻繁。通過從先前CF 的存儲快照中減去當(dāng)前CF，可以近似得到流的所需部分。離線階段通過提取的微聚簇運(yùn)行K-Means 變體算法生成宏聚簇。CluStream 雖可產(chǎn)生高質(zhì)量的聚類結(jié)果，但不能用于高維數(shù)據(jù)流聚類。

2.3 DenStream 算法

DenStream 算法使用基于CF 向量的特征向量，通過創(chuàng)建兩種類型的微聚簇（潛在微聚簇和孤立點(diǎn)微聚簇）克服了CluStream 算法對噪聲的敏感性。

在線階段每個(gè)潛在微聚簇都具有1 個(gè)相關(guān)的權(quán)值w表示其基于時(shí)間的重要性。通過衰減函數(shù)f(t)=2-λ（tλ＞0），每個(gè)數(shù)據(jù)點(diǎn)的權(quán)值隨時(shí)間t呈指數(shù)衰減。如果權(quán)值大于閾值μ，則將該聚簇視為核心微聚簇，其中Ti1，…，Tin是數(shù)據(jù)點(diǎn)pi1，…，pin的時(shí)間戳。t時(shí)刻，如果w≥βμ，則聚簇是潛在微聚簇，否則它是孤立點(diǎn)微聚簇，其中β是孤立點(diǎn)相對于核心微聚簇的閾值（0 ＜β＜1）。當(dāng)1 個(gè)新的數(shù)據(jù)點(diǎn)到達(dá)，DenStream 根據(jù)其更新的半徑將其插入到最近的潛在微聚簇中。如果插入失敗，嘗試將該數(shù)據(jù)點(diǎn)插入到最近的孤立點(diǎn)微聚簇中；如果插入成功，更新聚簇概要統(tǒng)計(jì)信息。否則，創(chuàng)建1 個(gè)新的孤立點(diǎn)微聚簇吸收這個(gè)點(diǎn)。DenStream 采用剪枝在孤立點(diǎn)緩沖區(qū)檢查孤立點(diǎn)微聚簇的權(quán)重，以保證能夠識別出真正的孤立點(diǎn)。然而，當(dāng)刪除1 個(gè)微聚簇或合并2 個(gè)舊的微聚簇時(shí)，不釋放分配的內(nèi)存單元，以及刪除孤立點(diǎn)的剪枝過程相當(dāng)耗時(shí)，這是DenStream 算法的不足。離線階段將在線階段發(fā)現(xiàn)的潛在微聚簇傳遞到DBSCAN 算法，以確定最終的聚類結(jié)果。

為了湊夠每天一萬多步,往常吃肉喝酒的傍晚,現(xiàn)在變成了在街頭徒步。饑餓如期而至,沿街的小餐館里飄出各種菜的香味。在一家館子的門口,我甚至嗅出了幾道菜的味道:蒜薹肉絲,火爆腰花……這是很大的折磨,雙腳也開始不聽使喚起來,步履變得沉重。但是,這種饑餓的感覺又讓我感到欣喜,因?yàn)槲夷軌虼_信,自己的行動正在產(chǎn)生價(jià)值。

2.4 ACSC 算法

ACSC 蟻群流聚類算法［34］提供一種對非平穩(wěn)聚簇進(jìn)行總結(jié)的流聚類方法，同時(shí)解決聚簇個(gè)數(shù)變化問題。該算法使用采樣解決數(shù)據(jù)流聚類的速度要求，點(diǎn)與聚簇的相似性評估僅使用這個(gè)聚簇中的1 個(gè)點(diǎn)。同時(shí)，隨機(jī)抽樣方法取代了傳統(tǒng)的窮舉搜索每個(gè)點(diǎn)合適的微聚簇，然后搜索每個(gè)微聚簇的最近鄰。單遍數(shù)據(jù)掃描后創(chuàng)建粗粒度的聚簇，第1 個(gè)數(shù)據(jù)點(diǎn)即為第1 個(gè)聚簇，后面的數(shù)據(jù)點(diǎn)被分配到1 個(gè)相似的現(xiàn)有聚簇，如果與所有聚簇都不相似，則生成1 個(gè)新的聚簇。只有在每個(gè)點(diǎn)被分配到各自的聚簇之后，才會創(chuàng)建微聚簇。每個(gè)點(diǎn)被轉(zhuǎn)換為1 個(gè)微聚簇，這些微聚簇只嘗試與同一聚簇中的其他點(diǎn)合并，合并操作代價(jià)高。

因?yàn)閱伪閽呙韬笊傻木鄞赝ǔ４植谇覀€(gè)數(shù)多，使用螞蟻啟發(fā)的排序方法對這些聚簇進(jìn)行細(xì)化。這種方法是建立在螞蟻行為上的模型，螞蟻會把尸體聚集到“墓地”或分類，即孤立的數(shù)據(jù)點(diǎn)應(yīng)該被撿起來，然后丟在其他有類似數(shù)據(jù)點(diǎn)的地方。排序螞蟻被分配到每個(gè)聚簇中，它們試圖通過概率性地挑選微聚簇并將它們放到更合適的聚簇中來精煉初始聚簇。這些操作傾向于解散較小的聚簇，將其內(nèi)容移動到相似的、較大的聚簇。直觀地說，聚簇中所有數(shù)據(jù)點(diǎn)應(yīng)放在一個(gè)大的聚簇中，而不是放在許多分布的小聚簇中。DenStream 算法中微聚簇由2 個(gè)參數(shù)定義：最大半徑ε和最小值。最小值表示ε內(nèi)密集的微聚簇的最小數(shù)據(jù)點(diǎn)數(shù)。但ACSC 中每個(gè)點(diǎn)最初被視為自己的微聚簇，因此參數(shù)最小值為1，故不再需要。這使得將微聚簇定義為核心、潛在或離群值的復(fù)雜性降低，從而每個(gè)微聚簇都被平等地對待。為進(jìn)一步簡化，ACSC 將密度可達(dá)、直接密度可達(dá)和密度連接的概念合并為僅密度可達(dá)1 個(gè)概念，其決定2 個(gè)微聚簇是否連接，并被視為同一聚簇的不同部分。ACSC 在創(chuàng)建和合并微聚簇之前會給聚簇分配樣本點(diǎn)，因此當(dāng)1 個(gè)新的微聚簇直接密度可達(dá)時(shí)，它也會密度可達(dá)并密度連接到聚簇中的所有微聚簇。這樣降低了算法整體的復(fù)雜性，并允許有效采樣。ACSC 有如下改進(jìn)：（1）將總結(jié)和聚類兩個(gè)階段結(jié)合成1 個(gè)在線過程；（2）微聚簇使用單個(gè)參數(shù)ε定義，總體只需要3 個(gè)參數(shù)；（3）使用單個(gè)密度概念形成聚簇，將離群點(diǎn)識別為包含單個(gè)數(shù)據(jù)點(diǎn)的聚類；（4）通過對每個(gè)聚簇進(jìn)行采樣，本地進(jìn)行排序操作，減少了計(jì)算時(shí)間。

2.5 D-Stream 算法

D-Stream 算法結(jié)合了基于密度和網(wǎng)格的方法。在線階段將接受到的每個(gè)數(shù)據(jù)點(diǎn)映射到某個(gè)網(wǎng)格中，離線階段計(jì)算網(wǎng)格密度，并基于密度將網(wǎng)格進(jìn)行聚類。D-Stream 算法進(jìn)行了下列改進(jìn)：

（1）為了獲得簇的動態(tài)演變，提出了與每個(gè)數(shù)據(jù)點(diǎn)密度相關(guān)的密度衰減因子。衰減因子賦予近期數(shù)據(jù)更大的權(quán)重，并且沒有丟棄歷史信息。

（2）由于數(shù)據(jù)流海量，完全保存每個(gè)數(shù)據(jù)記錄的信息不可行，D-Stream 算法將數(shù)據(jù)空間劃分成網(wǎng)格單元，并將數(shù)據(jù)點(diǎn)映射到對應(yīng)的網(wǎng)格單元中，同時(shí)更新網(wǎng)格的特征向量。使用網(wǎng)格作為概要數(shù)據(jù)結(jié)構(gòu)，不需要對原數(shù)據(jù)進(jìn)行保存只需要對網(wǎng)格單元進(jìn)行操作，具有較快的處理時(shí)間。

（3）采用基于密度的方法對網(wǎng)格單元進(jìn)行聚類，可以發(fā)現(xiàn)任意形狀的簇，能有效解決CluStream 算法等只能識別球形簇的問題。

（4）可動態(tài)調(diào)整簇，且不需要用戶指定目標(biāo)時(shí)間范圍和聚簇的個(gè)數(shù)。

D-Stream 算法盡管存在多種優(yōu)點(diǎn)，同時(shí)也存在一些不足之處，如：采用網(wǎng)格概要數(shù)據(jù)結(jié)構(gòu)會丟失數(shù)據(jù)的位置信息；當(dāng)被應(yīng)用于聚類高維數(shù)據(jù)流時(shí)，網(wǎng)格單元的個(gè)數(shù)可能會很大；對數(shù)據(jù)空間進(jìn)行均勻網(wǎng)格劃分，網(wǎng)格的劃分粒度將直接影響聚類的精度。使用基于密度的計(jì)算方法對當(dāng)前的數(shù)據(jù)流聚類能產(chǎn)生很多的聚類結(jié)果，不利于對歷史信息查詢。算法沒有對低密度的網(wǎng)格單元進(jìn)行處理，也會影響聚類的精度。

2.6 RPGStream 算法

定義4隨機(jī)投影。原始的d維數(shù)據(jù)使用隨機(jī)矩陣被投影到dc（dc?d）維子空間。樣本矩陣Xn×（dn個(gè)樣本，d維）利用式（6）投影到，即

JL 引理［37］是隨機(jī)投影的理論依據(jù)，即高維歐氏空間的點(diǎn)映射到低維空間，相對距離可得到一定誤差范圍內(nèi)的保持。

定理1［37］設(shè)樣本矩陣X∈Rn×d包含n個(gè)樣本d維特征，給定ε，β＞0，則

式中：參數(shù)ε控制距離保持的精度；β控制投影成功的概率。隨機(jī)矩陣R為一個(gè)d×dc矩陣，dc為正整數(shù)，且dc≥k0，設(shè)將X的第i行映射 到E的第i行。

對所有的u，v∈X，在至少1-n-β概率下，有

從式（8）看出，理論上JL 界（k0）不依賴于原始空間的維度d，為得到定理1 的結(jié)果，只需生成隨機(jī)投影矩陣R并進(jìn)行投影計(jì)算。隨機(jī)投影矩陣R(i，j)=rij，rij為一個(gè)獨(dú)立的隨機(jī)變量，可以由以下3 種概率分布生成

RPGStream 算法首先依據(jù)dc的大小生成隨機(jī)投影矩陣，當(dāng)一個(gè)新的數(shù)據(jù)點(diǎn)xi到達(dá)時(shí)，用將xi投影到對應(yīng)的dc維（dc?d）點(diǎn)yi。從而整個(gè)數(shù)據(jù)流DSn×d={x1，x2，…，xn}被投影到{y1，y2，…，yn}，再對使用G-Stream 算法進(jìn)行聚類。RPGStream 生成了包含一系列神經(jīng)元節(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的權(quán)值向量為。

3 軟件與工具

數(shù)據(jù)流聚類在實(shí)際應(yīng)用中的一個(gè)重要方面是可用的軟件和工具。只有少數(shù)作者為他們的算法提供參考實(shí)現(xiàn)，例如，C、C++或R 實(shí)現(xiàn)可以用于實(shí)現(xiàn)STREAM 算法［49］和REPSTREAM 算法。

可用的數(shù)據(jù)流挖掘軟件包括：

（1）WEKA①http://www.cs.waikato.ac.nz/ml/weka。WEKA 是學(xué)術(shù)領(lǐng)域最知名的數(shù)據(jù)挖掘軟件。WEKA 包括數(shù)據(jù)預(yù)處理、回歸、分類、聚類和關(guān)聯(lián)規(guī)則等1 組學(xué)習(xí)算法。

（2）大規(guī)模在線分析（Massive online analysis，MOA）②https://moa.cms.waikato.ac.nz/［50］。MOA 是用于數(shù)據(jù)流挖掘流行的開源框架，它包含了分類和聚類的離線在線集合，以及用于評估的工具。實(shí)現(xiàn)了流聚類算法D-Stream，Den-Stream 和CluStream。

（3）RapidMiner③https://rapidminer.com/。RapidMiner 是另一個(gè)用于數(shù)據(jù)挖掘的開源軟件。RapidMiner 比WEKA 更強(qiáng)大，因?yàn)樗薟EKA 中的所有算法和其他高級算法，并且將挖掘過程定義為一系列操作人員，提供更多可視化工具，更加直觀。

（4）streamMOA。為了更快地創(chuàng)建原型，還存在統(tǒng)計(jì)編程語言R 的流包［51］。它包含處理數(shù)據(jù)流的通用方法，還實(shí)現(xiàn)了D-Stream 等算法。擴(kuò)展包streamMOA［52］接口對DenStream 和CluStream 算法進(jìn)行MOA 實(shí)現(xiàn)。為了在高維空間中處理數(shù)據(jù)，子空間MOA 框架［53］提供了HDDStream 的Java 實(shí)現(xiàn)。同樣，R-語言子空間MOA 框架也可接口兩種方法，使它們可以被流包訪問。

（5）streamDM 華為諾亞方舟實(shí)驗(yàn)室2015 項(xiàng)目［54］提供了Spark 流數(shù)據(jù)挖掘方法，Spark 流是Spark 引擎的擴(kuò)展。目前它實(shí)現(xiàn)了CluStream 等算法，并計(jì)劃用更多的流聚類算法擴(kuò)展項(xiàng)目。

4 數(shù)據(jù)集

為了測試數(shù)據(jù)流聚類性能，常使用人工數(shù)據(jù)集。人工數(shù)據(jù)集讓用戶有機(jī)會指定流的屬性，如噪聲比、概念漂移、聚簇形狀和密度等。MOA 有許多類不同的MOA 流生成器，可生成不同形狀、有或沒有概念漂移的人工數(shù)據(jù)流。除了人工數(shù)據(jù)集，其他流行的真實(shí)數(shù)據(jù)集如表3 所示。

表3 流行的真實(shí)數(shù)據(jù)集Table 3 Statistics of popular datasets

5 結(jié)束語

本文系統(tǒng)地介紹了數(shù)據(jù)流挖掘的挑戰(zhàn)，給出了數(shù)據(jù)流聚類的一般框架，并描述了其與傳統(tǒng)靜態(tài)數(shù)據(jù)聚類之間的關(guān)聯(lián)，對數(shù)據(jù)流挖掘中的各種聚類算法進(jìn)行了綜述。盡管已有大量數(shù)據(jù)流聚類算法被提出，數(shù)據(jù)流聚類依然是極富挑戰(zhàn)的研究熱點(diǎn)。隨著愈加廣泛的應(yīng)用領(lǐng)域中大量數(shù)據(jù)流的產(chǎn)生，越來越多的研究主題不斷涌現(xiàn)出來。

（1）隱私保護(hù)和保密。數(shù)據(jù)流對數(shù)據(jù)挖掘中的隱私和機(jī)密性保護(hù)提出了新的挑戰(zhàn)和機(jī)遇。例如，健康監(jiān)測數(shù)據(jù)流、GPS 數(shù)據(jù)流等多隱含用戶的生理特征信息、位置信息，一旦數(shù)據(jù)遭暴露或?yàn)E用，嚴(yán)重影響用戶的隱私安全。因此，設(shè)計(jì)基于隱私保護(hù)的數(shù)據(jù)流聚類模型是一個(gè)可行且必要的研究方向。

（2）跟蹤聚簇演變。數(shù)據(jù)流中的數(shù)據(jù)類型具有異質(zhì)特性（文本、視頻、音頻、靜態(tài)圖像等），數(shù)據(jù)處理能力具有差異性（結(jié)構(gòu)化、半結(jié)構(gòu)化、非結(jié)構(gòu)化數(shù)據(jù)），以多視圖視角同時(shí)處理這些數(shù)據(jù)，也將是一類極具挑戰(zhàn)性的研究場景。在該類場景下，數(shù)據(jù)流聚類的一個(gè)有趣的未來應(yīng)用是社會網(wǎng)絡(luò)分析。社交網(wǎng)絡(luò)成員的活動可以看作是一個(gè)數(shù)據(jù)流，聚類算法可以用來顯示成員之間的相似性，以及這些相似的概況（聚簇）是如何隨著時(shí)間的推移而演變的。通過跟蹤聚簇的演變情況獲得有關(guān)數(shù)據(jù)流性質(zhì)的更多且更有價(jià)值的潛在模式。再如，在客戶關(guān)系管理系統(tǒng)中，管理公司利用數(shù)據(jù)流聚類算法嘗試挖掘新客戶群，或者更確切地說是否是現(xiàn)有客戶的行為進(jìn)行了轉(zhuǎn)移。

（3）實(shí)時(shí)聚類。某些關(guān)鍵的應(yīng)用領(lǐng)域?qū)Ψ答仌r(shí)間有著嚴(yán)格的要求。諸如事故檢測、航空交通控制等應(yīng)用領(lǐng)域必須實(shí)時(shí)給出數(shù)據(jù)流的聚類結(jié)果。雖然目前大多數(shù)的數(shù)據(jù)流聚類算法都已經(jīng)實(shí)現(xiàn)了用戶的聯(lián)機(jī)（在線）聚類查詢，但這些算法在時(shí)間上遠(yuǎn)遠(yuǎn)無法滿足實(shí)時(shí)應(yīng)用的需求。因此，構(gòu)建快速高效的實(shí)時(shí)數(shù)據(jù)流聚類算法亦是十分必要的研究方向。

（4）分布式數(shù)據(jù)流聚類。現(xiàn)實(shí)場景中，數(shù)據(jù)流數(shù)據(jù)的采集存在地理位置上的限制，因此分布式數(shù)據(jù)流聚類算法應(yīng)運(yùn)而生。在這類場景下，數(shù)據(jù)流聚類算法可與MapReduce 和分布式計(jì)算進(jìn)行結(jié)合，這將加快算法的速度，并處理有限的內(nèi)存問題。由于現(xiàn)在的存儲成本很低，可以僅存儲具有代表性的對象（如中心或概要）。通過存儲這些代表性對象可使最終用戶關(guān)注特定的時(shí)間段，并通過宏聚類或應(yīng)用其他數(shù)據(jù)挖掘算法進(jìn)一步分析匯總的數(shù)據(jù)。然而，許多數(shù)據(jù)聚類技術(shù)的并行化并不簡單，為了開發(fā)一些方法的分布式版本，需要大量的研究和理論分析，以提供新的方法。

（5）數(shù)據(jù)流概要。如何構(gòu)建數(shù)據(jù)流數(shù)據(jù)信息概要是一個(gè)重要的研究方向。到目前為止，數(shù)據(jù)流聚類最常見的概要是使用微聚簇及其變體。微聚簇通常創(chuàng)建凸形聚簇，而實(shí)際上聚簇可以以任何形狀出現(xiàn)，比如數(shù)據(jù)泡，在數(shù)據(jù)流場景下的“適應(yīng)”并不那么簡單。

（6）數(shù)據(jù)流算法評估。在數(shù)據(jù)流環(huán)境中，由于存在概念漂移、有限處理時(shí)間、驗(yàn)證延遲、多流結(jié)構(gòu)、刪失數(shù)據(jù)等問題，使得單一指標(biāo)度量動態(tài)變化的數(shù)據(jù)流環(huán)境的有效性較為困難。因此，更感興趣的是算法評估指標(biāo)如何隨著時(shí)間的推移而演變。