拟合未知曲线

Question

拟合未知曲线

10

我发现了一些相关的问题（例如这个，这个，这个和这个），但它们都是处理将数据拟合到已知曲线的问题。是否有一种方法可以将给定的数据拟合到未知曲线上？也就是说，给定一些数据，算法将给出一个函数或多个函数的总和来拟合数据。我正在使用C编程，但我完全不知道如何使用gsl包来实现这一点。我愿意使用任何能够（理想情况下）通过C进行传输的工具。但关于我应该寻找什么方向的任何帮助都将不胜感激。

编辑: 基本上这是我收集的实验（物理）数据，因此数据将经过添加的高斯分布噪声修改某些趋势。通常趋势将是非线性的，因此我认为线性回归拟合方法将不适用。至于排序，数据是按时间顺序排列的，因此曲线必须按照该顺序进行拟合。

- Kitchi

1

你可能会喜欢阅读维基百科上关于曲线拟合的文章。[http://en.wikipedia.org/wiki/Curve_fitting] - pmg

“我的意思是，给定一些数据，算法将给出一个适合数据的函数或函数之和。”：那么你的曲线就被称为某些函数的总和。我猜测你想要的可能是泰勒级数和傅里叶级数，因为它们可以将一个函数表示为无限项的总和。 - Thomas C. G. de Vilhena

2

这有点不够明确。有很多曲线拟合方法（回归、泰勒级数、傅里叶、样条等），但它们各自针对特定的应用。如果不了解数据的一些信息（即首先生成基础趋势的原因），就很难给出具体的答案。 - Oliver Charlesworth

你知道数据的排序（也称为参数化）吗？或者它是否也会根据曲线拟合而改变？例如，如果你的点被排序为：{Pt1，Pt2，Pt3}；当投影到曲线上时，你希望它们保持相同的顺序，还是可能变成类似{Pt2，Pt1，Pt3}这样的顺序？如果排序是固定的，@amit 的回答似乎是合理的。否则，还有更复杂的算法可以根据某些误差对数据集进行排序，并同时提供拟合结果。请在你的问题中详细说明这一点。 - meyumer

3个回答

4

您可能希望使用（快速）傅里叶变换将数据转换为频域。通过变换的结果（一组振幅、相位和频率），即使是最复杂的数据集也可以用几个函数（谐波）来表示：

r * cos(f * t - p)

r代表谐波振幅，f代表频率，p代表相位。

最后，未知数据曲线是所有谐波的总和。

我在R中已经完成了这个过程（您可以看到一些示例），但我相信C语言也有足够的工具来处理它。也可以将C和R进行管道连接，但我不是很了解。这里可能会有所帮助。

这种方法对于大块数据非常有效，因为它具有以下复杂性：

1）使用快速傅里叶变换（FFT）分解数据= O（n log n）

2）使用结果组件构建函数= O（n）

- Helio Santos

1

但是这样做会不会更加计算密集，因为我必须先进行傅里叶变换，然后再找出组成部分呢？虽然对于任意曲线来说，这听起来确实很可靠... - Kitchi

@Kitchi 快速傅里叶变换（FFT）比经典的离散傅里叶变换快得多（http://blogs.mathworks.com/steve/2012/05/01/the-dft-matrix-and-computation-time/）。找出组件并不是问题，因为它的复杂度大约是O(n)。 - Helio Santos

一些快速傅里叶变换的实现具有O(n log n)的复杂度，这意味着它们具有较小的计算成本。这意味着它们可以轻松处理大量数据，而使用O(n^2)的多项式插值方法则无法做到。 - Helio Santos

4

另一种选择是使用线性回归，但应用于多维数据。

关键在于人工生成额外的维度。您可以通过对原始数据集隐含一些函数来实现。常见的用法是生成多项式以匹配数据，因此在这里，您隐含的函数是f(x) = x^i，其中i < k（其中k是要获取的多项式的次数）。

例如，对于数据集(0,2),(2,3)和k = 3，您将获得额外的2个维度，因此您的数据集将为：(0,2,4,8),(2,3,9,27)。

线性回归算法将找到多项式p(x) = a_0 + a_1*x + ... + a_k * x^k的值a_0,a_1,...,a_k，该多项式最小化了每个点与预测模型（p(x)的值）之间的误差。

现在的问题是 - 当您开始增加维度时 - 您正在从欠拟合（一维线性回归）移动到过拟合（当 k==n 时，您有效地进行多项式插值）。

要“选择”最佳的 k 值 - 您可以使用交叉验证，并选择根据您的交叉验证最小化误差的 k。

请注意，这个过程可以完全自动化，您只需要迭代地检查所需范围内的所有 k 值，并选择根据交叉验证最小化误差的模型。

(1) 这个范围可以是 [1,n] - 虽然这可能会非常耗时，但我会选择 [1,sqrt(n)] 或者甚至是 [1,log(n)] - 但这只是一种直觉。

- amit

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

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

- amit · Accepted Answer

你可能正在寻找与数值分析相关的多项式插值。

在多项式插值中，给定一组点(x,y)，你试图找到最适合这些点的最佳多项式。其中一种方法是使用牛顿插值，这种方法相当容易编程。

数值分析和插值特别是广泛研究，你可能能够得到多项式误差的一些不错的上限。

请注意，由于你正在寻找最适合你的数据的多项式，而函数实际上并不是一个多项式 - 当远离你的初始训练集时，误差的规模会大幅增加。

此外，请注意，您的数据集是有限的，而可以适合数据的函数数量是无限的（实际上是不可枚举的无穷大），因此哪一个是最好的可能取决于您实际要实现的目标。

如果您正在寻找适合您的数据的模型，请注意，线性回归和多项式插值位于比例的两端：多项式插值可能过度拟合模型，而线性回归可能欠拟合它，应使用什么完全取决于具体情况，并因应用程序而异。

简单的多项式插值示例:

假设我们有数据(0,1),(1,2),(3,10)。

使用牛顿方法得到的表格¹如下:

0  | 1 |                 |
1  | 2 | (2-1)/(1-0)=1   |
3  | 9 | (10-2)/(3-1)=4  | (4-1)/(3-0)=1

现在，我们得到的多项式是以最后一个元素结尾的“对角线”：

1 + 1*(x-0) + 1*(x-0)(x-1) = 1 + x + x^2 - x = x^2 +1

（这确实是我们使用的数据的完美匹配）

(1) 这个表格是递归创建的：前两列是 x 和 y 的值，每一列都基于前一列。一旦理解了它，实现起来非常容易，在牛顿插值的维基百科页面上有完整的解释。