通过时间跟踪值的算法

Question

可能有一种已知的算法可以执行此操作，但是我无法利用自己的Google技能来找到它，所以我将尝试描述我必须做的事情以及到目前为止所做的事情。

我有一个系统特征值的来源，我想将其绘制成趋势。这些值是从算法实时返回的，每个值都有一组属性（幅度，相位，质量）。

但是，这些值会随时间出现和消失，而且我还会得到一些间歇性值，如果它们在较长时间内不重复（几个样本），我将忽略这些值。

例如，我可能会得到这些值：

Time     (Mag, Phase, Quality)
t = 1    (10.10, 0.90, 0.90);  (17.00, 0.02, 0,12)
t = 2    (10.15, 0.91, 0.89);  (17.10, 0.12, 0,12)
t = 3    (17.10, 0.12, 0,12)
t = 4    (10.25, 0.91, 0.89);  (17.12, 0.12, 0,12)
t = 5    ( 6.15, 0.41, 0.39);  (10.35, 0.91, 0.89);  (17.12, 0.12, 0,12)
t = 6    (10.20, 0.90, 0.85);  (17.02, 0.13, 0,11)
t = 7    ( 9.20, 0.90, 0.85);  (11.20, 0.90, 0.85);  (17.02, 0.13, 0,11)
t = 8    ( 9.80, 0.90, 0.85);  (11.80, 0.90, 0.85);  (17.02, 0.13, 0,11)

我想根据与先前值的相似性，通过时间跟踪这些值集。即在上面的示例中，我有两个主要趋势（Mag 10和Mag 17），并有几种特定情况：

1. 此刻我将很快丢失其中一个值（Mag 10在t = 3中丢失），
2. 此刻我很快就获得了单个样本的新的临时/无效读数（Mag 6中的t = 5），
3. 尚不清楚哪个集合对应于先前样本的时刻（Mag 9.2和Mag 11.2都可能是先前样本的Mag 10.2的延续，在t = 8中显然现在有两个不同的集合（Mag 9.8和Mag 11.8）。

[如果我只是将它们从系统中获得的值进行分组，那么我将无法获得它们的正确趋势，即，如果不进行跟踪，那么幅度将像这样：]

但是，将这些值与旧值正确匹配会导致这种趋势：

我已经编写了一种算法，可以通过相对于先前的“活动”集合有效地尝试集合的所有排列，从而跟踪时间值。它计算所有新值和先前已知值之间的差，这基本上是一种N^2算法，然后检查所有排列以找到最小的总距离（类似于N!复杂度）：

for each X in new_sets
     for each Y in existing_sets
           distance(X, Y) = calculate_distance(X, Y);

for each P in permutations(new_sets)
     total_distance = sum(distance(X, Y)) for all (X, Y) in permutation

permutation P with min total_distance is the best match
随着时间的流逝，如果几个样本中的测量值不匹配，我也会从existing_sets中删除测量值。

只要我没有太多的值，这就可以正常工作，但是当我开始跟踪10多个项目后，时间复杂度就会成问题。感觉也像是在重新发明轮子。

是否存在已知/更好的算法（就时间复杂度而言）？

[可能有一种已知的算法可以执行此操作，但是我无法利用自己的Google技能来找到它，因此，我将尝试描述我必须做的事情以及到目前为止所做的事情。我有一个来源...

Answer 1

在不限制来源行为的情况下，显然没有解决方案。如果我们可以说来自不同来源的幅度是合理地分开的，并且变化是相当小的，那么解决方案是将趋势保持在排序的顺序中。然后对它们进行二进制搜索，以找到最接近新读数的趋势。