10

几天来，我一直在尝试在 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, . . . 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 道歉，但我没有更简洁的方式将关键信息提供给读者。

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

4

5 回答 5

4

最小二乘问题要求找到一条最适合给定点的直线，并且有一个很好的封闭形式解决方案。该解决方案用作解决分段最小二乘问题的原语。

在分段最小二乘问题中，我们可以有任意数量的分段来拟合给定的点，并且我们必须为使用的每个新分段支付成本。如果使用新线段的成本为 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/

于 2013-11-27T09:35:30.923 回答
3

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

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一点，e(i,i+1)因为将一条线拟合到一个点不会产生错误，并且只产生两个点。

于 2010-11-03T06:11:23.820 回答
1

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

幸运的是，成本是根据您尝试解决的同一问题的子问题计算的，幸运的是，当您移动到下一个点 j 时，您已经解决了这些较小的子问题。因此，在新点 j 处，您试图在点 1 和 j 之间找到一个最佳点 i，以分离出包含 j 的新线段，并最小化成本：optimal_cost_up_to(i) + cost_of_split + cost_of_lsq_fit(i+1 ,j)。现在令人困惑的部分是，在任何时候，您似乎只是在找到一个拆分，但实际上所有之前的拆分都是由optimal_cost_up_to(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)。

于 2010-11-03T07:19:19.597 回答
0

动态编程的基本前提是递归地优化（降低“成本”或在这种情况下为错误）问题，同时存储子问题的成本，这样它们就不会被重新计算（这称为记忆化）。

有点晚了，所以我不会太详细，但看起来你最有问题的部分是核心 DP 本身。由于“分段”质量，此处需要 DP。正如您的 PDF 所示，通过最小二乘法找到最佳拟合线很简单，并且不需要 DP。

Opt(n) - e(i, n) + C + Opt(i-1) --- 我们的成本函数，其中
C 是新线段的恒定成本（没有它，问题很简单，我们只需制作新的每两点的线段）
e(i, n) 是点 i 到 n 的误差，其中一个线段（非递归）
Opt(i-1) 是从第一个点到 (i-1) 递归的最小成本)th

现在算法

确保点列表按 x 值排序
M[0] = 0 --- 自我解释
对于 i < j 的所有对 (i, j)：查找 e(i,j) ----（这将需要嵌套for/foreach 循环，或一种理解类型的结构。将这些值存储在二维数组中！）
For (j=1..n): M[j] = min([Opt(j) for i in range(1,j) )]

所以基本上，找到任意两个可能点之间的单线成本，存储在 e 中
找到 j 之前的最小成本，对于 j 在 1 和 n 之间。一路上的值将有助于以后的计算，所以存储它们！请注意， i 也是 Opt 的参数。M[n] 是总优化成本。

给您的问题-您如何确定分段发生的位置？你如何使用它和 M 来确定线段的集合？

希望这可以帮助！

于 2010-11-03T06:10:35.227 回答
0

以下是分段最小二乘问题的动态规划的公式：

在此处输入图像描述

在这里，表示拟合到 的点上M[j]的最小误差（回归）线，我们可以通过保持反向指针数组和动态规划数组来跟踪具有最小误差（MSE）的起点。此外，表示绘制一条线的成本（作为拟合线数的惩罚）。最优子结构性质是由贝尔曼方程。ijic

这是我python对上述 DP 算法的实现，在以下带有点的 2D 数据集上(xs, ys)（散点图如下）：

在此处输入图像描述

def ls_fit(xs, ys, m):
    a = (m*sum(xs*ys)-sum(xs)*sum(ys)) / (m*sum(xs**2)-sum(xs)**2)
    b = (sum(ys)-a*sum(xs)) / m
    return a, b

def compute_errors(xs, ys):
    n = len(xs)
    e = np.zeros((n,n))
    for j in range(n):
        for i in range(j+1):
            m = j-i+1
            if m > 1:
                a, b = ls_fit(xs[i:i+m], ys[i:i+m], m)
                e[i,j] = sum((ys[i:i+m] - a*xs[i:i+m] - b)**2)
    return e

def build_DP_table(e, n):
    M = np.zeros(n)
    p = np.zeros(n, dtype=int) # backpointers
    for j in range(1, n):
        cost = [e[i,j] + c + M[i-1] for i in range(j)]
        M[j] = np.min(cost)
        p[j] = np.argmin(cost)
    return M, p

现在绘制使用动态规划公式获得的最小二乘线段：

c = 10
tol = 2
starts = np.unique(p)
drawn = set([])
plt.plot(xs, ys, 'g.')
for start in starts:
    indices = np.where(abs(p-start) < tol)[0]
    a, b = ls_fit(xs[indices], ys[indices], len(indices))
    if not (a, b) in drawn:
        plt.plot([xs[min(indices)],xs[max(indices)]], [a*xs[min(indices)]+b, a*xs[max(indices)]+b], linewidth=3, 
                 label='line: ({:.2f}, {:.2f})'.format(a,b))
        drawn.add((a,b))
plt.legend()

在此处输入图像描述

正如预期的那样，DP 找到了适合数据的 3 条最佳最小二乘线 ( L=3)。

于 2021-12-03T22:29:43.307 回答