基于非线性最小二乘的地块形状匹配

Question

什么是实现简单形状匹配算法的最佳方式，以将仅从8个点(x，y)插值的图与相似图(> 12000个条目)的数据库进行匹配，每个图具有>100个节点。该数据库有6类曲线图(在6种不同条件下测量的信号)，主要目的是找到正确的类别(因此，对于每一类，大约有2000个曲线图可供比较)。

8节点图将表示来自测量的实际数据，但现在我将通过从数据库中选择一个随机图，然后从其中选择8个点，然后使用高斯随机数生成器涂抹它来模拟这一过程。

实现非线性最小二乘法将8节点图的形状与数据库中的每个图进行比较的最佳方法是什么？你知道有什么c++库可以帮助你做到这一点吗？

是否有必要找到8节点图的实际公式(f(x))以使用最小二乘法，或者在请求点中使用插值就足够了吗，例如来自gsl库的插值？

Answer 1

你当然可以在不知道实际公式的情况下使用最小二乘法。如果所有的曲线图都是以相同的x值测量的，那么这就很容易了--您只需以正常的方式计算总和：

​

​

其中，y_i是8节点绘图中的一个点，sigma_i是该点上的误差，Y(x_i)是数据库中与y_i位于相同x位置的绘图的值。如果所有绘图都是以相同的x值测量的，您就会明白为什么这是微不足道的。

如果它们不是，您可以通过使用某个函数(如果您知道)或通过在点之间进行插值(如果您不知道)来拟合数据库中的绘图，来获得Y(x_i)。最简单的插值就是用直线连接这些点，然后在x_i上找到你想要的直线的值。Other interpolations可能做得更好。

在我的领域中，我们使用ROOT来做这类事情。但是，scipy有大量的函数，如果您不介意使用Python的话，它可能更容易入门。

你可能会遇到的一个主要问题是这两个地块不是独立的。Wikipedia suggests McNemar's test in this case.

您可能会遇到的另一个问题是，您的测试图中没有太多信息，因此您的结果将受到统计波动的很大影响。换句话说，如果只有8个测试点和两个匹配的曲线图，您如何知道底层函数是否真的相同，或者这8个点是否只是跳来跳去(在它们的误差栏中)，看起来像数据库中的曲线图--纯粹是偶然的！恐怕你不会真的知道。因此，测试良好的曲线图将包括假阳性(低纯度)，而一些测试不好的曲线图可能实际上是良好的匹配(低效率)。

要解决这个问题，您需要使用具有更多点的测试图，或者引入其他信息。如果您可以从数据库中丢弃由于其他原因无法匹配的绘图，这将会有很大帮助。