分段最小二乘法，不了解这种动态规划的概念

Question

我尝试用Python实现这个算法已经有几天了。我不断地回到它，只是放弃和沮丧。我不知道怎么回事。我没有人可以请求帮助，也没有任何地方可以去寻求帮助，所以我来到这里。在

PDF警告：http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

我不认为这是一个清楚的解释，我肯定不明白。在

我的理解是：

我们有一组点（x1，y1），（x2，y2）。。我们想找到一些最适合这些数据的行。我们可以有多条直线，这些直线来自于给定的a和b论坛（y=ax+b）。在

现在算法从末尾开始（？）并假设点p（x_i，y_i）是线段的一部分。然后注释说最优解是{p1。π−1}正（最佳）线通过{pi。请注意。对我来说，就是到点p（x_i，y逖i），然后后退，找到另一条穿过其余点的线段。现在最佳解决方案是这两条线段。在

然后它进行了一个我无法理解的逻辑跳转，并说“假设最后一个点pn是从p_I开始的段的一部分，如果Opt（j）表示第一个j点的成本，e（j，k）表示 通过点j到k的最佳直线的误差，然后Opt（n）=e（i，n）+C+Opt（i−1）“

还有算法的伪代码，我不明白。我知道我们想迭代点列表，找到最小化OPT（n）公式的点，但是我没有遵循它。这让我觉得很蠢。在

我知道这个问题是个棘手的问题，不容易回答，但我只是在寻找一些关于理解这个算法的指导。我为PDF文件道歉，但我没有一种更简洁的方式来向读者传达关键信息。在

感谢您抽出时间阅读本文，我很感激。在

Answer 1

最小二乘问题要求找到一条与给定点最匹配的直线，并且有一个很好的闭合形式解。将此解作为求解分段最小二乘问题的基元。在

在分段最小二乘问题中，我们可以有任意数量的线段来拟合给定的点，并且我们必须为每一个使用的新线段支付费用。如果使用新线段的成本为0，我们可以通过将一条单独的线穿过每个点来完美地拟合所有点。在

现在假设我们正在寻找与n个给定点最匹配的线段集。如果我们知道n-1子问题的最佳解：第一个点的最佳拟合，前2个点的最佳拟合，…，前n-1个点的最佳拟合，那么我们可以计算出含有n个点的原问题的最佳解，如下所示：

第n个点位于一个线段上，该线段从某个较早的点i开始，对于某些i=1，2，…，n。我们已经解决了所有较小的子问题，即少于n个点，因此我们可以找到n个点的最佳拟合，从而使：

第一个i-1点的最佳拟合成本（已计算）+ 最适合点i到n的单线成本（使用最小二乘问题）+ 使用新段的成本

使上述数量最小化的i值给出了一个解决方案：对子问题i-1和通过点i到n的线段使用最佳拟合

如果你需要更多帮助，我已经写了一个算法的解释，并在这里提供了C++实现：^ a1}

Answer 2

最棘手的部分，动态编程部分，是部分

for j = 1 to n
    M[j] = min_(1=<i=<j) ( e(i,j) + C + M[i-1])

其中M[0] = 0在前面完成，n是数据点的总数。另外，下划线表示后面括号中的部分应该下标。教授完全可以用OPT代替M，这在其他一些大学的讲座中也有，你可以在网上找到（看起来几乎一样）。现在，如果你看一下我上面的代码块，你会发现一个不同。我用了M[i-1]，你的教授用了M[j-1]。你教授的伪代码有误。你甚至可以回顾一下之前的幻灯片，看看他在错误函数中的正确性。在

基本上，对于每个j，你会找到一个点i来画一条直线到j，这样它的误差，加上增加这条额外的线（C）的成本，再加上使所有线段达到i的成本（这已经被最佳地选择）最小化。在

另外，请记住e(i,i) = 0和{}，因为将一条直线拟合到一个点上不会产生误差，而且只会产生两个点。在

Answer 3

从点1开始，直到j点的最佳解决方案，必须在最后一条线段中包含新的端点j，所以问题就变成了我必须在哪里放置最后一条分割线以最小化最后一条线段的成本？在

幸运的是，成本是根据你试图解决的同一问题的子问题来计算的，幸运的是，你已经在移到下一个点j时解决了这些较小的子问题。所以在新的点j，你试图在点1和j之间找到一个最佳点i，分割一条包含j的新线段，并使成本最小化：最优的_cost_up_to（i）+cost_split+cost_lsq_fit（i+1，j）。现在让人困惑的是，在任何一点上，你可能看起来只是在寻找一个单一的分割，但事实上，所有先前的分割都是由最优的“成本”决定的，直到（i），而且由于你已经计算出了所有这些点到j的最优成本，然后你只需要记住答案，这样算法就不必在每次前进一个点时都重新计算这些成本。在

在python中，我可能会使用字典来存储结果，不过对于这种动态编程算法，数组可能会更好。。。在

不管怎样。。。在

    def optimalSolution(points,split_cost)
        solutions = {0:{'cost':0,'splits':[]}}
        for j in range(1,len(points)):
            best_split = None
            best_cost = lsqFitCost(points,0,j)
            for i in range(0,j):
                cost = solutions[i]['cost'] + split_cost + lsqFitCost(points,i+1,j)
                if cost < best_cost:
                   best_cost = cost
                   best_split = i
            if best_split != None:
                solution[j] = {'cost':best_cost,'splits':solution[best_split]['splits']+[best_split]}
            else:
                solution[j] = {'cost':best_cost,'splits':[]}
        return solutions

它不漂亮，而且我还没有检查过（可能有一个错误涉及到不分割是最好的成本的情况），但希望它能帮助您走上正确的道路？注意，lsqFitCost在每次迭代中都要做大量的工作，但是对于像这样的最小二乘法拟合，你可以通过维护计算中使用的运行和来降低成本。。。你应该谷歌最小二乘法拟合更多信息。这可以使lsqFitCost保持不变，因此总时间为O（N^2）。在