序列数据分割算法

数据挖掘 机器学习 聚类 顺序
2021-09-19 11:18:27

我有一个长度为 N 的大向量序列。我需要一些无监督学习算法将这些向量分成 M 个段。

例如:

在此处输入图像描述

K-means 不适合,因为它将来自不同位置的相似元素放入单个集群中。

更新:

真实数据如下所示:

在此处输入图像描述

在这里,我看到 3 个集群: [0..50], [50..200], [200..250]

更新 2:

我使用了修改后的 k-means 并得到了这个可接受的结果:

在此处输入图像描述

集群边界: [0, 38, 195, 246]

3个回答

请参阅我上面的评论,这是根据我从您的问题中理解的答案:

正如您正确指出的那样,您不需要Clustering而是Segmentation实际上,您正在寻找时间序列中的变化点答案实际上取决于数据的复杂性。如果数据与上面的示例一样简单,您可以使用在变化点处过冲的向量的差异,并设置一个阈值来检测这些点,如下所示: 在此处输入图像描述 如您所见,例如阈值为 20(即dx<20dx>20) 将检测点。当然,对于真实数据,您需要进行更多调查以找到阈值。

预处理

请注意,变化点的准确位置和段的准确数量之间存在权衡,即如果您使用原始数据,您将找到确切的变化点,但整个方法对噪声敏感,但如果您平滑首先您的信号可能找不到确切的变化,但噪声影响会小得多,如下图所示:

在此处输入图像描述 在此处输入图像描述

结论

我的建议是首先平滑您的信号并采用简单的聚类方法(例如使用GMM)来找到信号中段数的准确估计。有了这些信息,您就可以开始查找受您从前一部分中找到的段数限制的变化点。

我希望这一切都有帮助:)

祝你好运!

更新

幸运的是,您的数据非常简单明了。我强烈推荐降维算法(例如简单的PCA)。我想它揭示了你的集群的内部结构。将 PCA 应用于数据后,您可以更轻松、更准确地使用 k-means。

一个严肃的(!)解决方案

根据您的数据,我看到不同段的生成分布是不同的,这对您来说是一个很好的机会来分割您的时间序列。请参阅此(原始存档其他来源),这可能是解决您的问题的最佳和最先进的解决方案。本文背后的主要思想是,如果时间序列的不同部分是由不同的底层分布生成的,您可以找到这些分布,将其设置为聚类方法的基本事实并找到聚类。

例如,假设一个长视频,前 10 分钟有人骑自行车,后 10 分钟他在跑步,第三分钟他坐着。您可以使用这种方法对这三个不同的细分(活动)进行聚类。

众所周知,K-means 聚类会给出局部最小值,具体取决于您对聚类中心的初始初始化。

但是,我认为 k-means 分割可以在全球范围内解决,因为我们在寻找解决方案时不会进行任何置换。

我可以从您的评论中看到,您最终确实做到了细分。请问可以给点意见吗?你的解决方案是最好的解决方案吗?或者您是否满足于一个足够好的解决方案?

只是作为一个建议:您可以尝试使用 DBSCAN 算法,因为它通常比 K-means 更有效地进行聚类

否则,如果您想尝试一些新的聚类方法并学习一些有趣的东西,我建议您通过持久图尝试一些拓扑数据分析。我要给你一个很好的简单介绍:)

https://towardsdatascience.com/persistent-homology-with-examples-1974d4b9c3d0