$k$-shape是一种应用在时间序列数据中的聚类方法^[12]，此算法提出基于时间序列形态相似性的距离量度方式SBD，并采用一种新的聚类中心计算方式SE提取每类聚类中心的时间序列曲线形态，以此完成聚类。

定义1　SBD是一种基于形状的相似性度量方式，在一定程度上弥补了以欧式距离作为相似性评价指标的不足，通过SBD可得到两条时间序列之间的相似度量。具体过程如下：

基于形状的相似性度量方法：$({\rm{dist}},y') = {\rm{SBD}}(x,y)$

输入：两条Z-score标准化后的时间序列x，y；

输出：时间序列x，y的相似性度量dist和$y$相对于$x$的对齐序列$y'$；

计算${\rm{len}} = {2^{2*{\rm{length}}(x) - 1}}$；

对$x$和$y$分别进行快速傅里叶变换，即${F_x} = $$ {\rm{FFT}}(x,{\rm{len}})$，${F_y} = {\rm{FFT}}(y,{\rm{len}})$；

进行逆快速傅里叶变换，计算$x$和$y$之间的交相关序列CC，${\rm{ CC}} = {\rm{IFFT\{ }}{F_x}*{F_y}\}$；

根据系数归一化思想，计算$[{\rm{value,index}}] = $$ \dfrac{{{\rm{CC}}}}{{\left\| x \right\|\left\| y \right\|}}$，value为最大值，index为此时序列$x$和$y$对齐的起始位置；

${\rm{dist}} = 1 - {\rm{value}}$，${\rm{shif}}{\rm{t}} = {\rm{index}} - {\rm{length}}(x)$；

判断shift大小。若shift≥0，则y′$ = [{\rm{zeroes}}(1, $$ {\rm{shift}}), y(1:{\rm{end}} - {\rm{shif}}{\rm{t}})]$，否则y′ = [y (1−shift: end), zeroes(1, −shift)]。

由SBD算法可得到时间序列$x$和$y$之间的相似度量dist。当dist为0时，表示两条序列完全相似。同时，根据对齐的起始位置index，可得到$y$相对于$x$的对齐序列$y'$。

定义 2　SE是从时间序列中提取最具有代表的形态特征，以此进行聚类。根据文献[12]，$k$-shape利用SE方法可以在每种类别的数据中产生一个聚类中心。

基于代表性形态特征的聚类中心提取方法：${\boldsymbol{C}} = {\rm{SE}}({\boldsymbol{X}},{\boldsymbol{R}})$

输入：Z-score标准化后的时间序列集合${\boldsymbol{X}} = $$ [{x_1},{x_2}, \cdots ,{x_n}]$ (其中每条时间序列的长度为$p$)，与X对齐的参考序列向量${\boldsymbol{R}}$；

输出：聚类中心矩阵${\boldsymbol{C}}$；

设立对齐序列矩阵${\boldsymbol{M}}$；

对X中的每条时间序列${x_i}$，计算$[{\rm{dist}},{x'_i}] = {\rm{SBD}} $$ ({\boldsymbol{R}},{x_i})$，并将${x'_i}$加入${\boldsymbol{M}}$；

提取${\boldsymbol{M}}$的主要特征向量，${\boldsymbol{S}} = {{\boldsymbol{M}}^{\rm{T}}}{\boldsymbol{M}}$，${\boldsymbol{Q}} = {\boldsymbol{I}} - \dfrac{1}{p}{\boldsymbol{O}}$(${\boldsymbol{I}}$为单位矩阵，${\boldsymbol{O}}$为全1矩阵)，${\boldsymbol{M}} = {{\boldsymbol{Q}}^{\rm{T}}}{\boldsymbol{SQ}}$；

提取第1特征向量，即${\boldsymbol{C}} = {\rm{Eig}}({\boldsymbol{M}},1)$。

定义 3 　$k$-shape是一种基于时序形状的时间序列聚类方法。该方法首先利用SBD算法进行时间序列之间的相似性度量，获得相似序列。然后使用SE算法从相似序列中提取第一特征向量，作为聚类中心，进而完成聚类。

基于时间序列形态特征的聚类方法：${({{{\bf{IDX}}}},{\boldsymbol{C}})_{}} = k{\rm{ - }}{\rm{shape}}({\boldsymbol{X}},k)$

输入：聚类中心数$k$和Z-score标准化后的同类别的时间序列集${\boldsymbol{X}} = [{x_1},{x_2},\cdots,{x_n}]$，其中${x_i}$表示某一条时间序列；

输出：时间序列集${\boldsymbol{X}}$的类别标签向量IDX和时间序列集${\boldsymbol{X}}$的聚类中心矩阵${\boldsymbol{C}}$；

设置初始迭代次数iter=0，类别标签向量IDX为空向量；

while ${\rm{iter}} < 100$ do

　for $j \leqslant k$ do

　创建一个新的时间序列矩阵${\boldsymbol{X'}}$

　for $i \leqslant n$ do

　if ${\bf{IDX}}({{i}}) = {{j}}$ then

　${\boldsymbol{X'}} = [{\boldsymbol{X'}},{\boldsymbol{X}}(i)]$

${\boldsymbol{C}}(j) = {\rm{SE}}({\boldsymbol{X'}},{\boldsymbol{C}}(j))$

　for $i \leqslant n$do

设置$\min {\rm{dist}} = \infty $

for $j \leqslant k$ do

$[{\rm{dist}},x'] = {\rm{SBD}}({\bf{C}}(j),{\bf{X}}(i))$

if ${\rm{dist}} < {\rm{mindist}}$ then

${\bf{IDX}}({{i}}) = {{j}}$

${\rm{iter}} = {\rm{iter}} + 1$

新分类方法首先通过基于k-shape的聚类中心群方法构建每个类别的聚类中心群，然后结合基于FCM的模糊分类方法实现对时间序列的分类。该方法具有良好的分类性能。

绝大多数的时间序列都存在明显的位移和扭曲，传统的聚类算法不能有效解决这部分时间序列的聚类问题，而k-shape对具有位移和扭曲的时间序列聚类有更好的适用性，可以在一定程度上弥补传统聚类算法以欧氏距离作为相似性度量指标的不足。本文提出一种新的基于k-shape的聚类中心群方法KCG，该方法可得到单个类别的聚类中心群，且有较好的代表性。

图  1  $k$-shape算法优势

如图1所示，通过对时间序列数据集X提取聚类中心，可以看出k-shape提取的聚类中心相比于传统聚类算法k-means更符合数据集X的形态特征，更具有代表性。其算法过程如下。

基于k-shape聚类的聚类中心群方法： ${{\boldsymbol{C}}_a}$ = ${\rm{KCG}}({\boldsymbol{X}},k)$

输入：同一类别的时间序列数据集${\boldsymbol{X}} = [{x_1}, $$ {x_2}, \cdots ,{x_n}]$、X的类别标签A和聚类中心数$k$；

输出：聚类中心矩阵${{\boldsymbol{C}}_a} = [{c_{1{\rm{a}}}},{c_{2a}}, \cdots ,{c_{ka}}]$，${c_{ia}}$表示$A$类别的聚类中心群中的第i个中心代表对象；

1) 根据k-shape聚类算法，将时间序列数据集X划分成$k$类，得到k个聚类中心，即$({\bf{IDX}}_{a},{{\boldsymbol{{C}}}_{a}})$ = $k{\rm{\text{-}shape}}({\boldsymbol{X}},k)$，${\bf{IDX}}_{a}$和${{\boldsymbol{C}}_a}$分别代表X中所有序列的聚类标签向量和聚类中心矩阵；

2) 将步骤1)中得到的聚类中心矩阵${{\boldsymbol{C}}_a}$标记为${{\boldsymbol{C}}_a} = [{c_{1a}},{c_{2a}}, \cdots ,{c_{ka}}]$，代表$A$类别成员序列的聚类中心群。

通过基于k-shape聚类的聚类中心群方法KCG可以得到同类别时间序列集的聚类中心群，该中心群可代表整个类别的时间序列数据形态特征分布情况。

模糊分类相比于传统分类算法的硬划分，更符合时间序列分类的不确定性。FCM算法作为模糊分类的主流算法之一，能在一定程度上解决时间序列数据分类的不确定性问题，是传统硬聚类算法的一种改进。

FCM算法的核心思想是通过极小化目标函数求最优聚类中心^[13]，聚类结果是每一条时间序列对聚类中心的隶属程度，该隶属程度用一个数值来表示。本文提出一种基于FCM的模糊分类方法，通过已知的初始聚类中心群，进行模糊分类，降低初始值对最后分类结果的影响。为了便于理解和讨论模糊分类方法，假设时间序列数据集共分为两类，进一步解释该算法。其具体算法过程如下：

基于FCM的模糊分类算法：${\boldsymbol{D}}$=FCM $({\boldsymbol{Y}},{\boldsymbol{C}}, $${\rm{iter\_max}}) $

输入：包含已知类别$A$和类别$B$的聚类中心矩阵${{\boldsymbol{C}}_{}}$、允许的最大迭代次数${\rm{iter\_max}}$(默认为100)和时间序列测试数据集${\boldsymbol{Y}} = [{y_1},{y_2}, \cdots ,{y_m}]$；

输出：隶属度矩阵${\boldsymbol{D}}$；

1) 将聚类中心矩阵${\boldsymbol{C}}$中$A$类别的聚类中心群标记为${{\boldsymbol{C}}_a}$，$B$类别的聚类中心群标记为${{\boldsymbol{C}}_b}$；

2) 根据FCM模糊聚类算法，将${\boldsymbol{C}}$作为初始聚类中心进行聚类，得到模糊隶属度矩阵${\boldsymbol{D}}$，即${\boldsymbol{D}}$ = ${\rm{FCM}}({\boldsymbol{Y}},{\boldsymbol{C}},{\rm{iter\_max}})$。

通过基于模糊分类的FCM算法得到模糊隶属度矩阵${\boldsymbol{D}}$后，进一步分别计算${y_i}$属于${\boldsymbol{D}}$中$A$类别聚类中心群${{\boldsymbol{C}}_a}$和$B$类别聚类中心群${{\boldsymbol{C}}_b}$的隶属度之和，并判断大小。较大的隶属度之和代表的类标签为${y_i}$所属类别，即可完成分类。

基于FCM的模糊分类算法以k-shape聚类得到的聚类中心群作为初始聚类中心，经过一定次数的迭代，得到模糊隶属度矩阵，依次判断测试时间序列属于各类别标签的聚类中心群的隶属度之和，根据最大隶属度原则确定该测试时间序列属于哪个类别，从而完成时序数据的分类。

考虑到k-shape聚类算法和模糊分类算法的优势，本文将基于k-shape的聚类中心群算法KCG和基于FCM的模糊分类算法结合起来，提出了一种思路更为简单的时间序列分类方法(k-shape and FCM based time series clustering, KFCM)。KFCM算法首先将时间序列训练集各类别的序列成员进行k-shape聚类，分别得到每个类别的聚类中心群，形成已知类标签的聚类中心群。然后，使用基于FCM的模糊分类算法，将测试集序列与已知标签的聚类中心群进行聚类，输出模糊隶属度矩阵。最后，根据隶属度大小原则进一步判断测试集类别。具体算法如下：

基于k-shape的时间序列模糊分类方法：${\boldsymbol{L}} = $$ {\rm{KFCM}}({\boldsymbol{X}},{\boldsymbol{Y}},k,{\rm{iter\_max}})$。

输入：训练集X、测试集Y、默认最大迭代次数iter_max和聚类中心数k；

输出：测试集Y的类标签向量L；

1)根据训练集${\boldsymbol{X}} = [{x_1},{x_2}, \cdots ,x{}_n]$的成员类标签$[{h_1},{h_2}, \cdots ,{h_w}]$，依次利用KCG对类别${h_i}$包含的每个成员进行聚类，得到${h_i}$的聚类中心群${{\boldsymbol{C}}_i}$。将w个聚类中心群合并得到总聚类中心群C，C包含w个类别，共kw个聚类中心；

2)对测试集${\boldsymbol{Y}} = [{y_1},{y_2}, \cdots ,{y_m}]$，使用基于FCM的模糊分类算法，即${\boldsymbol{D}} = {\rm{FCM}}({\boldsymbol{Y}},{\bf{C}},{\rm{iter\_max}})$；

3)根据步骤2)得到的模糊隶属度矩阵${\boldsymbol{D}}$，计算测试集对象${y_j}$属于${\boldsymbol{D}}$中各类聚类中心群的隶属度之和，其较大者的类标签为${y_j}$所属类别${l_j}$；

4)重复步骤3)，获得Y中所有成员的类标签，即${\boldsymbol{L}} = [{l_1},{l_2}, \cdots ,{l_m}]$，其中m为测试集Y包含的时间序列数目。

为了验证本文提出算法的有效性，在30个时间序列数据集上做分类实验。通过实验结果可以验证分类精度的有效性，也可以验证针对存在位移和扭曲特征的时间序列分类，新方法的适用性。

算法代码使用Python 3.7在Anaconda科学计算环境中实现，运行所用计算机的CPU型号为InterCore i5-8250U (1.60 GHz)，RAM为16 GB，操作系统是Windows10 64位(DirectX 12)。

本文采用的数据集是UCR TS Archive 2015，UCR^[14]是时间序列数据集，每个数据集样本都带有样本类别标签，它是目前时间序列挖掘领域重要的开源数据集资源。从UCR数据集中选取了30个训练集，为了验证新方法具有更高的分类质量和性能，这30个数据集在类别、长度和大小上具有明显差异。具体数据集信息如表1所示。

在对训练数据集进行k-shape聚类时，训练集的类别和类别数是已知的，需要用k-shape单独对训练集每一个类别包含的时间序列进行聚类，进而确定各类别的聚类中心群。

在进行参数讨论时，假定训练集共有w个类别，每个类别的聚类中心数都是k，因此共可得到wk个聚类中心，且每个聚类中心群都标记着本类别的标签。本文以Cricket_X数据集为例，说明利用手肘法选取最佳聚类数k的过程。k的取值为1～8 (本文设置上限为8)。如图2所示，随着k增大，SSE的下降幅度会骤减，在k=4之后下降幅度趋于平缓。因此针对Cricket_X数据集，最佳聚类中心数是4。

图  2  $k$值选取对SSE的影响

本节将提出的KFCM算法与SVM^[6]、Bayes^[7]、EAIW^[8]和TLCS^[9]这4种基准分类算法进行比较。为了进一步验证k-shape在提取聚类中心过程中的算法优势，本文利用k-means算法提取各类别的聚类中心群来作为模糊分类的初始聚类中心，同时使用模糊分类方法对时间序列数据集进行分类。该算法称为KMFCM，作为KFCM的对比算法之一。利用以上6种方法对30组UCR数据集进行分类实验，分类错误率如表2所示。利用平均分类错误率、方差和胜出率3个指标评价分类效果，如表3所示。

从表2可知，KFCM算法的平均错误率最低，错误率的总体波动幅度较小，在30个数据集中有9个数据集的错误率最小，有最高的胜出率。为了更好地表现分类结果，本文通过对错误率的两两比较，使用可视化分类比较结果展示，如图3所示。KFCM的分类准确率和胜出率都高于KMFCM，同时，在ShapeletSim、MoteStrain、InlineSkate等数据集上也有较低的分类错误率，这证明了k-shape相比于k-means在聚类过程中有明显优势。KFCM在时间序列测试集上的分类性能优于SVM和Bayes，平均准确率有一定提升。最后，KFCM分类准确率相较于TLCS和EAIW也有一定提高，个别数据集提高效果较为明显。

图  3  分类算法错误率的比较

本文选取4个时间序列数据集，来说明聚类中心数$k$对分类结果的影响，如图4所示。k值对各数据集的分类结果影响不同，对于BeetleFly数据集，错误率最大值和最小值之间差距达到0.23；对于OliveOil数据集，错误率最大值和最小值之间差距为0.06。

图  4  $k$与错误率的关系

由此可知，对于不同的数据集，k对最后分类效果的影响也是不同的。有的数据集如BeetleFly受影响比较大，因此参数k需根据具体数据而设定。

本文分析了30个时间序列训练集中部分时间序列数据的特点，将时间序列训练集按照是否存在明显位移和扭曲的特点分为两大类，计算每一类的平均错误率。横向比较，新方法KFCM在存在明显位移和扭曲特点的时间序列平均错误率要比趋势较为一致的时间序列平均错误率要低；纵向比较，对于存在明显扭曲和位移的时间序列集，新方法KFCM相比其他5个方法的错误率低，分类性能更好。

从图5中看出，InlineSkate、MoteStrain和ShapeletSim这3个时间序列数据集具有较明显的位移和扭曲，故SVM、Bayes和KMFCM在处理此类的数据集分类时存在较大的不足，但KFCM算法表现良好。Symbols、TwoLeadECG和Car这3个时间序列集中同一类时间序列数据上“几乎”不存在位移或者扭曲，故SVM、Bayes和KMFCM在这3个数据集上的分类效果比较理想。图6也表明新方法KFCM在InlineSkate、MoteStrain和ShapeletSim 时间序列数据集上有更低的错误率。

时间序列分类的性能不仅体现在分类效果上，而且也包含了算法的整体时间消耗。为了更直观的比较以上6种分类方法的时间效率，本文随机抽取了WormsTwoClass、Ham、Beef和FaceFour这4个时间序列数据集，进行方法运行时间效率的对比实验。

由图7可知，KFCM方法在4个时间序列数据集上的时间效率比KMFCM、SVM和Bayes低，分类时间较长。但相比于EAIW和TLCS，KFCM方法所花费的时间则相对较少。总体来讲，KFCM的时间效率要高于EAIW和TLCS，低于SVM、Bayes和KMFCM。文献[15]在大型电力负荷时间序列曲线聚类实验中证明k-shape的时间复杂度高于k-means。本文研究的时间序列分类方法主要是通过k-shape提取聚类中心群，该阶段的计算复杂度较高，导致整体算法在大数据环境下的时间效率较低，并不适用于大型数据集。但结合分类质量来看，KFCM可以使用较高的时间效率来获得较好的分类效果。

图  5  部分训练集中label=1的时序数据

图  6  部分数据集错误率比较

图  7  部分数据集时间效率比较

鉴于k-shape在时间序列数据聚类领域的优越性，本文提出了一种新的时间序列分类方法KFCM。该方法首先利用k-shape对时间序列数据训练集中的各个类别包含的成员进行聚类，得到聚类中心群。然后，将聚类中心群作为模糊分类的初始聚类中心，根据隶属度最大原则确定测试时间序列数据的类别标签。通过实验验证，与传统时间序列分类方法相比，新分类方法具有以下优势：1)通过使用k-shape聚类算法，提高了对具有位移和扭曲特征的时间序列数据集分类的适用性，在一定程度上弥补了传统聚类算法以欧氏距离作为相似性指标的不足；2)新分类方法可以利用手肘法确定最佳聚类数，减小参数变化对最终分类结果的影响；3)与传统分类方法相比，新分类方法能够实现更好的分类效果，具有一定的优越性。然而，该方法相较于传统分类方法SVM和Bayes有较高的时间复杂度，在大型数据集上应用效果不佳，这是未来需要进一步研究的工作。