大家好，如果您还对时间序列聚类不太了解，没有关系，今天就由本站为大家分享时间序列聚类的知识，包括时间序列聚类算法的问题都会给大家分析到，还望可以解决大家的问题，下面我们就开始吧！
本文目录
一、读《不等长时间序列滑窗STS距离聚类算法》论文
1）时间序列聚类的研究一般采用等长划分，会丢失重要特征点，对聚类结果有负面影响。
2）采用时间序列测量值不能准确度量相似度。
如下埃博拉出血热、卫生部在数值上很相似，但教育部和卫生部在形状更相似。若是以形状作为度量传统的欧氏距离可能就不太合适了。
不等长时间序列滑窗STS聚类算法：
1）通过标准分数z_score预处理，消除时间序列观测值数量级差异的影响。
2）更改了相似度计算的方式，采用基于滑窗的 *** 计算不等长序列的距离。
3）采用类k-means的聚类算法的中心曲线计算 *** 。
时间序列数据因其趋势信息的直观展现形式，广泛应用于社交 *** 、互联网搜索和新闻媒体数据分析中。例如：Google应用搜索流感的相关信息的时间序列预测流感爆发趋势。根据某话题热度时间序列数据趋势的规律性，通过聚类区分不同类型的时间序列数据。同一类簇的Twitter话题具有相同或相似的发展趋势，进而应用于话题的发展趋势的预测。
时间序列聚类算法可以分为两类。
1）基于原始数据的时间序列聚类算法。
2）基于特征的时间序列聚类算法。
基于特征的时间序列聚类算法指根据原始数据从时间序列中提取形态特征（极值点位置、分段斜率）、结构特征（平均值、方差等统计值特征）、模型特征（模型的预测值），从而根据这些特征值进行聚类。这类 *** 的优点解决了不等长时间序列聚类问题，缺点是减弱了原始数据值得影响，聚类的形状趋势信息往往比较粗糙。
STS距离计算的是累加时间序列间每个时间间隔斜率差的平方，公式
如上图所示，g1、g2和g2、g3的欧式距离的数值更相近。g1、g2的STS距离大于g2、g3的数值。在形状距离上，STS距离计算方式表现更好，一定程度上可以解决欧式距离度量时间序列局部特征信息确实和受观测数值数量级差异影响大的问题，但是依旧无法度量不等长时间序列的距离。
如上图所示，当计算不同长度的时间序列的s和r的距离时，先不断平移时间序列s，然后找到s和r距离最近的字段，就如同上图虚线之间的位置，此时s和r距离最近，这个最近距离作为s和r之间的距离。
z-score标准分数用数据观测值和观测值平均值的距离代替原观测值。z-score处理后的数据平均值为0，标准差为1。标准差的作用是统一量纲，去除数值的数量级差异影响。
本论文提出了形状距离的不等长时间序列的聚类 *** 。我们可以学到的有
1）z-score统一量纲，消除数值数量级差异，聚类效果更好。
2）计算x和y时间序列的STS距离，可以平移其中一个时间序列，求最小值作为STS距离值，这就消除了同一时间序列不同起始点的影响。
二、聚类算法可以和时间序列相结合做预测吗
1、如果你处理的数据本身就是时间序列数据，如果采用聚类的话，就会忽略数据的顺序信息。也就是说并不知道得到那些簇之间的先后顺序，既然不知道顺序用时间序列来坐预测就没有什么意义。
2、你对数据先聚类后预测，我大致能了解你的意图。你可以试着把聚类算法换成序列模式挖掘算法。比如，利用PrefixSpan找出频繁出现的序列模式，那样的话，给定一个序列模式，直接去匹配更符合的频繁模式，就可以做简单的预测。
3、此外，针对时间序列预测，有专门的比如ARIMA这种算法来进行预测，为什么要先聚类了？
三、什么是时间序列聚类呀~~详细点儿的
理解了时间序列与普通数据的区别就明白了。按顺序排列的多个普通数据点构成了时间序列，比如一个单词或短语的发音，在这个发音时间内，频率随时间按一定规律变化，幅值也按自己的规律变化；如果你通过分析很多小段的语音，发现了相似的（频率、幅值）变化规律，就把它们聚类为同一个单词或短语。不知这样比喻是否恰当。
四、论文阅读_时序聚类K-Shape
1、这是一篇发表于2015年SIGMODE数据管理国际顶会的论文，它主要针对时序数据的聚类问题，提出了K-Shape *** 。与以往的 *** 相比，它优化了距离计算 *** ，质心计算 *** ，还引入了提取频域特征 *** ，以提升效率。
2、作者认为它是一种独立于领域、高精度、高效率的时间序列聚类 *** 。
3、我觉得相对于传统 *** ，它聚类效果更好；相对于DTW类 *** ，效果稍差，但速度快很多。毕竟从原理来看，K-Shape只考虑了纵向拉伸和横向平移，而DTW还考虑了横向拉伸。
4、 K-Shape原理和K-means相似，不同在于它改进了距离计算 *** ，并优化了质心计算 *** 。一方面支持振幅缩放和平移不变性，另一方面计算效率也比较高，并且不用手动设置参数，便于扩展到更多领域。
5、距离算法用于计算两组时序数据的差异，其中的核心问题是如何处理时序数据的形变，论文中的图-1展示的心电图数据被分为A/B两类：
6、其中A类的特点是：上升->下降->上升，而B类的特点是：下降->上升。图-1的右下图展示了理想的建模效果，它识别到了相同的模式，而忽略了幅度和相位的差异。人们也更倾向使用这种 *** 计算距离，很多时候甚至认为距离计算 *** 比聚类 *** 更加重要。一般来说，支持振幅缩放和平移不变性的 *** ，计算成本较高，难以对大数据量建模。
7、 K-Shape之前的主流距离算法如下：
8、 K-Shape用互相关 *** 计算两个时间序列的距离。假设有X和Y两个时间序列，序列长度均为m。为实现平移不变性，Y不变，一步一步划动X，并计算每一步X与Y的差异。
9、如上图所示：假设绿 *** 域为Y，白 *** 域为划动的X，每一行s（step)向前划动一步，序列长度为m=4，s∈(-3,3)共7种取值，w是所有移动的可能性2m-1=7次，w-m=s=k，也就是下面公式中的对齐位置（对齐逻辑贯穿整个算法）。
10、利用R来计算x和y在每一步的相似度，在对的上(在X,Y中都存在)的位置计算点积，最终R是有效区域的点积之和（对每个对上的小块加和）。可以说，R越大两个序列越相似。
11、由于对比的每个子序列振幅不同，块数也不同，所以在对比时需要进行归一化，归一化 *** 有三种，第三种使用了互相关 *** ，效果更好。
12、其中图(a)使用z-normalization只做了对振幅的归一化，没有平移，可见在上述情况下，不平移（正对上）时对齐效果更好。从(b)(c)(d)可以看到：(d)图使用第三种 *** ，在最中间的点上相似度值更大（s=0时），即正对上的时候，其相似度更大，这与(a)呈现出的效果一致。而(b)(c)都认为最相似的情况出现在右侧，这明显不太对。
13、文中定义了基于形态的距离SBD（Shape-based distance），块重叠越多形状越像CC越大，对比所有可能位置的相似度值，取最相似的max(CC)，然后用1-max(CC)得到SBD，也就是说形状越相似，距离SBD越小，归一化后的NCC值在[-1,1]之间，因此，SBD值在[0,2]之间。
14、可以看到，用以上 *** 时间在序列较长时复杂度比较高，当序列较长时，计算量也会很大，为解决这一问题，作者提出使用傅里叶变换将序列由时域转到频域再比较，以节约计算量。
15、定义了距离之后，还需要根据距离逻辑来调整质心算法。
16、从图-4可以看到：时序数据的质心也是一条时序变化线，图中的蓝色线使用均值 *** （计算每个点的均值）来计算质心；由于错位，波峰和波谷被拉成了直线，因此不能正确地表达形状趋势。
17、 K-Shape使用基于SBD的方式计算质心。
18、该公式的目标是寻找μk*，使质心μk与该簇Pk中各条序列xi的相似度NCC更大。
19、算法一：先使用SBD()函数计算dist和y'，dist是时序x,y之间的距离，y'是y中与x最匹配的子段。使用这种 *** 解决了波峰波谷对不齐，以致相互抵消的问题。
20、然后用基于线性代数 *** ，将公式13展开成公式15：
21、最终可利用瑞利商公式加以简化：
22、瑞利商R(M,x)的一个重要的性质是：R的更大值等于矩阵M更大的特征值，最小值等于矩阵M最小的特征值。此时，就不用太考虑R(M,x)中的x(即本问题中的uk)。公式13被简化成以下算法：
23、算法二：ShapeExtraction()根据簇的当前质心C和簇内的所有点X，计算更合理的质心C'。
24、 line3:计算各点与质心的距离dist以及其中与质心最为相似的片断x'
25、 line4:将最为相似的片断加入X'
26、 line5: X'转置与X相乘生成一个方阵（X的平方）
27、 line8:取矩阵M对应更大特征值时的特征向量，以实现对X'的特征抽取
28、（以上说明为个人理解，不一定对，仅供参考）
29、最终的聚类 *** 通过迭代实现，每次迭代分为两步：之一步重新计算质心，第二步根据每个序列与新质心的距离将它们重新分配到不同的簇中；一直循环迭代到标签不再变化为止。
30、算法三：聚类的完整过程由 k-Shape()实现：
31、其中X是所有序列，k是簇的个数，IDX是标签。
32、 line3:在标签稳定前&迭代次数不超过100次的条件下，不断迭代
33、 line4-10：根据簇中的元素重新计算每个簇的质心C
34、 line11-line17：计算每个序列与各个质心的距离，并将它分配到新的簇中（重新打标签）。
35、 K-Shape算法每次迭代所需时间为：
36、 O(max{n·k·m·log(m), n·m^2, k·m^3})
37、其中n是实例个数，k是簇个数，m是序列长度。可见，该算法大部分的计算代价依赖于时间序列的长度m。然而，这个长度通常比时间序列的数目小得多，因此，对m的依赖不是瓶颈。在m非常大的极少数情况下，可以使用分段或降维 *** 来有效地减小序列的长度。
38、图-5对比了K-Shape、ED和DTW模型效果，可以看到绝大多数情况下，SBD好于ED，部分情况下SBD好于DTW。但SBD比DTW好在它速度更快。
如果你还想了解更多这方面的信息，记得收藏关注本站。
