论文阅读_时间序列聚类K形
作者认为这是一种与领域无关、高精度、高效率的时间序列聚类方法。
我认为它比传统方法有更好的聚类效果。与DTW方法相比，效果稍差，但速度快得多。毕竟原则上K形只考虑纵向拉伸和横向平移，而DTW也考虑横向拉伸。
K-Shape的原理和K-means类似，不同的是改进了距离计算方法，优化了质心计算方法。一方面支持幅度缩放和平移不变性，另一方面计算效率比较高，不需要手动设置参数，方便扩展到更多领域。
距离算法用于计算两组时间序列数据的差异，核心问题是如何处理时间序列数据的变形。本文图-1所示的心电图数据分为A/B两类:
其中，A类的特征是:上升->；谢绝-& gt；上升，而B类的特征是:下降->；站起来。图-1右下图是理想的建模效果，识别出相同的模式，忽略幅度和相位的差异。人们也更喜欢用这种方法来计算距离，很多时候甚至认为距离计算方法比聚类方法更重要。一般来说，支持幅度缩放和平移不变性的方法计算成本高，难以对大量数据建模。
K形之前的主流距离算法如下:
K-Shape通过互相关方法计算两个时间序列之间的距离。假设有两个时间序列，X和Y，序列长度都是m，为了达到平移不变性和Y不变性，一步一步划X，计算每一步X和Y的差。
如上图所示，如果绿色区域为Y，白色区域为X，则每条线s(步)向前移动一步，序列长度为m=4，s∈(-3，3)***7个值，w为所有移动的可能性2m-1=7次，w-m = s =
定义互相关系数CC:
用R计算每一步X和Y的相似度，计算对上位置的点积(同时存在于X和Y中)。最后，R是有效面积的点积之和(每对上的小块相加)。可以说R越大，两个序列越相似。
因为每个子序列的幅度不同，块数不同，所以有三种归一化方法，第三种采用互相关法，效果最好。
归一化效果如下图所示:
其中图(a)只使用了z归一化对振幅进行归一化，没有平移，可见不平移(面朝上)对齐效果最好。从(b)、(c)、(d)中可以看出:(d)图形采用第三种方法，相似度值在中点处最大(s=0时)，即正对时，其相似度最大，与(a)中呈现的效果一致。而(b)和(c)都认为最相似的情况出现在右边，这显然不太对。
本文定义了基于形状的距离SBD(Shape-based distance)。重叠的区块越多，形状看起来就越像CC。比较所有可能位置的相似度值，取最相似的max(CC)，然后用1-max(CC)得到SBD，也就是说形状越相似，距离SBD越小，归一化的NCC值在之间。
可以看出，当序列较长时，上述方法的时间复杂度较高，当序列较长时，计算量会较大。针对这一问题，作者提出用傅里叶变换将序列从时域变换到频域，再进行比较，以节省计算量。
定义距离后，我们需要根据距离逻辑调整质心算法。
从图-4可以看出，时间序列数据的质心也是一条时间序列变化线，图中蓝线采用平均法(计算各点的平均值)计算质心；因为错位，峰谷被画成一条直线，所以不能正确表达形状走向。
K-Shape使用基于SBD的方法来计算质心。
该公式的目标是找到μk*并最大化质心μk和簇Pk中每个序列xi之间的相似性NCC。
算法一:首先用SBD()函数计算dist和y '，其中dist是时间序列x和y之间的距离，y '是y中与x最匹配的子段..这种方法用于解决波峰和波谷不对齐的问题，使它们相互抵消。
然后用基于线性代数方法将公式13展开成公式15:
最后，可以用瑞利商公式来简化:
瑞利商R(M，x)的一个重要性质是R的最大值等于矩阵M的最大特征值，最小值等于矩阵M的最小特征值..此时，你不必过多考虑R(M，x)中的x(也就是本题中的uk)。等式13简化为以下算法:
算法二:ShapeExtraction()根据聚类的当前质心C和聚类中所有点X计算出一个更合理的质心C’。
第2行:遍历簇中的所有点X(i)。
第3行:计算每个点和质心以及与质心最相似的线段X '之间的距离dist。
第4行:将最相似的片段添加到X’
第5行:X '转置乘以X生成一个方阵(X的平方)
第6行:为正则化创建一个矩阵Q。
第7行:正则化后生成矩阵m。
第8行:取矩阵M对应最大特征值时的特征向量，实现X '的特征提取
(以上解释为个人理解，不一定正确，仅供参考)
最终的聚类方法是通过迭代实现的，每次迭代分为两步:第一步是重新计算质心，第二步是根据与新质心的距离将每个序列重新分配到不同的簇中；迭代，直到标签不再改变。
算法三:聚类全过程由k-Shape()实现；
其中x是所有序列，k是聚类数，IDX是标签。
第3行:在标签稳定之前&；在迭代次数不超过100的条件下，继续迭代。
Line4-10:根据簇中的元素重新计算每个簇的质心c。
第11行-第17行:计算每个序列与每个质心之间的距离，并将其分配给一个新的簇(重新标记)。
K形算法每次迭代所需时间为:
o(最大值{n k m log(m)，n m^2，k m^3})
其中n是实例的数量，k是聚类的数量，m是序列长度。可以看出，这种算法的大部分计算成本取决于时间序列的长度m。但是这个长度通常比时间序列的个数小很多，所以对m的依赖不是瓶颈。在m非常大的极少数情况下，可以使用分段或降维来有效地减少序列的长度。
图-5比较了K形、ED和DTW模型的效果，可以看出在大多数情况下，SBD优于ED，在某些情况下，SBD优于DTW。但是SBD比DTW好，因为它更快。