數(shù)據(jù)流聚類(lèi)算法研究

朱穎雯，陳松燦

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

引 言

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

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

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

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

1 問(wèn)題描述

1.1 數(shù)據(jù)流聚類(lèi)

設(shè)數(shù)據(jù)流DS={x1，x2，…，xn}（n的取值可以無(wú)限大）為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ù)聚類(lèi)相比數(shù)據(jù)流聚類(lèi)具有以下不同。

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

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

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

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

定義1概念。產(chǎn)生數(shù)據(jù)流的過(guò)程可以被考慮為在隨機(jī)變量Y和X={X1，…，Xn}上的聯(lián)合分布，這里y∈dom(Y)表示類(lèi)別標(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ù)聚類(lèi)的結(jié)果通常是精確的，但數(shù)據(jù)流聚類(lèi)一般只能得到近似結(jié)果。

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

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

1.2 時(shí)間窗口

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

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

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

界標(biāo)窗口根據(jù)事件將數(shù)據(jù)流分割成不連貫的塊。從開(kāi)始時(shí)刻1 到當(dāng)前時(shí)刻tc的數(shù)據(jù)，記為W[1，tc]，即界標(biāo)到達(dá)后的所有數(shù)據(jù)點(diǎn)都同樣重要，沒(méi)有過(guò)去和現(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）滑動(dòng)窗口

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

（3）衰減窗口

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

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

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

1.3 計(jì)算方法

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

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

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

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

1.4 流聚類(lèi)評(píng)估方法

為了對(duì)各種數(shù)據(jù)流聚類(lèi)算法的精度進(jìn)行評(píng)估，常用以下3 項(xiàng)評(pí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 越大表明聚類(lèi)精度越高。

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

歸一化互信息NMI 是量化兩個(gè)分布之間共享統(tǒng)計(jì)信息的對(duì)稱(chēng)策略。當(dāng)聚簇標(biāo)簽和真實(shí)樣本類(lèi)別一對(duì)一映射時(shí)，NMI 值得到最大值1。給定真實(shí)聚簇A={A1，A2，…，Ak} 和某聚類(lèi)算法得到的聚簇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ù)對(duì)，其中n為數(shù)據(jù)集中樣本個(gè)數(shù)，P1、P2表示兩種聚類(lèi)算法，n1為數(shù)據(jù)對(duì)（xi，xj）在P1、P2中劃分為同一類(lèi)的數(shù)據(jù)對(duì)數(shù)，n00則為（xi，xj）隸屬不同類(lèi)的數(shù)據(jù)對(duì)數(shù)，RI 計(jì)算如下

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

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

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

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

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

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

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

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

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

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

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

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

2.2 CluStream 算法

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

2.3 DenStream 算法

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

在線(xiàn)階段每個(gè)潛在微聚簇都具有1 個(gè)相關(guān)的權(quán)值w表示其基于時(shí)間的重要性。通過(guò)衰減函數(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)相對(duì)于核心微聚簇的閾值（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)重，以保證能夠識(shí)別出真正的孤立點(diǎn)。然而，當(dāng)刪除1 個(gè)微聚簇或合并2 個(gè)舊的微聚簇時(shí)，不釋放分配的內(nèi)存單元，以及刪除孤立點(diǎn)的剪枝過(guò)程相當(dāng)耗時(shí)，這是DenStream 算法的不足。離線(xiàn)階段將在線(xiàn)階段發(fā)現(xiàn)的潛在微聚簇傳遞到DBSCAN 算法，以確定最終的聚類(lèi)結(jié)果。

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

2.4 ACSC 算法

ACSC 蟻群流聚類(lèi)算法［34］提供一種對(duì)非平穩(wěn)聚簇進(jìn)行總結(jié)的流聚類(lèi)方法，同時(shí)解決聚簇個(gè)數(shù)變化問(wèn)題。該算法使用采樣解決數(shù)據(jù)流聚類(lèi)的速度要求，點(diǎn)與聚簇的相似性評(píng)估僅使用這個(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)被分配到各自的聚簇之后，才會(huì)創(chuàng)建微聚簇。每個(gè)點(diǎn)被轉(zhuǎn)換為1 個(gè)微聚簇，這些微聚簇只嘗試與同一聚簇中的其他點(diǎn)合并，合并操作代價(jià)高。

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

2.5 D-Stream 算法

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

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

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

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

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

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

2.6 RPGStream 算法

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

JL 引理［37］是隨機(jī)投影的理論依據(jù)，即高維歐氏空間的點(diǎn)映射到低維空間，相對(duì)距離可得到一定誤差范圍內(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行。

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

從式（8）看出，理論上JL 界（k0）不依賴(lài)于原始空間的維度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投影到對(duì)應(yīng)的dc維（dc?d）點(diǎn)yi。從而整個(gè)數(shù)據(jù)流DSn×d={x1，x2，…，xn}被投影到{y1，y2，…，yn}，再對(duì)使用G-Stream 算法進(jìn)行聚類(lèi)。RPGStream 生成了包含一系列神經(jīng)元節(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)的權(quán)值向量為。

3 軟件與工具

數(shù)據(jù)流聚類(lèi)在實(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ù)處理、回歸、分類(lèi)、聚類(lèi)和關(guān)聯(lián)規(guī)則等1 組學(xué)習(xí)算法。

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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