KShape：时间序列数据聚类
时序数据的聚类是聚类领域中一块特殊而重要的模块，对于时序数据的聚类主要有两个思路：
一是将时序数据预处理（特征空间转化）成普通聚类算法需要的数据，将原始时间序列数据转化为另一特征空间的数据对象，然后调用其他如层次聚类、密度聚类的传统聚类算法在特征空间中对数据对象进行聚类。
二是针对时间序列数据具体特征定义适用于本数据的距离度量来衡量样本之间的相似度，再调用传统聚类算法基于新的距离度量做聚类。
还有一种对时序数据做多分辨率解析，是在不同分辨率视角下结合不同方法进行聚类分析，提升传统方法的聚类效果，相当于对聚类结果做优化，但不算一种思路，感兴趣可参考《A novel two-level clustering method for time series data analysis》。
对于一个时序数据集 ，需要将其聚类成K个簇 。根据聚类序列对象的多寡，大致可以分为多序列聚类和单序列聚类：
多序列聚类就是对多个时间序列做聚类，此时 表示不同的时序对象，即每一个 都是一个时间序列 ，其中 表示时间点的值，例如，对于日常购物的销售数据来说，萝卜和白菜的时序数据会聚类成蔬菜类，而衣服和鞋子会聚成衣物类。
单序列聚类是对单个时间序列的子序列做聚类，这里 表示的是不同的步长，此时 ，例如，对于衣服的时序销售数据而言，6，7，8月会聚成夏天类，12，1，2月会聚成冬天类。
从多序列聚类可以引出全序列聚类的概念，它是指对一组时间序列的相似性进行聚类，一般针对更常见的多序列聚类问题，例如对于不同公司的股票的价格数据进行聚类。全序列是相对“子序列”而言的，“子序列”有两种：一种是单个时间序列的子序列‘片段’，如一年之中的某个季度，此后的子序列专指子序列‘片段’；另一种是时间点，即单位时间粒度，如一年之中的具体哪一天。所以单序列聚类又可以分为子序列聚类和时间点聚类：
子序列聚类（subsequence time series clustering）通过滑动窗口提取子序列，即对单个长时间序列中的片段进行聚类，可以有效的发现较长时序中的“频繁模式”和“异常片段”。是对一个时间序列的不同时间周期下的子序列进行聚类，本质上也可以转化为全时序数据聚类。
时间点聚类（time point clustering）是基于时间点的接近度和对应值的相似性的时间点的聚类。这种方法类似于时间序列分割。但与分割不同的是，它不需要将所有的点都分配到聚类中，也就是说，会有一些时间点被认为是噪声点。
我们今天要介绍的就是既可以做子序列聚类又可以做全序列聚类的KShape时序聚类算法，KShape原理和Kmeans相似，不同在于它改进了距离计算方法，并优化了质心计算方法。一方面支持振幅缩放和平移不变性，另一方面计算效率也比较高，并且不用手动设置参数，便于扩展到更多领域。
不变性是指即使目标的外观发生了某种变化，但是你依然可以把它识别出来。距离度量具有某种不变性是指对序列做了该种变换后距离度量依然能识别，面对两个序列就是对其中一个做该种变换后发现两个序列一样（相似度高）。因为我们希望图像中目标无论是被平移，被旋转，还是被缩放，甚至是其他不同的变换条件下都可以被成功地识别出来。KShape就是一种与领域无关、精确且可扩展的时间序列聚类算法，该算法具有对缩放和移动不变性的距离度量SBD(因为SDB是基于互相关性计算相似度)。
除此之外，一般的距离度量还应具备遮挡不变性和复杂度不变性，遮挡不变性是当缺少子序列时，仍然可以通过忽略不匹配的子序列来比较序列。这种不变性在手写时很有用，如果有打字错误或字母丢失。复杂性不变性是当序列具有相似的形状但复杂度不同时，我们可能希望根据不同需求使其具有低或高的相似性。
如图，室内A和室外B记录的同一句话的音频信号复杂度不同但依然是相似的，尽管室外信号比室内信号噪音更大。但总体趋势相似度很高。当然，这个复杂度只是小拓展，与kshape关系不大，下面开始介绍基于互相关性的距离度量SBD。
了解Kshape聚类思想之前先来回顾一下Kmeans的思想，面对n个样本（一堆点），先随机初始化k个质心，然后分别计算剩下每个样本点和这k个质心的欧式距离并把该点分配给距离最近的质心。第一次划分簇完成后，根据簇成员求算数平均值更新质心，更新质心后再重新划簇，就这样迭代到最大次数或质心不在变化，Kshape的聚类思想跟Kmeans基本一致，只不过在划簇时计算的不是欧式距离，而是另一种距离度量SBD距离；更新质心的方式换成了基于SBD的最大化互相关系数的优化问题。这里的SBD距离跟互相关系数的关系为：SBD等于1减去最大（规范化）互相关系数，下面我们来详细介绍：
互相关是一种统计度量，我们可以用它来确定两个等长序列的相似性，即 和 ，即使它们没有正确对齐。为了实现平移不变性，计算互相关性需要保持 静止，并在 上一步步滑动 ，以计算 的每个平移 步后两个序列的内积。我们用以下公式表示序列的平移，如下所示：
这里s的方向和大小是从x 和y 两头对齐时为基准计算的，用下图演示：假设绿色区域为y，白色区域为划动的x，每一行s（step)向前划动一步，序列长度为m=4，s∈(-3,3)共7种取值，w是所有移动的可能性2m-1=7次，w-m=s=k代表移动步长，表示移动k步时两个序列最相似。x 和y 两头对齐时是s=0时的情况，看w=6这种情况，从对齐时的基准情况下的x 移动到w=6时的x 向右走了2步，所以s的方向为正，大小为2。
当知道了所有的序列平移情况 后可以计算互相关系数 ，是一个长度为2m-1的互相关序列，定义如下：
利用 R 来计算x和y在每一步的相似度，在对应(在X,Y中都存在)的位置计算点积，最终 R 是有效(对齐)区域的点积之和（对每个对上的小块的乘积加和）。可以说，R 越大两个序列越相似。我们的目标是计算 最大化的位置w，因为w有2m-1种，每一个w都会计算出一个 ，然后用1减去最大的 就是SBD距离了。
有了互相关系数，就可以给出SDB的定义： ，对比所有可能位置的相似度值，取最相似的 ，然后用 得到SBD，这样做是为了适配Kmeans中距离越小越应该划为同一簇的特性，也就是说两个序列形状越相似，SBD距离就越小。
仔细观察SBD公式可以发现，是对 取最大值，而非互相关系数 ，这是对其进行了一个系数归一化的规范化操作，目的是为了去除量纲（在这里指振幅和相位）的影响。规范化有三种，分别是有偏估计量 、无偏估计量 和系数归一化量 ，系数归一化就是将互相关序列除以各个序列自相关的几何平均值。其定义如下：
通过实验证明，第三种 的规范化效果最好,所以定义SDB距离时选择了 。至于实验过程，在此不在赘述，详情可以参考论文《k-Shape: Efficient and Accurate Clustering of Time Series》，归一化后的互相关系数NCC值在[-1,1]之间，因此，SBD值在[0,2]之间。
为了能够更快速有效的计算SDB距离，在实际计算时是对 做了一个傅里叶变换（其实这块我没看懂，哈哈哈，你懂请踹我！！！），目的是缩短计算时间。
定义了距离之后，还需要根据SBD距离来计算质心，传统质心一般指平均序列。从一组序列中提取平均序列的最简单方法是将序列的每个坐标计算为所有序列对应坐标的算术平均值。最流行的聚类方法k-means使用这种方法。但是这样的质心不能有效利用类特征。
为了避免质心不能有效利用类特征的问题，Kshape将质心计算转化为一个优化问题，其目标是找到所有其他时间序列的平方距离之和的最小值：
在这里有必要说明一下， 是一个虚拟质心的代表符号（可以理解为很多待选择的质心点）， 就是 中我们要找到的那个使所有其他时间序列到该质心的平方距离之和 最小的质心。然而，由于互相关系数度量的是时间序列的相似性，而不是相异性，我们可以将 转换为求其最大值来表示所有其他时间序列的平方相似性。通过将方程6改写为最大化问题，并从方程5中得出：
该公式的目标是寻找 ，使质心 与该簇 中各条序列 的相似度NCC最大。通过进一步转化，可以变成：
通过上述转换，我们将方程7的优化简化为方程8的优化，称为瑞利商最大化。其中 ，I 是单位矩阵， O 是一个全是1的矩阵； ， 。我们通过对M提取第一特征向量可以找到最大值 ，即实对称矩阵M的最大特征值对应的特征向量，这个特征向量序列就是我们要找的质心 。
现在我们来梳理一下Kshape的思路：首先输入已经 归一化好的时间序列集X和我们想要生成的聚类数k。然后将X中的时间序列随机分配k个簇。调用最大相似度优化算法计算每个簇的质心。一旦计算出质心，就计算每个样本距所有质心的SBD距离并将其划给距离最小的质心来更新簇成员。我们重复这个过程，直到算法收敛或达到最大迭代次数（通常是一个较小的数字，如100）。该算法的输出是将序列分配到的簇和每个簇的质心。
总之，k-Shape执行两个步骤：
1、在分配步骤中，算法通过将每个时间序列与所有计算出的质心进行比较，并将每个时间序列分配给最近质心的簇来更新簇成员关系；（类似Kmeans）
2、在更新质心中，更新簇质心以反映前一步骤中簇成员的变化。该算法重复这两个步骤，直到集群成员身份没有变化或达到允许的最大迭代次数。在赋值步骤中，k形依赖于SDB的距离度量，而在细化步骤中，k形依赖于质心计算方法。
Kshape是一种新的时间序列聚类算法。依赖于SBD距离度量和形状提取方法来高效地生成时间序列的聚类方法。它基于与k-means中使用的类似的迭代细化过程。通过这个迭代过程，k-Shape将平方距离之和最小化转化为求相似度最大化来求质心，可以生成均匀且分离良好的簇，以及可以在缩放和平移不变性下有效地比较各时间序列。