CART による2進木解析

CART は、2進再帰分割法として知られています。親ノードは必ず 2つの子ノードに分岐されるので「2進」的であり、子ノードが親ノードとなってさらに分岐してゆくので「再帰」的であるからです。CART の原理は、次のようになります。

分岐ルール

CART では、質問に対して「Yes」か「No」かで、親ノードが2つの子ノードに分岐してゆきます。たとえば、

という質問に答えてゆくのです。

 

分岐ルールはどのように設定するのか？

CART は、すべての変数に関して可能な分岐をすべてチェックします。たとえば 19 の変数をもった 215 サンプルのデータセットで考えてみましょう。CART は、最大で 19変数 × 215サンプル = 4085回 の分岐を試みます。分岐のルールには限りがあるので、CART はそれらすべてを単純計算します。つぎに CART は、うまい具合に分岐がなされたかという観点に立って、それぞれの分岐ルールをランクづけします。CART がデフォルトに設定されている判断基準は、親ノードに含まれるサンプルがいかにうまく 2つに分類できたかを判断基準とする GINI (ジニ) 法が用いられます。(その他の方法も利用できます。)

 

分類の仕方

もっともよい分岐ルールがみつかったら CART は、これ以上分岐ができない、あるいは中止されるまで、さらに子ノードで最良の分岐ルールの発見を繰返してゆきます。あるノードにサンプルが 1つだけになった、あるいはすべてのサンプルがまったく同じであった場合は、分岐は不可能になります。CART は、たとえばノードに含まれているサンプルの数が少ないなど (デフォルトではこの数は 10 ですが、変更することができます) 、その他の理由によって分岐を中断させることもできます。

ターミナルノードがみつかると、その中のサンプルをあるクラスに分類することができます。単純な方法として、数の多い方を採用して分類する多数決方式があります。CART はターミナルノードに行き着いても、さらに分類を進めていきます。なぜなら、すべてのノードはターミナルノードになる可能性があり、ターミナルノードであるなしに関わらず、クラス分けすることができるからです。分類のルールは、単純な多数決から、分類の際の間違いをコストとして考慮し修正する方法まであります。

2進木分析の初期の手法では、うまく分岐ができたという何らかの結論に落着くまで、ノードの分岐を繰返す (樹木を生長させる) という方法が一般的でした。分岐がある水準より良くなったとき、その枝の生長を止めました。ルートから生じたすべての枝がターミナルノードにたどり着くと、樹木は完成されたと見なされます。この手法は、現在でも CHAID、KnowledgeSEEKER® で採用されており、しばしば間違った結論を導き出しています。CART は、これとはまったく異なる手法を用いています。

 

結論

CART は、データのツリーモデルを作るために非常に巧妙な方法を使っています。そのため、小さなデータセット、詳細が分らないようなデータでも、分析してみることが可能です。データセットの分析方針を決める前に、とにかく CART を試してみて下さい。これは決して誇張ではありません。CART は非常に有用な結果を導き出してくれるでしょう。

CART とステップワイズ・ロジスティック回帰分析あるいは判別分析を比べたとき、学習用サンプルに関しては CART は遙かによい結論を導き出してくれます。検証用サンプルについていえば、もっと重要です。なぜなら CART は、一般的なステップワイズの手法ではやっかいな欠損値にも対処できるからです。検証用データに対しては、CART はより正確といえます。もっともよく作られたパラメトリックモデルと比較しても、CART は十分に強力です。CART はたった 1日、2日で、専門家が何日もかかって構築したモデルの若干予測精度の劣る程度のモデルを、自動的に作り上げてくれるのですから。

 

分岐ルールは本当に有効なのか？

2進木分析というのは本当に有効なのでしょうか？　一般的にデータマイニングの世界で考えられているよりも、非常に有効であるといえるでしょう。事実、正しいルールを採用するか、間違ったルールを採用するかによって、数百万ドルに値する差が表れています。

それほど有効ならば、なぜもっとよく知られていないのですか？　答えは簡単です。データセットが小さくて正確ならば、ツリーは簡単に生成することができます、特別な分岐ルールは重要ではありません。あなたのゴルフボールがカップから 1インチのところにある場合は、どのクラブを使おうが重要ではありません。何を使おうがボールは簡単にホールに入れられるでしょう。あまり違いのみられない分岐ルールの間で、どれが有効なルールなのかを判断する従来の方法は、とりわけよい結果を発見することがむずかしい大きなデータセットには、向いていなかったのです。

不正が行われていないかの調査、12か月以内に破産しそうな顧客の特定、ダイレクトメールキャンペーンの実施、あるいは手持のデータを使いながら 90％以上の精度が必要な問題などでは、分岐ルールに何を選ぶかで決定的な違いが表れます。さらに異なる分岐ルールが、同じくらい正確な分岐変数を選んだとしても、その差は重要です。誤差率の等しい 2本のツリーでも、特定のクラスに関して優れているツリーの方が重要でしょう。決定木が、因果関係のプロセス、あるいはデータベースの構造に対する洞察を導き出すことが目的であるならば、同じくらい精度の高い分岐ルールはデータの解釈および理解のために異なるツリーを作り出すでしょう。

ここでは、非常に重要な 3つのツリーの生長基準すなわち GINI、Twoing、エントロピーと、その選択法について説明します。どのような場合にどれを選んだらよいのか述べますが、いつも複数の分岐ルールを使ってツリーを生長させ、比較してみることを奨めます。異なる分岐ルール毎に異なった結果が得られるでしょう。そして経験を積むにつれ、特定の問題に関して最適な分岐ルールは何かを学ぶことができるでしょう。１つのルールに固執しないことが肝要です。

 

GINI、Twoing、エントロピー

2進再帰分割のための最もよく知られているルールは、GINI、Twoing およびエントロピーです。各々が異なるスタイルのツリーを育てるとともに、異なる哲学を表わしています。

  1. GINI (ジニ) 分岐ルール
    GINI は、データベースの中から最も大きなクラス (例：クラス A) を捜し出して、他のすべてのクラスからそれを分離しようとします。例えば、4つのクラス A、B、C、D がデータの中でそれぞれ 40、30、20、10％ を占めるとすると、GINI ルールではクラス A に属するレコードを 1つのノードにまとめようとします。もちろん実際のデータでは、そのような分離は可能ではないかもしれません、しかし、GINI は可能な限りそうしようとします。下の図は、もっともよく GINI ルールで分類された状態を示しています。

    最初の分岐が終ると、GINI はさらに分類を続けようとします。すわなち、クラス B、C、D が混在している右側の子ノードの分類です。最初の分岐と同様に、ノード中の最大のクラスであるクラス B のレコードをすべて取出そうとします。そのあとさらに GINI は、クラス C と D を分けるために最後のノードの分類に取りかかります。GINI ルールがうまくいった場合、最終的なツリーは 4つの「純粋」な子ノードでかたち作られます。

    上記のような「純粋」な決定木は、非常にまれな状況においてのみ到達可能です。ほとんどの場合は、データベースの各フィールドをきれいにクラス分けしようとしても難しいでしょう。もしそれが可能になれば、ダイレクトメールの送り先の失敗や、貸倒れで損失を被ったりすることがなくなるでしょう。したがって、このような完璧なツリーが得られることを期待してはいけません。GINI は、この理想にできるだけ近づけようとするのです。GINI を使って成長させた現実的な決定木は、次の図のようになります。不完全ですが、それでも非常に正確なツリーです。

    GINI の神髄は何でしょうか？　GINI は、その都度 1つのクラスに注目して分類を行います。注目するクラスは、ノードの中で最大のもの、あるいは重みづけ (コスト) をした場合は最も重要なクラスとなります。この方法は非常に単純だと思えるかもしれませんが、しばしば非常によい結果を導き出しますので、ぜひお試しください。最良の分岐ルールであることが非常に多いので、CART は GINI をデフォルト設定の分岐ルールとしています。

  2. Twoing、エントロピー分岐ルール
    Twoing の考え方は、GINI のそれとまったく異なります。最初に1つののクラスを取出そうとするのではなく、合計するとデータの 50％になる 2つのグループにクラスを分けようとします。Twoing は、2つのサブグループに分けるための分岐の仕方を見つけ出します。次の図は、Twoing ルールが完璧にうまくいったときの例です。

    これは本当に理想的な分岐です。実際の世界のデータベースを使った場合は、4つのクラスを 2つのサブグループに分けようとしても、こんなにうまくはいかないでしょう。しかしながら、まったく不可能ではないかもしれません。Twoing は、それにもっとも近い分岐の仕方を見つけようとします。エントロピー分岐ルールも、Twoing に非常によく似た分岐ルールです。

    Twoing のバリエーション

    Twoing 分岐ルールの一種で注目すべきものに、加重 Twoing 法があります。それはノードの中のデータを 2つのグループに分割する際、重み付けする方法です。上図のような完璧な分岐ができれば、Twoing と加重 Twoing は同じ結果となります。完璧に分類できない場合は、加重 Twoing の方がより 50％ 対 50％ に近い分類を実現します。

 

成功のノウハウ

通信、銀行、市場調査で得られたノウハウを以下に示します。他の分野とはデータセットが異なるかもしれません。しかしながら、他の領域でもこれは十分有効であると考えられます。

最後の経験則の例を挙げます。28台の乗用車のうち消費者はどれを好むのかというデータマイニングは、分岐ルールをいろいろと変えながら重大な要因を見つけ出していく典型的な例です。この場合は、変数はきわめて限られた数しかありませんでした。また、ドライバーの収入や乗用車の価格に関係なくツリーを成長させる必要があります。したがって、最終的な精度のレベルは低いと予想されました。デフォルト設定のまま最初に実行してみたとろこ、GINI 分岐ルールは 0.919 の相対誤差で 89 ノードのツリーを育てました。Twoing 分岐ルールをを使った2回目は、相対誤差 0.876 で 50 ノードのツリーが成長しました。

以下に示すツリーのシーケンスをみてみると、Twoing 分岐ルールの方が大きなツリーを作り出す GINI 分岐ルールよりも、最初によい分岐を行っていることがわかります。また 2番目のツリーは誤差の項目で高い誤差率を持ちますが、それは最初のツリーを劇的に改良しているからです。乗用車の好みをさぐるこの例では、Twoing 分岐ルールが正解でした。しかしデータセットが変われば、加重 Twoing、GINI、あるいはさらに別の分岐ルールがよくなるかもしれません。

CART ツリーシーケンス (目的変数 28水準、GINI を使用)
ターミナル
ノード数
テストセットの
誤差率±標準誤差
相対誤分類率
 複雑度パラメータ
100
0.91973 +/- 0.00636
0.80182
0.00076
95
0.92016 +/- 0.00636
0.80591
0.00079
94
0.92054 +/- 0.00636
0.80678
0.00085
89** (optimal)
0.91921 +/- 0.00636
0.81140
0.00090
88
0.92348 +/- 0.00636
0.81238
0.00095
78
0.92498 +/- 0.00630
0.82236
0.00097
70
0.92259 +/- 0.00639
0.83084
0.00103
19
0.94185 +/- 0.00657
0.90447
0.00236
18
0.94393 +/- 0.00649
0.90696
0.00241
17
0.94393 +/- 0.00649
0.90970
0.00265
13
0.94903 +/- 0.00650
0.92238
0.00306
4
0.97052 +/- 0.00640
0.95574
0.00358
3
0.97227 +/- 0.00566
0.96447
0.00843
2
0.97795 +/- 0.00399
0.97884
0.01386
1
1.00000 +/- 0.00004
1.00000
0.02042

ターミナル
ノード数
テストセットの
誤差率±標準誤差
相対誤分類率
 複雑度パラメータ
CART ツリーシーケンス (目的変数 28水準、Twoing を使用)
55
0.88054 +/- 0.00643
0.77145
0.00112
54
0.88067 +/- 0.00648
0.772064
0.00116
53
0.88067 +/- 0.00648
0.77384
0.00117
51
0.87681 +/- 0.00657
0.77632
0.00121
50** (optimal)
0.87623 +/- 0.00660
0.77764
0.00128
45
0.87697 +/- 0.00653
0.78517
0.00146
43
0.87697 +/- 0.00653
0.78819
0.00147
40
0.88095 +/- 0.00648
0.79281
0.00150
15
0.88822 +/- 0.00703
0.84970
0.00351
14
0.89282 +/- 0.00698
0.85413
0.00428
7
0.90537 +/- 0.00544
0.89082
0.00585
5
0.91961 +/- 0.00513
0.90667
0.00765
4
0.93286 +/- 0.00490
0.92311
0.01586
3
0.94789 +/- 0.00380
0.94347
0.01964
2
0.96803 +/- 0.00217
0.96833
0.02398
1
1.00000 +/- 0.00004
1.00000
0.03055

 

結論

2進木を育てる場合、どの分岐ルールを選ぶかは非常に重要です。そして分岐ルールによる違いは、時にはわずかであったり、また過大であったりします。分岐ルールの賢明な選択はツリーの誤差率を 5～10％ 縮小してくれます。また、正確さを超えた違いもあります。異なる分岐ルールによって育てられた 2つのツリーの精度がまったく同じであったとしても、データ構造を明らかにするという点で差が出てくることもあります。目的変数のある値の中にどれくらい最良のノードがあるかによって決定木の価値が決って、ツリー全体の精度とは無関係という場合もあるでしょう。そのよう場合、GINI と Twoing 分岐ルールの差は、成功と失敗の違いとなります。

すべての問題あるいはすべての目的に最適な分岐ルールがないならば、2進木解析ソフトウェアは異なる手法と特長をもった複数の分岐ルールを持っていることが、非常に重要です。