工程科学学报，第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 series ( 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 multidimensional time series，and thus a dynamical clustering algorithm of multidimensional time series is proposed without predefining clustering numbers． The experimental results demonstrate that the SDCTS algorithm improves the clustering accuracy for time series compared 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-1<x)∩(x>x+i)}U{(x-1>x)∩(x<x+)}. 变化趋势信息进行较好的保留，然而降维后会形成不 (1) 等长的时间序列，无法用欧氏距离对不等长数据进行 {(x-1≤x)n(x<)}U{(x-1≥x)n 相似性度量.uczak倒考虑动态时间弯曲(dynamic (>)U(i<x)n(=)}U time warping,DTW)及扩展动态时间弯(derivative dy- {(x-1>x)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 dynamic 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 旗舰版操作系统，使用软件为 MATLAB Ｒ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 representation 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 ·