时间序列数据挖掘中的聚类研究综述

李海林，张丽萍

(1. 华侨大学信息管理与信息系统系 福建 泉州 362021；2. 华侨大学应用统计与大数据研究中心 福建 厦门 361021)

大数据背景下，数据挖掘与分析成为信息处理和知识管理等相关学科领域重点关注的研究对象[1]。在各种复杂数据类型中，广泛存在于金融市场和工业工程等领域的时间序列是一种与时间密切相关的数据，根据变量属性维度的大小其可分为单变量和多变量两种时间序列。相应地，时间序列数据挖掘是从时间序列数据库中发现信息与知识的理论与方法，为帮助政府和企业管理者在相关领域中提供更为可靠的辅助决策与技术支持[2]。时间序列的高维性具有时间维度长、属性变量多、数据体量大等特征，给传统数据挖掘技术的实施带来了极大困扰，在一定程度上阻碍了其在时间序列数据分析领域中的应用与发展。因此，运用数据挖掘技术从高维时间序列数据中发现信息和知识成为了数据分析领域中具有挑战性且最主要的研究方向之一[3]。

传统时间序列数据分析主要基于某种数据分布假设，再选取和制定计量经济模型来对时间序列数据预测分析。在大数据时代，除了需要传统的统计模型对时间序列数据进行预测与分析之外，鉴于时间序列数据具有时间维度长、属性变量多和数据体量大等高维性特征，借助机器学习、模式识别、智能计算和数据挖掘等模型和算法对高维时间序列数据可以进行深入研究与挖掘。聚类是数据挖掘相关研究和应用中非常重要的方法，涉及计算机科学、模式识别、人工智能和机器学习等多个研究领域，同时也常被用于教育、营销、医学和生物信息学等学科，在大数据、人工智能和机器人等热点领域有突出贡献[4]。如在大规模群体决策中，聚类分析被用于划分大规模群体、处理非合作行为和社区发现等[5-6]。聚类分析也是一项重要而且基础的工作，其过程包括了时间序列的数据表达、特征提取、相似性度量以及具体聚类模型与算法等。为此，本文对时间数据挖掘中的聚类分析进行综述研究，首先介绍了目前时间序列聚类方法分类，然后分别从特征表示、相似性度量、聚类算法和簇原型等方面进行国内外研究状况分析，最后分析了目前研究存在的不足，同时给出了未来的研究方向。

1 时间序列聚类

时间序列聚类研究大体上可分为3 种类型[7]，分别为整体时间序列聚类、子序列聚类和时间点聚类。整体时间序列聚类把每条时间序列视为数据对象，对具有共同数据特征的时间序列对象进行聚类。它常以相似性度量为基础，结合数据降维和特征表示来找出两个数据对象之间的共性，进而实现时间序列数据的簇划分。

如图1 所示，分别使用主成分分析(principal component analysis, PCA)和 对 称 性 主 成 分 分 析(asynchronism-based principal component analysis,APCA)[8]对10 条Synthetic_Control 时间序列数据进行特征表示，并使用相应的相似性度量方法结合层次聚类实现整体时间序列的聚类分析。

图1 两种方法对整体时间序列数据层次聚类

子序列聚类通常指对一条时间较长的一元序列利用滑动窗和矢量量化等方法进行子序列划分，并使用相应聚类方法实现分段子序列的聚类。子序列聚类方法可以有效地发现较长时间序列中的频繁模式和异常片段，也能够发现不同时间序列数据之间存在的共同模式和关联关系。

时间点聚类则是从时间点和相应数据点两个角度出发来研究基于时间点的数据对象之间的近似性，把具有较高相似性的时间点聚合成同一簇，进而实现时间序列数据点划分[7-8]。该方法能够用来对一条时间序列进行分段划分，实现数据降维和特征表示，与传统时间序列分割表示方法相比，具有较高的时间效率。

目前国内外学者对于子序列聚类的研究目前尚存一些争议[9]。鉴于整体时间序列聚类的模型与算法可直接或间接应用于子序列聚类和时间点聚类，大部分集中于对整体时间序列聚类的研究。主要研究方法有：1) 传统聚类方法，如K-Means、模糊聚类和基于密度的等聚类方法，根据时间序列的数据特征定制合适的距离度量函数，实现原始时间序列数据聚类[10]；2) 对时间序列数据通过特征空间转化[11]，将原始时间序列数据转化为另一特征空间的数据对象，再选取合适的传统聚类方法在特征空间中对数据对象进行聚类[12]；3) 通过时间序列数据的多分辨率解析，在不同分辨率视角下结合不同方法进行聚类分析，提升传统方法的聚类效果[13]。

2 国内外研究现状

针对时间序列数据挖掘中的聚类分析主要集中在整体时间序列的聚类研究，通常整体时序数据聚类方法也可用于子序列聚类中，使得整体时间序列聚类显得更为重要。由于时间的连续性，对时间点聚类的研究相对较少。

如图2 所示，重点从整体时间序列聚类的视角来分析时间序列数据挖掘领域中的聚类研究状况。有关整体时间序列聚类的国内外相关文献主要从4 个方向对其进行了相关理论和方法的研究，分别为数据降维与特征表示、相似性度量、聚类模型与算法和簇原型，采用不同的技术手段和理论方法从这4 个方向进行分析与探究。

图2 时间序列数据聚类的主要研究问题

2.1 研究地位

目前已经出现了不少成熟经典的聚类模型与算法，但一些基本问题始终是该领域的研究重点，其中包括不同结构特征数据的相似性度量、高维数据的降维与特征表示、基于噪声数据的聚类鲁棒性、大规模数据集聚类算法的有效性选择等[14]。高维时间序列数据与传统数据不同，随着时间维度的增加，各时间点产生的数据具有不确定性[15]，在聚类分析过程中除了要解决因高维性给有关模型和算法带来精度不高和复杂度过大等问题，还需要考虑动态实时、不确定性和高噪声等其他特征因素给聚类结果带来的影响。另外，时间序列聚类结果所产生的模式通常也被用于其他时间序列挖掘任务和方法中，如时间序列的数据降维与特征表示、模式匹配、关联分析、分类、数据可视化等[16-18]，使得整个时间序列数据挖掘任务具有更为出色的效果。

时间序列数据挖掘包括特征表示、相似性度量、聚类、分类、关联规则、模式发现和可视化等重要任务和关键技术[2]。聚类分析与特征表示和相似性度量方法一样，通常作为其他时间序列挖掘任务的子程序或中间件，以便更好地提升相关挖掘技术的性能和质量[10]。时间序列聚类分析研究的另一个重要动力来自于实际应用领域中超大容量数据的获取，包括经济金融、电子信息、医疗行业、航空航天、天体气象等。这些与时间相关的高维数据隐藏着大量有价值的信息和知识，需要通过聚类分析对时间序列数据进行模式发现，进而有针对性地对相关模式和知识进行处理，以便数据科学家和管理者进行技术分析和决策支持。

由于时间序列数据自身存在一定的特殊性，使得数据降维与特征表示以及相似性度量方法成为其他时间序列数据挖掘方法研究的基础任务，其质量好坏在一定程度上影响其他挖掘任务的效果[19]。文献[20]对单变量和多变量两种时间序列数据的特征表示和相似性度量进行了较为系统的研究，研究成果能较好地改善和提高有关挖掘技术和方法的质量和效率。同时，聚类自身也可用来发现时间序列中的频繁模式或时间序列数据库中的奇异模式，甚至作为一种降维手段来实现数据特征表示[21]。另外，在大部分情况下，时间序列聚类通常是建立在特征表示和相似性度量基础之上的一种机器学习方法，实现获得较高质量的聚类分析结果[10]。

2.2 数据降维与特征表示

数据降维和特征表示是高维时间序列数据挖掘中至关重要的过程，其目的是对高维数据进行数据变换，在低维空间下使用相应的特征来表示原始时间序列的关键信息，进而提高时间序列聚类算法的效率和质量。目前，已有一些较为成熟的方法对一元时间序列进行特征表示，包括矢量量化[22]、分段表示[23]、聚合符号化表示[24]、多项式回归参数[25]和模型参数[26]等。鉴于多元时间序列数据的广泛性和重要性，主要从序列的时间和属性两个维度进行数据降维，代表性方法有基于主成分分析的[27]、基于独立成成分的[12]、基于奇异值分解的[28]等。

将时间序列数据转化为复杂网络方法，再使用复杂网络的拓扑结构特征来表示原始时间序列数据也是目前较为常用的一种时间序列数据特征表示方法，通常包括基于可视图、基于相空间重构法、基于递归法和基于符号模式等建网方法[29]。特别地，可视图可以将周期时间序列、随机时间序列和分形时间序列分别转化为规则网络、随机网络和无标度网，其拓扑结构能够较好地反映时间序列的数据特征。若时间序列中两个数据所表示的直方条能够画一条不与任何中间直方条相交的直线，则此直方条组所对应的数据组之间可以形成网络连边，即：

基于数据降维和特征表示的时间序列聚类主要从基于形态的、基于特征的和基于模式的等方面来研究。基于形态的时间序列聚类[30]主要从数据形态变化的角度来匹配序列之间的相似性，包括同步形态和异步形态，进而聚类算法可将具有相似性形态变化特征的时序对象归入同一簇。基于特征的时间序列聚类[31]将时间序列进行数据转化，在低维的特征空间中进行时间序列的聚类分析。基于模式的时间序列聚类[10]则是将原始时间序列转化为模型参数，结合传统聚类算法实现时间序列的模式识别。

2.3 相似性度量

相似性度量也是时间序列聚类算法中必不可少的中间件，基于相似性度量的聚类算法有时间序列数据划分聚类、层次聚类和基于密度的聚类等。文献[32]提出了时间序列相似性搜索过程中距离度量的理论基础，要求设计的快速近似度量函数满足真实距离的下界性，以免相似性检索时发生漏报情况。

目前存在各种不同的时间序列距离度量方法[19]，最典型的两种方法为欧氏距离(Euclidean distance,ED)和动态时间弯曲方法(dynamic time warping,DTW)[11,33-34]。欧氏距离通常要求两条时间序列具有相等的长度，即对于两条时间序列A与B，有：

如图3 所示，欧氏距离对时间序列进行了同步硬性度量，动态时间弯曲方法根据最优化匹配路径，实现异步相似形态的度量。前者满足三角不等式，比较适用于时间序列的相似性搜索，但其结果易受异常数据点的影响，且无法度量不等长时间序列之间的相似性；后者利用动态规划方法从两条时间序列中找到一条距离最优的弯曲路径，使具有相似形态的异步数据相互匹配，进而实现不等长时间序列之间的距离度量，但其平方阶的时间复杂度限制了其在高维时间序列数据聚类过程中的应用。

图3 欧氏距离与动态时间弯曲度量

大量实验表明，在时间序列数据聚类中，使用SBD 可以获得比使用DTW 更好的聚类性能和效果。

另外，一些基于特征表示的距离度量方法也常用于时间序列的聚类分析，如基于多项式参数的[25]和基于主成分分析的[27]等距离度量方法在时间序列数据挖掘中起到了提升聚类效果的作用。

2.4 聚类算法

时间序列数据聚类主要包括层次聚类、划分聚类、基于模型的聚类、基于密度的聚类、基于格的聚类和多步聚类等[18]。时间序列层次聚类[36]是一种具有直观效果的聚类方法，分为基于凝聚和基于分裂的层次聚类。特别地，为了检索特征表示或相似性度量方法的有效性，通常被用来直观显示基于形态的或基于特征的时间序列聚类情况。

划分聚类[37]是时间序列聚类算法研究中最为常用的方法之一，通常借助于相似性度量函数来实现簇划分，具体方法包括K-Means、K-Medoids和 FCM。例如，在时间序列SBD 距离计算中，使用K-Means 的思想来对时间序列进行快速有效地聚类，通过寻找最优参数来达到目标评价函数最优，即：

基于划分的聚类方法需要事先设定聚类个数，但在应用中通常无法确定聚类个数，特别是对海量高维时间序列数据来说，该参数的确定显得更加困难。文献[38]研究了适当的初始中心对时间序列K-Means 聚类的质量和效率有很大影响。文献[39]认为K-Means 和K-Medoids 与层次聚类相比，其具有较好的时间性能，比较适用于时间序列的聚类分析。与这两种聚类相比，FCM 是一种基于模糊理论的软划分，该方法在一定程度上考虑了时间序列数据对象的不确定性问题[40]。

基于模型的聚类与其他方法不同，它假设同一簇中数据服从某种模型的数据分布，通过数据模型学习来试图调整近似模型，使其接近数据客观存在的真实模型[41]。目前也有一些较为成熟的方法[10]，如自组织映射、多项式回归分析、高斯混合模型、ARIMA 模型、马尔可夫链和隐马尔可夫模型等。然而，基于模型的聚类方法存在一些问题有待研究：一方面，模型需要用户事先设定假设模型和模型参数，若假设模型与真实模型相差甚远，则会导致最终的聚类结果不准确；另一方面，此类模型需要较长的计算时间，不利于高维时间序列数据和动态时间相关数据的聚类分析。

基于密度的和基于格的聚类方法[42-43]先将时间序列数据转化为另一种数据形态，使其能够适用于传统数据挖掘中的聚类算法，如DBSCAN、OPTICS、STING 和Wave Cluster 等方法。多步聚类方法[44]则是从聚类算法设计和分析的角度出发，通过多种方法对时间序列数据进行分步聚类，其效果通常要优于传统基于特征表示的、基于相似性度量的和基于模型的聚类方法。

数据挖掘中的聚类算法[4]较为成熟，除了具有较为完善的理论基础，其在许多领域都有很好的应用效果，因此，它们也可以直接或间接应用于时间序列数据的聚类分析。然而，由于时间序列数据具有时间和变量高维性、概念漂移、随机性和混沌现象等特点[29,45]，需要进行数据降维、特征表示和相似性度量，也包括异常点发现等前期处理工作。根据传统聚类算法思路设计适用于时间序列数据聚类的模型和算法，如将传统聚类思路结合复杂网络特征，实现多变量时间序列数据的聚类[46-47]。

2.5 簇原型

簇原型[48]是指某一特定簇的近似代表对象，其质量好坏直接影响某些聚类算法的分类效果，如K均值、模糊聚类和近邻传播聚类(AP)等算法都需要定义相应的簇原型。在时间序列数据聚类领域中，簇原型大体可分为3 种，分别是簇中心代表点[49]、簇的平均序列[50]和基于局部搜索的簇原型[37]。

通过基于DTW 的距离计算来重复交替迭代计算簇中心序列和分配簇成员，实现时间序列数据的聚类。

如图4 所示，图4a 显示了同一个簇中3 条时间序列样本的形态波动示例，图4b 中较粗曲线表示了DBA 方法的簇平均序列，易发现基于DBA的簇平均序列的形态波动与簇成员的形态波动相似。基于局部搜索的簇原型[37]是一种在簇类中进行局部搜索找出簇原型的方法，与基于簇中心代表点的和基于簇平均序列的K中心点聚类算法相比，基于局部搜索簇原型的K中心聚类具有较好的挖掘效果。

图4 簇平均代表序列

2.6 应用研究

时间序列数据挖掘中的聚类研究成果主要应用于两个方面：1)将聚类算法作为其他时间序列数据挖掘技术和方法的子程序或中间件，其聚类结果可以辅助其他数据分析任务的顺利进行并提高数据挖掘任务的效果[51-52]；2)聚类算法可被运用在具体的实际生产和生活领域中，如生物信息、天体气象、经济金融、医疗卫生、语音识别和工业工程等[53-57]，根据具体背景知识来发现相关行业时间序列数据中的兴趣模式、异常模式和频繁模式。

在工业工程领域中，文献[58]提出了一种基于灰色关联聚类的特征提取算法，利用灰色关联度作为动态聚类欧氏距离的思想，构建以某型涡扇发动机为例的灰色关联聚类特征提取模型，以便满足故障诊断要求。特别地，在金融数据分析应用领域中，通过时间序列聚类分析方法可以发现股票市场中相似的股票群，结合滑窗法可以实现基于动态衍化聚类的股票识别。金融市场被众多因素共同影响，不仅有宏观的政治、经济等环境因素，还有微观的企业运作方式、人们的心理作用等因素。通过对金融时间序列进行聚类，可以挖掘出金融市场的内在机制，对揭示数据背后的发展变化规律有重要作用。文献[59]提出一种基于影响力计算模型的股票网络中心节点层次聚类算法，利用社区发现方法对股票时间序列进行聚类。文献[60]提出一种基于支持向量回归和自组织神经网络的聚类方法，提取投资组合选择方法，实现了金融股票价格和波动率的预测分析，对印度国家证券交易所102 支股票进行最优投资组合，具有低风险高盈利的特征。文献[61]针对金融股价时间序列数据的时间属性变量高维性，提出利用三阶段聚类模型，对股票进行增量式聚类，进而发现上市公司之间的联动关系。

3 主要问题与未来研究方向

时间序列数据聚类研究主要集中于整体序列数据对象，在数据降维与特征表示、相似性度量、聚类模型与算法、簇原型和应用等方法上取得了一定的学术进展，拥有应用价值，但仍存在一些问题有待探讨，以便系统性地研究和提高聚类分析在时间序列数据资料中的挖掘质量和应用性能。

1) 传统时间序列聚类模型与算法主要以一元时间序列数据为研究对象，通过数据转换、特征表示或模型参数实现时间维度的降维，利用数据挖掘中经典聚类方法进行分析，缺少兼顾时间序列数据时间维度长、属性变量多和数据体量大等高维性的问题。特别地，数据体量大造成算法在运行期间需要消耗巨大的内存空间，使得以静态处理方式为基础的传统聚类算法在此类高维时间序列数据集中无法得到有效地运行。因此，根据高维时间序列数据自身的特点，需要研究适用于高维时间序列数据的实时、动态或者增量运行的聚类算法。

2) 基于原始数据的时间序列距离度量通常需要较大的时间复杂度和空间复杂度，并且大部分距离度量方法对数据中的扭曲数据较为敏感，使其在计算过程中无法获得直观的度量效果。数据降维后的特征表示在一定程度上能够改善此种境况，降低了聚类算法和模型的复杂性，但特征表示对高维原始时间序列数据的精确定位难以实现，最终影响聚类模型与算法的精度。针对基于特征表示和相似性度量方法的高维时间序列数据聚类模型与算法研究，需要改变传统方法仅对高维数据进行某个特定维度上的数据降维和特征表示，制定适用于特征表示后由于信息丢失而造成距离度量不准确的情况，进而提升相关模型与算法的聚类效果。

3) 动态时间弯曲是时间序列数据挖掘领域中最为常用的相似性度量方法，它能有效地匹配时间序列数据中的近似形态趋势，对时间点异常数据不敏感，能够度量不等长时间序列之间的相似性，具有较好的度量质量和较高的准确性等优势。在高维时间序列数据库中，过长的时间维度、过多的属性变量和过大的数据体量造成动态时间弯曲方法容易平滑时间序列局部形态的特点，不能有效反映高维时间序列数据对象之间的形态变化关系，无法实现真实距离的有效度量，进而影响基于动态时间弯曲的高维时间序列聚类效果。如何提高动态时间弯曲方法的精确度量和计算性能是高维时间序列聚类研究中需要解决的问题之一。

4) 关于时间序列聚类的研究目前大多数集中在提升特征表示、距离度量和簇原型的质量或效率上，对于聚类本身的设计与研究相对不足。虽然已有学者利用多步聚类方法在一定程度上改进了传统聚类算法在时间序列数据中的分析效果，但也存在步骤繁琐、聚类结果易受参数设置影响、计算性能较低等问题。同时，由于时间序列数据高维性和其他特征因素的影响，聚类方法在相关应用中大多数局限于变量属性少、时间维度短和数据量少等对象的分析，较少考虑不确定性和高噪声等因素的影响，使得聚类分析理论和方法在实际应用中具有局限性。为此，通过总结现有的时间序列聚类算法优缺点，结合具体问题中的数据特征，在考虑多种特征因素影响的情况下来构建符合高维时间序列数据的高性能聚类算法值得深入研究。

4 结 束 语

本文梳理了目前常用的时序聚类算法，综述了该领域中的相关研究成果，归纳了已有研究存在的不足，提出了一些值得研究的方向。研究发现，时间序列数据挖掘中聚类模型与算法的研究顺应了大数据时代潮流，解决了高维性给传统时间序列聚类分析带来不能快速有效挖掘的问题，提高和拓展了时间序列数据挖掘领域中的相关理论和方法。时间序列数据聚类研究成果能给政府部门和企业对相关事务决策提供更为完备成熟的理论基础与技术，以便进行更为科学合理的智能管理。