何 萍，姜玉麟，徐曉華，林惠惠，葛方毅，方 威，仁 祥

（揚(yáng)州大學(xué)信息工程學(xué)院，揚(yáng)州 225009）

聚類作為數(shù)據(jù)挖掘領(lǐng)域中一種非常有效的數(shù)據(jù)分析方式，其主要是將數(shù)據(jù)間相似度較高的數(shù)據(jù)樣本劃分到同一簇中，將相似度相差較大的劃分到不同的簇中。傳統(tǒng)的聚類算法往往在靜態(tài)數(shù)據(jù)的處理上具有良好的效果，但在實(shí)際問題的處理中，數(shù)據(jù)往往是隨時(shí)間的推移而變化的，通過聚類挖掘數(shù)據(jù)的演化機(jī)制，并且保證聚類結(jié)果在時(shí)間上盡可能平滑，即當(dāng)前時(shí)間快照上的聚類結(jié)果應(yīng)該與歷史快照上的聚類結(jié)果要盡可能地相似。

傳統(tǒng)的機(jī)器學(xué)習(xí)的基本假設(shè)是所有的數(shù)據(jù)都是獨(dú)立同分布的，不會隨著時(shí)間的推移而發(fā)生變化，也不會隨著時(shí)間的推移出現(xiàn)數(shù)據(jù)的增加或衰減的情況。比如在文本的挖掘、圖像的合成、分割等任務(wù)中，假設(shè)訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集的數(shù)據(jù)都是在一定的時(shí)間點(diǎn)，從一個(gè)概率分布中獨(dú)立地抽取得到的。然而在一些實(shí)際應(yīng)用問題的數(shù)據(jù)分布是隨著時(shí)間動態(tài)變化的，例如，在新聞、博客和BBS 等在線媒體中，人們討論的話題大多數(shù)都會隨著時(shí)間發(fā)生變化，即使對于同一個(gè)話題，一年前和當(dāng)前的內(nèi)容也不完全相同，這被稱為概念漂移［1］。

圖1 演示的是演化數(shù)據(jù)隨著時(shí)間的分布移動。圖1（a～d）分別是不同時(shí)刻的數(shù)據(jù)分布。從圖中可以看出，T1～T4時(shí)刻有3 個(gè)簇，分別用紅、綠、藍(lán)表示。隨著時(shí)間推移，圖1（b～d）中3 個(gè)簇的位置發(fā)生變化。由此可見，演化數(shù)據(jù)在時(shí)間的推移過程中，數(shù)據(jù)的位置分布和相互關(guān)系往往會發(fā)生變化。

圖1 演化數(shù)據(jù)示例Fig.1 Illustration of evolutionary data

傳統(tǒng)的聚類算法，如K 均值和譜聚類，處理的是靜態(tài)的數(shù)據(jù)，算法被要求在給定的數(shù)據(jù)集合上有盡可能好的聚類劃分。演化數(shù)據(jù)上的聚類是這樣一個(gè)學(xué)習(xí)任務(wù)：數(shù)據(jù)的分布隨時(shí)間而變化，在每一時(shí)刻，為演化的數(shù)據(jù)作出新的聚類劃分。

由于演化聚類處理的是隨時(shí)間動態(tài)變化的數(shù)據(jù)，且在每個(gè)時(shí)刻都要產(chǎn)生一個(gè)聚類結(jié)果，因此任何時(shí)刻的聚類結(jié)果不僅需要反映數(shù)據(jù)的分布，并且前后時(shí)刻的聚類結(jié)果要盡可能相似，即保持相鄰時(shí)刻聚類結(jié)果的平滑，不能出現(xiàn)較大的抖動。總體來說，現(xiàn)有的演化聚類算法主要有3 個(gè)目標(biāo)：首先，每一時(shí)刻上的數(shù)據(jù)聚類性能要盡可能好；其次，希望通過聚類發(fā)掘數(shù)據(jù)的演化機(jī)制，例如聚類的出現(xiàn)、分裂、消失等；最后，要充分利用歷史信息幫助提高聚類性能、保持聚類結(jié)果的時(shí)間平滑性能，從而挖掘數(shù)據(jù)的演化規(guī)律［1］。

演化聚類的研究收到了廣泛的關(guān)注，雖然已經(jīng)提出了許多方法，但大多數(shù)算法并沒有很好地考慮到數(shù)據(jù)在時(shí)序上的信息融合。Chakrabarti 等［2?4］通過修改標(biāo)準(zhǔn)K?means 的目標(biāo)函數(shù)，提出了演化K?means。Chi 等［5］將時(shí)序平滑思想引入譜聚類中，提出了PCQ（Preserving cluster quality）和PCM（Pre?serving cluster membership）兩種演化譜聚類框架。Lin 等［6］則是提出了一種分析動態(tài)社交網(wǎng)絡(luò)及其演化的概率生成模型，該模型從貝葉斯的角度解決了演化聚類的問題，其假設(shè)在一段時(shí)間內(nèi)社區(qū)的數(shù)目固定，采用迭代期望最大化算法的隨機(jī)分塊模型以及基于Dirchlet 分布的概率模型來捕捉演化規(guī)律。Tang 等［7］提出了一種新的演化聚類算法來分析動態(tài)網(wǎng)絡(luò)，通過不同類型的節(jié)點(diǎn)組成網(wǎng)絡(luò)，交替優(yōu)化進(jìn)行求解，但其計(jì)算成本較大。Folino 等［8?9］將演化譜聚類的問題定義為多目標(biāo)優(yōu)化問題，認(rèn)為其解是通過遺傳算法求解得到，但在研究演化數(shù)據(jù)的過程中，數(shù)據(jù)點(diǎn)的多樣性以及復(fù)雜性往往沒有得到充分考慮。因此，Rana 等［10］和Giulio 等［11］主要通過利用鄰域的方式，針對演化數(shù)據(jù)的動態(tài)性，對其演化的過程進(jìn)行預(yù)測。Xu 等［12?13］以及Yu 等［14］則是提出了進(jìn)化聚類框架，其能夠精確地跟蹤數(shù)據(jù)之間隨時(shí)間變化之間的相似性，并靜態(tài)聚類。Li 等［15］則是提出了一種演化協(xié)同聚類算法，其所涉及的優(yōu)化問題是非凸、非光滑和不可分離的。在上述的一些演化算法中，大多數(shù)不能很好地利用先驗(yàn)信息，只考慮相鄰時(shí)間節(jié)點(diǎn)或者節(jié)點(diǎn)的鄰域信息，認(rèn)為相鄰時(shí)刻的數(shù)據(jù)與當(dāng)前時(shí)刻數(shù)據(jù)存在一定的線性關(guān)系，并不能很好地反映數(shù)據(jù)的演化機(jī)制。

為了克服上述問題，本文提出一種基于時(shí)間平滑性的演化聚類框架，通過設(shè)定滑動窗口的大小，自適應(yīng)地尋找與當(dāng)前數(shù)據(jù)最為近似的歷史數(shù)據(jù)，而不是單純地考慮前一時(shí)刻的數(shù)據(jù)，從而對歷史數(shù)據(jù)進(jìn)行更為合理的利用；有機(jī)融合了基于靜態(tài)和基于時(shí)間序列的兩種相似度計(jì)算方法，其能夠較好地反映樣本點(diǎn)之間的關(guān)系；最后將框架應(yīng)用到譜聚類算法中，提出了兩種自適應(yīng)平滑的演化譜聚類算法ESC?PCQ（Evolutionary spectral clustering?pre?serving cluster quality）和ESC?PCM（Evolutionary spectral clustering?preserving cluster membership）。

1 相關(guān)工作

在演化數(shù)據(jù)的聚類問題上，最常見的方法就是采用傳統(tǒng)聚類的方式設(shè)計(jì)函數(shù)從而對每個(gè)時(shí)刻的數(shù)據(jù)進(jìn)行處理，隨后通過在代價(jià)函數(shù)上加入光滑正則項(xiàng)的方式來顯示數(shù)據(jù)的動態(tài)演化。該類方法側(cè)重于如何提高當(dāng)前時(shí)刻數(shù)據(jù)的聚類性能以及如何保持在聚類過程中的平滑性。

1.1 在線式框架

Chakrabarti 等［2］首先提出了一種泛化的在線式框架，并且將其應(yīng)用到了K?means 算法上得到演化K?means 算法。此框架包括兩個(gè)部分：快照聚類質(zhì)量和時(shí)間損失。在其所提出的演化聚類框架中，每一時(shí)刻t上的聚類任務(wù)可以視為以下目標(biāo)函數(shù)的最大化

式中：sq(Ct，Mt)衡量了算法在當(dāng)前時(shí)刻t數(shù)據(jù)上的聚類質(zhì)量；hc(Ct-1，Ct)則表示算法的時(shí)間損失；參數(shù)cp則為用戶自定義的，主要用于約束時(shí)間損失所占大小。

1.2 時(shí)間平滑的演化譜聚類

Chi 等［5］在進(jìn)化聚類的框架思想上，提出兩種結(jié)合時(shí)間平滑的演化譜聚類算法。這兩種算法將時(shí)間平滑度與演化聚類相結(jié)合。在“平滑假設(shè)”的基礎(chǔ)上進(jìn)一步擴(kuò)展，結(jié)合了圖分割的標(biāo)準(zhǔn)割思想與平均關(guān)聯(lián)。算法中代價(jià)函數(shù)的定義包括兩部分，傳統(tǒng)的聚類質(zhì)量代價(jià)和引入規(guī)范的時(shí)間平滑代價(jià)。其中，快照聚類質(zhì)量（CS），主要針對當(dāng)前數(shù)據(jù)特征度量聚類結(jié)果的聚類質(zhì)量，其中較高的快照代價(jià)意味著較差的聚類結(jié)果；時(shí)間損失（CT），根據(jù)聚類結(jié)果的擬合度，針對歷史數(shù)據(jù)特征或者歷史聚類結(jié)果，測量時(shí)間平滑度，其中，較高的時(shí)間代價(jià)意味著較差的時(shí)間平滑度?？偞鷥r(jià)函數(shù)定義為兩個(gè)代價(jià)的線性組合

式中：0 ≤α≤1 為用戶分配的參數(shù)，反映了用戶對聚類代價(jià)和時(shí)間代價(jià)的權(quán)衡。

兩種演化譜聚類算法的區(qū)別在于如何定義時(shí)間代價(jià)CT。第1 個(gè)算法為PCQ，它將當(dāng)前分區(qū)應(yīng)用于歷史數(shù)據(jù)，產(chǎn)生的群集質(zhì)量決定了時(shí)間代價(jià)。

它對式（2）中的CS 定義為多路標(biāo)準(zhǔn)割函數(shù)NC，然而在實(shí)際問題求解中屬于NP?hard［16］，因此采取寬松的方式進(jìn)行處理，其表達(dá)式為

因此，PCQ 算法的具體代價(jià)函數(shù)為

第2 個(gè)算法PCM，其快照聚類質(zhì)量與PCQ 保持一致，區(qū)別在于時(shí)間損失的構(gòu)造，主要通過比較當(dāng)前時(shí)刻的簇劃分與上一個(gè)時(shí)刻簇劃分的差異來決定時(shí)間代價(jià)，其代價(jià)函數(shù)主要為

由此可見，PCM 和PCQ 的差異主要體現(xiàn)在歷史代價(jià)的定義上，PCQ 將當(dāng)前時(shí)刻數(shù)據(jù)的簇劃分應(yīng)用到前一時(shí)刻的數(shù)據(jù)上來衡量聚類效果，而PCM 則是衡量前后兩個(gè)時(shí)刻簇劃分之間的差異度來作為演化聚類的時(shí)間代價(jià)。

2 時(shí)間平滑的演化譜聚類

2.1 問題引入

在Chakrabarti 等［2］所提出的在線式框架中，在時(shí)間損失上存在一定的局限性，它只考慮的是前一時(shí)刻的數(shù)據(jù)點(diǎn)對當(dāng)前時(shí)刻數(shù)據(jù)點(diǎn)的影響，假設(shè)數(shù)據(jù)的演化結(jié)構(gòu)是線性的，但在實(shí)際應(yīng)用中一些演化數(shù)據(jù)在t時(shí)刻受到影響最大的有可能不是它的前一時(shí)刻，而是更為久遠(yuǎn)的歷史數(shù)據(jù)。

如圖2 所示，截取電影中的4 個(gè)時(shí)間戳的視頻圖片，圖2（a）是主人公A 出現(xiàn)，圖2（b）為主人公B出現(xiàn)，圖2（c）是主人公A 和B 同時(shí)出現(xiàn)，圖2（d）則是主人公B 出現(xiàn)，可以發(fā)現(xiàn)圖2（d）聚類（或圖像分割）與前一時(shí)刻圖2（c）并沒有太大的關(guān)聯(lián)，反而與圖2（b）關(guān)聯(lián)性較強(qiáng)，即T4時(shí)刻與T2時(shí)刻的數(shù)據(jù)關(guān)聯(lián)性較強(qiáng)。

圖2 非線性演化數(shù)據(jù)示例Fig.2 Illustration of non?linear evolutionary data

因此在Chakrabarti 等人所提出的演化聚類框架中，并沒有有效地利用歷史時(shí)刻的聚類信息，且前一時(shí)刻的歷史時(shí)間代價(jià)也不盡可能小。

2.2 基本框架

給定數(shù)據(jù)集X= {X1，X2，…，XT}，其中Xt(Xt?X)表示t時(shí)刻所有的數(shù)據(jù)對象。在每個(gè)時(shí)刻t(1≤t≤T)，都有一個(gè)新的數(shù)據(jù)集Xt到達(dá)。假設(shè)這個(gè)數(shù)據(jù)集可以用一個(gè)n×n的矩陣Mt來表示每對數(shù)據(jù)間的相互關(guān)系。在每個(gè)時(shí)刻t，根據(jù)新的矩陣Mt和歷史信息得到時(shí)刻t的聚類結(jié)果Ct。

考慮到t時(shí)刻到達(dá)的數(shù)據(jù)，對其造成影響的可能不是t-1 時(shí)刻的數(shù)據(jù)，而是與之前的某一時(shí)刻t-k(k

式中：sq(Ct，Mt)主要指在當(dāng)前時(shí)間快照t上的聚類質(zhì)量，而hc(Ct-k，Ct)則表示當(dāng)前時(shí)間快照與回溯窗口范圍內(nèi)歷史快照上的數(shù)據(jù)之間的時(shí)間損失；參數(shù)η>0 則是由用戶自己定義的，其主要控制時(shí)間損失在目標(biāo)函數(shù)中的權(quán)重，而r則表示時(shí)間回溯范圍。

2.3 Mt 構(gòu)造

在所提出的在線式框架中，Mt相似度矩陣的計(jì)算主要包含兩個(gè)部分：基于當(dāng)前時(shí)刻的數(shù)據(jù)點(diǎn)間靜態(tài)相似度和基于時(shí)間序列的動態(tài)相似度。對于當(dāng)前時(shí)刻數(shù)據(jù)點(diǎn)的靜態(tài)相似度，計(jì)算過程只使用當(dāng)前時(shí)刻的信息而忽略其他的所有時(shí)刻信息；而后者則針對的是各個(gè)數(shù)據(jù)在隨時(shí)間演化規(guī)律上的相似性。

在每對數(shù)據(jù)之間的靜態(tài)相似度計(jì)算上，使用基于Bregman 散度的Itakura?Saito（IS）距離進(jìn)行計(jì)算。Bregman 散度［17］是一種類似于距離度量的方式，主要用于衡量兩者之間的差異大小。Bregman散度可以認(rèn)為是損失或者失真函數(shù)，考慮如下情況：假設(shè)點(diǎn)x是點(diǎn)y的失真或近似點(diǎn)，即可能通過對點(diǎn)y添加一些噪聲形成點(diǎn)x，損失函數(shù)的目的是度量點(diǎn)x近似點(diǎn)y導(dǎo)致的失真或者損失，其形式化定義如下。

給定一個(gè)嚴(yán)格凸函數(shù)Φ，由該函數(shù)生成的Bregman 散度為

式中：?Φ(y)為函數(shù)Φ在y點(diǎn)處的梯度，(x-y)為向量x和向量y的差；?Φ(y)，(x-y) 為?Φ(y)與(x-y)的內(nèi)積。

本文在衡量當(dāng)前時(shí)間快照與歷史快照之間的相似度St時(shí)，使用的是基于Bregman 散度的Itakura?Saito（IS）距離測度。

時(shí)間序列上的動態(tài)相似度計(jì)算定義了一個(gè)改進(jìn)的時(shí)間序列相關(guān)系數(shù)，具體為

式中θ表示時(shí)間序列之間的相似度在目標(biāo)函數(shù)中所占比重。

2.4 ESC 算法

將上述框架結(jié)合譜聚類，得到兩種演化譜聚類（Evolutionary spectral clustering，ESC）算法，分別是ESC?PCQ 和ESC?PCM。在ESC?PCQ 中通過衡量當(dāng)前時(shí)刻的簇劃分應(yīng)用到前r個(gè)時(shí)刻的歷史數(shù)據(jù)上的最佳聚類效果來確定時(shí)間代價(jià)，而ESC?PCM 則是通過衡量當(dāng)前時(shí)刻的簇劃分與用前r個(gè)時(shí)刻的歷史數(shù)據(jù)的最小差異來確定時(shí)間代價(jià)。

2.4.1 基于PCQ 的演化譜聚類

然后，將找到k*所對應(yīng)的前c個(gè)最大特征值所對應(yīng)的特征向量記為Ut=Ut(k*)，通過對Ut進(jìn)行行歸一化，能夠?qū)㈨旤c(diǎn)的簇指示矩陣的行向量投影到一個(gè)單位超球面上

ESC?PCQ 的具體算法框架如算法1 所示。

2.4.2 基于PCM 的演化譜聚類

在基于PCM 的算法框架中，主要考慮到當(dāng)前時(shí)刻的數(shù)據(jù)與歷史時(shí)刻數(shù)據(jù)的差異，需要計(jì)算t時(shí)刻的簇劃分Ut與t-k時(shí)刻的簇劃分Ut-k之間的距離，進(jìn)而構(gòu)造自適應(yīng)的時(shí)間損失，因此構(gòu)造距離dist(Ut，Ut-k)函數(shù)，其具體形式為

因此基于PCM 的演化譜聚類算法的目標(biāo)函數(shù)為

ESC?PCM 的具體算法如算法2 所示。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證兩種ESC 算法的聚類性能，在真實(shí)數(shù)據(jù)集上，通過比對標(biāo)準(zhǔn)譜聚類、演化K?means 以及演化譜聚類算法，驗(yàn)證算法的聚類性能。在參數(shù)的設(shè)置上，令η=0.125，r=6。

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

第1 個(gè)驗(yàn)證數(shù)據(jù)集是Iris 數(shù)據(jù)集。由于Iris 數(shù)據(jù)集樣本數(shù)較少，因此在初始時(shí)刻后的數(shù)據(jù)是通過對原始數(shù)據(jù)添加隨機(jī)噪聲所產(chǎn)生的二維數(shù)據(jù)集，并分配到10 個(gè)不同的時(shí)刻進(jìn)行模擬演化，噪聲分布滿足N(0，0.5)。Iris 數(shù)據(jù)集是鳶尾花的特征數(shù)據(jù)集，一共有150 個(gè)樣本數(shù)據(jù)，每個(gè)樣本的屬性分別為鳶尾花萼片的長與寬以及花瓣的長與寬。

第2 個(gè)驗(yàn)證數(shù)據(jù)集是MNIST 數(shù)據(jù)集，是由數(shù)字0～9 的手寫數(shù)字構(gòu)成的字符數(shù)據(jù)集（圖3）。MNIST 數(shù)據(jù)集有784 維，共分為10 類。 從MNIST 數(shù)據(jù)集的每個(gè)類中隨機(jī)選取600 個(gè)樣本，并把數(shù)據(jù)隨機(jī)分配成10 等份，分配到10 個(gè)不同的時(shí)刻進(jìn)行模擬演化。因此每個(gè)時(shí)刻的樣本有600個(gè)，屬于10 個(gè)類別。

圖3 MNIST 部分?jǐn)?shù)據(jù)樣本示例Fig.3 Illustration of data samples in MNIST dataset

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

采用了3 種評價(jià)標(biāo)準(zhǔn)來衡量算法性能?？煺站垲愘|(zhì)量衡量當(dāng)前時(shí)間片的聚類質(zhì)量。

時(shí)間損失衡量當(dāng)前時(shí)間片的聚類結(jié)果與歷史時(shí)間的聚類結(jié)果的差距，時(shí)間損失越小越好。

式中f表示將t時(shí)刻的簇心映射到t-k時(shí)刻簇心的函數(shù)。

NMI（Normalized mutual information）是歸一化互信息，NMI 值越大，聚類質(zhì)量越高。

式中：I(X，Y)表示隨機(jī)變量X和Y之間的互信息，而H(?)表示隨機(jī)變量的熵。

3.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境采用的是1 臺Intel Core i3 M 390 2.67 GHz，RAM 4 GB 的計(jì)算機(jī)，所有實(shí)驗(yàn)在Win?dows 7 系統(tǒng)的Matlab R2019a 環(huán)境下執(zhí)行。

圖4～6 給出了在Iris 數(shù)據(jù)集上快照聚類質(zhì)量、時(shí)間損失和NMI 的性能比較，其中橫軸表示時(shí)間戳T1到T10，從圖中可以看出，本文所提出的2 種ESC 算法的快照聚類質(zhì)量和NMI 高于其他算法，且時(shí)間損失也較小。

圖4 Iris 數(shù)據(jù)集快照聚類質(zhì)量的比較Fig.4 Comparison of snapshots quality on Iris dataset

圖5 中在T5時(shí)刻之后，兩種ESC 算法在時(shí)間損失上與前一時(shí)刻沒有較大變化。而演化K?means 和演化譜聚類算法則有較大的起伏，這是因?yàn)檫@兩種算法在目標(biāo)函數(shù)的構(gòu)造上只與前一時(shí)刻比較，當(dāng)其分布并不與歷史時(shí)刻分布一致時(shí)容易出現(xiàn)較大的抖動。

圖5 Iris 數(shù)據(jù)集時(shí)間損失的比較Fig.5 Comparison of history cost on Iris dataset

圖7～9 分別為在MNIST 數(shù)據(jù)集上的快照聚類質(zhì)量、時(shí)間損失以及NMI 度量指標(biāo)的實(shí)驗(yàn)結(jié)果。從圖可知，本文提出的兩種ESC 算法整體而言在對演化數(shù)據(jù)的聚類問題上聚類的質(zhì)量較高且時(shí)間損失較低，其中ESC?PCM 因?yàn)楦鼈?cè)重于時(shí)間損失比ESC?PCQ 更低一些，但快照聚類質(zhì)量卻相當(dāng)。

圖7 MNIST 數(shù)據(jù)集快照聚類質(zhì)量的比較Fig.7 Comparison of snapshots quality on MNIST dataset

圖6 Iris 數(shù)據(jù)集NMI 的比較Fig.6 Comparison of NMI on Iris dataset

圖8 MNIST 數(shù)據(jù)集時(shí)間損失的比較Fig.8 Comparison of history cost on MNIST dataset

圖9 MNIST 數(shù)據(jù)集NMI 的比較Fig.9 Comparison of NMI on MNIST dataset

為了討論不同參數(shù)對算法性能的影響，以ESC?PCM 算法為例，在Iris 數(shù)據(jù)集上分析回溯范圍的參數(shù)r以及時(shí)間損失權(quán)重參數(shù)η對于NMI 指標(biāo)的影響。從圖10～11 可以看出，在回溯范圍參數(shù)r=0 時(shí)，即不設(shè)置回溯范圍，聚類的性能較低，而隨著r值的不斷增大，聚類的性能不斷增長而逐漸持平，但隨著r值范圍逐漸覆蓋到數(shù)據(jù)的全部時(shí)間，其計(jì)算成本較高，且聚類性能提升不大。另外，在約束時(shí)間損失的參數(shù)η的設(shè)置上，如果設(shè)置時(shí)間損失的權(quán)重過大（如η=0.25，0.5），其聚類的性能反而會降低。由此可見，本文采用的r=6，η=0.125 是一組性能較好的參數(shù)設(shè)置。

圖10 參數(shù)r 對性能的影響Fig.10 Influence of parameter r on performance

圖11 參數(shù)η 對性能的影響Fig.11 Influence of parameter η on performance

4 結(jié)論

本文主要針對演化數(shù)據(jù)的聚類問題，提出了自適應(yīng)時(shí)間平滑的演化譜聚類。考慮當(dāng)前時(shí)刻的簇劃分與前r個(gè)時(shí)刻的歷史數(shù)據(jù)存在一定的關(guān)聯(lián)，對時(shí)間回溯窗口進(jìn)行設(shè)定，自適應(yīng)地尋找與當(dāng)前快照最為相關(guān)的歷史快照。在相似度矩陣的構(gòu)造上有機(jī)融合了基于IS 的靜態(tài)相似度以及基于時(shí)間序列的動態(tài)相似度，并結(jié)合譜聚類提出了兩種自適應(yīng)平滑的演化譜聚類算法ESC?PCQ 和ESC?PCM。兩種算法相較于其他演化聚類算法，在聚類效果上更好且更為平滑。然而，如果設(shè)定較大的時(shí)間回溯范圍，會導(dǎo)致計(jì)算代價(jià)變高。因此，如何在保持或者降低時(shí)間代價(jià)的基礎(chǔ)上進(jìn)一步提高演化聚類的性能，將是下一步研究的工作重點(diǎn)。