algorithm - 嘈杂数据集中的二维模式匹配

Question

我有一个数据集，由 RFID 天线在两个人移动的 2D x,y 位置上给出。一个人携带 3 个 RFID 标签，而另一个人携带 4 个标签。两者都沿着 y 轴移动，如下所示。红色和青色是路径，两个人在走。

x,y 比例的位置图如下所示。

理想情况下，橙色、黄色、蓝色和灰色线(RFID x、y 数据点)应该位于正水平线上，而下面的绿色、深蓝色和天蓝色线应该位于负水平线上。

问题 虽然线条不是直线，但出现了一种视觉模式，可以将零线以上聚集在一起，零线以下聚集在一起。我的问题是可以使用什么算法/方法来比较这些模式并将它们聚集在一起。 (所以理想情况下答案应该是，4 行以上在一个集群中，3 行以下在另一个集群中。)

很难将其视为线性运动，因为人们可以以非线性方式行走。所以最佳拟合线不起作用。非常感谢任何建议或阴影。

Answer 1

您想了解聚类时间序列 (1d) 或轨迹 (2d) 的方法。

两者的方法几乎相同。首先，你想找到一个合适的距离度量(相异性度量)，其次，你决定一个合适的聚类算法。

可能的距离度量

以下是您可以使用的一些距离示例，每个距离都有一些简短的参数:

• 欧氏距离:非常基础
• 动态时间环绕 (DTW):可以解释轮类
• Longuest Common Subsequence (LCSS):考虑到偏移并可以处理异常值
• 使用 Real Penalty (EDP) 编辑距离:考虑到偏移并可以处理异常值

例如，可以在 this paper 中找到更多详细信息。 .可以找到距离的实现 here .

可能的聚类算法

• K-Means
• DBSCAN
• Single Linkage clustering

您通常可以将任何距离度量与任何基于距离的聚类算法相结合。

意见

查看您的数据，我会尝试将 DTW 作为距离度量。如果您期望两个集群，那么 k=2 的 K-Means 应该可以工作。否则你可以尝试单链接聚类，它会给你类似于下图的东西。