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

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

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

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

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

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

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

（4）針對(duì)時(shí)序事件聚類準(zhǔn)確率低的問(wèn)題，提出基于K-means 的矩陣聚類方法，對(duì)RDS 與數(shù)據(jù)集的動(dòng)態(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é)者對(duì)時(shí)間序列事件聚類方法進(jìn)行了深入研究，取得了一定的研究成果。

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

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

2 RDS候選集選取

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

2.1 事件近鄰評(píng)價(jià)體系構(gòu)建

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

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

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

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

RDS 選取策略影響事件聚類效率，直接從數(shù)據(jù)集T中選取的代價(jià)過(guò)高，因而先構(gòu)建其候選集，再?gòu)暮蜻x集中查找k個(gè)代表性與差異性同時(shí)最大的事件構(gòu)成RDS。

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

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

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

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

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

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

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

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

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

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

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

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

公式中，通過(guò)對(duì)Nb(t)取對(duì)數(shù)縮小其尺度，使其變化更平穩(wěn)，由于Nb(t)可能為0，對(duì)其加1，可避免對(duì)數(shù)計(jì)算值出現(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)建

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

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

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

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

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

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

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

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

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

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

2.對(duì)T中的每個(gè)事件計(jì)算第r近鄰w；

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

4.依據(jù)式（5）計(jì)算t的近鄰評(píng)分S(t)；

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

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

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

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

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

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

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

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

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

3 時(shí)間序列事件聚類

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

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

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

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

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

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

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

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

算法2選取RDS算法

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

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

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

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

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

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

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

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

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

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

3.2 基于K-means的矩陣聚類

在3.1 節(jié)選出的RDS 的基礎(chǔ)上，通過(guò)動(dòng)態(tài)構(gòu)建RDS 與數(shù)據(jù)集的距離矩陣進(jìn)行聚類對(duì)象的轉(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í)際參與聚類的事件數(shù)量，n表示數(shù)據(jù)集T中所有事件的數(shù)量，M中的元素mji表示RDSi與T中事件j的距離。

矩陣M的一個(gè)重要屬性是其蘊(yùn)含事件間的相對(duì)距離大小。圖7為在Plane數(shù)據(jù)集上選出的RDS與數(shù)據(jù)集的距離矩陣示意圖，圖中的每一個(gè)點(diǎn)的坐標(biāo)值表示一個(gè)事件與RDS1以及RDS2的距離，如點(diǎn)(X,Y)表示一個(gè)事件與RDS1的距離為0.337，與RDS2的距離為0.039。由于各個(gè)事件間的相對(duì)距離大小的不同，該距離矩陣間接地把原始數(shù)據(jù)集劃分成了7個(gè)類別，對(duì)矩陣M聚類將實(shí)現(xiàn)對(duì)原始數(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ò)展、動(dòng)態(tài)構(gòu)建生成，其目的是進(jìn)一步提高聚類的準(zhǔn)確率和效率。當(dāng)計(jì)算RDSi與數(shù)據(jù)集的距離向量后，將該向量添加為矩陣M的一列橫向擴(kuò)展M，根據(jù)當(dāng)前的聚類純度Pur的大小，再?zèng)Q定是否需要繼續(xù)拓展M以及進(jìn)行聚類操作。聚類純度的計(jì)算公式如下：

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

4.2 聚類可靠性對(duì)比

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

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

4.3 聚類效率對(duì)比

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

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

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

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

Fig.9 Comparison of running time圖9 運(yùn)行時(shí)間對(duì)比

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

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

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

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

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

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

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

5 結(jié)論

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