python - 分段最小二乘的动态规划算法

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) 是线段的一部分。然后注释说最优解是'is optimal solution for {p1, . . . pi−1} 加上通过 {pi , . . . pn}'。这对我来说意味着，我们到达点 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++ 实现:http://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/