第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jun.2015 D0:10.3969/j.issn.1673-4785.201405047 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150401.1459.001.html 基于特征矩阵的多元时间序列最小距离度量方法 李海林，郭韧，万校基 (华侨大学信息管理系，福建泉州362021) 摘要：相似性度量是多元时间序列数据挖掘任务过程中一项重要的前期工作，度量质量直接影响到后期整个数据 挖掘的性能和结果。利用主成分分析方法对数据集中的每个多元时间序列数据进行特征分析，提取其特征矩阵并 且构建相应的新正交坐标系。通过夹角公式来度量2个正交坐标系之间距离，并且结合匈牙利算法计算它们之间 的最小距离，进而实现了一种基于特征矩阵的多元时间序列最小距离度量方法。实验结果表明，与传统方法相比， 新方法具有较好的相似性度量质量，提高了多元时间序列的数据挖掘效果。 关键词：多元时间序列：相似性度量：特征矩阵：最小距离：主成分分析：匈牙利算法；数据挖掘 中图分类号：TP301文献标志码：A文章编号：1673-4785(2015)03-0442-06 中文引用格式：李海林，郭韧，万校基.基于特征矩阵的多元时间序列最小距离度量方法[J].智能系统学报，2015,10(3)：442447. 英文引用格式：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 ex- tracted 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 com- putation 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 meth- od 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 compo- nent analysis;Hungary algorithm;data mining 多元时间序列是数据挖掘领域中常见的一种数 2种高维特性，即时间属性维度和变量属性维度，它 据类型，广泛存在于经济、金融、医疗卫生、电子信息 们决定了多元时间序列数据的复杂性，同时也影响 和航空航天等行业中山.与其他数据类型相比，它有 着数据挖掘技术在多元时间序列数据中的应用性 能。为了解决多元时间序列的维灾问题，许多学者 收稿日期：2014-05-23.网络出版日期：2015-04-01. 基金项目：国家自然科学基金资助项目(61300139)：福建省中青年 提出利用数据降维和特征表示等方法结合相关技术 教师教育科研项目(JAS14024)：华侨大学中青年教师科 来提高多元时间序列的数据挖掘性能[2)。除了简 研提升资助计划项目(ZQN-PY220). 通信作者：李海林.E-mail:hailin@(mail.dut.cdu.cn. 单运用一元时间序列的降维技术和特征表示外，通
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０５０４７ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０４０１．１４５９．００１．ｈｔｍｌ 基于特征矩阵的多元时间序列最小距离度量方法 李海林，郭韧，万校基 （华侨大学 信息管理系，福建 泉州 ３６２０２１） 摘 要：相似性度量是多元时间序列数据挖掘任务过程中一项重要的前期工作，度量质量直接影响到后期整个数据 挖掘的性能和结果。 利用主成分分析方法对数据集中的每个多元时间序列数据进行特征分析，提取其特征矩阵并 且构建相应的新正交坐标系。 通过夹角公式来度量 ２ 个正交坐标系之间距离，并且结合匈牙利算法计算它们之间 的最小距离，进而实现了一种基于特征矩阵的多元时间序列最小距离度量方法。 实验结果表明，与传统方法相比， 新方法具有较好的相似性度量质量，提高了多元时间序列的数据挖掘效果。 关键词：多元时间序列；相似性度量；特征矩阵；最小距离；主成分分析；匈牙利算法；数据挖掘 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４４２⁃０６ 中文引用格式：李海林，郭韧，万校基． 基于特征矩阵的多元时间序列最小距离度量方法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４４２⁃４４７． 英文引用格式：ＬＩ Ｈａｉｌｉｎ， ＧＵＯ Ｒｅｎ， ＷＡＮ Ｘｉａｏｊｉ． Ａ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍｅｔｈｏｄ ｆｏｒ ａ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｆｅａｔｕｒｅ ｍａｔｒｉｘ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４４２⁃４４７． Ａ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍｅｔｈｏｄ ｆｏｒ ａ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｆｅａｔｕｒｅ ｍａｔｒｉｘ ＬＩ Ｈａｉｌｉｎ， ＧＵＯ Ｒｅｎ， ＷＡＮ Ｘｉａｏｊｉ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ， Ｈｕａｑｉａｏ Ｕｎｉｖｅｒｓｉｔｙ， Ｑｕａｎｚｈｏｕ ３６２０２１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ｐｒｅｌｉｍｉｎａｒｙ ｗｏｒｋｓ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｄａｔａ ｍｉｎｉｎｇ． Ｉｔｓ ｑｕａｌｉｔｙ ｄｉｒｅｃｔｌｙ ｉｎｆｌｕｅｎｃｅｓ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｌａｔｅｒ ｔａｓｋｓ ｏｆ ｄａｔａ ｍｉｎｉｎｇ． Ｔｈｅ ｄａｔａ ｏｆ ｅｖｅｒｙ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｉｎ ｄａｔａｓｅｔ ｃａｎ ｂｅ ａｎａｌｙｚｅｄ ｂｙ ｔｈｅ ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ． Ｔｈｅ ｆｅａｔｕｒｅ ｍａｔｒｉｃｅｓ ａｒｅ ｅｘ⁃ ｔｒａｃｔｅｄ ｔｏ ｃｏｎｓｔｒｕｃｔ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｎｅｗ ｏｒｔｈｏｇｏｎａｌ ｃｏｏｒｄｉｎａｔｅ ｓｙｓｔｅｍｓ ｗｈｏｓｅ ｄｉｓｔａｎｃｅ ｃａｎ ｂｅ ｍｅａｓｕｒｅｄ ｂｙ ｃｏｓｉｎｅ ｖａｌｕｅ ｏｆ ｔｈｅ ａｎｇｌｅｓ ｂｅｔｗｅｅｎ ｔｗｏ ａｘｅｓ． Ｍｅａｎｗｈｉｌｅ， ｔｈｅ Ｈｕｎｇａｒｙ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｃｏｍ⁃ ｐｕｔａｔｉｏｎ ｏｆ ｔｈｅ ｔｗｏ ｃｏｏｒｄｉｎａｔｅ ｓｙｓｔｅｍｓ． Ｉｎ ｔｈｉｓ ｗａｙ， ｔｈｅ ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｆｅａｔｕｒｅ ｍａｔｒｉｘ ｉｓ ａｃｈｉｅｖｅｄ． Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｅｘｐｅｒｉｍｅｎｔ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈ⁃ ｏｄ ｈａｓ ｂｅｔｔｅｒ ｑｕａｌｉｔｙ ｏｆ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｔｈａｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｏｎｅｓ ａｎｄ ｉｍｐｒｏｖｅｓ ｔｈｅ ｅｆｆｅｃｔｓ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ｆｏｒ ｔｈｅ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ． Ｋｅｙｗｏｒｄｓ： ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ； ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ； ｆｅａｔｕｒｅ ｍａｔｒｉｘ； ｍｉｎｉｍｕｍ ｄｉｓｔａｎｃｅ； ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏ⁃ ｎｅｎｔ ａｎａｌｙｓｉｓ； Ｈｕｎｇａｒｙ ａｌｇｏｒｉｔｈｍ； ｄａｔａ ｍｉｎｉｎｇ 收稿日期：２０１４⁃０５⁃２３． 网络出版日期：２０１５⁃０４⁃０１． 基金项目：国家自然科学基金资助项目（６１３００１３９）； 福建省中青年 教师教育科研项目（ ＪＡＳ１４０２４）； 华侨大学中青年教师科 研提升资助计划项目（ＺＱＮ⁃ＰＹ２２０）． 通信作者：李海林． Ｅ⁃ｍａｉｌ： ｈａｉｌｉｎ＠ ｍａｉｌ．ｄｌｕｔ．ｅｄｕ．ｃｎ． 多元时间序列是数据挖掘领域中常见的一种数 据类型，广泛存在于经济、金融、医疗卫生、电子信息 和航空航天等行业中［１］ ．与其他数据类型相比，它有 ２ 种高维特性，即时间属性维度和变量属性维度，它 们决定了多元时间序列数据的复杂性，同时也影响 着数据挖掘技术在多元时间序列数据中的应用性 能。 为了解决多元时间序列的维灾问题，许多学者 提出利用数据降维和特征表示等方法结合相关技术 来提高多元时间序列的数据挖掘性能［２⁃３］ 。 除了简 单运用一元时间序列的降维技术和特征表示外，通
第3期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 443· 常利用数据变换的方法来实现数据处理，达到减噪 方法，是基于某种类型的投影机制，将高维的数据向 降冗的效果，例如奇异值分解4]、独立成分分 低维空间（特征空间）投影，并期望在特征空间中数 析和主成分分析0等。其中，主成分分析 据的方差最大。通过选择占有绝大部分信息的主成 (principal component analysis,PCA)是多元时间序 分来实现数据降维，同时进行特征表示。换句话说， 列数据降维和特征表示中最常用的方法之一[山)，它 如果把所有的点映射在一起，则几乎所有的原始信 通过对多元时间序列的协方差矩阵进行特征分解， 息都将丢失：若映射后数据的方差尽可能大，则数据 实现数据空间变换得到方差最大的主成分作为原始 点将被分开，使得距离信息保留得更多。因此，传统 数据的特征。同时，根据方差大小选择对应的前几 的主成分分析方法通过方差的大小来选择主成分。 个主成分作为多元时间序列的数据特征，从而实现 对于多元时间序列X=[X,X2…X]可以 原始多元时间序列的变量属性维度的降维。 表示成一个n×m的矩阵，即X=(x写)xm。其 在多元时间序列数据挖掘前期任务中，除了进 中，X,表示第个变量属性所形成的序列，x:表 行数据降维和特征表示外，相似性（或距离）度量也 示多元时间序列第i个时间点第j个变量的观测 是一项重要的工作，其度量质量直接影响着后期数 值，n和m分别表示多元时间序列的时间维度 据挖掘技术的性能和挖掘质量。例如，多元时间序 (长度)和变量维度。 列的聚类、分类、相似性查找和匹配、异常检测等都 根据主成分分析原理，首先需要计算多元时间 需要进行距离度量。在时间序列数据挖掘中，最常 序列变量之间的协方差，得到一个协方差矩阵 用的2种方法是欧氏距离(Euclidean distance)[和 Smxm,再通过奇异值分解对协方差矩阵Smxm进行特 动态时间弯曲方法(dynamic time warping, 征值和特征向量分解，得到以特征值大小排列形成 DTW))。前者能较快地计算序列之间的相似性， 特征值对角矩阵Σmxm=diag(入1，d2,…,入m)和对 适用于等长时间序列的相似性度量：后者对不等长 应的特征矩阵Umxm=[山1山2…u】,故有 时间序列的距离度量具有较强的鲁棒性，但需要二 Snkm=UxΣxnUExm (1) 阶的时间和空间复杂度，不利用大量较长时间序列 利用主成分分析方法对多元时间序列Xxm进 的相似性度量。针对主成分分析方法得到的特征数 行特征分解，可以得到相应的特征值和特征矩阵。 据，存在许多距离度量方法来实现特征数据的相似 同时，根据特征值（即方差）的大小，可以选择对应 性计算。其中，较为常用的是一种被称为EOs的距 的特征向量作为特征空间中的坐标轴，进而得到相 离度量方法[1，它利用夹角公式来度量2个特征向 应的主成分。选取前k(k<m)个主成分作为该多 量之间的关系，同时以相应的方差作为权重，较好地 元时间序列的特征，即 描述了多元时间序列经过特征变换后特征数据之间 Ynxt=X.xmUmxt (2) 的差异性。然而，Eos是根据特征序列方差大小来 与原始多元时间序列Xxm相比，由于k<m, 选择相应特征向量进行匹配，迫使较大方差对应的 特征序列Y4实现了数据降维.同时，其对原始数据 特征向量被用来计算相似性。另外，权重是由方差 信息的保存量为e=∑，A,/∑，A。然而，特征 的大小决定，使得Eos因过分强调方差的重要性而 序列Y4虽然对多元时间序列进行了降维处理，但 忽视了特征空间之间的差异性。 仅局限于从变量属性维度进行数据压缩，没有实现 针对上述问题，本文提出一种基于特征矩阵的 从时间属性维度方向的数据降维。鉴于此，部分学 多元时间序列最小距离度量方法，它利用主成分分 者通过比较数据降维后的特征空间来区分原始多元 析对多元时间序列进行特征表示，并获得相应的特 时间序列的数据分布特征[4。 征矩阵并构建相应的正交坐标系。另外，通过夹角 Eos距离度量方法就是一种基于特征空间的多 公式来度量2个多元时间序列对应正交坐标系中不 元时间序列相似性度量方法4。它利用主成分分 同坐标轴之间的距离，并结合匈牙利算法计算它们 析方法对多元时间序列进行特征分解，得到相应的 之间的最小距离。该方法不依赖于方差的大小来选 特征值和特征矩阵。同时，根据特征值的大小，选取 择夹角向量，而是通过度量正交坐标系之间的相似 对应的特征向量形成特征空间坐标系，并且结合综 性来反映原始多元时间序列的差异，进而克服了传 合权重W来计算2个多元时间序列A和B对应特征 统Eros方法的局限性。 空间坐标系之间的相似性，即 1 主成分分析与Eros距离度量 Eros(A,B,W)= ∑10，cos0 主成分分析(PCA)是一种最常用的线性降维 (3)
常利用数据变换的方法来实现数据处理，达到减噪 降冗的 效 果， 例 如 奇 异 值 分 解［４⁃６］ 、 独 立 成 分 分 析［７⁃８］和 主 成 分 分 析［９⁃１０］ 等。 其 中， 主 成 分 分 析 （ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ， ＰＣＡ） 是多元时间序 列数据降维和特征表示中最常用的方法之一［１１］ ，它 通过对多元时间序列的协方差矩阵进行特征分解， 实现数据空间变换得到方差最大的主成分作为原始 数据的特征。 同时，根据方差大小选择对应的前几 个主成分作为多元时间序列的数据特征，从而实现 原始多元时间序列的变量属性维度的降维。 在多元时间序列数据挖掘前期任务中，除了进 行数据降维和特征表示外，相似性（或距离）度量也 是一项重要的工作，其度量质量直接影响着后期数 据挖掘技术的性能和挖掘质量。 例如，多元时间序 列的聚类、分类、相似性查找和匹配、异常检测等都 需要进行距离度量。 在时间序列数据挖掘中，最常 用的 ２ 种方法是欧氏距离（Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ） ［１２］和 动 态 时 间 弯 曲 方 法 （ ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ， ＤＴＷ） ［１３］ 。 前者能较快地计算序列之间的相似性， 适用于等长时间序列的相似性度量；后者对不等长 时间序列的距离度量具有较强的鲁棒性，但需要二 阶的时间和空间复杂度，不利用大量较长时间序列 的相似性度量。 针对主成分分析方法得到的特征数 据，存在许多距离度量方法来实现特征数据的相似 性计算。 其中，较为常用的是一种被称为 Ｅｒｏｓ 的距 离度量方法［１４］ ，它利用夹角公式来度量 ２ 个特征向 量之间的关系，同时以相应的方差作为权重，较好地 描述了多元时间序列经过特征变换后特征数据之间 的差异性。 然而，Ｅｒｏｓ 是根据特征序列方差大小来 选择相应特征向量进行匹配，迫使较大方差对应的 特征向量被用来计算相似性。 另外，权重是由方差 的大小决定，使得 Ｅｒｏｓ 因过分强调方差的重要性而 忽视了特征空间之间的差异性。 针对上述问题，本文提出一种基于特征矩阵的 多元时间序列最小距离度量方法，它利用主成分分 析对多元时间序列进行特征表示，并获得相应的特 征矩阵并构建相应的正交坐标系。 另外，通过夹角 公式来度量 ２ 个多元时间序列对应正交坐标系中不 同坐标轴之间的距离，并结合匈牙利算法计算它们 之间的最小距离。 该方法不依赖于方差的大小来选 择夹角向量，而是通过度量正交坐标系之间的相似 性来反映原始多元时间序列的差异，进而克服了传 统 Ｅｒｏｓ 方法的局限性。 １ 主成分分析与 Ｅｒｏｓ 距离度量 主成分分析（ ＰＣＡ） 是一种最常用的线性降维 方法，是基于某种类型的投影机制，将高维的数据向 低维空间（特征空间）投影，并期望在特征空间中数 据的方差最大。 通过选择占有绝大部分信息的主成 分来实现数据降维，同时进行特征表示。 换句话说， 如果把所有的点映射在一起，则几乎所有的原始信 息都将丢失；若映射后数据的方差尽可能大，则数据 点将被分开，使得距离信息保留得更多。 因此，传统 的主成分分析方法通过方差的大小来选择主成分。 对于多元时间序列 Ｘ ＝ Ｘ１ Ｘ２ … Ｘｍ [ ] 可以 表示成一个 ｎ × ｍ 的矩阵，即 Ｘ ＝ （ ｘｉｊ） ｎ ×ｍ 。 其 中， Ｘｊ 表示第 ｊ 个变量属性所形成的序列， ｘｉｊ 表 示多元时间序列第 ｉ 个时间点第 ｊ 个变量的观测 值， ｎ 和 ｍ 分别表示多元时间序列的时间维度 （长度）和变量维度。 根据主成分分析原理，首先需要计算多元时间 序列变 量 之 间 的 协 方 差， 得 到 一 个 协 方 差 矩 阵 Ｓｍ×ｍ ，再通过奇异值分解对协方差矩阵 Ｓｍ×ｍ 进行特 征值和特征向量分解，得到以特征值大小排列形成 特征值对角矩阵 Σ ｍ×ｍ ＝ ｄｉａｇ λ１ ，λ２ ，…，λ ｍ ( ) 和对 应的特征矩阵 Ｕｍ×ｍ ＝ ｕ１ ｕ２ … ｕｍ [ ] ，故有 Ｓｍ×ｍ ＝ Ｕｍ×ｍ Σ ｍ×ｍ Ｕ Ｔ ｍ×ｍ （１） 利用主成分分析方法对多元时间序列 Ｘｎ×ｍ 进 行特征分解，可以得到相应的特征值和特征矩阵。 同时，根据特征值（即方差）的大小，可以选择对应 的特征向量作为特征空间中的坐标轴，进而得到相 应的主成分。 选取前 ｋ（ｋ ＜ ｍ） 个主成分作为该多 元时间序列的特征，即 Ｙｎ×ｋ ＝ Ｘｎ×ｍ Ｕｍ×ｋ （２） 与原始多元时间序列 Ｘｎ×ｍ 相比，由于 ｋ ＜ ｍ ， 特征序列 Ｙｎ×ｋ 实现了数据降维．同时，其对原始数据 信息的保存量为 ｅ ＝∑ ｋ ｉ ＝ １ λｉ ／∑ ｍ ｊ ＝ １ λｊ 。 然而，特征 序列 Ｙｎ×ｋ 虽然对多元时间序列进行了降维处理，但 仅局限于从变量属性维度进行数据压缩，没有实现 从时间属性维度方向的数据降维。 鉴于此，部分学 者通过比较数据降维后的特征空间来区分原始多元 时间序列的数据分布特征［１４］ 。 Ｅｒｏｓ 距离度量方法就是一种基于特征空间的多 元时间序列相似性度量方法［１４］ 。 它利用主成分分 析方法对多元时间序列进行特征分解，得到相应的 特征值和特征矩阵。 同时，根据特征值的大小，选取 对应的特征向量形成特征空间坐标系，并且结合综 合权重 Ｗ 来计算２ 个多元时间序列 Ａ 和 Ｂ 对应特征 空间坐标系之间的相似性，即 Ｅｒｏｓ（Ａ，Ｂ，Ｗ） ＝ ∑ ｋ ｉ ＝ １ ｗｉ ｜ ＜ ｕ ａ ｉ ，ｕ ｂ ｉ ＞ ｜ ＝ ∑ ｋ ｉ ＝ １ ｗｉ ｃｏｓ θｉ （３） 第 ３ 期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 ·４４３·
·444. 智能系统学报 第10卷 式中：0：∈0是利用主成分分析对所有多元时间序 量。因此，该思路可以归纳为一个线性规划问题： 列进行特征分解后其第讠组特征值在前k组特征值 中的比率，即0，=∑r(.0/∑∑rG, MEros(A,B,k)=min (6) )。N表示数据库中多元时间序列的数目， W(,)表示第j个多元时间序列经主成分分析后的 s.t. 第i个特征值，即W,i)=}。 式中：{c}xk是一个二元矩阵，且当c=1时，表示 2最小距离度量方法 夹角距离矩阵D中元素d(i,)对最小距离度量具 有贡献值。 Eros距离度量方法是一种基于特征空间坐标系 上述线性规划问题实质是一个线性任务分配问 的相似性度量方法，让2个多元时间序列经PCA转 题，即k个人分配k项任务，一个人只能分配一项任 换后前k个坐标轴根据它们的特征值大小进行相应 务，一项任务只能分配给一个人。为此，选取匈牙利 的夹角度量，即一个多元时间序列第i个特征向量 算法[1)来解决该线性任务分配问题，该算法是用来 与另一个多元时间序列的第i个特征向量进行夹角 解决二分图最小匹配问题的经典算法。对于多元时 度量。然而，在某些情况下，一个多元时间序列的第 间序列的主成分之间的最小夹角距离可以从矩阵D i个特征向量可能与另一个多元时间序列的第j个 出发，把该矩阵的各行和各列分别视为线性任务分 特征向量的夹角更相似。鉴于此种情况，提出基于 配问题中的人员和任务，即如何从距离矩阵D中把 特征矩阵的多元时间序列最小距离度量方法。 第列的任务分配给第i行的对象，使得最终每个人 最小距离度量方法的主要思想就是利用主成分 完成一项任务，且所有人员完成所有任务后花费的 分析方法对数据库中的每个多元时间序列进行特征 代价要求最小。 分解，得到相应的特征向量。通过夹角公式分别计算 由于多元时间序列经过主成分分析方法进行变 2个多元时间序列对应前k个特征向量中任意2个向 换后，不同多元时间序列的特征向量可以构成不同 量之间的相似性，并建立夹角距离矩阵。最后通过匈 的坐标系，不同坐标系的维表示的意义各不相同。 牙利算法[5]对该距离矩阵实现最小距离度量。由于 若简单按照各特征值大小顺序来构建坐标系，并且 该方法是基于传统Eos的多元时间序列距离度量方 比较对应坐标系之间的夹角来描述多元时间序列特 法，故亦可称之为MEros(minimum Eros)。 征的差异性，将显得不合理。针对此问题，利用匹配 假设2个多元时间序列A,xm和Bxm,通过主 不同时间序列的特征向量构建的坐标系之间的最小 成分分析方法得到相应的特征矩阵为U。和U。,且 距离，便可以使得2个坐标系中最相似的维被相互 U。=[uu…u]和U。=[…],则利用 比较，进而更为灵活有效地对多元时间序列的特征 夹角公式来计算由特征矩阵U,和U。中向量所形成 进行距离度量。 的坐标系中前k个坐标轴之间的相似性，即 综上所述，基于特征矩阵的多元时间序列最小 Sim(i,j)=(u,u2 =I cos 0 I (4) 距离度量算法如下。 由于|cos0:|∈[0,1]，故任意2条坐标轴之间的相 算法：最小距离度量da=MEros(A,B,k)。 似性Sim(i,)可以转化为相应的距离度量公式，即 输入：多元时间序列A与B,降维后的维度k。 d(i,j)=1 Sim(i,j)=1 -1 cos 0I (5) 输出：最小距离度量dn。 通过夹角公式计算2个多元时间序列对应前k个特 步骤： 征向量中任意2个向量之间的夹角距离矩阵为 1)对多元时间序列A与B计算协方差矩阵，即 「d(1,1)d(1,2)…d(1,k) S=E[(A-E[A])(A-E[A])T]S=E[(B- d(2,1)d(2,2)…d(2,k) E[B])(B-E[B])]; 2)利用奇异值分解方法对协方差矩阵进行特 Ld(k,1)d(k,2)…d(k,k)」 征分解，使得Sa=UE4UA和SB=UEUB,其中 最小距离度量方法就是基于夹角距离矩阵D, U4和U。分别为2个协方差矩阵的特征矩阵，且向 根据传统EOs思想找到一组最优匹配，使得该匹配 量按特征值大小排列： 具有最小的距离。即通过PCA降维后，一个多元时 3)分别在U。和Ug中选取前k个特征向量作 间序列的前k个特征向量能够与另一个多元时间序 为新坐标系的坐标轴，根据距离度量式(5)，建立夹 列的前k个特征向量对应比较，并取得最小距离度 角距离矩阵D;
式中： ｗｉ ∈ ｗ 是利用主成分分析对所有多元时间序 列进行特征分解后其第 ｉ 组特征值在前 ｋ 组特征值 中的比率，即 ｗｉ ＝ ∑ ｉ ｊ ＝ １ Ｗ（ｊ，ｉ） ／∑ ｋ ｌ ＝ １∑ Ｎ ｊ ＝ １ Ｗ（ｊ， ｌ）。 Ｎ 表 示 数 据 库 中 多 元 时 间 序 列 的 数 目， Ｗ(ｊ，ｉ) 表示第 ｊ 个多元时间序列经主成分分析后的 第 ｉ 个特征值，即 Ｗ（ｊ，ｉ） ＝ λ ｊ ｉ 。 ２ 最小距离度量方法 Ｅｒｏｓ 距离度量方法是一种基于特征空间坐标系 的相似性度量方法，让 ２ 个多元时间序列经 ＰＣＡ 转 换后前 ｋ 个坐标轴根据它们的特征值大小进行相应 的夹角度量，即一个多元时间序列第 ｉ 个特征向量 与另一个多元时间序列的第 ｉ 个特征向量进行夹角 度量。 然而，在某些情况下，一个多元时间序列的第 ｉ 个特征向量可能与另一个多元时间序列的第 ｊ 个 特征向量的夹角更相似。 鉴于此种情况，提出基于 特征矩阵的多元时间序列最小距离度量方法。 最小距离度量方法的主要思想就是利用主成分 分析方法对数据库中的每个多元时间序列进行特征 分解，得到相应的特征向量。 通过夹角公式分别计算 ２ 个多元时间序列对应前 ｋ 个特征向量中任意 ２ 个向 量之间的相似性，并建立夹角距离矩阵。 最后通过匈 牙利算法［１５］对该距离矩阵实现最小距离度量。 由于 该方法是基于传统 Ｅｒｏｓ 的多元时间序列距离度量方 法，故亦可称之为 ＭＥｒｏｓ （ｍｉｎｉｍｕｍ Ｅｒｏｓ）。 假设 ２ 个多元时间序列 Ａｎ１ ×ｍ 和 Ｂｎ２ ×ｍ ，通过主 成分分析方法得到相应的特征矩阵为 Ｕａ 和 Ｕｂ ，且 Ｕａ ＝ ｕ ａ １ ｕ ａ ２ … ｕ ａ ｍ [ ] 和 Ｕｂ ＝ ｕ ｂ １ ｕ ｂ ２ … ｕ ｂ ｍ [ ] ，则利用 夹角公式来计算由特征矩阵 Ｕａ 和 Ｕｂ 中向量所形成 的坐标系中前 ｋ 个坐标轴之间的相似性，即 Ｓｉｍ(ｉ，ｊ) ＝ 〈ｕ ａ ｉ ，ｕ ｂ ｊ 〉 ＝｜ ｃｏｓ θｉｊ ｜ （４） 由于 ｃｏｓ θｉｊ ∈ [０，１] ，故任意 ２ 条坐标轴之间的相 似性 Ｓｉｍ(ｉ，ｊ) 可以转化为相应的距离度量公式，即 ｄ(ｉ，ｊ) ＝ １ － Ｓｉｍ(ｉ，ｊ) ＝ １ －｜ ｃｏｓ θｉｊ ｜ （５） 通过夹角公式计算 ２ 个多元时间序列对应前 ｋ 个特 征向量中任意 ２ 个向量之间的夹角距离矩阵为 Ｄｋ×ｋ ＝ ｄ（１，１） ｄ（１，２） … ｄ（１，ｋ） ｄ（２，１） ｄ（２，２） … ｄ（２，ｋ） ︙ ︙ ︙ ︙ ｄ（ｋ，１） ｄ（ｋ，２） … ｄ（ｋ，ｋ） é ë ê ê ê ê ê ù û ú ú ú ú ú 最小距离度量方法就是基于夹角距离矩阵 Ｄ ， 根据传统 Ｅｒｏｓ 思想找到一组最优匹配，使得该匹配 具有最小的距离。 即通过 ＰＣＡ 降维后，一个多元时 间序列的前 ｋ 个特征向量能够与另一个多元时间序 列的前 ｋ 个特征向量对应比较，并取得最小距离度 量。 因此，该思路可以归纳为一个线性规划问题： ＭＥｒｏｓ(Ａ，Ｂ，ｋ) ＝ ｍｉｎ ∑ ｋ ｉ ＝ １ ∑ ｋ ｊ ＝ １ ｃｉｊｄ(ｉ，ｊ) ｓ．ｔ． ∑ ｋ ｉ ＝ １ ｃｉｊ ＝ １ ，∑ ｋ ｊ ＝ １ ｃｉｊ ＝ １ ì î í ï ïï ï ï （６） 式中： ｃｉｊ { } ｋ×ｋ 是一个二元矩阵，且当 ｃｉｊ ＝ １ 时，表示 夹角距离矩阵 Ｄ 中元素 ｄ(ｉ，ｊ) 对最小距离度量具 有贡献值。 上述线性规划问题实质是一个线性任务分配问 题，即 ｋ 个人分配 ｋ 项任务，一个人只能分配一项任 务，一项任务只能分配给一个人。 为此，选取匈牙利 算法［１５］来解决该线性任务分配问题，该算法是用来 解决二分图最小匹配问题的经典算法。 对于多元时 间序列的主成分之间的最小夹角距离可以从矩阵 Ｄ 出发，把该矩阵的各行和各列分别视为线性任务分 配问题中的人员和任务，即如何从距离矩阵 Ｄ 中把 第 ｊ 列的任务分配给第 ｉ 行的对象，使得最终每个人 完成一项任务，且所有人员完成所有任务后花费的 代价要求最小。 由于多元时间序列经过主成分分析方法进行变 换后，不同多元时间序列的特征向量可以构成不同 的坐标系，不同坐标系的维表示的意义各不相同。 若简单按照各特征值大小顺序来构建坐标系，并且 比较对应坐标系之间的夹角来描述多元时间序列特 征的差异性，将显得不合理。 针对此问题，利用匹配 不同时间序列的特征向量构建的坐标系之间的最小 距离，便可以使得 ２ 个坐标系中最相似的维被相互 比较，进而更为灵活有效地对多元时间序列的特征 进行距离度量。 综上所述，基于特征矩阵的多元时间序列最小 距离度量算法如下。 算法：最小距离度量 ｄｍｉｎ ＝ ＭＥｒｏｓ(Ａ，Ｂ，ｋ) 。 输入：多元时间序列 Ａ 与 Ｂ ，降维后的维度 ｋ 。 输出：最小距离度量 ｄｍｉｎ 。 步骤： １）对多元时间序列 Ａ 与 Ｂ 计算协方差矩阵，即 ＳＡ ＝ Ｅ［（Ａ － Ｅ［Ａ］） （Ａ － Ｅ［Ａ］） Ｔ ］ 和 ＳＢ ＝ Ｅ［（Ｂ － Ｅ［Ｂ］） （Ｂ － Ｅ［Ｂ］） Ｔ ］ ； ２）利用奇异值分解方法对协方差矩阵进行特 征分解，使得 ＳＡ ＝ ＵＡΣ ＡＵ Ｔ Ａ 和 ＳＢ ＝ ＵＢΣ ＢＵ Ｔ Ｂ ，其中 ＵＡ 和 ＵＢ 分别为 ２ 个协方差矩阵的特征矩阵，且向 量按特征值大小排列； ３）分别在 ＵＡ 和 ＵＢ 中选取前 ｋ 个特征向量作 为新坐标系的坐标轴，根据距离度量式（５），建立夹 角距离矩阵 Ｄ ； ·４４４· 智 能 系 统 学 报 第 １０ 卷
第3期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 445· 4)利用匈牙利算法对夹角距离矩阵进行最小 误地归为一类。然而，本文提出的距离度量方法 距离计算，即da=munkres(D),其中，munkres为 MEros能够很好地将2类数据成功归类，如图1(b) 匈牙利算法求解二分图最小匹配问题的函数。 所示，前后10个数据对象分别被归成一类，符合实 基于特征矩阵的多元时间序列最小距离度量方 际分类情况。因此，可以说MEos具有较好的距离 法能够有效地描述原始多元时间序列之间的相似 度量质量，能够提高多元时间序列数据的聚类性能。 性。同时，与传统Eos方法相比，最小距离度量方 法MEros不受其他多元时间序列经PCA转化后特 征值的影响。通过比较特征向量所形成的坐标系之 间的差异性来区分不同多元时间序列的特征，不仅 能够有效地对多元时间序列进行特征描述，而且还 能从时间维度和变量维度2个方向进行数据降维， 即原来n×m维降至k×k维.通常情况下，k<n和 k<m。 需要说明的是，最小距离度量方法利用匈牙利 0 0.5 0 0.5 0 0.5 算法对夹角距离矩阵进行最优化匹配求解，最坏情 (a)Eros (b)MEros (c)Euclidean 况下，其消耗的时间复杂度为O(k3)。然而，在大 图13种度量方法对等长多元时间序列的聚类结果 多数情况下，经过PCA转化后，较小的k值所对应 Fig.I The clustering results of the tree measurements for 的主成分也能保留原始多元时间序列的大部分信 multivariate time series with different lengths 息，使得最小距离度量能够快速有效地对多元时间 3.2数据分类 序列进行相似性度量。 聚类分析实验采用等长多元时间序列EEG数 据集和另外一个不等长多元时间序列EEGEye数据 3 数值实验 集[16]，它们都是具有2类标签的多元时间序列数据 为了有效地评估MEos方法的性能，利用多元 集。同时，EEGEye数据集中包含24个长度不等的 时间序列聚类和分类算法进行距离度量质量检测， 多元时间序列，其长度范围21~2051，具有14个观 同时比较了几种方法的计算时间效率。 测属性。 3.1数据聚类 利用最近邻分类方法比较MEros、Eros和欧氏 层次聚类方法能够较好地从视觉角度表达聚类 距离Euclidean或动态时间弯曲DTW等方法在多元 结果的层次关系，并且能够很好地评估数据距离度 时间序列数据集的度量效果，通过分类错误率来评 量方法的准确性。本次实验能过层次聚类算法和3 价距离度量方法的质量。让多元时间序列数据集中 种距离度量方法(MEros、Eros和欧氏距离Euclide- 的每个序列都与其他序列进行距离度量，查找与之 an)来对等长多元时间序列进行聚类分析，进而比 最相似的序列作为检测序列，并通过比较检测序列 较3种距离度量方法的度量质量 与被检测序列之间的标签来判断分类结果的正确 实验数据为EEG多元时间序列数据集，它具有 性，最终通过平均分类错误率来衡量距离度量方法 2类标签且包含了20个多元时间序列，每个时间序 在分类实验中的应用性能。 列具有相同的观测时间，即时间序列长度相同且为 另外，选取不同的降维维度来比较距离度量方 256,是对64个部位进行观测的序列数据，可视为 法在分类实验中的性能，即通过比较不同维度k的 256×64的数据矩阵。同时，前后10个多元时间序 坐标系来考察距离度量的质量。对等长时间序列数 列分别为同一类数据，即序号为1,2,3,4,5,6,7,8， 据集EEG和不等长时间序列数据集EEGEye的分 9,10}为同一类，其余{11,12,13,14,15,16,17,18， 类结果如图2和3所示。从分类实验结果可以发 19,20}为另外一类。在本次实验中，选取k=3为主 现，与传统方法Eros相比，新方法MEros具有较好 成分分析降维后的维度，并将相应的特征数据用于 的分类结果，说明它具有更好地距离度量质量，能够 考查MEros和Eros的度量性能，其聚类分析结果如 提高多元时间序列数据挖掘的挖掘效果。另外，由 图1所示。从层次聚类结果视图中分析易知，距离 于Euclidean和DTW分别善于对等长和不等长时间 度量方法Eros和欧氏距离Euclidean对等长多元时 序列的相似性度量，故在实验中比较它们与新方法 间序列数据的聚类出现明显的错误归类，如图1(a) 的分类效果。在图2分类结果中发现，MEos具有 和1(c)中粗连线所示，它们将不同类的数据对象错 最好的分类结果，而在图3分类结果中可以知道，在
４）利用匈牙利算法对夹角距离矩阵进行最小 距离计算，即 ｄｍｉｎ ＝ ｍｕｎｋｒｅｓ （Ｄ） ，其中，ｍｕｎｋｒｅｓ 为 匈牙利算法求解二分图最小匹配问题的函数。 基于特征矩阵的多元时间序列最小距离度量方 法能够有效地描述原始多元时间序列之间的相似 性。 同时，与传统 Ｅｒｏｓ 方法相比，最小距离度量方 法 ＭＥｒｏｓ 不受其他多元时间序列经 ＰＣＡ 转化后特 征值的影响。 通过比较特征向量所形成的坐标系之 间的差异性来区分不同多元时间序列的特征，不仅 能够有效地对多元时间序列进行特征描述，而且还 能从时间维度和变量维度 ２ 个方向进行数据降维， 即原来 ｎ × ｍ 维降至 ｋ × ｋ 维．通常情况下， ｋ ＜ ｎ 和 ｋ ＜ ｍ 。 需要说明的是，最小距离度量方法利用匈牙利 算法对夹角距离矩阵进行最优化匹配求解，最坏情 况下，其消耗的时间复杂度为 Ｏ（ｋ ３ ） 。 然而，在大 多数情况下，经过 ＰＣＡ 转化后，较小的 ｋ 值所对应 的主成分也能保留原始多元时间序列的大部分信 息，使得最小距离度量能够快速有效地对多元时间 序列进行相似性度量。 ３ 数值实验 为了有效地评估 ＭＥｒｏｓ 方法的性能，利用多元 时间序列聚类和分类算法进行距离度量质量检测， 同时比较了几种方法的计算时间效率。 ３．１ 数据聚类 层次聚类方法能够较好地从视觉角度表达聚类 结果的层次关系，并且能够很好地评估数据距离度 量方法的准确性。 本次实验能过层次聚类算法和 ３ 种距离度量方法（ＭＥｒｏｓ、Ｅｒｏｓ 和欧氏距离 Ｅｕｃｌｉｄｅ⁃ ａｎ）来对等长多元时间序列进行聚类分析，进而比 较 ３ 种距离度量方法的度量质量． 实验数据为 ＥＥＧ 多元时间序列数据集，它具有 ２ 类标签且包含了 ２０ 个多元时间序列，每个时间序 列具有相同的观测时间，即时间序列长度相同且为 ２５６，是对 ６４ 个部位进行观测的序列数据，可视为 ２５６ × ６４ 的数据矩阵。 同时，前后 １０ 个多元时间序 列分别为同一类数据，即序号为｛１，２，３，４，５，６，７，８， ９，１０｝为同一类，其余｛１１，１２，１３，１４，１５，１６，１７，１８， １９，２０｝为另外一类。 在本次实验中，选取 ｋ ＝ ３ 为主 成分分析降维后的维度，并将相应的特征数据用于 考查 ＭＥｒｏｓ 和 Ｅｒｏｓ 的度量性能，其聚类分析结果如 图 １ 所示。 从层次聚类结果视图中分析易知，距离 度量方法 Ｅｒｏｓ 和欧氏距离 Ｅｕｃｌｉｄｅａｎ 对等长多元时 间序列数据的聚类出现明显的错误归类，如图 １（ａ） 和 １（ｃ）中粗连线所示，它们将不同类的数据对象错 误地归为一类。 然而，本文提出的距离度量方法 ＭＥｒｏｓ 能够很好地将 ２ 类数据成功归类，如图 １（ｂ） 所示，前后 １０ 个数据对象分别被归成一类，符合实 际分类情况。 因此，可以说 ＭＥｒｏｓ 具有较好的距离 度量质量，能够提高多元时间序列数据的聚类性能。 图 １ ３ 种度量方法对等长多元时间序列的聚类结果 Ｆｉｇ．１ Ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｔｒｅｅ ｍｅａｓｕｒｅｍｅｎｔｓ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｌｅｎｇｔｈｓ ３．２ 数据分类 聚类分析实验采用等长多元时间序列 ＥＥＧ 数 据集和另外一个不等长多元时间序列 ＥＥＧＥｙｅ 数据 集［１６］ ，它们都是具有 ２ 类标签的多元时间序列数据 集。 同时，ＥＥＧＥｙｅ 数据集中包含 ２４ 个长度不等的 多元时间序列，其长度范围 ２１ ～ ２ ０５１，具有 １４ 个观 测属性。 利用最近邻分类方法比较 ＭＥｒｏｓ、Ｅｒｏｓ 和欧氏 距离 Ｅｕｃｌｉｄｅａｎ 或动态时间弯曲 ＤＴＷ 等方法在多元 时间序列数据集的度量效果，通过分类错误率来评 价距离度量方法的质量。 让多元时间序列数据集中 的每个序列都与其他序列进行距离度量，查找与之 最相似的序列作为检测序列，并通过比较检测序列 与被检测序列之间的标签来判断分类结果的正确 性，最终通过平均分类错误率来衡量距离度量方法 在分类实验中的应用性能。 另外，选取不同的降维维度来比较距离度量方 法在分类实验中的性能，即通过比较不同维度 ｋ 的 坐标系来考察距离度量的质量。 对等长时间序列数 据集 ＥＥＧ 和不等长时间序列数据集 ＥＥＧＥｙｅ 的分 类结果如图 ２ 和 ３ 所示。 从分类实验结果可以发 现，与传统方法 Ｅｒｏｓ 相比，新方法 ＭＥｒｏｓ 具有较好 的分类结果，说明它具有更好地距离度量质量，能够 提高多元时间序列数据挖掘的挖掘效果。 另外，由 于 Ｅｕｃｌｉｄｅａｎ 和 ＤＴＷ 分别善于对等长和不等长时间 序列的相似性度量，故在实验中比较它们与新方法 的分类效果。 在图 ２ 分类结果中发现，ＭＥｒｏｓ 具有 最好的分类结果，而在图 ３ 分类结果中可以知道，在 第 ３ 期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 ·４４５·
·446 智能系统学报 第10卷 对不等时间序列相似性比较时，DTW的分类质量优 的分类实验结果，可以说明新方法MEOs是一种较为 于MEros,其原因是EEGEye数据集的形态特征区 快速且更为有效的多元时间序列相似性度量方法。 分较为明显，利用DTW通过最优化路径选择并产 4*103 生相应的距离值，它能够使其取得较好的分类效果， 日一Eros 3 e—MEros 但从时间效率比较实验中易知，DTW时间消耗不适 Euclidean 合于大量高维时间序列的数据挖掘。 2 0.5 日—Eros 0.4 -eMEros t一Euclidean 3 5 7 91113 0.2 图43种方法对EEG数据集的时间代价 尔0.1 Fig.4 The time cost of the three methods for EEG B 9 9 9 5 > 9 1113 10 2.0,×103 +一DTW -B-Eros 图23种方法对EEG数据集的分类结果 8 1.5 -e-MEros 0 Fig.2 The classification results of three methods for EEG 之1.0 0. 日 日 日 日 Eros 日0.5冲 0.4 MEros 0电日日日日日日 DTW 1357913 135791113 0.3 彩 (a)DTW (b)Eros和MEros 0.24 图53种方法对EEGEye数据集的时间代价 0.10 Fig.5 The time cost of the three methods for EEGEye 5 791113 k 图33种方法对EEGEye数据集的分类结果 4 结束语 Fig.3 The classification results of three methods for EEGEye 文章提出了一种基于特征矩阵的多元时间序列 3.3效率比较 最小距离度量方法。该方法是基于主成分分析特征 为了更好地比较距离度量方法之间的性能，除 表示的距离度量方法，首先利用主成分分析对多元 了评价它们在多元时间序列数据挖掘中的挖掘质 时间序列进行特征分解，根据特征值的大小选择相 量，还需要评估其实际实验中的运行效率。根据上 应的特征向量构建反映多元时间序列数据特征的坐 面实验步骤，记录每个检测序列与被检测序列之间 标系，并且通过比较坐标系之间的差异性来度量多 相互匹配的CPU计算时间，将平均消耗时间作为最 元时间序列之间的距离。该方法不依赖于特征值 终的评估时间代价。另外，根据不同的k值，观测距 (方差)的大小来选择夹角向量，而是通过度量正交 离度量方法的时间消耗情况。 坐标系之间的相似性来反映原始多元时间序列的差 3种距离度量方法对2组时间序列数据集的 异，进而克服了传统Eos方法的局限性。同时，通 CPU时间代价如图4和5所示。容易发现，与E- 过匈牙利算法，把线性规划问题转化为求解二分图 clidean和Eros相比，新方法MEros需要消耗较多的 最小匹配问题，其计算原理简单明了。最后，数值实 计算时间。然而，从实验结果中的纵轴数据量大小 验结果表明，新方法MEos是一种快速有效的多元 易知，这3种方法仅需要10-3秒级的时间。然而， 时间序列距离度量方法。 对于不等长时间序列度量来说，DTW需要平均消耗 与传统Eros相比，新方法MEros具有较高的度 7.2s左右的时间。相比之下，适合计算不等长时间 量质量，但其时间效率略低。MEos算法主要包括 序列之间距离的其他2种方法(Eros和MEros)的计 了多元时间序列的协方差矩阵、特征矩阵、距离矩阵 算效率明显较好。另外，如图4和5(b)所示，MEos 和匈牙利算法等计算过程，其中前3个矩阵在传统 的计算时间随着降维后维度k值的增长而变大，其 Eros算法中都需要被运算，因此MEros的额外计算 原因是MEos算法过程中的匈牙利方法计算速度依 时间代价主要是由匈牙利算法求解二分图最小匹配 赖于k值，即O(k3)。k值越大，其计算时间代价越 问题引起的。另外，匈牙利算法对距离矩阵的求解 高，但其运算速度保持在10-3秒级。因此，结合前面 效率依赖于多元时间序列的降维后维度k,其最坏
对不等时间序列相似性比较时，ＤＴＷ 的分类质量优 于 ＭＥｒｏｓ，其原因是 ＥＥＧＥｙｅ 数据集的形态特征区 分较为明显，利用 ＤＴＷ 通过最优化路径选择并产 生相应的距离值，它能够使其取得较好的分类效果， 但从时间效率比较实验中易知，ＤＴＷ 时间消耗不适 合于大量高维时间序列的数据挖掘。 图 ２ ３ 种方法对 ＥＥＧ 数据集的分类结果 Ｆｉｇ．２ Ｔｈｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ｔｈｒｅｅ ｍｅｔｈｏｄｓ ｆｏｒ ＥＥＧ 图 ３ ３ 种方法对 ＥＥＧＥｙｅ 数据集的分类结果 Ｆｉｇ．３ Ｔｈｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｆ ｔｈｒｅｅ ｍｅｔｈｏｄｓ ｆｏｒ ＥＥＧＥｙｅ ３．３ 效率比较 为了更好地比较距离度量方法之间的性能，除 了评价它们在多元时间序列数据挖掘中的挖掘质 量，还需要评估其实际实验中的运行效率。 根据上 面实验步骤，记录每个检测序列与被检测序列之间 相互匹配的 ＣＰＵ 计算时间，将平均消耗时间作为最 终的评估时间代价。 另外，根据不同的 ｋ 值，观测距 离度量方法的时间消耗情况。 ３ 种距离度量方法对 ２ 组时间序列数据集的 ＣＰＵ 时间代价如图 ４ 和 ５ 所示。 容易发现，与 Ｅｕ⁃ ｃｌｉｄｅａｎ 和 Ｅｒｏｓ 相比，新方法 ＭＥｒｏｓ 需要消耗较多的 计算时间。 然而，从实验结果中的纵轴数据量大小 易知，这 ３ 种方法仅需要 １０ －３ 秒级的时间。 然而， 对于不等长时间序列度量来说，ＤＴＷ 需要平均消耗 ７．２ ｓ 左右的时间。 相比之下，适合计算不等长时间 序列之间距离的其他 ２ 种方法（Ｅｒｏｓ 和 ＭＥｒｏｓ）的计 算效率明显较好。 另外，如图 ４ 和 ５（ｂ）所示，ＭＥｒｏｓ 的计算时间随着降维后维度 ｋ 值的增长而变大，其 原因是 ＭＥｒｏｓ 算法过程中的匈牙利方法计算速度依 赖于 ｋ 值，即 Ｏ（ｋ ３ ） 。 ｋ 值越大，其计算时间代价越 高，但其运算速度保持在 １０ －３ 秒级。 因此，结合前面 的分类实验结果，可以说明新方法 ＭＥｒｏｓ 是一种较为 快速且更为有效的多元时间序列相似性度量方法。 图 ４ ３ 种方法对 ＥＥＧ 数据集的时间代价 Ｆｉｇ．４ Ｔｈｅ ｔｉｍｅ ｃｏｓｔ ｏｆ ｔｈｅ ｔｈｒｅｅ ｍｅｔｈｏｄｓ ｆｏｒ ＥＥＧ 图 ５ ３ 种方法对 ＥＥＧＥｙｅ 数据集的时间代价 Ｆｉｇ．５ Ｔｈｅ ｔｉｍｅ ｃｏｓｔ ｏｆ ｔｈｅ ｔｈｒｅｅ ｍｅｔｈｏｄｓ ｆｏｒ ＥＥＧＥｙｅ ４ 结束语 文章提出了一种基于特征矩阵的多元时间序列 最小距离度量方法。 该方法是基于主成分分析特征 表示的距离度量方法，首先利用主成分分析对多元 时间序列进行特征分解，根据特征值的大小选择相 应的特征向量构建反映多元时间序列数据特征的坐 标系，并且通过比较坐标系之间的差异性来度量多 元时间序列之间的距离。 该方法不依赖于特征值 （方差）的大小来选择夹角向量，而是通过度量正交 坐标系之间的相似性来反映原始多元时间序列的差 异，进而克服了传统 Ｅｒｏｓ 方法的局限性。 同时，通 过匈牙利算法，把线性规划问题转化为求解二分图 最小匹配问题，其计算原理简单明了。 最后，数值实 验结果表明，新方法 ＭＥｒｏｓ 是一种快速有效的多元 时间序列距离度量方法。 与传统 Ｅｒｏｓ 相比，新方法 ＭＥｒｏｓ 具有较高的度 量质量，但其时间效率略低。 ＭＥｏｒｓ 算法主要包括 了多元时间序列的协方差矩阵、特征矩阵、距离矩阵 和匈牙利算法等计算过程，其中前 ３ 个矩阵在传统 Ｅｒｏｓ 算法中都需要被运算，因此 ＭＥｒｏｓ 的额外计算 时间代价主要是由匈牙利算法求解二分图最小匹配 问题引起的。 另外，匈牙利算法对距离矩阵的求解 效率依赖于多元时间序列的降维后维度 ｋ，其最坏 ·４４６· 智 能 系 统 学 报 第 １０ 卷
第3期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 447· 情况下的计算时间效率为O(k3)。因此，如何提升 sion reduction method for multivariate time series based on 匈牙利算法的计算时间或研究一种能够快速求解式 common principal component [J].Control and Decision, (6)的算法是将来有待研究的问题。 2013,28(4):531-536. [10]李正欣，张凤鸣，张晓丰，等.多元时间序列特征降维 参考文献： 方法研究[J].小型微型计算机系统，2013,34(2)： 338-346. [1]ESLING P,AGON C.Time-series data mining[J].ACM LI Zhengxin,ZHANG Fengming,ZHANG Xiaofeng.Re- Computing Surverys,2012,45(1):11-12. search on feature dimension reduction method for multivari- [2]李海林，杨丽彬.时间序列数据降维及特征表示新方法 ate time series[J].Journal of Chinese Computer Systems, [J].控制与决策，2013,28(11)：1718-1722 LI Hailin,YANG Libin.Novel method of dimensionality re- 2013,34(2):338-346. duction and feature representation for time series[J].Con- [11]LI Hailin.Asynchronism-based principal component analy- sis for time series data mining[J].Expert Systems with trol and Decision,2013,28(11):1718-1722. Applications,2014,41(6):2842-2850. [3]YANG K,SHAHABI C.An efficient nearest neighbor [12]YANKOV D,KEOGH E,REBBAPRAGADA U.Disk a- search for multivariate time series[J].Information and ware discord discovery:finding unusual time series in ter- Computation,2007,205(1):65-98. abyte sized datasetsJ.Knowledge and Information Sys- [4]韩敏，李德才.基于EOF-SVD模型的多元时间序列相关 tems,2007,17(2):381-390. 性研究及预测[J].系统仿真学报，2008,20(7)：1669- [13]CHEN Yanping,HU Bing,KEOGH E,et al.DTW-D: 1672 time series semi-supervised learning from a single example HAN Min,LI Decai.Multiple time series correlation extrac- [C]//Proceedings of the 19th ACM SIGKDD International tion and prediction based on EOF-SVD model[J].Journal of Conference on Knowledge Discovery and Data Mining.Chi- System Simulation,2008,20(7):1669-1672. cag0,USA,2013:383-391. [5]WENG Xiaoqing,SHEN Junyi.Classification of multivariate [14]YANG K,SHAHABI C.A PCA-based similarity measure time series using two dimensional singular value decomposi- tion[J].Knowledge-Based Systems.2008,21(7):535- for multivariate time series[C]//Proceedings of the 2nd ACM International Workshop on Multimedia Databases. 539. Washington,DC,USA,2004:65-74. 「6]吴虎胜，张风鸣，钟斌.基于二维奇异值分解的多元时 [15]何坚勇.运筹学基础[M].北京：清华大学出版社 间序列相似匹配方法[J].电子与信息学报，2014,36 2006:217-220. (4):847-854. [16]BACHE K,LICHMAN M.UCI machine learning repository WU Husheng,ZHANG Fengming,ZHONG Bin.Similar [EB/0L].(2013-12-21)[2014-04-28].http:/archive. pattern matching method for multivariate time series based ics.uci.edu/ml. on two-dimensional singular value decomposition[J].Jour- 作者简介： nal of Electronics Information Technology,2014,36(4): 李海林，男，1982年生，副教授，博 847-854. 士，主要研究方向为数据挖掘与决策支 [7]樊继聪，王友清，秦泗钊.联合指标独立成分分析在多 持，主持国家自然科学基金和省部级青 变量过程故障诊断中的应用[J].自动化学报，2013,39 年基金各1项，发表学术论文30余篇， (5):494-501. 其中被SCI检索7篇、EI检索10余篇。 FAN Jicong,WANG Youqing,QIN Sizhao.Combined indi- ces for ICA and their applications to multivariate process fault diagnosis[J].Acta Automatica Sinica,2013,39(5): 郭韧，女，1975年生，讲师，博士研 494-501. 究生，主要研究方向为知识管理与数据 [8]梁胜杰，张志华，崔立林，等.基于主成分分析与核独 挖掘，发表学术论文近20篇，其中被 立成分分析的降维方法[J].系统工程与电子技术， CSSCI检索9篇。 2011,33(9):2144-2148. LIANG Shengjie,ZHANG Zhihua,CUI Lilin,et al.Dimen- sionality reduction method based on PCA and KICA[J]. Systems Engineering and Electronics,2011,33(9):2144- 万校基，男，1982年生，讲师，博士， 2148. 主要研究方向为数据挖掘与决策支持， [9]李正欣，郭建胜，惠晓滨，等.基于共同主成分的多元 发表学术论文10余篇。 时间序列降维方法[J刀].控制与决策，2013,28(4)：531- 536. LI Zhengxin,GUO Jiansheng,HUI Xiaobin,et al.Dimen-
情况下的计算时间效率为 Ｏ（ｋ ３ ） 。 因此，如何提升 匈牙利算法的计算时间或研究一种能够快速求解式 （６）的算法是将来有待研究的问题。 参考文献： ［１］ＥＳＬＩＮＧ Ｐ， ＡＧＯＮ Ｃ． Ｔｉｍｅ⁃ｓｅｒｉｅｓ ｄａｔａ ｍｉｎｉｎｇ ［ Ｊ］． ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｒｙｓ， ２０１２， ４５（１）： １１⁃１２． ［２］李海林， 杨丽彬． 时间序列数据降维及特征表示新方法 ［Ｊ］． 控制与决策， ２０１３， ２８（１１）：１７１８⁃１７２２． ＬＩ Ｈａｉｌｉｎ， ＹＡＮＧ Ｌｉｂｉｎ． Ｎｏｖｅｌ ｍｅｔｈｏｄ ｏｆ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅ⁃ ｄｕｃｔｉｏｎ ａｎｄ ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ ｔｉｍｅ ｓｅｒｉｅｓ［ Ｊ］． Ｃｏｎ⁃ ｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２０１３， ２８（１１）：１７１８⁃１７２２． ［３］ ＹＡＮＧ Ｋ， ＳＨＡＨＡＢＩ Ｃ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ［ Ｊ ］． Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２００７， ２０５（１）： ６５⁃９８． ［４］韩敏， 李德才． 基于 ＥＯＦ⁃ＳＶＤ 模型的多元时间序列相关 性研究及预测［Ｊ］． 系统仿真学报， ２００８， ２０（７）： １６６９⁃ １６７２ ＨＡＮ Ｍｉｎ， ＬＩ Ｄｅｃａｉ． Ｍｕｌｔｉｐｌｅ ｔｉｍｅ ｓｅｒｉｅｓ ｃｏｒｒｅｌａｔｉｏｎ ｅｘｔｒａｃ⁃ ｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ ｂａｓｅｄ ｏｎ ＥＯＦ⁃ＳＶＤ ｍｏｄｅｌ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍ Ｓｉｍｕｌａｔｉｏｎ， ２００８， ２０（７）： １６６９⁃１６７２． ［５］ＷＥＮＧ Ｘｉａｏｑｉｎｇ， ＳＨＥＮ Ｊｕｎｙｉ． Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｕｓｉｎｇ ｔｗｏ ｄｉｍｅｎｓｉｏｎａｌ ｓｉｎｇｕｌａｒ ｖａｌｕｅ ｄｅｃｏｍｐｏｓｉ⁃ ｔｉｏｎ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃Ｂａｓｅｄ Ｓｙｓｔｅｍｓ． ２００８， ２１ （ ７）： ５３５⁃ ５３９． ［６］吴虎胜， 张凤鸣， 钟斌． 基于二维奇异值分解的多元时 间序列相似匹配方法［ Ｊ］． 电子与信息学报， ２０１４， ３６ （４）： ８４７⁃８５４． ＷＵ Ｈｕｓｈｅｎｇ， ＺＨＡＮＧ Ｆｅｎｇｍｉｎｇ， ＺＨＯＮＧ Ｂｉｎ． Ｓｉｍｉｌａｒ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ｔｗｏ⁃ｄｉｍｅｎｓｉｏｎａｌ ｓｉｎｇｕｌａｒ ｖａｌｕｅ ｄｅｃｏｍｐｏｓｉｔｉｏｎ［ Ｊ］． Ｊｏｕｒ⁃ ｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ＆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， ２０１４， ３６（４）： ８４７⁃８５４． ［７］樊继聪， 王友清， 秦泗钊． 联合指标独立成分分析在多 变量过程故障诊断中的应用［Ｊ］． 自动化学报， ２０１３， ３９ （５）： ４９４⁃５０１． ＦＡＮ Ｊｉｃｏｎｇ， ＷＡＮＧ Ｙｏｕｑｉｎｇ， ＱＩＮ Ｓｉｚｈａｏ． Ｃｏｍｂｉｎｅｄ ｉｎｄｉ⁃ ｃｅｓ ｆｏｒ ＩＣＡ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ｍｕｌｔｉｖａｒｉａｔｅ ｐｒｏｃｅｓｓ ｆａｕｌｔ ｄｉａｇｎｏｓｉｓ［Ｊ］． Ａｃｔａ Ａｕｔｏｍａｔｉｃａ Ｓｉｎｉｃａ， ２０１３， ３９（５）： ４９４⁃５０１． ［８］梁胜杰， 张志华， 崔立林， 等． 基于主成分分析与核独 立成分分析的降维方法［ Ｊ］． 系统工程与电子技术， ２０１１， ３３（９）： ２１４４⁃２１４８． ＬＩＡＮＧ Ｓｈｅｎｇｊｉｅ， ＺＨＡＮＧ Ｚｈｉｈｕａ， ＣＵＩ Ｌｉｌｉｎ， ｅｔ ａｌ． Ｄｉｍｅｎ⁃ ｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ＰＣＡ ａｎｄ ＫＩＣＡ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ， ２０１１， ３３（９）： ２１４４⁃ ２１４８． ［９］李正欣， 郭建胜， 惠晓滨， 等． 基于共同主成分的多元 时间序列降维方法［Ｊ］． 控制与决策， ２０１３， ２８（４）： ５３１⁃ ５３６． ＬＩ Ｚｈｅｎｇｘｉｎ， ＧＵＯ Ｊｉａｎｓｈｅｎｇ， ＨＵＩ Ｘｉａｏｂｉｎ， ｅｔ ａｌ． Ｄｉｍｅｎ⁃ ｓｉｏｎ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ｃｏｍｍｏｎ ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ［ Ｊ ］． Ｃｏｎｔｒｏｌ ａｎｄ Ｄｅｃｉｓｉｏｎ， ２０１３， ２８（４）： ５３１⁃５３６． ［１０］李正欣， 张凤鸣， 张晓丰， 等． 多元时间序列特征降维 方法研究［ Ｊ］． 小型微型计算机系统， ２０１３， ３４ （ ２）： ３３８⁃３４６． ＬＩ Ｚｈｅｎｇｘｉｎ， ＺＨＡＮＧ Ｆｅｎｇｍｉｎｇ， ＺＨＡＮＧ Ｘｉａｏｆｅｎｇ． Ｒｅ⁃ ｓｅａｒｃｈ ｏｎ ｆｅａｔｕｒｅ ｄｉｍｅｎｓｉｏｎ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｍｕｌｔｉｖａｒｉ⁃ ａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ， ２０１３， ３４（２）： ３３８⁃３４６． ［１１］ＬＩ Ｈａｉｌｉｎ． Ａｓｙｎｃｈｒｏｎｉｓｍ⁃ｂａｓｅｄ ｐｒｉｎｃｉｐａｌ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙ⁃ ｓｉｓ ｆｏｒ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ｍｉｎｉｎｇ ［ Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ４１（６）： ２８４２⁃２８５０． ［１２］ ＹＡＮＫＯＶ Ｄ， ＫＥＯＧＨ Ｅ， ＲＥＢＢＡＰＲＡＧＡＤＡ Ｕ． Ｄｉｓｋ ａ⁃ ｗａｒｅ ｄｉｓｃｏｒｄ ｄｉｓｃｏｖｅｒｙ： ｆｉｎｄｉｎｇ ｕｎｕｓｕａｌ ｔｉｍｅ ｓｅｒｉｅｓ ｉｎ ｔｅｒ⁃ ａｂｙｔｅ ｓｉｚｅｄ ｄａｔａｓｅｔｓ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓ⁃ ｔｅｍｓ， ２００７， １７（２）： ３８１⁃３９０． ［１３］ ＣＨＥＮ Ｙａｎｐｉｎｇ， ＨＵ Ｂｉｎｇ， ＫＥＯＧＨ Ｅ， ｅｔ ａｌ． ＤＴＷ⁃Ｄ： ｔｉｍｅ ｓｅｒｉｅｓ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｆｒｏｍ ａ ｓｉｎｇｌｅ ｅｘａｍｐｌｅ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｃｈｉ⁃ ｃａｇｏ， ＵＳＡ， ２０１３： ３８３⁃３９１． ［１４］ＹＡＮＧ Ｋ， ＳＨＡＨＡＢＩ Ｃ． Ａ ＰＣＡ⁃ｂａｓｅｄ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２ｎｄ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｍｕｌｔｉｍｅｄｉａ Ｄａｔａｂａｓｅｓ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２００４： ６５⁃７４． ［１５］何坚勇． 运筹学基础［ Ｍ］． 北京： 清华大学出版社， ２００６： ２１７⁃２２０． ［１６］ＢＡＣＨＥ Ｋ， ＬＩＣＨＭＡＮ Ｍ． ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ ［ＥＢ／ ＯＬ］． （ ２０１３⁃１２⁃２１） ［ ２０１４⁃０４⁃２８］． ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ． ｉｃｓ．ｕｃｉ．ｅｄｕ ／ ｍｌ． 作者简介： 李海林，男，１９８２ 年生，副教授，博 士，主要研究方向为数据挖掘与决策支 持， 主持国家自然科学基金和省部级青 年基金各 １ 项，发表学术论文 ３０ 余篇， 其中被 ＳＣＩ 检索 ７ 篇、ＥＩ 检索 １０ 余篇。 郭韧，女，１９７５ 年生，讲师，博士研 究生，主要研究方向为知识管理与数据 挖掘，发表学术论文近 ２０ 篇，其中被 ＣＳＳＣＩ 检索 ９ 篇。 万校基，男，１９８２ 年生，讲师，博士， 主要研究方向为数据挖掘与决策支持， 发表学术论文 １０ 余篇。 第 ３ 期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 ·４４７·