決定木のアルゴリズム3選!CHAIDとCARTとC5.0を紹介!

こんにちは!
IT企業に勤めて、約2年間でデータサイエンティストになったごぼちゃん(@XB37q)です!

このコラムでは、決定木分析に存在する3種類のアルゴリズム「CHAID」「CART」「C5.0」を紹介します!
決定木分析のメリットとデメリットも紹介してます。

決定木分析については、下記のコラム「pythonでできる!万能手法である決定木分析の見方と解説!」をご覧ください。

決定木の大枠 回帰木と分類木

分類木と回帰木
分類木と回帰木

決定木には分類木と回帰木の2種類があります。

分類木は、目的変数が(〇 or ×)や(男性 or 女性)などのカテゴリ値の場合に使用する決定木です。
分岐の条件に該当するノードの最頻値が予測値になります。
つまり、〇〇×の場合、〇が1番多く出現しているため、予測値は〇になります。
最頻値は分岐の条件に該当する場合の期待値を表します。

回帰木は、目的変数が(100円~1,000円)や(1mm~10,000mm)などの数値の場合に使用する決定木です。
分岐の条件に該当するノードの平均値が予測値になります。
つまり、100円と200円のデータが存在するノードの場合、150円が平均値であるため、予測値は150円になります。
平均値は分岐の条件に該当する場合の期待値を表します。

学習の手順

決定木分析の学習手順
決定木分析の学習手順

構築手順分岐停止条件を理解することにより、決定木分析の学習を理解することができます。
決定木分析では、下記の構築手順通りに決定木を構築し、分岐停止の条件に該当した場合、構築を終わります。

構築手順

学習データに対して、再帰的に分岐条件を定義し、分岐が終わるまでその1つ1つの条件に沿って学習データを分類します。

  1. 学習データ全体で最適な分岐条件を探索し、データをその条件に従って振り分ける
  2. 分岐したデータで再帰的に同様の分岐(分岐条件の探索、データ分割)を繰り返す
  3. 分岐停止条件に達したら、分岐を停止する

分岐停止条件

学習データに対して、過学習を抑制ながら、決定木分析は分岐を行います。
過学習を抑制するため、下記の条件を設定し、条件に該当する場合に分岐を停止し、モデル構築を終了します。

  • 分岐した後に含まれるデータ数がある閾値以下
  • 分岐した後に含まれる不純度がある閾値以下
  • 分岐回数がある閾値に達した場合

決定木のアルゴリズム3選

CART,CHAID,C5.0
CART,CHAID,C5.0

決定木分析と一概に呼ばれていますが、決定木分析の中には様々なアルゴリズムが存在します。
この章では、一般的に使われる3つのアルゴリズムである「CART」「CHAID」「C5.0」を紹介します!

これらのアルゴリズムは、分岐できる数や、目的変数と説明変数に使える変数、分岐に使われる指標がそれぞれ違うため、それらを意識して各アルゴリズムを理解すると良いと思います!

CART

CARTと呼ばれるアルゴリズムです。
他のアルゴリズムとは違い、分岐が必ず2分岐になります。
そのため、複雑な分岐を行うことができませんが、結果がシンプルになり解釈性が高くなります。

Gini係数と呼ばれる各分岐の不純度が低くなるように分岐を行います。

pythonでXGBoostを行う場合、CARTが構築されます。

CHAID

CHAIDと呼ばれるアルゴリズムです。
他のアルゴリズムとは違い、説明変数に質的変数のみをとりますが、量的変数は質的変数に変換を行って使用することができるため、特別大きな違いはありません。

カイ二乗検定と呼ばれる統計的仮説検定を用いて分岐を行います。
分岐が統計的に意味があるかを検定して、分岐を行っていくため、過学習しにくい傾向にあると思います。
また、目的変数が量的変数の場合、F検定と呼ばれる平均値の検定を用いて分岐を行います。

C5.0

C5.0と呼ばれるアルゴリズムです。
他のアルゴリズムとは違い、目的変数が質的変数のみとなります。
そのため、数値を表す量的変数を分岐させることは不可能です。

エントロピーと呼ばれる指標を用いて分岐を行います。
エントロピーは、情報がよりランダムに近いほど、値が大きくなり、逆に情報がよりランダムで無く偏っている時、値が小さくなります。
そのため、分岐後にデータの分割が完璧にできている場合、エントロピーは0になります。

決定木分析の特徴

決定木分析の分岐イメージ
決定木分析の分岐イメージ

主な特徴

  • 目的変数を説明変数ごとに矩形領域(長方形のイメージ)に分割するため、目的変数と説明変数に相関が無い場合でも、予測や分類が可能である
  • 数値の値の大きさに依存せず、値の大きさの順序のみに依存するため、AIモデルを構築する前の標準化や正規化は必要ない

標準化や正規化については、他コラム「精度に直結!データクレンジングの方法」をご覧ください!

メリット

  • 木構造で if then を表すルールで解釈できるため、目的変数に対してどの説明変数がどのような条件で効くのか、視覚的に判断しやすい
  • 矩形で表現できる範囲は、非線形なモデルを表現可能
  • 数値変数の標準化や正規化が不要
  • 説明変数がカテゴリの場合の親和性が高いため、ダミー変数化が不要
  • 目的変数、説明変数の数に限りが無い

デメリット

  • パラメータ(分岐数、ツリーの高さ)の決め方が難しく、データを分割していきデータ量が少なくなるため、過学習が起こりやすく、ある程度のデータが無いと精度が高くなりにくい
  • 空間を矩形に分割するため、変数間で相関が大きい場合、適切な分割が難しくなる 
  • 可読性は高いが精度面の限界がある。そのため、複数の決定木を用いてアンサンブル学習するアルゴリズムが発展 
  • 変数に対して1番目に影響を与える説明変数のみが採用されるため、2番目に影響を与える説明変数は、結果に影響を与えない場合がある

まとめ

  • 分類木
    • ノードの最頻値を予測値とする
  • 回帰木
    • ノードの平均値を予測値とする
  • 構築手順
    • 学習データ全体で最適な分岐条件を探索し、データをその条件に従って振り分ける
    • 分岐したデータで再帰的に同様の分岐(分岐条件の探索、データ分割)を繰り返す
    • 分岐停止条件に達したら、分岐を停止する
  • 分岐停止条件
    • 分岐した後に含まれるデータ数がある閾値以下
    • 分岐した後に含まれる不純度がある閾値以下
    • 分岐回数がある閾値に達した場合
  • CART
    • 分岐が必ず2分岐
    • Gini係数で分岐
  • CHAID
    • カテゴリ値の場合、カイ二乗検定で分岐
    • 連続値の場合、F検定で分岐
  • C5.0
    • 目的変数が質的変数のみ
    • エントロピーで分岐
  • メリット
    • 結果を視覚的に解釈しやすい
    • データの加工がそれほど必要ない
  • デメリット
    • 過学習がしやすい
    • 精度面に限界がある

参考図書