基于多维时间序列形态特征的相似性动态聚类算法

工程科学学报，第39卷，第7期：1114-1122,2017年7月 Chinese Journal of Engineering,Vol.39,No.7:1114-1122,July 2017 D0l:10.13374/j.issn2095-9389.2017.07.019:http://journals..ustb.edu.cn 基于多维时间序列形态特征的相似性动态聚类算法 玲12四，孟建瑶2》，徐培培2》，彭开香12) 1)北京科技大学自动化学院，北京1000832)北京科技大学工业过程知识自动化教有部重点实验室，北京100083 区通信作者，E-mail:lingwang@usth.ed.cen 摘要由于时间序列数据具有高维度、动态性等特点，这就导致传统的数据挖掘技术很难有效的对其进行处理，为此，提出 了一种基于多维时间序列形态特征的相似性动态聚类算法(similarity dynamical clustering algorithm based on multidimensional shape features for time series,SDCTS).首先，提取多维时间序列的特征点以实现降维，然后，根据多维时间序列的斜率、长度和 幅值变化的形态特征定义了一种新的时间序列相似性度量标准，进而提出无需人为给定聚类个数的多维时间序列动态聚类 算法。实验结果表明，与其他算法相比，此算法对时间序列具有良好的聚类效果. 关键词相似性度量：聚类：时间序列：形态特征：降维 分类号TP311 Similarity dynamical clustering algorithm based on multidimensional shape features for time series WANG Ling MENG Jian-yao,XU Pei-pei,PENG Kai-xiang 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Key Laboratory of Knowledge Automationfor Industrial Processes (Ministry of Education),University of Science and Technology Beijing,Beijing 100083.China Corresponding author,E-mail:lingwang@ustb.edu.cn ABSTRACT Traditional data mining methods are difficult to deal with the high dimensionality and dynamics characteristic of the time series.Therefore,in this study,a similarity dynamical clustering algorithm based on multidimensional shape features for time se- ries (SDCTS)was proposed.First,the feature points of multidimensional time series are extracted to realize dimensionality reduction. Second,a new similarity measure criterion is defined with the shape features (slope,length,and amplitude)of the obtained multidi- mensional time series,and thus a dynamical clustering algorithm of multidimensional time series is proposed without predefining cluste- ring numbers.The experimental results demonstrate that the SDCTS algorithm improves the clustering accuracy for time series com- pared with other algorithms. KEY WORDS similarity measure;clustering;time series:shape features:dimensionality reduction 时间序列数据是指带有时间属性标签的数据的集 考虑到时间序列具有高维度、动态性、在时间轴上 合，其广泛存在于商业、医学、工程、社会科学等数据库 分布离散、易受噪声干扰等特点四，在对时间序列进行 中，对其进行高效处理和应用，能够带来极大的应用价 聚类之前，需要进行一定的预处理，常用的预处理方法 值Ⅲ.为了有效地获取时间序列数据内部的结构，可 有降维、相似性或相异性度量.考虑到时间序列的特 以采用聚类方法对时间序列进行分析 殊性，首先对时间序列进行降维处理，常见的降维方法 收稿日期：201701-03 基金项目：国家自然科学基金资助项目(61572073)：北京科技大学中央高校基本科研业务费专项资金资助(FRF-BD-16O05A):北京市重点 学科共建资助项目(XK100080537)

工程科学学报，第 39 卷，第 7 期: 1114--1122，2017 年 7 月 Chinese Journal of Engineering，Vol． 39，No． 7: 1114--1122，July 2017 DOI: 10． 13374 /j． issn2095--9389． 2017． 07． 019; http: / /journals． ustb． edu． cn 基于多维时间序列形态特征的相似性动态聚类算法 王 玲1，2) ，孟建瑶1，2) ，徐培培1，2) ，彭开香1，2) 1) 北京科技大学自动化学院，北京 100083 2) 北京科技大学工业过程知识自动化教育部重点实验室，北京 100083 通信作者，E-mail: lingwang@ ustb． edu． cn 摘 要 由于时间序列数据具有高维度、动态性等特点，这就导致传统的数据挖掘技术很难有效的对其进行处理，为此，提出 了一种基于多维时间序列形态特征的相似性动态聚类算法( similarity dynamical clustering algorithm based on multidimensional shape features for time series，SDCTS) ． 首先，提取多维时间序列的特征点以实现降维，然后，根据多维时间序列的斜率、长度和 幅值变化的形态特征定义了一种新的时间序列相似性度量标准，进而提出无需人为给定聚类个数的多维时间序列动态聚类 算法． 实验结果表明，与其他算法相比，此算法对时间序列具有良好的聚类效果． 关键词 相似性度量; 聚类; 时间序列; 形态特征; 降维 分类号 TP311 Similarity dynamical clustering algorithm based on multidimensional shape features for time series WANG Ling1，2)  ，MENG Jian-yao1，2) ，XU Pei-pei1，2) ，PENG Kai-xiang1，2) 1) School of Automation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Key Laboratory of Knowledge Automationfor Industrial Processes ( Ministry of Education) ，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: lingwang@ ustb． edu． cn ABSTＲACT Traditional data mining methods are difficult to deal with the high dimensionality and dynamics characteristic of the time series． Therefore，in this study，a similarity dynamical clustering algorithm based on multidimensional shape features for time se￾ries ( SDCTS) was proposed． First，the feature points of multidimensional time series are extracted to realize dimensionality reduction． Second，a new similarity measure criterion is defined with the shape features ( slope，length，and amplitude) of the obtained multidi￾mensional time series，and thus a dynamical clustering algorithm of multidimensional time series is proposed without predefining cluste￾ring numbers． The experimental results demonstrate that the SDCTS algorithm improves the clustering accuracy for time series com￾pared with other algorithms． KEY WOＲDS similarity measure; clustering; time series; shape features; dimensionality reduction 收稿日期: 2017--01--03 基金项目: 国家自然科学基金资助项目( 61572073) ; 北京科技大学中央高校基本科研业务费专项资金资助( FＲF--BD--16--005A) ; 北京市重点 学科共建资助项目( XK100080537) 时间序列数据是指带有时间属性标签的数据的集 合，其广泛存在于商业、医学、工程、社会科学等数据库 中，对其进行高效处理和应用，能够带来极大的应用价 值［1］． 为了有效地获取时间序列数据内部的结构，可 以采用聚类方法对时间序列进行分析． 考虑到时间序列具有高维度、动态性、在时间轴上 分布离散、易受噪声干扰等特点［2］，在对时间序列进行 聚类之前，需要进行一定的预处理，常用的预处理方法 有降维、相似性或相异性度量． 考虑到时间序列的特 殊性，首先对时间序列进行降维处理，常见的降维方法

王玲等：基于多维时间序列形态特征的相似性动态聚类算法 *1115· 包括傅立叶变换田、基于小波的变换田、分段线性拟 则数据点x:为表征时间序列变化的极值转折特征点； 合可等，但这些方法常常存在计算复杂度相对比较高 若其满足公式(2)，则数据点x:为可以反映时间序列 等问题.文献6-]通过提取时间序列中的某些特征 局部变化趋势的非极值转折特征点. 点来实现时间序列的降维，且能对原有时间序列中的 {(x-1x+i)}U{(x-1>x)∩(x)U(ix)n(x=x)}. (2) namic time warping,DDTW)方法对不等长时间序列进 为了进一步对时间序列数据进行压缩，在保证时 行聚类时的优势，提出了一种新的距离度量标准，能够 间序列变化趋势的前提下，选择出最少的特征点，本文 较好的实现不同时间序列的距离度量，实现时间序列 以平均拟合误差作为筛选原则，剔除那些左右两侧趋 的聚类.谢福鼎等可通过提取时间序列中部分极值点 势变化不明显的噪声特征点 实现序列降维，等长处理后基于欧氏距离及模糊C均 定义2平均拟合误差：假设时间序列s={(, 值聚类(fuzzy C-means clustering,FCM)算法实现时间 x）,…,(x）,…,(.x)}(i=1,2,…,n)提取了k 序列聚类，计算复杂度低，容易实现，但存在要求时间 个特征点，根据这些特征点，可以将时间序列划分为 序列长度一致、对时间轴变化敏感等问题.孙雅与李 k-1段，即 志华@选取区域极值点作为时间序列中的特征点实 s={s1,…5,…,$k-1}={(1l2,x1,x2),…, 现时间序列降维处理，然后基于动态弯曲距离提出了 （4+1xxi）,…,（1ex-x)}.(3) 种时间序列层次聚类的算法，但该算法相似性度量 其中，x,和x,1(=1,2,…,k-1)分别表示s中第段 计算复杂度较高，影响了算法效率.刘永志等四在考 子时间序列的起始值和终值；，和：分别表示s中第 虑时间序列中关键点的基础上实现时间序列的降维， 段子时间序列的起始时刻和终止时刻.采用插补方 对不等长时间序列进行转换后通过置信区间计算序列 法将第。段子序列的首尾两点相连，得到拟合直线 相似度，计算量较低，但其关键点筛选时未考虑整体拟 (）=k,t+b,其中： 合情况，且结果受置信度影响较大：刘琴等网结合滑 动窗口及类K-means聚类算法提出了一种基于滑窗不 k=山龙 (4) l+1-t, 等长时间序列的短时间序列(short time series,STS)距 (x1-) b.=x11-l, (5) 离的聚类算法，能够解决不等长时间序列聚类的问题， 但最佳聚类个数难以确定. 第v段子序列的平均拟合误差如下式所示： 针对上述算法中存在的问题，本文首先在保证原 ∑1x-f()1 有时间序列趋势不变的前提下，通过选择一些蕴含重 8.= (6) 要信息的特征点，提出基于特征点的时间序列降维算 1-↓，+1 法来实现对时间序列数据压缩，降低时间序列维度，然 通过特征点提取策略，提出了一种基于特征点的 后根据多维序列的形态特征，设计了一种新的时间序 时间序列降维算法，基本思路是：首先提取原始时间序 列相似性度量标准，并在此基础上，提出了一种基于多 列中的转折特征点，然后利用平均拟合误差对已选择 维时间序列形态特征的相似性动态聚类算法 特征点进行筛选，在保留原时间序列局部和整体变化 趋势的同时，尽可能多的删除左右侧趋势变化不明显 1基于特征点的时间序列降维 的噪声特征点，实现时间序列的降维处理.降维算法 为了实现对多维时间序列的降维处理并保证原有 流程如下 时间序列的变化趋势，可通过提取时间序列的特征点， 输入：时间序列s={(11,x）,…,(,x),…,(。, 对其依次相连构成时间序列的降维表示.根据时间序 x)},平均拟合误差阈值E· 列中不同数据点的特征变化，本文选择的特征点分为 输出：最终特征点序列 边界特征点和转折特征点两类.其中，边界特征点是 初始化：sx=⑦ 时间序列的起始和终止两个端点 Stepl将时间序列s中的边界特征点x,和x。添 定义1转折特征点：假设包含n个数据点的时 加到初始特征点序列s、中. 间序列为s={(1,x),…,(,x),…,(n,x)},其中 Step2从时间序列s中依次获得新的数据点x: x:为第i(i=1,2,…,n)个数据点在时间t,处的取值. (i=2,3,…,n-1) 对于数据点x(i=2,3,…,n-1),若其满足公式(1)， (a)如果x:满足公式(1)，则它为极值转折特征

王 玲等: 基于多维时间序列形态特征的相似性动态聚类算法 包括傅立叶变换［3］、基于小波的变换［4］、分段线性拟 合［5］等，但这些方法常常存在计算复杂度相对比较高 等问题． 文献［6--7］通过提取时间序列中的某些特征 点来实现时间序列的降维，且能对原有时间序列中的 变化趋势信息进行较好的保留，然而降维后会形成不 等长的时间序列，无法用欧氏距离对不等长数据进行 相似性 度 量． uczak［8］ 考虑 动 态 时 间 弯 曲( dynamic time warping，DTW) 及扩展动态时间弯( derivative dy￾namic time warping，DDTW) 方法对不等长时间序列进 行聚类时的优势，提出了一种新的距离度量标准，能够 较好的实现不同时间序列的距离度量，实现时间序列 的聚类． 谢福鼎等［9］通过提取时间序列中部分极值点 实现序列降维，等长处理后基于欧氏距离及模糊 C 均 值聚类( fuzzy C-means clustering ，FCM) 算法实现时间 序列聚类，计算复杂度低，容易实现，但存在要求时间 序列长度一致、对时间轴变化敏感等问题． 孙雅与李 志华［10］选取区域极值点作为时间序列中的特征点实 现时间序列降维处理，然后基于动态弯曲距离提出了 一种时间序列层次聚类的算法，但该算法相似性度量 计算复杂度较高，影响了算法效率． 刘永志等［11］在考 虑时间序列中关键点的基础上实现时间序列的降维， 对不等长时间序列进行转换后通过置信区间计算序列 相似度，计算量较低，但其关键点筛选时未考虑整体拟 合情况，且结果受置信度影响较大; 刘琴等［12］结合滑 动窗口及类 K-means 聚类算法提出了一种基于滑窗不 等长时间序列的短时间序列( short time series，STS) 距 离的聚类算法，能够解决不等长时间序列聚类的问题， 但最佳聚类个数难以确定． 针对上述算法中存在的问题，本文首先在保证原 有时间序列趋势不变的前提下，通过选择一些蕴含重 要信息的特征点，提出基于特征点的时间序列降维算 法来实现对时间序列数据压缩，降低时间序列维度，然 后根据多维序列的形态特征，设计了一种新的时间序 列相似性度量标准，并在此基础上，提出了一种基于多 维时间序列形态特征的相似性动态聚类算法． 1 基于特征点的时间序列降维 为了实现对多维时间序列的降维处理并保证原有 时间序列的变化趋势，可通过提取时间序列的特征点， 对其依次相连构成时间序列的降维表示． 根据时间序 列中不同数据点的特征变化，本文选择的特征点分为 边界特征点和转折特征点两类． 其中，边界特征点是 时间序列的起始和终止两个端点． 定义 1 转折特征点: 假设包含 n 个数据点的时 间序列为 s = { ( t1，x1 ) ，…，( ti，xi ) ，…，( tn，xn ) } ，其中 xi 为第 i( i = 1，2，…，n) 个数据点在时间 ti 处的取值． 对于数据点 xi ( i = 2，3，…，n － 1) ，若其满足公式( 1) ， 则数据点 xi 为表征时间序列变化的极值转折特征点; 若其满足公式( 2) ，则数据点 xi 为可以反映时间序列 局部变化趋势的非极值转折特征点． { ( xi － 1 ＜ xi ) ∩( xi ＞ xi + 1 ) } ∪{ ( xi － 1 ＞ xi ) ∩( xi ＜ xi + 1 ) } ． ( 1) { ( xi － 1≤xi ) ∩( xi ＜ xi + 1 ) } ∪{ ( xi － 1≥xi ) ∩ ( xi ＞ xi + 1 ) } ∪{ ( xi － 1 ＜ xi ) ∩( xi = xi + 1 ) } ∪ { ( xi － 1 ＞ xi ) ∩( xi = xi + 1 ) } ． ( 2) 为了进一步对时间序列数据进行压缩，在保证时 间序列变化趋势的前提下，选择出最少的特征点，本文 以平均拟合误差作为筛选原则，剔除那些左右两侧趋 势变化不明显的噪声特征点． 定义 2 平均拟合误差: 假设时间序列 s = { ( t1， x1 ) ，…，( ti，xi ) ，…，( tn，xn ) } ( i = 1，2，…，n) 提取了 k 个特征点，根据这些特征点，可以将时间序列划分为 k － 1 段，即 s = { s1，…，sv，…，sk － 1 } = { ( t1，t2，x1，x2 ) ，…， ( tv，tv + 1，xv，xv + 1 ) ，…，( tk － 1，tk，xk － 1，xk ) } ． ( 3) 其中，xv 和 xv + 1 ( v = 1，2，…，k － 1) 分别表示 s 中第 v 段 子时间序列的起始值和终值; tv 和 tv + 1分别表示 s 中第 v 段子时间序列的起始时刻和终止时刻． 采用插补方 法将第 v 段子序列的首尾两点相 连，得 到 拟 合 直 线 fv( t) = kvt + bv，其中: kv = xv + 1 － xv tv + 1 － tv ， ( 4) bv = xv + 1 － tv + 1 tv + 1 － tv ( xv + 1 － xv) ． ( 5) 第 v 段子序列的平均拟合误差如下式所示: εv = ∑ tv+1 t = tv | xvt － fv( t) | tv +1 － tv + 1 ． ( 6) 通过特征点提取策略，提出了一种基于特征点的 时间序列降维算法，基本思路是: 首先提取原始时间序 列中的转折特征点，然后利用平均拟合误差对已选择 特征点进行筛选，在保留原时间序列局部和整体变化 趋势的同时，尽可能多的删除左右侧趋势变化不明显 的噪声特征点，实现时间序列的降维处理． 降维算法 流程如下． 输入: 时间序列 s = { ( t1，x1 ) ，…，( ti，xi ) ，…，( tn， xn ) } ，平均拟合误差阈值 Eth ． 输出: 最终特征点序列 s槇K ． 初始化: sK = ． Step1 将时间序列 s 中的边界特征点 x1 和 xn 添 加到初始特征点序列 sK 中． Step2 从时间序列 s 中依次获得新的数据点 xi ( i = 2，3，…，n － 1) ． ( a) 如果 xi 满足公式( 1) ，则它为极值转折特征 · 5111 ·

·1116 工程科学学报，第39卷，第7期 点，sx=sxU(t,x) ={a…n,…,。-w}={(2,n,2),…, (b)如果x:满足公式(2)，则它为非极值转折特 征点，sx=skU(,x),否则i=i+1,返回(a). (,w,,n),…,(ia-w,a,dant)小. Step3噪声特征点的筛选：假设初始特征点序列 (10) 为sk={(,x),…,(始x）,…,(1,x)},其中m为 其中，x,ew(=1,2,…,m-1)表示中第v段子 特征点个数，x:为初始特征时间序列中第个数据点， 时间序列的起始值和终值；。，i)表示中第v段子 其对应的时间为 时间序列的起始时刻和终止时刻.同理，也可划分 (a)首先将初始特征点序列sk中的数据点xi和 为m-1段，即 x添加到最终特征点序列$x中，且q=2. (b)将特征点序列ss中的数据点x(i=3,4,…, 等={，…，，…，m}={(,2,,2),…, m)依次取一个点添加到最终特征点序列中，令。 (nD,w）,…,(ga-w,n,a-,n)}. (11) 中的新数据点1=x,1=x在中查找其左边两 且公式中相应符号的含义与式(10)类似.则相似 数据点x,-和xg由这三个数据点得到子序列段(，-’ 性度量如下式所示： xx),其中x和x为子序列段在起始时 刻，和终止时刻的数值，则段内平均拟合误差如 sim()= 下式所示： 可县()+)+) Ix:-f()I (12) (7) -1+1 其中，.=一和长，= 山一分别表示 (c)若E≤E,则认为最终特征点序列乐中的xg licn -il w-1 为噪声特征点，将其从中删除，否则q=9+1,i=i+ 序列$和号中第u段拟合直线段斜率；=+D-I 1,返回(b) 和=+w-分别表示序列$和号中第段拟合 Step4输出最终特征点序列sx. 直线段长度：y=|+D-文。|和y=1e+)-|分 2 相似性度量 别表示序列和3中第v段拟合直线段变化幅值.令 等长的时间序列经过降维算法处理后往往变成了 相似性阈值为sim,如果sim(,)≤simu,则时间序 不等长的时间序列，为了实现它们之间的相似性度量， 列$和多是相似的，且数值越小越相似 需要对其进行等长处理.这里采用文献B9]中使用 的方法，将两个序列中的时间点取并集，得到新时间点 3基于多维时间序列形态特征的相似性动 集合，利用所得时间点集合对时间序列重新划分，得到 态聚类算法(SDCTS) 新的等长时间序列.该方法虽然会增加部分计算量， 目前的时间序列聚类方法存在特征点选择不充分 但不会改变降维序列中对原有时间序列变化趋势的描 的问题，这会导致时间序列丢失部分变化趋势，进而影 述，避免对结果产生影响，简单易行. 响相似性聚类的准确性，且这些方法的相似性度量标 时间序列等长处理后，本文根据各时间序列对应 准计算复杂度相对较高，需要人为设置聚类个数，往往 的拟合直线段的斜率、长度和幅值变化的形态特征，提 会导致聚类效率低下.针对上述问题，本文提出了一 出了一种新的时间序列相似性度量标准，其可以计算 种基于多维时间序列形态特征的相似性动态聚类算法 任意时间序列间的相似度，降低计算复杂度，提高算法 (SDCTS),基本思路是：首先利用降维算法提取原始时 效率. 间序列中的特征点，在此基础上，根据时间序列相似性 定义3相似性度量：假定两条不等长特征点时 度量标准，提出无需预先指定聚类个数的时间序列动 间序列经过等长处理后，分别得到长度为m的等长降 态聚类算法.由于时间序列的特殊性，聚类对象是数 维时间序列 据点集而不是以往单个数据点，因此需要对聚类中心 $={(ia,）,…,(i,n),…,(im,）},(8) 进行重新定义. 定义4时间序列聚类中心：假定包含n个时间 ={(），…,(n,),…,(,)}.(9) 序列的时间序列聚类c,={s,…,s,…,s},其中 根据时间点2，a,…,iaw把分为m-1段，即 (i=1,2,…,n)表示第r个聚类c,中第i个时间序列

工程科学学报，第 39 卷，第 7 期 点，sK = sK∪( ti，xi ) ． ( b) 如果 xi 满足公式( 2) ，则它为非极值转折特 征点，sK = sK∪( ti，xi ) ，否则 i = i + 1，返回( a) ． Step3 噪声特征点的筛选: 假设初始特征点序列 为 sK = { ( t'1，x'1 ) ，…，( t'i，x'i ) ，…，( t'm，x'm ) } ，其中 m 为 特征点个数，x'i 为初始特征时间序列中第 i 个数据点， 其对应的时间为 t'i ． ( a) 首先将初始特征点序列 sK 中的数据点 x'1 和 x'2 添加到最终特征点序列 s槇K 中，且 q = 2． ( b) 将特征点序列 sK 中的数据点 x'i ( i = 3，4，…， m) 依次取一个点添加到最终特征点序列 s槇K 中，令 s槇K 中的新数据点 t'q + 1 = t'i，x'q + 1 = x'i，在 s槇K 中查找其左边两 数据点 x'q － 1和 x'q，由这三个数据点得到子序列段( t'q － 1， t'q + 1，x'q － 1，x'q + 1 ) ，其中 x'q － 1和 x'q + 1为子序列段在起始时 刻 t'q － 1和终止时刻 t'q + 1的数值，则段内平均拟合误差如 下式所示: ε = ∑ t'q+1 t = t'q－1 | x't － f'( t) | t'q +1 － t'q －1 + 1 ． ( 7) ( c) 若 ε≤Eth，则认为最终特征点序列 s槇K 中的 x'q 为噪声特征点，将其从 s槇K 中删除，否则 q = q + 1，i = i + 1，返回( b) ． Step4 输出最终特征点序列 s槇K ． 2 相似性度量 等长的时间序列经过降维算法处理后往往变成了 不等长的时间序列，为了实现它们之间的相似性度量， 需要对其进行等长处理． 这里采用文献［8--9］中使用 的方法，将两个序列中的时间点取并集，得到新时间点 集合，利用所得时间点集合对时间序列重新划分，得到 新的等长时间序列． 该方法虽然会增加部分计算量， 但不会改变降维序列中对原有时间序列变化趋势的描 述，避免对结果产生影响，简单易行． 时间序列等长处理后，本文根据各时间序列对应 的拟合直线段的斜率、长度和幅值变化的形态特征，提 出了一种新的时间序列相似性度量标准，其可以计算 任意时间序列间的相似度，降低计算复杂度，提高算法 效率． 定义 3 相似性度量: 假定两条不等长特征点时 间序列经过等长处理后，分别得到长度为 m 的等长降 维时间序列 s槇i = { ( t 槇i1，x槇i1 ) ，…，( t 槇iv，x槇iv) ，…，( t 槇im，x槇im ) } ， ( 8) s槇j = { ( t 槇j1，x槇j1 ) ，…，( t 槇jv，x槇jv) ，…，( t 槇jm，x槇jm ) } ． ( 9) 根据时间点 t 槇i2，t 槇i3，…，t 槇i( m － 1) 把 s槇i分为 m － 1 段，即 s槇i = { s槇i1，…，s槇iv，…，s槇i( m － 1) } = { ( t 槇i1，t 槇i2，x槇i1，x槇i2 ) ，…， ( t 槇iv，t 槇i( v + 1) ，x槇iv，x槇i( v + 1) ) ，…，( t 槇i( m － 1) ，t 槇im，x槇i( m － 1) ，x槇im ) } ． ( 10) 其中，x槇iv，x槇i( v + 1) ( v = 1，2，…，m － 1) 表示 s槇i 中第 v 段子 时间序列的起始值和终值; t 槇iv，t 槇i( v + 1) 表示 s槇i 中第 v 段子 时间序列的起始时刻和终止时刻． 同理，s槇j 也可划分 为 m － 1 段，即 s槇j = { s槇j1，…，s槇jv，…，s槇j( m － 1) } = { ( t 槇j1，t 槇j2，x槇j1，x槇j2 ) ，…， ( t 槇jv，t 槇j( v + 1) ，x槇jv，x槇j( v + 1) ) ，…，( t 槇j( m － 1) ，t 槇jm，x槇j( m － 1) ，x槇jm ) } ． ( 11) 且公式中相应符号的含义与式( 10) 类似． 则相似 性度量如下式所示: sim( s槇i，s槇j ) = 1 3( m － 1) ∑ m －1 v = ( 1 kiv － kjv kiv + k ) jv 2 ( + liv － ljv liv + l ) jv 2 ( + yiv － yjv yiv + y ) jv 2 ． ( 12) 其中，kiv = | x槇i( v + 1) － x槇iv | | t 槇i( v + 1) － t 槇iv | 和 kjv = | x槇j( v + 1) － x槇jv | | t 槇j( v + 1) － t 槇jv | 分别表示 序列 s槇i 和 s槇j 中第 v 段拟合直线段斜率; liv = | t 槇i( v + 1) － t 槇iv | 和 ljv = | t 槇j( v + 1) － t 槇jv | 分别表示序列 s槇i 和 s槇j 中第 v 段拟合 直线段长度; yiv = | x槇i( v + 1) － x 槇iv | 和 yjv = | x槇j( v + 1) － x 槇jv | 分 别表示序列 s槇i 和 s槇j 中第 v 段拟合直线段变化幅值． 令 相似性阈值为 simth，如果 sim( s槇i，s槇j) ≤simth，则时间序 列 s槇i 和 s槇j 是相似的，且数值越小越相似． 3 基于多维时间序列形态特征的相似性动 态聚类算法( SDCTS) 目前的时间序列聚类方法存在特征点选择不充分 的问题，这会导致时间序列丢失部分变化趋势，进而影 响相似性聚类的准确性，且这些方法的相似性度量标 准计算复杂度相对较高，需要人为设置聚类个数，往往 会导致聚类效率低下． 针对上述问题，本文提出了一 种基于多维时间序列形态特征的相似性动态聚类算法 ( SDCTS) ，基本思路是: 首先利用降维算法提取原始时 间序列中的特征点，在此基础上，根据时间序列相似性 度量标准，提出无需预先指定聚类个数的时间序列动 态聚类算法． 由于时间序列的特殊性，聚类对象是数 据点集而不是以往单个数据点，因此需要对聚类中心 进行重新定义． 定义 4 时间序列聚类中心: 假定包含 n 个时间 序列的时间序列聚类 cr = { s r 1，…，s r i，…，s r n } ，其中 s r i ( i = 1，2，…，n) 表示第 r 个聚类 cr 中第 i 个时间序列． · 6111 ·

王玲等：基于多维时间序列形态特征的相似性动态聚类算法 *1117· 计算该聚类中任意时间序列s与其他时间序列s的 Step5输出时间序列聚类结果 相似性度量之和E(s)=∑sim({,s}),相似性度 4 实验结果及分析 量之和最小的时间序列s就是聚类c,的聚类中心. 为了验证本文所提的时间序列动态聚类算法的有 SDCTS算法流程如下. 效性及可行性，实验使用了UCI数据库集及UCR 输入：时间序列集S={s1,…,s,…,5},相似性度 数据库集中的多个时间序列数据集（如表1所示）， 量阈值simh~ 从算法的计算复杂度、聚类个数、聚类正确率、有效性 输出：时间序列聚类结果 指标等角度对SDCTS算法与其他多种不同的算法进 Stepl以集合S中的时间序列s,为聚类中心构 行了对比实验.根据多次实验验证，本文中平均拟合 建初始聚类℃1，完成聚类初始化. 误差阌值E取值范围设置为D.05,0.1],相似性度量 Step2由定义2，假设有w个聚类c,={s,…,s, 阈值simu取值范围设置为D.2,0.25]. …,s}(r=1,2,…,w),其中m表示聚类c,中所含时 实验环境为Intel酷睿i3CPU,4GB内存，320GB 间序列个数.依次从集合S中读入时间序列s(=2, 硬盘，Windows7旗舰版操作系统，使用软件为MAT- 3,…,n)与聚类c,中的第r个时间序列s(i=1,2,…, LAB R2014a m)作等长处理，然后计算相似度之和E(s)= 表1时间序列数据集 豆m(). Table 1 Time series dataset 时间序列数据集 时间序列属性数据量类别数 Step3若min(E(s)）≤(m*sim.）,将时间 Synthetic control 60 600 6 =1,2, 1559 26 序列s添加到具有最小相似性度量的聚类c,中，更新 Isolet5 617 Olive-oil 570 60 c,中的时间序列个数m=m+1,并用下式来更新聚类 Trace 275 200 中心c,然后返回Step2,否则执行Step4. Beef 60 470 5 c9=s, [=arg,min(E(),5∈S, 4.1评价标准 定义5压缩率：对于长度为n的时间序列，在进 i=arg,mn（E(s2), 行数据降维以后得到长度为m的时间序列，则该时间 s.. E'(s)=E'(s;)sim(s;,s)) 序列数据的压缩率如下式所示： s.t. Σim稀，+sim(. Comprasion Ratio=(1-只）×10o%. (16) 定义6聚类正确率：对于包含n条时间序列 (13) Step4对时间序列s与各聚类中心c(r=l,2, 的序列集合S={s,…,5…s}=1,2,…,n),根据 不同时间序列的所属类别，其可以被表示为S={, …,w)进行等长处理，计算欧氏距离d(s,c),通过下 …,h,…h}(i=1,2,…,g),其中，h:表示属于第i类 式找到最小欧氏距离对应的聚类c,· 的时间序列：g表示时间序列类别数.根据不同的聚 r=ag（d(sc9）. (14) 类划分，时间序列集合S可以被表示为S={c1,,c, (a若d(sc>（d(c),则时间序 …,c.}(r=1,2,…,w),其中c,={s,…,s,…si}表 列s不属于任何聚类，需要建立新的聚类，其中，Ic,1 示第r个聚类所含时间序列：w表示聚类个数：1c,1表 表示聚类c,中的时间序列个数. 示聚类c,中所含时间序列个数.根据时间序列不同的 (b)若d(sc)<,-m(d(sc),则将时间 所属类别，时间序列聚类c,可以被表示为C,={s,…, 序列s添加到聚类c,中，并通过公式(15)更新聚类中 sa,…,s},且IsI表示聚类c,中属于第i类的时间序 心c,然后返回Step3. 列个数.则聚类正确率如式(17)所示： = Accuracy (17) j=arg,min(E(s)）, j1,2w◆1 定义7有效性指标Va:对时间序列数据集的 rE'(s;)=E(s)sim (s;,s}) 任意时间序列s,其有效性指标V表示所得时间序列 s.t. Σsim场，+sim(写，小. 聚类中各时间序列与其对应的聚类中心的平均相似性 度量ADIS(V)与各个聚类中心间相似性的最小值 (15) DISe()的比值，如下式所示：

王 玲等: 基于多维时间序列形态特征的相似性动态聚类算法 计算该聚类中任意时间序列 s r i 与其他时间序列 s r j 的 相似性度量之和 Er ( s r i ) = ∑ n j = 1 j≠i sim( { s r i，s r j} ) ，相似性度 量之和最小的时间序列 s r i 就是聚类 cr 的聚类中心 c 0 r ． SDCTS 算法流程如下． 输入: 时间序列集 S = { s1，…，sj ，…，sn } ，相似性度 量阈值 simth ． 输出: 时间序列聚类结果． Step1 以集合 S 中的时间序列 sj 为聚类中心构 建初始聚类 c1，完成聚类初始化． Step2 由定义 2，假设有 w 个聚类 cr = { s r 1，…，s r i， …，s r m } ( r = 1，2，…，w) ，其中 m 表示聚类 cr 中所含时 间序列个数． 依次从集合 S 中读入时间序列 sj ( j = 2， 3，…，n) 与聚类 cr 中的第 r 个时间序列 s r i ( i = 1，2，…， m) 作 等 长 处 理，然 后 计 算 相 似 度 之 和 Er ( sj ) = ∑ m i = 1 sim( { sj ，s r i} ) ． Step3 若 min r = 1，2，…，w ( Er ( sj) ) ≤( m* simth ) ，将时间 序列 sj 添加到具有最小相似性度量的聚类 cr 中，更新 cr 中的时间序列个数 m = m + 1，并用下式来更新聚类 中心 c 0 r ，然后返回 Step2，否则执行 Step4． c 0 r = s r i， s． t． r = arg min r = 1，2，…，w ( Er ( sj ) ) ，sj ∈ S， i = arg min j = 1，2，…m ( Er ( s r i ) ) ， s． t． Er ( s r i ) = Er ( s r i ) + sim( { s r i，sj } ) = ∑ m j = 1 j≠i sim{ s r i，s r j} + sim( { s r i，sj } ) {        ． ( 13) Step4 对时间序列 sj 与各聚类中心 c 0 r ( r = 1，2， …，w) 进行等长处理，计算欧氏距离 d( sj ，c 0 r ) ，通过下 式找到最小欧氏距离对应的聚类 cr ． r = arg min r = 1，2，…，w ( d( sj ，c 0 r ) ) ． ( 14) ( a) 若 d( sj ，c 0 r ) ＞ max i = 1，2，…，|cr | ( d( sj ，c 0 r ) ) ，则时间序 列 sj 不属于任何聚类，需要建立新的聚类，其中，| cr | 表示聚类 cr 中的时间序列个数． ( b) 若 d( sj ，c 0 r ) ＜ max j = 1，2，…，|cr | ( d( sj ，c 0 r ) ) ，则将时间 序列 sj 添加到聚类 cr 中，并通过公式( 15) 更新聚类中 心 c 0 r ，然后返回 Step3． c 0 r = s r j， s． t． j = arg min j = 1，2…m + 1 ( Er ( s r j ) ) ， s． t． Er ( s r j ) = Er ( s r j ) + sim( { s r j，si} ) = ∑ m j = 1 j≠i sim{ s r i，s r j} + sim( { s r j，si} { { ． ( 15) Step5 输出时间序列聚类结果． 4 实验结果及分析 为了验证本文所提的时间序列动态聚类算法的有 效性及可行性，实验使用了 UCI 数据库集［13］ 及 UCＲ 数据库集［14］中的多个时间序列数据集( 如表 1 所示) ， 从算法的计算复杂度、聚类个数、聚类正确率、有效性 指标等角度对 SDCTS 算法与其他多种不同的算法进 行了对比实验． 根据多次实验验证，本文中平均拟合 误差阈值 Eth取值范围设置为［0. 05，0. 1］，相似性度量 阈值 simth取值范围设置为［0. 2，0. 25］． 实验环境为 Intel 酷睿 i3 CPU，4 GB 内存，320 GB 硬盘，Windows 7 旗舰版操作系统，使用软件为 MAT￾LAB Ｒ2014a． 表 1 时间序列数据集 Table 1 Time series dataset 时间序列数据集 时间序列属性 数据量 类别数 Synthetic control 60 600 6 Isolet5 617 1 559 26 Olive-oil 570 60 4 Trace 275 200 4 Beef 60 470 5 4. 1 评价标准 定义 5 压缩率: 对于长度为 n 的时间序列，在进 行数据降维以后得到长度为 m 的时间序列，则该时间 序列数据的压缩率如下式所示: Compression Ｒatio = 1 － ( m ) n × 100% ． ( 16) 定义 6 聚类正确率［15］: 对于包含 n 条时间序列 的序列集合 S = { s1，…，sj ，…sn } ( j = 1，2，…，n) ，根据 不同时间序列的所属类别，其可以被表示为 S = { h1， …，hi，…hg } ( i = 1，2，…，g) ，其中，hi 表示属于第 i 类 的时间序列; g 表示时间序列类别数． 根据不同的聚 类划分，时间序列集合 S 可以被表示为 S = { c1，…，cr， …，cw } ( r = 1，2，…，w) ，其中 cr = { s r 1，…，s r i，…s r |cr | } 表 示第 r 个聚类所含时间序列; w 表示聚类个数; | cr | 表 示聚类 cr 中所含时间序列个数． 根据时间序列不同的 所属类别，时间序列聚类 cr 可以被表示为 cr = { s1r，…， sir，…，sgr } ，且| sir | 表示聚类 cr 中属于第 i 类的时间序 列个数． 则聚类正确率如式( 17) 所示: Accuracy = ∑ w r = 1 |cr | n × max i = 1，2，…g | sir | |cr | ． ( 17) 定义 7 有效性指标 V ［16］: 对时间序列数据集的 任意时间序列 s，其有效性指标 V 表示所得时间序列 聚类中各时间序列与其对应的聚类中心的平均相似性 度量 ADISintra ( V) 与各个聚类中心间相似性的最小值 DISinter ( V) 的比值，如下式所示: · 7111 ·

·1118 工程科学学报，第39卷，第7期 ∑∑sim(s,c) 0(n(q,-1)),空间复杂度为0(n×q):在相似性动 态聚类阶段，因为多维时间序列数据集S划分得到 V= DIS(） n min(sim(c)) (18) (1≤w≤n)个聚类，即在动态聚类中，各时间序列均与 DIS(V) 已存在聚类进行相似性计算，最终建立新的聚类，则所 其中，w表示时间序列聚类个数；i,j表示两个不同的 需时间复杂度为0(w),空间复杂度为0(n×92):综 时间序列聚类：c表示时间序列聚类c,的聚类中心；n 述可以得到，时间序列聚类过程中，SDCTS算法所需时 表示所有时间序列聚类中的序列个数.ADIS()= 间复杂度为0(n)+0(n(g:-1))+0(e2)(1≤9，≤ m,1≤e≤n),空间复杂度为O(n×m).而在最坏的情 一，其数值越小，则序列间的相似性越 况下，即各时间序列降维均得到m个特征点，多维时 间序列数据集S划分得到n个聚类，此时SDCTS算法 大，表明聚类中各时间序列与聚类中心距离越小. 所需时间复杂度为0(n)+0(n(m-1))+0(n2),空 DIS,()=min(sim(c,c)),其数值越大，则各聚类 间复杂度为O(m×n).因此，SDCTS算法的时间复 间的相似性越小，表明各聚类间距离越大。因此所得 杂度主要与选择特征点个数及相似性度量这两方面 有效性指标V数值越小，表明时间序列聚类效果越好 相关，而空间复杂度仅与选择特征点个数相关，且在 4.2计算复杂度分析 最坏情况下等于时间序列数据量，因此，无需增加额 SDCTS算法主要由时间序列降维，相似性动态聚 外其他空间. 类两部分构成.对包含n条时间序列的多维时间序列 4.3降维算法的对比分析 数据集S={s1,52,…,s,…,5},其中s={x,x2,…, 为了验证本文算法的有效性及压缩率参数变化对 xg,…,xm}为数据库中第i个属性的时间序列，假定时 算法效果的影响，采用实际数据集及UCI数据集中的 间序列在降维阶段选择的初始特征点个数为9，(2≤ 部分数据集，在不同压缩率下，对比了SDCTS算法与 41≤m),去除噪声特征点后剩余特征点个数为92(2≤ 分段近似算法（piecewise constant approximation, 42≤k,）,多维时间序列数据集S划分得到w(1≤0≤ PCA)、重要点近似表示算法(important points represen- )个聚类，则在时间序列降维阶段，得到初始特征点 tation approximation,IPRA)和重要趋势转折点算法 序列所需时间复杂度为O(n),空间复杂度为O(n× (important trend turning point,ITTP)的理论优度（见表 m):进行噪声特征点的筛选所需时间复杂度为 2)及拟合误差（见表3）. 表2理论优度对比 Table 2 Theory superiority comparison 理论优度 数据集 压缩率/% PCA可 PRA阿 ITTP SDCTS 5 0.2905 0.3159 0.6764 0.2822 0.2793 0.7664 0.2692 Air Quality 85 0.5017 0.7671 0.4405 90 0.7109 家 0.8250 0.6146 95 0.8191 0.9917 0.7796 15 0.4710 率 0.6858 0.3572 0.4615 0.7442 0.3512 Istanbul Stock Exchange 85 0.6065 0.7712 0.3865 90 0.5700 0.800 0.4563 95 0.8045 1.1107 0.5819 75 0.3143 0.7490 0.3569 80 0.3030 0.7722 0.3169 Dow Jones Index 85 0.2832 0.9054 0.2793 90 0.4603 1.0491 0.4073 95 0.6792 1.5893 0.6492 万 0.3796 0.2883 0.4506 0.2799 80 0.3894 0.4793 0.2374 Japanese Vowels 85 0.4280 0.5249 0.2864 90 0.5998 0.9127 0.5197 95 0.8421 1.0219 0.5633 注：*表示达不到压缩率要求，最小值加粗表示

工程科学学报，第 39 卷，第 7 期 V = ADISintra ( V) DISinter ( V) = ∑ w i = 1 ∑s∈ci sim( s，c 0 i ) n min i，j ( sim( c 0 i ，c 0 j ) ) ． ( 18) 其中，w 表示时间序列聚类个数; i，j 表示两个不同的 时间序列聚类; c 0 i 表示时间序列聚类 ci 的聚类中心; n 表示所有时间序列聚类中的序列个数． ADISintra ( V) = ∑ w i = 1 ∑s∈ci sim( s，c 0 i ) n ，其数值越小，则序列间的相似性越 大，表明聚类中各时间序列与聚类中心距离越小． DISinter ( V) = mini，j ( sim( c 0 i ，c 0 j ) ) ，其数值越大，则各聚类 间的相似性越小，表明各聚类间距离越大． 因此所得 有效性指标 V 数值越小，表明时间序列聚类效果越好． 4. 2 计算复杂度分析 SDCTS 算法主要由时间序列降维，相似性动态聚 类两部分构成． 对包含 n 条时间序列的多维时间序列 数据集 S = { s1，s2，…，si，…，sn } ，其中 si = { xi1，xi2，…， xij，…，xim } 为数据库中第 i 个属性的时间序列，假定时 间序列在降维阶段选择的初始特征点个数为 q1 ( 2≤ q1≤m) ，去除噪声特征点后剩余特征点个数为 q2 ( 2≤ q2≤k1 ) ，多维时间序列数据集 S 划分得到 w( 1≤w≤ n) 个聚类，则在时间序列降维阶段，得到初始特征点 序列所需时间复杂度为 O( n) ，空间复杂度为 O( n × m) ; 进行噪声特征点 的筛选所需时间复杂度为 O( n( q1 － 1) ) ，空间复杂度为 O( n × q1 ) ; 在相似性动 态聚类阶段，因为多维时间序列数据集 S 划分得到 w ( 1≤w≤n) 个聚类，即在动态聚类中，各时间序列均与 已存在聚类进行相似性计算，最终建立新的聚类，则所 需时间复杂度为 O( w2 ) ，空间复杂度为 O( n × q2 ) ; 综 述可以得到，时间序列聚类过程中，SDCTS 算法所需时 间复杂度为 O( n) + O( n( q1 － 1) ) + O( w2 ) ( 1≤q1≤ m，1≤w≤n) ，空间复杂度为 O( n × m) ． 而在最坏的情 况下，即各时间序列降维均得到 m 个特征点，多维时 间序列数据集 S 划分得到 n 个聚类，此时 SDCTS 算法 所需时间复杂度为 O( n) + O( n( m － 1) ) + O( n2 ) ，空 间复杂度为 O( m × n) ． 因此，SDCTS 算法的时间复 杂度主要与选择特征点个数及相似性度量这两方面 相关，而空间复杂度仅与选择特征点个数相关，且在 最坏情况下等于时间序列数据量，因此，无需增加额 外其他空间． 4. 3 降维算法的对比分析 为了验证本文算法的有效性及压缩率参数变化对 算法效果的影响，采用实际数据集及 UCI 数据集中的 部分数据集，在不同压缩率下，对比了 SDCTS 算法与 分 段 近 似 算 法 ( piecewise constant approximation， PCA) 、重要点近似表示算法 ( important points represen￾tation approximation，IPＲA) 和重要趋势转折点算法 ( important trend turning point，ITTP) 的理论优度( 见表 2) 及拟合误差( 见表 3) ． 表 2 理论优度对比 Table 2 Theory superiority comparison 数据集 压缩率/% 理论优度 PCA［5］ IPＲA［6］ ITTP［7］ SDCTS 75 0. 2905 0. 3159 0. 6764 0. 2822 80 0. 2793 * 0. 7664 0. 2692 Air Quality 85 0. 5017 * 0. 7671 0. 4405 90 0. 7109 * 0. 8250 0. 6146 95 0. 8191 * 0. 9917 0. 7796 75 0. 4710 * 0. 6858 0. 3572 80 0. 4615 * 0. 7442 0. 3512 Istanbul Stock Exchange 85 0. 6065 * 0. 7712 0. 3865 90 0. 5700 * 0. 800 0. 4563 95 0. 8045 * 1. 1107 0. 5819 75 0. 3143 * 0. 7490 0. 3569 80 0. 3030 * 0. 7722 0. 3169 Dow Jones Index 85 0. 2832 * 0. 9054 0. 2793 90 0. 4603 * 1. 0491 0. 4073 95 0. 6792 * 1. 5893 0. 6492 75 0. 3796 0. 2883 0. 4506 0. 2799 80 0. 3894 * 0. 4793 0. 2374 Japanese Vowels 85 0. 4280 * 0. 5249 0. 2864 90 0. 5998 * 0. 9127 0. 5197 95 0. 8421 * 1. 0219 0. 5633 注: * 表示达不到压缩率要求，最小值加粗表示． · 8111 ·

王玲等：基于多维时间序列形态特征的相似性动态聚类算法 *1119· 表3拟合误差对比 Table 3 Fitting error comparison 拟合误差 数据集 压缩率/% PCA可 IPRA TTP切 SDCTS 75 0.9946 0.6477 1.5435 0.6153 80 1.3006 1.6595 0.9599 Air Quality 85 1.9239 2.4204 2.0331 90 2.6732 3.1067 2.6342 95 3.5451 3.5408 3.0553 分 1.4609 1.3427 0.9462 80 1.5892 1.4252 1.1347 Istanbul Stock Exchange 85 2.0999 1.4643 1.4051 90 2.1306 1.5051 1.4408 95 2.6994 1.6750 1.6706 75 0.8964 1.4041 0.8871 80 1.2965 1.4551 1.2442 Dow Jones Index 85 1.2467 1.5643 1.4335 90 2.0507 1.6459 1.5958 95 2.7100 2.3372 2.0654 分 1.5216 0.5746 1.2471 0.5968 80 1.8392 1.3514 0.7074 Japanese Vowels 85 2.2281 1.4462 1.2129 90 2.9875 2.4643 2.2941 95 3.7611 1.8666 1.8590 注：*表示达不到压缩率要求，最小值加粗表示 从表2中可以看到，在Air Quality、Istanbul Stock (下三角加粗表示)与欧氏距离度量标准的度量结果 Exchange及轧钢数据集中，算法SDCTS所得的理论优 (上三角未加粗表示)如表5所示 度数值最小，而在Dow Jones Index数据集中，当压缩率 表4与DTW的度量结果对比 为75%~80%时，算法PSA所得理论优度为0.3143 Table 4 Comparison of measurement results with DTW 和0.3030，而算法SDCTS为0.3569和0.3169，虽然数 本文相似 动态弯曲距离度量 值大于前者，但两种算法数值相差较小，而在其他相同 性度量 53 54 556 对比条件下，算法SDCTS所得数值仍然是最小的.在 395.63367.56397.78335.50378.22 Japanese Vowels数据集中，算法SDCTS所得的理论优 0.60 253.02301.51298.05357.87 度数值仍最小.从表3中可以看到，虽然在不同数据 0.13 0.64 一 294.83239.11363.86 集中，均存在拟合误差小于算法SDCTS的情况，但算 54 30.99 43.02230.65 300.12293.34 法SDCTS所得拟合误差仍要小于其他算法，且与最小 值相差较小.此外，在不同的压缩率下，算法SDCTS在 40.6357.79 2970 29.50 277.85 各个数据集中所得理论优度数值和拟合误差的数值范 56 36.4060.35 125430.1112.79 围变化波动不大，表明压缩率参数的变化对算法 表5与欧氏距离的度量结果对比 SDCTS的影响不大. Table 5 Comparison of measurement results with Euclidean distance 4.4不同相似性度量标准的对比分析 本文相似 欧氏距离度量 为验证本文所提相似性度量标准的有效性，该部 性度量 5 35 56 分使用数据集Isolet5中3条类标签为12的时间序列 51 8.1311.2012.3710.8114.14 样本数据，3条类标签为13的时间序列样本数据，分 0.60 10.9210.6710.91 13.94 别对比本文所提相似性度量标准与动态弯曲距离度量 标准及欧氏距离度量标准的度量结果.其中，本文所 0.13 0.64 11.87 10.99 12.29 提相似性度量标准的度量结果（下三角加粗表示）与 54 30.99 43.02 230.65 7.32 12.24 动态弯曲距离度量标准的度量结果（上三角未加粗表 40.63 57.79 2970 29.50 12.79 示)如表4所示，本文所提相似性度量标准的度量结果 6 36.4060.35125430.1112.79

王 玲等: 基于多维时间序列形态特征的相似性动态聚类算法 表 3 拟合误差对比 Table 3 Fitting error comparison 数据集 压缩率/% 拟合误差 PCA［5］ IPＲA［6］ ITTP［7］ SDCTS 75 0. 9946 0. 6477 1. 5435 0. 6153 80 1. 3006 * 1. 6595 0. 9599 Air Quality 85 1. 9239 * 2. 4204 2. 0331 90 2. 6732 * 3. 1067 2. 6342 95 3. 5451 * 3. 5408 3. 0553 75 1. 4609 * 1. 3427 0. 9462 80 1. 5892 * 1. 4252 1. 1347 Istanbul Stock Exchange 85 2. 0999 * 1. 4643 1. 4051 90 2. 1306 * 1. 5051 1. 4408 95 2. 6994 * 1. 6750 1. 6706 75 0. 8964 * 1. 4041 0. 8871 80 1. 2965 * 1. 4551 1. 2442 Dow Jones Index 85 1. 2467 * 1. 5643 1. 4335 90 2. 0507 * 1. 6459 1. 5958 95 2. 7100 * 2. 3372 2. 0654 75 1. 5216 0. 5746 1. 2471 0. 5968 80 1. 8392 * 1. 3514 0. 7074 Japanese Vowels 85 2. 2281 * 1. 4462 1. 2129 90 2. 9875 * 2. 4643 2. 2941 95 3. 7611 * 1. 8666 1. 8590 注: * 表示达不到压缩率要求，最小值加粗表示． 从表 2 中可以看到，在 Air Quality、Istanbul Stock Exchange 及轧钢数据集中，算法 SDCTS 所得的理论优 度数值最小，而在 Dow Jones Index 数据集中，当压缩率 为 75% ～ 80% 时，算法 PSA 所得理论优度为 0. 3143 和 0. 3030，而算法 SDCTS 为 0. 3569 和 0. 3169，虽然数 值大于前者，但两种算法数值相差较小，而在其他相同 对比条件下，算法 SDCTS 所得数值仍然是最小的． 在 Japanese Vowels 数据集中，算法 SDCTS 所得的理论优 度数值仍最小． 从表 3 中可以看到，虽然在不同数据 集中，均存在拟合误差小于算法 SDCTS 的情况，但算 法 SDCTS 所得拟合误差仍要小于其他算法，且与最小 值相差较小． 此外，在不同的压缩率下，算法 SDCTS 在 各个数据集中所得理论优度数值和拟合误差的数值范 围变化 波 动 不 大，表 明 压 缩 率 参 数 的 变 化 对 算 法 SDCTS 的影响不大． 4. 4 不同相似性度量标准的对比分析 为验证本文所提相似性度量标准的有效性，该部 分使用数据集 Isolet5 中 3 条类标签为 12 的时间序列 样本数据，3 条类标签为 13 的时间序列样本数据，分 别对比本文所提相似性度量标准与动态弯曲距离度量 标准及欧氏距离度量标准的度量结果． 其中，本文所 提相似性度量标准的度量结果( 下三角加粗表示) 与 动态弯曲距离度量标准的度量结果( 上三角未加粗表 示) 如表4 所示，本文所提相似性度量标准的度量结果 ( 下三角加粗表示) 与欧氏距离度量标准的度量结果 ( 上三角未加粗表示) 如表 5 所示． 表 4 与 DTW 的度量结果对比 Table 4 Comparison of measurement results with DTW 本文相似 性度量 动态弯曲距离度量 s1 s2 s3 s4 s5 s6 s1 — 395. 63 367. 56 397. 78 335. 50 378. 22 s2 0. 60 — 253. 02 301. 51 298. 05 357. 87 s3 0. 13 0. 64 — 294. 83 239. 11 363. 86 s4 30. 99 43. 02 230. 65 — 300. 12 293. 34 s5 40. 63 57. 79 2970 29. 50 — 277. 85 s6 36. 40 60. 35 1254 30. 11 12. 79 — 表 5 与欧氏距离的度量结果对比 Table 5 Comparison of measurement results with Euclidean distance 本文相似 性度量 欧氏距离度量 s1 s2 s3 s4 s5 s6 s1 — 8. 13 11. 20 12. 37 10. 81 14. 14 s2 0. 60 — 10. 92 10. 67 10. 91 13. 94 s3 0. 13 0. 64 — 11. 87 10. 99 12. 29 s4 30. 99 43. 02 230. 65 — 7. 32 12. 24 s5 40. 63 57. 79 2970 29. 50 — 12. 79 s6 36. 40 60. 35 1254 30. 11 12. 79 — · 9111 ·

·1120 工程科学学报，第39卷，第7期 从表4和表5中可以看到，采用本文相似性度量 Jones Index中，当相似度阈值在区间0.1,0.15]时，聚 标准所得结果中，属于同一类时间序列的度量结果要 类正确率较低，而在其他情况下，具有较高的数值：从 明显小于属于不同类时间序列的度量结果（如时间序 图2中可以看到，在相似度阈值变化的条件下，Air 列s1与时间序列s2,s3的度量结果为0.60,0.13：而时 Quality、Dow Jones Index及轧钢数据集的聚类个数波 间序列51与s4,55,56度量结果为30.99,40.63， 动较大，但是当数值在区间0.2,0.25]时，波动相对 36.40),具有较好的区分度；而在采用动态弯曲距离的 较小：而从图3中可以看到，当相似性阈值在区间 度量结果及采用欧氏距离的度量结果中，属于不同类 D.2,0.25]时，数据集的有效性指标数值变化较为稳 时间序列的度量结果存在小于属于同一类时间序列的 定：因此，当相似度阈值范围在区间0.2,0.25]时，聚 情况（如在表3采用动态弯曲距离的度量结果中，时间 类个数、聚类正确率和有效性指标三者的效果都比 序列s,5,的度量结果为367.56，而时间序列s15的 较好. 度量结果为335.50)，而且所得度量结果数值比较接 4.6聚类正确率对比分析 近，区分度不高，如果阈值设定不当，对聚类结果会产 为验证算法SDCTS的有效性，针对表1中的时间 生较大的影响.因此，可以说明本文所提相似性度量 序列数据集，该实验分别设计了6种不同的聚类方案 标准的有效性 如表6所示（准确线性近似聚合）(piecewise linear ag- 4.5相似性阈值变化对算法SDCTS的影响分析 gregation approximation,PLAA);基于拉普拉斯欧氏点 针对不同的相似性阈值，分析对比了算法的聚类 的经验划分(Laplace Euclidcan points empirical seg- 个数、聚类正确率及有效性指标.其中，图1为聚类个 mentation,LEPES)).与其他方案相比，本文的方案6 数对比，图2为聚类正确率对比，图3为有效性指标 无需人为设置聚类个数，因此为了保证在相同的条件 对比. 下进行对比，首先根据4.5节的相似性阈值分析确定 2 方案6的聚类正确率最高时所对应的压缩率及聚类个 10 0.100.150.20色0.25 8 数，然后根据聚类个数和压缩率相同的条件，分别对比 方案6（算法SDCTS)与其他5种不同聚类方案的聚类 0 正确率，实验结果如表7所示，其中最大值加粗表示 Air Quality Istanbur Dow Jones 轧钢 Stock Index Vowels 数据集 表6聚类方案 Exchange 不同相似度阈值下的数据集 Table 6 Clustering scheme 图1聚类个数对比 聚类方案 方案简述 Fig.I Comparison of cluster numbers 利用本文动态聚类算法直接对原始时间序列进行聚 方案1 类（无降维） 1.2 解1.0 口0.10a0.15a0.20a0.25 利用层次聚类算法对原始时间序列进行聚类（无降 方案2 08 维) 0.6 0.4 利用PLAA团算法对原始时间序列进行降维后实 方案3 0.2 现层次聚类 0 Air Quality Istanbur Dow Jones Japanese 轧钢 利用LEPES回算法对原始时间序列进行降维后实 Stock 方案4 Index Vowels 数据集 现层次聚类 Exchange 不同相似度阈值下的数据集 利用本文降维算法对原始时间序列进行降维后实现 方案5 层次聚类 图2聚类正确率对比 Fig.2 Comparison of clustering accuracy 方案6 利用SDCTS算法对原始时间序列进行聚类 15[ 可以看到，方案6（算法SDCTS)在所有数据集中 12 ■0.10s0.150.200.25 所得聚类正确率均最大，优于其他算法，因此，可以证 9 6 明本文算法SDCTS具有较好的聚类效果：对比于方案 0 1和2，可以看到，在原始时间序列无压缩的情况下，方 Air Quality Istanbur Dow Jones Japanese 轧钢 Stock Index Vowels 案1所得聚类正确率高于方案2，说明本文基于相似 数据集 Exchange 性度量的聚类方法效果较好：对比于方案3、4和5，都 不同相似度阈值下的数据集 是对原始时间序列进行了降维处理，方案5在数据集 图3有效性指标对比 Trace、数据集Beef及数据集Isolet5中效果最好，对于 Fig.3 Comparison of effectiveness index 数据集Synthetic control及数据集Olive-il,方案5所得 从图1中可以看到，在数据集Air Quality及Dow 聚类正确率与其他方案中的最大值相差微小，说明本

工程科学学报，第 39 卷，第 7 期 从表 4 和表 5 中可以看到，采用本文相似性度量 标准所得结果中，属于同一类时间序列的度量结果要 明显小于属于不同类时间序列的度量结果( 如时间序 列 s1 与时间序列 s2，s3 的度量结果为 0. 60，0. 13; 而时 间序 列 s1 与 s4，s5，s6 度 量 结 果 为 30. 99，40. 63， 36. 40) ，具有较好的区分度; 而在采用动态弯曲距离的 度量结果及采用欧氏距离的度量结果中，属于不同类 时间序列的度量结果存在小于属于同一类时间序列的 情况( 如在表3 采用动态弯曲距离的度量结果中，时间 序列 s1，s3 的度量结果为 367. 56，而时间序列 s1，s5 的 度量结果为 335. 50) ，而且所得度量结果数值比较接 近，区分度不高，如果阈值设定不当，对聚类结果会产 生较大的影响． 因此，可以说明本文所提相似性度量 标准的有效性． 4. 5 相似性阈值变化对算法 SDCTS 的影响分析 针对不同的相似性阈值，分析对比了算法的聚类 个数、聚类正确率及有效性指标． 其中，图 1 为聚类个 数对比，图 2 为聚类正确率对比，图 3 为有效性指标 对比． 图 1 聚类个数对比 Fig． 1 Comparison of cluster numbers 图 2 聚类正确率对比 Fig． 2 Comparison of clustering accuracy 图 3 有效性指标对比 Fig． 3 Comparison of effectiveness index 从图 1 中可以看到，在数据集 Air Quality 及 Dow Jones Index 中，当相似度阈值在区间［0. 1，0. 15］时，聚 类正确率较低，而在其他情况下，具有较高的数值; 从 图 2 中可 以 看 到，在相似度阈值变化的条件下，Air Quality、Dow Jones Index 及轧钢数据集的聚类个数波 动较大，但是当数值在区间［0. 2，0. 25］时，波动相对 较小; 而 从 图 3 中 可 以 看 到，当 相 似 性 阈 值 在 区 间 ［0. 2，0. 25］时，数据集的有效性指标数值变化较为稳 定; 因此，当相似度阈值范围在区间［0. 2，0. 25］时，聚 类个数、聚类正确率和有效性指标三者的效果都比 较好． 4. 6 聚类正确率对比分析 为验证算法 SDCTS 的有效性，针对表 1 中的时间 序列数据集，该实验分别设计了 6 种不同的聚类方案 如表 6 所示( 准确线性近似聚合［7］( piecewise linear ag￾gregation approximation，PLAA) ; 基于拉普拉斯欧氏点 的经验划分［9］( Laplace Euclidcan points empirical seg￾mentation，LEPES) ) ． 与其他方案相比，本文的方案 6 无需人为设置聚类个数，因此为了保证在相同的条件 下进行对比，首先根据 4. 5 节的相似性阈值分析确定 方案 6 的聚类正确率最高时所对应的压缩率及聚类个 数，然后根据聚类个数和压缩率相同的条件，分别对比 方案 6( 算法 SDCTS) 与其他 5 种不同聚类方案的聚类 正确率，实验结果如表 7 所示，其中最大值加粗表示． 表 6 聚类方案 Table 6 Clustering scheme 聚类方案 方案简述 方案 1 利用本文动态聚类算法直接对原始时间序列进行聚 类( 无降维) 方案 2 利用层次聚类算法对原始时间序列进行聚类( 无降 维) 方案 3 利用 PLAA［17］算法对原始时间序列进行降维后实 现层次聚类 方案 4 利用 LEPES［9］算法对原始时间序列进行降维后实 现层次聚类 方案 5 利用本文降维算法对原始时间序列进行降维后实现 层次聚类 方案 6 利用 SDCTS 算法对原始时间序列进行聚类 可以看到，方案 6( 算法 SDCTS) 在所有数据集中 所得聚类正确率均最大，优于其他算法，因此，可以证 明本文算法 SDCTS 具有较好的聚类效果; 对比于方案 1 和 2，可以看到，在原始时间序列无压缩的情况下，方 案 1 所得聚类正确率高于方案 2，说明本文基于相似 性度量的聚类方法效果较好; 对比于方案 3、4 和 5，都 是对原始时间序列进行了降维处理，方案 5 在数据集 Trace、数据集 Beef 及数据集 Isolet5 中效果最好，对于 数据集 Synthetic control 及数据集 Olive-oil，方案 5 所得 聚类正确率与其他方案中的最大值相差微小，说明本 · 0211 ·

王玲等：基于多维时间序列形态特征的相似性动态聚类算法 ·1121· 表7聚类方法对比 Table 7 Clustering method comparison 相似性阈值 压缩率/呢 聚类正确率 数据集 聚类个数 (方案1,6) (除方案1,2) 方案1 方案2 方案3方案4 方案5方案6 Synthetic control 0.20 75 > 0.818 0.793 0.735 0.791 0.790 0.935 Olive-oil 0.21 95 6 0.752 0.735 0.707 0.801 0.796 0.808 Trace 0.33 80 6 0.847 0.835 0.848 0.847 0.850 0.897 Beef 0.20 90 6 0.538 0.518 0.515 0.502 0.522 0.557 Isolet5 0.25 80 27 0.704 0.579 0.627 0.693 0.696 0.749 文所提基于特征点的降维方法可以保留时间序列重要 选择其中类标签为12~14的时间序列数据，采用表6 的信息，利于提高聚类效果：对比于方案1和6，可知 中的聚类方案进行对比实验，并对所得聚类结果（各 本文的算法通过时间序列降维处理后可以在一定程度 聚类所含时间序列样本数Num_cust,正确聚类时间序 上提高聚类效果：最后通过对比同一数据集中的结果 列样本数Corr_cust,错误聚类时间序列样本数Er_ 可以发现，方案6的聚类正确率均大于相同条件下的 clust,聚类序列长度Len_seq及聚类正确率Accuracy) 其他方案，说明算法SDCTS可以通过适当的参数选取， 进行统计分析，结果如表8所示.其中数据集Isolet5 来获得较好的聚类正确率，而且相比于其他方案，算法 中类标签为12的时间序列样本数为60，类标签为13 SDCTS无需设定聚类个数，受主观因素影响较小. 的时间序列样本数为59，类标签为14的时间序列样 为进一步验证算法的有效性，针对数据集Isolet5, 本数为60. 表8聚类结果分析对比 Table 8 Clustering results comparison 类标签为12的聚类 类标签为13的聚类 类标签为14的聚类 聚类 Num Corr_ 运行 Num Corr_ Err Nm Comr Err Len_seq Accuracy 方案 时间/s clust clust clust clust clust clust clust clust clust 方案1 68 45 23 49 36 13 62 35 27 617 0.654 100 方案2 56 54 2 44 22 3 79 45 34 617 0.583 160 方案3 59 33 26 40 23 17 80 54 26 329 0.603 140 方案4 56 12 50 24 2 73 西 34 219 0.600 120 方案5 25 20 吃 22 38 94 60 34 284 0.602 80 方案6 64 55 9 52 34 伊 40 23 284 0.716 60 由表8可知，方案3、4、5和6，进行时间序列降维 态特征的相似性动态聚类算法.为了验证算法的性能 处理后形成的聚类序列长度与原始时间序列长度有明 及有效性，文中采用实际数据集和UCI及UCR数据库 显的差异，但方案6（算法SDCTS)的聚类序列长度仅 中的部分数据集进行仿真实验，与其他算法相比，本文 仅大于方案4，而聚类正确率和运行时间明显优于其 所提算法在数据的降维效果和聚类准确性方面均具有 他5种方案，说明该算法不仅能在保留原时间序列主 较好的优势 要信息的基础上实现降维，而且无需人为设置聚类个 数，可以使时间序列动态聚类算法具有较好的聚类 参考文献 效果 5结语 [Li HL,Guo C H.Survey of feature representations and similarity measurements in time series data mining.Appl Res Comput,2013, 本文以特征点提取技术为基础，对时间序列的聚 30(5):1285 类分析进行研究，首先在保证原有时间序列变化趋势 (李海林，郭崇慧.时间序列数据挖掘中特征表示与相似性度 量研究综述.计算机应用研究，2013,30(5)：1285) 的前提下，提出了一种基于特征点的时间序列降维算 2] Wang YT,Wang J D,Chen H Y.Time series dimensionality re- 法，实现了时间序列的降维处理，并以此为基础，考虑 duction and aircraft model recognition in airport-noise.Jilin Uni 降维序列自身形态特征，定义了一种新的时间序列相 Eng Technol Ed,2016,46(4):1202 似性度量标准，进而提出了一种基于多维时间序列形 (王寅同，王建东，陈海燕.时间序列降维及机场噪声中的机

王 玲等: 基于多维时间序列形态特征的相似性动态聚类算法 表 7 聚类方法对比 Table 7 Clustering method comparison 数据集 相似性阈值 ( 方案 1，6) 压缩率/% ( 除方案 1，2) 聚类个数 聚类正确率 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 Synthetic control 0. 20 75 7 0. 818 0. 793 0. 735 0. 791 0. 790 0. 935 Olive-oil 0. 21 95 6 0. 752 0. 735 0. 707 0. 801 0. 796 0. 808 Trace 0. 33 80 6 0. 847 0. 835 0. 848 0. 847 0. 850 0. 897 Beef 0. 20 90 6 0. 538 0. 518 0. 515 0. 502 0. 522 0. 557 Isolet5 0. 25 80 27 0. 704 0. 579 0. 627 0. 693 0. 696 0. 749 文所提基于特征点的降维方法可以保留时间序列重要 的信息，利于提高聚类效果; 对比于方案 1 和 6，可知 本文的算法通过时间序列降维处理后可以在一定程度 上提高聚类效果; 最后通过对比同一数据集中的结果 可以发现，方案 6 的聚类正确率均大于相同条件下的 其他方案，说明算法 SDCTS 可以通过适当的参数选取， 来获得较好的聚类正确率，而且相比于其他方案，算法 SDCTS 无需设定聚类个数，受主观因素影响较小． 为进一步验证算法的有效性，针对数据集 Isolet5， 选择其中类标签为 12 ～ 14 的时间序列数据，采用表 6 中的聚类方案进行对比实验，并对所得聚类结果( 各 聚类所含时间序列样本数 Num_clust，正确聚类时间序 列样本数 Corr_clust，错误聚类时间序列样本数 Err_ clust，聚类序列长度 Len_seq 及聚类正确率 Accuracy) 进行统计分析，结果如表 8 所示． 其中数据集 Isolet5 中类标签为 12 的时间序列样本数为 60，类标签为 13 的时间序列样本数为 59，类标签为 14 的时间序列样 本数为 60． 表 8 聚类结果分析对比 Table 8 Clustering results comparison 聚类 方案 类标签为 12 的聚类 类标签为 13 的聚类 类标签为 14 的聚类 Num_ clust Corr_ clust Err_ clust Num_ clust Corr_ clust Err_ clust Nm_ clust Corr_ clust Err_ clust Len_seq Accuracy 运行 时间/ s 方案 1 68 45 23 49 36 13 62 35 27 617 0. 654 100 方案 2 56 54 2 44 22 22 79 45 34 617 0. 583 160 方案 3 59 33 26 40 23 17 80 54 26 329 0. 603 140 方案 4 56 44 12 50 24 26 73 39 34 219 0. 600 120 方案 5 25 20 5 60 22 38 94 60 34 284 0. 602 80 方案 6 64 55 9 52 34 18 63 40 23 284 0. 716 60 由表 8 可知，方案 3、4、5 和 6，进行时间序列降维 处理后形成的聚类序列长度与原始时间序列长度有明 显的差异，但方案 6( 算法 SDCTS) 的聚类序列长度仅 仅大于方案 4，而聚类正确率和运行时间明显优于其 他 5 种方案，说明该算法不仅能在保留原时间序列主 要信息的基础上实现降维，而且无需人为设置聚类个 数，可以使时间序列动态聚类算法具有较好的聚类 效果． 5 结语 本文以特征点提取技术为基础，对时间序列的聚 类分析进行研究，首先在保证原有时间序列变化趋势 的前提下，提出了一种基于特征点的时间序列降维算 法，实现了时间序列的降维处理，并以此为基础，考虑 降维序列自身形态特征，定义了一种新的时间序列相 似性度量标准，进而提出了一种基于多维时间序列形 态特征的相似性动态聚类算法． 为了验证算法的性能 及有效性，文中采用实际数据集和 UCI 及 UCＲ 数据库 中的部分数据集进行仿真实验，与其他算法相比，本文 所提算法在数据的降维效果和聚类准确性方面均具有 较好的优势． 参 考 文 献 ［1］ Li H L，Guo C H． Survey of feature representations and similarity measurements in time series data mining． Appl Ｒes Comput，2013， 30( 5) : 1285 ( 李海林，郭崇慧． 时间序列数据挖掘中特征表示与相似性度 量研究综述． 计算机应用研究，2013，30( 5) : 1285) ［2］ Wang Y T，Wang J D，Chen H Y． Time series dimensionality re￾duction and aircraft model recognition in airport-noise． J Jilin Univ Eng Technol Ed，2016，46( 4) : 1202 ( 王寅同，王建东，陈海燕． 时间序列降维及机场噪声中的机 · 1211 ·

·1122. 工程科学学报，第39卷，第7期 型识别.吉林大学学报（工学版），2016,46(4)：1202) cally extreme point.Comput Eng,2015,41(5):33 B3]Agrawal R,Faloutsos C.Swami A.Efficient similarity search in (孙雅，李志华.基于区域极值点的时间序列聚类算法.计 sequence databases /International Conference on Foundations of 算机工程，2015,41(5)：33) Data Organization and Algorithms.Chicago,1993:69 [11]Liu Y Z,Pi D C,Chen C M.Similarity measurement based on 4]Han Z M,Chen N,Le J J,et al.An efficient and effective cluste- key points of time series with different length.Comput Eng Appl, ring algorithm for time series of hot topics.Chin Comput,2012, 2014,50(20):1 35(11):2337 (刘永志，皮德常，陈传明.基于关键点的不同长度时间序 (韩忠明，陈妮，乐嘉锦，等.面向热点话题时间序列的有效 列相似性度量.计算机工程与应用，2014,50(20)：1) 聚类算法研究.计算机学报，2012,35(11)：2337) [12]Liu Q,Wang K L,Rao W X.Non-equal time series clustering 5]Keogh EJ,Pazzani M J.A simple dimensionality reduction tech- algorithm with sliding window STS distance.Frontiers Comput nique for fast similarity search in large time series databases / Sci Technol,2015,9(11):1301 PacificAsia Conference on Knowledge Discovery and Data Mining. (刘琴，王恺乐，饶卫雄.不等长时间序列滑窗SS距离聚 Kyoto,2000:122 类算法.计算机科学与探索，2015,9(11)：1301) [6]Yu G Z,Peng H,Hu J S,et al.Hierarchical algorithm to match 03] Asuncion A,Newman D.UCI machine leaming repository [EB/ similar time series data.Comput Eng Appl,2006,42 (23):152 OL].Center for Machine Learning and Intelligent System(2008) (喻高瞻，彭宏，胡劲松，等.时间序列的相似性的分层查询 2017-01-03].http://archive.ics.uci.edu/ml 计算机工程与应用，2006,42(23)：152) [14]Chen Y P,Keogh E.The UCR time series classification archive Liao J,Yu L.Luo H,et al.Time series piecewise linear repre- [EB/OL].NSF Career Axard (2015)[017-01-03].http:/ sentation based on trend transition point.Comput Eng Appl, www.cs.ucr.edu/~eamonn/time series_data/ 2010,46(30):50 [15]Izakian H,Pedrycz W,Jamal I.Fuzzy clustering of time series (廖俊，于雷，罗寰，等.基于趋势转折点的时间序列分段线 data using dynamic time warping distance.Eng Appl Artif Intelli- 性表示.计算机工程与应用，2010,46(30)：50) gence,2015,39:235 8]Luczak M.Hierarchical clustering of time series data with para- [16]Wu D.Research of Sequence Clustering Algorithm Based on metric derivative dynamic time warping.Expert Syst Appl,2016, Weighted Similarity [Dissertation].Qinhuangdao:Yanshan Uni- 62:116 versity,2014 Xie F D.Li Y,Sun Y,et al.Cluster algorithm for time series (吴迪.基于加权相似度的序列聚类算法研究[学位论文] based on key points.Comput Sci,2012,39(3):157 秦皇岛：燕山大学，2014) (谢福鼎，李迎，孙岩，等。一种基于关键点的时间序列聚类 [17]Hung N Q V,Anh D T.An improvement of PAA for dimension- 算法.计算机科学，2012,39(3)：157) ality reduction in large time series databases /Pacific Rim Inter- [10]Sun Y,Li Z H.Clustering algorithm for time series based on lo- national Conference on Artificial Intelligence.Hanoi,2008:698

工程科学学报，第 39 卷，第 7 期 型识别． 吉林大学学报( 工学版) ，2016，46( 4) : 1202) ［3］ Agrawal Ｒ，Faloutsos C，Swami A． Efficient similarity search in sequence databases / / International Conference on Foundations of Data Organization and Algorithms． Chicago，1993: 69 ［4］ Han Z M，Chen N，Le J J，et al． An efficient and effective cluste￾ring algorithm for time series of hot topics． Chin J Comput，2012， 35( 11) : 2337 ( 韩忠明，陈妮，乐嘉锦，等． 面向热点话题时间序列的有效 聚类算法研究． 计算机学报，2012，35( 11) : 2337) ［5］ Keogh E J，Pazzani M J． A simple dimensionality reduction tech￾nique for fast similarity search in large time series databases / / Pacific-Asia Conference on Knowledge Discovery and Data Mining． Kyoto，2000: 122 ［6］ Yu G Z，Peng H，Hu J S，et al． Hierarchical algorithm to match similar time series data． Comput Eng Appl，2006，42( 23) : 152 ( 喻高瞻，彭宏，胡劲松，等． 时间序列的相似性的分层查询． 计算机工程与应用，2006，42( 23) : 152) ［7］ Liao J，Yu L，Luo H，et al． Time series piecewise linear repre￾sentation based on trend transition point． Comput Eng Appl， 2010，46( 30) : 50 ( 廖俊，于雷，罗寰，等． 基于趋势转折点的时间序列分段线 性表示． 计算机工程与应用，2010，46( 30) : 50) ［8］ uczak M． Hierarchical clustering of time series data with para￾metric derivative dynamic time warping． Expert Syst Appl，2016， 62: 116 ［9］ Xie F D，Li Y，Sun Y，et al． Cluster algorithm for time series based on key points． Comput Sci，2012，39( 3) : 157 ( 谢福鼎，李迎，孙岩，等． 一种基于关键点的时间序列聚类 算法． 计算机科学，2012，39( 3) : 157) ［10］ Sun Y，Li Z H． Clustering algorithm for time series based on lo￾cally extreme point． Comput Eng，2015，41( 5) : 33 ( 孙雅，李志华． 基于区域极值点的时间序列聚类算法． 计 算机工程，2015，41( 5) : 33) ［11］ Liu Y Z，Pi D C，Chen C M． Similarity measurement based on key points of time series with different length． Comput Eng Appl， 2014，50( 20) : 1 ( 刘永志，皮德常，陈传明． 基于关键点的不同长度时间序 列相似性度量． 计算机工程与应用，2014，50( 20) : 1) ［12］ Liu Q，Wang K L，Ｒao W X． Non-equal time series clustering algorithm with sliding window STS distance． J Frontiers Comput Sci Technol，2015，9( 11) : 1301 ( 刘琴，王恺乐，饶卫雄． 不等长时间序列滑窗 STS 距离聚 类算法． 计算机科学与探索，2015，9( 11) : 1301) ［13］ Asuncion A，Newman D． UCI machine learning repository［EB / OL］． Center for Machine Learning and Intelligent System( 2008) ［2017--01--03］． http: / /archive． ics． uci． edu /ml ［14］ Chen Y P，Keogh E． The UCＲ time series classification archive ［EB /OL］． NSF Career Award( 2015) ［2017--01--03］． http: / / www． cs． ucr． edu / ～ eamonn /time_series_data / ［15］ Izakian H，Pedrycz W，Jamal I． Fuzzy clustering of time series data using dynamic time warping distance． Eng Appl Artif Intelli￾gence，2015，39: 235 ［16］ Wu D． Ｒesearch of Sequence Clustering Algorithm Based on Weighted Similarity［Dissertation］． Qinhuangdao: Yanshan Uni￾versity，2014 ( 吴迪． 基于加权相似度的序列聚类算法研究［学位论文］． 秦皇岛: 燕山大学，2014) ［17］ Hung N Q V，Anh D T． An improvement of PAA for dimension￾ality reduction in large time series databases / / Pacific Ｒim Inter￾national Conference on Artificial Intelligence． Hanoi，2008: 698 · 2211 ·