馬瑞強(qiáng)，宋寶燕，丁琳琳，王俊陸

遼寧大學(xué) 信息學(xué)院，沈陽110036

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

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

（1）基于事件r近鄰密度和反向近鄰數(shù)構(gòu)建事件近鄰評價體系，依據(jù)評價值優(yōu)劣衡量事件的代表性；

（2）在此基礎(chǔ)上，提出事件近鄰評分的后向差分計算策略，依據(jù)差分結(jié)果確定評分邊界，通過近鄰評分與邊界值的大小關(guān)系構(gòu)建RDS 候選集，提高RDS選取效率；

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

（4）針對時序事件聚類準(zhǔn)確率低的問題，提出基于K-means 的矩陣聚類方法，對RDS 與數(shù)據(jù)集的動態(tài)化距離矩陣聚類，最終得到事件的類別標(biāo)簽。

圖1為RDMC方法結(jié)構(gòu)示意圖。

Fig.1 Schematic diagram of RDMC structure圖1 RDMC方法結(jié)構(gòu)示意圖

1 相關(guān)工作

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

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

綜上，本文對時間序列事件聚類進(jìn)行了深入研究，針對現(xiàn)有聚類方法的不足，綜合考慮事件的復(fù)雜結(jié)構(gòu)特征，提出一種基于RDS 的時間序列事件聚類方法，在確保聚類準(zhǔn)確性的同時提高聚類效率。

2 RDS候選集選取

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

2.1 事件近鄰評價體系構(gòu)建

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

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

最大化地代表不同類簇是指RDSi分別與不同類簇的相似性最大，差異性最大是指多個RDSi之間的相似性最小。圖2 為RDS 定義示意圖，數(shù)據(jù)集T被劃分為四個類簇C1～C4，每個類簇包含的事件如藍(lán)色小圓圈所示，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 選取策略影響事件聚類效率，直接從數(shù)據(jù)集T中選取的代價過高，因而先構(gòu)建其候選集，再從候選集中查找k個代表性與差異性同時最大的事件構(gòu)成RDS。

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

事件大多具有漂移性等復(fù)雜的結(jié)構(gòu)特征，為準(zhǔn)確衡量它們之間的相似度，給出DTW（dynamic time warping）距離度量方法。

若有兩個時間序列事件t1和t2，長度分別為|t1|和|t2|，記規(guī)整路徑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距離為：

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

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

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

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

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

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

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

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

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

2.2 基于后向差分法的RDS候選集構(gòu)建

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

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

如圖3中所示，候選集C中事件的近鄰評分高于正常事件，故C中的事件均位于高評分區(qū)域，正常事件處于低評分區(qū)域，且在二者的邊界處，近鄰評分的跳躍幅度大?；诖耍疚奶岢鼋徳u分的后向差分計算策略，通過比較差分值的大小確定邊界并構(gòu)建候選集，后向差分計算公式如下：

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

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

RDS候選集C構(gòu)建的具體過程如算法1所示。

算法1構(gòu)建C算法

輸入：數(shù)據(jù)集T，閾值參數(shù)φ。

輸出：RDS候選集結(jié)果C。

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

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

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

4.依據(jù)式（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)＜φ，轉(zhuǎn)至步驟7，否則,令r=r+1，轉(zhuǎn)至步驟2；

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

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

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

10.返回候選集結(jié)果C。

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

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

3 時間序列事件聚類

在候選集C的基礎(chǔ)上，提出基于組合優(yōu)化的RDS最優(yōu)選取方法，動態(tài)構(gòu)建RDS與數(shù)據(jù)集的距離矩陣，提出基于K-means的矩陣聚類方法，實現(xiàn)事件的類別劃分。

3.1 最優(yōu)RDS解選取

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

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

u、v現(xiàn)不在同一尺度下，將其規(guī)格化至[0,1]區(qū)間，使二者具有可比性。此外，為準(zhǔn)確量化可行解f的選取質(zhì)量，本文提出質(zhì)量指標(biāo)的概念。

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

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

綜上所述，最優(yōu)RDS解選取過程如算法2所示。

算法2選取RDS算法

輸入：數(shù)據(jù)集T，閾值參數(shù)α，RDS大小k。

輸出：RDS最優(yōu)解o。

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

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

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

4.根據(jù)式（9）計算f的QI；

5.根據(jù)式（10）求得最優(yōu)解的o。

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

Fig.5 Schematic diagram of clusters of Plane data set圖5 Plane數(shù)據(jù)集的類簇示意圖

對該數(shù)據(jù)集上構(gòu)建候選集C后，當(dāng)k取2時，得到如圖6所示的RDS選取結(jié)果示意圖。

3.2 基于K-means的矩陣聚類

在3.1 節(jié)選出的RDS 的基礎(chǔ)上，通過動態(tài)構(gòu)建RDS 與數(shù)據(jù)集的距離矩陣進(jìn)行聚類對象的轉(zhuǎn)化，提出基于K-means的矩陣聚類方法，根據(jù)矩陣聚類結(jié)果得到事件的類別標(biāo)簽。

RDS與數(shù)據(jù)集的距離矩陣M的形式如下所示。

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

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

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

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

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

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

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

算法3 聚類算法

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

輸出：事件類別標(biāo)簽Labels。

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

2.由算法2獲得候選集RDS最優(yōu)解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)＜τ，轉(zhuǎn)至步驟11；

10.i++；

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

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

4 實驗分析

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

Table 1 Experimental data set表1 實驗數(shù)據(jù)集

4.1 聚類準(zhǔn)確率對比

本節(jié)在表1 的基準(zhǔn)數(shù)據(jù)集上評估RDMC 方法的聚類準(zhǔn)確率，使用RI（Rand index）作為評價指標(biāo)，RI計算公式如下：

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

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

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

4.2 聚類可靠性對比

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

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

4.3 聚類效率對比

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

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

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

Fig.8 Comparison of class labels圖8 聚類所得類別標(biāo)簽對比

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

總之，RDMC 具有良好的聚類效率且比其他方法更適合處理具有復(fù)雜結(jié)構(gòu)的持續(xù)事件。

4.4 參數(shù)敏感度分析

本節(jié)對RDMC方法的閾值參數(shù)φ與τ的敏感性進(jìn)行分析并討論其合理取值，φ與τ在不同取值情況下的聚類準(zhǔn)確率如圖10、圖11所示，聚類準(zhǔn)確率使用式（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 τ 的取值對聚類純度的影響

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

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

5 結(jié)論

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