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

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

スポンサーリンク

KD-Treeのc++実装であるnanoflannライブラリの使い方

KD-Treeは普通の平衡二分木を多次元(2次元以上)に拡張させたもので、空間座標の範囲検索や最近傍検索を効率的に行えるデータ構造です。特にK近傍法やDBSCANといったクラスタリング・アルゴリズムにはもって来いです。

nanoflannはC++で実装されたKD-Treeのヘッダライブラリですが、使い方がちょっと分からなかったので、いろいろと調べながらラッパークラス(自分用)を作ってみました。 

KD-Tree自体の説明(こちらのスライドが分かりやすかったです)

www.slideshare.net

KD-Treeのライブラリ

C++でKD-TreeのライブラリーというとFLANNが有名ですが、他にもいくつかあるようです。

  • FLANN - Marius Muja and David G. Lowe (University of British Columbia).
  • FASTANN - James Philbin (VGG, University of Oxford).
  • ANN - David M. Mount and Sunil Arya (University of Maryland).
  • libkdtree++ - Martin F. Krafft & others.
  • nanoflann - Jose Luis Blanco-Claraco

いくつか試してみたのですが、動的にノードが追加出来て導入が簡単なnanoflannを選びました。

実際のコード

nanoflannはこちらを使用しました。

https://github.com/jlblancoc/nanoflann/blob/master/include/nanoflann.hpp
自作したクラスはこんな感じです。

 

利用するにはこんな風にします。

実行結果
f:id:fxborg:20171222142518p:plain

最後に

今回はnanoflannについて調べてみました。個人的には主要な高値と安値をクラスタリングしてサポート・レジスタンスの検出などに使用する予定です。

今年も残すところわずかになりましたが来年もよろしくお願いします。良いお年をお迎えください。