c++ - 近正弦数据下界的(线性或多项式)回归算法

Question

我需要找到一条适合我的离散数据较低点的曲线。线性回归没问题，但多项式会很棒 :)

通常我不处理这样的任务，所以如果这是一个太简单的问题，请不要对我苛刻。我仍在进行研究，但我认为在这里提问也无妨。

最重要的是，任何点都不应该在这条线之下。据我所知，通常回归估计数据中间的一些线，这对我不利。我可以使用什么算法？我打算用 C++ 编写代码，但任何语言的示例都很棒。

图解说明:

蓝色 - 我的数据橙色 - 足够好的解决方案绿色 - 很好的解决方案!

谢谢!

Answer 1

嗯，您还没有向我们提供相关数据，所以我使用您的图像作为输入。线性下界的计算非常简单:

1. 为您的数据计算边界框
2. bin 在 bbox 中搜索“所有有效”行作为下限

这里是简单的 C++ 示例:

//---------------------------------------------------------------------------
double *pnt=NULL; int pnts=0;   // input data points pnt[pnts]={ x0,y0,x1,y1,x2,y2,... } loaded during init of app from image
double fit0[4]={0,0,0,0};       // output line endpoints fit0 = { x0,y0,x1,y1 }
//---------------------------------------------------------------------------
void compute()
    {
    int i,j;
    double x,x0,x1,y,y0,y1,yy,a,a0,a1,X0;
    // bbox
    x0=x1=pnt[0]; X0=x0;
    y0=y1=pnt[1];
    for (i=0;i<pnts;)
        {
        x=pnt[i]; i++;
        y=pnt[i]; i++;
        if (x0>x) x0=x;
        if (y0>y){y0=y; X0=x; } // X0 is the point where y is minimal
        if (x1<x) x1=x;
        if (y1<y) y1=y;
        }
    // fit0 (line)
    fit0[0]=X0;
    fit0[1]=y0;
    fit0[2]=x1;
    fit0[3]=y0;
    for (a0=y0,a1=y1,j=0;j<10;j++)          // bin search accuracy iterations
        {
        a=0.5*(a0+a1);
        for (i=0;i<pnts;)
            {
            x=pnt[i]; i++;                  // tested point from data
            y=pnt[i]; i++;
            yy=y0+((x-X0)*(a-y0)/(x1-X0));  // coresponding y value of fited line
            if (yy>y) { i=-1; break; }      // too big
            }
        if (i>=0){ a0=a; fit0[3]=a; }       // valid line
         else      a1=a;                    // invalid line
        }
    }
//---------------------------------------------------------------------------

所以我将边界设置为线。它的第一个端点是从左边开始的第一个全局最小值，我对第二个端点进行二进制搜索。其中 x 是 x 的全局最大值，y 在全局最小值和最大值之间进行测试(记住最佳解决方案)。此处预览: