張寶杰，余 濤，王 玉，陳斯羽

（西安石油大學(xué)計(jì)算機(jī)學(xué)院，西安 710065）

0 引言

物聯(lián)網(wǎng)（IoT）技術(shù)，智能手機(jī)和社交媒體服務(wù)的廣泛使用產(chǎn)生了大量的高速數(shù)據(jù)流，比如，實(shí)時(shí)監(jiān)控系統(tǒng)產(chǎn)生的數(shù)據(jù)，相機(jī)的圖像序列（視頻）數(shù)據(jù)，或社交媒體流的文本輸入，等等［1］。在面對以上應(yīng)用場景時(shí)，如何快速對這些數(shù)據(jù)流進(jìn)行分析和處理成為首要任務(wù)。聚類通常被用于對數(shù)據(jù)進(jìn)行快速探索性數(shù)據(jù)分析。然而傳統(tǒng)的聚類方法在處理流數(shù)據(jù)時(shí)會面臨兩個問題：①提取有效信息效率低；②要占用大量設(shè)備內(nèi)存。如何使用聚類方法從流數(shù)據(jù)中提取有用的信息成為研究熱點(diǎn)。

流數(shù)據(jù)聚類方法解決了傳統(tǒng)的聚類方法在處理流數(shù)據(jù)上出現(xiàn)的問題。常見流數(shù)據(jù)聚類的具體實(shí)現(xiàn)過程如下：

（1）面對流數(shù)據(jù)M={m1,m2,…,mn}，使用窗口模型對數(shù)據(jù)進(jìn)行分割，獲得K組數(shù)據(jù)塊；

（2）對第一組數(shù)據(jù)塊使用聚類方法進(jìn)行聚類，獲取聚類信息；

（3）提取當(dāng)前的聚類信息；

（4）結(jié)合（3）中獲取的聚類信息以及第i（1＜i＜K）塊數(shù)據(jù)，重新進(jìn)行聚類，獲得聚類結(jié)果；

（5）重復(fù)（3）、（4）步驟，直到i=K，輸出聚類結(jié)果。

本文首先介紹流數(shù)據(jù)聚類中的基本概念，其次對流數(shù)據(jù)聚類算法進(jìn)行分類，依據(jù)分類分別介紹了當(dāng)前存在的流數(shù)據(jù)聚類算法，在第三節(jié)主要介紹流數(shù)據(jù)聚類實(shí)驗(yàn)中常用的應(yīng)用及衡量標(biāo)準(zhǔn)，最后對流數(shù)據(jù)聚類進(jìn)行總結(jié)和展望。

1 基本概念

1.1 聚類

聚類是一種典型的無監(jiān)督學(xué)習(xí)方式，能夠?qū)⒕哂邢嗨菩缘臄?shù)據(jù)劃分為一組。通常被用于進(jìn)行快速探索性數(shù)據(jù)分析。假設(shè)有N個對象的集合M={m1,m2,…,mn}，那么將這N個對象依據(jù)某種特征劃分為k∈{2,3,…,N-1}個子集，其中每個m由一個p維特征向量定義，xi∈Rp在X={x1,x2,…,xn}∈Rp集合中。這樣的過程被稱為聚類。

1.2 窗口模型

流數(shù)據(jù)在理論上是一組大量、連續(xù)沒有邊界的數(shù)據(jù)序列［2］。當(dāng)前流數(shù)據(jù)聚類檢測主要面臨兩個問題：①存儲挑戰(zhàn)。由于數(shù)據(jù)點(diǎn)不斷到達(dá)，序列理論上是無窮無盡的，因此從一開始就將整個流存儲在內(nèi)存中是不可行的。②效率問題。在實(shí)際應(yīng)用中需要立刻對當(dāng)前的數(shù)據(jù)進(jìn)行分析并得出聚類結(jié)果［3］。研究表明，在流數(shù)據(jù)中使用窗口模型將整個數(shù)據(jù)切割，只處理最新到達(dá)的數(shù)據(jù)對象比處理全部數(shù)據(jù)更有效，而且該方法對內(nèi)存需求量少，能夠加快分析效率。當(dāng)前有四種主要的窗口模型（如圖1所示），分別是阻尼窗口模型（damped window model）、地標(biāo)窗口模型（landmark window model）、滑動窗口模型（sliding window model）和傾斜窗口模型（tilted window model）。

圖1 常用流數(shù)據(jù)窗口模型

阻尼窗口模型：該模型為每一個對象分配權(quán)重，通過設(shè)置衰減函數(shù)或衰減因子，使最新到達(dá)的對象獲得盡可能大的權(quán)重，隨著時(shí)間變化，該權(quán)重會逐漸下降。地標(biāo)窗口模型：該模型主要通過在流數(shù)據(jù)中設(shè)置聚類的起始點(diǎn)，從起始點(diǎn)開始進(jìn)行聚類?；瑒哟翱谀Ｐ停夯瑒哟翱谀Ｐ椭饕ㄟ^設(shè)置一個固定長度的窗口m，從t1時(shí)間開始，只有最近的m個數(shù)據(jù)對象被拿來進(jìn)行聚類。傾斜窗口模型：該模型能夠在整個窗口期保存主要的信息［4-6］。

2 方法概述

依據(jù)傳統(tǒng)（批處理）聚類算法的分類對流數(shù)據(jù)聚類進(jìn)行分類，主要可以分為五個類別：層次聚類、分區(qū)聚類、密度聚類、網(wǎng)格聚類和模型聚類［7］。依據(jù)流數(shù)據(jù)方法實(shí)現(xiàn)可主要分為三大類：數(shù)據(jù)匯總聚類［8-10］、在線（實(shí)時(shí)）聚類、時(shí)間序列聚類［11-12］。其分類結(jié)果如圖2所示。在本文中，主要依據(jù)傳統(tǒng)分類方法對當(dāng)前提出的流數(shù)據(jù)方法進(jìn)行介紹。

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

2.1 基于層次的流數(shù)據(jù)聚類方法

流數(shù)據(jù)層次聚類方法核心和層次聚類方法類似，主要基于二叉樹的數(shù)據(jù)結(jié)構(gòu)。基于層次的流數(shù)據(jù)聚類方法的優(yōu)點(diǎn)是不需要提前預(yù)估計(jì)數(shù)據(jù)中存在的簇，可以根據(jù)自己的需要直接切割從而獲得聚類結(jié)果，同時(shí)基于層次聚類能夠輸出當(dāng)前流數(shù)據(jù)塊的樹狀結(jié)構(gòu)圖。然而基于層次的流數(shù)據(jù)聚類方法時(shí)間復(fù)雜度比較高，此外還容易受到異常值的影響。

ODAC方法是Rodrigues等［12］提出的時(shí)間流數(shù)據(jù)的層次聚類方法，該方法使用樹結(jié)構(gòu)來更新流數(shù)據(jù)中簇的變化。通過對聚類的質(zhì)量進(jìn)行測量，將同一簇對象之間的最大不相似度定義為簇的直徑。但是由于層次聚類自身在添加或刪除葉子節(jié)點(diǎn)時(shí)需要對樹結(jié)構(gòu)進(jìn)行調(diào)整，所以會導(dǎo)致時(shí)間復(fù)雜度變高。Udommanetanakit等［13］在2007年提出E-Stream方法，該方法用一種新的聚類表示方法和距離函數(shù)來改進(jìn)流聚類算法，它是基于進(jìn)化的流聚類方法，支持出現(xiàn)、消失、自進(jìn)化、合并和分裂等不同類型的聚類結(jié)構(gòu)演化。對于一組數(shù)據(jù)M={m1,m2,…,mn}，最初時(shí)將每次輸入的一個mi看作是一個對象，當(dāng)?shù)趍in個對象到達(dá)時(shí)，如果A={mi1,mi2,…}的密度足夠大，那么A就是一個簇。因此，該方法根據(jù)相似度評分將新到達(dá)的對象分配給一個簇，否則可以將數(shù)據(jù)歸類為孤立的數(shù)據(jù)。Meesuksabai等［14］在2011年提出HUE-Stream方法，該方法解決了E-Stream方法在異構(gòu)數(shù)據(jù)上出現(xiàn)的不確定性問題，并且能夠針對不同類型的聚類結(jié)構(gòu)進(jìn)行演化。

2.2 基于分區(qū)的流數(shù)據(jù)聚類方法

在批處理聚類中，常見的分區(qū)聚類方法典型代表就是K-means方法。假設(shè)有限數(shù)據(jù)集M={m1,m2,…,mn}中有K個簇，設(shè)置初始的聚類簇中心K={K1,K2,…,KK}，DiK是每個對象到Ki的距離，i={1,2,…,K}；據(jù)此將每個對象分配給具有min{DiK}的簇，找出該組數(shù)據(jù)劃分為MK1={mi1,mi2,…,mib},…,MKK={mic,mic+1,…,mn}，更新簇中心?；诜謪^(qū)的流數(shù)據(jù)聚類方法大部分是在基于分區(qū)的批處理方法上面進(jìn)行擴(kuò)展，它的優(yōu)點(diǎn)是易于實(shí)現(xiàn)，易于理解，但是基于分區(qū)的流數(shù)據(jù)聚類方法需要預(yù)估計(jì)當(dāng)前數(shù)據(jù)對象中存在簇的個數(shù)，如果預(yù)估計(jì)的簇少于實(shí)際存在的簇的個數(shù)，這將會導(dǎo)致出現(xiàn)無效聚類。

基于分區(qū)的相關(guān)流數(shù)據(jù)聚類算法有SWClustering［15］，Streamkm++［16］，Adaptive Stream Kmeans［17］，F(xiàn)EAC-Stream［18］等。SWClustering方法通過使用滑動窗口和聚類特征指數(shù)直方圖（exponential histogram of cluster feature,EHCF）來維護(hù)流數(shù)據(jù)中簇的特性，因此該方法能夠獲得最近窗口中簇的分布及其演化過程，能夠根據(jù)選擇的樣本集合計(jì)算出聚類結(jié)果［19］。Streamkm++是K-means++［20］算法對數(shù)據(jù)流聚類的擴(kuò)展，是K-means算法的擴(kuò)展，該方法能夠在流數(shù)據(jù)上取得很好的聚類結(jié)果。Puschmann等［17］提出Adaptive Stream K-means方法，該方法是一種基于在線分區(qū)的流數(shù)據(jù)聚類算法，Puschmann指出該方法克服了基于分區(qū)的流聚類方法需要預(yù)先確定K以及難適應(yīng)輸入數(shù)據(jù)中概念漂移的問題。該方法的一個局限性是需要對當(dāng)前數(shù)據(jù)中存在的簇進(jìn)行估計(jì)，預(yù)估計(jì)的簇?cái)?shù)量會直接影響到聚類結(jié)果。de Andrade Silva等［18］提出基于kmeans算法的FEAC-Stream聚類方法，該方法通過使用進(jìn)化方法來自動估計(jì)K值。FEACStream是完全在線的方法，使用Page-Hinkley（PH）［21］評價(jià)當(dāng)前算法聚類結(jié)果的質(zhì)量，通過Page-Hinkley（PH）評價(jià)方法能夠協(xié)助FEACStream聚類方法自行調(diào)整到最優(yōu)策略，能夠直接維護(hù)最終的聚類結(jié)果。Clustream方法提出了在線-離線框架，使用傾斜窗口模型，在線通過微簇結(jié)構(gòu)來獲取并維護(hù)流數(shù)據(jù)的樣本信息，在離線階段，基于在線階段總結(jié)的樣本信息產(chǎn)生聚類結(jié)果［22］。Clustream方法能夠應(yīng)用于各種復(fù)雜的情況并產(chǎn)生較好的聚類結(jié)果。然而該方法并沒有區(qū)分出過期數(shù)據(jù)與近期數(shù)據(jù)的差異性權(quán)重，因此在高維數(shù)據(jù)上聚類性能會變差。

2.3 基于密度的流數(shù)據(jù)聚類方法

基于密度的流數(shù)據(jù)聚類方法具有任意形狀簇的噪聲魯棒性，它通過計(jì)算數(shù)據(jù)之間的密度，從密度低的區(qū)域進(jìn)行切割，將密度高的區(qū)域劃分為一個簇［23］。然而該方法在面對具有多種密度的簇的情況下，大部分基于密度的流數(shù)據(jù)聚類方法難以獲得滿意的聚類結(jié)果。

Cao等［10］提出DenStream算法，該方法采用了在線-離線原理。在線階段主要通過使用一種“密集”簇（core-micro-cluster）的方法對當(dāng)前流數(shù)據(jù)中的簇進(jìn)行歸納，并維護(hù)和區(qū)分潛在的簇和異常點(diǎn)。在離線階段通過利用在線階段獲得的結(jié)論進(jìn)行聚類，從而獲得聚類結(jié)果。MuDi-Stream［23］方法解決了當(dāng)流數(shù)據(jù)中簇具有多密度情況時(shí)，基于密度的流數(shù)據(jù)聚類表現(xiàn)效果急劇下降的問題。使用基于在線-離線框架的流數(shù)據(jù)聚類方法，在線階段通過采用基于網(wǎng)格的方法，獲得以核心小集群的形式保存的多密度流數(shù)據(jù)的匯總樣本，在離線階段通過DBSCAN的擴(kuò)展方法計(jì)算聚類結(jié)果。然而該方法沒有解決歷史數(shù)據(jù)樣本與當(dāng)前數(shù)據(jù)之間關(guān)系的問題。Chenaghlou等［3］提出了一種考慮觀測時(shí)間接近性和空間接近性，以實(shí)時(shí)識別異常的算法（online clustering anomaly detection，OnCAD）。該方法不能直觀展示當(dāng)前數(shù)據(jù)中的簇結(jié)構(gòu)，因此在亂序數(shù)據(jù)集上表現(xiàn)較差。Fahy等［24］提出了一種基于生物的在線聚類動態(tài)數(shù)據(jù)流的方法——蟻群流聚類（ACSC）算法，該方法極大提高了算法的聚類效率。Tareq等［25］提出了基于自適應(yīng)切比切夫距離（CEC）的進(jìn)化數(shù)據(jù)流聚類，該方法是一種基于密度的在線聚類算法，它解決了聚類質(zhì)量受距離函數(shù)（distance）影響這一問題，當(dāng)使用距離函數(shù)時(shí)，會導(dǎo)致聚類結(jié)果降低。DFPSclustering（the dynamic FPS-clustering algorithm）該算法引入基于密度的目標(biāo)函數(shù)，采用適應(yīng)度比例共享策略對聚類中心進(jìn)行更有效的搜索，該方法能夠應(yīng)用于社交媒體分析、股票市場預(yù)測和網(wǎng)絡(luò)入侵檢測等領(lǐng)域，其缺點(diǎn)是計(jì)算成本略高［26］。

2.4 基于網(wǎng)格的流數(shù)據(jù)聚類

基于網(wǎng)格的流數(shù)據(jù)聚類方法基于網(wǎng)格聚類模型。首先使用網(wǎng)格對數(shù)據(jù)空間進(jìn)行分割，將數(shù)據(jù)對象映射到網(wǎng)格單元［27］。獲取網(wǎng)格單元之間的密度，從密度低的區(qū)域進(jìn)行切割，獲得一組密度大于周圍網(wǎng)格單元的連接網(wǎng)格單元，這樣獲得的簇被稱為網(wǎng)格簇。單元格的密度被定義為當(dāng)前單元格中點(diǎn)的密度，在流數(shù)據(jù)中單元格能夠保存流數(shù)據(jù)的歷史信息，同時(shí)在流數(shù)據(jù)聚類中需要在線對單元格信息進(jìn)行更新。然而在網(wǎng)格單元上進(jìn)行聚類需要耗費(fèi)大量的時(shí)間。

潘登等［28］提出一種能夠并行處理數(shù)據(jù)和便于增量計(jì)算的智能聚類方法，該方法主要結(jié)合徑向基函數(shù)（radial basis function，RBF）和網(wǎng)格劃分，實(shí)現(xiàn)了流數(shù)據(jù)聚類。張東月等［29］依據(jù)在線-離線模式提出了一種基于網(wǎng)格耦合的流數(shù)據(jù)聚類方法。在線階段主要實(shí)現(xiàn)對數(shù)據(jù)映射，以及對網(wǎng)格進(jìn)行更新、添加和刪除的操作。在離線階段進(jìn)行聚類操作獲得流數(shù)據(jù)的聚類結(jié)果。

2.5 基于模型的流數(shù)據(jù)聚類方法

基于模型的流數(shù)據(jù)聚類方法主要是通過找到最適合輸入數(shù)據(jù)的數(shù)據(jù)分布模型，從而利用該模型進(jìn)行聚類來獲得聚類結(jié)果，該方法具有噪聲穩(wěn)定性。其中SWEM方法就是一種基于模型的流數(shù)據(jù)聚類方法［30-31］。

此外，AutoCloud聚類方法是一種基于典型和偏心數(shù)據(jù)分析的在線數(shù)據(jù)流聚類進(jìn)化方法［32］,它基于最近引入的典型性和偏心數(shù)據(jù)分析的概念，主要用于異常檢測任務(wù)。evoStream［33］算法能夠利用流中的空閑時(shí)間來增量地提高聚類結(jié)果。

3 評價(jià)指標(biāo)及應(yīng)用

3.1 評價(jià)指標(biāo)

當(dāng)前流數(shù)據(jù)聚類方法大多分為在線-離線方案，通過離線實(shí)現(xiàn)聚類并輸出聚類結(jié)果。因此在大部分論文中，依舊采用和批處理聚類一樣的評價(jià)指標(biāo)。在批處理聚類方法上，其評價(jià)指標(biāo)可以分為兩類：內(nèi)部評價(jià)指標(biāo)和外部評價(jià)指標(biāo)。內(nèi)部指標(biāo)是無監(jiān)督的，主要是通過計(jì)算對象與簇中心的距離來衡量聚類結(jié)果的好壞。其中常用的內(nèi)部指標(biāo)有戴維森堡丁指數(shù)（Daviesbouldin index，DBI）、鄧恩指數(shù)（Dunn validity index，DVI）、輪廓系數(shù)（silhouette coefficient）［34］。常用的外部指標(biāo)有標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）、調(diào)整互信息（adjusted mutual information，AMI）、局部精度（partation accuracy，PA）等。

調(diào)整互信息的計(jì)算如下：

其中，E{M I(U,V)}為互信息M I(U,V)的期望，其計(jì)算方法如下：

其中k=(ai+bj-N)+為max(1,ai+bj-N)；ai和bj分別為列聯(lián)表M的第i行和第j列和，具體為：

3.2 實(shí)際應(yīng)用

表1舉例了四種流數(shù)據(jù)聚類方法及其應(yīng)用。

表1 流數(shù)據(jù)方法及應(yīng)用

Peixoto等［35］提出一個應(yīng)用于車載自組織網(wǎng)絡(luò)（vehicular ad-hoc networks，VANETs）的流數(shù)據(jù)聚類框架，該框架定義了兩種減少交通數(shù)據(jù)流的方法：其中之一為普通的交通擁塞檢測方法——基線方法，并通過實(shí)驗(yàn)表明該方法能夠有效降低通信成本，為VANETs的發(fā)展帶來顯著成果。textClust［36］實(shí)現(xiàn)了文本流的聚類算法，該方法通過使用兩階段聚類方法來識別和跟蹤文本流中的主題。GMMSEQ［34］是一種能夠用于管理附加在聲發(fā)射信號上的連續(xù)時(shí)間戳的聚類算法。在聚類過程中利用時(shí)間戳，使人們能夠獲得對聲發(fā)射數(shù)據(jù)流的信息。Hassan等［37］對進(jìn)化聚類算法（ECA*）進(jìn)行改進(jìn)，稱為iECA*。該方法能夠用于COVID-19和醫(yī)療疾病數(shù)據(jù)集的實(shí)際應(yīng)用。

4 結(jié)語

本文主要對流數(shù)據(jù)聚類方法進(jìn)行分類和總結(jié)，從層次聚類、分區(qū)聚類、密度聚類、網(wǎng)格聚類和模型聚類五個方面分別介紹了幾種流數(shù)據(jù)聚類方法，并對這五個大類的流數(shù)據(jù)聚類方法普遍存在的優(yōu)缺點(diǎn)進(jìn)行分析，介紹了近幾年提出的流數(shù)據(jù)聚類方法；對當(dāng)前常用的流數(shù)據(jù)聚類指標(biāo)做了簡要的介紹，并介紹了一些實(shí)際應(yīng)用場景。