比较两个点数组

Question

比较两个点数组

4

我正在尝试找到一种比较两个不同数据点数组相似性的方法。我在相似图案周围画了圆圈，想在让我们说每100个数据点的时间间隔内进行某种自动比较，并告诉那个时间间隔的相似性系数。正如您所看到的，它可能不是完全对齐的，因此点对点比较也不是一个好的解决方案（我想）。略微错位的模式也可能意味着它们匹配该模式（但显然系数较小）。

相似性可以意味着什么（1个系数是完美匹配，0或更低-根本不匹配）：

640到660点-非常相似（系数约为0.8）
670到690个点-相当相似（系数约为0.5-〜0.6）
720到780个点-假设相当相似（系数约为0.5-〜0.6）
790到810个点-完全相似（系数为1）

系数只是我对比较函数最终计算结果可能看起来的想法。

我阅读了SO上的许多帖子，但似乎没有解决我的问题。我会非常感激您的帮助。谢谢。

P.S.完美的答案将是提供一个函数的伪代码，该函数可以接受两个数据数组为参数（数据区间），并返回相似性系数。

点击此处查看要比较的点：链接

- Vytautas Butkus

你能澄清一下 - 你的“point”是什么类型的数据？它代表什么？（你提供的图形太小了，看不清） - Alma Do

1

我认为您正在寻找一些相关性或交叉相关性的度量。这对我来说过于复杂，无法从头开始尝试解释或提供伪代码。建议您查阅相关主题（例如维基百科）并回来提出更精确的问题。 - High Performance Mark

@Eugene的观点只是一个整数：arrayA = [0,1,2,0]和arrayB = [0,1,2,0]将完全匹配。但是，arrayA = [0,1,2,0]和arrayB = [0,0,1,2]将非常相似，但需要对齐。而arrayA = [0,1,2,0]与arrayB = [0,2,3,0]也意味着非常相似或相当相似的匹配，因为它们的模式相似。 - Vytautas Butkus

4

这个问题似乎不适合本站，因为它涉及到在数据中寻找相似性的好方法。它更适合发布在http://math.stackexchange.org或http://stats.stackexchange.org上。 - Chowlett

仅仅因为一些可能不知道[so]适当规则的用户点赞了你的问题，并不意味着你的问题符合[so]规则。允许任何与他人相关但不符合规则的内容通常会迅速严重降低任何网站的质量（有选择地允许是另一回事）。 - Bernhard Barker

显示剩余4条评论

4个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- collapsar · Answer 1

我认为HighPerformanceMarks的建议是完成工作的标准方式。

一个计算轻量级的替代方法可能是点积。

将两个数组分成相同的预定义索引间隔。
将每个间隔中的数组元素视为高维空间中的向量坐标。
计算两个向量的点积。

点积不会是负数。如果两个向量在它们的向量空间中是垂直的，那么点积将为0（事实上这就是“垂直”在更高维度中通常的定义），并且对于相同的向量它将达到最大值。

如果您接受垂直性的几何概念作为（不）相似性度量，那么这里就是解决方案。

注意：这是一种选择计算效率的特定启发式方法。我无法告诉您该过程和分离属性的数学/统计属性 - 如果您需要严格的分析，您可能会更好地使用相关理论，并应该将您的问题转发给math.stackexchange.com。

- Aaron · Answer 2

我认为高性能标记基本上已经给出了你的答案（交叉相关）。在我看来，大多数其他答案只是给你需要的一半（即点积加上与某个阈值进行比较）。然而，这不会考虑到信号与其自身的移位版本相似的情况。你需要计算这个点积N+M-1次，其中N、M是数组的大小。对于每次迭代，计算数组1和数组2的移位版本之间的点积。你可以把数组2看作是一个窗口，它在数组1上滑动。你需要从数组2的最后一个元素开始循环，只有与数组1的第一个元素重叠。

这个循环将为不同的移位量生成数字，你可以根据需要处理这些数字。也许你可以将它（或它的绝对值）与你定义的阈值进行比较，以判断两个信号是否“相似”。

最后，在许多情况下，信号被认为是其自身的缩放版本（在幅度上而不是时间缩放），因此在计算交叉相关之前必须进行归一化处理。通常通过调整数组的元素使其与自身的点积等于1来实现这一点。只需小心确保在数值上对您的应用程序有意义，即整数并不适合在0和1之间进行缩放:-)

- Bhargav Ponnapalli · Answer 3

我的尝试：

Total_sum=0
1. For each index i in the range (m,n)
2.     sum=0
3.     k=Array1[i]*Array2[i]; t1=magnitude(Array1[i]); t2=magnitude(Array2[i]);
4.     k=k/(t1*t2)
5.     sum=sum+k
6. Total_sum=Total_sum+sum
Coefficient=Total_sum/(m-n)

如果所有值都相等，那么总和在每种情况下都会返回1，而total_sum将返回(m-n)*(1)。因此，当被(m-n)除时，我们得到的值为1。如果图形是完全相反的，我们得到-1，对于其他变化，返回-1和1之间的值。
当y范围或x范围巨大时，这并不高效。但是，我只是想给你一个想法。

另一个选择是执行广泛的xnor操作。

1. For each index i in the range (m,n)
2.     sum=1
3.     k=Array1[i] xnor Array2[i]; 
4.     k=k/((pow(2,number_of_bits))-1) //This will scale k down to a value between 0 and 1
5.     sum=(sum+k)/2

Coefficient=sum

这个有帮助吗？

- Antti Huima · Answer 4

你可以为长度为N的包含区间[-1, 1]中的数字的两个向量A和B定义距离度量，例如：

 sum = 0
 for i in 0 to 99:
   d = (A[i] - B[i])^2  // this is in range 0 .. 4
 sum = (sum / 4) / N // now in range 0 .. 1

现在，对于完全相反的向量（一个是全1，另一个是全-1），返回距离1，对于相同的向量返回0。

您可以通过以下方式将其转换为系数：

 coeff = 1 - sum

然而，这是一种粗略的方法，因为它没有考虑到您要比较的信号之间可能存在水平失真或偏移的事实，因此让我们看看一些应对这种情况的方法。

您可以对两个数组进行排序（例如按升序），然后计算距离/系数。这返回比原始度量更相似的结果，并且不关心信号的排列/偏移。

您还可以计算差分并计算距离/系数，然后也可以对其进行排序。使用差分的好处是它消除了垂直偏移。排序的差分消除了水平偏移，但仍然比排序的原始数据点更好地识别不同的形状。

然后，您可以对不同的系数进行平均处理。以下是更完整的代码。下面的例程计算给定大小的数组A和B的系数，并首先取d个不同的差分（递归）。如果sorted为true，则最终（分化）数组将被排序。

procedure calc(A, B, size, d, sorted):
  if (d > 0):
     A' = new array[size - 1]
     B' = new array[size - 1]
     for i in 0 to size - 2:
        A'[i] = (A[i + 1] - A[i]) / 2   // keep in range -1..1 by dividing by 2
        B'[i] = (B[i + 1] - B[i]) / 2
     return calc(A', B', size - 1, d - 1, sorted)
  else:
     if (sorted):
       A = sort(A)
       B = sort(B)
     sum = 0
     for i in 0 to size - 1:
       sum = sum + (A[i] - B[i]) * (A[i] - B[i])
     sum = (sum / 4) / size
     return 1 - sum // return the coefficient

procedure similarity(A, B, size):
  sum a = 0
  a = a + calc(A, B, size, 0, false)
  a = a + calc(A, B, size, 0, true)
  a = a + calc(A, B, size, 1, false)
  a = a + calc(A, B, size, 1, true)
  return a / 4 // take average

如果想要尝试一些完全不同的东西，你也可以使用FFT运行傅里叶变换，然后对返回的频谱进行距离度量。