·250· 智能系统学报 第11卷 的相似性，其度量质量能较好地反映数据之间的异 在减小数据存储和提高计算效率方面起到了很大的 步关系[o]。然而，由于DTW需要在代价矩阵中计 作用。通过对长度为n的序列S=(s1,s2,…,sn)转 算最优弯曲路径，使其具有较高的时间复杂度或较 化为另一条长度为m的序列Q=(q1,92,…,9m), 好的度量精度[)。 实现时间序列的数据降维和特征表示，其中n>m, 时间序列降维表示是通过某种方法将原始序列 且令k=n/m。新序列中任意元素q:满足： 进行转换或者特征提取，以达到将原始时间序列在 低维度表示的目的。由于直接使用和计算原始时间 1≤i≤m(1) 序列可能需要付出较大的代价，如消耗较多存储空 对序列S进行分段后求出每段的均值，每段均值 间，运行效率低等问题，加上原始时间序列包含很多 形成序列Q,进而达到序列S数据降维的目的。如图 “噪音点”，容易导致相似性度量结果不准确。因 1,子图(a)显示了长度为60的时间序列S通过PAA 此，为简化数据模型和算法的复杂性，提高数据挖掘 被平均分成10段，每段均值代表相应片段的特征：子 技术的性能，有必要对原始时间序列进行降维处理， 图(b)显示由10个均值组成的新序列Q。 达到效率和准确性的平衡。目前，针对时间序列降 2 1.0 维的方法已有很多且较为成熟，如分段聚合近似 (piecewise aggregate approximation,PAA)【],该方 法通过将时间序列进行平均分段，并以分段均值反 映分段信息，最终达到数据降维的目的：分段线性近 似(piecewise liner approximation,PLA)【I利用线性 -1.0 模型对时间序列进行分割，根据不同的分割策略可 2040 60 246810 时间戳/s 时间戳/s 以得到不同的时间序列降维效果：基于域变换的离 (a)时间序列及其分段均值 (b)时间序列的特征表示 散傅里叶变换(discrete fourier transform,DFT)【u6和 图1基于PAA的时间序列数据降维和特征表示 离散小波变换(discrete wavelet transform, Fig.1 Dimensionality reduction and feature represen- DWT)【1),利用变换后的系数对时间序列进行特征 tation of time series based on PAA 表示；奇异值分解(singular value decomposition, 分段聚合近似方法通过均值来表示序列片段的 SVD)[1),利用数值计算将高维数据转换到低维空 特征，容易忽略数据的局部形态变化情况。然而，在 间，不仅应用在时间序列数据降维及索引，而且也被 实际运用中，时间序列的整体形态通常是关注和研 广泛地应用于模式识别、图像压缩等等。由于降维 究的重点。PAA得到的序列特征不仅能够很好地 方法对整个研究过程起着十分关键的作用，不仅要 反映较长时间序列数据形态的整体变化趋势，而且 求算法能够尽可能简单快速，以降低时间消耗，也要 还能对时间序列数据进行数据降维，起到提高相关 尽量充分反映时间序列的信息。因此研究过程中应 数据挖掘算法效率的作用。 选择合适的降维方法来解决问题。 1.2动态时间弯曲 鉴于传统DTW方法在度量时间序列相似性时 动态时间弯曲最初被应用于语音识别中，常被 具有计算时间效率较低和缺少考虑序列的形态（即 运用到比较2条时间序列的相似性。针对2条时间 凹凸性)等问题，并且从使用较为简单的数据降维 方法以简化模型的角度出发，本文提出通过利用分 序列S=(s1s2,…,sn)和Q=(91,92,…,9m),对任 意两点之间的距离构建一个n×m的距离矩阵D, 段聚合近似(PAA)方法对时间序列进行数据降维， 获得保持原始序列主要特征的数据序列，再构造基 其中d(i,)表示时间序列数据点s:和g之间的距 于数据点的一阶导数的新特征序列，结合动态时间 离，即d(i,)=(s:-g)。DTW的基本思想就是从 弯曲提出一种新的距离度量方法，即近似导数动态 距离矩阵中寻找一条使得2条序列之间的累计距离 时间弯曲方法。数值实验分类结果和效率分析表 最小的路径，其最小累积距离值为 明，该方法能从形态视角出发，较好地从数据集中找 DTw(s.)=min() (2) 出相似序列，提高数据挖掘领域中分类算法的质量， 具有一定的优越性。 弯曲路径是一条具有连续K个距离矩阵元素 的集合W=（01,w2,…,0x),第k个元素为0g= 1 相关理论基础 (i,j)k且max(n,m)≤K≤n+m-1。与此同时， 1.1分段聚合近似(PAA) 弯曲路径通常要遵循着3个条件： 分段聚合近似是一种有效的数据降维方法，其 1)边界性：w1=（1,1),0k=（n,m);的相似性，其度量质量能较好地反映数据之间的异 步关系［１０］ 。 然而，由于 ＤＴＷ 需要在代价矩阵中计 算最优弯曲路径，使其具有较高的时间复杂度或较 好的度量精度［１１⁃１３］ 。 时间序列降维表示是通过某种方法将原始序列 进行转换或者特征提取，以达到将原始时间序列在 低维度表示的目的。 由于直接使用和计算原始时间 序列可能需要付出较大的代价，如消耗较多存储空 间，运行效率低等问题，加上原始时间序列包含很多 “噪音点”，容易导致相似性度量结果不准确。 因 此，为简化数据模型和算法的复杂性，提高数据挖掘 技术的性能，有必要对原始时间序列进行降维处理， 达到效率和准确性的平衡。 目前，针对时间序列降 维的方法已有很多且较为成熟，如分段聚合近似 （ｐｉｅｃｅｗｉｓｅ ａｇｇｒｅｇａｔｅ ａｐｐｒｏｘｉｍａｔｉｏｎ， ＰＡＡ） ［１４］ ，该方 法通过将时间序列进行平均分段，并以分段均值反 映分段信息，最终达到数据降维的目的；分段线性近 似（ｐｉｅｃｅｗｉｓｅ ｌｉｎｅｒ ａｐｐｒｏｘｉｍａｔｉｏｎ， ＰＬＡ） ［１５］利用线性 模型对时间序列进行分割，根据不同的分割策略可 以得到不同的时间序列降维效果；基于域变换的离 散傅里叶变换（ｄｉｓｃｒｅｔｅ ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ， ＤＦＴ） ［１６］和 离 散 小 波 变 换 （ ｄｉｓｃｒｅｔｅ ｗａｖｅｌｅｔ ｔｒａｎｓｆｏｒｍ， ＤＷＴ） ［１７］ ，利用变换后的系数对时间序列进行特征 表示； 奇 异 值 分 解 （ ｓｉｎｇｕｌａｒ ｖａｌｕｅ ｄｅｃｏｍｐｏｓｉｔｉｏｎ， ＳＶＤ） ［１８］ ，利用数值计算将高维数据转换到低维空 间，不仅应用在时间序列数据降维及索引，而且也被 广泛地应用于模式识别、图像压缩等等。 由于降维 方法对整个研究过程起着十分关键的作用，不仅要 求算法能够尽可能简单快速，以降低时间消耗，也要 尽量充分反映时间序列的信息。 因此研究过程中应 选择合适的降维方法来解决问题。 鉴于传统 ＤＴＷ 方法在度量时间序列相似性时 具有计算时间效率较低和缺少考虑序列的形态（即 凹凸性）等问题，并且从使用较为简单的数据降维 方法以简化模型的角度出发，本文提出通过利用分 段聚合近似（ＰＡＡ）方法对时间序列进行数据降维， 获得保持原始序列主要特征的数据序列，再构造基 于数据点的一阶导数的新特征序列，结合动态时间 弯曲提出一种新的距离度量方法，即近似导数动态 时间弯曲方法。 数值实验分类结果和效率分析表 明，该方法能从形态视角出发，较好地从数据集中找 出相似序列，提高数据挖掘领域中分类算法的质量， 具有一定的优越性。 １ 相关理论基础 １．１ 分段聚合近似（ＰＡＡ） 分段聚合近似是一种有效的数据降维方法，其 在减小数据存储和提高计算效率方面起到了很大的 作用。 通过对长度为 ｎ 的序列 Ｓ ＝ （ｓ１ ，ｓ２ ，…，ｓｎ ） 转 化为另一条长度为 ｍ 的序列 Ｑ ＝ （ｑ１ ，ｑ２ ，…，ｑｍ ） ， 实现时间序列的数据降维和特征表示，其中 ｎ ＞ ｍ ， 且令 ｋ ＝ ｎ ／ ｍ 。 新序列中任意元素 ｑｉ 满足： ｑｉ ＝ １ ｋ ∑ ｋ∗ｉ ｊ ＝ ｋ∗（ｉ－１） ＋１ ｓｉ， １ ≤ ｉ ≤ ｍ （１） 对序列 Ｓ 进行分段后求出每段的均值，每段均值 形成序列 Ｑ ，进而达到序列 Ｓ 数据降维的目的。 如图 １，子图（ａ）显示了长度为 ６０ 的时间序列 Ｓ 通过 ＰＡＡ 被平均分成 １０ 段，每段均值代表相应片段的特征；子 图（ｂ）显示由 １０ 个均值组成的新序列 Ｑ 。 图 １ 基于 ＰＡＡ 的时间序列数据降维和特征表示 Ｆｉｇ．１ Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ａｎｄ ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎ⁃ ｔａｔｉｏｎ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ ｂａｓｅｄ ｏｎ ＰＡＡ 分段聚合近似方法通过均值来表示序列片段的 特征，容易忽略数据的局部形态变化情况。 然而，在 实际运用中，时间序列的整体形态通常是关注和研 究的重点。 ＰＡＡ 得到的序列特征不仅能够很好地 反映较长时间序列数据形态的整体变化趋势，而且 还能对时间序列数据进行数据降维，起到提高相关 数据挖掘算法效率的作用。 １．２ 动态时间弯曲 动态时间弯曲最初被应用于语音识别中，常被 运用到比较 ２ 条时间序列的相似性。 针对 ２ 条时间 序列 Ｓ ＝ （ｓ１ ，ｓ２ ，…，ｓｎ ） 和 Ｑ ＝ （ｑ１ ，ｑ２ ，…，ｑｍ ） ，对任 意两点之间的距离构建一个 ｎ × ｍ 的距离矩阵 Ｄ ， 其中 ｄ（ｉ，ｊ） 表示时间序列数据点 ｓｉ 和 ｑｊ 之间的距 离，即 ｄ（ｉ，ｊ） ＝ （ｓｉ － ｑｊ） ２ 。 ＤＴＷ 的基本思想就是从 距离矩阵中寻找一条使得 ２ 条序列之间的累计距离 最小的路径，其最小累积距离值为 ＤＴＷ（Ｓ，Ｑ） ＝ ｍｉｎ Ｗ （∑ Ｋ ｋ ＝ １ ｗｋ） （２） 弯曲路径是一条具有连续 Ｋ 个距离矩阵元素 的集合 Ｗ ＝ （ｗ１ ，ｗ２ ，…，ｗＫ ） ，第 ｋ 个元素为 ｗｋ ＝ （ｉ，ｊ）ｋ 且 ｍａｘ（ｎ，ｍ） ≤ Ｋ ≤ ｎ ＋ ｍ － １。 与此同时， 弯曲路径通常要遵循着 ３ 个条件： １）边界性： ｗ１ ＝ （１，１） ， ｗｋ ＝ （ｎ，ｍ） ； ·２５０· 智 能 系 统 学 报 第 １１ 卷