0 引言

时间序列聚类方法是数据挖掘领域中重要的研究对象，受到了各个领域的关注，例如，金融学^[1]、气象学^[2]、医药学^[3]、生物学^[4]等。由于时间序列的高维性以及内部存在的大量噪声数据，一些研究者更关注时间序列内部特征的差异性，并提出了大量基于特征的时间序列聚类方法。基于u-shapelets(unsupervised shapelets)的时间序列聚类算法也可视为基于特征的时间序列聚类算法。u-shapelet是基于shapelet^[5-7]的时间序列分类算法在时间序列聚类方向上的扩展延伸，两者都关注时间序列中极具辨识度的局部特征，基于这类局部特征的分类和聚类方法都具有强解释性特点；且u-shapelet更适用于无标签或获取标签困难的场景，能够实现时间序列数据的准确划分，基于u-shapelets的时间序列聚类算法也受到了越来越多的关注^[8-10]。

原始的基于u-shapelets的时间序列聚类算法(BruteForce算法^[8])旨在利用u-shapelets集合构建一个与时间序列数据集相关的距离矩阵，并使用现有的聚类算法，例如k-means算法，对距离矩阵进行聚类。为了保证u-shapelets集合能够构造一个良好的距离矩阵，BruteForce算法将时间序列数据集中的所有子序列作为u-shapelet候选子序列，并对u-shapelet候选集中的所有子序列进行质量评估以找出最佳的u-shapelets集合。假设一个数据集中具有n条时间序列，每条时间序列的长度为m，则一个数据集中的所有子序列的数量为O(nm²)；评估一条子序列质量的计算量为O(nm²)；因此，使用BruteForce算法查找一个u-shapelet的时间复杂度为O(n²m⁴)。

显然，BruteForce算法存在时间复杂度过高的缺点，主要表现为在选中一条子序列作为u-shapelet时，需要评估u-shapelet候选集中的所有子序列的质量，而评估一条子序列的时间复杂度过大。为了解决时间复杂度过高的问题，Zakaria等^[9]使用近似值对时间序列间的距离进行估计，并采用剪枝策略减少u-shapelet候选子序列的评估；Ulanova等^[10]对时间序列数据进行符号聚类近似(Symbolic Aggregate approXimate, SAX)转化，并选取1%的子序列作为u-shapelet候选集。这两种方法均在牺牲聚类准确度的条件下提高了时间序列的聚类效率。而在前人的研究基础上，本文将从提升u-shapelets集合整体质量的角度提高基于u-shapelet的时间序列聚类的准确度，同时保持算法效率基本不变。

选择一个高质量的u-shapelets集合是提高时间序列聚类准确度的最佳手段，集合中的u-shapelets应具备极具辨识度以及彼此互不相似的特点。满足极具辨识度特性的一个u-shapelet在一定程度上能够区分一个类，即一个u-shapelet只在某一类时间序列中普遍存在，而不存在于其他类时间序列中。如图 1为Trace数据集中的两类时间序列，显然图 1中标识的u-shapelet能够有效地区分两类时间序列。子序列的辨识度由子序列的质量来体现，一条子序列的质量越高其辨识度越强。现有的基于u-shapelet的时间序列聚类方法使用Gap值来评估一条子序列的质量。Gap值只通过衡量被子序列划分的两个子集之间的分离度来确认子序列的质量，而本文认为一个好的子序列质量评估方法应该同时考虑被划分的子集之间的分离度以及子集内部的紧密程度。为了确认该想法的准确性，本文研究了不同内部聚类评价指标对u-shapelet提取过程的影响。此外，为了得到最佳的u-shapelets集合，对u-shapelet候选集进行去冗余操作是必不可少的步骤。而现有的去冗余方法过度依赖于前一步的划分操作的结果，若划分不正确将会降低最终聚类结果的准确性，详细分析见2.2节。

由此，为了解决目前质量评估方法和去冗余方法筛选出的u-shapelets集合质量较低而导致聚类准确度不理想的问题，本文提出一种基于最佳u-shapelets的时间序列聚类算法。该算法主要从两个方面完成最佳u-shapelets集合的筛选:首先，研究各类质量评估方法的效用，以选择最佳的质量评估方法来尽可能准确地评估u-shapelet候选集中子序列的质量；其次，采用多元top-k查询技术对u-shapelet候选集进行处理，有效去除冗余子序列并筛选出最佳u-shapelets集合。综上所述，本文的主要工作有：

1) 研究使用不同子序列质量评估方法对基于u-shapelets时间序列聚类结果的影响，并选出最佳的子序列质量评估方法。

2) 结合新的质量评估方法，并引入多元top-k查询技术来去除冗余的u-shapelet候选子序列，得到最佳u-shapelets集合。

3) 将所提出的算法与其他基于u-shapelets的时间序列聚类算法以及经典的时间序列聚类算法进行对比，阐明本文算法在时间序列聚类方面的有效性。

1 u-shapelet相关定义及背景 1.1 相关定义

定义1 时间序列与子序列的距离sdist。假设子序列S的长度为l，时间序列T的长度为n，且l≪n，时间序列T与子序列S之间的距离sdist为：sdist(S, T)=min(dist(S, T_{i, j}))。其中：T_{i, j}为时间序列T中长度为l的子序列，i表示子序列的在时间序列T中的起始位置。

定义2 候选u-shapelet。候选u-shapelet是一个由子序列S和距离阈值d组成的元组〈S, d〉。其中：子序列S是数据集D中任意一条时间序列内任意位置上的子序列；距离阈值d可以将数据集D划分为两个子集D_L和D_R，子集D_L和D_R内包含的时间序列的条数分别表示为n_L、n_R。

定义3 距离矩阵Dist。距离矩阵Dist是u-shapelets集合内每个u-shapelet子序列到数据集D中每条时间序列的距离的集合。假设数据集D中存在N条时间序列，u-shapelets集合内含有m个u-shapelet，则距离矩阵的大小为[N*m]。矩阵每列表示了一个u-shapelet到每条时间序列的距离的集合，表示为dis。

定义4 多元top-k查询^[11]。给定查询对象集合G={v₁, v₂, …, v_n}，每个在集合G中存在的对象v_i均对应一个分值score(v_i)。对于集合中任意两个对象v_i、v_j，给定一个用户自定义的相似度函数sim(v_i, v_j)以及阈值τ，如果存在sim(v_i, v_j)＞τ，则对象v_i与v_j相似，表示为v_i≈ v_j。

给定整数k(1≤k≤ n)，多元top-k查询即是为了从集合G中选出前k个分值最大且互不相似的对象集合C，其中C必须满足以下三个条件：

1) C⊆G且|C|≤k;

2) 对于任意对象v_i∈C及对象v_j∈G-C，满足score(v_i)＞score(v_j)，其中G-C={v|v∈G, v∉C};

3) 对于任意两个对象v_i, v_j∈G且v_i≠v_j，如果存在v_i≈v_j, 则{v_i, v_j}⊄C。

定义5 相似u-shapelet。给定两个候选u-shapelet〈S₁, d₁〉和〈S₂, d₂〉，如果两个候选u-shapelet的距离dist(S₁, S₂)＜min(d₁, d₂)，则两个候选u-shapelet S₁、S₂相似，表示为S₁≈S₂。

定义6 最佳u-shapelets集合。存在u-shapelet候选集Candidates={s₁, s₂, …, s_n}以及整数k(1≤k≤n)，对于u-shapelet候选集中的每条子序列均有其对应的质量Q(s_i)。最佳u-shapelets集合中存在的k个u-shapelet均满足极具辨识度且互不相似的特点，即最佳u-shapelets集合Ush满足以下条件：

1) Ush⊆Candidates且|Ush|≤k;

2) 对于任意候选子序列s_i∈Ush及s_j∈Candidates-Ush，如果存在s_i≈s_j，则Q(s_i)＞Q(s_j)，其中Candidates-Ush={s|s∈Candidates, s∉Ush}；

3) 对于任意两条候选子序列s_i, s_j∈Candidates且s_i≠s_j，如果存在s_i≈s_j，则{s_i, s_j}⊄Ush。

1.2 BruteForce算法

现有的基于u-shapelets的时间序列聚类方法都是在BruteForce算法^[8]的基础上进行提速^[9-10]，算法1中详细介绍了BruteForce算法蛮力搜索u-shapelet的过程。

算法1 U-shapeletsSelection(D, sLen)。

输入 数据集D，子序列长度sLen；

输出 u-shapelets集合Set。

1)  Set=[]       //u-shapelets集合，初始设定为空

2)  while true

3)   Set=[]

4)    for each ts in D       //D中的每条时间序列

5)     Candidates=GenerateAllCandidates(ts, sLen)

6)     for each cand in Candidates

7)      [gap, dt]=computeGap(cand, D)       //评估cand的质量

8)      end for

9)     end for

10)     index1=max(gap)

11)     Set=Candidates(index1)   //选取质量最好的子序列

12)     dis=computeDistance(Candidates(index1), D)

13)     D_L=find(dis＜dt)

14)     if length(D_L)==1, break;

15)     else

16)      index2=max(dis), ts=D(index2, :)

17)      θ=mean(disD_L)+std(disD_L)

18)      D^*=find(dis＜θ), D=D-D^*

19)     end if

20)  end while

21)  return Set

BruteForce算法使用迭代的方式搜索u-shapelets集合。每次迭代过程分为两个阶段：首先，算法1中的4) ~9) 行将数据集D中所有时间序列的子序列作为u-shapelet候选集，并对u-shapelet候选集中的所有子序列进行质量评估；其次，10) ~19) 行选取u-shapelet候选集中质量最好的子序列作为u-shapelet，并使用θ值去除可能存在u-shapelet子序列的时间序列，更新数据集D中的时间序列数据。不断循环整个过程直到在集合D_L的大小为1时结束循环，并返回找到的u-shapelets集合。

BruteForce算法存在以下三个问题：

1) 时间复杂度高。使用滑动窗口的方法产生子序列使u-shapelet候选集过于庞大, 而查找一条u-shapelet需要对u-shapelet候选集中的所有子序列进行质量评估, 且评估一条子序列所需的时间复杂度是O(nm²)(其中:n为时间序列数据集的大小，m为一条时间序列的长度)。

2) 子序列质量评估方法只考虑被子序列划分的两个子集之间的分离度。一个u-shapelet候选子序列利用一个距离阈值d将数据集D划分为两个子集D_L和D_R。BruteForce算法使用computeGap()方法评估两个子集之间的分离度，并使用该分离度作为候选子序列的质量而忽视了子集内部的紧密度。本文认为一个好的u-shapelet应该能使其划分的两个子集之间达到最大分离度，并且子集内部保证高紧密性。

3) θ值过度依赖于被划分的子集D_L。算法1中16) ~18) 行表明BruteForce算法使用θ值去除数据集D中可能存在u-shapelet子序列的时间序列，以此达到去除冗余候选子序列的目的。注意，每查找一个u-shapelet即需要重新评估u-shapelet候选集中所有子序列的质量，θ值将会影响每次循环结束后u-shapelet候选集的大小；而θ值过度依赖于被划分的子集D_L，一旦划分出现偏差，错误的θ值也将会影响其他u-shapelet的搜索，并直接影响到最终时间序列聚类的准确度以及运行时间。具体实验结果见3.2.2节。

为了解决以上三个问题，本文将采用新的u-shapelet质量评估方法并引入多元top-k查询方法对u-shapelet进行搜索，以达到从提升u-shapelets集合整体质量的角度提高时间序列聚类的准确度的目的。

2 本文算法

本章将讨论使用不同内部聚类评价指标作为子序列质量评估方法对基于u-shapelets的时间序列聚类的影响，并找到一个最佳的子序列质量评估方法；其次，本文将引入多元top-k查询方法来去除冗余的u-shapelet候选子序列，并选择一个高质量的u-shapelets集合来提高时间序列聚类准确度。

2.1 子序列质量评估方法研究

一个u-shapelet候选子序列cand能够将时间序列数据集D划分为两个子集D_L和D_R。而一个好的子序列质量评估方法应该同时考虑被子序列cand划分的两个子集间分离度以及子集内部的紧密性。为了找到一个最佳的子序列质量评估方法，本文将从子集间的分离度和紧密性两个角度选择三个常见的内部聚类评价指标进行研究：均方根标准差(Root-Mean-Square STandard Deviation, RMSSTD)^[12]、R平方(R-squared, RS)^[13]以及Ⅰ指标(Ⅰ index)^[14]。

这三个内部聚类评价指标所涉及的定义及符号在基于u-shapelet的时间序列聚类方法中的表示如式(1) ~(3) 所示，注意三个内部聚类评价指标的评估对象是被子序列cand划分的两个子集D_L和D_R。其中：dis表示该子序列cand到数据集D中所有时间序列的距离的集合；n为数据集D的大小；g是距离集合dis的中心；P表示dis的维数，P=1；NC代表子集的个数，NC=2；C_i表示第i个子集；c_i是第i个子集C_i的中心；文中选择使用算数平均值来计算中心g和c_i的值。

1) RMSSTD, 衡量子集内部的紧密性。

$RMSSTD={{\left[ {\sum\limits_{i}{\sum\limits_{x\in {{C}_{i}}}{\|x-{{c}_{i}}{{\|}^{2}}}}}/{\left( P\sum\limits_{i}{{{n}_{i}}-1} \right)}\; \right]}^{1/2}}$

(1)

2) RS, 衡量子集之间分离度的大小。

$RS=1-{\sum\limits_{i}{\sum\limits_{x\in {{C}_{i}}}{\|x-{{c}_{i}}{{\|}^{2}}}}}/{\sum\limits_{x\in \mathit{\boldsymbol{dis}}}{\|x-g{{\|}^{2}}}}\;$

(2)

3) I指标：同时考虑子集间的分离度和子集内部的紧密性。

$I={{\left( \frac{1}{NC}\frac{\sum\limits_{x\in \mathit{\boldsymbol{dis}}}{d\left( x,g \right)}}{\sum\limits_{i}{\sum\limits_{x\in {{C}_{i}}}{d(x,\rm{ }{{c}_{i}})}}}\underset{i,j}{\mathop{\rm{max}}}\,d({{c}_{i}},{{c}_{j}}) \right)}^{P}}$

(3)

以上三个内部聚类评价指标都考虑了数据集内数据的分布情况。RMSSTD衡量了子集内部对象的紧密性，子集内对象的相似程度越高，RMSSTD值越小，划分效果越好；RS直观地描述了子集间的分离度，子集间的分离度越大，RS值越大，划分效果越好；而I同时衡量了子集间的分离度以及子集内对象的紧密程度，I值越大，划分效果越好。

为了研究这三种内部评价指标在基于u-shapelets的时间序列聚类中的有效性，本文研究将从最终的时间序列聚类结果进行判断。本文使用文献[10]中提出的算法SUSh(Scalable U-shapelet)进行实验证明。SUSh算法需要用户自定义u-shapelet的长度。为了实验结果的公平性，在验证四种方法(RMSSTD、RS、Ⅰ指标、Gap)时将采用相同的长度值。表 1中显示了四种评估方法在22个数据集上的具体性能，其中Total Wins一行标明了四种评估方法在22个数据集上的取得最佳效果的数量；表 2描述了22个数据集详细情况(即每个时间序列数据集的大小、数据集中所包含的时间序列的类数、数据集中时间序列的长度)，对每个数据集的时间或精度上表现最佳的值加粗处理。在精度方面，Ⅰ指标在11个数据集上取得了最佳效果，且Ⅰ指标分别在19个数据集上超越了Gap、RMSSTD，并在13个数据集上超越了RS；其次是RS在7个数据集上取得了最佳效果，而RMSSTD的效果最差。从实验结果中可以看出，同时考虑子集内部的紧密性和子集间的分离度取得的效果最好，其次是只考虑子集间的分离度，而只考虑子集内的紧密度的效果最差。在时间方面，本研究中的四种评估方法所用的时间比较相近，四种子序列质量评估方法在运行时间上没有明显的差别。且本文的目的在于如何通过提升u-shapelets集合的整体质量来提高基于u-shapelets的时间序列聚类方法的性能，因此在各类方法的时间相近的情况下本文将选择聚类效果最佳的子序列质量评估方法。如表 1中所示，Ⅰ指标能够在不增加运行时间的情况下有效提升时间序列聚类的准确度，因此本文认为Ⅰ指标能够更好地评估子序列的质量，得到最具辨识度的u-shapelet。

2.2 DivUshapCluster算法

一个好的子序列质量评估方法能在一定程度上提升被选择的u-shapelet的质量。为了进一步提高时间序列聚类的准确率，本文从如何对u-shapelet候选集进行去冗余操作着手，从中选择k个最具辨识度且互不相似的u-shapelet组成最佳的u-shapelets集合。为了解决这个问题，本文引入多元top-k查询方法提出DivUshapCluster算法以查找最佳的u-shapelets集合，并利用u-shapelets集合对应的距离矩阵完成时间序列的聚类操作。多元top-k查询技术^[11]的核心思想是平衡查询结果的相关性和多样性，利用多样化的搜索结果提升用户对查询结果的满意度，即：从相关性和多样性两个方面对查询结果进行考虑找到k个相关度最大且互不相似的对象集合。多元top-k查询技术已经被应用于多个领域，例如文档查询^[15]、Web查询^[16]、图搜索^[17]等。本文提出的DivUshapCluster算法也旨在搜索到k个最具辨识度且互不相似的u-shapelet。

算法2详细描述了具体过程。首先，在第2) 行，本文使用滑动窗口技术对数据集D中的所有时间序列进行预处理，产生固定长度的子序列集合，使用SAX表示每条子序列，并利用文献[10]中的方法选择部分子序列作为u-shapelet候选集。文献[10]表明，这种选取部分子序列的方法能使u-shapelet的发现过程提速两个数量级。在第3) ~5) 行，本文使用Ⅰ指标评估u-shapelet候选集中每条子序列的质量，评估的具体过程在算法3中详细描述。在得到u-shapelet候选集中所有子序列的质量之后，本文将使用多元top-k查询技术搜索k个最具辨识度且互不相似的u-shapelet。在6) ~16) 行，本文方法迭代地查询最佳的u-shapelets集合。在每次迭代过程中，本文方法先从u-shapelet候选集中选取质量最佳的子序列作为u-shapelet，随后将去除u-shapelet候选集中与u-shapelet相似的子序列。不断迭代搜索完k个u-shapelet后结束查询。当产生最佳的u-shapelets集合后，在17) ~21) 行，本文方法计算u-shapelets集合中每个u-shapelet到数据集D中的所有时间序列的距离，组成距离矩阵Dist。最后，在第22) 行，使用传统的聚类方法，比如k-means，对距离矩阵进行聚类，得到时间序列数据集D最终的聚类结果。

算法2 DivUshapCluster(D, sLen, k, p)。

输入 数据集D，子序列长度sLen，u-shapelets集合大小k，聚类个数p；

输出 聚类结果Result。

1)  Ush=∅, i=1, DIS=[]

2)  CandidateUsh= GenerateCandidates(D, sLen)

3)  for i=1 to |CandidateUsh|

4)   assessQuality (CandidateUsh[i], D)

5)  end for

6)  while i＜k

7)   $ush=\underset{ush\in CandidateUsh}{\mathop{\arg \max }}\,ush.\,quality$

8)   Ush.add(ush)

9)   i=i+1

10)   for j=1 to |CandidateUsh|

11)    if (CandidateUsh[j]≈ush)

12)     deletUsh.add (CandidateUsh[j])

13)   end for

14)   CandidateUsh=CandidateUsh-SubUsh

15)   if |CandidateUsh|=0, break;

16)  end while

17)  for cnt=1 to |Ush|

18)   ush=Ush[cnt]

19)   dis=computeDistance (ush, D)

20)   Dist=[Dist dis]

21)  end for

22)  [cluster_centers, Result]=k-means (Dist, p)

23)  return Result

算法3是评估一条u-shapelet候选子序列质量的具体过程。首先，计算候选子序列ush到数据集D中所有时间序列的距离，并对这一系列距离进行排序得到该候选子序列ush对应的距离集合dis。随后，在4) ~17) 行，每个可能的距离阈值d把距离集合dis分为两个子集disD_R和disD_L。注意，假设数据集D中存在N条时间序列，则一个候选子序列对应的距离集合dis中将存在N个距离值，而距离阈值d的可能取值有N-1个。利用I指标衡量每个阈值d划分后的结果，并选择最大的I值作为该候选子序列的质量，并得到该候选子序列对应的元组(ush, d)。

算法3 assessQuality (ush, Data)。

输入 候选子序列ush，数据集D；

输出 候选子序列ush的质量quality。

1)  dis=computeDistance (ush, D);

2)  disSorted=sort (dis);

3)  quality=0;

4)  for l=1 to |dis|-1

5)   d=dis(l);

6)   disD_R=find (disSorted＜d);

7)   disD_L=find (disSorted＞d);

8)   r=|disD_R|/|disD_L|;

9)   if 1/k＜r＜ (1-1/k)

10)    ma=mean (disSorted(Dr));

    mb=mean (disSorted(Dl));

11)    m=mean (disSorted);

12)    U=sum (abs (dis-m))*abs (ma-mb);

13)    B=sum (abs (disD_R-ma))+sum(abs (disD_L-mb));

14)    I=U/(2*B);

15)   end if

16)   if I＞quality, quality=I;

17)  end for

18)  return quality

为了更直观地说明DivUshapCluster算法，图 2展示了DivUshapCluster算法在Coffee数据集上的聚类效果。

Coffee数据集中有56条时间序列，每条时间序列的长度为286，Coffee数据集中的时间序列分为两个类，图 2(a)中展现了两个类中时间序列的代表形状。设定子序列的长度为50，DivUshapCluster算法使用多元top-k u-shapelet查询技术从13 272条子序列中筛选出2条最具代表性且互不相似的子序列组成u-shapelets集合，图 2(a)中标识部分即为DivUshapCluster算法筛选出的两个u-shapelet。图 2(b)中展现的是利用u-shapelets集合得到的Coffee数据集所对应的距离矩阵，从图 2(b)中可以清晰地看出，使用传统的聚类方法，形如k-means方法，可以对距离矩阵进行聚类，并得到很好的时间序列聚类效果。

3 实验结果与分析

为了验证本文提出的DivUshapCluster时间序列聚类算法的有效性，将DivUshapCluster算法、文献[8]中的BruteForce算法、文献[10]中的SUSh算法以及三个经典的聚类算法(k-means、层次聚类、谱聚类)进行对比。

3.1 实验数据集与参数

实验由Window 10操作系统，Intel Core i5-3470 CPU 3.20 GHz, 4 GB内存以及Matlab R2012b作为实验环境。为了阐明DivUshapCluster方法在时间序列聚类问题上的效果，本文选用了美国加州大学滨河分校(University of California Riverside, UCR)的时间序列数据集合^[18]中的22个通用的数据集作为实验对象(表 2中说明了22个时间序列数据集的详细信息)。且根据2.1节的结论，本文中的所有实验将采用Ⅰ指标作为子序列质量的评估手段。

DivUshapCluster算法存在3个参数：时间序列子序列的长度值sLen、u-shapelets集合的大小k以及最终聚类个数p。不同数据集中的时间序列具有不同的长度及特性，难以统一所有时间序列数据集的子序列长度。表 3中sLen列给出了DivUshapCluster算法在22个时间序列数据集上所选用的子序列长度值。最终聚类个数p也将由用户自定义，实验中使用时间序列数据集中实际类的个数作为p的取值。其次，u-shapelets集合的大小k在一定程度上将会影响最终聚类的效果，k值过小将会使找到的u-shapelets集合难以代表数据集中每类时间序列的特性。为了得到最佳的k值，本文研究了在22个数据集上不同k值对整体聚类准确度的影响，图 3展示了k值变化时，在22个数据集上平均聚类准确度的变化趋势。从图 3中可以明显观察到：随着k值的增长，平均聚类准确度在不断攀升，直到k值达到10以后，k值的增长不再影响平均聚类准确度。因此，为了保持实验内容的一致性，将统一采用k=10完成接下来的实验。

3.2 实验结果 3.2.1 准确度对比

为了验证本文提出的DivUshapCluster算法能够有效提高时间序列聚类的准确度，本节将DivUshapCluster算法与文献[8]中的BruteForce算法、文献[10]中的SUSh算法以及三个经典的聚类算法(k-means、层次聚类、谱聚类)进行对比，并使用Rand index作为聚类结果的评价指标，结果如表 3所示，其中Total Wins一行标明了各种聚类算法在22个数据集上的取得最佳效果的数量。

表 3中显示在22个时间序列数据集中本文提出的DivUshapCluster算法分别在17个数据集上优于BruteForce算法、SUSh算法，可以观察到在其中6个数据集上DivUshapCluster算法的准确度较前两者均提升了30%。显而易见，本文提出的DivUshapCluster算法能够有效提高基于u-shapelets的时间序列聚类的准确度。此外，在与经典的聚类算法进行对比上，表 3显示DivUshapCluster算法分别在16、16、14个时间序列数据集上优于层次聚类算法、谱聚类算法以及k-means算法。结果表明，虽然每个算法都能在不同的数据集上取得最佳聚类效果，但是DivUshapCluster算法的整体效果最佳。

3.2.2 运行时间对比

BruteForce算法和SUSh算法都是基于u-shapelets的时间序列聚类方法，而文献[10]中的研究结果表明，SUSh算法在运行速度上比BruteForce算法快两个数量级。因此，本节主要对比SUSh算法与DivUshapCluster算法在22个时间序列数据集上的运行时间，结果如表 4所示，可以看出DivUshapCluster算法在大部分数据集上都略快于SUSh算法。

为了更详细地对比DivUshapCluster与SUSh算法，本文选取UCR时间序列数据集中较大的两个数据集Cricket_X和SwedishLeaf进行对比实验，其中子序列长度均设置为35。图 4展示了运行时间随两个数据集中时间序列的数量变化的曲线，图 5展示了时间序列聚类准确率随两个数据集中时间序列的数量变化的曲线。

图 4(a)中，当Cricket_X数据集中时间序列数量不断增加时，SUSh算法的运行时间从9 s增长到了22 min, 而DivUshapCluster算法则是从15 s增长到了7 min。DivUshapCluster算法运行时间的增长幅度小于SUSh算法的原因是：尽管两个算法都只选取了小部分的时间序列子序列作为u-shapelet候选集，但是SUSh算法和BruteForce算法一样，每提取一个u-shapelet都需要重新对u-shapelet候选集中的子序列进行质量评估，见算法1；而DivUshapCluster算法则只需要对u-shapelet候选集评估一次。此外，SUSh算法中去除冗余子序列的方法也源于BruteForce算法，第2章中讨论了这种不恰当的去冗余方式将会影响到u-shapelet的选取，并最终影响时间序列聚类的时间与准确度。从图 4(b)中也可观察到虽然两个算法在运行时间上十分相近，但是如图 5(b)中所示，DivUshapCluster算法的时间序列聚类准确度远远高于SUSh算法的准确度。

4 结语

为了解决u-shapelets集合质量较低的问题，本文提出一种基于最佳u-shapelets的时间序列聚类算法。该方法选用Ⅰ指标对u-shapelet候选集进行质量评估，并使用多元top-k查询技术从u-shapelet候选集中筛选出最佳u-shapelets集合，利用最佳u-shapelets集合对数据集进行转换并实现后续聚类。通过与传统时间序列聚类算法以及现有的BruteForce算法和SUSh算法进行比较，可以得出本文算法能够在保证整体效率的情况下有效提高时间序列的聚类准确度。在后续的研究中，将考虑如何进一步提升效率。