论文阅读-Time-series clustering – A decade review

 

时序数据聚类综述

1. 引言

聚类是一种数据挖掘技术，将相似的数据放入相关或同质的组中，而无需事先了解组的定义。具体而言，聚类是通过将与组内其他对象具有最大相似性、与其他组中的对象具有最小相似性的对象分组而形成的。这是一种有用的探索性数据分析方法，因为它通过客观地将数据组织成相似的组来识别未标记数据集中的结构。此外，聚类常被用于探索性数据分析以生成特征，并作为其他数据挖掘任务的预处理步骤或作为复杂系统的一部分。

1.1 时序聚类

(1)时间序列数据库包含可以通过模式发现获得的有价值的信息。聚类一种常见的解决方案，用于揭示时间序列数据集上的某些有规律的模式。

(2)时间序列数据往往非常庞大，人类无法很好地用直观的方式来理解，通过时间序列聚类，将不同的时序数据进行划分，然后分而分析之，在一定程度上，理解时序问题会变得更简单些

(3)时间序列聚类是最常用的一种探索技术，也常常是更复杂的数据挖掘算法(如规则发现、索引、分类和异常检测)的必备过程之一。

(4)将时间序列簇结构表示为可视图像(时间序列数据的可视化)可以帮助用户快速理解数据集中的数据结构、簇、异常和其他规则。

1.2 时序聚类的应用

时间序列数据聚类主要用于发现时间序列数据集中的有趣模式，该任务本身分为两类: 第一类用于查找数据集中频繁出现的模式；第二类是发现数据集中意外发生的模式的方法。

简单地说，找到时间序列的聚类可以在不同的领域有利于回答以下现实世界的问题: 异常、新颖性或不和谐检测:异常检测是发现数据集中意外发生的异常和意外模式的方法。

1.3 时序聚类的分类

大部分聚类时间序列相关的工作可以分为三大类:全时间序列聚类、子序列聚类和时间点聚类。

(1)全时间序列聚类（whole time series clustering）是指对一组时间序列的相似性进行聚类，即对多个序列数据之间进行聚类。

(2)子序列聚类（subsequence time series clustering）是指对单个时间序列的一组子序列进行聚类，通过滑动窗口提取子序列，即对单个长时间序列中的片段进行聚类。

(3)时间点聚类（time point clustering）。它是基于时间点的接近度和对应值的相似性的时间点的聚类。这种方法类似于时间序列分割。但与分割不同的是，它不需要将所有的点都分配到聚类中，也就是说，会有一些时间点被认为是噪声点。

本研究的重点是“全时间序列聚类”。全时间序列的聚类通常有三种不同的方法，即基于形状、基于特征和基于模型。如下表:

在基于形状的方法中，通过时间轴的非线性拉伸和收缩，尽可能地匹配两个时间序列的形状。这种方法也被称为基于原始数据的方法，因为它通常直接处理原始时间序列数据。基于形状的算法通常采用传统的聚类方法，这些聚类方法与静态数据兼容，而其距离/相似度度量经过了适当的时间序列度量修改。在基于特征的方法中，将原始时间序列转换为较低维的特征向量。然后，将传统的聚类算法应用于提取的特征向量。通常在这种方法中，从每个时间序列中计算一个等长的特征向量，然后进行欧氏距离测量。在基于模型的方法中，将原始时间序列转化为模型参数(参数化模型)，然后选择合适的模型距离和聚类算法(通常是传统的聚类算法)，并应用于提取的模型参数。研究表明，通常基于模型的方法存在可伸缩性问题，当集群彼此接近时，其性能会下降。

时间序列聚类本质上有四个组成部分:降维或表示方法、距离测量、聚类算法、原型定义和评价。

2. 时序聚类的表示方法

数据自适应、非数据自适应、基于模型和数据指示的表示方法，如下图所示：

2.1 数据自适应

数据自适应表示方法对数据集中的所有时间序列进行表示，并尝试使用任意长度(非等长)段最小化全局重构误差。该技术已被应用于不同的方法，如分段多项式插值(PPI)，分段多项式回归(PPR)， 分段线性近似(PLA)、分段常数近似(PCA)、自适应分段常数近似(APCA)、奇异值分解(SVD)、自然语言(Natural Language)、符号自然语言(NLG)[98]、符号聚合近似(SAX)和iSAX。数据自适应表示可以较好地逼近每个序列，但比较多变量的时间序列比较困难。

2.2 非数据自适应

非数据自适应方法是一种适合于固定大小(等长度)分割的时间序列的表示，并且比较几个时间序列的表示是直接的。这组方法包括小波: HAAR, DAUBECHIES, Coeiflets,Symlets, Discrete Wavelet Transform(DWT), spectral Cheby-shev Polynomials, s p e c t r a l D F T , Random Mappings, Piecewise Aggregate Approximation (PAA) and Indexable Piecewise Linear Approximation (IPLA).

2.3 基于模型

基于模型的方法以随机的方式表示时间序列，如马尔可夫模型和隐马尔可夫模型(HMM)，统计模型，时间序列位图和自回归移动平均(ARMA)。在数据自适应、非数据自适应和基于模型的方法中，用户可以根据手头的应用定义压缩比。

2.4 数据指示

压缩比是基于原始时间序列自动定义的。下表列出了文献中常用的几种表示方法：

2.5 小结

在以往的研究中，研究人员对时间序列数据提出了许多不同的表示方法。这些方法大多侧重于加速计算，并且大多强调为实现这一目标而建立索引的过程，另一方面，其他一些方法考虑了表示的质量，有的作者关注表示方法的准确性，并提出了时间序列的水平近似。每个时间序列由一个位串表示，每个位值指定数据点的值是否高于时间序列的平均值。这种表示可以用来计算时间序列的近似聚类。这种表示也称为剪切表示，可以与原始时间序列进行比较，但在其他表示中，必须将数据集中的所有时间序列转换为相同的降维表示。然而，剪切序列在理论上和实验上已经足够用于基于变化相似度的聚类(基于模型的不相似度量)，而不是基于形状的聚类。回顾文献表明，对于离散的时间序列的研究工作是有限的，而且值得注意的是，大多数研究工作是基于均匀抽样数据，而有限的工作是针对不均匀抽样数据。此外，在大多数研究工作中，数据误差没有被考虑在内。最后，在本文综述的所有论文中，没有一篇涉及处理每个变量长度不同的多元时间序列数据。

3. 时序聚类中的相似/不相似度量

时间序列相似/不相似搜索的理论问题由Agrawal等人提出，随后成为数据挖掘界的一个基本理论问题。时间序列聚类在很大程度上依赖于距离度量。有不同的测量方法可以用来测量时间序列之间的距离。一些相似度量是基于特定的时间序列表示提出的，例如与SAX兼容的MINDIST，不管表示方法如何，它都是与原始时间序列兼容的。在传统的聚类中，静态对象之间的距离是基于精确匹配的，而在时间序列聚类中，距离是近似计算的。计算两个时间序列之间距离的最简单方法是将它们视为单变量时间序列，然后计算所有时间点之间的距离测量。

3.1 在时间上找到相似的时间序列

这种方式所定义的时间序列自建的相似指的是两个时间序列数据在每一个时间步上都相似，例如欧式距离就很适合这样的目标。然而，因为这种相似度的计算方式对于长时间序列的计算往往是非常耗费时间的，因此，计算常常是在变换后的时间序列上进行的，例如傅里叶变换、小波变换或分段聚合近似(PAA)。 Keogh和Kasetty，对这个问题做了全面的回顾。一个典型的例子，将许多公司相关的股价的时间序列聚类，以发现哪些股票一起变化，以及它们如何相互关联被归类。

3.2 在形状上找到相似的时间序列

要找到形状上相似的时间序列，模式发生的时间并不重要。因此，采用弹性方法，如Dynamic time Warping (DTW)进行不相似度计算。利用这一定义，我们可以构造具有相似变化模式的时间序列聚类，而不考虑时间点。例如，将股票具有共同模式的不同公司的股价聚类，而这些公司的股价独立于其在时间序列中的出现。时间上的相似是形状上相似的一种特殊情况。一项研究表明，形状相似度优于基于时间相似度的度量。

3.3 在变化中寻找相似的时间序列(结构相似性)

该方法通常采用隐马尔可夫模型(HMM)或ARMA过程等建模方法，然后对拟合模型的参数与时间序列进行相似性度量。即具有类似自相关结构的聚类时间序列，如次日股价下跌后有上涨趋势的股票的聚类。这种方法适用于长时间序列，而不适用于中等或较短的时间序列。

3.4 思考

(1)通过研究上述的相似性/不相似性度量方法，可以发现最有效和准确的方法是基于动态规划(DP)的方法，这种方法的时间复杂度很高(因为比较两个时间序列的时间复杂度为O(n^2)，n为序列的长度)。尽管通常会对这些距离/相似性度量采取一些约束来降低复杂性，但它需要仔细地调整参数以提高效率和有效性。因此，在选择相似性度量时时，应该在精度和效率之间找到平衡。另一种观点是，有必要理解距离测量在大尺度时间序列数据集中的有效性。这个问题不是从文献中得到的，因为大多数被考虑的论文都是基于相当小的数据集。

(2)在相似性度量的研究中，距离度量面临着各种挑战。一个很大的挑战是距离度量与表示方法的不兼容问题。例如，用于时间序列分析的常用方法之一是将时序数据从时域转换到频域上，而在使用频域空间时，很难找到序列之间的相似性以产生基于值的差异用于聚类。

(3)欧氏距离和DTW是时间序列聚类中最常用的相似性度量方法。有研究表明，在时间序列分类精度方面，欧氏距离具有惊人的竞争力，而DTW在相似性度量方面也有其不可削弱的优势。

4. 时序聚类原型

在时间序列的文献中已经发表了一些计算原型的方法，但是这些出版物中的大多数都没有证明其方法的正确性。但是，通常有三种方法可以用来定义原型：集合的中位数序列、集合的平均序列和局部搜索原型。

4.1 集合的中位数序列

在时间序列聚类中，最常见的获取最优斯坦纳序列的方法是使用聚类中值作为原型。在这种方法中，集群的中心被定义为一个序列，该序列使集群内到其他对象的距离平方和最小。给定聚类中的时间序列，聚类中所有时间序列对的距离使用距离度量(如欧几里得或DTW)计算。然后，定义聚类中一个平方和误差较低的时间序列为聚类的中位数。此外，如果距离是欧几里得等非弹性方法，或者可以计算出聚类的质心，则可以说中位数是距离质心最近的时间序列。

4.2 集合的平均序列

如果时间序列都是等长的，聚类过程中的距离度量是一个非弹性距离度量(如欧氏距离)，则平均方法是一种简单的平均技术，即时间序列在每个点上的平均值。此时的做法其实等同于在做常规的静态数据的聚类，只不过每个时间步的序列值对应着每个特征。

4.3 局部搜索原型

该方法首先计算聚类的集合的中位数序列，然后使用平均法，基于wraping path计算平均prototype。然后，根据average prototype计算出新的wraping path。Hautamaki等提出了一种通过局部搜索获得的原型，而不是medoid，以克服欧氏空间中时间序列聚类质量较差的问题。他们在k-Medoids上应用medoid、average和局部搜索、随机交换(RS)以及层次聚类来评估他们的工作。他们发现，局部搜索提供了最好的聚类精度，也比k-Medoids更好。

4.4 小结

导致聚类精度低的问题之一是时间序列聚类过程中prototype的定义或更新方法较差，特别是在划分方法上。许多聚类算法存在表示方法准确率低的问题。而且，不准确的prototype会影响聚类算法的收敛，导致得到的聚类质量较低。在本研究中，由于使用的距离度量是一个非弹性距离度量(ED)，因此使用平均方法来寻找子簇的prototype。虽然为了合并的目的，可以使用任意方法，如果它兼容弹性方法。

5. 时序聚类算法

一般聚类可以大致分为六组:分区聚类、分层聚类、网格聚类、模型聚类、密度聚类和多步聚类算法。

5.1 时间序列的层次聚类

一种聚类分析方法，利用凝聚或分裂的方式将样本划分成不同层次的聚类簇。凝聚式的层次聚类初始将每个样本视为一个聚类簇，然后逐步合并聚类(自底向上)。相比之下,分裂算法则完全相反。一般来说，分层算法的质量较差，因为在分裂法中，分簇后无法调整聚类，在凝聚法中，合并后也无法调整聚类。因此，通常将分层聚类算法与另一种聚类算法相结合，形成一种混合聚类方法来解决问题。层次聚类在时间序列聚类中具有很强的可视化能力，这使得它在很大程度上成为时间序列聚类的一种方法。由于二次计算的复杂性，分层聚类本质上不能有效地处理大时间序列，因此可扩展性差，限制在小数据集。

5.2 时间序列的划分聚类

从未标记的对象中生成组，每个组至少包含一个对象。划分聚类最常用的算法之一是k-Means，其中每个聚类都有一个prototype，该prototype是其对象的均值。k-Means聚类背后的主要思想是最小化一个聚类中所有对象与它们的聚类中心(原型)之间的总距离(通常是欧氏距离)。

k-Means过程中的原型定义为聚类对象的均值向量。然而，当涉及到时间序列聚类时，这是一个具有挑战性的问题，kmeans需要确定簇的数量这一点比较烦人，但是与层次聚类相比，k-Means和k-Medoids的聚类速度非常快，这使得它们非常适合于时间序列聚类，并在许多工作中被使用。k-Means和k-Medoids算法以“hard”或“soft”的方式构建聚类，这意味着一个对象要么是一个聚类的成员，要么不是。另一方面，FCM(Fuzzy c-Means)算法和Fuzzy c-Medoids算法构建“软”聚类。在模糊聚类中，对象在每个聚类中都有隶属度。模糊划分算法已被用于某些领域的时间序列聚类。

5.3 基于模型的聚类

试图从一组数据中恢复原始模型。这种方法为每个集群假定一个模型，并找出最适合该模型的数据。详细地说，它假设有一些随机选择的质心，然后一些噪声以正态分布添加到它们。从生成数据中恢复的模型定义了cluster。比较为人所知的是GMM，SOM和HMM，一般来说，基于模型的聚类有两个缺点:首先，需要设置参数而且它是基于用户的假设（例如GMM假设原始数据服从混合高斯分布），而用户的假设可能是错误的，因此聚类结果将是不准确的。其次，在大数据集上处理时间较慢(尤其是SOM)。

5.4 基于密度的聚类

聚类是密集对象的子空间，这些子空间被低密度对象的子空间分隔开。其中一个著名的基于密度概念的算法是DBSCAN，在该算法中，如果一个集群的邻居密度较大，则该集群将被扩展。OPTICS是另一种基于密度的算法，它解决了在不同密度的数据中检测有意义的簇的问题。Chandrakala和Chandra提出的模型是少数案例之一，作者提出了一种基于密度的核特征空间聚类方法，用于聚类变长度的多元时间序列数据。此外，他们还提出了一种启发式的方法来寻找他们提出的算法中所使用的参数的初值。然而，回顾文献可以发现，基于密度的聚类方法由于其较高的复杂性，尚未被广泛应用于时间序列数据聚类。

5.4 基于网格的聚类

将空间量化为有限数量的网格单元，然后在网格单元上执行聚类。STING和Wave Cluste是基于网格概念的聚类算法的两个典型例子。据我们所知，引用的文献中没有应用基于网格的方法来聚类时间序列的工作。

5.5 小结

考虑到大量的工作，我们了解到，在大多数模型中，作者使用时间序列数据作为原始静态数据或进行representation之后，使用标准的传统聚类算法。很明显，这种使用没有任何优化的蛮力方法来分析时间序列的方法是科学理论的正确解决方案，而不是现实世界的问题，因为它们在大型数据库中自然非常缓慢或不准确。因此，在许多研究中，研究者的注意力被吸引到使用定制的算法对时间序列数据聚类作为最终的解决方案。

6. 时序聚类评价方法

      一般来说，在没有数据标签的情况下，对抽取的cluster进行评估是不容易的，这仍然是一个悬而未决的问题。cluster的定义取决于用户和领域，而且是主观的。例如，聚类的数量、聚类的大小、离群值的定义、问题中时间序列之间相似性的定义，都是依赖于手头任务的概念，应该主观地声明。这些都使得时间序列聚类成为数据挖掘领域的一大挑战。但是，由于分类数据标记为人工判断或它们的生成器(在合成数据集中)，结果可以通过一些措施来评价。

在聚类原始数据方面，人类判断的标签并不完美，但在实践中，它抓住了算法的优缺点作为基本事实。为了评估MTC，数据集来自于它们的标签已知的不同领域。下图展示了在时间序列聚类中评价新模型的过程。

常见的时间序列聚类的评估指标如下：

在标量精度测量中，生成一个实数来表示不同聚类方法的精度。用于判断聚类效度各个方面的数值测度分为两类:

外部指标(External Index):该指标用于衡量形成的聚类与外部提供的类标签或ground truth的相似性，是目前最常用的聚类评价方法。在文献中，该指标又被称为外部标准、外部验证、外部方法和监督方法，因为ground truth是可用的。

内部指标:该指标用于衡量一个聚类结构的优度，而不考虑外部信息。在文献中，该指标也被称为内部标准、内部验证、内部方法和无监督方法。本节的其余部分将讨论这些评估技术。

7. 总结

揭示规律，探索数据手段，理解时序数据 ，用于查找数据集中经常出现的模式。例如，股价变动相似的公司的发现，商店中特定产品的不同日常销售模式；发现数据集中发生的异常模式的方法。时间序列的聚类可以在不同的领域解决以下现实世界的问题:异常检测（anomaly detection）、新奇检测（novelty detection）或不和谐检测（ discord detection）

时序聚类的挑战：时序数据长，数据量大，工程压力大；高维时序数据下，很多常规聚类算法不work；时序数据的相似度定义复杂；时序数据很容易存在噪声；时序数据长度常常不同。

需要论文原文以及纸质阅读总结的朋友可以移步百度网盘进行下载。

链接：https://pan.baidu.com/s/11ZI3G3vaLJWRXrAhdaezGQ 
提取码：xd11 
--来自百度网盘超级会员V5的分享