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 = 1、2、...、n の場合、以前の点 i から始まります。すべての小さな部分問題、つまり、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 はデータ ポイントの総数です。また、アンダースコアは、その後の括弧内のセクションに添字を付ける必要があることを意味します。教授は M の代わりに OPT を使用した可能性があります。これは、Web で見つけることができる他の大学の講義で行われています (ほとんど同じように見えます)。上記の私のコードブロックと講義のコードブロックを見ると、違いに気付くでしょう。私は を使用M[i-1]し、あなたの教授は を使用しM[j-1]ました。教授の疑似コードのタイプミスです。以前のスライドを振り返ってみると、彼がそこにあるエラー関数でそれを正しくしていたことがわかります。

基本的に、各 j について、点 i から j に線を引く点 i を見つけて、その誤差に加えて、この余分な線を追加するコスト (C) に加えて、i までのすべての線分を作成するコスト (既に最適に選択されている) が最小化されます。

また、線を点に当てはめてもエラーが発生せず、2 つの点だけになることe(i,i) = 0も覚えておいてください。e(i,i+1)

于 2010-11-03T06:11:23.820 に答える
1

ポイント 1 からポイント j までの最適なソリューションは、最後の線分に新しいエンドポイント j を含める必要があるため、この最後の線のコストを最小限に抑えるために、最後の分割をどこに配置する必要があるかという問題になります。セグメント？

幸いなことに、コストは解決しようとしている同じ問題の部分問題の観点から計算されます。幸いなことに、次の点 j に移動するまでに、これらの小さな部分問題は既に解決されています。したがって、新しい点 j で、点 1 と j の間の最適な点 i を見つけて、j を含む新しい線分を分割し、コストを最小化しようとしています。 、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 は各反復で多くの作業を行う必要があることに注意してください。ただし、このような最小二乗直線近似では、計算で使用される実行中の合計を維持することで、このコストを大幅に削減できます...最小二乗直線近似を Google で検索する必要があります。より詳しい情報。これにより、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 までの 1つの線分 (再帰的ではない) の誤差です。
Opt(i-1) は最初の点から (i-1 ）番目

これでアルゴリズム

ポイントのリストが x 値でソートされていることを確認します
M[0] = 0 --- 自明
i < j のすべてのペア (i, j) について: e(i,j) を検索 ---- (これにはネストされたものが必要になりますfor/foreach ループ、または構造の内包構造. これらの値を 2D 配列に格納してください!)
For (j=1..n): M[j] = min([Opt(j) for i in range(1,j) )]

したがって、基本的には、任意の 2 つの点の間の 1 行のコストを
見つけ、e に保存します。1 と n の間の j について、j までの最小コストを見つけます。途中の値は後の計算に役立つので、保存しておいてください! i も Opt のパラメータであることに注意してください。M[n] は、最適化された総コストです。

あなたへの質問 - セグメンテーションが発生する場所をどのように判断できますか? これと M をどのように使用して、線セグメントのセットを決定することができますか?

お役に立てれば！

于 2010-11-03T06:10:35.227 に答える