基于边界距离的时间序列聚类

基于边界距离的时间序列聚类

李俊奎， 王元珍， 李新萍

华中科技大学计算机科学与技术学院(430074）

E-mail ：[email protected]

摘 要：聚类的关键是定义对象之间的相似度或不相似度。提出了一种基于边界的时间序列距离度量D LB _HUST ，较之已存在的基于边界的时间序列距离度量D LB _Keogh ，D LB _HUST 更下界且是对称的距离度量，因而可以应用于时间序列聚类。引入了基于聚类边界的时间序列聚类方法，每次新加入时间序列到簇中后更新簇的边界，使新簇中各个时间序列对簇边界施加影响。实验结果表明，基于边界距离度量D LB _HUST 的时间序列聚类方法优于基于Euclidean 距离和

DTW 距离度量的聚类方法，其是有效可行的。

关键词：时间序列, 聚类, 边界, 对称距离

1. 引 言

时间序列是一种重要的高维数据类型，它是由某个物理量在不同时间点的采样值按照时间先后次序排列而组成的序列。在科学、工程和商业领域具有广泛应用。如：股票市场每天的股票收盘价格数据、每季度乘坐某次航班的旅客数、电话公司每小时的话务量等都是时间序列数据。近年来，对于时间序列数据的挖掘激发了越来越多的研究人员的研究热情[9]。本文主要讨论时间序列数据的聚类。

聚类是根据数据的不同特征，将其分组成为不同的数据类或簇(Cluster)，使得同一簇个体之间的距离尽可能地小，而不同簇个体之间的距离尽可能的大[5]。给定一个数据集

X ={x 1, x 2,..., x n }，将其划分为k

k

个相似的子集簇{C 1, C 2,..., C k }，其中C i ⊆X ，且∪C i

i =1

=X

。聚类的关键

是定义对象之间的相似度或不相似度。目前时间序列之间的相似度研究主要集中在对于时间序列的距离度量上。

Agrawal 等人[1]率先使用等长时间序列的Euclidean 距离度量时间序列间的相似度，后面基于此衍生出DFT [6]，Haar [4]，PCA [7]，PAA [12]，APCA [11]等时间序列以及子序列相似度度量。但是Euclidean 距离度量对于时间序列的突变比较敏感，对于不同步时间序列的相似度度量则会出现较大的偏差。 Berndt等人[2]则引入在语音识别中被广泛使用的DTW 距离作为时间序列的相似度度量距离。 Keogh等人[10]分析了DTW 距离的特性，针对时间序列索引和查询提出了基于时间序列边界的D LB _Keogh 距离，这是目前最好的时间序列度量距离，它下界于

Euclidean 距离和DTW 距离。但是D LB _Keogh 距离不是一种对称的时间序列距离度量，所以并不

适合直接应用于时间序列的聚类。针对这个问题，我们提出了一种对称的基于边界的时间序并且证明了它下界于D LB _Keogh ，从而为基于边界的时间序列距离度量应列距离度量D LB _HUST ，

用于时间序列聚类奠定了基础。

时间序列是一种特殊的高维数据，它具有随时间变化的幅度等特性，当前时间序列聚类中用簇中一个对象或变种来表示簇中心并不能完全反映簇中所有时间序列的影响。于是我们针对时间序列的这些特性，引入了时间序列簇的边界概念，并且证明分处两个时间序列簇的

- 1 -

时间序列的距离大于这两个时间序列簇的簇间距，然后提出了基于边界的时间序列聚类算法，每次有新的时间序列加入到簇中时，则自动更新簇的边界，体现簇中所有时间序列对于新簇的影响。

本文第2节给出基于边界的时间序列距离；第3节讨论基于边界的时间序列聚类算法；第4节给出实验结果及其分析；在第5节对全文的工作进行总结。

2. 基于边界的距离

在这一节中，我们首先介绍Keogh 等人提出的时间序列距离度量D LB _Keogh ，分析其不是对称的距离度量，接着给出对称的基于边界的时间序列距离度量D LB _HUST ，最后讨论该距离度量的重要特性。下面首先给出本文中使用的一些概念。

2.1 相关概念

定义 1(时间序列) 时间序列T =T (1),T (2),...,T (n ) 是一串按照时间顺序观测所得的n 个实数值。

定义2(对称的距离度量) 设D 是一个时间序列距离度量函数，若对∀S , T 为时间序列，有D (S , T ) =D (T , S ) ，则D 是一种对称的距离度量，否则D 是非对称的距离度量。

定义3(时间序列边界) 时间序列S =S (1),S (2),...,S (n ) 的边界分为上边界和下边界，是指在其上滑动大小为2w +1的滑动窗口形成的两个序列U S =U S (1),U S (2),...,U S (n ) 和

L S =L S (1),L S (2),...,L S (n ) ，其中：

U S (i ) =max(S （i −w ),..., S (i ),..., S (i +w )),1≤i ≤n . (1)

L S (i ) =min(S (i −w ),..., S (i ),..., S (i +w )),1≤i ≤n . (2)

由(1)(2)容易得出：

U S (i ) ≥S (i ) ≥L S (i ) ，1≤i ≤n (3)

时间序列边界示意如图1 所示。

图 1 时间序列的上下边界

2.2 一种非对称的时间序列距离度量

下面介绍D LB [10]_Keogh 。

Keogh 等人定义时间序列S 和T 之间的距离为：

- 2 -

D LB _Keogh (S , T ) = (4)

D LB _Keogh 的计算示意如图2所示。

图2 D LB _Keogh 距离度量

定理1 D LB _Keogh 满足Euclidean 距离下界。

证明： 见文献[13]。

定理2 D LB _Keogh 满足DTW 距离下界。 证明： 见文献[10]。 但是，D LB _Keogh 是非对称的距离度量。

定理3 D LB _Keogh 是非对称的距离度量，即∃S , T D LB _Keogh (S , T ) ≠D LB _Keogh (T , S ) 。 证明： 举反例如下：

则有：

U T (i ) =max(T (i −w ),..., T (i ),..., T (i +w )) =2， L T (i ) =min(T (i −w ),..., T (i ),..., T (i +w )) =−2， U S (i ) =max(S (i −w ),..., S (i ),..., S (i +w )) =1， L S (i ) =min(S (i −w ),..., S (i ),..., S (i +w )) =−1。

T (i ) =2 kw ≤i ≤(k +2) w , k ∈N ， −2 (k +2) w ⎧1 kw ≤i ≤(k +w S (i ) =⎨, k ∈N ，

k w i kw 12) − (+

{

(5) (6)

(7) (8) (9) (10) □

由(4)(7)(8)(9)(10)可得：

D LB _Keogh (S , T ) =0, D LB _Keogh (T , S ) >0。

2.3 一种对称的时间序列距离度量

根据聚类的特点，在聚类过程计算距离时需要距离度量满足对称要求。通过式(4)和图2可以看出，D LB _Keogh 不对称的关键原因在于时间序列S 和T 处于不对等地位， 计算时间序列

S 中超出T 上下边界的部分距离，S 中未超出T 上下边界的部分距离计算为0。为了能够使S

和T 处于对等地位，我们比较S 和T 的各自边界，提出一种时间序列边界距离度量方法为：

- 3 -

D LB _HUST (S , T ) (11)

D LB _HUST 的计算示意如图3所示。

图3 D LB _HUST 距离度量

由式(11)和图3可以看出，D LB _HUST 计算时分别计算S 和T 的上下边界超出对方的最小部分，对于在边界内的部分则计算为0。由式(3)可得， D LB _HUST 中三种分支将两时间序列中数据的关系进行了划分，在任何情形下，只会同时满足一种分支条件。

定理4 D LB _HUST 下界于D LB _Keogh ，即

下面分情形计算：

(i ) L S (i ) >U T (i )

∀S , T D LB _HUST (S , T ) ≤D LB _Keogh (S , T )

(12) (13) (14)

证明： 对∀S , T 由(3)我们有：

L S (i ) ≤S (i ) ≤U S (i ),1≤i ≤n . L T (i ) ≤T (i ) ≤U T (i ),1≤i ≤n .

由(13)(14)，我们有

U S (i ) ≥S (i ) ≥L S (i ) >U T (i ) ≥T (i ) ≥L T (i )

，于是有

S (i ) −U T (i ) ≥L S (i ) −U T (i ) >0，所以(S (i ) −U T (i )) 2≥(L S (i ) −U T (i )) 2。

(ii ) L T (i ) >U S (i ) 与(i ) 类似，可得T (i ) >U S (i ) 且(T (i ) −U S (i )) 2≥(L T (i ) −U S (i )) 2。

于是根据(4)(11)，我们可以得到：

D LB _HUST (S , T ) ≤D LB _Keogh (S , T ) 。

□

通过定理4，我们可以看出D LB _HUST 比D LB _Keogh 更下界，而由定理1和定理2， D LB _Keogh 分别下界于Euclidean 和DTW 距离，所以可得D LB _HUST 也下界于Euclidean 和DTW 距离，而且更重要的是，D LB _HUST 是一种对称的基于边界的距离度量。

定理5 D LB _HUST 是对称的距离度量，即∀S , T D LB _HUST (S , T ) =D LB _HUST (T , S ).

证明： 由(11)易证，证明从略。

3. 基于边界的时间序列聚类算法

上一节给出了对称的基于边界的时间序列距离度量方法D LB _HUST ，这一节在此基础上讨论基于边界的时间序列聚类算法。首先我们列出聚类中用到的时间序列簇的相关定义。

- 4 -

3.1 时间序列簇相关定义

定义4(时间序列簇) 时间序列聚类形成的集合，记为C S 。

定义5(时间序列簇边界) 时间序列簇C S ={S 1, S 2,..., S k }边界是指包裹簇中所有时间序列的边界点所组成的曲线。分为上边界和下边界，分别记为U C S 和L C S ，定义为：

U C S =U C S (1),U C S (2),...,U C S (n ) ，其中：

U C S (i ) =max(U S 1(i ), U S 2(i ),..., U S k (i )),1≤i ≤n . (15)

L C S =L C S (1),L C S (2),...,L C S (n ) , 其中：

L C S (i ) =min(L S 1(i ), L S 2(i ),..., L S k (i )),1≤i ≤n . (16)

由(3)(15)(16)可以很容易得到：

定义3和定义5很相似，这为单一时间序列形成一个时间序列簇奠定了基础。 时间序列簇边界示意如图4所示。

U C S (i ) ≥U s m (i ) ≥L s m (i ) ≥L C S (i ) ，1≤m ≤k (17)

图4 时间序列簇的上下边界

下面，我们定义时间序列簇间距离。

则C S 和C T 之间的距离为：

定义6(时间序列簇间距离) 设C S 和C T 分别是两个时间序列簇，

D LB _HUST (C S , C T ) (18)

若C T =∅，则定义D LB _HUST (C S , C T ) =D LB _HUST (C S , ∅) =0.

最近在文献[8]中也提出了与式(18)类似的时间序列集合间距离度量，用于数据流查询中的数据过滤，通过减少比较数据量而提高过滤效率。

从定义6可以看出，时间序列簇间距离是基于簇的边界点的距离，任意簇与空簇的簇间距离为0。又由(15)(16)，簇的边界点来自于簇中所有的时间序列，所以D LB _HUST (C S , C T ) 反映了簇C S 和C T 中时间序列对簇间距离的影响。

定义7(时间序列簇合并) 将时间序列簇C S 和C T 合并成C union ，记为C union =C S ∪C T ，其中：

U C union (i ) =max{U C S (i ), U C T (i )},1≤i ≤n . (19)

L C union (i ) =min{L C S (i ), L C T (i )},1≤i ≤n . (20)

- 5 -

若C T =∅，则定义C union =C S ∪C T =C S ∪∅=C S 。

由定义7可以看出，时间序列簇合并后的边界仍然是由包裹簇中所有时间序列的边界点构成，新加入的时间序列对簇的边界将产生影响。若任意簇与空簇合并，则合并后的簇即为该簇。

下面我们证明一个时间序列边界距离的重要定理。 定理6 给定两个时间序列簇C S 和C T ，∀S ∈C S , T ∈C T 有：

(i ) L C S (i ) >U C T (i )

D LB _HUST (C S , C T ) ≤D LB _HUST (S , T )

(21)

证明： 与定理4的证明类似，我们分情形计算：

由(3)(17)可得L S (i ) ≥L C S (i ) >U C T (i ) ≥U T (i ) ，于是有L S (i ) −U T (i ) >L C S (i ) −U C T (i ) >0， 所以

(L S (i ) −U T (i )) 2>(L C S (i ) −U C T (i )) 2。

(ii ) L C T (i ) >U C S (i ) 类似于(i ) ，可得(L T (i ) −U S (i )) 2>(L C T (i ) −U C S (i )) 2。

又由(11)(18)可得 D LB _HUST (C S , C T ) ≤D LB _HUST (S , T ) □

由定理6可知，分处两个时间序列簇的任意两个时间序列的距离均大于簇间距离，所以时间序列簇间距离能够用于聚类距离衡量，这即是我们基于边界距离的时间序列聚类算法的理论依据。

3.2 基于边界的时间序列聚类算法

下面讨论基于边界距离的时间序列聚类算法。

基于边界距离的时间序列聚类算法的基本思想是：首先时间序列数据库中的所有时间序列都看作是由其上下边界包裹形成的一个簇，然后取出各个簇与结果簇依次比较，如果簇间距离小于给定簇间距离阈值D cluster ，则根据定义7将该簇合并到结果簇中。若没有簇间距离小于D cluster 的结果簇，则将该簇合并到与该簇簇间距离最小的结果簇中。

算法1 基于边界距离的时间序列聚类算法BoundaryDistance-BasedTSClustering 。 输入： 时间序列数据库TSDB ，簇间距离阈值D cluster ，滑动窗口参数w ，聚类最大数目K 。 输出： 聚类结果Clusters ={Cluster 1, Cluster 2,..., Cluster K }。

1) 初始化Clusters ，其中Cluster i ←∅(1≤i ≤K ); // 时间序列聚类结果置空 2) FOR each S ∈TSDB DO // 扫描时间序列数据库 3) 对S 施加大小为2w +1的滑动窗口，按式(1)(2)分别形成U S 和L S ; 4) C S ←{S };U C S ←U S ; L C S ←L S ; // 每个时间序列首先自成一簇

5) min Dist ←MAX _POSSIBLE ;min ClusterNum ←1; //初始化当前最小的簇间距离和簇编号 6) FOR i =1 TO K DO // 与各结果簇进行比较 7) dist =D LB _HUST (C S , Cluster i ); // 计算簇间距离

8) IF dist

- 6 -

12) IF i ==K // 无结果簇与该簇簇间距离小于D cluster 13) Cluster min ClusterNum ←Cluster min ClusterNum ∪C S ; // 将C S 与最小簇间距结果簇合并 14) Return Clusters ={Cluster 1, Cluster 2,..., Cluster K }; // 返回聚类结果

设|TSDB |=n ，则算法第1) 步是初始化聚类结果，时间开销为O (1)，第2)-4) 步首先从各时间序列分解出边界并自成一簇，时间开销为O (n ) ，第6)-13) 步是将簇与各个结果簇进行逐个比较，如果与结果簇的簇间距离小于D cluster ，则将该簇合并到结果簇中，否则记下最小的簇间距离和簇编号。若在结果簇中没有满足簇间距离小于D cluster 的簇，则将该簇合并到与该簇具有最小簇间距离的结果簇中，其中第6)-11) 步最多执行K 次，时间开销为O (nK ) ，第12)-13) 步时间开销为O (n ) ，第14) 步返回聚类结果集，时间开销为O (1)。则算法的总时间开销为：

O (1)+O (n ) +O (nK ) +O (n ) +O (1)=O (nK ).

(22)

设TSDB 中时间序列长度为l ，算法每次为时间序列分配两个大小为l 的向量存储上下边界，故算法的总空间开销为：

O (2l ) =O (l ) 。 (23)

4. 实验研究

4.1 聚类评价标准

聚类结果的评价是一个复杂的问题。以往的方法是通过人的直观经验和观察来解释聚类结果，并给出对结果的评判。 虽然出现过几种评价方法[5]，但是还没有一种统一的方法。我们从聚类的定义和目标出发，给出一种聚类算法的评价标准如下：

p =

∑C

i =1

k

1

i 1≤i

∑

D (s i , s j )

1≤i

D (C i , C j )

(24)

其中分子部分表示在聚类结果中各类中的时间序列的平均距离之和，分母部分表示在聚类结果中各类间距离之和。聚类的目的是将给定数据分成不同的类，使类内的数据比较相似，而类间的数据则比较不相似。故对于给定的数据，p 越小则表示聚类的效果越明显。

另外一个经常用于评价聚类质量的标准是使用侧影宽度(silhouette width)，具体定义见文献[15]。侧影宽度s (i ) 总是落在-1到1之间。如果s (i ) 接近于1，则表明对象i 的聚类效果好; 如果接近于0，则对象i 落在两个簇之间，如果接近于-1则表明对象i 的聚类效果较差，一般认为如果s (i ) 大于0.5，则对对象i 的聚类结果可以接受。

我们同时采用这两种评价标准来分析实验中的聚类结果。

4.2 实验环境和准备

由定理3，D LB _Keogh 是非对称的距离度量，并不适用于时间序列的聚类。我们分别实现了基于Euclidean 距离、DTW 距离和D LB _HUST 距离的时间序列聚类。我们的实验环境是： 操作系统Windows2000Server ， 内存256M ， 硬盘40G 。，CPU PIII-866。实验数据集选用Income 数据集[3]，其中包括美国25个州1929-2004这76年中个人收入的统计数据。以及UCR 时

- 7 -

间序列数据集Synthetic Control Chart Time Series[14]，其中包含600个合成的时间序列数据，每个时间数据长度为60，分为Normal ， Cyclic， Increasing trend ， Decreasing trend ， Upward shift ， Downward shift6种类型。

实验中为了消除因为数据集中具体数值对不同距离度量的影响，首先进行正则化处理，使数据在相同幅值范围内：

X S (i ) =

S (i ) −[(max(S ) −min(S )]2

(25)

[max(S ) +min(S )]/2

其中max(S ) 和min(S ) 分别是序列S 的最大值和最小值，易知X S (i ) ≤1，而且X S 的轮廓与S 相似。

由前面讨论，D LB _HUST 下界于Euclidean 和DTW 距离，所以在各实验中使用三种距离进行聚类时我们根据距离度量的数量级给出簇间距离阈值D cluster 。实际上我们在算法中给出D cluster 是为了避免在算法初始阶段由于时间序列簇与空簇距离为0，而导致前K 个时间序列都自动如果与已经存在的结果簇的距离小于D cluster ，将立即发生归并，归并到空簇中。引入D cluster 后，而不再与空簇比较。

实验结果中计算p 值时，对于计算Euclidean 和DTW 聚类时类之间距离D (C i , C j ) 采用的是类的上下边界的均值形成的曲线。

4.3 实验结果和分析

实验1 对Income 数据集进行聚类。我们在实验中取K =3，w =3，在Euclidean 聚类时采用D cluster =1e −1，在DTW 聚类时采用D cluster =0.4，在D LB _HUST 采用D cluster =1e −4. 实验结果分别如表1和图5、6所示。

图 5 在不同距离度量下聚类的p 值

图 6 各簇的平均侧影宽度

- 8 -

表1三种聚类Income 过程中的侧影距离和簇编号

Euclidean DTW 距离聚类时ND 与其他各对象的距离较大而导致其侧影宽度接近-1， D LB _HUST 距离在聚类初始阶段效果不佳，但总体效果较好。这是由于D LB _HUST 距离聚类时对象间距离较小，要设定最优的D cluster 比较困难所致。

实验2 对Synthetic Control Chart Time Series数据集进行聚类。由于在数据集产生说明中已经预先获知分为6种类型，所以实验中我们取K =6，w =5，在Euclidean 聚类时采用

D cluster =2.5，在DTW 聚类时采用D cluster =3.5，在D LB _HUST 聚类时采用D cluster =1e −2。限于篇幅，

我们只给出p 和各个簇平均侧影距离。实验结果分别如图7和图8所示。

- 9 -

图 7 在不同距离度量下聚类的p 值

图 8 各簇的平均侧影宽度

可以看出， D LB _HUST 在以p 为标准时，与DTW 比较接近，两者都比Euclidean 显著，但若以侧影宽度为标准，则使用D LB _HUST 时各簇的平均侧影宽度标准较之DTW 和Euclidean 更好。其原因是D LB _HUST 不仅更加下界，而且由定理6，给定一定条件的D cluster 后， D LB _HUST 能够灵敏地识别出在这个距离以内的所有时间序列并将其聚类。

5. 结束语

本文主要研究时间序列的聚类问题。针对当前基于边界时间序列距离度量D LB _Keogh 不适合应用于时间序列聚类的问题，提出了一种对称的时间序列距离度量D LB _HUST ，证明D LB _HUST 比D LB _Keogh 更下界。为了表示聚类过程中簇中时间序列对簇的影响，引入了时间序列簇边界概念，证明分处两个时间序列簇的时间序列的距离大于这两个时间序列簇的簇间距，并以此为基础，提出了基于边界距离D LB _HUST 的时间序列的聚类方法。并通过实验结果表明这种聚类方法优于基于Euclidean 和DTW 距离的聚类方法。

致谢 在此，我们向对本文的工作给予支持和建议的同行表示感谢。

参考文献

[1] Agrawal R, Faloutsos C,Swami A. Efficient Similarity search in sequence databases.In: D.Lomet,

eds.Proc.of the 4th Conference on Foundations of Data Organization and Algorithms. Chicago,

Illinois: Springer Verlag, 1994.69-84. [2] Berndt D, Clifford J. Using dynamic time warping to find patterns in time series. AAAI Workshop

on Knowledge Discovery in Databases, 1994. 229-248. [3] Bureau of Economic Analysis: Regional Economic

Accounts.2006. http://www.bea.gov/bea/regional/spi/.

[4] Chan K. Fu A. Yu C. Haar wavelets for efficient similarity search for time-series: with and

without time warping. IEEE Transactions on Knowledge and Data Engineering, 25(3), 2003.686-705. [5] Ding Z J,Yu J. Overview of cluster analysis technique.In:Machine Learning and Its Application.

Wang J, Zhou Z H, Zhou A Y eds.Tsinghua University Press, Beijing, China,2006.59-80(In Chinese).

[6] Faloutsos C, Ranganathan M, Manolopoulos Y. Fast subsequence matching in time-series

databases. In: Proc. of ACM SIGMOD Conf. Minneapolis, 1994. 419-429.

- 10 -

[7] Gavrilov M, Anguelov D, Indyk P, et al.Mining the stock market: Which measure is best? In

Proc. of the Knowledge Discovery and Data Mining, 2000. 487-496.

[8] Li W, Keogh E, Xi X, Herle H, et al. Atomic Wedgie: Efficient Query Filtering for Streaming

Time Series. In the 4th IEEE Int’l Conf. on Data Mining (ICDM2005), Lousiana, New Orleans, 2005.490-497.

[9] Keogh E, Kasetty S. On the need for time series data mining benchmarks: a survey and empirical

demonstration. In the 8th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002.102-111.

[10] Keogh E. Exact indexing of dynamic time warping. Proc. of 28th Int’l Conf. on Very Large

Data Bases (VLDB 2002).Hong Kong, China, 2002.406-417.

[11] Keogh E, Chakrabarti K.Pazzani M.Locally adaptive dimensionality reduction for indexing

large time series databases. In Proc. Of ACM SIGMOD Conference on Management of Data, 2001.151-162.

[12] Keogh E, Chakrabarti K, Pazzani M, Mehrotra S. Dimensionality Reduction for Fast Similarity

Search in Large Time Series Databases. In: 4th Pacific-Asia Conf.Knowledge and Data Mining (PAKDD 2000), Kyoto, Japan, 2000. 122-133.

[13] Keogh E, Palpanas T, Zordan V, Gunopulos D, et al.Indexing large human-motion databases.

In Proc. of 30th Int’l Conf. on Very Large Data Bases (VLDB2004), Toronto, Canada, 2004.780-791.

[14] Keogh E, Folias T. The UCR Time Series Data Mining Archive. Riverside CA.University of

California-Computer Science & Engineering Department, 2002. http://www.cs.ucr.edu/~eamonn/TSDMA/index.html.

[15] Mathsoft, Inc. SPlus-2000 guide to Statistics.

附中文参考文献:

[5] 丁泽进,于剑.聚类分析技术综述.In:机器学习及其应用.王珏,周志华,周傲英 主编.北京:清华大学出版社, 2006.59-80.

Boundary Distance-Based Time Series Clustering

LI Jun-Kui, WANG Yuan-Zhen, LI Xin-Ping

(College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China)

Abstract

The key to cluster is to define the similarity or dissimilarity between objects. A boundary based distance measure between time series, D LB _HUST , is presented to represent the dissimilarity.D LB _HUST is

tighter lower bounding than existing boundary based time series distance measure D LB _Keogh ,moreover D LB _HUST is a symmetry distance measure, hence it is applicable to time

series clustering. A boundary based time series clustering method is proposed, which updates the boundary of the cluster each time a new time series is added into the cluster, the new boundary of the cluster is the outline of all the time series in the cluster. The thorough experiments show that the method outperformsEuclidean and DTW distance based time series clustering method, and is effective and practical.

Keywords ：Time Series, Clustering, Boundary, Symmetry distance

- 11 -

作者简介

李俊奎(1981－),男,江西景德镇人,博士研究生,主要研究领域为数据挖掘,机器学习;

王元珍(1945－),女,教授,博士 生导师,主要研究领域为现代数据库理论与实现,数据挖掘;李新萍(1983－),女,硕士研究生,主要研究领域为数据挖掘。

- 12 -