網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150401.1459.001.html

基于特征矩陣的多元時(shí)間序列最小距離度量方法

李海林，郭韌，萬(wàn)?；?/p>

(華僑大學(xué) 信息管理系，福建 泉州 362021)

摘要：相似性度量是多元時(shí)間序列數(shù)據(jù)挖掘任務(wù)過(guò)程中一項(xiàng)重要的前期工作，度量質(zhì)量直接影響到后期整個(gè)數(shù)據(jù)挖掘的性能和結(jié)果。利用主成分分析方法對(duì)數(shù)據(jù)集中的每個(gè)多元時(shí)間序列數(shù)據(jù)進(jìn)行特征分析，提取其特征矩陣并且構(gòu)建相應(yīng)的新正交坐標(biāo)系。通過(guò)夾角公式來(lái)度量2個(gè)正交坐標(biāo)系之間距離，并且結(jié)合匈牙利算法計(jì)算它們之間的最小距離，進(jìn)而實(shí)現(xiàn)了一種基于特征矩陣的多元時(shí)間序列最小距離度量方法。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)方法相比，新方法具有較好的相似性度量質(zhì)量，提高了多元時(shí)間序列的數(shù)據(jù)挖掘效果。

關(guān)鍵詞：多元時(shí)間序列；相似性度量；特征矩陣；最小距離；主成分分析；匈牙利算法；數(shù)據(jù)挖掘

DOI:10.3969/j.issn.1673-4785.201405047

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)志碼：A

收稿日期：2014-05-23. 網(wǎng)絡(luò)出版日期：2015-04-01.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61300139); 福建省中青年教師教育科研項(xiàng)目(JAS14024); 華僑大學(xué)中青年教師科研提升資助計(jì)劃項(xiàng)目(ZQN-PY220).

作者簡(jiǎn)介：

中文引用格式：李海林，郭韌，萬(wàn)?；? 基于特征矩陣的多元時(shí)間序列最小距離度量方法[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(3): 442-447.

英文引用格式：LI Hailin, GUO Ren, WAN Xiaoji. A minimum distance measurement method for a multivariate time series based on the feature matrix[J]. CAAI Transactions on Intelligent Systems, 2015, 10(3): 442-447.

A minimum distance measurement method for a

multivariate time series based on the feature matrix

LI Hailin, GUO Ren, WAN Xiaoji

(Department of Information Management, Huaqiao University, Quanzhou 362021, China)

Abstract：Similarity measurement is one of the most important preliminary works in the process of multivariate data mining. Its quality directly influences the performance and result of the later tasks of data mining. The data of every multivariate time series in dataset can be analyzed by the principal component analysis. The feature matrices are extracted to construct the corresponding new orthogonal coordinate systems whose distance can be measured by cosine value of the angles between two axes. Meanwhile, the Hungary algorithm is applied to the minimum distance computation of the two coordinate systems. In this way, the minimum distance measurement method for the multivariate time series based on the feature matrix is achieved. The results of experiment demonstrated that the proposed method has better quality of similarity measurement than the traditional ones and improves the effects of data mining for the multivariate time series.

Keywords：multivariate time series; similarity measurement; feature matrix; minimum distance; principal component analysis; Hungary algorithm; data mining

通信作者：李海林. E-mail: hailin@mail.dlut.edu.cn.

多元時(shí)間序列是數(shù)據(jù)挖掘領(lǐng)域中常見(jiàn)的一種數(shù)據(jù)類(lèi)型，廣泛存在于經(jīng)濟(jì)、金融、醫(yī)療衛(wèi)生、電子信息和航空航天等行業(yè)中[1]．與其他數(shù)據(jù)類(lèi)型相比，它有2種高維特性，即時(shí)間屬性維度和變量屬性維度，它們決定了多元時(shí)間序列數(shù)據(jù)的復(fù)雜性，同時(shí)也影響著數(shù)據(jù)挖掘技術(shù)在多元時(shí)間序列數(shù)據(jù)中的應(yīng)用性能。為了解決多元時(shí)間序列的維災(zāi)問(wèn)題，許多學(xué)者提出利用數(shù)據(jù)降維和特征表示等方法結(jié)合相關(guān)技術(shù)來(lái)提高多元時(shí)間序列的數(shù)據(jù)挖掘性能[2-3]。除了簡(jiǎn)單運(yùn)用一元時(shí)間序列的降維技術(shù)和特征表示外，通常利用數(shù)據(jù)變換的方法來(lái)實(shí)現(xiàn)數(shù)據(jù)處理，達(dá)到減噪降冗的效果，例如奇異值分解[4-6]、獨(dú)立成分分析[7-8]和主成分分析[9-10]等。其中，主成分分析(principal component analysis, PCA)是多元時(shí)間序列數(shù)據(jù)降維和特征表示中最常用的方法之一[11]，它通過(guò)對(duì)多元時(shí)間序列的協(xié)方差矩陣進(jìn)行特征分解，實(shí)現(xiàn)數(shù)據(jù)空間變換得到方差最大的主成分作為原始數(shù)據(jù)的特征。同時(shí)，根據(jù)方差大小選擇對(duì)應(yīng)的前幾個(gè)主成分作為多元時(shí)間序列的數(shù)據(jù)特征，從而實(shí)現(xiàn)原始多元時(shí)間序列的變量屬性維度的降維。

在多元時(shí)間序列數(shù)據(jù)挖掘前期任務(wù)中，除了進(jìn)行數(shù)據(jù)降維和特征表示外，相似性(或距離)度量也是一項(xiàng)重要的工作，其度量質(zhì)量直接影響著后期數(shù)據(jù)挖掘技術(shù)的性能和挖掘質(zhì)量。例如，多元時(shí)間序列的聚類(lèi)、分類(lèi)、相似性查找和匹配、異常檢測(cè)等都需要進(jìn)行距離度量。在時(shí)間序列數(shù)據(jù)挖掘中，最常用的2種方法是歐氏距離(Euclidean distance)[12]和動(dòng)態(tài)時(shí)間彎曲方法(dynamic time warping, DTW)[13]。前者能較快地計(jì)算序列之間的相似性，適用于等長(zhǎng)時(shí)間序列的相似性度量；后者對(duì)不等長(zhǎng)時(shí)間序列的距離度量具有較強(qiáng)的魯棒性，但需要二階的時(shí)間和空間復(fù)雜度，不利用大量較長(zhǎng)時(shí)間序列的相似性度量。針對(duì)主成分分析方法得到的特征數(shù)據(jù)，存在許多距離度量方法來(lái)實(shí)現(xiàn)特征數(shù)據(jù)的相似性計(jì)算。其中，較為常用的是一種被稱(chēng)為Eros的距離度量方法[14]，它利用夾角公式來(lái)度量2個(gè)特征向量之間的關(guān)系，同時(shí)以相應(yīng)的方差作為權(quán)重，較好地描述了多元時(shí)間序列經(jīng)過(guò)特征變換后特征數(shù)據(jù)之間的差異性。然而，Eros是根據(jù)特征序列方差大小來(lái)選擇相應(yīng)特征向量進(jìn)行匹配，迫使較大方差對(duì)應(yīng)的特征向量被用來(lái)計(jì)算相似性。另外，權(quán)重是由方差的大小決定，使得Eros因過(guò)分強(qiáng)調(diào)方差的重要性而忽視了特征空間之間的差異性。

針對(duì)上述問(wèn)題，本文提出一種基于特征矩陣的多元時(shí)間序列最小距離度量方法，它利用主成分分析對(duì)多元時(shí)間序列進(jìn)行特征表示，并獲得相應(yīng)的特征矩陣并構(gòu)建相應(yīng)的正交坐標(biāo)系。另外，通過(guò)夾角公式來(lái)度量2個(gè)多元時(shí)間序列對(duì)應(yīng)正交坐標(biāo)系中不同坐標(biāo)軸之間的距離，并結(jié)合匈牙利算法計(jì)算它們之間的最小距離。該方法不依賴(lài)于方差的大小來(lái)選擇夾角向量，而是通過(guò)度量正交坐標(biāo)系之間的相似性來(lái)反映原始多元時(shí)間序列的差異，進(jìn)而克服了傳統(tǒng)Eros方法的局限性。

1主成分分析與Eros距離度量

主成分分析(PCA)是一種最常用的線性降維方法，是基于某種類(lèi)型的投影機(jī)制，將高維的數(shù)據(jù)向低維空間(特征空間)投影，并期望在特征空間中數(shù)據(jù)的方差最大。通過(guò)選擇占有絕大部分信息的主成分來(lái)實(shí)現(xiàn)數(shù)據(jù)降維，同時(shí)進(jìn)行特征表示。換句話說(shuō)，如果把所有的點(diǎn)映射在一起，則幾乎所有的原始信息都將丟失；若映射后數(shù)據(jù)的方差盡可能大，則數(shù)據(jù)點(diǎn)將被分開(kāi)，使得距離信息保留得更多。因此，傳統(tǒng)的主成分分析方法通過(guò)方差的大小來(lái)選擇主成分。

(1)

利用主成分分析方法對(duì)多元時(shí)間序列Xn×m進(jìn)行特征分解，可以得到相應(yīng)的特征值和特征矩陣。同時(shí)，根據(jù)特征值(即方差)的大小，可以選擇對(duì)應(yīng)的特征向量作為特征空間中的坐標(biāo)軸，進(jìn)而得到相應(yīng)的主成分。選取前k(k

(2)

Eros距離度量方法就是一種基于特征空間的多元時(shí)間序列相似性度量方法[14]。它利用主成分分析方法對(duì)多元時(shí)間序列進(jìn)行特征分解，得到相應(yīng)的特征值和特征矩陣。同時(shí)，根據(jù)特征值的大小，選取對(duì)應(yīng)的特征向量形成特征空間坐標(biāo)系，并且結(jié)合綜合權(quán)重W來(lái)計(jì)算2個(gè)多元時(shí)間序列A和B對(duì)應(yīng)特征空間坐標(biāo)系之間的相似性，即

(3)

2最小距離度量方法

Eros距離度量方法是一種基于特征空間坐標(biāo)系的相似性度量方法，讓2個(gè)多元時(shí)間序列經(jīng)PCA轉(zhuǎn)換后前k個(gè)坐標(biāo)軸根據(jù)它們的特征值大小進(jìn)行相應(yīng)的夾角度量，即一個(gè)多元時(shí)間序列第i個(gè)特征向量與另一個(gè)多元時(shí)間序列的第i個(gè)特征向量進(jìn)行夾角度量。然而，在某些情況下，一個(gè)多元時(shí)間序列的第i個(gè)特征向量可能與另一個(gè)多元時(shí)間序列的第j個(gè)特征向量的夾角更相似。鑒于此種情況，提出基于特征矩陣的多元時(shí)間序列最小距離度量方法。

最小距離度量方法的主要思想就是利用主成分分析方法對(duì)數(shù)據(jù)庫(kù)中的每個(gè)多元時(shí)間序列進(jìn)行特征分解，得到相應(yīng)的特征向量。通過(guò)夾角公式分別計(jì)算2個(gè)多元時(shí)間序列對(duì)應(yīng)前k個(gè)特征向量中任意2個(gè)向量之間的相似性，并建立夾角距離矩陣。最后通過(guò)匈牙利算法[15]對(duì)該距離矩陣實(shí)現(xiàn)最小距離度量。由于該方法是基于傳統(tǒng)Eros的多元時(shí)間序列距離度量方法，故亦可稱(chēng)之為MEros(minimumEros)。

(4)

(5)

通過(guò)夾角公式計(jì)算2個(gè)多元時(shí)間序列對(duì)應(yīng)前k個(gè)特征向量中任意2個(gè)向量之間的夾角距離矩陣為

最小距離度量方法就是基于夾角距離矩陣D，根據(jù)傳統(tǒng)Eros思想找到一組最優(yōu)匹配，使得該匹配具有最小的距離。即通過(guò)PCA降維后，一個(gè)多元時(shí)間序列的前k個(gè)特征向量能夠與另一個(gè)多元時(shí)間序列的前k個(gè)特征向量對(duì)應(yīng)比較，并取得最小距離度量。因此，該思路可以歸納為一個(gè)線性規(guī)劃問(wèn)題：

(6)

上述線性規(guī)劃問(wèn)題實(shí)質(zhì)是一個(gè)線性任務(wù)分配問(wèn)題，即k個(gè)人分配k項(xiàng)任務(wù)，一個(gè)人只能分配一項(xiàng)任務(wù)，一項(xiàng)任務(wù)只能分配給一個(gè)人。為此，選取匈牙利算法[15]來(lái)解決該線性任務(wù)分配問(wèn)題，該算法是用來(lái)解決二分圖最小匹配問(wèn)題的經(jīng)典算法。對(duì)于多元時(shí)間序列的主成分之間的最小夾角距離可以從矩陣D出發(fā)，把該矩陣的各行和各列分別視為線性任務(wù)分配問(wèn)題中的人員和任務(wù)，即如何從距離矩陣D中把第j列的任務(wù)分配給第i行的對(duì)象，使得最終每個(gè)人完成一項(xiàng)任務(wù)，且所有人員完成所有任務(wù)后花費(fèi)的代價(jià)要求最小。

由于多元時(shí)間序列經(jīng)過(guò)主成分分析方法進(jìn)行變換后，不同多元時(shí)間序列的特征向量可以構(gòu)成不同的坐標(biāo)系，不同坐標(biāo)系的維表示的意義各不相同。若簡(jiǎn)單按照各特征值大小順序來(lái)構(gòu)建坐標(biāo)系,并且比較對(duì)應(yīng)坐標(biāo)系之間的夾角來(lái)描述多元時(shí)間序列特征的差異性，將顯得不合理。針對(duì)此問(wèn)題，利用匹配不同時(shí)間序列的特征向量構(gòu)建的坐標(biāo)系之間的最小距離，便可以使得2個(gè)坐標(biāo)系中最相似的維被相互比較，進(jìn)而更為靈活有效地對(duì)多元時(shí)間序列的特征進(jìn)行距離度量。

綜上所述，基于特征矩陣的多元時(shí)間序列最小距離度量算法如下。

輸入：多元時(shí)間序列A與B，降維后的維度k。

輸出：最小距離度量dmin。

步驟：

1)對(duì)多元時(shí)間序列A與B計(jì)算協(xié)方差矩陣，即SA=E[(A-E[A])(A-E[A])T]和SB=E[(B-E[B])(B-E[B])T]；

3)分別在UA和UB中選取前k個(gè)特征向量作為新坐標(biāo)系的坐標(biāo)軸，根據(jù)距離度量式(5)，建立夾角距離矩陣D；

4)利用匈牙利算法對(duì)夾角距離矩陣進(jìn)行最小距離計(jì)算，即dmin=munkres (D)，其中，munkres為匈牙利算法求解二分圖最小匹配問(wèn)題的函數(shù)。

基于特征矩陣的多元時(shí)間序列最小距離度量方法能夠有效地描述原始多元時(shí)間序列之間的相似性。同時(shí)，與傳統(tǒng)Eros方法相比，最小距離度量方法MEros不受其他多元時(shí)間序列經(jīng)PCA轉(zhuǎn)化后特征值的影響。通過(guò)比較特征向量所形成的坐標(biāo)系之間的差異性來(lái)區(qū)分不同多元時(shí)間序列的特征，不僅能夠有效地對(duì)多元時(shí)間序列進(jìn)行特征描述，而且還能從時(shí)間維度和變量維度2個(gè)方向進(jìn)行數(shù)據(jù)降維，即原來(lái)n×m維降至k×k維．通常情況下，k

需要說(shuō)明的是，最小距離度量方法利用匈牙利算法對(duì)夾角距離矩陣進(jìn)行最優(yōu)化匹配求解，最壞情況下，其消耗的時(shí)間復(fù)雜度為O(k3)。然而，在大多數(shù)情況下，經(jīng)過(guò)PCA轉(zhuǎn)化后，較小的k值所對(duì)應(yīng)的主成分也能保留原始多元時(shí)間序列的大部分信息，使得最小距離度量能夠快速有效地對(duì)多元時(shí)間序列進(jìn)行相似性度量。

3數(shù)值實(shí)驗(yàn)

為了有效地評(píng)估MEros方法的性能，利用多元時(shí)間序列聚類(lèi)和分類(lèi)算法進(jìn)行距離度量質(zhì)量檢測(cè)，同時(shí)比較了幾種方法的計(jì)算時(shí)間效率。

3.1數(shù)據(jù)聚類(lèi)

層次聚類(lèi)方法能夠較好地從視覺(jué)角度表達(dá)聚類(lèi)結(jié)果的層次關(guān)系，并且能夠很好地評(píng)估數(shù)據(jù)距離度量方法的準(zhǔn)確性。本次實(shí)驗(yàn)?zāi)苓^(guò)層次聚類(lèi)算法和3種距離度量方法(MEros、Eros和歐氏距離Euclidean)來(lái)對(duì)等長(zhǎng)多元時(shí)間序列進(jìn)行聚類(lèi)分析，進(jìn)而比較3種距離度量方法的度量質(zhì)量．

實(shí)驗(yàn)數(shù)據(jù)為EEG多元時(shí)間序列數(shù)據(jù)集，它具有2類(lèi)標(biāo)簽且包含了20個(gè)多元時(shí)間序列，每個(gè)時(shí)間序列具有相同的觀測(cè)時(shí)間，即時(shí)間序列長(zhǎng)度相同且為256，是對(duì)64個(gè)部位進(jìn)行觀測(cè)的序列數(shù)據(jù)，可視為256×64的數(shù)據(jù)矩陣。同時(shí)，前后10個(gè)多元時(shí)間序列分別為同一類(lèi)數(shù)據(jù)，即序號(hào)為{1,2,3,4,5,6,7,8,9,10}為同一類(lèi)，其余{11,12,13,14,15,16,17,18,19,20}為另外一類(lèi)。在本次實(shí)驗(yàn)中，選取k=3為主成分分析降維后的維度，并將相應(yīng)的特征數(shù)據(jù)用于考查MEros和Eros的度量性能，其聚類(lèi)分析結(jié)果如圖1所示。從層次聚類(lèi)結(jié)果視圖中分析易知，距離度量方法Eros和歐氏距離Euclidean對(duì)等長(zhǎng)多元時(shí)間序列數(shù)據(jù)的聚類(lèi)出現(xiàn)明顯的錯(cuò)誤歸類(lèi)，如圖1(a)和1(c)中粗連線所示，它們將不同類(lèi)的數(shù)據(jù)對(duì)象錯(cuò)誤地歸為一類(lèi)。然而，本文提出的距離度量方法MEros能夠很好地將2類(lèi)數(shù)據(jù)成功歸類(lèi)，如圖1(b)所示，前后10個(gè)數(shù)據(jù)對(duì)象分別被歸成一類(lèi)，符合實(shí)際分類(lèi)情況。因此，可以說(shuō)MEros具有較好的距離度量質(zhì)量，能夠提高多元時(shí)間序列數(shù)據(jù)的聚類(lèi)性能。

3.2數(shù)據(jù)分類(lèi)

聚類(lèi)分析實(shí)驗(yàn)采用等長(zhǎng)多元時(shí)間序列EEG數(shù)據(jù)集和另外一個(gè)不等長(zhǎng)多元時(shí)間序列EEGEye數(shù)據(jù)集[16]，它們都是具有2類(lèi)標(biāo)簽的多元時(shí)間序列數(shù)據(jù)集。同時(shí)，EEGEye數(shù)據(jù)集中包含24個(gè)長(zhǎng)度不等的多元時(shí)間序列，其長(zhǎng)度范圍21~2 051，具有14個(gè)觀測(cè)屬性。

利用最近鄰分類(lèi)方法比較MEros、Eros和歐氏距離Euclidean或動(dòng)態(tài)時(shí)間彎曲DTW等方法在多元時(shí)間序列數(shù)據(jù)集的度量效果，通過(guò)分類(lèi)錯(cuò)誤率來(lái)評(píng)價(jià)距離度量方法的質(zhì)量。讓多元時(shí)間序列數(shù)據(jù)集中的每個(gè)序列都與其他序列進(jìn)行距離度量，查找與之最相似的序列作為檢測(cè)序列，并通過(guò)比較檢測(cè)序列與被檢測(cè)序列之間的標(biāo)簽來(lái)判斷分類(lèi)結(jié)果的正確性，最終通過(guò)平均分類(lèi)錯(cuò)誤率來(lái)衡量距離度量方法在分類(lèi)實(shí)驗(yàn)中的應(yīng)用性能。

另外，選取不同的降維維度來(lái)比較距離度量方法在分類(lèi)實(shí)驗(yàn)中的性能，即通過(guò)比較不同維度k的坐標(biāo)系來(lái)考察距離度量的質(zhì)量。對(duì)等長(zhǎng)時(shí)間序列數(shù)據(jù)集EEG和不等長(zhǎng)時(shí)間序列數(shù)據(jù)集EEGEye的分類(lèi)結(jié)果如圖2和3所示。從分類(lèi)實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，與傳統(tǒng)方法Eros相比，新方法MEros具有較好的分類(lèi)結(jié)果，說(shuō)明它具有更好地距離度量質(zhì)量，能夠提高多元時(shí)間序列數(shù)據(jù)挖掘的挖掘效果。另外，由于Euclidean和DTW分別善于對(duì)等長(zhǎng)和不等長(zhǎng)時(shí)間序列的相似性度量，故在實(shí)驗(yàn)中比較它們與新方法的分類(lèi)效果。在圖2分類(lèi)結(jié)果中發(fā)現(xiàn)，MEros具有最好的分類(lèi)結(jié)果，而在圖3分類(lèi)結(jié)果中可以知道，在對(duì)不等時(shí)間序列相似性比較時(shí)，DTW的分類(lèi)質(zhì)量?jī)?yōu)于MEros，其原因是EEGEye數(shù)據(jù)集的形態(tài)特征區(qū)分較為明顯，利用DTW通過(guò)最優(yōu)化路徑選擇并產(chǎn)生相應(yīng)的距離值，它能夠使其取得較好的分類(lèi)效果，但從時(shí)間效率比較實(shí)驗(yàn)中易知，DTW時(shí)間消耗不適合于大量高維時(shí)間序列的數(shù)據(jù)挖掘。

圖2　3種方法對(duì)EEG數(shù)據(jù)集的分類(lèi)結(jié)果 Fig.2　The classification results of three methods for EEG

圖3　3種方法對(duì)EEGEye數(shù)據(jù)集的分類(lèi)結(jié)果 Fig.3　The classification results of three methods for EEGEye

3.3效率比較

為了更好地比較距離度量方法之間的性能，除了評(píng)價(jià)它們?cè)诙嘣獣r(shí)間序列數(shù)據(jù)挖掘中的挖掘質(zhì)量，還需要評(píng)估其實(shí)際實(shí)驗(yàn)中的運(yùn)行效率。根據(jù)上面實(shí)驗(yàn)步驟，記錄每個(gè)檢測(cè)序列與被檢測(cè)序列之間相互匹配的CPU計(jì)算時(shí)間，將平均消耗時(shí)間作為最終的評(píng)估時(shí)間代價(jià)。另外，根據(jù)不同的k值，觀測(cè)距離度量方法的時(shí)間消耗情況。

3種距離度量方法對(duì)2組時(shí)間序列數(shù)據(jù)集的CPU時(shí)間代價(jià)如圖4和5所示。容易發(fā)現(xiàn)，與Euclidean和Eros相比，新方法MEros需要消耗較多的計(jì)算時(shí)間。然而，從實(shí)驗(yàn)結(jié)果中的縱軸數(shù)據(jù)量大小易知，這3種方法僅需要10-3秒級(jí)的時(shí)間。然而，對(duì)于不等長(zhǎng)時(shí)間序列度量來(lái)說(shuō)，DTW需要平均消耗7.2 s左右的時(shí)間。相比之下，適合計(jì)算不等長(zhǎng)時(shí)間序列之間距離的其他2種方法(Eros和MEros)的計(jì)算效率明顯較好。另外，如圖4和5(b)所示，MEros的計(jì)算時(shí)間隨著降維后維度k值的增長(zhǎng)而變大，其原因是MEros算法過(guò)程中的匈牙利方法計(jì)算速度依賴(lài)于k值，即O(k3)。k值越大，其計(jì)算時(shí)間代價(jià)越高，但其運(yùn)算速度保持在10-3秒級(jí)。因此，結(jié)合前面的分類(lèi)實(shí)驗(yàn)結(jié)果，可以說(shuō)明新方法MEros是一種較為快速且更為有效的多元時(shí)間序列相似性度量方法。

圖4　 3種方法對(duì)EEG數(shù)據(jù)集的時(shí)間代價(jià) Fig.4　The time cost of the three methods for EEG

圖5　3種方法對(duì)EEGEye數(shù)據(jù)集的時(shí)間代價(jià) Fig.5　The time cost of the three methods for EEGEye

4結(jié)束語(yǔ)

文章提出了一種基于特征矩陣的多元時(shí)間序列最小距離度量方法。該方法是基于主成分分析特征表示的距離度量方法，首先利用主成分分析對(duì)多元時(shí)間序列進(jìn)行特征分解，根據(jù)特征值的大小選擇相應(yīng)的特征向量構(gòu)建反映多元時(shí)間序列數(shù)據(jù)特征的坐標(biāo)系，并且通過(guò)比較坐標(biāo)系之間的差異性來(lái)度量多元時(shí)間序列之間的距離。該方法不依賴(lài)于特征值(方差)的大小來(lái)選擇夾角向量，而是通過(guò)度量正交坐標(biāo)系之間的相似性來(lái)反映原始多元時(shí)間序列的差異，進(jìn)而克服了傳統(tǒng)Eros方法的局限性。同時(shí)，通過(guò)匈牙利算法，把線性規(guī)劃問(wèn)題轉(zhuǎn)化為求解二分圖最小匹配問(wèn)題，其計(jì)算原理簡(jiǎn)單明了。最后，數(shù)值實(shí)驗(yàn)結(jié)果表明，新方法MEros是一種快速有效的多元時(shí)間序列距離度量方法。

與傳統(tǒng)Eros相比，新方法MEros具有較高的度量質(zhì)量，但其時(shí)間效率略低。MEors算法主要包括了多元時(shí)間序列的協(xié)方差矩陣、特征矩陣、距離矩陣和匈牙利算法等計(jì)算過(guò)程，其中前3個(gè)矩陣在傳統(tǒng)Eros算法中都需要被運(yùn)算，因此MEros的額外計(jì)算時(shí)間代價(jià)主要是由匈牙利算法求解二分圖最小匹配問(wèn)題引起的。另外，匈牙利算法對(duì)距離矩陣的求解效率依賴(lài)于多元時(shí)間序列的降維后維度k，其最壞情況下的計(jì)算時(shí)間效率為O(k3)。因此，如何提升匈牙利算法的計(jì)算時(shí)間或研究一種能夠快速求解式(6)的算法是將來(lái)有待研究的問(wèn)題。

參考文獻(xiàn):

[1]ESLING P, AGON C. Time-series data mining[J]. ACM Computing Surverys, 2012, 45(1): 11-12.

[2]李海林, 楊麗彬. 時(shí)間序列數(shù)據(jù)降維及特征表示新方法[J]. 控制與決策, 2013, 28(11):1718-1722.

LI Hailin, YANG Libin. Novel method of dimensionality reduction and feature representation for time series[J]. Control and Decision, 2013, 28(11):1718-1722.

[3]YANG K, SHAHABI C. An efficientknearest neighbor search for multivariate time series[J]. Information and Computation, 2007, 205(1): 65-98.

[4]韓敏, 李德才. 基于EOF-SVD模型的多元時(shí)間序列相關(guān)性研究及預(yù)測(cè)[J]. 系統(tǒng)仿真學(xué)報(bào), 2008, 20(7): 1669-1672

HAN Min, LI Decai. Multiple time series correlation extraction and prediction based on EOF-SVD model[J]. Journal of System Simulation, 2008, 20(7): 1669-1672.

[5]WENG Xiaoqing, SHEN Junyi. Classification of multivariate time series using two dimensional singular value decomposition[J]. Knowledge-Based Systems. 2008, 21(7): 535-539.

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

WU Husheng, ZHANG Fengming, ZHONG Bin. Similar pattern matching method for multivariate time series based on two-dimensional singular value decomposition[J]. Journal of Electronics & Information Technology, 2014, 36(4): 847-854.

[7]樊繼聰, 王友清, 秦泗釗. 聯(lián)合指標(biāo)獨(dú)立成分分析在多變量過(guò)程故障診斷中的應(yīng)用[J]. 自動(dòng)化學(xué)報(bào), 2013, 39(5): 494-501.

FAN Jicong, WANG Youqing, QIN Sizhao. Combined indices for ICA and their applications to multivariate process fault diagnosis[J]. Acta Automatica Sinica, 2013, 39(5): 494-501.

[8]梁勝杰, 張志華, 崔立林, 等. 基于主成分分析與核獨(dú)立成分分析的降維方法[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33(9): 2144-2148.

LIANG Shengjie, ZHANG Zhihua, CUI Lilin, et al. Dimensionality reduction method based on PCA and KICA[J]. Systems Engineering and Electronics, 2011, 33(9): 2144-2148.

[9]李正欣, 郭建勝, 惠曉濱, 等. 基于共同主成分的多元時(shí)間序列降維方法[J]. 控制與決策, 2013, 28(4): 531-536.

LI Zhengxin, GUO Jiansheng, HUI Xiaobin, et al. Dimension reduction method for multivariate time series based on common principal component[J]. Control and Decision, 2013, 28(4): 531-536.

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

LI Zhengxin, ZHANG Fengming, ZHANG Xiaofeng. Research on feature dimension reduction method for multivariate time series[J]. Journal of Chinese Computer Systems, 2013, 34(2): 338-346.

[11]LI Hailin. Asynchronism-based principal component analysis for time series data mining[J]. Expert Systems with Applications, 2014, 41(6): 2842-2850.

[12]YANKOV D, KEOGH E, REBBAPRAGADA U. Disk aware discord discovery: finding unusual time series in terabyte sized datasets[J]. Knowledge and Information Systems, 2007, 17(2): 381-390.

[13]CHEN Yanping, HU Bing, KEOGH E, et al. DTW-D: time series semi-supervised learning from a single example[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago, USA, 2013: 383-391.

[14]YANG K, SHAHABI C. A PCA-based similarity measure for multivariate time series[C]//Proceedings of the 2nd ACM International Workshop on Multimedia Databases. Washington, DC, USA, 2004: 65-74.

[15]何堅(jiān)勇. 運(yùn)籌學(xué)基礎(chǔ)[M]. 北京: 清華大學(xué)出版社, 2006: 217-220.

[16]BACHE K, LICHMAN M. UCI machine learning repository[EB/OL]. (2013-12-21)[2014-04-28]. http://archive.ics.uci.edu/ml.

李海林，男，1982年生，副教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與決策支持, 主持國(guó)家自然科學(xué)基金和省部級(jí)青年基金各1項(xiàng),發(fā)表學(xué)術(shù)論文30余篇，其中被SCI檢索7篇、EI檢索10余篇。

郭韌，女，1975年生，講師，博士研究生，主要研究方向?yàn)橹R(shí)管理與數(shù)據(jù)挖掘，發(fā)表學(xué)術(shù)論文近20篇，其中被CSSCI檢索9篇。

萬(wàn)?；?，1982年生，講師，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘與決策支持，發(fā)表學(xué)術(shù)論文10余篇。