Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

差分統計処理のための平均計算。

データを定期的に収集して統計計算を行うシステムを書いている際に、差分処理を行いたい場合がある。データはどんどん蓄積されていき、インプットとなるデータが巨大となった時、処理速度はそれに比例して遅くなってしまうためである。そういった時は逐次計算を行えばいい。既に計算された前回の統計計算の結果に、前回からのインプットデータの差分を取り込んで計算する。
以下は平均値の逐次計算である。

count += 1
average += (value - average) / count

averageは平均、countは回数、valueは追加される値を表す。 上記は以下のような計算で成り立つ。

average[new] = (average[old] * count[old] + value) / (count[old] + 1)
average[new] = average[old] + x

average[old] + x = (average[old] * count[old] + value) / (count[old] + 1)

average[old] + average[old] * count[old] + x * (count[old]+1) = average[old] * count[old] + value
average[old] + x * (count[old]+1) = value

x = (value - average[old]) / (total[old] + 1)


一番最初に計算を行う場合は、averageに値を平均の推定値を入れておくといい。0でもいい。
以下はPythonで簡単に今回の計算証明のために書いたコード。

#!/usr/bin/env python
'''
count += 1
average += (value - average) / count
'''

class Average:

    def __init__(self, c=0, a=0, r=[]):
        self.count = c
        self.average = a
        self.result = r

    def onlineAverage(self, value):
        self.count += 1
        self.average += (value - self.average) / self.count
        self.result.append(self.average)
        return self.average, self.result

def test():
    a = Average()
    assert a.onlineAverage(10) == (10, [10])
    assert a.onlineAverage(20) == (15, [10, 15])
    assert a.onlineAverage(30) == (20, [10, 15, 20])

    return 'OK! test'

if __name__ == '__main__':
    print test()

結果は以下のとおり。

OK! test

大量のデータをテーブルからselectして統計計算をするといった時に、メモリに収まらないといったケースで利用することがあり、これらの計算はオンラインアルゴリズムとも呼ばれている。
データ分析といった分野ではよく使うのではないだろうか。

僕自身そういったプロジェクトに現在身を置いていて、統計計算はかなり重要なコア的な処理であるためここらへんはもっと勉強したい。

Remove all ads