第11卷第2期 智能系统学报 Vol.11 No.2 2016年4月 CAAI Transactions on Intelligent Systems Apr.2016 D0I:10.11992/is.201507064 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160315.1239.012.html 分段聚合近似和数值导数的动态时间弯曲方法 李海林，梁叶 (华侨大学信息管理系，福建泉州362021)》 摘要：针对动态弯曲方法对时间序列数据相似性度量的质量和效率的局限性，本文提出一种基于分段聚合近似和 数值导数的动态时间弯曲方法。该方法通过分段聚合近似将时间序列数据进行有效地降维，再结合数值导数对降 维后的特征序列构建新特征序列，并且设计符合该特征序列相似性度量方法。实验结果分析表明，与传统动态弯曲 方法相比，新方法具有较好的度量质量，能在时间序列数据挖掘中得到较好的分类效果，且在低维空间具有较高的 分类效率，具有一定的优越性。 关键词：动态时间弯曲；时间序列：分段聚合近似；数值导数：相似性度量：分类：数据降维：特征表示 中图分类号：TP301文献标志码：A文章编号：1673-4785(2016)02-0249-08 中文引用格式：李海林，梁叶.分段聚合近似和数值导数的动态时间弯曲方法[J】.智能系统学报，2016,11(2)：249-256. 英文引用格式：LI Hailin,LIANG Ye.Dynamic time warping based on piecewise aggregate approximation and data derivatives[J]. CAAI transactions on intelligent systems,2016,11(2):249-256. Dynamic time warping based on piecewise aggregate approximation and data derivatives LI Hailin,LIANG Ye (Department of Information Management,Huaqiao University,Quanzhou 362021,China) Abstract:Dynamic time warping(DTW)is often used to measure the similarity of time series data;however,it has efficiency and quality limitations.In this study,a novel DTW method combining piecewise aggregate approximation (PAA)and derivatives is proposed to measure the similarity of time series.The dimensionality of the time series data was effectively reduced by PAA,and the feature sequence was transformed into new sequences by combining the numerical derivatives after the dimensionality reduction.Furthermore,the DTW design corresponded to the sim- ilarity measurement method of the feature sequence.The experimental results demonstrate that the proposed method is superior because it has better measurement quality,obtains a better classification effect in time series data min- ing,and has high efficiency in lower dimensional spaces. Keywords:dynamic time warping;time series;piecewise aggregate approximation;numerical derivative;similari- ty measure;classification;dimensionality reduction;feature representation 近年来，时间序列成为了数据挖掘研究领域中 极其关键的工作之一，很多挖掘任务的结果易受其 的热点，其研究成果已被广泛地应用在工业、金融、 相似性度量质量和效率的影响。目前，动态时间弯 气象、航天、生物医学等各种领域]。然而，相似 曲(dynamic time warping,DTW)是一种鲁棒性较强 性度量方法成为时间序列数据挖掘领域中基础而又的方法之一，其最早应用于语音识别6，如今已被 广泛应用于时间序列相似性的度量[]。欧氏距离 收稿日期：2015-07-24.网络出版日期：2016-03-15. 基金项目：国家自然科学基金项目(61300139)：福建省中青年教育科研 虽能快速度量时间序列之间的相似性，但其限于相 基金项目(JAS14024):华侨大学中青年教师科研提升计划项 同时间点上的数据匹配，而且对异常数据点较为敏 目(ZQN-PY220). 通信作者：李海林.E-mail:hailin(@hqu.cdu.cn 感。DTW不仅可以弯曲度量不等长时间序列之间第 １１ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．２ ２０１６ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０６４ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０３１５．１２３９．０１２．ｈｔｍｌ 分段聚合近似和数值导数的动态时间弯曲方法 李海林，梁叶 （华侨大学 信息管理系， 福建 泉州 ３６２０２１） 摘 要：针对动态弯曲方法对时间序列数据相似性度量的质量和效率的局限性，本文提出一种基于分段聚合近似和 数值导数的动态时间弯曲方法。 该方法通过分段聚合近似将时间序列数据进行有效地降维，再结合数值导数对降 维后的特征序列构建新特征序列，并且设计符合该特征序列相似性度量方法。 实验结果分析表明，与传统动态弯曲 方法相比，新方法具有较好的度量质量，能在时间序列数据挖掘中得到较好的分类效果，且在低维空间具有较高的 分类效率，具有一定的优越性。 关键词：动态时间弯曲；时间序列；分段聚合近似；数值导数；相似性度量；分类；数据降维；特征表示 中图分类号： ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０２⁃０２４９⁃０８ 中文引用格式：李海林，梁叶． 分段聚合近似和数值导数的动态时间弯曲方法［Ｊ］． 智能系统学报， ２０１６， １１（２）： ２４９⁃２５６． 英文引用格式：ＬＩ Ｈａｉｌｉｎ， ＬＩＡＮＧ Ｙｅ． Ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ ｂａｓｅｄ ｏｎ ｐｉｅｃｅｗｉｓｅ ａｇｇｒｅｇａｔｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｎｄ ｄａｔａ ｄｅｒｉｖａｔｉｖｅｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（２）： ２４９⁃２５６． Ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ ｂａｓｅｄ ｏｎ ｐｉｅｃｅｗｉｓｅ ａｇｇｒｅｇａｔｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｎｄ ｄａｔａ ｄｅｒｉｖａｔｉｖｅｓ ＬＩ Ｈａｉｌｉｎ， ＬＩＡＮＧ Ｙｅ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｍａｎａｇｅｍｅｎｔ， Ｈｕａｑｉａｏ Ｕｎｉｖｅｒｓｉｔｙ， Ｑｕａｎｚｈｏｕ ３６２０２１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ （ＤＴＷ） ｉｓ ｏｆｔｅｎ ｕｓｅｄ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ； ｈｏｗｅｖｅｒ， ｉｔ ｈａｓ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｑｕａｌｉｔｙ ｌｉｍｉｔａｔｉｏｎｓ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ａ ｎｏｖｅｌ ＤＴＷ ｍｅｔｈｏｄ ｃｏｍｂｉｎｉｎｇ ｐｉｅｃｅｗｉｓｅ ａｇｇｒｅｇａｔｅ ａｐｐｒｏｘｉｍａｔｉｏｎ （ＰＡＡ） ａｎｄ ｄｅｒｉｖａｔｉｖｅｓ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｍｅａｓｕｒｅ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ． Ｔｈｅ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｏｆ ｔｈｅ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ｗａｓ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅｄｕｃｅｄ ｂｙ ＰＡＡ， ａｎｄ ｔｈｅ ｆｅａｔｕｒｅ ｓｅｑｕｅｎｃｅ ｗａｓ ｔｒａｎｓｆｏｒｍｅｄ ｉｎｔｏ ｎｅｗ ｓｅｑｕｅｎｃｅｓ ｂｙ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｎｕｍｅｒｉｃａｌ ｄｅｒｉｖａｔｉｖｅｓ ａｆｔｅｒ ｔｈｅ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｔｈｅ ＤＴＷ ｄｅｓｉｇｎ ｃｏｒｒｅｓｐｏｎｄｅｄ ｔｏ ｔｈｅ ｓｉｍ⁃ ｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｍｅｔｈｏｄ ｏｆ ｔｈｅ ｆｅａｔｕｒｅ ｓｅｑｕｅｎｃｅ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｉｓ ｓｕｐｅｒｉｏｒ ｂｅｃａｕｓｅ ｉｔ ｈａｓ ｂｅｔｔｅｒ ｍｅａｓｕｒｅｍｅｎｔ ｑｕａｌｉｔｙ， ｏｂｔａｉｎｓ ａ ｂｅｔｔｅｒ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｅｆｆｅｃｔ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ｍｉｎ⁃ ｉｎｇ， ａｎｄ ｈａｓ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ ｉｎ ｌｏｗｅｒ ｄｉｍｅｎｓｉｏｎａｌ ｓｐａｃｅｓ． Ｋｅｙｗｏｒｄｓ： ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ； ｔｉｍｅ ｓｅｒｉｅｓ； ｐｉｅｃｅｗｉｓｅ ａｇｇｒｅｇａｔｅ ａｐｐｒｏｘｉｍａｔｉｏｎ； ｎｕｍｅｒｉｃａｌ ｄｅｒｉｖａｔｉｖｅ； ｓｉｍｉｌａｒｉ⁃ ｔｙ ｍｅａｓｕｒｅ； ｃｌａｓｓｉｆｉｃａｔｉｏｎ；ｄｉｍｅｎｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ； ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ 收稿日期：２０１５⁃０７⁃２４． 网络出版日期：２０１６⁃０３⁃１５． 基金项目：国家自然科学基金项目（６１３００１３９）；福建省中青年教育科研 基金项目（ＪＡＳ１４０２４）；华侨大学中青年教师科研提升计划项 目（ＺＱＮ⁃ＰＹ２２０）． 通信作者：李海林． Ｅ⁃ｍａｉｌ：ｈａｉｌｉｎ＠ ｈｑｕ．ｅｄｕ．ｃｎ． 近年来，时间序列成为了数据挖掘研究领域中 的热点，其研究成果已被广泛地应用在工业、金融、 气象、航天、生物医学等各种领域［１⁃５］ 。 然而，相似 性度量方法成为时间序列数据挖掘领域中基础而又 极其关键的工作之一，很多挖掘任务的结果易受其 相似性度量质量和效率的影响。 目前，动态时间弯 曲（ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ， ＤＴＷ）是一种鲁棒性较强 的方法之一，其最早应用于语音识别［６］ ，如今已被 广泛应用于时间序列相似性的度量［７⁃９］ 。 欧氏距离 虽能快速度量时间序列之间的相似性，但其限于相 同时间点上的数据匹配，而且对异常数据点较为敏 感。 ＤＴＷ 不仅可以弯曲度量不等长时间序列之间