JavaScriptで決定木を作って、D3.jsで可視化してみた
(研究テーマとは全く関係ないけど)最近、機械学習の不均衡データをどうやって取り扱うべきかという論文を読みました。
その論文では、分類器に決定木を使ったものが取り扱われていました。
そこで、自分で決定木を実装してみようと思い立って作ってみました。
自分の中ではプログラミングの訓練という位置付けなので、Rは使わずにコード書きました。
そんで、どうせならと思ってブラウザ上で可視化してみました。
決定木とは
決定木が生成するモデルは、直感的にわかりやすく、推論過程を理解しやすいというメリットを持っています。
具体的にに生成されるモデルは、以下に示すようになります。
http://himetani.github.io/decision-tree/
機械学習の分野では有名らしい、IrisDataを使いました。
if−then文の感覚で、各節点をたどっていくと分類できるという非常にシンプルなものです。
決定木を生成するためには、与えられたデータセットの中からデータを分割する点を選ぶ必要があり、その点が決定木の節点となります。
この分割点を探すアルゴリズムとして有名なものはCART(Classfication and Regression Trees)とC4.5です。
どちらも各集合の中で最高の分割点を選ぶための方法ですが、最高の分割点であることを評価する方法が異なります。
CARTではジニ不純度を用いて評価し、C4.5では情報エントロピーを使って計算される情報ゲインという指標が用いられます。
今回の実装では、CARTアルゴリズムを用いました。
ちなみに、ジニ不純度の式は以下のようになります。
全体の流れは、
- データセット全体の中で、分割後の二つの集合のジニ不純度の相加平均が最も小さい分割点を探す
- 1.で決まった点でデータを分割し、分割後のデータで再び1.計算する
- 分割前のジニ不純度が分割後のジニ不純度の相加平均より小さくなるまで1.2.を繰り返す
という感じです。
これをJavaScriptで実装して、D3.jsで可視化しました。
実装はこんな感じです。