面向時間序列事件的動態矩陣聚類方法

馬瑞強，宋寶燕，丁琳琳，王俊陸

遼寧大學 信息學院，沈陽110036

近年來，隨著信息化技術的快速發展，金融、生物、氣象、醫學等各個領域產生了大量的時間序列數據[1]，挖掘數據中的潛在價值對決策者具有重大的指導作用。聚類[2-4]作為一種無監督學習[5-6]方法，由于其事先無需對任一樣本打類別標記，在分析數據的內在關系及蘊含的信息、知識等方面發揮著至關重要的作用。時間序列數據本身具有偽事件、持續性及漂移性等復雜結構特征，現有方法多直接對數據集中結構復雜的持續事件聚類，未將聚類對象進行轉化，聚類結果準確性低且效率差，因此如何設計一種精準高效的時間序列事件聚類[7]方法，一直是流式數據挖掘[8-9]領域研究的難點。

針對這些問題，本文提出一種面向時間序列事件的動態矩陣聚類方法RDMC（RDS dynamic matrixbased clustering），通過精準、高效地構建RDS（representative and diversifying sequences）與數據集的距離矩陣，將對原始數據集的聚類轉化為對動態化矩陣的聚類，實現時間序列事件的有效劃分。本文的主要貢獻如下：

（1）基于事件r近鄰密度和反向近鄰數構建事件近鄰評價體系，依據評價值優劣衡量事件的代表性；

（2）在此基礎上，提出事件近鄰評分的后向差分計算策略，依據差分結果確定評分邊界，通過近鄰評分與邊界值的大小關系構建RDS 候選集，提高RDS選取效率；

（3）綜合RDS的雙重約束條件，提出基于組合優化法最優解集篩選策略，實現RDS的高效查找；

（4）針對時序事件聚類準確率低的問題，提出基于K-means 的矩陣聚類方法，對RDS 與數據集的動態化距離矩陣聚類，最終得到事件的類別標簽。

圖1為RDMC方法結構示意圖。

Fig.1 Schematic diagram of RDMC structure圖1 RDMC方法結構示意圖

1 相關工作

目前，許多專家學者對時間序列事件聚類方法進行了深入研究，取得了一定的研究成果。

Euán等人[10]提出基于譜密度[11]以及全變分距離[12]的聚類方法，通過事件的相似振蕩行為構建類簇，該方法沒有對原始數據集進行轉化，直接對時間序列事件聚類，受事件的復雜結構影響，聚類準確率低；Azencott 等人[13]提出在大規模時間序列數據上的自動聚類方法，通過隨機梯度下降法[14-15]最小化衡量聚類質量的代價函數，從而自動生成最優化類簇，由于代價函數的優化過程耗時過長，該方法的聚類效率較差；鄭建煒等人[16]提出聯合拉普拉斯正則項[17]和自適應特征學習方法，能夠同時進行特征選擇和數據聚類，但該方法需人工設定多個參數，參數的不同取值直接影響聚類結果的準確率；張東月等人[18]提出基于網格耦合和核心網格的聚類方法GCStream，通過網格耦合更精確地表達數據之間的相關性，但該方法建立的網格要求邊長相等，無法適用于結構復雜的時間序列數據；Zakaria 等人[19]提出利用數據集中具有特征性的局部形狀（U-Shapelets）進行聚類的方法，方法具有較高的準確性，但由于提取U-Shapelets的時間復雜度過高，導致聚類效率極低；Madiraju 等人[20]提出深度時間聚類方法（deep temporal clustering，DTC），該方法利用一個自動編碼器降低時間維數并通過一個新穎的時間聚類層進行聚類分配。迭代訓練時間聚類層時，優化目標為最小化預測分布和目標分布的KL 散度損失[21-22]，目標分布通過預測分布進行計算并在每次迭代時更新，這導致該方法存在不穩定性，聚類準確性波動較大。

綜上，本文對時間序列事件聚類進行了深入研究，針對現有聚類方法的不足，綜合考慮事件的復雜結構特征，提出一種基于RDS 的時間序列事件聚類方法，在確保聚類準確性的同時提高聚類效率。

2 RDS候選集選取

時間序列事件是在時間域上滿足一定條件的一系列離散數據點組成的序列。相同類型的事件通常都具有相同或相似的特征規律。提出事件近鄰評價體系構建方法，依據評價值的優劣衡量事件的代表性，提出后向差分法確定近鄰評分邊界值，通過邊界值與評價值的大小關系構建RDS候選集。

2.1 事件近鄰評價體系構建

提出RDS 及其候選集概念，并基于事件近鄰密度和反向近鄰數構建事件近鄰評價體系，通過評價值準確衡量數據集中任意事件的代表性。RDS如定義1所示。

定義1（RDS）給定時間序列事件數據集T={t1,t2,…,tn}，ti(1 ≤i≤n)為多個離散點集合構成的一個持續事件，RDS 為從T中選出的可最大化地代表不同類簇且差異性最大的k(1 ≤k≤|T|)個事件，其中的一個事件記為RDSi(1 ≤i≤k)。

最大化地代表不同類簇是指RDSi分別與不同類簇的相似性最大，差異性最大是指多個RDSi之間的相似性最小。圖2 為RDS 定義示意圖，數據集T被劃分為四個類簇C1～C4，每個類簇包含的事件如藍色小圓圈所示，T中最佳的RDS 如紅色小圓圈所示。其中，RDS1與類簇C1中任一事件的距離d1較小，使得它與C1的整體相似度最大，即它可最大化地代表C1；同理，RDS2、RDS3可分別最大化地代表C2、C3。RDS1～RDS3間的距離d4～d6均較大，即它們在最大化地代表T中不同類別事件的同時，滿足互相之間的差異性最大。

Fig.2 Schematic diagram of RDS definition圖2 RDS定義示意圖

RDS 選取策略影響事件聚類效率，直接從數據集T中選取的代價過高，因而先構建其候選集，再從候選集中查找k個代表性與差異性同時最大的事件構成RDS。

RDS候選集C表示從數據集T中選擇的具有代表性的m個事件的集合，即C={t1,t2,…,tm}，ti(1 ≤i≤m)表示一個事件，且k?m?n，k表示RDS 里包含的事件數量，n為T的大小。所選擇的一個事件必須與某一類簇的相似度較高，但多個事件之間不要求差異性較大。

事件大多具有漂移性等復雜的結構特征，為準確衡量它們之間的相似度，給出DTW（dynamic time warping）距離度量方法。

若有兩個時間序列事件t1和t2，長度分別為|t1|和|t2|，記規整路徑W={w1,w2,…,wr}，其中max(|t1|,|t2|)≤r≤|t1|+|t2|，wr的形式為(i,j)，i為t1中的一個元素，j為t2中的一個元素。令t1和t2的代價矩陣為D，則D中的一條路徑為：

其中，ED(i,j)為i和j的歐式距離，最后得到t1和t2的DTW距離為：

以下，先構建事件近鄰評價體系，通過評價值衡量數據集T中事件的代表性。事件r鄰域的定義如下。

定義2（r鄰域）給定數據集T，事件t的r鄰域NNr(t)定義為與t距離最近的r個事件的集合，即：

其中，d(t,x)表示t與事件x的DTW距離，dr(t)表示t與其他事件間的第r近鄰DTW距離。對于一個事件t，用t的近鄰密度量化t與其r鄰域內的事件的總體相近程度。

定義3（近鄰密度）給定事件t的r鄰域NNr(t)，t的近鄰密度P(t)定義為：

P(t)越大，表示t與所有在其r鄰域內的事件的整體相似性越高；反之，則相似性越低。此外，通過反向近鄰數可從反向角度衡量事件t與其他事件的相近程度。

定義4（反向近鄰數）反向近鄰數Nb(t)表示在對T中的每個事件計算其r近鄰距離的過程中，事件t被其他事件近鄰的總次數。即：?x∈T，若?t∈NNr(x)，則Nb(t)=Nb(t)+1，1 ≤r＜n。

Nb(t)越大，表明t被更多的事件近鄰，反向說明t與更多事件的距離越近，即相似性越高。在近鄰密度和反向近鄰數的基礎上，提出事件近鄰評分的概念，同時從正反兩方面綜合衡量事件t與其他事件的整體相似性。

定義5（近鄰評分）給定事件t的反向近鄰數Nb(t)與近鄰密度P(t)，t的近鄰評分S(t)為ln(Nb(t)+1)與P(t)的乘積，即：

公式中，通過對Nb(t)取對數縮小其尺度，使其變化更平穩，由于Nb(t)可能為0，對其加1，可避免對數計算值出現負數，即使得ln(Nb(t)+1)≥0。公式表明，給定t的r鄰域NNr(t)，若t的反向近鄰數Nb(t)與近鄰密度P(t)越大，則S(t)越大，表明t與更多事件相似，即t是具有代表性的事件。

2.2 基于后向差分法的RDS候選集構建

在近鄰評價體系的基礎上，提出近鄰評分的后向差分計算策略，依據差分計算結果快速篩選RDS候選集。

不同事件的反向近鄰數與近鄰密度均相差較大，使得近鄰評分的計算值不在同一尺度下，需將其歸一化至[0,1]區間。以來自UCR 數據庫的Plane 數據集為例，對該數據集中的所有事件計算近鄰評分，歸一化并排序，得到圖3（a）中的近鄰評分示意圖。

如圖3中所示，候選集C中事件的近鄰評分高于正常事件，故C中的事件均位于高評分區域，正常事件處于低評分區域，且在二者的邊界處，近鄰評分的跳躍幅度大。基于此，本文提出近鄰評分的后向差分計算策略，通過比較差分值的大小確定邊界并構建候選集，后向差分計算公式如下：

?S(t)=S(t)-S(t-1) （6）

其中，?S(t)為差分算子，S(t)與S(t-1)為兩個相鄰事件。圖3（b）為近鄰評分的后向差分計算結果，從中可看出，差分最大值所在點正好位于圖3（a）中評分出現較大跳躍的位置。

RDS候選集C構建的具體過程如算法1所示。

算法1構建C算法

輸入：數據集T，閾值參數φ。

輸出：RDS候選集結果C。

1.初始化：r=0，N(r)=0；

2.對T中的每個事件計算第r近鄰w；

3.Nb(w)←Nb(w)+1，NNr(t)←NNr(t)?{w}；

4.依據式（5）計算t的近鄰評分S(t)；

5.若Nb(t)==0，則N(r)=N(r)+1；

Fig.3 Schematic diagram of r-nearest neighbor score and its difference圖3 近鄰評分及其差分示意圖

6.若(N(r-1)-N(r))/N(r-1)＜φ，轉至步驟7，否則,令r=r+1，轉至步驟2；

7.對S(t)進行歸一化處理并排序；

8.依據式（6）計算S(t)的后向差分D，記最大值的索引值為max；

9.若S(t)>S(max)，則t∈C，令C=C?t，否則,t?C；

10.返回候選集結果C。

首先，在構建T中所有事件r鄰域的過程中，對每個事件t計算其第r近鄰序列w，將w的反向近鄰數Nb(w)加1，并將w添加至t的r鄰域NNr(t)，計算t的近鄰評分S(t)。此時，統計T中事件的反向近鄰數等于0的數量N(r)，若N(r)的下降率小于給定的閾值φ（0 ≤φ?1，一般取[0,0.1]之間的數)，則r鄰域構建完成，迭代結束，否則繼續構建第r+1 鄰域；如圖4所示，剛開始時，隨著r增大，N(r)快速減小；當r增至一定大時，N(r)減小的速度趨于平緩并最終減小至0。N(r)平緩減小時，r獲得最佳截止值。以某一事件t為例，若r再增大，將導致與t相距較遠的事件被錯誤添加至t的r鄰域，近鄰關系建立不當將使得近鄰評分值無法正確衡量t的代表性。其次，對歸一化并排序處理后的近鄰評分S進行差分計算，計算結果D中的最大值索引記為max。最后，位于max側的事件屬于RDS候選集，將它們添加到C，返回C。

Fig.4 Schematic diagram of change trend of N圖4 N的變化趨勢示意圖

3 時間序列事件聚類

在候選集C的基礎上，提出基于組合優化的RDS最優選取方法，動態構建RDS與數據集的距離矩陣，提出基于K-means的矩陣聚類方法，實現事件的類別劃分。

3.1 最優RDS解選取

由定義1 可知，RDS 需同時滿足“相似性”與“差異性”兩個條件，故RDS的選取為多條件約束最優解問題，可通過組合優化的方法求解，依據近鄰評分計算候選集中所有可行解的質量指標QI，通過比較QI的大小得到最優解。

記C中任意k個事件的一個組合為RDS 的一個可行解，所有可行解構成集合F，對于特定的一個可行解f∈F，f中k個事件的近鄰評分均值記為u，它們之間的距離均值記為v。即：

u、v現不在同一尺度下，將其規格化至[0,1]區間，使二者具有可比性。此外，為準確量化可行解f的選取質量，本文提出質量指標的概念。

定義6質量指標QI（quality index）用于同時衡量RDS 的一個可行解f的雙重約束條件，計算公式如下：

其中，0 ＜α＜1，系數α用于均衡u與v的占比，默認情況下，α=0.5。u,v越大，則QI(f)越大，表明f的“相似性”與“差異性”越大，選取質量越高。當QI(f)最大時，RDS取得最優解o，即：

綜上所述，最優RDS解選取過程如算法2所示。

算法2選取RDS算法

輸入：數據集T，閾值參數α，RDS大小k。

輸出：RDS最優解o。

1.由算法1獲得候選集C；

2.將從C中取k個事件的所有可行解記為F；

3.對于每一個可行解f，根據式（5）、式（6）計算u,v，并將其歸一化；

4.根據式（9）計算f的QI；

5.根據式（10）求得最優解的o。

圖5 為Plane 數據集的類簇示意圖，該數據集包含210條數據，分為7個類別。

Fig.5 Schematic diagram of clusters of Plane data set圖5 Plane數據集的類簇示意圖

對該數據集上構建候選集C后，當k取2時，得到如圖6所示的RDS選取結果示意圖。

3.2 基于K-means的矩陣聚類

在3.1 節選出的RDS 的基礎上，通過動態構建RDS 與數據集的距離矩陣進行聚類對象的轉化，提出基于K-means的矩陣聚類方法，根據矩陣聚類結果得到事件的類別標簽。

RDS與數據集的距離矩陣M的形式如下所示。

Fig.6 Schematic diagram of RDS selection result圖6 RDS選取結果示意圖

M的大小為[n,i]，i≤k，表示RDS 中實際參與聚類的事件數量，n表示數據集T中所有事件的數量，M中的元素mji表示RDSi與T中事件j的距離。

矩陣M的一個重要屬性是其蘊含事件間的相對距離大小。圖7為在Plane數據集上選出的RDS與數據集的距離矩陣示意圖，圖中的每一個點的坐標值表示一個事件與RDS1以及RDS2的距離，如點(X,Y)表示一個事件與RDS1的距離為0.337，與RDS2的距離為0.039。由于各個事件間的相對距離大小的不同，該距離矩陣間接地把原始數據集劃分成了7個類別，對矩陣M聚類將實現對原始數據集的類別劃分。

Fig.7 Schematic diagram of distance matrix between RDS and data set圖7 RDS與數據集的距離矩陣示意圖

此外，M不是由RDS與數據集的距離向量直接構成，而是逐步擴展、動態構建生成，其目的是進一步提高聚類的準確率和效率。當計算RDSi與數據集的距離向量后，將該向量添加為矩陣M的一列橫向擴展M，根據當前的聚類純度Pur的大小，再決定是否需要繼續拓展M以及進行聚類操作。聚類純度的計算公式如下：

其中，n表示總的事件個數；C={c1,c2,…,cj}表示真實的類簇劃分；Ω={w1,w2,…,wk}表示當前聚類的類簇劃分。

基于K-means 的矩陣聚類方法的具體過程如算法3所示。

算法3 聚類算法

輸入：數據集T，閾值參數τ，RDS大小k1，事件類別數k2。

輸出：事件類別標簽Labels。

1.初始化：i=0，iters=1，MaxIters=50；

2.由算法2獲得候選集RDS最優解R；

3.Whilei＜k1:

4.計算第RDSi與T的距離向量dist;

5.Dist=[Dist dist]；

6.[Labels,Centroids]=K-means(Dist,k2)；iters++;

7.若iters

8.CP(i)=1-Pur(Labels(i-1),Labels(i))；

9.若CP(i)＜τ，轉至步驟11；

10.i++；

11.返回聚類結果Labels(i)。

首先，構建候選集C并得到RDS 最優解R；其次，迭代地進行聚類過程（4～10 行），當i＜k1時，計算RDSi與T的距離向量dist并將其橫向添加到Dist里，Dist此時為RDS 中前i個事件與T的距離矩陣。使用K-means 對Dist聚類，為使聚類結果更準確，Kmeans 運行了多次。記聚類純度Pur的變化量為CP（Change inPur），假定第i-1 次循環時得到的聚類標簽是正確的，則由公式可得，第i次循環時對應的CP(i)=1-Pur(Labels(i-1),Labels(i))。當CP小于τ（0 ≤τ?1，一般取[0,0.1]之間的數）時，循環結束。隨著參與構建矩陣Dist的RDS的數量的增加，Dist里包含更詳盡的事件間的相對距離信息，促使RI呈現上升趨勢，當CP較小時，表明此時已得到最佳聚類結果，無需再繼續進行聚類過程；最后，返回通過聚類得到的事件類別標簽。

4 實驗分析

實驗平臺為Intel?i5-6500 3.20 GHz處理器，8 GB內存，Windows 10（64 bit）操作系統。從UCR公開數據庫中選取6個數據集進行實驗，如表1所示。從聚類準確率、聚類可靠性、時間效率等方面驗證本文提出的RDMC 方法的有效性，對比方法為K-means、DBSCAN（density-based spatial clustering of applications with noise）、Spectral、U-Shapelets 等。閾值參數τ取0.05，φ在兩個較大數據集FordA 與StarLightCurves上取0.07，在其他小規模數據集上取0.03。

Table 1 Experimental data set表1 實驗數據集

4.1 聚類準確率對比

本節在表1 的基準數據集上評估RDMC 方法的聚類準確率，使用RI（Rand index）作為評價指標，RI計算公式如下：

其中，TP表示屬于同一類且被分到同一簇中的事件數量；TN表示屬于不同類且被分到不同簇中的事件數量；FP表示屬于不同類但被分到同一簇中的事件數量；FN表示屬于同一類但被分到不同簇中的事件數量。0 ≤RI≤1，RI值越大，聚類準確率越高。表2為RDMC方法與各對比方法的RI結果對比。

Table 2 Comparison of clustering accuracy(RI)表2 聚類準確率（RI）對比

由結果可知，RDMC 方法在4 個數據集上的RI高于其他方法，在所有數據集上都有RI≥0.84。此外，相對于K-means、DBSCAN、Spectral、U-Shapelets方法，RDMC 方法在所有數據集上的準確率平均提升了12%、22%、23%、36%。因此，RDMC 方法具有更高的準確率。

4.2 聚類可靠性對比

本節在Plane數據集上通過實際的聚類結果對比RDMC 方法與其他四種方法的聚類可靠性，聚類所得類別標簽對比如圖8所示，其中，Real組的七幅子圖表示所有事件的真實所屬類別，其余五組中的七幅子圖分別表示各聚類方法將數據集實際所劃分的類別。

從圖8 中可看出，K-means 方法對類4、6、7 的劃分基本正確，但類1、2中的部分事件應屬于類5，理應屬于類1、2 中的部分事件被錯誤地分到了類3；DBSCAN對各個類的劃分大致正確，但該方法基于密度聚類，聚類質量高度依賴于參數鄰域半徑Eps和Eps內的最少事件數Minpts的取值，不在各個類簇任一事件鄰域半徑內的事件均被識別為噪聲，這導致有相當一部分正常事件被誤劃分為噪聲數據；Spectral、U-Shapelets 與K-means 類似，聚類結果中均有部分事件被錯誤歸類；RDMC 方法的預測標簽接近于真實類別標簽，僅有極少數事件未被正確聚類。綜上，RDMC方法比其他方法具有更優的聚類質量，可靠性更高。

4.3 聚類效率對比

本節驗證RDMC 方法的聚類效率，各個方法在不同數據集上的具體運行時間對比如圖9 所示，UShapelets 方法的運行時間比其他方法高出幾個數量級，故在圖中使用同一橫坐標、不同的縱坐標對比幾種方法的時間消耗。

由實驗結果可發現，K-means 耗時最少；Spectral構建相似性矩陣并進行特征值分解的代價較高，導致其聚類效率較低；DBSCAN 的時間主要花費在查找Eps 鄰域內符合條件的事件，其代價明顯低于Spectral；RDMC 的耗時高于K-means，低于DBSCAN與Spectral；U-Shapelets提取過程極為漫長，使得該方法的運行時間遠遠高于其他方法。

特別地，在較大數據集FordA、StarLightCurves上，雖然K-means的效率高于RDMC，但由4.1節的實驗結果可知，RDMC 在這兩個數據集上的聚類準確率高于K-means，一個可能的原因是這兩個數據集中的部分序列存在漂移性，其結構較復雜，RDMC把對原始數據集的聚類轉化為對矩陣的聚類后，極大地減少了結構失真問題對準確率的影響。

Fig.8 Comparison of class labels圖8 聚類所得類別標簽對比

Fig.9 Comparison of running time圖9 運行時間對比

總之，RDMC 具有良好的聚類效率且比其他方法更適合處理具有復雜結構的持續事件。

4.4 參數敏感度分析

本節對RDMC方法的閾值參數φ與τ的敏感性進行分析并討論其合理取值，φ與τ在不同取值情況下的聚類準確率如圖10、圖11所示，聚類準確率使用式（11）中的Pur來衡量。φ與τ均近似等于0，二者的取值均限制在[0,0.1]之間。

Fig.10 Effect of value of φ on clustering purity圖10 φ 的取值對聚類純度的影響

Fig.11 Effect of value of τ on clustering purity圖11 τ 的取值對聚類純度的影響

由結果可知，隨著φ增大，小數據上的Pur先保持穩定后小幅度減小，大規模數據集上的Pur基本不變。φ對Pur的影響與數據集大小有關，若數據集規模較大（事件數量較多），則在算法1 中，相距較遠的事件不會被輕易錯誤添加至r鄰域，反之，則容易錯誤添加至r鄰域。因此，在小規模數據集上，φ取[0,0.05]之間的數，確保聚類準確性；在大數據集上，φ的取值最好在[0.05,0.08]之間，保證聚類準確性的同時，提高聚類效率（φ越大，r鄰域構建過程的迭代次數越少）。

而隨著τ增大，Pur在所有數據集上均先保持穩定后緩慢減小。這是因為τ決定聚類過程（算法3）何時結束，其越小，Pur越高，但效率會小幅降低。因此，τ的最佳取值在[0.04,0.06]之間。

5 結論

本文對時間序列事件聚類進行了深入的研究，針對現有聚類方法聚類準確度低、效率差等問題，提出一種面向時間序列事件的動態矩陣聚類方法。首先，提出事件近鄰評價體系，實現事件代表性的有效衡量；根據近鄰評分的后向差分計算策略界定評分高低，實現RDS候選集的快速構建，進而提高RDS選取的效率；其次，提出基于組合優化的選取方法，實現RDS的高效且最優查找；最后，針對直接對時序事件聚類的準確率低的問題，在動態地構建RDS 與數據集的距離矩陣的基礎上，提出基于K-means的矩陣聚類方法，實現事件所屬類別的正確劃分。實驗驗證了所提方法的有效性。