英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
k-Shape:高效准备的时间序列聚类
摘要
横跨多种分项瞬时数据的普遍存在和增长已然引发了各界对时间序列数据分析和挖掘的浓厚兴趣。聚类是最受欢迎、应用最为广泛的数据挖掘方式之一，不仅因为它强大的发掘能力，也因为它可以作为预处理过程或者其他技术的子程序。在这篇论文中我们展示了一种新型时间序列聚类算法k-Shape.k-Shape算法依赖于一个可伸缩的迭代更新过程，这个过程会创建一组均匀且彼此完全分离的类。提到它的距离测量方法，k-Shape应用了一种相互关联方案的标准化版本，以此在比对时间序列的同时也考虑到时间序列的形态问题。基于距离测量方案的性能，我们开发了一种计算类形心的计算方法，它被用在每一次迭代过程中更新分配到每个类的形心。为了论证k-Shape的鲁棒性，我们做了大量的实验，并将当前最有竞争力的算法与之对比评价。k-Shape在精确性上超越了所有可拓展分析方法。更重要的是，k-Shape也超越了除了带有DTW的k-mediods外所有的不可伸缩方案。k-Shape和k-medoids with DTW的精确度相似。而其他不可拓展算法也因为不可拓展而被认定为不具备可操作性。K-medoids with DTW 需要更新它的位置测量结果而且计算成本高昂，运算速度显著慢于k-Shape.总之k-Shape是一种高精度、领域独立的时间序列聚类方法，并且有着广泛的应用。
【k-medoids with DTW考自Fast_and_Accurate_Time-Series_Clustering】
- 简介
或暂态或连续，这类数据挖掘解决的问题是于自然产生、自然组成的数据和序列。我们参考了这样的数据序列，并判断其中是都包含明确的时变信息。假如有，那我们把它作为时间序列，例如股票、音频、演讲和影像；或者里面包含了明确可供参考的时间轴，比如说签名或者数据流。几乎每一个学科里都包含了大量时间序列，这些学科涵盖了航天、生物、气象、医药，和其他[1,6,25,27，36,52,70,72]（这几个数字代表学科代码吗）时间序列的广泛存在引起了各界对考证[2,19,45,46,48,62,74,79]，指出[9,13,41,42,44,77]，定义[37，56,68,88]，聚类[43,54，64,87,89]以及建模[4,38,86]这样一些数据
在所有用在处理时间聚类的技术中，聚类适应用最广泛的一种。并不仅仅因为它不依赖人类监督也因为它不需要做费时的数据注释。使用聚类的方法，我们可以认知定义或者归纳出那些很有趣的模式并且统计潜在的数据。在过去的几个世纪里，时间序列聚类受到了大量关注，这不仅因为它是突出的探索能力也因为它可以作为一个预处理过程或者其他任务的子程序。
包括聚类在内的绝大多数时间序列分析方案都严重依赖与距离测量方案的选取。在比对两个时间序列时一个关键问题是如何处理各种畸变，这些畸变也正是序列的特征，之后我们会来讨论这个问题。为了说明这个论点，考虑ECG-Five-Days数据集，它记录了同一患者在不同天的心电图序列。
尽管两个序列看起来相似，但是很明显他们属于两个不同的类：类型A的特征是一个剧烈上升接一个剧烈下降后再接一个缓慢的上升。但是类型B的特征是一个缓慢上升接缓慢下降最后是一个缓慢上升。理想情况下，基于形状的聚类方法应该生成类似于图1中所示的类的分区，其中具有相似模式的序列根据其形状相似性被放置到相同的集群中，而不考虑振幅和相位的差异。由于无法精确定义形状的概念，人们提出了几十种距离测量方法[11、12、14、19、20、22、55、75、78、81]，以提供数据中多重固有失真的不变性。然而，研究表明，提供振幅和相位不变性的距离度量表现得非常好[19,81]，因此，这种距离度量用于基于形状的聚类[53,59,64,87]。
由于这些困难和各个领域间对不变性的不同需求，更多的关注被投注在距离测量方法的创新而不是聚类算法的创新上。距离测量比算法本身更加重要，这是目前被普遍相信的一个观点。这直接导致了现在的时间序列聚类主要依赖于经典聚类手段，要么用更适合时间序列的距离度量代替默认的距离度量，要么将时间序列转换成“平面”数据，以便直接使用现有的聚类算法[83]。但是聚类方法的选择还是会有影响：1.准确性影响，因为每种方法表示聚类的同质性和分离性的方式不同；2.由于计算成本不同，所以效率有些差异性。比如说频谱聚类或者特定层次聚类的变体相比于k-Means或者k-medoids来说用来识别基于密度的聚类更加合适，但另一方面，k-Means比层次聚类、频谱聚类、k-medoids这些方法比起来，他更加高效。
但是，最新的图形聚类方法，应用了基于图形划的集群随着距离测量方案改变的位移是不变的，这就带来了两个明显的缺陷：1、这个方案是不能扩展到大数据集的，因为它非常依赖于繁复的计算或者距离测量[53,59,64,37]；2、这些方法是为某些特定领域开发的[87]，他们的高效性只表现在某个特定领域或者某个特定的数据集。更重要的是最成功的图形聚类方法解决相位不变性是通过一个局部序列坐标的非线性变换完成的，有时甚至要通过一个全局非线性排列。比如图1所示的ECG(心电图)数据集，一个有效的线性变换可以显示出两个时间序列模式上潜在的差异，但是一个高计算成本的非线性变换可能会匹配两个序列的每一个上升或下降，这会使得区分两个类非常困难。很重要的一点是，以我们目前的知识而言，这些方法从来没有被广泛的相互对比评估过，当然也没有和其他的分类方法或者以层次聚类为代表的的其他聚类方法作比较。接下来我们将展示这样一个试验评估。
这篇论文中我们提出了一种新型算法k-Shape，它针对基于图像的时间序列聚类问题。K-Shape是高效且独立于其他领域的。k-Shape是基于一种有限迭代更新过程的，这与k-Means算法有些相似，但它们也有显著的不同。特别的是，k-Shape使用了和k-Means完全不同的方式去测量距离和计算中心的更新位置。基于以上讨论，k-Shape试图去在比较时间序列的同时保留其形状。为了达成这个目的，k-Shape需要一个不变的缩放和移动距离度量。与其他的聚类方法不同[53,64,87]，对于k-Shape，我们采用了互相关统计度量，并展示了:1.我们如何以一种有原则的方式推导出尺度不变和移位不变的时间序列距离度量;2.如何有效地计算这个距离。摘要根据互相关归一化的性质，提出了一种计算聚类中心的新方法。
为了论证k-Shape和距离测量的有效性，我们基于48个数据集组织了大量的实验，同时通过严格的统计分析比对了当前最先进的时间序列聚类方法和k-Shape的性能。为了保证实验结果的可再现性，我们采取了很多措施，其中包括公开我们的代码和使用公开数据集。结果显示，我们的距离测量方式是很有竞争力的，它的表现超越了欧几里得距离也达到了与有约束动态时间规整(cDTW)相近的结果[20]。cDTW是目前表现最好的距离测量算法，我们的距离测量算法结果与之相近，但是我们的算法不需要任何的调整更新而且执行同等命令更快。对于图1中的ECG数据集，我们的距离测量实现了98.9%的最近邻分类准确率，显著高于cDTW 79.7%的任务准确率。
对于聚类，我们证明了与文献报道相比，ED的k-means算法是一种稳健的方法，不适当地修改距离度量和形心计算会降低其性能。更重要的是，简单的划分方法在距离度量上的表现优于层次方法和谱方法，这说明有时被认为不如距离度量重要的算法的选择与距离度量的选择同样重要。类似地，我们证明了k-Shape在精度方面优于所有可伸缩和不可伸缩的分区、层次和频谱方法，只有一种现有的方法例外，即使用cDTW的k-medoids可以获得类似的结果。但是，这种方法有一些问题是可以用kShape来避免的:1.k-medoids计算不同矩阵的要求使它无法缩放，而且特别慢，比k-Shape慢两个数量级;2.它的距离测量需要调优，可以通过依赖于实例标记的自动化方法，也可以通过领域专家的帮助;这个需求对于集群来说是有问题的，因为集群是一个非监督任务。相比之下，kShape使用了一种简单的、无参数的距离度量。总的来说，对于时间序列
集群来说，k-Shape是一个非常准确和可伸缩的选择，它可以在不同的域上执行非常出色的性能。k-Shape特别适用于涉及相似但失相位序列的应用，如图1中的ECG数据集，其中k-Shape达到84%的聚类精度，显著高于使用cDTW的k-medoids的53%的精度。
在本文中，我们首先对聚类时间序列的研究现状进行了深入的回顾，并对我们的焦点问题给出了一个精确的定义(第2节)，然后我们提出了我们的新方法如下:
bull;我们展示了如何以一种有原则的方式从互相关测量中导出尺度、平移和位移不变距离测量，以及如何有效地计算该测量(第3.1节)。
bull;我们提出了一种计算距离测量时簇形质心的新方法(3.2节)。
bull;我们开发了k-Shape，一种基于中心点的timeseries聚类算法(第3.3节)。
bull;我们通过进行广泛的实验评估(第4节和第5节)来评估我们的想法。
- 前言
在这个部分我们回顾了相关的理论背景（2.1节）。我们讨论了时间序列中常见的失真（2.2节）以及当前对此类数据处理最为热门的距离测量方法（2.3节）。然后我们归纳总结了现在时间序列聚类的途径（2.4节），以及计算更新中心位置的总结（2.5节）。最后我们正式提出了我们的问题焦点（2.6节）。
2.1理论背景
聚类的困难：聚类是将n个观测值划分为k个簇的一般问题。其中一个簇的特征是同质性—也就是簇内观测值的相似性。不同簇的观测值存在差异性，也就是分离性。尽管许多用于捕获同质性和分离性的聚类标准已经被提出 ，但最常用的事最小簇内距离的平方和，因为它同时表示了两者。给出一组向量X = {hellip;hellip;hellip;hellip;}其中所有的向量属于集合R。有一个确定的常量k，k为簇的数量且有klt;n。这样做的目的是把数据集X划分成k个成对且不相关的簇P{hellip;hellip;hellip;hellip;} ，这样簇内的距离平方和最小。
这里向量是划分出类的中心，其中类属于集合P。在欧几里得空间中，这是一个kge;2的N-P困难问题，就算维数m=2，这也是一个N-P困难问题。由于寻找全局最优是困难的，所以经常使用k-Means方法等启发式方法来寻找局部最优。具体来说，k-Means将数据点随机分配到k个簇中，然后使用迭代过程，每次迭代执行两个步骤:(i)在赋值步骤中，将每个数据点分配到其最近的形心簇中，用距离函数确定;(ii)在细化步骤中，更新集群的中心体以反映集群成员关系的变化。当集群成员数没有变化或达到最大迭代次数时，算法收敛。
Steiner序列:在细化步骤中，k-means计算新的中心体来作为簇的代表。质心被定义为使到所有其他数据点的距离平方和最小的数据点，因此，它取决于使用的距离度量。找到这样的质心称为Steinerrsquo;s 序列问题[63]:给定一个分区属于集合P，相应的质需要满足:
当选用ED作为距离测量方案时，簇的中心可以用算数平均值的性质来计算。在许多需要观测对齐的情况下，这个问题被称为多重序列对比问题，它被称为N-P完全问题[80]。在时间序列的背景下，动态时间规整(Dynamic time Warping, DTW)(见第2.3节)是最常用的时间序列比对比对方法，人们提出了许多启发式方法来寻找DTW下的平均序列(见第2.5节)。
2.2时间序列不变性
基于定义域的序列往往存在一定程度的失真，距离度量需要满足一定数量的不变性才能对序列进行有意义的比较。在本节中，我们将回顾常见的时间序列扭曲及其不变性。有关更详细的回顾，请参见[7]。
放缩和转换不变性：在很多问题上，时间序列的不变性对认知时间序列的相似性是非常有用的，尽管它们可能在振幅和偏置上存在一定的差异性。换句话说，将一个序列 向量x 转换成 x = ax b
其中a和b是常量，而且x不能变成其他的序列。比如说这些不变性也许对于分析国外市场货币价值的季节性变化，而且不会受到通货膨胀的影响。
位移不变性：当两个序列相似但是局部排列相位存在差异或者序列中存在一致的部分也存在差异部分的时候，我们也许还需要认为他们是相似的。比如说，心跳可能不同步，这取决于我们什么时候开始测量(全局对齐)，而来自不同人的短语的手写需要根据字母的大小和单词之间的空间进行对齐(局部对齐)。
统一放缩不变性：长度不一样的序列需要进行处理，将短序列拉长或者将长序列压缩，这样我们可以更加有效率地对比这两个序列。比如说，这种不变性在测量不同持续时间的心跳是必须的。
遮挡不变性:当序列丢失时，仍然可以通过忽略不匹配的子序列来比较序列。这种不变性在手写中很有用，如果有一个打字错误或一个字母丢失了。
复杂性不变性:当序列具有相似的形状但不同的复杂性时，我们可能希望根据应用程序使它们具有低或高相似性。例如，记录在室内和室外的音频信号可能被认为是相似的，尽管室外信号将比室内信号更嘈杂。对于许多任务，当我们比较时间序列序列时，需要一些或所有上述不变性。为了满足适当的不变性，我们可以在聚类之前对数据进行预处理以消除相应的失真。
例如，通过对[29]数据进行z归一化，可以实现缩放和平移不变性。然而，对于不能通过预处理步骤轻松实现的不变性，我们可以定义提供失真不变性的复杂距离度量。在下一节中，我们将回顾最常见的这种距离度量。
2.3时间序列的距离测量
现在有两个最新的时间序列比对方法，
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238902]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
