読者です 読者をやめる 読者になる 読者になる

FXボーグ | テクニカル実験室

テクニカル分析を使った自動売買プログラムの開発に挑戦!

スポンサーリンク

有向非巡回グラフでMTAアルゴリズムの高速化(その1)

MTAアルゴリズムを高速化するアイデアを考えてみました。MTAでは分割可能な全ての区間の統計量(残差平方和)を計算しているのですが、以下のグラフに沿って集計していけば事前に全ての区間の統計量を求めることが出来そうです。

f:id:fxborg:20170311004006p:plain

こんな感じで全ての辺に向きがあって同じノードに戻ることのないグラフを有効非巡回グラフ(DAG)と言うのですが、プログラムを推敲する時などにとても便利です。

とりあえず簡単な足し算を例を説明した後に、こちらの記事の方法で残差平方和を求めていきます。

 足し算の例

次の時系列データで2つ間隔に全とおりの区間のYの合計値を計算します。

f:id:fxborg:20170311013852p:plain

全とおりの区間は具体的には以下の区間になります。

0-3、0ー6、0-9、0-12、3-6、3-9、3-12、6-9、6-12、9-12

・・・ではグラフに沿って計算していきます。

f:id:fxborg:20170311014933p:plain

一番上の段にある数字はXの値をあらわしています。時系列データなので左から右に1個ずつ読み進めていきます。

イ.0→(0)となっているのは区間(0-0)の合計という意味になります。この場合は Y0の20です。

ロ.次に[1、2、3]が薄い青で囲まれていますが、これは集計するという意味で、具体的にはY1-Y3の「25,40,35」を足して100です。

ハ.3→(3)となっているのは区間(3-3)の合計という意味で35になります。

ニ.(0)と[1、2、3]がもう一つの(0)につながっています。これは区間(0-3)の合計を意味しており、また(イ)と(ロ)を足すことで求められるということを表現しています。具体的には20+100=120になります。

 この流れで同様に解いていくのですが、これをプログラムにするとこんな感じです。

f:id:fxborg:20170311024051p:plain
 【出力】
f:id:fxborg:20170311030040p:plain

これで全とおりの区間の合計が求まりました。残るは残差平方和を求め方になりますが、こんなクラスを作って追加や合成が行えるようにしています。 

【実行結果】

f:id:fxborg:20170311031351p:plain
(以下略)

最後に

今回はオンライン回帰アルゴリズムを使用してMTAを高速化するアイデアを試してみました。このロジックを使ったらインジケーターにしても耐えられるんじゃないかと期待しています。次回は実際のMTAで試してみたいと思います。

こちらからどうぞ

online_sum.py
onlineregression.py
online_regr.py