自適應時間平滑的演化譜聚類

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

（揚州大學信息工程學院，揚州 225009）

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

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

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

圖1 演化數據示例Fig.1 Illustration of evolutionary data

傳統的聚類算法，如K 均值和譜聚類，處理的是靜態的數據，算法被要求在給定的數據集合上有盡可能好的聚類劃分。演化數據上的聚類是這樣一個學習任務：數據的分布隨時間而變化，在每一時刻，為演化的數據作出新的聚類劃分。

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

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

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

1 相關工作

在演化數據的聚類問題上，最常見的方法就是采用傳統聚類的方式設計函數從而對每個時刻的數據進行處理，隨后通過在代價函數上加入光滑正則項的方式來顯示數據的動態演化。該類方法側重于如何提高當前時刻數據的聚類性能以及如何保持在聚類過程中的平滑性。

1.1 在線式框架

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

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

1.2 時間平滑的演化譜聚類

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

式中：0 ≤α≤1 為用戶分配的參數，反映了用戶對聚類代價和時間代價的權衡。

兩種演化譜聚類算法的區別在于如何定義時間代價CT。第1 個算法為PCQ，它將當前分區應用于歷史數據，產生的群集質量決定了時間代價。

它對式（2）中的CS 定義為多路標準割函數NC，然而在實際問題求解中屬于NP?hard［16］，因此采取寬松的方式進行處理，其表達式為

因此，PCQ 算法的具體代價函數為

第2 個算法PCM，其快照聚類質量與PCQ 保持一致，區別在于時間損失的構造，主要通過比較當前時刻的簇劃分與上一個時刻簇劃分的差異來決定時間代價，其代價函數主要為

由此可見，PCM 和PCQ 的差異主要體現在歷史代價的定義上，PCQ 將當前時刻數據的簇劃分應用到前一時刻的數據上來衡量聚類效果，而PCM 則是衡量前后兩個時刻簇劃分之間的差異度來作為演化聚類的時間代價。

2 時間平滑的演化譜聚類

2.1 問題引入

在Chakrabarti 等［2］所提出的在線式框架中，在時間損失上存在一定的局限性，它只考慮的是前一時刻的數據點對當前時刻數據點的影響，假設數據的演化結構是線性的，但在實際應用中一些演化數據在t時刻受到影響最大的有可能不是它的前一時刻，而是更為久遠的歷史數據。

如圖2 所示，截取電影中的4 個時間戳的視頻圖片，圖2（a）是主人公A 出現，圖2（b）為主人公B出現，圖2（c）是主人公A 和B 同時出現，圖2（d）則是主人公B 出現，可以發現圖2（d）聚類（或圖像分割）與前一時刻圖2（c）并沒有太大的關聯，反而與圖2（b）關聯性較強，即T4時刻與T2時刻的數據關聯性較強。

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

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

2.2 基本框架

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

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

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

2.3 Mt 構造

在所提出的在線式框架中，Mt相似度矩陣的計算主要包含兩個部分：基于當前時刻的數據點間靜態相似度和基于時間序列的動態相似度。對于當前時刻數據點的靜態相似度，計算過程只使用當前時刻的信息而忽略其他的所有時刻信息；而后者則針對的是各個數據在隨時間演化規律上的相似性。

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

給定一個嚴格凸函數Φ，由該函數生成的Bregman 散度為

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

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

時間序列上的動態相似度計算定義了一個改進的時間序列相關系數，具體為

式中θ表示時間序列之間的相似度在目標函數中所占比重。

2.4 ESC 算法

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

2.4.1 基于PCQ 的演化譜聚類

然后，將找到k*所對應的前c個最大特征值所對應的特征向量記為Ut=Ut(k*)，通過對Ut進行行歸一化，能夠將頂點的簇指示矩陣的行向量投影到一個單位超球面上

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

2.4.2 基于PCM 的演化譜聚類

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

因此基于PCM 的演化譜聚類算法的目標函數為

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

3 實驗與分析

為了驗證兩種ESC 算法的聚類性能，在真實數據集上，通過比對標準譜聚類、演化K?means 以及演化譜聚類算法，驗證算法的聚類性能。在參數的設置上，令η=0.125，r=6。

3.1 數據集

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

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

圖3 MNIST 部分數據樣本示例Fig.3 Illustration of data samples in MNIST dataset

3.2 評價指標

采用了3 種評價標準來衡量算法性能?？煺站垲愘|量衡量當前時間片的聚類質量。

時間損失衡量當前時間片的聚類結果與歷史時間的聚類結果的差距，時間損失越小越好。

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

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

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

3.3 實驗結果

實驗環境采用的是1 臺Intel Core i3 M 390 2.67 GHz，RAM 4 GB 的計算機，所有實驗在Win?dows 7 系統的Matlab R2019a 環境下執行。

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

圖4 Iris 數據集快照聚類質量的比較Fig.4 Comparison of snapshots quality on Iris dataset

圖5 中在T5時刻之后，兩種ESC 算法在時間損失上與前一時刻沒有較大變化。而演化K?means 和演化譜聚類算法則有較大的起伏，這是因為這兩種算法在目標函數的構造上只與前一時刻比較，當其分布并不與歷史時刻分布一致時容易出現較大的抖動。

圖5 Iris 數據集時間損失的比較Fig.5 Comparison of history cost on Iris dataset

圖7～9 分別為在MNIST 數據集上的快照聚類質量、時間損失以及NMI 度量指標的實驗結果。從圖可知，本文提出的兩種ESC 算法整體而言在對演化數據的聚類問題上聚類的質量較高且時間損失較低，其中ESC?PCM 因為更側重于時間損失比ESC?PCQ 更低一些，但快照聚類質量卻相當。

圖7 MNIST 數據集快照聚類質量的比較Fig.7 Comparison of snapshots quality on MNIST dataset

圖6 Iris 數據集NMI 的比較Fig.6 Comparison of NMI on Iris dataset

圖8 MNIST 數據集時間損失的比較Fig.8 Comparison of history cost on MNIST dataset

圖9 MNIST 數據集NMI 的比較Fig.9 Comparison of NMI on MNIST dataset

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

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

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

4 結論

本文主要針對演化數據的聚類問題，提出了自適應時間平滑的演化譜聚類?？紤]當前時刻的簇劃分與前r個時刻的歷史數據存在一定的關聯，對時間回溯窗口進行設定，自適應地尋找與當前快照最為相關的歷史快照。在相似度矩陣的構造上有機融合了基于IS 的靜態相似度以及基于時間序列的動態相似度，并結合譜聚類提出了兩種自適應平滑的演化譜聚類算法ESC?PCQ 和ESC?PCM。兩種算法相較于其他演化聚類算法，在聚類效果上更好且更為平滑。然而，如果設定較大的時間回溯范圍，會導致計算代價變高。因此，如何在保持或者降低時間代價的基礎上進一步提高演化聚類的性能，將是下一步研究的工作重點。