クラスタリングをやってみる

Society Of ActuariesのCompAct誌に載っているクラスタリング手法について試してみました。
https://www.soa.org/Library/Newsletters/Compact/2009/July/com-2009-iss32.pdf
k近傍法と呼ばれる手法の変形のようで、通常のk近傍法では最も近いセルを統合するところ、この手法では(セル間の距離×セルのサイズ)が最も小さいセルが統合されるようです。

CompAct誌にはRコードが載っていますが、理解のためにPythonで書き直してみました。
https://gist.github.com/threecourse/d69b82a54241afdeccb0#file-cluster_logic_sample-py

これだと速度が遅すぎるので、少し速く動くようにロジックを修正し、C#でも書いてみました。
https://gist.github.com/threecourse/d69b82a54241afdeccb0#file-clustering-cs

クラスタリングを試してみた結果は以下の図のとおりで、なんとなくうまくいっているようです。
青の円がもともとのセル、赤の円がクラスタリング後のセルを表しています。
cluster

しかしながら、計算量O(n^2 * logn)はともかく、メモリ使用量がO(n^2)というのがいまいちで、10000セルくらいで限界を迎えてしまうようです。
KDTreeというものでもう少し効率的にできるらしいので、次回はそれを試してみようとおもいます。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です