余思琴，閆秋艷，閆欣鳴

(中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱ysq@cumt.edu.cn)

基于最佳u-shapelets的時間序列聚類算法

余思琴*，閆秋艷，閆欣鳴

(中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱ysq@cumt.edu.cn)

針對基于u-shapelets的時間序列聚類中u-shapelets集合質(zhì)量較低的問題，提出一種基于最佳u-shapelets的時間序列聚類算法DivUshapCluster。首先，探討不同子序列質(zhì)量評估方法對基于u-shapelets的時間序列聚類結(jié)果的影響；然后，選用最佳的子序列質(zhì)量評估方法對u-shapelet候選集進(jìn)行質(zhì)量評估；其次，引入多元top-k查詢技術(shù)對u-shapelet候選集進(jìn)行去除冗余操作，搜索出最佳的u-shapelets集合；最后，利用最佳u-shapelets集合對原始數(shù)據(jù)集進(jìn)行轉(zhuǎn)化，達(dá)到提高時間序列聚類準(zhǔn)確率的目的。實(shí)驗(yàn)結(jié)果表明，DivUshapCluster算法在聚類準(zhǔn)確度上不僅優(yōu)于經(jīng)典的時間序列聚類算法，而且與BruteForce算法和SUSh算法相比，DivUshapCluster算法在22個數(shù)據(jù)集上的平均聚類準(zhǔn)確度分別提高了18.80%和19.38%。所提算法能夠在保證整體效率的情況下有效提高時間序列的聚類準(zhǔn)確度。

時間序列；聚類；u-shapelets；內(nèi)部聚類評價指標(biāo)；多元化top-k查詢

0 引言

時間序列聚類方法是數(shù)據(jù)挖掘領(lǐng)域中重要的研究對象，受到了各個領(lǐng)域的關(guān)注，例如，金融學(xué)[1]、氣象學(xué)[2]、醫(yī)藥學(xué)[3]、生物學(xué)[4]等。由于時間序列的高維性以及內(nèi)部存在的大量噪聲數(shù)據(jù)，一些研究者更關(guān)注時間序列內(nèi)部特征的差異性，并提出了大量基于特征的時間序列聚類方法。基于u-shapelets(unsupervised shapelets)的時間序列聚類算法也可視為基于特征的時間序列聚類算法。u-shapelet是基于shapelet[5-7]的時間序列分類算法在時間序列聚類方向上的擴(kuò)展延伸，兩者都關(guān)注時間序列中極具辨識度的局部特征，基于這類局部特征的分類和聚類方法都具有強(qiáng)解釋性特點(diǎn)；且u-shapelet更適用于無標(biāo)簽或獲取標(biāo)簽困難的場景，能夠?qū)崿F(xiàn)時間序列數(shù)據(jù)的準(zhǔn)確劃分，基于u-shapelets的時間序列聚類算法也受到了越來越多的關(guān)注[8-10]。

原始的基于u-shapelets的時間序列聚類算法(BruteForce算法[8])旨在利用u-shapelets集合構(gòu)建一個與時間序列數(shù)據(jù)集相關(guān)的距離矩陣，并使用現(xiàn)有的聚類算法，例如k-means算法，對距離矩陣進(jìn)行聚類。為了保證u-shapelets集合能夠構(gòu)造一個良好的距離矩陣，BruteForce算法將時間序列數(shù)據(jù)集中的所有子序列作為u-shapelet候選子序列，并對u-shapelet候選集中的所有子序列進(jìn)行質(zhì)量評估以找出最佳的u-shapelets集合。假設(shè)一個數(shù)據(jù)集中具有n條時間序列，每條時間序列的長度為m，則一個數(shù)據(jù)集中的所有子序列的數(shù)量為O(nm2)；評估一條子序列質(zhì)量的計算量為O(nm2)；因此，使用BruteForce算法查找一個u-shapelet的時間復(fù)雜度為O(n2m4)。

顯然，BruteForce算法存在時間復(fù)雜度過高的缺點(diǎn)，主要表現(xiàn)為在選中一條子序列作為u-shapelet時，需要評估u-shapelet候選集中的所有子序列的質(zhì)量，而評估一條子序列的時間復(fù)雜度過大。為了解決時間復(fù)雜度過高的問題，Zakaria等[9]使用近似值對時間序列間的距離進(jìn)行估計，并采用剪枝策略減少u-shapelet候選子序列的評估；Ulanova等[10]對時間序列數(shù)據(jù)進(jìn)行符號聚類近似(Symbolic Aggregate approXimate, SAX)轉(zhuǎn)化，并選取1%的子序列作為u-shapelet候選集。這兩種方法均在犧牲聚類準(zhǔn)確度的條件下提高了時間序列的聚類效率。而在前人的研究基礎(chǔ)上，本文將從提升u-shapelets集合整體質(zhì)量的角度提高基于u-shapelet的時間序列聚類的準(zhǔn)確度，同時保持算法效率基本不變。

選擇一個高質(zhì)量的u-shapelets集合是提高時間序列聚類準(zhǔn)確度的最佳手段，集合中的u-shapelets應(yīng)具備極具辨識度以及彼此互不相似的特點(diǎn)。滿足極具辨識度特性的一個u-shapelet在一定程度上能夠區(qū)分一個類，即一個u-shapelet只在某一類時間序列中普遍存在，而不存在于其他類時間序列中。如圖1為Trace數(shù)據(jù)集中的兩類時間序列，顯然圖1中標(biāo)識的u-shapelet能夠有效地區(qū)分兩類時間序列。子序列的辨識度由子序列的質(zhì)量來體現(xiàn)，一條子序列的質(zhì)量越高其辨識度越強(qiáng)?，F(xiàn)有的基于u-shapelet的時間序列聚類方法使用Gap值來評估一條子序列的質(zhì)量。Gap值只通過衡量被子序列劃分的兩個子集之間的分離度來確認(rèn)子序列的質(zhì)量，而本文認(rèn)為一個好的子序列質(zhì)量評估方法應(yīng)該同時考慮被劃分的子集之間的分離度以及子集內(nèi)部的緊密程度。為了確認(rèn)該想法的準(zhǔn)確性，本文研究了不同內(nèi)部聚類評價指標(biāo)對u-shapelet提取過程的影響。此外，為了得到最佳的u-shapelets集合，對u-shapelet候選集進(jìn)行去冗余操作是必不可少的步驟。而現(xiàn)有的去冗余方法過度依賴于前一步的劃分操作的結(jié)果，若劃分不正確將會降低最終聚類結(jié)果的準(zhǔn)確性，詳細(xì)分析見2.2節(jié)。

圖1 極具辨識度的u-shapelet示例Fig. 1 Best discriminating u-shapelet example

由此，為了解決目前質(zhì)量評估方法和去冗余方法篩選出的u-shapelets集合質(zhì)量較低而導(dǎo)致聚類準(zhǔn)確度不理想的問題，本文提出一種基于最佳u-shapelets的時間序列聚類算法。該算法主要從兩個方面完成最佳u-shapelets集合的篩選:首先，研究各類質(zhì)量評估方法的效用，以選擇最佳的質(zhì)量評估方法來盡可能準(zhǔn)確地評估u-shapelet候選集中子序列的質(zhì)量；其次，采用多元top-k查詢技術(shù)對u-shapelet候選集進(jìn)行處理，有效去除冗余子序列并篩選出最佳u-shapelets集合。綜上所述，本文的主要工作有：

1)研究使用不同子序列質(zhì)量評估方法對基于u-shapelets時間序列聚類結(jié)果的影響，并選出最佳的子序列質(zhì)量評估方法。

2)結(jié)合新的質(zhì)量評估方法，并引入多元top-k查詢技術(shù)來去除冗余的u-shapelet候選子序列，得到最佳u-shapelets集合。

3)將所提出的算法與其他基于u-shapelets的時間序列聚類算法以及經(jīng)典的時間序列聚類算法進(jìn)行對比，闡明本文算法在時間序列聚類方面的有效性。

1 u-shapelet相關(guān)定義及背景

1.1 相關(guān)定義

定義1 時間序列與子序列的距離sdist。假設(shè)子序列S的長度為l，時間序列T的長度為n，且l?n，時間序列T與子序列S之間的距離sdist為：sdist(S,T)=min(dist(S,Ti, j))。其中：Ti, j為時間序列T中長度為l的子序列，i表示子序列的在時間序列T中的起始位置。

定義2 候選u-shapelet。候選u-shapelet是一個由子序列S和距離閾值d組成的元組〈S,d〉。其中：子序列S是數(shù)據(jù)集D中任意一條時間序列內(nèi)任意位置上的子序列；距離閾值d可以將數(shù)據(jù)集D劃分為兩個子集DL和DR，子集DL和DR內(nèi)包含的時間序列的條數(shù)分別表示為nL、nR。

定義3 距離矩陣Dist。距離矩陣Dist是u-shapelets集合內(nèi)每個u-shapelet子序列到數(shù)據(jù)集D中每條時間序列的距離的集合。假設(shè)數(shù)據(jù)集D中存在N條時間序列，u-shapelets集合內(nèi)含有m個u-shapelet，則距離矩陣的大小為[N*m]。矩陣每列表示了一個u-shapelet到每條時間序列的距離的集合，表示為dis。

定義4 多元top-k查詢[11]。給定查詢對象集合G={v1,v2,…,vn}，每個在集合G中存在的對象vi均對應(yīng)一個分值score(vi)。對于集合中任意兩個對象vi、vj，給定一個用戶自定義的相似度函數(shù)sim(vi,vj) 以及閾值τ，如果存在sim(vi,vj)>τ，則對象vi與vj相似，表示為vi≈vj。

給定整數(shù)k(1≤k≤n)，多元top-k查詢即是為了從集合G中選出前k個分值最大且互不相似的對象集合C，其中C必須滿足以下三個條件：

1)C?G且|C|≤k;

2)對于任意對象vi∈C及對象vj∈G-C，滿足score(vi)>score(vj)，其中G-C={v|v∈G,v?C};

3)對于任意兩個對象vi,vj∈G且vi≠vj，如果存在vi≈vj,則{vi,vj}?C。

定義5 相似u-shapelet。給定兩個候選u-shapelet 〈S1,d1〉和〈S2,d2〉，如果兩個候選u-shapelet的距離dist(S1,S2)

定義6 最佳u-shapelets集合。存在u-shapelet候選集Candidates={s1,s2, …,sn}以及整數(shù)k(1≤k≤n)，對于u-shapelet候選集中的每條子序列均有其對應(yīng)的質(zhì)量Q(si)。最佳u-shapelets集合中存在的k個u-shapelet均滿足極具辨識度且互不相似的特點(diǎn)，即最佳u-shapelets集合Ush滿足以下條件：

1)Ush?Candidates且|Ush|≤k;

2)對于任意候選子序列si∈Ush及sj∈Candidates-Ush，如果存在si≈sj，則Q(si)>Q(sj)，其中Candidates-Ush={s|s∈Candidates,s?Ush}；

3)對于任意兩條候選子序列si,sj∈Candidates且si≠sj，如果存在si≈sj，則{si,sj}?Ush。

1.2 BruteForce算法

現(xiàn)有的基于u-shapelets的時間序列聚類方法都是在BruteForce算法[8]的基礎(chǔ)上進(jìn)行提速[9-10]，算法1中詳細(xì)介紹了BruteForce算法蠻力搜索u-shapelet的過程。

BruteForce算法使用迭代的方式搜索u-shapelets集合。每次迭代過程分為兩個階段：首先，算法1中的4)～9)行將數(shù)據(jù)集D中所有時間序列的子序列作為u-shapelet候選集，并對u-shapelet候選集中的所有子序列進(jìn)行質(zhì)量評估；其次，10)～19)行選取u-shapelet候選集中質(zhì)量最好的子序列作為u-shapelet，并使用θ值去除可能存在u-shapelet子序列的時間序列，更新數(shù)據(jù)集D中的時間序列數(shù)據(jù)。不斷循環(huán)整個過程直到在集合DL的大小為1時結(jié)束循環(huán)，并返回找到的u-shapelets集合。

BruteForce算法存在以下三個問題：

1)時間復(fù)雜度高。使用滑動窗口的方法產(chǎn)生子序列使u-shapelet候選集過于龐大,而查找一條u-shapelet需要對u-shapelet候選集中的所有子序列進(jìn)行質(zhì)量評估,且評估一條子序列所需的時間復(fù)雜度是O(nm2)(其中:n為時間序列數(shù)據(jù)集的大小，m為一條時間序列的長度)。

2)子序列質(zhì)量評估方法只考慮被子序列劃分的兩個子集之間的分離度。一個u-shapelet候選子序列利用一個距離閾值d將數(shù)據(jù)集D劃分為兩個子集DL和DR。BruteForce算法使用computeGap()方法評估兩個子集之間的分離度，并使用該分離度作為候選子序列的質(zhì)量而忽視了子集內(nèi)部的緊密度。本文認(rèn)為一個好的u-shapelet應(yīng)該能使其劃分的兩個子集之間達(dá)到最大分離度，并且子集內(nèi)部保證高緊密性。

3)θ值過度依賴于被劃分的子集DL。算法1中16)～18)行表明BruteForce算法使用θ值去除數(shù)據(jù)集D中可能存在u-shapelet子序列的時間序列，以此達(dá)到去除冗余候選子序列的目的。注意，每查找一個u-shapelet即需要重新評估u-shapelet候選集中所有子序列的質(zhì)量，θ值將會影響每次循環(huán)結(jié)束后u-shapelet候選集的大??；而θ值過度依賴于被劃分的子集DL，一旦劃分出現(xiàn)偏差，錯誤的θ值也將會影響其他u-shapelet的搜索，并直接影響到最終時間序列聚類的準(zhǔn)確度以及運(yùn)行時間。具體實(shí)驗(yàn)結(jié)果見3.2.2節(jié)。

為了解決以上三個問題，本文將采用新的u-shapelet質(zhì)量評估方法并引入多元top-k查詢方法對u-shapelet進(jìn)行搜索，以達(dá)到從提升u-shapelets集合整體質(zhì)量的角度提高時間序列聚類的準(zhǔn)確度的目的。

2 本文算法

本章將討論使用不同內(nèi)部聚類評價指標(biāo)作為子序列質(zhì)量評估方法對基于u-shapelets的時間序列聚類的影響，并找到一個最佳的子序列質(zhì)量評估方法；其次，本文將引入多元top-k查詢方法來去除冗余的u-shapelet候選子序列，并選擇一個高質(zhì)量的u-shapelets集合來提高時間序列聚類準(zhǔn)確度。

中國現(xiàn)有的文化創(chuàng)意產(chǎn)業(yè)園區(qū)可分為五大類，即產(chǎn)業(yè)型、混合型、藝術(shù)型、休閑娛樂型和地方特色型，每一類型的園區(qū)數(shù)目及比例如圖2所示[1].

2.1 子序列質(zhì)量評估方法研究

一個u-shapelet候選子序列cand能夠?qū)r間序列數(shù)據(jù)集D劃分為兩個子集DL和DR。而一個好的子序列質(zhì)量評估方法應(yīng)該同時考慮被子序列cand劃分的兩個子集間分離度以及子集內(nèi)部的緊密性。為了找到一個最佳的子序列質(zhì)量評估方法，本文將從子集間的分離度和緊密性兩個角度選擇三個常見的內(nèi)部聚類評價指標(biāo)進(jìn)行研究：均方根標(biāo)準(zhǔn)差(Root-Mean-Square STandard Deviation, RMSSTD)[12]、R平方(R-squared, RS)[13]以及I指標(biāo)(I index)[14]。

這三個內(nèi)部聚類評價指標(biāo)所涉及的定義及符號在基于u-shapelet的時間序列聚類方法中的表示如式(1)～(3)所示，注意三個內(nèi)部聚類評價指標(biāo)的評估對象是被子序列cand劃分的兩個子集DL和DR。其中：dis表示該子序列cand到數(shù)據(jù)集D中所有時間序列的距離的集合；n為數(shù)據(jù)集D的大??；g是距離集合dis的中心；P表示dis的維數(shù)，P=1；NC代表子集的個數(shù)，NC=2；Ci表示第i個子集；ci是第i個子集Ci的中心；文中選擇使用算數(shù)平均值來計算中心g和ci的值。

1)RMSSTD,衡量子集內(nèi)部的緊密性。

(1)

2)RS,衡量子集之間分離度的大小。

(2)

3)I指標(biāo)：同時考慮子集間的分離度和子集內(nèi)部的緊密性。

(3)

為了研究這三種內(nèi)部評價指標(biāo)在基于u-shapelets的時間序列聚類中的有效性，本文研究將從最終的時間序列聚類結(jié)果進(jìn)行判斷。本文使用文獻(xiàn)[10]中提出的算法SUSh(Scalable U-shapelet)進(jìn)行實(shí)驗(yàn)證明。SUSh算法需要用戶自定義u-shapelet的長度。為了實(shí)驗(yàn)結(jié)果的公平性，在驗(yàn)證四種方法(RMSSTD、RS、I指標(biāo)、Gap)時將采用相同的長度值。表1中顯示了四種評估方法在22個數(shù)據(jù)集上的具體性能，其中Total Wins一行標(biāo)明了四種評估方法在22個數(shù)據(jù)集上的取得最佳效果的數(shù)量；表2描述了22個數(shù)據(jù)集詳細(xì)情況(即每個時間序列數(shù)據(jù)集的大小、數(shù)據(jù)集中所包含的時間序列的類數(shù)、數(shù)據(jù)集中時間序列的長度)，對每個數(shù)據(jù)集的時間或精度上表現(xiàn)最佳的值加粗處理。在精度方面，I指標(biāo)在11個數(shù)據(jù)集上取得了最佳效果，且I指標(biāo)分別在19個數(shù)據(jù)集上超越了Gap、RMSSTD，并在13個數(shù)據(jù)集上超越了RS；其次是RS在7個數(shù)據(jù)集上取得了最佳效果，而RMSSTD的效果最差。從實(shí)驗(yàn)結(jié)果中可以看出，同時考慮子集內(nèi)部的緊密性和子集間的分離度取得的效果最好，其次是只考慮子集間的分離度，而只考慮子集內(nèi)的緊密度的效果最差。在時間方面，本研究中的四種評估方法所用的時間比較相近，四種子序列質(zhì)量評估方法在運(yùn)行時間上沒有明顯的差別。且本文的目的在于如何通過提升u-shapelets集合的整體質(zhì)量來提高基于u-shapelets的時間序列聚類方法的性能，因此在各類方法的時間相近的情況下本文將選擇聚類效果最佳的子序列質(zhì)量評估方法。如表1中所示，I指標(biāo)能夠在不增加運(yùn)行時間的情況下有效提升時間序列聚類的準(zhǔn)確度，因此本文認(rèn)為I指標(biāo)能夠更好地評估子序列的質(zhì)量，得到最具辨識度的u-shapelet。

表1 各質(zhì)量評估方法的準(zhǔn)確度與運(yùn)行時間對比Tab. 1 Comparison of clustering accuracy and discovery time for each quality measurement

表2 實(shí)驗(yàn)中使用的UCR數(shù)據(jù)集Tab. 2 UCR dataset used in the experiment

2.2 DivUshapCluster算法

一個好的子序列質(zhì)量評估方法能在一定程度上提升被選擇的u-shapelet的質(zhì)量。為了進(jìn)一步提高時間序列聚類的準(zhǔn)確率，本文從如何對u-shapelet候選集進(jìn)行去冗余操作著手，從中選擇k個最具辨識度且互不相似的u-shapelet組成最佳的u-shapelets集合。為了解決這個問題，本文引入多元top-k查詢方法提出DivUshapCluster算法以查找最佳的u-shapelets集合，并利用u-shapelets集合對應(yīng)的距離矩陣完成時間序列的聚類操作。多元top-k查詢技術(shù)[11]的核心思想是平衡查詢結(jié)果的相關(guān)性和多樣性，利用多樣化的搜索結(jié)果提升用戶對查詢結(jié)果的滿意度，即：從相關(guān)性和多樣性兩個方面對查詢結(jié)果進(jìn)行考慮找到k個相關(guān)度最大且互不相似的對象集合。多元top-k查詢技術(shù)已經(jīng)被應(yīng)用于多個領(lǐng)域，例如文檔查詢[15]、Web查詢[16]、圖搜索[17]等。本文提出的DivUshapCluster算法也旨在搜索到k個最具辨識度且互不相似的u-shapelet。

算法2詳細(xì)描述了具體過程。首先，在第2)行，本文使用滑動窗口技術(shù)對數(shù)據(jù)集D中的所有時間序列進(jìn)行預(yù)處理，產(chǎn)生固定長度的子序列集合，使用SAX表示每條子序列，并利用文獻(xiàn)[10]中的方法選擇部分子序列作為u-shapelet候選集。文獻(xiàn)[10]表明，這種選取部分子序列的方法能使u-shapelet的發(fā)現(xiàn)過程提速兩個數(shù)量級。在第3)～5)行，本文使用I指標(biāo)評估u-shapelet候選集中每條子序列的質(zhì)量，評估的具體過程在算法3中詳細(xì)描述。在得到u-shapelet候選集中所有子序列的質(zhì)量之后，本文將使用多元top-k查詢技術(shù)搜索k個最具辨識度且互不相似的u-shapelet。在6)～16)行，本文方法迭代地查詢最佳的u-shapelets集合。在每次迭代過程中，本文方法先從u-shapelet候選集中選取質(zhì)量最佳的子序列作為u-shapelet，隨后將去除u-shapelet候選集中與u-shapelet相似的子序列。不斷迭代搜索完k個u-shapelet后結(jié)束查詢。當(dāng)產(chǎn)生最佳的u-shapelets集合后，在17)～21)行，本文方法計算u-shapelets集合中每個u-shapelet到數(shù)據(jù)集D中的所有時間序列的距離，組成距離矩陣Dist。最后，在第22)行，使用傳統(tǒng)的聚類方法，比如k-means，對距離矩陣進(jìn)行聚類，得到時間序列數(shù)據(jù)集D最終的聚類結(jié)果。

算法2 DivUshapCluster(D,sLen,k,p)。

輸入 數(shù)據(jù)集D，子序列長度sLen，u-shapelets集合大小k，聚類個數(shù)p；

輸出 聚類結(jié)果Result。

1)Ush=?,i=1,DIS=[]

2)CandidateUsh=GenerateCandidates(D,sLen)

3) fori=1 to |CandidateUsh|

4) assessQuality(CandidateUsh[i],D)

5) end for

6) whilei

8) Ush.add(ush)

9)i=i+1

10) forj=1 to |CandidateUsh|

11) if(CandidateUsh[j]≈ush)

12) deletUsh.add(CandidateUsh[j])

13) end for

14)CandidateUsh=CandidateUsh-SubUsh

15) if |CandidateUsh|=0, break;

16) end while

17) forcnt=1 to |Ush|

18)ush=Ush[cnt]

19)dis=computeDistance(ush,D)

20)Dist=[Distdis]

21) end for

22) [cluster_centers,Result]=k-means(Dist,p)

23) returnResult

算法3是評估一條u-shapelet候選子序列質(zhì)量的具體過程。首先，計算候選子序列ush到數(shù)據(jù)集D中所有時間序列的距離，并對這一系列距離進(jìn)行排序得到該候選子序列ush對應(yīng)的距離集合dis。隨后，在4)～17)行，每個可能的距離閾值d把距離集合dis分為兩個子集disDR和disDL。注意，假設(shè)數(shù)據(jù)集D中存在N條時間序列，則一個候選子序列對應(yīng)的距離集合dis中將存在N個距離值，而距離閾值d的可能取值有N-1個。利用I指標(biāo)衡量每個閾值d劃分后的結(jié)果，并選擇最大的I值作為該候選子序列的質(zhì)量，并得到該候選子序列對應(yīng)的元組(ush,d)。

算法3 assessQuality(ush,Data)。

輸入 候選子序列ush，數(shù)據(jù)集D；

輸出 候選子序列ush的質(zhì)量quality。

1)dis=computeDistance(ush,D);

2)disSorted=sort(dis);

3)quality=0;

4) forl=1 to |dis|-1

5)d=dis(l);

6)disDR=find(disSorted

7)disDL=find(disSorted>d);

8)r=|disDR|/|disDL|;

9) if 1/k

10)ma=mean(disSorted(Dr));

mb=mean(disSorted(Dl));

11)m=mean(disSorted);

12)U=sum(abs(dis-m))*abs(ma-mb);

13)B=sum(abs(disDR-ma))+sum(abs(disDL-mb));

14)I=U/(2*B);

15) end if

16) ifI>quality,quality=I;

17) end for

18) returnquality

為了更直觀地說明DivUshapCluster算法，圖2展示了DivUshapCluster算法在Coffee數(shù)據(jù)集上的聚類效果。

圖2 DivUshapCluster算法在Coffee數(shù)據(jù)集上的聚類效果Fig. 2 Clustering results of DivUshapCluster method on Coffee dataset

Coffee數(shù)據(jù)集中有56條時間序列，每條時間序列的長度為286，Coffee數(shù)據(jù)集中的時間序列分為兩個類，圖2(a)中展現(xiàn)了兩個類中時間序列的代表形狀。設(shè)定子序列的長度為50，DivUshapCluster算法使用多元top-ku-shapelet查詢技術(shù)從13 272條子序列中篩選出2條最具代表性且互不相似的子序列組成u-shapelets集合，圖2(a)中標(biāo)識部分即為DivUshapCluster算法篩選出的兩個u-shapelet。圖2(b)中展現(xiàn)的是利用u-shapelets集合得到的Coffee數(shù)據(jù)集所對應(yīng)的距離矩陣，從圖2(b)中可以清晰地看出，使用傳統(tǒng)的聚類方法，形如k-means方法，可以對距離矩陣進(jìn)行聚類，并得到很好的時間序列聚類效果。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的DivUshapCluster時間序列聚類算法的有效性，將DivUshapCluster算法、文獻(xiàn)[8]中的BruteForce算法、文獻(xiàn)[10]中的SUSh算法以及三個經(jīng)典的聚類算法(k-means、層次聚類、譜聚類)進(jìn)行對比。

3.1 實(shí)驗(yàn)數(shù)據(jù)集與參數(shù)

實(shí)驗(yàn)由Window 10操作系統(tǒng)，Intel Core i5- 3470 CPU 3.20 GHz, 4 GB 內(nèi)存以及Matlab R2012b作為實(shí)驗(yàn)環(huán)境。為了闡明DivUshapCluster方法在時間序列聚類問題上的效果，本文選用了美國加州大學(xué)濱河分校(University of California Riverside, UCR)的時間序列數(shù)據(jù)集合[18]中的22個通用的數(shù)據(jù)集作為實(shí)驗(yàn)對象(表2中說明了22個時間序列數(shù)據(jù)集的詳細(xì)信息)。且根據(jù)2.1節(jié)的結(jié)論，本文中的所有實(shí)驗(yàn)將采用I指標(biāo)作為子序列質(zhì)量的評估手段。

DivUshapCluster算法存在3個參數(shù)：時間序列子序列的長度值sLen、u-shapelets集合的大小k以及最終聚類個數(shù)p。不同數(shù)據(jù)集中的時間序列具有不同的長度及特性，難以統(tǒng)一所有時間序列數(shù)據(jù)集的子序列長度。表3中sLen列給出了DivUshapCluster算法在22個時間序列數(shù)據(jù)集上所選用的子序列長度值。最終聚類個數(shù)p也將由用戶自定義，實(shí)驗(yàn)中使用時間序列數(shù)據(jù)集中實(shí)際類的個數(shù)作為p的取值。其次，u-shapelets集合的大小k在一定程度上將會影響最終聚類的效果，k值過小將會使找到的u-shapelets集合難以代表數(shù)據(jù)集中每類時間序列的特性。為了得到最佳的k值，本文研究了在22個數(shù)據(jù)集上不同k值對整體聚類準(zhǔn)確度的影響，圖3展示了k值變化時，在22個數(shù)據(jù)集上平均聚類準(zhǔn)確度的變化趨勢。從圖3中可以明顯觀察到：隨著k值的增長，平均聚類準(zhǔn)確度在不斷攀升，直到k值達(dá)到10以后，k值的增長不再影響平均聚類準(zhǔn)確度。因此，為了保持實(shí)驗(yàn)內(nèi)容的一致性，將統(tǒng)一采用k=10完成接下來的實(shí)驗(yàn)。

圖3 22個數(shù)據(jù)集上平均聚類準(zhǔn)確度隨k值的變化曲線Fig. 3 Curve of the average clustering accuracy on 22 datasets changing with the value of k

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

3.2.1 準(zhǔn)確度對比

為了驗(yàn)證本文提出的DivUshapCluster算法能夠有效提高時間序列聚類的準(zhǔn)確度，本節(jié)將DivUshapCluster算法與文獻(xiàn)[8]中的BruteForce算法、文獻(xiàn)[10]中的SUSh算法以及三個經(jīng)典的聚類算法(k-means、層次聚類、譜聚類)進(jìn)行對比，并使用Rand index作為聚類結(jié)果的評價指標(biāo)，結(jié)果如表3所示，其中Total Wins一行標(biāo)明了各種聚類算法在22個數(shù)據(jù)集上的取得最佳效果的數(shù)量。

表3 DivUshapCluster算法與對比算法在22個數(shù)據(jù)集上的聚類準(zhǔn)確度對比Tab. 3 Clustering accuracy comparison of DivUshapCluster and contrast algorithms on 22 datasets

表3中顯示在22個時間序列數(shù)據(jù)集中本文提出的DivUshapCluster算法分別在17個數(shù)據(jù)集上優(yōu)于BruteForce算法、SUSh算法，可以觀察到在其中6個數(shù)據(jù)集上DivUshapCluster 算法的準(zhǔn)確度較前兩者均提升了30%。顯而易見，本文提出的DivUshapCluster 算法能夠有效提高基于u-shapelets的時間序列聚類的準(zhǔn)確度。此外，在與經(jīng)典的聚類算法進(jìn)行對比上，表3顯示DivUshapCluster算法分別在16、16、14個時間序列數(shù)據(jù)集上優(yōu)于層次聚類算法、譜聚類算法以及k-means算法。結(jié)果表明，雖然每個算法都能在不同的數(shù)據(jù)集上取得最佳聚類效果，但是DivUshapCluster算法的整體效果最佳。

3.2.2 運(yùn)行時間對比

BruteForce算法和SUSh算法都是基于u-shapelets的時間序列聚類方法，而文獻(xiàn)[10]中的研究結(jié)果表明，SUSh算法在運(yùn)行速度上比BruteForce算法快兩個數(shù)量級。因此，本節(jié)主要對比SUSh算法與DivUshapCluster算法在22個時間序列數(shù)據(jù)集上的運(yùn)行時間，結(jié)果如表4所示，可以看出DivUshapCluster算法在大部分?jǐn)?shù)據(jù)集上都略快于SUSh算法。

表4 DivUshapCluster算法與SUSh算法在22個數(shù)據(jù)集上的運(yùn)行時間對比Tab. 4 Running time comparison between DivUshapCluster and SUSh on 22 datasets

為了更詳細(xì)地對比DivUshapCluster與SUSh算法，本文選取UCR時間序列數(shù)據(jù)集中較大的兩個數(shù)據(jù)集Cricket_X和SwedishLeaf進(jìn)行對比實(shí)驗(yàn)，其中子序列長度均設(shè)置為35。圖4展示了運(yùn)行時間隨兩個數(shù)據(jù)集中時間序列的數(shù)量變化的曲線，圖5展示了時間序列聚類準(zhǔn)確率隨兩個數(shù)據(jù)集中時間序列的數(shù)量變化的曲線。

圖4 DivUshapCluster與SUSh算法關(guān)于數(shù)據(jù)集大小影響運(yùn)行時間的比較Fig. 4 Time comparison between DivUshapCluster and SUSh with different dataset size

圖5 DivUshapCluster與SUSh算法關(guān)于數(shù)據(jù)集大小影響準(zhǔn)確度的比較Fig. 5 Accuracy comparison between DivUshapCluster and SUSh with different dataset size

圖4(a)中，當(dāng)Cricket_X數(shù)據(jù)集中時間序列數(shù)量不斷增加時，SUSh算法的運(yùn)行時間從9 s增長到了22 min,而DivUshapCluster算法則是從15 s增長到了7 min。DivUshapCluster算法運(yùn)行時間的增長幅度小于SUSh算法的原因是：盡管兩個算法都只選取了小部分的時間序列子序列作為u-shapelet候選集，但是SUSh算法和BruteForce算法一樣，每提取一個u-shapelet都需要重新對u-shapelet候選集中的子序列進(jìn)行質(zhì)量評估，見算法1；而DivUshapCluster算法則只需要對u-shapelet候選集評估一次。此外，SUSh算法中去除冗余子序列的方法也源于BruteForce算法，第2章中討論了這種不恰當(dāng)?shù)娜ト哂喾绞綄绊懙絬-shapelet的選取，并最終影響時間序列聚類的時間與準(zhǔn)確度。從圖4(b)中也可觀察到雖然兩個算法在運(yùn)行時間上十分相近，但是如圖5(b)中所示，DivUshapCluster算法的時間序列聚類準(zhǔn)確度遠(yuǎn)遠(yuǎn)高于SUSh算法的準(zhǔn)確度。

4 結(jié)語

為了解決u-shapelets集合質(zhì)量較低的問題，本文提出一種基于最佳u-shapelets的時間序列聚類算法。該方法選用I指標(biāo)對u-shapelet候選集進(jìn)行質(zhì)量評估，并使用多元top-k查詢技術(shù)從u-shapelet候選集中篩選出最佳u-shapelets集合，利用最佳u-shapelets集合對數(shù)據(jù)集進(jìn)行轉(zhuǎn)換并實(shí)現(xiàn)后續(xù)聚類。通過與傳統(tǒng)時間序列聚類算法以及現(xiàn)有的BruteForce算法和SUSh算法進(jìn)行比較，可以得出本文算法能夠在保證整體效率的情況下有效提高時間序列的聚類準(zhǔn)確度。在后續(xù)的研究中，將考慮如何進(jìn)一步提升效率。

References)

[1] RUIZ E J, HRISTIDIS V, CASTILLO C, et al. Correlating financial time series with micro-blogging activity [C]// WSDM 2012: Proceeding of the fifth ACM International Conference on Web Search and Data Mining. New York: ACM, 2012:513-522.

[2] HONDA R, WANG S, KIKUCHI T, et al. Mining of moving objects from time-series images and its application to satellite weather imagery [J]. Journal of Intelligent Information Systems, 2002, 19(1): 79-93.

[3] HIRANO S, TSUMOTO S. Cluster analysis of time-series medical data based on the trajectory representation and multiscale comparison techniques [C]// ICDM 2006: Proceedings of the Sixth International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2006: 896-901.

[4] JIANG D, PEI J, RAMANATHAN M, et al. Mining gene-sample-time microarray data: a coherent gene cluster discovery approach [J]. Knowledge and Information Systems, 2007, 13(3): 305-335.

[5] YE L, KEOGH E. Time series shapelets: a novel technique that allows accurate, interpretable and fast classification [J]. Data Mining and Knowledge Discovery, 2011, 22(1/2): 149-182.

[6] 原繼東,王志海,韓萌.基于Shapelet剪枝和覆蓋的時間序列分類算法[J].軟件學(xué)報,2015,26(9):2311-2325. (YUAN J D, WANG Z H, HAN M. Shapelet pruning and Shapelet coverage for time series classification [J]. Journal of Software, 2015, 26(9): 2311-2325.)

[7] 孫其法,閆秋艷,閆欣鳴.基于多樣化top-kshapelets轉(zhuǎn)換的時間序列分類方法[J].計算機(jī)應(yīng)用,2017,37(2):335-340. (SUN Q F, YAN Q Y, YAN X M. Diversified top-kshapelets transform for time series classification [J]. Journal of Computer Applications, 2017, 37(2): 335-340.)

[8] ZAKARIA J, MUEEN A, KEOGH E. Clustering time series using unsupervised-shapelets [C]// ICDM 2012: Proceedings of the IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 785-794.

[9] ZAKARIA J, MUEEN A, KEOGH E, et al. Accelerating the discovery of unsupervised-shapelets [J]. Data Mining and Knowledge Discovery, 2016, 30(1): 243-281.

[10] ULANOVA L, BEGUM N, KEOGH E. Scalable clustering of time series with u-shapelets [C]// SDM 2015: Proceedings of the 2015 SIAM International Conference on Data Mining. Philadelphia, PA: SIAM, 2015: 900-908.

[11] QIN L, YU J X, CHANG L. Diversifying top-kresults [J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1124-1135.

[12] HALKIDI M, BATISTAKIS Y, VAZIRGIANNIS M, et al. On clustering validation techniques [J]. Journal of Intelligent Information Systems, 2001, 17(2): 107-145.

[13] HASSANI M, SEIDL T. Internal clustering evaluation of data streams [C]// PAKDD 2015 Workshops: Proceedings of the 2015 Trends and Applications in Knowledge Discovery and Data Mining, LNCS 9441. Berlin: Springer-Verlag, 2015: 198-209.

[14] MAULIK U, BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12): 1650-1654.

[15] ZHANG Y, CALLAN J, MINKA T. Novelty and redundancy detection in adaptive filtering [C]// SIGIR ’02: Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2002: 81-88.

[16] AGRAWAL R, GOLLAPUDI S, HALVERSON A, et al. Diversifying search results [C]// WSDM ’09: Proceeding of the Second ACM International Conference on Web Search and Data Mining. New York: ACM, 2009: 5-14.

[17] YUAN L, QIN L, LIN X, et al. Diversified top-kclique search [J]. The VLDB Journal, 2016, 25(2): 171-196.

[18] CHEN Y, KEOGH E, HU B, et al. The UCR time series classification archive [DB/OL]. [2015- 07- 01]. www.cs.ucr.edu/～eamonn/time_series_data/.

This work is partially supported by the National Natural Science Foundation of China (51674255), the Natural Science Foundation of Jiangsu Province of China (BK20140192).

YUSiqin, born in 1995, M. S. candidate. Her research interests include time series data mining.

YANQiuyan, born in 1978, Ph. D., associate professor. Her research interests include time series data mining, machine learning.

YANXinming, born in 1993, M. S. candidate. Her research interests include time series data mining.

Clusteringalgorithmoftimeserieswithoptimalu-shapelets

YU Siqin*, YAN Qiuyan, YAN Xinming

(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221116,China)

Focusing on low quality of u-shapelets (unsupervised shapelets) in time series clustering based on u-shapelets, a time series clustering method based on optimal u-shapelets named DivUshapCluster was proposed. Firstly, the influence of different subsequence quality assessment methods on time series clustering results based on u-shapelets was discussed. Secondly, the selected best subsequence quality assessment method was used to evaluate the quality of the u-shapelet candidates. Then, the diversified top-kquery technology was used to remove redundant u-shapelets from the u-shapelet candidates and select the optimal u-shapelets. Finally, the optimal u-shapelets set was used to transform the original dataset, so as to improve the accuracy of the time series clustering. The experimental results show that the DivUshapCluster method is superior to the traditional time series clustering methods in terms of clustering accuracy. Compared with the BruteForce method and the SUSh method, the average clustering accuracy of DivUshapCluster method is increased by 18.80% and 19.38% on 22 datasets, respectively. The proposed method can effectively improve the clustering accuracy of time series in the case of ensuring the overall efficiency.

time series; clustering; u-shapelets; internal clustering evaluation measurement; diversified top-kquery

TP311.13

A

2017- 01- 10;

2017- 02- 22。

國家自然科學(xué)基金資助項(xiàng)目(51674255)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK20140192)。

余思琴(1995—)，女，江西萍鄉(xiāng)人，碩士研究生，主要研究方向：時間序列數(shù)據(jù)挖掘； 閆秋艷(1978—)，女，江蘇徐州人，副教授，博士，主要研究方向：時間序列數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí) 閆欣鳴(1993—)，女，江蘇徐州人，碩士研究生，主要研究方向：時間序列數(shù)據(jù)挖掘。

1001- 9081(2017)08- 2349- 08

10.11772/j.issn.1001- 9081.2017.08.2349