LS-Cluster:大規(guī)模多變量時間序列聚類方法

鄭 誠 王 鵬 汪 衛(wèi)

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 201203) (復(fù)旦大學(xué)上海市數(shù)據(jù)科學(xué)重點實驗室 上海 201203)

LS-Cluster:大規(guī)模多變量時間序列聚類方法

鄭 誠 王 鵬 汪 衛(wèi)

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院 上海 201203) (復(fù)旦大學(xué)上海市數(shù)據(jù)科學(xué)重點實驗室 上海 201203)

現(xiàn)有的關(guān)于多變量時間序列聚類的研究中所研究的變量規(guī)模均較少，而現(xiàn)實生活又經(jīng)常會出現(xiàn)大規(guī)模多變量時間序列，因此提出了LS-Cluster算法，旨在對有上萬變量的大規(guī)模多變量時間序列進行聚類。首先，將每個時刻的多變量時間序列轉(zhuǎn)化成矩形網(wǎng)格，然后使用二維離散余弦變換對其進行特征提取。接著提出了LS相似度用于計算特征序列之間的相似程度。最后，采用層次聚類方法發(fā)現(xiàn)其中所蘊含的模式。實驗結(jié)果顯示，該方法在人工合成數(shù)據(jù)和真實數(shù)據(jù)上都有較好的效果和可擴展性。

大規(guī)模 多變量時間序列 離散余弦變換 LS相似度 聚類

0 引 言

在現(xiàn)實生活中，經(jīng)常會出現(xiàn)同一時刻產(chǎn)生多個數(shù)據(jù)值的情況，這些數(shù)據(jù)值共同描述了當(dāng)前的狀態(tài)。例如在有上千個傳感器結(jié)點的大規(guī)模傳感器網(wǎng)絡(luò)中，同一時刻會有上千個數(shù)據(jù)產(chǎn)生，這些數(shù)據(jù)共同描述了當(dāng)前傳感器網(wǎng)絡(luò)的狀態(tài)。又如在金融領(lǐng)域中，滬深股市共有2 000多支股票，在交易時間段內(nèi)每一時刻就會產(chǎn)生2 000多個價格，這2 000多個價格共同描述了當(dāng)前股市的狀態(tài)。這些狀態(tài)按照時間順序排列就構(gòu)成了一條序列，這種序列就叫作多變量時間序列。多變量時間序列廣泛存在于金融、傳感器網(wǎng)絡(luò)、醫(yī)療等各種領(lǐng)域。本文旨在對這種有上千甚至上萬個變量的大規(guī)模多變量時間序列進行聚類分析。對大規(guī)模傳感器網(wǎng)絡(luò)多變量時間序列以天為周期進行聚類，我們可以得到一年中哪些天的傳感器狀態(tài)是相似的，這對傳感器網(wǎng)絡(luò)的監(jiān)測和維護有著重要的意義。對股票行情數(shù)據(jù)以交易日為周期進行聚類，我們可以得到一年中哪些交易日的行情是相似的，這可以作為投資者投資和決策的參考依據(jù)。在已有的研究工作中，其研究的多變量時間序列的變量數(shù)目均很少，在這些已有研究所使用的數(shù)據(jù)集中，變量數(shù)目最多的是EEG數(shù)據(jù)集[1]，有64個變量。而在現(xiàn)實生活中又經(jīng)常會出現(xiàn)有上千甚至上萬變量的大規(guī)模多變量時間序列的數(shù)據(jù)，并且變量之間有一定的相關(guān)性。例如在大規(guī)模傳感器網(wǎng)絡(luò)、股票行情和大型服務(wù)器機房監(jiān)控等數(shù)據(jù)中，變量數(shù)就有可能會達到上千甚至上萬。因此有必要研究在大規(guī)模多變量時間序列下的聚類方法。本文中，我們提出了LS-Cluster聚類方法，和之前的研究工作不同，我們主要聚焦于處理變量數(shù)目非常多的大規(guī)模多變量時間序列，例如數(shù)千甚至上萬個變量的多變量時間序列，并且方法考慮了變量之間的相關(guān)性。

首先，將多變量時間序列中每個時刻的每個變量的值放入矩形網(wǎng)格中，使得每個時刻的數(shù)據(jù)都形成一個矩形網(wǎng)格，然后我們使用二維離散余弦變換來對矩形網(wǎng)格提取特征，得到一個特征矩陣。從一個時刻到另一時刻的特征矩陣的變換可以看成是高維空間中的一個向量，我們把這種向量稱為線段，所有的線段的序列我們稱之為線段序列。從而，多變量時間序列可以用高維空間的線段序列來表示。為了進行聚類分析，我們提出了LS相似度來計算線段序列之間的相似程度，最后我們采用層次聚類來發(fā)現(xiàn)其中的模式并找出其中的離群點。

實驗環(huán)節(jié)中，我們采取人工合成數(shù)據(jù)和金融數(shù)據(jù)來驗證我們的方法。在人工合成數(shù)據(jù)上的實驗結(jié)果顯示我們的方法比其他的方法有更好的聚類效果和可擴展性。進一步的，我們在2008年上海證券交易所的1 120支股票行情數(shù)據(jù)上進行了實驗。我們發(fā)現(xiàn)聚類結(jié)果和上證指數(shù)有著較高的一致性，并發(fā)現(xiàn)了一些離群點，說明了我們的方法得到了較好的聚類效果。

1 問題定義和相關(guān)工作

1.1 問題定義

1.2 相關(guān)工作

文獻[2]把構(gòu)成多變量時間序列的每個單變量時間序列分別進行離散傅里葉變換，把變換后的結(jié)果分別保留前幾個系數(shù)，并把這些系數(shù)連接起來作為特征。該方法把多變量拆分為單變量，使用單變量的特征提取方法進行特征提取，但是其忽略了變量之間的相關(guān)性。主成分分析(PCA)[3]是常用的多變量時間序列的特征提取方法，該方法通過尋找正交的方向向量，構(gòu)成一個低維的特征空間，讓各變量作為一個整體在該低維特征空間進行投影，從而得到一些新的互不相關(guān)的新的變量。該方法考慮了多變量之間的相關(guān)性，但對于不同的MTS其得到的新變量意義不同，破壞了MTS的同構(gòu)性[4]。

Guan等提出了一種稱為交叉相關(guān)系數(shù)矩陣的相似性度量方法[5]。文獻[6]中，作者提出了一種基于主成分分析(PCA)的相似度度量方法Eros，用于度量多變量時間序列數(shù)據(jù)的相似度。文獻[7]提出了一種基于點分布特征的匹配方法(PD)，使用局部重要點來表示MTS，然而這樣會導(dǎo)致丟失變量之間關(guān)聯(lián)信息。文獻[8]提出了一種基于二維SVD的相似度匹配方法——2DSVD，通過MTS的行-行和列-列協(xié)方差矩陣來得到特征向量，并利用Euclid范數(shù)來度量特征的相似度。

Yang和Zhou等提出了一種名叫HcluStream的聚類算法[9]。在文獻[10]的研究中，采用基于分割的兩步過程對多變量時間序列進行挖掘。Huang等使用樸素貝葉斯方法對時間序列進行聚類[11]。Owsley等使用隱馬爾科夫模型來聚類多變量時間序列[12]。文獻[13]中提出了基于PCA和K-Means的PCA-CLUSTER聚類算法。

2 提出的方法

2.1 概 述

首先，我們將多變量時間序列每個時刻所有變量的值都轉(zhuǎn)化成矩形網(wǎng)格的形式。第二步，對矩形網(wǎng)格進行二維離散余弦變換，將變換后得到的系數(shù)矩陣的左上角的p×q部分作為特征矩陣。從一個時刻到另外一個時刻的特征矩陣可以形成一個高維空間中的向量，我們稱這個向量為線段。所有的向量構(gòu)成了一條線段序列。第三步，使用本文提出的LS相似度(LineSequenceSimilarityMeasure)來計算任意兩條線段序列之間的相似度以得到相似度矩陣。最后，通過第三步得到的相似度矩陣使用層次聚類方法進行聚類。

2.2MTS的矩形網(wǎng)格表示

為了對大規(guī)模多變量時間序列進行聚類分析，首先需要對其進行轉(zhuǎn)換。方法是將MTS中每個時刻所有變量的值放入一個矩形網(wǎng)格中。例如有10 000個變量就可以一一對應(yīng)放入100×100的網(wǎng)格中，變量放置的次序可以是任意的，只要每次都將同一變量放在同一位置即可。

2.3 基于二維離散余弦變換的特征提取

通過上一步的方法，將每個時刻的序列值轉(zhuǎn)換成了一個矩形網(wǎng)格，為了更好地進行相似度的計算，我們需要進行特征提取，提取出主要信息，忽略細節(jié)和噪聲。這里我們使用二維離散余弦變換DCT來進行特征提取。使用二維DCT不僅能夠進行降維，而且考慮了多變量之間的關(guān)聯(lián)性，相比于其他的一維方法，能夠使特征更加明顯。

離散余弦變換最早是由Ahmed于1974年提出的[14]，作為一種實數(shù)域變換，DCT克服了離散傅里葉變換中復(fù)數(shù)域的缺點，因此被廣泛運用于數(shù)據(jù)壓縮、特征提取中。

DCT有多種表示形式，以下給出其中一種表示，假設(shè)矩形網(wǎng)格的規(guī)模是m×n，其二維DCT公式為：

(1)

其逆變換是：

(2)

其中：

根據(jù)DCT的意義，原先m×n的矩陣經(jīng)過DCT變換后得到系數(shù)矩陣的大小也是m×n，其中低頻信息集中在左上角，高頻信息集中在右下角，要提取特征只需要保留低頻部分，去掉高頻部分。因此，我們只保留左上角的p×q部分，其中1

2.4LS相似度

為了詳細闡述LS相似度的定義，首先定義下面的一些概念。

(1) 矩形網(wǎng)格 一個多變量時間序列在某一時刻所有變量的值一一對應(yīng)放入一個網(wǎng)格形成了一個矩形網(wǎng)格。

(2) 點(Point) 一個點是從一個矩形網(wǎng)格提取出來的維度是p×q的特征矩陣，如圖1中的p1。

(4) 線段序列(LineSequence) 由高維空間中線段首尾相接組成，如圖1中p1到p7之間所有線段首尾相接組成了一個線段序列。

因為一個矩形網(wǎng)格可以用一個高維特征矩陣來壓縮表示，所以MTS可以用高維空間的線段序列來表示。如圖1所示，對于一個點pi，它表示從時刻i的矩形網(wǎng)格所提取出來的特征矩陣。

圖1 MTS用高維空間的線段序列表示

如圖2所示，給定兩個線段序列S1和S2，他們之間的相似度計算公式如下：

(3)

圖2 兩個線段序列

如圖3所示，X1X2和Y1Y2分別是線段序列S1和S2中的線段，它們是一對線段對。它們之間的相似度為：

(4)

d1=|X1-Y1|=∑i,j|MX1(i,j)-MY1(i,j)|

(5)

d2=|X2-Y2|=∑i,j|MX2(i,j)-MY2(i,j)|

(6)

在上述公式中，(i,j)是特征矩陣MX1和MY1的索引。

圖3 兩個線段的距離

因此：

其中‖*‖表示一個線段的長度。

通過使用MX1、MX2、MY1和MY2取代上述公式中的X1、X2、Y1、Y2得到：

MY2(k,l)-MX1(k,l)|

2.5LS-Cluster聚類方法

離群點的存在破壞了數(shù)據(jù)內(nèi)在的一致性，導(dǎo)致了不可靠的結(jié)果，也降低了模式挖掘的有效性。然而，層次聚類算法[15]可以很好地發(fā)現(xiàn)數(shù)據(jù)蘊含的模式同時找到離群點。所以，我們LS-Cluster基于層次聚類算法來挖掘時間序列的模式并檢測離群點。

在聚類之前，我們先使用LS相似度計算每兩個線段序列之間的相似度從而構(gòu)建相似度矩陣，之后需要對該矩陣進行歸一化，具體的做法就是將相似度矩陣中所有的值通過以下公式轉(zhuǎn)化成之間的值：

x′=(x-xmin)/(xmax-xmin)

(7)

其中，x是原相似度，x′是歸一化后的相似度，xmax和xmin分別為相似度矩陣中的最大值和最小值。

歸一化后即可開始進行聚類操作，聚類算法的步驟如下：首先，把每個線段序列都看成一個簇，在每次迭代中，算法將相似度最高的兩個簇合并，然后更新相似度矩陣。假設(shè)Ci和Cj是兩個簇，他們的相似度是他們的組平均，計算公式定義如下:

(8)

其中，mi和mj分別是兩個簇Ci和Cj中線段序列的數(shù)目。兩個簇之間的相似度是兩個簇的所有點對的相似度的均值。為了避免將所有的線段序列合并成一個簇，我們設(shè)置了一個聚類數(shù)K，當(dāng)簇的數(shù)目達到K時即停止合并。一旦聚類完成，含有大量的線段序列的簇被看成是正常模式，而含有少量線段序列的簇則被認為是離群點。

3 實 驗

我們分別使用人工合成數(shù)據(jù)和2008年上海證券交易所1 120支股票的行情數(shù)據(jù)對我們的方法進行測試。所有實驗的硬件環(huán)境為Inteli5-3470主頻3.2GHz、8GB內(nèi)存、1TB硬盤，操作系統(tǒng)為Windows10，代碼使用Python2.7進行實現(xiàn)。

3.1 人工合成數(shù)據(jù)

由于本文主要聚焦于大規(guī)模多變量的時間序列，變量的數(shù)目可以達到幾千甚至上萬。所以許多的數(shù)據(jù)集對本方法來說并不合適。因此在本試驗中，我們通過模擬傳感器網(wǎng)絡(luò)來生成測試數(shù)據(jù)。

假設(shè)有m×n個傳感器，我們使用以下四種不同的模型來模擬生成多變量時間序列數(shù)據(jù)。數(shù)據(jù)生成的具體方法是，對于同一個傳感器網(wǎng)絡(luò)，每個傳感器結(jié)點都使用相同的模型來進行數(shù)據(jù)生成，但對于不同結(jié)點使用隨機生成的不同參數(shù)。四種數(shù)據(jù)生成模型如下：

(1) 隨機游走時間序列模型：時間序列的首個值從[-10,10]中隨機選取，其后每個值均從前一值的偏移量在[-5,5]中隨機選取，圖4是某個傳感器首個值取-5.38時的圖像。

圖4 隨機游走時間序列模型

(2) 單一高斯時間序列模型：時間序列中的值從一個高斯分布中隨機選取，而這個高斯分布的均值從[-10,10]中隨機選取，標(biāo)準(zhǔn)差從[1,5]中隨機選取，圖5是某個傳感器均值取6.86，標(biāo)準(zhǔn)差取2.11時的圖像。

圖5 高斯時間序列模型

(3) 多段高斯時間序列模型： 時間序列隨機由多個連續(xù)的單一高斯模型序列片段連接而成，序列片段數(shù)從[5,10]中隨機選取，圖6是某個傳感器序列片段數(shù)取4時的圖像。

圖6 多段高斯時間序列模型

(4) 混合正弦時間序列模型： 時間序列是基于多個正旋波疊加的曲線采樣生成。這些正弦波的周期從[5,10]中隨機選取，振幅從[5,10]中隨機選取，正弦波的個數(shù)從[2,10]，某個傳感器的圖像如圖7所示。

圖7 混合正弦時間序列模型

對于上述4種模型都各產(chǎn)生50條序列，4個模型一共是200條序列，每條序列的長度取100。為了驗證我們提出的LS相似度的可擴展性，我們把LS相似度與文獻[7]提出的PD匹配方法以及文獻[8]提出的2DSVD匹配方法進行了比較，其中LS相似度特征矩陣的規(guī)模p和q均取max(5,m/10)，PD方法的參數(shù)取i1=i2=4，j1=j2=2，分位點采用極小值、5%、10%、25%、50%、75%、90%、95%和極大值共9個。2DSVD方法參數(shù)取r=33,s=4。

表1比較了三種方法在不同傳感器規(guī)模下計算兩個MTS間的相似度所花費的時間。在傳感器規(guī)模在10×10的情況下，LS所花費時間稍微比PD和2DSVD多一些，然而隨著傳感器規(guī)模的增大，LS顯示出比2DSVD和PD更好的性能。由此可見，LS相似度在對大規(guī)模多變量時間序列的處理上有著較好的可擴展性。

表1 計算兩個MTS的相似度所花費的時間 s

在準(zhǔn)確性方面，我們使用F度量來對聚類的效果進行評估，F(xiàn)度量基于精度和召回率，是兩者的綜合評價。對于已知劃分{P1,P2,…Pj,…,Pn}和聚類得到的簇{C1,C2,…,Ci,…,Cm}，其精度、召回率和F度量定義如下：

精度：

(9)

召回率：

(10)

F度量：

(11)

利用式(11)，我們對于每個預(yù)先標(biāo)注的Pj，可以得到其F度量：

F(Pj)=max1≤i≤mF(Pj,Ci)

(12)

對所有的簇進行F度量加權(quán)平均就得到了整個聚類結(jié)果的總F度量：

(13)

分別使用LS、PD和2DSVD三種方法作為相似性度量，采用組平均來計算合并后的簇間相似度，使用凝聚層次聚類來考察不同時間序列長度下三種方法聚類的加權(quán)平均F度量。使用傳感器的規(guī)模是100×100，聚類簇的個數(shù)均為4，結(jié)果如圖8所示。橫坐標(biāo)表示MTS的長度，縱坐標(biāo)表示聚類的總F度量。結(jié)果顯示，LS的效果在不同序列長度下表現(xiàn)均為最優(yōu)，2DSVD次之，PD最差，并且LS和2DSVD聚類方法的總F度量隨著序列長度有增大的趨勢，而PD方法的總F度量隨著序列的長度有所降低。由此可以得出，PD只適合應(yīng)用在小規(guī)模的多變量時間序列，不適用應(yīng)用在規(guī)模較大的多變量時間序列上，而本文提出的LS和基于PCA的2DSVD能夠很好地應(yīng)用在大規(guī)模對變量時間序列上，并且LS的效果要略優(yōu)于2DSVD。

圖8 各相似性度量方法在不同長度下的聚類總F度量

3.2 真實的金融數(shù)據(jù)

在本實驗中，采用2008年上證1 120支股票，共有246個交易日。2008年是中國股票大跌的一年，上證指數(shù)從2007年10月16日的6 120.04點下跌到2008年10月28日的1 664.93點，因此選擇2008年的股票行情數(shù)據(jù)來進行實驗很具有代表性。具體實驗方法是將每個交易日作為一個時間窗口，將1 120支股票的每支股票均作為一個變量分別放入35×32的矩形網(wǎng)格內(nèi)，每分鐘的收盤價作為一個采樣值，對于每支股票一天產(chǎn)生240個值，因此一個交易日的數(shù)據(jù)就可以用長度為240的矩形網(wǎng)格的序列來描述。在本實驗中，特征矩陣的規(guī)模取p×q取p=q=6。

通過本方法的聚類，一共產(chǎn)生了5個類：類1包含了106天，類2包含了40天，類3包含了97天，類4只有2天，類5只有1天，因此可以把類4和類5看作是離群點。由于實驗的數(shù)據(jù)是上證的幾乎所有股票數(shù)據(jù)，因此上證的指數(shù)(股票代碼：SH000001)可以一定程度上的反應(yīng)股票整體的情況，而本方法也是將每只股票作為一個變量，結(jié)果也是反映所有股票的整體情況，因此可以和上證指數(shù)進行對比分析。在上證指數(shù)中共有139天收盤價下跌，其中有94天跌幅大于1%；有107天上漲，其中有63天漲幅大于1%；另外有94天漲跌幅小于1%。而實驗結(jié)果的類1中，106天中有78天跌幅大于1%，因此可以認為類1的標(biāo)簽是跌幅較大的類。而類2中的40天有34天漲幅大于1%，因此類2可以看作是漲幅較大的類。類3的97天有80天漲跌幅小于1%，因此類3可以看作是漲跌幅度不大的類。類4只包含了2天，分別是4月24日和9月19日，4月24日由于財政部、國家稅務(wù)總局決定從2008年4月24日起，調(diào)整證券交易印花稅率，由原來的3%調(diào)整為1%，導(dǎo)致股市大漲9.29%，而9月19日有三大利好消息，即印花稅單邊征收、國資委鼓勵國企大股東回購公司股票、中央?yún)R金公司將在二級市場購入工、中、建三行股票，因此股市大漲9.45%，導(dǎo)致了這兩天的數(shù)據(jù)和其他交易日的數(shù)據(jù)有較大的不同。類5中只有一個類，即2008年7月2日，當(dāng)天的漲幅只有0.004 5%，因此也和其他交易日的數(shù)據(jù)有較大不同，因此成了離群點。實驗結(jié)果顯示，我們在2008年的上海證券交易所1 120支股票的行情數(shù)據(jù)上的聚類結(jié)果和實際股市表現(xiàn)較為相符。

4 結(jié) 語

本文中，我們提出了一種新的方法——LS-Cluster來發(fā)現(xiàn)大規(guī)模多變量時間序列蘊含的模式。把多變量時間序列每個時刻所有變量的值放入一個矩形網(wǎng)格中，再用二維離散余弦變換來提取高維特征向量。為了進行聚類分析，我們提出了LS相似度來計算不同的多變量時間序列之間的相似程度。最后采用層次聚類來發(fā)現(xiàn)其中的模式并找出其中的離群點。

我們在人工合成數(shù)據(jù)和2008年1 120支股票的數(shù)據(jù)進行了實驗，證明了本方法的有效性和可擴展性，可以被用于有上萬變量數(shù)的大規(guī)模多變量時間序列的聚類分析。雖然我們的實驗是基于金融數(shù)據(jù)的，但是本方法還可以被應(yīng)用在其他的數(shù)據(jù)上，例如傳感器網(wǎng)絡(luò)、醫(yī)療、服務(wù)器機房狀態(tài)監(jiān)控等。

[1]EEGDatabase[OL].http://kdd.ics.uci.edu/databases/eeg/eeg.html.

[2]WuYL,AgrawalD,AbbadiAE.AcomparisonofDFTandDWTbasedsimilaritysearchintime-seriesdatabases[C]//ProceedingsoftheNinthInternationalConferenceonInformationandKnowledgeManagement.ACM,2000:488-495.

[3]JolliffeI.Principalcomponentanalysis[M].Hoboken,NJ,USA:JohnWiley&SonsInc,2002.

[4] 李正欣,張鳳鳴,張曉豐,等.多元時間序列特征降維方法研究[J].小型微型計算機系統(tǒng),2013,34(2):338-344.

[5]GuanH,JiangQ,HongZ.Anewmetricforclassificationofmultivariatetimeseries[C]//FuzzySystemsandKnowledgeDiscovery,2007FourthInternationalConferenceon.IEEE,2007:453-457.

[6]YangK,ShahabiC.APCA-basedsimilaritymeasureformultivariatetimeseries[C]//Proceedingsofthe2ndACMInternationalWorkshoponMultimediaDatabases.ACM,2004:65-74.

[7] 管河山,姜青山,王聲瑞.基于點分布特征的多元時間序列模式匹配方法[J].軟件學(xué)報,2009,20(1):67-79.

[8] 吳虎勝,張鳳鳴,鐘斌.基于二維奇異值分解的多元時間序列相似匹配方法[J].電子與信息學(xué)報,2014,36(4):847-854.

[9]YangC,ZhouJ.Aheterogeneousdatastreamclusteringalgorithm[J].ChineseJournalofComputers,2007,30(8):1364-1371.

[10]LiaoTW.Aclusteringprocedureforexploratoryminingofvectortimeseries[J].PatternRecognition,2007,40(9):2550-2562.

[11]HuangYP,HsuCC,WangSH.Patternrecognitionintimeseriesdatabase:acasestudyonfinancialdatabase[J].ExpertSystemswithApplications,2007,33(1):199-205.

[12]OwsleyLMD,AtlasLE,BernardGD.Automaticclusteringofvectortime-seriesformanufacturingmachinemonitoring[C]//Acoustics,Speech,andSignalProcessing,1997IEEEInternationalConferenceon.IEEE,1997:3393-3396.

[13] 周大鐲,姜文波,李敏強.一個高效的多變量時間序列聚類算法[J].計算機工程與應(yīng)用,2010,46(1):137-139.

[14]AhmedN,NatarajanT,RaoKR.Discretecosinetransform[J].IEEETransactionsonComputers,1974,23(1):90-93.

[15]TanPN,SteinbachM,KumarV.數(shù)據(jù)挖掘?qū)д?完整版)[M].范明,范宏建,譯.北京:人民郵電出版社,2011.

LS-CLUSTER: LARGE SCALE MULTIVARIATE TIME SERIES CLUSTERING METHOD

Zheng Cheng Wang Peng Wang Wei

(SchoolofComputerScience,FudanUniversity,Shanghai201203,China) (ShanghaiKeyLaboratoryofDataScience,FudanUniversity,Shanghai201203,China)

In the existing studies on multivariate time series clustering, the size of the variables studied is small, and in real life, large scale multivariate time series often appear. Therefore, LZ-Cluster algorithm is proposed, which aims at clustering large scale multivariate time series with tens of thousands of variables. Firstly, the multivariate time series of each time is transformed into a rectangle grid, and then two-dimensional discrete cosine transform is used to extract features. LZ similarity is proposed to calculate the degree of similarity between feature series. Finally, hierarchical clustering method is used to discover the patterns. The experimental results show that the proposed method has good performance and extensibility in both synthetic data and real data.

Large scale Multivariate time series Discrete cosine transform LS similarity Clustering

2016-04-01。國家自然科學(xué)基金項目(U1509213)。鄭誠，碩士生，主研領(lǐng)域：時間序列，數(shù)據(jù)挖掘。王鵬，副教授。汪衛(wèi)，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.05.036