4

直線関数 y = a*x + b(aとは既知の定数) が与えられると、直線とサンプルのウィンドウ(は最も古いサンプル、は最新のサンプル)bの間の平方和の距離を簡単に計算できます。(1, Y1), (2, Y2), ..., (n, Yn)Y1Yn

sum((Yx - (a*x + b))^2 for x in 1,...,n)

ローリング ウィンドウ (長さn) のこの値を計算するための高速なアルゴリズムが必要です。新しいサンプルが到着するたびにウィンドウ内のすべてのサンプルを再スキャンすることはできません。
明らかに、新しいサンプルがウィンドウに入り、古いサンプルがウィンドウから出るたびに、何らかの状態を保存して更新する必要があります。
サンプルがウィンドウを離れると、残りのサンプルの指数も変化することに注意してください。すべての Yx が Y(x-1) になります。したがって、サンプルがウィンドウを離れると、ウィンドウ内の他のすべてのサンプルが新しい合計に異なる値を与えます:(Yx - (a*(x-1) + b))^2の代わりに(Yx - (a*x + b))^2.

これを計算するための既知のアルゴリズムはありますか? そうでない場合は、1つ考えられますか？(一次線形近似のため、多少の誤差があっても問題ありません)。

4

2 に答える 2

2

単純なアプローチでうまくいきませんか? ...

「簡単」とは、サンプルのキューを維持することを意味します。新しいサンプルが届いたら、次のことを行います。

  • キューから最も古いサンプルを取り出す
  • あなたの合計からその距離を引きます
  • 新しいサンプルをキューに追加します
  • その距離を計算し、それを合計に追加します

時間に関しては、キューがリンクされたリストまたは同様のものとして実装されている場合、ここにあるものはすべて O(1) です。サンプルとの距離もキューに格納する必要があるため、一度だけ計算します。したがって、メモリ使用量は、サンプルごとに 3 float - O(n) です。

于 2012-01-06T00:11:40.447 に答える
1

用語を展開すると、用語(Yx - (a*x + b))^2は 3 つの部分に分かれます。

  1. a、xおよびのみの項b。これらは、合計するnと何らかの定数を生成し、無視できます。
  2. と のみのYx​​条件b。これらは、@Xion が説明したボックスカー インテグレーターのスタイルで処理できます。
  3. の一期-2*Yx*a*x。は-2*a定数なので、その部分は無視してください。部分和を考えてみましょうS = Y1*1 + Y2*2 + Y3*3 ... Yn*n。とY1実行中の合計R = Y1 + Y2 + ... + Ynを指定すると、他の各項がS - R消去および削減され、 が残ります。ここで、(2) と同様に、 off を減算して を加算することにより、実行中の合計を更新します。に新しい用語を追加します。Y1*1Y2*1 + Y3*2 + ... + Yn*(n-1)RY1Y(n+1)Yn*nS

これらの部分項をすべて足し合わせるだけです。

于 2012-01-06T00:40:41.950 に答える