移動平均 - uokumura’s diary

件のチーム防御率のグラフで、初期の成績がいつまでも影響してしまうと狩野捕手の成長が見えないので、移動平均を取りたくなりました。移動平均というのは、リストの先頭から１個ずつ後ろにずらしながらn個のデータの平均値を取ったリストのことで、リストlの移動平均をn=3で取れば、

[(l[0] + l[1] + l[2])/3, (l[1] + l[2] + l[3])/3, (l[2] + l[3] + l[4])/3, …, (l[-3] + l[-2] + l[-1])/3]

の様になります。リストの先頭から1件ずつずらしながらn値の平均を取って行くので移動平均、て訳です。バラツキの有るデータのバラツキを抑制しつつ大きな流れが見れる便利なやつです。
ただ、この移動平均というやつは件数が減ってしまうのが難点です。例えば1〜5まで5件のデータが有るリストからn=3の移動平均を取ると、
[(1+2+3)/3, (2+3+4)/3, (3+4+5)/3]
となるように、平均を取るためにn件要るのでn件目以降からしか移動平均が取れずにn-1件データが減ってしまいます。そうなると元データとグラフを重ねたりするとぶさいくになっちゃうんです。
そこで、今回はn-1件目までは単純にそこまでの平均値を入れて
[(1)/1, (1+2)/2, (1+2+3)/3, (2+3+4)/3, (3+4+5)/3]
と件数をそろえるようにしました。

まずはテスト

1,2,3,…のような1ずつ増える数列を使って、nを奇数にすると移動平均部分が対象データの中央値になって扱いやすいので、IntRangeをテストデータにしました。

assert (1..10).movingAverage(5) == [1,1.5,2,2.5] + (3..8)
assert ((2..20).step(2)).movingAverage(5) == ([2,3,4,5] + (6..16).step(2))

先頭に付加するデータは[1, (1+2)/2, (1+2+3)/3, (1+2+3+4)/4]で[1, 1.5, 2, 2.5]
1..10の移動平均は[(1+2+3+4+5)/5, (2+3+4+5+6)/5, …, (6+7+8+9+10)/5]の中央値のリストを取って3..8

なので、その2つを連結した[1, 1.5, 2, 2.5] + (3..8)で実際の移動平均の算出結果をテストしています。
さらに、その倍のデータで倍の結果が変えるテストもしておきます。

素直な実装

List.metaClass.define {
    getAverage {-> sum() / size() }
    
    movingAverage {int n->
        (1..<n).collect{delegate[0..<it].average} +
        (n..size()).collect {i->delegate[(i-n)..<i].average}
    }
}

1件目からn件目直前まではそこまでの値の平均値のリスト
n件目以降はそこまでのn件のデータを平均したリスト

を結合します。というそのままのコードです。

とりあえず動いたので、特殊ケースを

コードを眺めてみると

    movingAverage {int n->
        (1..<n).collect{delegate[0..<it].average} +
        (n..size()).collect {i->delegate[(i-n)..<i].average}
    }

まぁ、空のリストが非常に危なそうですね。ほかに、n=1の場合、n=sizeの場合、n > sizeの場合、が危なそうです。

assert [].movingAverage(3) == []
assert [1,2,3].movingAverage(1) == [1,2,3]
assert [1,2,3].movingAverage(3) == [1,1.5,2]
assert [1,2,3].movingAverage(4) == [1,1.5,2]

まずは0件でエラーが出たので、とりあえずガード節を追加します。

    movingAverage {int n->
        if (empty) {
            return []
        }
        (1..<n).collect{delegate[0..<it].average} +
        (n..size()).collect {i->delegate[(i-n)..<i].average}
    }

今度はn>sizeのケースで発生しました。n=1やn=sizeは大丈夫だったようです。n > sizeの場合、移動平均計算を行うn件目に到達しないので、n=sizeの場合と期待する結果は一緒になります。なので、n>sizeならn=sizeにしてしまいましょう。

    movingAverage {int n->
        if (empty) {
            return []
        }
        if (n > size()) {
            n = size()
        }
        (1..<n).collect{delegate[0..<it].average} +
        (n..size()).collect {i->delegate[(i-n)..<i].average}
    }

最後にエラーケースも

nに0以下の値を渡したらIllegalArgumentExceptionですね。

try {
    [1,2,3].movingAverage(0)
    assert false: "移動平均のnに0は指定できない"
} catch (IllegalArgumentException expected) {
}
try {
    [1,2,3].movingAverage(-1)
    assert false: "移動平均のnに負数は指定できない"
} catch (IllegalArgumentException expected) {
}

ちゃんとassertで捕まえられる事を確認して、実装です。

    movingAverage {int n->
        if (n <= 0) {
            throw new IllegalArgumentException("移動平均算出でn=${n}が指定されました。")
        }
        if (empty) {
            return []
        }
        if (n > size()) {
            n = size()
        }
        (1..<n).collect{delegate[0..<it].average} +
        (n..size()).collect {i->delegate[(i-n)..<i].average}
    }

テストしてみたら通りました。これで異常系も一通り大丈夫そうです。

計算量について

上記のロジックだと、(リストの件数-n)回、n個の値の平均を算出するので、計算量は指定したnの数値とリストの長さのそれぞれに比例します。
nが大きくなる場合は、移動平均 - Wikipediaにあるように、「前回の移動平均値 - l[i-n]/n + l[i]/n」で計算できますが、この場合誤差が積み重なってしまいますので、移動平均値の代わりに合計値を取っておいて「移動合計値 = (前回の移動合計値 - l[i-n] + l[i]); 移動平均値 = 移動合計値 / n」とするのが良さそうです。移動合計値なんて言葉が有るかどうかは置いておいて。

…が、めんどくさいのでここまでにします^^;