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

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150401.1459.001.html

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

李海林，郭韌，萬校基

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

摘要：相似性度量是多元時間序列數據挖掘任務過程中一項重要的前期工作，度量質量直接影響到后期整個數據挖掘的性能和結果。利用主成分分析方法對數據集中的每個多元時間序列數據進行特征分析，提取其特征矩陣并且構建相應的新正交坐標系。通過夾角公式來度量2個正交坐標系之間距離，并且結合匈牙利算法計算它們之間的最小距離，進而實現了一種基于特征矩陣的多元時間序列最小距離度量方法。實驗結果表明，與傳統方法相比，新方法具有較好的相似性度量質量，提高了多元時間序列的數據挖掘效果。

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

DOI:10.3969/j.issn.1673-4785.201405047

中圖分類號：TP301 文獻標志碼：A

收稿日期：2014-05-23. 網絡出版日期：2015-04-01.

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

作者簡介：

中文引用格式：李海林，郭韌，萬校基. 基于特征矩陣的多元時間序列最小距離度量方法[J]. 智能系統學報, 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.

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

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

針對上述問題，本文提出一種基于特征矩陣的多元時間序列最小距離度量方法，它利用主成分分析對多元時間序列進行特征表示，并獲得相應的特征矩陣并構建相應的正交坐標系。另外，通過夾角公式來度量2個多元時間序列對應正交坐標系中不同坐標軸之間的距離，并結合匈牙利算法計算它們之間的最小距離。該方法不依賴于方差的大小來選擇夾角向量，而是通過度量正交坐標系之間的相似性來反映原始多元時間序列的差異，進而克服了傳統Eros方法的局限性。

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

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

(1)

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

(2)

Eros距離度量方法就是一種基于特征空間的多元時間序列相似性度量方法[14]。它利用主成分分析方法對多元時間序列進行特征分解，得到相應的特征值和特征矩陣。同時，根據特征值的大小，選取對應的特征向量形成特征空間坐標系，并且結合綜合權重W來計算2個多元時間序列A和B對應特征空間坐標系之間的相似性，即

(3)

2最小距離度量方法

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

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

(4)

(5)

通過夾角公式計算2個多元時間序列對應前k個特征向量中任意2個向量之間的夾角距離矩陣為

最小距離度量方法就是基于夾角距離矩陣D，根據傳統Eros思想找到一組最優匹配，使得該匹配具有最小的距離。即通過PCA降維后，一個多元時間序列的前k個特征向量能夠與另一個多元時間序列的前k個特征向量對應比較，并取得最小距離度量。因此，該思路可以歸納為一個線性規劃問題：

(6)

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

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

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

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

輸出：最小距離度量dmin。

步驟：

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

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

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

基于特征矩陣的多元時間序列最小距離度量方法能夠有效地描述原始多元時間序列之間的相似性。同時，與傳統Eros方法相比，最小距離度量方法MEros不受其他多元時間序列經PCA轉化后特征值的影響。通過比較特征向量所形成的坐標系之間的差異性來區分不同多元時間序列的特征，不僅能夠有效地對多元時間序列進行特征描述，而且還能從時間維度和變量維度2個方向進行數據降維，即原來n×m維降至k×k維．通常情況下，k

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

3數值實驗

為了有效地評估MEros方法的性能，利用多元時間序列聚類和分類算法進行距離度量質量檢測，同時比較了幾種方法的計算時間效率。

3.1數據聚類

層次聚類方法能夠較好地從視覺角度表達聚類結果的層次關系，并且能夠很好地評估數據距離度量方法的準確性。本次實驗能過層次聚類算法和3種距離度量方法(MEros、Eros和歐氏距離Euclidean)來對等長多元時間序列進行聚類分析，進而比較3種距離度量方法的度量質量．

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

3.2數據分類

聚類分析實驗采用等長多元時間序列EEG數據集和另外一個不等長多元時間序列EEGEye數據集[16]，它們都是具有2類標簽的多元時間序列數據集。同時，EEGEye數據集中包含24個長度不等的多元時間序列，其長度范圍21~2 051，具有14個觀測屬性。

利用最近鄰分類方法比較MEros、Eros和歐氏距離Euclidean或動態時間彎曲DTW等方法在多元時間序列數據集的度量效果，通過分類錯誤率來評價距離度量方法的質量。讓多元時間序列數據集中的每個序列都與其他序列進行距離度量，查找與之最相似的序列作為檢測序列，并通過比較檢測序列與被檢測序列之間的標簽來判斷分類結果的正確性，最終通過平均分類錯誤率來衡量距離度量方法在分類實驗中的應用性能。

另外，選取不同的降維維度來比較距離度量方法在分類實驗中的性能，即通過比較不同維度k的坐標系來考察距離度量的質量。對等長時間序列數據集EEG和不等長時間序列數據集EEGEye的分類結果如圖2和3所示。從分類實驗結果可以發現，與傳統方法Eros相比，新方法MEros具有較好的分類結果，說明它具有更好地距離度量質量，能夠提高多元時間序列數據挖掘的挖掘效果。另外，由于Euclidean和DTW分別善于對等長和不等長時間序列的相似性度量，故在實驗中比較它們與新方法的分類效果。在圖2分類結果中發現，MEros具有最好的分類結果，而在圖3分類結果中可以知道，在對不等時間序列相似性比較時，DTW的分類質量優于MEros，其原因是EEGEye數據集的形態特征區分較為明顯，利用DTW通過最優化路徑選擇并產生相應的距離值，它能夠使其取得較好的分類效果，但從時間效率比較實驗中易知，DTW時間消耗不適合于大量高維時間序列的數據挖掘。

圖2　3種方法對EEG數據集的分類結果 Fig.2　The classification results of three methods for EEG

圖3　3種方法對EEGEye數據集的分類結果 Fig.3　The classification results of three methods for EEGEye

3.3效率比較

為了更好地比較距離度量方法之間的性能，除了評價它們在多元時間序列數據挖掘中的挖掘質量，還需要評估其實際實驗中的運行效率。根據上面實驗步驟，記錄每個檢測序列與被檢測序列之間相互匹配的CPU計算時間，將平均消耗時間作為最終的評估時間代價。另外，根據不同的k值，觀測距離度量方法的時間消耗情況。

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

圖4　 3種方法對EEG數據集的時間代價 Fig.4　The time cost of the three methods for EEG

圖5　3種方法對EEGEye數據集的時間代價 Fig.5　The time cost of the three methods for EEGEye

4結束語

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

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

參考文獻:

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

[2]李海林, 楊麗彬. 時間序列數據降維及特征表示新方法[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模型的多元時間序列相關性研究及預測[J]. 系統仿真學報, 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]吳虎勝, 張鳳鳴, 鐘斌. 基于二維奇異值分解的多元時間序列相似匹配方法[J]. 電子與信息學報, 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]樊繼聰, 王友清, 秦泗釗. 聯合指標獨立成分分析在多變量過程故障診斷中的應用[J]. 自動化學報, 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]梁勝杰, 張志華, 崔立林, 等. 基于主成分分析與核獨立成分分析的降維方法[J]. 系統工程與電子技術, 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]李正欣, 郭建勝, 惠曉濱, 等. 基于共同主成分的多元時間序列降維方法[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]李正欣, 張鳳鳴, 張曉豐, 等. 多元時間序列特征降維方法研究[J]. 小型微型計算機系統, 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]何堅勇. 運籌學基礎[M]. 北京: 清華大學出版社, 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年生，副教授，博士，主要研究方向為數據挖掘與決策支持, 主持國家自然科學基金和省部級青年基金各1項,發表學術論文30余篇，其中被SCI檢索7篇、EI檢索10余篇。

郭韌，女，1975年生，講師，博士研究生，主要研究方向為知識管理與數據挖掘，發表學術論文近20篇，其中被CSSCI檢索9篇。

萬校基，男，1982年生，講師，博士，主要研究方向為數據挖掘與決策支持，發表學術論文10余篇。