霍緯綱，程 震，程文莉

(中國民航大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

面向不等長多維時間序列的聚類改進(jìn)算法

霍緯綱*，程 震，程文莉

(中國民航大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

針對已有基于模型的多維時間序列(MTS)聚類算法處理不等長MTS速度較慢的問題，提出了一種基于LR分量提取的MTS聚類算法(MUTSCA〈LRCE〉)。首先，采用等頻離散化方法符號化MTS；然后，計算用于表達(dá)MTS樣本各維時間序列之間時序模式的LR向量，對每個LR向量進(jìn)行排序后從其兩端提取固定數(shù)目的不同關(guān)鍵分量，所有提取的關(guān)鍵分量拼接形成表示MTS樣本的模型向量，該過程將不等長MTS樣本集轉(zhuǎn)換為等長的模型向量集；最后，采用k-means算法對生成的等長模型向量集進(jìn)行聚類分析。在多個公共數(shù)據(jù)集上的實驗結(jié)果表明，與基于模型的MTS聚類算法——MUTSCA〈LR〉相比，所提算法能夠在保證聚類效果的前提下，顯著提高不等長MTS數(shù)據(jù)集的聚類速度。

等頻離散化；k-means聚類；時序模式；多維時間序列；效率

0 引言

時間序列作為數(shù)據(jù)挖掘問題中一種重要的數(shù)據(jù)形式，是聚類領(lǐng)域的重點研究對象之一。從變量數(shù)目的角度看，時間序列可以分為單維時間序列和多維時間序列(Multivariate Time Series, MTS)。MTS是多維變量按照時間順序所記錄的一系列觀察值的集合，廣泛存在于商業(yè)、金融業(yè)、航空業(yè)、社會學(xué)、生物學(xué)等眾多應(yīng)用背景中，MTS數(shù)據(jù)集有其重要的數(shù)據(jù)特點：1)MTS的各維之間可能存在一些固有的時序關(guān)系，簡單地拆分和降維容易造成關(guān)鍵信息的丟失；2)MTS樣本之間長度往往不等，故與樣本長度相關(guān)的預(yù)處理算法不利于后期的聚類分析；3)每個MTS樣本由多個單維時間序列組成，這些時間序列的數(shù)據(jù)類型可能不同。以上特點增加了MTS數(shù)據(jù)集的聚類難度，使得面向MTS數(shù)據(jù)集的聚類算法有別于一般的方法。

現(xiàn)有的時間序列聚類算法主要包含三類[1]：基于原始數(shù)據(jù)的聚類、基于特征的聚類和基于模型的聚類。然而在這些聚類算法中，用于MTS數(shù)據(jù)集的聚類算法相對較少。文獻(xiàn)[2]利用單維時間序列的聚類思想，給多維時間序列的各個維度賦予特定的權(quán)值，每個行向量作為一個時間點。由于MTS樣本長度不等，樣本之間的相似度使用動態(tài)時間彎曲(Dynamic Time Warping, DTW)度量，最佳匹配路徑上每一對時間點的多維向量之間的距離利用閔可夫斯基參數(shù)模型計算。該算法需要領(lǐng)域知識為各個變量賦予權(quán)值，且DTW距離度量方法的計算量較大。文獻(xiàn)[3]提出基于變量相關(guān)性的MTS特征表示方法，通過協(xié)方差反映系統(tǒng)中各個參數(shù)的相關(guān)關(guān)系，將MTS樣本轉(zhuǎn)化為協(xié)方差矩陣；MTS集所有的協(xié)方差矩陣拼接為綜合協(xié)方差矩陣，對該協(xié)方差矩陣進(jìn)行主成分分析得到各MTS的特征矩陣。該方法可以將數(shù)值型不等長MTS數(shù)據(jù)集轉(zhuǎn)變?yōu)榇笮∠嗤奶卣骶仃嚰?，處理結(jié)果可用于聚類分析。文獻(xiàn)[4]提出了一種基于參數(shù)交互關(guān)系的MTS聚類方法，指出MTS中的任一維變量都可以被其他解釋變量近似線性組合表示，且將一維線性關(guān)系納入了考慮范疇，假定這些變量間的線性相關(guān)關(guān)系可以用來進(jìn)行聚類，其不足之處在于模型計算時間會隨著樣本數(shù)量變大而增加，也不能處理非數(shù)值型變量。文獻(xiàn)[5]將每一維時間序列轉(zhuǎn)化為一個統(tǒng)計特征數(shù)組，MTS樣本由各維變量統(tǒng)計特征數(shù)組拼接成的向量來表示。該算法可以處理不等長時間序列，但要求各維選取的統(tǒng)計特征必須一致導(dǎo)致其在處理混合型MTS數(shù)據(jù)集時會遇到困難。文獻(xiàn)[6]針對MTS數(shù)據(jù)集存在的樣本之間不等長、數(shù)據(jù)類型多樣和噪聲等問題，提出了一種基于協(xié)方差矩陣與測地線距離(geodesic-based distance)的MTS聚類算法。該算法首先將MTS樣本轉(zhuǎn)化為協(xié)方差矩陣；然后將協(xié)方差矩陣從黎曼空間映射到歐氏空間；最后對矩陣集進(jìn)行聚類。如果使用基于距離的聚類算法，上述映射過程可以省略，協(xié)方差矩陣之間的距離度量方法使用測地線距離。Zhou等[7]提出了一種基于模型的多維時間序列聚類算法——MUTSCA〈LR〉(Multivariate Time Series Clustering Algorithm 〈Lift Ratio〉)，該聚類算法假設(shè)目標(biāo)數(shù)據(jù)集由一系列概率分布模型系統(tǒng)生成，不同的系統(tǒng)將生成相異的多維時間序列。該算法先將連續(xù)型數(shù)值符號化；然后在符號化樣本上計算由LR(Lift Ratio)向量表示的時序模式，將時序模式累加生成用來表示MTS樣本的模型向量；最后對模型向量集進(jìn)行聚類。它不需要特定的領(lǐng)域知識，同時可以處理包含數(shù)值和非數(shù)值型變量的混合型MTS數(shù)據(jù)集。但實際應(yīng)用中的MTS數(shù)據(jù)集，各樣本的長度往往不等，該算法在處理不等長多維時間序列時需要利用DTW[8]或滑動窗口[9]來度量模型向量之間的相似性，造成算法的時間開銷較大。

針對上述算法在處理MTS數(shù)據(jù)集時的不足，本文將在MUTSCA〈LR〉的基礎(chǔ)上進(jìn)行改進(jìn)，提出一種基于LR分量提取的多維時間序列聚類算法(MUltivariate Time Series Clustering Algorithm based on LR Component Extraction，MUTSCA〈LRCE〉)。該算法使用等頻離散化方法對MTS數(shù)據(jù)集進(jìn)行符號化；在符號化后的MTS樣本每一維時間序列之間計算時序模式向量LR，對LR向量進(jìn)行排序并提取向量兩端固定數(shù)目不同數(shù)值的分量，同一MTS樣本內(nèi)的提取分量拼接成一個模型向量(Model Vector, MV)，MTS數(shù)據(jù)集由MV向量的集合表示；最后對模型向量集使用k-means算法進(jìn)行聚類分析。實驗結(jié)果表明，改進(jìn)算法可以快速地完成不等長MTS數(shù)據(jù)集的聚類分析。

1 相關(guān)知識背景

1.1 符號表示與相關(guān)定義

定義2 時序模式。用LR向量表示的時序模式的計算方法[6]如下：

(1)

1.2 MUTSCA〈LR〉算法

MUTSCA〈LR〉算法首先使用MDD(Mode-Driven Discretization)算法[10]對MTS樣本進(jìn)行符號化，MDD符號化過程如下：MDD算法將MTS作為由若干個向量組成的矩陣，行為向量，列為變量維；首先選取MTS中獨立冗余度 (Multiple interdependence Redundancy, MR)值最大的變量維作為標(biāo)簽屬性，標(biāo)簽維每一行的符號值為該行向量的分類標(biāo)簽；然后利用有監(jiān)督的離散化算法OCDD(Optimal Class-Dependent Discretization)[11]對其他數(shù)值型變量維進(jìn)行符號化。在符號化后的MTS樣本上利用式(1)計算時序模式LR并累加得到模型向量。最后，利用k-means算法對模型向量集進(jìn)行聚類分析。MUTSCA〈LR〉算法模型向量計算方法如下：

輸出N個模型向量組成的向量集finalLR。

For 每個多維時間序列Si*

利用式(1)計算intra-pattern;

利用式(1)計算inter-pattern;

finalLRi+=inter-pattern;

End

finalLRi+=intra-pattern;

End

finalLR=finalLR∪{finalLRi};

End

MUTSCA〈LR〉算法存在兩個問題：

1)MDD算法中采用的OCDD利用動態(tài)規(guī)劃的思想選取分割點集，若處理長時間序列需要較多的離散化符號，則要求候選分割點集包含較多的元素，導(dǎo)致OCDD的開銷過高，離散化執(zhí)行效率低下。

2)由于j,k∈{1,2,…,m}，每個樣本計算得到m2個時序模式向量LR，多維時間序列Si*最終生成的時序模型finalLRi由m2個LR向量累加求和得到。如果多維時間序列集S*中的各個樣本Si*長度不等，則MUTSCA〈LR〉生成的模型向量集finalLR中的各個finalLRi(i∈{1,2,…,N})長度也不相等。上述問題增加了相似性度量的難度，造成該算法在聚類過程的耗時較長。

2 MUTSCA〈LRCE〉算法

2.1 多維時間序列的等頻離散化

針對MDD算法效率較低的問題，文中采用等頻離散化(Equal Frequency Discretization, EFD)算法進(jìn)行符號化。EFD是一種簡單的離散化方法，它需要事先給定一個參數(shù)來決定離散化后最終的離散符號個數(shù)，記為num_bin。在沒有領(lǐng)域知識的情況下，各個樣本的num_bin往往難以確定。傳統(tǒng)的等頻離散化方法需要用戶隨機(jī)給出num_bin的取值，如此會導(dǎo)致MTS聚類分析的效果不穩(wěn)定。num_bin的取值同MTS樣本長度有關(guān)，但MTS數(shù)據(jù)集各樣本長度差異過大會導(dǎo)致num_bin的值域范圍較寬。鑒于以上原因，本文基于樣本長度和變異系數(shù)提出一個用來為樣本Si(i∈{1,2,…,N})選取num_bin值的計算方法：

(2)

其中：C為由MTS樣本集S確定的唯一常數(shù)，n是Si的時間序列長度。輸入樣本集S={S1,S2,…,SN}，統(tǒng)計S中各MTS長度的均值M和標(biāo)準(zhǔn)差Ve，計算變異系數(shù)CV=Ve/M，C為變異系數(shù)的倒數(shù)1/CV。從式(2)可知，當(dāng)MTS樣本集各樣本長度的CV取值越大，參數(shù)C的取值越小，從而緩解各MTS樣本離散符號數(shù)目差異大的問題。文中的等頻離散化方法具體描述如下。

輸出 符號化后的樣本集S*={S1*,S2*,…,SN*}。

統(tǒng)計樣本集各個時間序列的均值和方差，并計算系數(shù)C；

For 樣本集每一個多維時間序列Si

利用式(2)計算Si的num_bin;

END

S*=S*∪Si*;

END

2.2 模型向量集的生成方法及其聚類

輸出 模型向量集MV={MV1,MV2,…,MVN}。

For 每一個多維時間序列Si*

For 多維時間序列的所有參數(shù)v1(1≤v1≤m)

For 多維時間序列的所有參數(shù)v2(1≤v2≤m)

利用式(1)計算LR向量;

對LR進(jìn)行排序，從中提取首尾K個數(shù)值不同的分量，并 拼接到MVi;

End

End

MV=MV∪MVi;

End

文中采用k-means算法對模型向量集MV進(jìn)行聚類分析，首先隨機(jī)選取k個模型向量作為初始簇中心，計算模型向量與各簇中心的歐氏距離，并將該向量分配給最相似的簇，MV分類完畢后更新簇中心。重復(fù)上述步驟，直至分簇結(jié)果不再變化，輸出分簇結(jié)果向量KM=[km1,km2,…,kmN]，其中kmi(kmi∈{1,2,…,k})表示樣本Si的分簇編號。聚類過程如下。

輸入 模型向量集MV={MV1,MV2,…,MVN}，分簇個數(shù)k；

輸出 分簇結(jié)果向量KM=[km1,km2,…,kmN]。

從MV中隨機(jī)選取k個向量作為初始簇中心集合Core={core1,core2,…,corek};

構(gòu)建一個數(shù)組Num[k];

初始化KM=[0,0,…,0];

Do

初始化Core′為0向量集，Num[k]為0向量;

For 模型向量MVi(1≤i≤N)

計算每個模型向量與Core的k個簇中心的相似度，并將它分 配到最相似的簇θ，其中θ∈{1,2,…,k};

kmi=θ;

Num[kmi-1]++;

End

利用Core′與Num[k]更新簇中心，結(jié)果返還給Core;

UntilKMno change

3 實驗與結(jié)果分析

算法使用Java進(jìn)行編程實現(xiàn)，實驗在一臺配備Intel四核3.80 GHz處理器、4 GB內(nèi)存、裝有Window 7系統(tǒng)的PC上進(jìn)行。

3.1 實驗準(zhǔn)備與數(shù)據(jù)集介紹

選用4個來自UCI的MTS數(shù)據(jù)集：EMGPAD(EMG Physical Action Data set)、EMGLL(EMG dataset in Lower Limb)、AReM(Activity Recognition system based on Multisensor data fusion)、DSAD(Daily and Sports Activities Data set)，其中AReM與DSAD為等長MTS數(shù)據(jù)集，詳見表1。

1)EMGPAD。樣本數(shù)目80，包括3位男性和1位女性實驗者。每個實驗者做20個動作(20個樣本)，包括10個攻擊性動作和10個一般動作，樣本長度大多在10 000左右。實驗使用動作的性質(zhì)為標(biāo)簽，即攻擊性和非攻擊性。

2)EMGLL。樣本數(shù)目66，包括11位膝關(guān)節(jié)患者和11位正常人。每個實驗者做3種運(yùn)動，各樣本長度波動較大。實驗使用自然人的分類作為標(biāo)簽，即患者和正常人。

3)AReM。樣本數(shù)目87，包括7個類型一的彎腰動作、5個類型二的彎腰動作、15個騎車動作、15個躺動作、15個坐動作、15個站立動作、15個走路動作，各樣本長度均為480。實驗使用動作的類型作為標(biāo)簽，共7種類別。該數(shù)據(jù)集是為了驗證改進(jìn)算法MUTSCA〈LRCE〉在等長MTS數(shù)據(jù)集上可以維持MUTSCA〈LR〉的聚類效果。

4)DSAD。樣本數(shù)目9 120，由8位實驗參與者完成19種動作，每個動作包含60個樣本。該數(shù)據(jù)集旨在檢驗算法MUTSCA〈LRCE〉在大樣本集下的聚類效果。

實驗過程中參數(shù)設(shè)置如下，LR計算的時間延時τ的值取5，k-means聚類算法的簇中心個數(shù)k取值為數(shù)據(jù)集的類別個數(shù)，提取排序后LR向量的首尾分量個數(shù)K取10。由于實驗數(shù)據(jù)集有標(biāo)簽，故采用F-measure和信息熵作為實驗中多維時間序列聚類算法的評價指標(biāo)。

表1 實驗數(shù)據(jù)介紹Tab. 1 Introduction to experimental data

為了便于算法MUTSCA〈LR〉與MUTSCA〈LRCE〉對比，本實驗使用兩種方法對MUTSCA〈LR〉進(jìn)行修改使其能夠處理不等長MTS數(shù)據(jù)集：1)使用DTW計算不等長模型向量之間的距離，采用文獻(xiàn)[12]提出的基于DTW的全局平均法進(jìn)行k-means聚類中心點的更新；2)使用滑動窗口計算不等長模型向量之間的距離，簇中心點的更新方法如下：假設(shè)某次k-means迭代過程產(chǎn)生的簇中心集合為Core={core1,core2,…,corek}，length(corei)表示向量corei的長度。設(shè)corei所在簇中有ni個模型向量，在簇中心corei(1≤i≤k)的更新過程中，創(chuàng)建兩個長度為length(corei)的0向量，記為Sum和weight。對于corei簇中的某模型向量MVj(1≤j≤ni)，若length(MVj)≥length(corei)，使用滑動窗口在MVj上截取與corei最相似的子序列累加至Sum、weight各分量數(shù)值加1；若length(MVj)

3.2 本文的等頻離散化方法評估

表2 等頻離散化與MDD效果評估Tab. 2 Evaluation of equal frequency discretization and MDD

圖1 MDD算法評估Fig. 1 Evaluation of MDD algorithm

3.3 MUTSCA〈LRCE〉算法評估

使用4個MTS數(shù)據(jù)集對改進(jìn)算法MUTSCA〈LRCE〉進(jìn)行評估，如表3所示，其中MUTSCA〈LR〉使用MDD進(jìn)行樣本集符號化，MUTSCA〈LRCE〉則采用改進(jìn)的EFD算法。聚類時間包括模型計算時間和k-means執(zhí)行時間，由表3可知，在不等長MTS數(shù)據(jù)集EMGPAD與EMGLL上，改進(jìn)后的MUTSCA〈LRCE〉因包含向量排序過程，故時間略長，這里認(rèn)為算法改進(jìn)前后的模型計算時間基本一致。算法MUTSCA〈LRCE〉的k-means執(zhí)行時間分別為35 ms和16 ms，而原算法k-means的執(zhí)行時間明顯較長。這是由于算法MUTSCA〈LRCE〉生成的模型向量長度僅取決于MTS參數(shù)個數(shù)m以及分量個數(shù)K，模型向量長度固定，使得算法聚類速度較快。此外，基于滑動窗口的MUTSCA〈LR〉在數(shù)據(jù)集EMGPAD上執(zhí)行時間少于EMGLL的原因是EMGPAD中各樣本長度波動較小，模型向量之間的相似性度量包含的窗口滑動次數(shù)較少。從聚類結(jié)果來看， MUTSCA〈LRCE〉與MUTSCA〈LR〉在EMGPAD上的聚類效果相當(dāng)，而在數(shù)據(jù)集EMGLL上算法MUTSCA〈LR〉的F-measure值在0.75附近，由實驗3.2節(jié)的分析可知其在該數(shù)據(jù)集上失效的原因在于該數(shù)據(jù)集存在長度較短的樣本，它們的候選分割點集中元素較少，導(dǎo)致MDD離散化效果不佳，影響了后續(xù)的聚類分析。

數(shù)據(jù)集AReM是樣本數(shù)目較少的等長多維時間序列數(shù)據(jù)集，由于樣本長度較短，聚類時間相互之間區(qū)分度低，參考價值不大。從聚類結(jié)果的角度看，三種算法的熵和F-measure值基本一致。數(shù)據(jù)集DSAD為包含較多等長多維時間序列樣本，該部分實驗選取了4 800個樣本，由于本文算法生成的模型向量維度與變量個數(shù)有關(guān)，模型向量維度L大于樣本長度，其中L=m2*K，樣本長度為125。因此模型向量維度高，聚類時間較長。同時，較高維度的模型向量包含更多特征，故聚類效果優(yōu)于算法MUTSCA〈LR〉。所以，算法MUTSCA〈LRCE〉在多標(biāo)簽的等長MTS數(shù)據(jù)集上仍然有效。

表3 MUTSCA〈LRCE〉的聚類工作評估Tab. 3 Clustering work evaluation of MUTSCA〈LRCE〉

為了評估聚類簇個數(shù)k值對k-means聚類結(jié)果的影響，本文從數(shù)據(jù)集DSAD中選取兩組樣本子集進(jìn)行實驗，實驗結(jié)果如表4所示。第一組樣本子集包含樣本數(shù)目240個，分別來自4種不同類型動作的樣本集，標(biāo)簽數(shù)目為4。第二組樣本子集包含1 920個樣本，實驗以同一動作類型的同一個行為主體的60個樣本為一組，抽取32組，所以樣本子集標(biāo)簽數(shù)目為32。

表4 MUTSCA〈LRCE〉算法k值對聚類結(jié)果的影響Tab. 4 Influence of k value in MUTSCA〈LRCE〉algorithm on clustering results

由表4可以看出，當(dāng)k值小于標(biāo)簽個數(shù)時聚類效果較差，當(dāng)參數(shù)k略大于標(biāo)簽數(shù)時，聚類效果較好。這是因為k值較小時，不同標(biāo)簽的樣本容易被合并到同一類簇中。當(dāng)k值略大于樣本標(biāo)簽數(shù)目時，k-means分簇更精細(xì)，噪聲樣本對聚類過程的影響降低。

4 結(jié)語

本文基于時序模式Lift Ratio向量的MTS表示方法提出了MUTSCA〈LRCE〉算法，該算法利用改進(jìn)的等頻離散化方法對MTS進(jìn)行符號化，通過LR向量分量提取的方式將不等長MTS樣本轉(zhuǎn)化為等長的模型向量。實驗結(jié)果表明本文算法可以更好地對不等長MTS數(shù)據(jù)集進(jìn)行聚類分析。時間序列是數(shù)據(jù)之間具有嚴(yán)格上下文關(guān)系的一類特殊數(shù)據(jù)對象，LR向量所展現(xiàn)的MTS時序模式僅反映了時間點之間的時序關(guān)系，如何利用時間段之間的時序關(guān)系進(jìn)行MTS聚類并減少時間段處理過程中造成的信息丟失有待進(jìn)一步研究。

References)

[1] LIAO T W. Clustering of time series data — a survey [J]. Pattern Recognition, 2005, 38(11): 1857-1874.

[2] CHANDRA B, GUPTA M, GUPTA M P. A multivariate time series clustering approach for crime trends prediction [C]// Proceedings of the 2008 IEEE International Conference on Systems, Man & Cybernetics. Piscataway, NJ: IEEE, 2008: 892-896.

[3] 李海林.基于變量相關(guān)性的多元時間序列特征表示[J].控制與決策,2015,30(3):441-447.(LI H L. Feature representation of multivariate time series based on correlation among variables [J]. Control and Decision, 2015, ,30(3): 441-447.)

[4] PLANT C, WOHLSCHLAGER A M, ZHERDIN A. Interaction-based clustering of multivariate time series [C]// Proceedings of the 9th IEEE International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2009: 914-919.

[5] WANG X Z, WIRTH A, WANG L. Structure-based statistical features and multivariate time series clustering [C]// Proceedings of the 2007 IEEE International Conference on Data Mining. Piscataway, NJ: IEEE, 2007: 351-360.

[6] SUN J. Clustering multivariate time series based on Riemannian manifold [J]. Electronics Letters, 2016, 52(19): 1607-1609.

[7] ZHOU P Y, CHAN K C C. A model-based multivariate time series clustering algorithm [C]// Proceedings of the 2014 International Workshops Trends and Applications in Knowledge Discovery and Data Mining, LNCS 8643. Berlin: Springer, 2014: 805-817.

[8] KEOGH E. Exact indexing of dynamic time warping [J]. Knowledge and Information Systems, 2005, 7(3): 358-386.

[9] YE L, KEOGH E. Time series shapelets:a new primitive for data mining [C]// KDD 2009: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2009: 947-956.

[10] WONG A K C, WU B, WU G P K, et al. Pattern discovery for large mixed-mode database [C]// CIKM 2010: Proceedings of the 19th ACM International Conference on Information & Knowledge Management. New York: ACM, 2010: 859-868.

[11] LIU L, WONG A K C, WANG Y. A global optimal algorithm for class-dependent discretization of continuous data [J]. Intelligent Data Analysis, 2004, 8(2): 151-170.

[12] PETITJEAN F, KETTERLIN A, GANCARSKI P. A global averaging method for dynamic time warping, with applications to clustering [J]. Pattern Recognition, 2011, 44(3): 678-693.

This work is partially supported by the National Natural Science Foundation of China (61301245), the Joint Funds of Civil Aviation Administration of China (U1633110).

HUOWeigang, born in 1978, Ph. D., associate professor. His research interests include data mining, fuzzy clustering.

CHENGZhen, born in 1991, M. S. candidate. His research interests include data mining.

CHENGWenli, born in 1992, M. S. candidate. Her research interests include big data.

Improvedclusteringalgorithmformultivariatetimeserieswithunequallength

HUO Weigang*, CHENG Zhen, CHENG Wenli

(SchoolofComputerScienceandTechnology,CivilAviationUniversityofChina,Tianjin300300,China)

Aiming at the problem of slow speed of the existing model-based Multivariate Time Series (MTS) clustering algorithm when dealing with MTS wtih unequal length, an improved clustering algorithm named MUltivariate Time Series Clustering Algorithm based on Lift Ratio (LR) Component Extraction (MUTSCA〈LRCE〉) was proposed. Firstly, the equal frequency discretization method was used to symbolize MTS. Then, the LR vector was calculated to express the temporal pattern between the dimensions of time series of MTS samples. Each LR vector was sorted and a fixed number of different key components were extracted from both ends. All the extracted key components were spliced to form a model vector for representing the MTS samples. The MTS sample set with unequal length was transformed into a model vector set with equal length. Finally, thek-means algorithm was used for the clustering analysis of generated model vector set with equal length. The experimental results on multiple common data sets show that, compared with the model-based MTS clustering algorithm named MUltivariate Time Series Clustering Algorithm〈LR〉(MUTSCA〈LR〉), the proposed algorithm can significantly improve the clustering speed of MTS data sets with unequal length under the premise of guaranteeing clustering effect.

equal frequency discretization;k-means clustering; temporal pattern; Multivariate Time Series (MTS); efficiency

2017- 05- 18;

2017- 07- 05。

國家自然科學(xué)基金資助項目(61301245);中國民航聯(lián)合研究基金資助項目(U1633110)。

霍緯綱(1978—)，男，山西洪洞人，副教授，博士，CCF會員，主要研究方向：數(shù)據(jù)挖掘、模糊分類； 程震(1991—)，男，江蘇沛縣人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘； 程文莉(1992—)，女，河南鶴壁人，碩士研究生，主要研究方向：大數(shù)據(jù)。

1001- 9081(2017)12- 3477- 05

10.11772/j.issn.1001- 9081.2017.12.3477

(*通信作者電子郵箱wghuo@cauc.edu.cn)

TP311.13；TP181

A