第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分类结果中可以知道，在４）利用匈牙利算法对夹角距离矩阵进行最小 距离计算，即 ｄｍｉｎ ＝ ｍｕｎｋｒｅｓ （Ｄ） ，其中，ｍｕｎｋｒｅｓ 为 匈牙利算法求解二分图最小匹配问题的函数。 基于特征矩阵的多元时间序列最小距离度量方 法能够有效地描述原始多元时间序列之间的相似 性。 同时，与传统 Ｅｒｏｓ 方法相比，最小距离度量方 法 ＭＥｒｏｓ 不受其他多元时间序列经 ＰＣＡ 转化后特 征值的影响。 通过比较特征向量所形成的坐标系之 间的差异性来区分不同多元时间序列的特征，不仅 能够有效地对多元时间序列进行特征描述，而且还 能从时间维度和变量维度 ２ 个方向进行数据降维， 即原来 ｎ × ｍ 维降至 ｋ × ｋ 维．通常情况下， ｋ ＜ ｎ 和 ｋ ＜ ｍ 。 需要说明的是，最小距离度量方法利用匈牙利 算法对夹角距离矩阵进行最优化匹配求解，最坏情 况下，其消耗的时间复杂度为 Ｏ（ｋ ３ ） 。 然而，在大 多数情况下，经过 ＰＣＡ 转化后，较小的 ｋ 值所对应 的主成分也能保留原始多元时间序列的大部分信 息，使得最小距离度量能够快速有效地对多元时间 序列进行相似性度量。 ３ 数值实验 为了有效地评估 ＭＥｒｏｓ 方法的性能，利用多元 时间序列聚类和分类算法进行距离度量质量检测， 同时比较了几种方法的计算时间效率。 ３．１ 数据聚类 层次聚类方法能够较好地从视觉角度表达聚类 结果的层次关系，并且能够很好地评估数据距离度 量方法的准确性。 本次实验能过层次聚类算法和 ３ 种距离度量方法（ＭＥｒｏｓ、Ｅｒｏｓ 和欧氏距离 Ｅｕｃｌｉｄｅ⁃ ａｎ）来对等长多元时间序列进行聚类分析，进而比 较 ３ 种距离度量方法的度量质量． 实验数据为 ＥＥＧ 多元时间序列数据集，它具有 ２ 类标签且包含了 ２０ 个多元时间序列，每个时间序 列具有相同的观测时间，即时间序列长度相同且为 ２５６，是对 ６４ 个部位进行观测的序列数据，可视为 ２５６ × ６４ 的数据矩阵。 同时，前后 １０ 个多元时间序 列分别为同一类数据，即序号为｛１，２，３，４，５，６，７，８， ９，１０｝为同一类，其余｛１１，１２，１３，１４，１５，１６，１７，１８， １９，２０｝为另外一类。 在本次实验中，选取 ｋ ＝ ３ 为主 成分分析降维后的维度，并将相应的特征数据用于 考查 ＭＥｒｏｓ 和 Ｅｒｏｓ 的度量性能，其聚类分析结果如 图 １ 所示。 从层次聚类结果视图中分析易知，距离 度量方法 Ｅｒｏｓ 和欧氏距离 Ｅｕｃｌｉｄｅａｎ 对等长多元时 间序列数据的聚类出现明显的错误归类，如图 １（ａ） 和 １（ｃ）中粗连线所示，它们将不同类的数据对象错 误地归为一类。 然而，本文提出的距离度量方法 ＭＥｒｏｓ 能够很好地将 ２ 类数据成功归类，如图 １（ｂ） 所示，前后 １０ 个数据对象分别被归成一类，符合实 际分类情况。 因此，可以说 ＭＥｒｏｓ 具有较好的距离 度量质量，能够提高多元时间序列数据的聚类性能。 图 １ ３ 种度量方法对等长多元时间序列的聚类结果 Ｆｉｇ．１ Ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ｔｈｅ ｔｒｅｅ ｍｅａｓｕｒｅｍｅｎｔｓ ｆｏｒ ｍｕｌｔｉｖａｒｉａｔｅ ｔｉｍｅ ｓｅｒｉｅｓ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｌｅｎｇｔｈｓ ３．２ 数据分类 聚类分析实验采用等长多元时间序列 ＥＥＧ 数 据集和另外一个不等长多元时间序列 ＥＥＧＥｙｅ 数据 集［１６］ ，它们都是具有 ２ 类标签的多元时间序列数据 集。 同时，ＥＥＧＥｙｅ 数据集中包含 ２４ 个长度不等的 多元时间序列，其长度范围 ２１ ～ ２ ０５１，具有 １４ 个观 测属性。 利用最近邻分类方法比较 ＭＥｒｏｓ、Ｅｒｏｓ 和欧氏 距离 Ｅｕｃｌｉｄｅａｎ 或动态时间弯曲 ＤＴＷ 等方法在多元 时间序列数据集的度量效果，通过分类错误率来评 价距离度量方法的质量。 让多元时间序列数据集中 的每个序列都与其他序列进行距离度量，查找与之 最相似的序列作为检测序列，并通过比较检测序列 与被检测序列之间的标签来判断分类结果的正确 性，最终通过平均分类错误率来衡量距离度量方法 在分类实验中的应用性能。 另外，选取不同的降维维度来比较距离度量方 法在分类实验中的性能，即通过比较不同维度 ｋ 的 坐标系来考察距离度量的质量。 对等长时间序列数 据集 ＥＥＧ 和不等长时间序列数据集 ＥＥＧＥｙｅ 的分 类结果如图 ２ 和 ３ 所示。 从分类实验结果可以发 现，与传统方法 Ｅｒｏｓ 相比，新方法 ＭＥｒｏｓ 具有较好 的分类结果，说明它具有更好地距离度量质量，能够 提高多元时间序列数据挖掘的挖掘效果。 另外，由 于 Ｅｕｃｌｉｄｅａｎ 和 ＤＴＷ 分别善于对等长和不等长时间 序列的相似性度量，故在实验中比较它们与新方法 的分类效果。 在图 ２ 分类结果中发现，ＭＥｒｏｓ 具有 最好的分类结果，而在图 ３ 分类结果中可以知道，在 第 ３ 期 李海林，等：基于特征矩阵的多元时间序列最小距离度量方法 ·４４５·