第2期 李海林，等：分段聚合近似和数值导数的动态时间弯曲方法 .253. 时间序列相似性度量形态匹配所占比重越大：反之 S.A.R.S.、S.A.R.SⅡ、S.C.分别表示Diatom Size Reduction、ECG Five 则形态匹配的比重就越小。图4也说明了时间序列 Days、Italy Power Demand、Medical Images、Mote Strain,Sony AIBO Ro-- bot Surface,Sony AlBO Robot Surface II,Synthetic Control. 数据集在大部分情况下更倾向于形态匹配而不是具 表2实验分类错误率 体数值上的比较。 Table 2 Classification error ratesof the experiments Datasets DTW DDTW PADD(avg) PADD(min) Beef 50.00 30.00 32.33 23.33(2) CBF 0.33 27.11 1.14 0.00(7) Coffee 17.86 14.29 2.86 0.00(3,5,10) D.S.Z. 3.27 6.21 5.49 3.27(5.10) 6 10 ECG200 23.00 19.00 12.90 9.00(2) 图4不同w下的最优参数0 E.F.D. 23.23 35.08 26.82 17.65(1) Fig.4 The best parameter for different w Face Four 17.05 29.55 20.91 15.91(5,6,7) 本次实验使用Keogh教授提供的数据集[0] fish 16.57 10.29 12.41 10.86(6) 并随机抽取20个数据集进行分类实验。如表1所 Gun-Point 9.33 1.33 5.40 2.67(5,7) 示，包含了各个数据集的基本详细信息，包括数据集 I.P.D. 4.96 8.75 6.81 4.28(6,8) 名称、类别个数、训练集个数、测试集个数、时间序列 Lighting7 27.40 41.09 28.63 23.29(1) 长度。表2包含了DTW、DDTW、PADD的平均错误 M.I. 26.32 32.24 29.89 26.45(5) 率，并且给出了PADD的最小错误率，其中括号表 M.S. 16.53 28.04 16.53 12.70(8) 示能够取得PADD的最小分类错误率的w,例如当 Olive Oil 13.33 16.67 14.00 13.33(2-9) CBF数据被降维到原始序列长度的70%时，可以取 OSU Leaf 40.91 7.02 27.89 19.42(2,5) 得最小错误率0。 S.A.R.S. 27.45 25.46 28.40 20.13(9) 表1时间序列数据集信息 S.A.R.SΠ 16.98 16.37 21.49 16.26(9) Table 1 Information of time series dataset Symbols 5.03 2.51 4.31 3.62(2,3) Datasets NO.C S.tr S.Tst length 5 S.C. 0.67 56.33 6.33 0.67(10) Beef 30 30 470 CBF 4 30 900 128 Trace 0.00 1.00 2.90 0.00(5,10) Coffee 2 28 28 286 MEAN 17.01 20.42 15.37 11.14 D.S.Z. 4 16 306 345 SD 13.42 14.74 10.78 8.89 ECG200 2 100 100 96 从实验结果来看，PADD的平均分类效果与 E.F.D. 2 23 861 136 Face Four 4 24 88 350 DTW和DDTW相比有着较大的优势，并且从最小分 Fish 7 175 175 463 类错误率的均值及标准差上来看也取得了不错的效 Gun Point 2 150 150 果，进而验证了PADD在时间序列数据挖掘中距离 I.P.D. 2 67 1029 24 度量的有效性。实验结果反映了时间序列分段聚合 Lighting7 7 70 13 319 后的特征序列长度大多数为原始序列长度的50%~ M.I. 10 381 760 99 100%,即0大多数取值为5~10时，PADD将会取到 M.S. 2 20 1252 84 比较好的效果。这也说明在进行序列转换过程中， Olive Oil 4 30 30 570 将时间序列的整体信息以及具体细节尽量完整保存 OSU Leaf 6 200 242 427 下来会取得更好的效果。 S.A.R.S. 2 20 601 70 S.A.R.SΠ 2 27 为了更为清楚地剖析分类结果在不同参数下的 953 65 Symbols 情况，给出了Sony AIBO Robot Surface和ECG这两 6 3 995 398 S.C. 6 300 300 60 个数据集的分类情况，如图5所示。从图5中可以 Trace 23 1139 82 看出，分类错误率呈高低波动状态。对于某些数据 注：表头NO.C、S.Tr,S.Tst、Length分别表示类别个数、训练集个数 集如Sony AIB0 Robot Surface来说，在不同w情况 测试集个数、序列长度。数据集名D.S.Z.、EFD.、LP.D.、ML.、M.S.、 下并非所有的PADD错误率都是最小的，但是在最时间序列相似性度量形态匹配所占比重越大；反之， 则形态匹配的比重就越小。 图 ４ 也说明了时间序列 数据集在大部分情况下更倾向于形态匹配而不是具 体数值上的比较。 图 ４ 不同 ｗ 下的最优参数 θ Ｆｉｇ．４ Ｔｈｅ ｂｅｓｔ ｐａｒａｍｅｔｅｒ θ ｆｏｒ ｄｉｆｆｅｒｅｎｔ ｗ 本次实验使用 Ｋｅｏｇｈ 教授提供的数据集［ ２０ ］ ， 并随机抽取 ２０ 个数据集进行分类实验。 如表 １ 所 示，包含了各个数据集的基本详细信息，包括数据集 名称、类别个数、训练集个数、测试集个数、时间序列 长度。 表 ２ 包含了 ＤＴＷ、ＤＤＴＷ、ＰＡＤＤ 的平均错误 率，并且给出了 ＰＡＤＤ 的最小错误率，其中括号表 示能够取得 ＰＡＤＤ 的最小分类错误率的 ｗ ，例如当 ＣＢＦ 数据被降维到原始序列长度的 ７０％时，可以取 得最小错误率 ０。 表 １ 时间序列数据集信息 Ｔａｂｌｅ １ Ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａｓｅｔ Ｄａｔａｓｅｔｓ ＮＯ．Ｃ Ｓ．ｔｒ Ｓ．Ｔｓｔ ｌｅｎｇｔｈ Ｂｅｅｆ ５ ３０ ３０ ４７０ ＣＢＦ ４ ３０ ９００ １２８ Ｃｏｆｆｅｅ ２ ２８ ２８ ２８６ Ｄ．Ｓ．Ｚ． ４ １６ ３０６ ３４５ ＥＣＧ２００ ２ １００ １００ ９６ Ｅ．Ｆ．Ｄ． ２ ２３ ８６１ １３６ Ｆａｃｅ Ｆｏｕｒ ４ ２４ ８８ ３５０ Ｆｉｓｈ ７ １７５ １７５ ４６３ Ｇｕｎ Ｐｏｉｎｔ ２ ５０ １５０ １５０ Ｉ．Ｐ．Ｄ． ２ ６７ １ ０２９ ２４ Ｌｉｇｈｔｉｎｇ７ ７ ７０ ７３ ３１９ Ｍ． Ｉ． １０ ３８１ ７６０ ９９ Ｍ．Ｓ． ２ ２０ １ ２５２ ８４ Ｏｌｉｖｅ Ｏｉｌ ４ ３０ ３０ ５７０ ＯＳＵ Ｌｅａｆ ６ ２００ ２４２ ４２７ Ｓ．Ａ．Ｒ．Ｓ． ２ ２０ ６０１ ７０ Ｓ．Ａ．Ｒ．Ｓ ＩＩ ２ ２７ ９５３ ６５ Ｓｙｍｂｏｌｓ ６ ２５ ９９５ ３９８ Ｓ．Ｃ． ６ ３００ ３００ ６０ Ｔｒａｃｅ ４ ２３ １ １３９ ８２ 注：表头 ＮＯ．Ｃ、Ｓ．Ｔｒ、Ｓ．Ｔｓｔ、Ｌｅｎｇｔｈ 分别表示类别个数、训练集个数、 测试集个数、序列长度。 数据集名 Ｄ．Ｓ．Ｚ．、Ｅ．Ｆ．Ｄ．、Ｉ．Ｐ．Ｄ．、Ｍ．Ｉ．、Ｍ．Ｓ．、 Ｓ．Ａ．Ｒ．Ｓ．、Ｓ．Ａ．Ｒ．Ｓ ＩＩ、Ｓ．Ｃ．分别表示 Ｄｉａｔｏｍ Ｓｉｚｅ Ｒｅｄｕｃｔｉｏｎ、ＥＣＧ Ｆｉｖｅ Ｄａｙｓ、Ｉｔａｌｙ Ｐｏｗｅｒ Ｄｅｍａｎｄ、Ｍｅｄｉｃａｌ Ｉｍａｇｅｓ、Ｍｏｔｅ Ｓｔｒａｉｎ、Ｓｏｎｙ ＡＩＢＯ Ｒｏ⁃ ｂｏｔ Ｓｕｒｆａｃｅ、Ｓｏｎｙ ＡＩＢＯ Ｒｏｂｏｔ Ｓｕｒｆａｃｅ ＩＩ、Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ． 表 ２ 实验分类错误率 Ｔａｂｌｅ ２ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｅｒｒｏｒ ｒａｔｅｓｏｆ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ％ Ｄａｔａｓｅｔｓ ＤＴＷ ＤＤＴＷ ＰＡＤＤ（ａｖｇ） ＰＡＤＤ（ｍｉｎ） Ｂｅｅｆ ５０．００ ３０．００ ３２．３３ ２３．３３（２） ＣＢＦ ０．３３ ２７．１１ １．１４ ０．００（７） Ｃｏｆｆｅｅ １７．８６ １４．２９ ２．８６ ０．００（３，５，１０） Ｄ．Ｓ．Ｚ． ３．２７ ６．２１ ５．４９ ３．２７（５，１０） ＥＣＧ２００ ２３．００ １９．００ １２．９０ ９．００（２） Ｅ．Ｆ．Ｄ． ２３．２３ ３５．０８ ２６．８２ １７．６５（１） Ｆａｃｅ Ｆｏｕｒ １７．０５ ２９．５５ ２０．９１ １５．９１（５，６，７） ｆｉｓｈ １６．５７ １０．２９ １２．４１ １０．８６（６） Ｇｕｎ⁃Ｐｏｉｎｔ ９．３３ １．３３ ５．４０ ２．６７（５，７） Ｉ．Ｐ．Ｄ． ４．９６ ８．７５ ６．８１ ４．２８（６，８） Ｌｉｇｈｔｉｎｇ７ ２７．４０ ４１．０９ ２８．６３ ２３．２９（１） Ｍ．Ｉ． ２６．３２ ３２．２４ ２９．８９ ２６．４５（５） Ｍ．Ｓ． １６．５３ ２８．０４ １６．５３ １２．７０（８） Ｏｌｉｖｅ Ｏｉｌ １３．３３ １６．６７ １４．００ １３．３３（２～ ９） ＯＳＵ Ｌｅａｆ ４０．９１ ７．０２ ２７．８９ １９．４２（２，５） Ｓ．Ａ．Ｒ．Ｓ． ２７．４５ ２５．４６ ２８．４０ ２０．１３（９） Ｓ．Ａ．Ｒ．Ｓ ＩＩ １６．９８ １６．３７ ２１．４９ １６．２６（９） Ｓｙｍｂｏｌｓ ５．０３ ２．５１ ４．３１ ３．６２（２，３） Ｓ．Ｃ． ０．６７ ５６．３３ ６．３３ ０．６７（１０） Ｔｒａｃｅ ０．００ １．００ ２．９０ ０．００（５，１０） ＭＥＡＮ １７．０１ ２０．４２ １５．３７ １１．１４ ＳＤ １３．４２ １４．７４ １０．７８ ８．８９ 从实验结果来看， ＰＡＤＤ 的平均分类效果与 ＤＴＷ 和 ＤＤＴＷ 相比有着较大的优势，并且从最小分 类错误率的均值及标准差上来看也取得了不错的效 果，进而验证了 ＰＡＤＤ 在时间序列数据挖掘中距离 度量的有效性。 实验结果反映了时间序列分段聚合 后的特征序列长度大多数为原始序列长度的 ５０％ ～ １００％，即 ｗ 大多数取值为 ５～１０ 时，ＰＡＤＤ 将会取到 比较好的效果。 这也说明在进行序列转换过程中， 将时间序列的整体信息以及具体细节尽量完整保存 下来会取得更好的效果。 为了更为清楚地剖析分类结果在不同参数下的 情况，给出了 Ｓｏｎｙ ＡＩＢＯ Ｒｏｂｏｔ Ｓｕｒｆａｃｅ 和 ＥＣＧ 这两 个数据集的分类情况，如图 ５ 所示。 从图 ５ 中可以 看出，分类错误率呈高低波动状态。 对于某些数据 集如 Ｓｏｎｙ ＡＩＢＯ Ｒｏｂｏｔ Ｓｕｒｆａｃｅ 来说，在不同 ｗ 情况 下并非所有的 ＰＡＤＤ 错误率都是最小的，但是在最 第 ２ 期 李海林，等：分段聚合近似和数值导数的动态时间弯曲方法 ·２５３·