MLエンジニアへの道 #9

このブログ記事では、機械学習において決定木がどのように活用できるかを紹介します。

これまで、さまざまな問題を解決するために線形回帰を使用してきました。しかし、決定木を使用することもできます。

決定木

たとえば、犬の身長と体重を使用して、その種を予測する分類問題があるとしましょう。この場合、ソフトマックス回帰を使用する代わりに、下図のような決定木を使用して分類を行うことができます。

決定木の各要素はノードと呼ばれ、予測されたクラスが含まれる下部のノードはリーフノードと呼ばれます。ノードで各条件をチェックし、ツリーを下ってリーフノードにたどり着くことで予測を行います。上図から、各条件がデータの分類のために空間を効果的に分割していることがわかります。この方法は、回帰にも使用できます。たとえば、種と体重を基に犬の身長を予測することができます。

図の点の不透明度は、犬の身長を示しています。分類に使用される決定木は分類木と呼ばれ、回帰に使用されるものは回帰木と呼ばれます。タスクの性質に応じて、どちらかを選び使用することができます。

決定木の構築方法

では、これらの決定木はどのように構築すれば良いでしょうか。実は、決定木は驚くほどシンプルに構築できます。離散変数と連続変数のどちらについても、隣接する2点の中間値を分割候補として取り、各分割に対してエントロピーの合計（分類木の場合）または残差の二乗和（回帰木の場合）を計算します。

E = - \sum p log(p) \\ SSR = \sum (y - f(x))^2

ここで、p は分割された空間内でそのクラスが観測される確率、y は真の値、f(x) はツリーからの予測値で、これは分割された空間の平均値で計算できます。これらの値の合計を不純度と言い、不純度に改善が見られなくなった時点で枝の作成を終了します。線型回帰モデルのパラメータ更新を通知するためにコスト関数を追跡するように、決定木では、不純度を追跡してノードを構築する訳です。

決定木は構築が簡単で理解しやすいですが、一つ重大な欠点があります。それは、過学習しやすいという点です。実質、決定木は各データポイントに対してリーフノードを作成することで不純度、バイアスをゼロにすることができます。そして、決定木の構築方法にそれを防ぐためのメカニズムはデフォルトでは整備されていないです。そのため、バイアスバリアンストレードオフによってテストデータセットでのパフォーマンスが非常に悪くなる（高いバリアンすを持つ）傾向があります。

コスト複雑度剪定

決定木は過学習しやすいため、それを防ぐためのメカニズムが必要です。その一つが、コスト複雑度剪定(コストふくざつどせんてい　英: Cost Complexity Pruning 略: CCP)です。これは、リーフノードの数が多い複雑な決定木にペナルティを課すことで過学習を防ごうとするものです。エントロピーの合計や残差の二乗和を直接使用する代わりに、ツリーの複雑さに以下のようにペナルティを加えます。

Score_{clf} = E + \alpha T \\ Score_{reg} = SSR + \alpha T

ここで、 $\alpha$ はペナルティ率であり、 $T$ はリーフノードの数です。これにより、アルゴリズムがよりシンプルなツリーを好むようになります。これは、正則化が小さなパラメータを選択するようペナルティ項を追加するのと同様です。ペナルティ率は、正則化率と同様に、ペナルティの大きさを制御するハイパーパラメータであり、交差検証によって調整することができます。リーフノードを削除してツリーを小さくすることを剪定と呼び、上記の方法は複雑さにコストを加えることで間接的に剪定を実現します。そのため、コスト複雑度剪定という名前が付いているという訳です。

コードの実装

sklearnライブラリには、DecisionTreeClassifierおよびDecisionTreeRegressorがあり、これを使用して上記の手法を簡単に実装できます。今回は、Irisデータセットを使用して複数の種の分類を行うためにDecisionTreeClassifierを使用してみましょう。(DecisionTreeRegressorは自分で試してみて下さい。) データの探索および前処理のステップはここでは省略します。

ステップ3. モデル

コスト複雑度剪定に対して適切なペナルティ率を選択するために、次のように交差検証用の関数を設定できます。

from sklearn.model_selection import StratifiedKFold
from sklearn import tree
 
def dt_cross_validation(alphas, score, n_splits=10, shuffle=True, verbose=True):
  scores = {}
  kf = StratifiedKFold(n_splits=n_splits, shuffle=shuffle)
 
  for i, (train_index, test_index) in enumerate(kf.split(X_train, np.argmax(y_train, axis=1))):
    print(f"{i+1}th Fold") if verbose else None
    for alpha in alphas:
      clf = tree.DecisionTreeClassifier(criterion="entropy", ccp_alpha=alpha)
      clf.fit(X_train[train_index], y_train[train_index])
      pred = clf.predict(X_train[test_index])
      pred, y_val = np.argmax(pred, axis=1), np.argmax(y_train[test_index], axis=1)
      scores[alpha] = scores.get(alpha, 0) + (score(y_val, pred) / n_splits)
      print(f"{alpha}: {scores[alpha]}") if verbose else None
 
  return scores

ccp_alphaパラメータは、ペナルティ率を設定する場所です。f1_weighted関数をスコアリングに使用し、交差検証を実行することができます。

from sklearn.metrics import accuracy_score, precision_score, recall_score, f1_score
 
def f1_weighted(y_true, pred):
  return f1_score(y_true, pred, average="weighted")
 
dt_cross_validation([1, 0.1, 0.01, 0.001], f1_weighted, verbose=False)
# {1: 0.1835164835164835,
#  0.1: 0.9692698412698411,
#  0.01: 0.9688253968253968,
#  0.001: 0.9485396825396826}

交差検証の結果、ペナルティ率が0.1未満ではモデルが過学習し、ペナルティ率が0.1以上ではモデルが過少適合することがわかります。では、 0.1をモデルのペナルティ率として選択して学習させましょう。

from sklearn import tree
clf = tree.DecisionTreeClassifier(criterion="entropy", ccp_alpha=0.1)
clf.fit(X_train, y_train)

ステップ4. モデルの評価

次に、モデルを評価しましょう。ソフトマックス回帰で使用した評価方法と同じものを使用できます（ここでは混同行列を省略します）。

from sklearn.metrics import classification_report
pred = np.argmax(pred, axis=1)
y_test = np.argmax(y_test, axis=1)
 
print(classification_report(y_test, pred))
 
#               precision    recall  f1-score   support
 
#            0       1.00      1.00      1.00        15
#            1       0.91      0.95      0.93        22
#            2       0.92      0.85      0.88        13
 
#     accuracy                           0.94        50
#    macro avg       0.94      0.93      0.94        50
# weighted avg       0.94      0.94      0.94        50

上記の結果から、VersicolorとVirginicaクラス間に多少の混同があるにもかかわらず、モデルは非常に良好なパフォーマンスを発揮していることがわかります。また、決定木を使用する利点の一つは、決定木を簡単に可視化できることです。早速、決定木を可視化してみましょう。

tree.plot_tree(clf)

モデルが主に4番目の特徴（花弁の幅）を使用していることがわかります。データ探索ステップ（MLエンジニアへの道 #1 - 線形回帰モデルで確認可能）で示したように、花弁の幅を見たときに分布が最も分離されるため、これは理にかなっています。このモデルはシンプルであるにもかかわらず、非常に高いパフォーマンスを発揮していることが分かります。

注意点

高次元データは、すべての次元で類似することが困難になるため、クラスターを形成しにくくなります。そのため、決定木は、データを十分なサンプル数に分割できる良好な分割を見つけるのに苦労し、しばしば過小適合に陥ります。そのため、事前にPCAなどの次元削減を行い、決定木が識別的な特徴を見つける可能性を高めることをお勧めします（この高次元データの問題は、すべての機械学習モデルに影響を与えるため、次元の呪いとして知られています）。

さらに、max_depth、min_samples_split、min_samples_leafなど、ツリーの剪定を行うための他の多くのハイパーパラメータもあります。これらは過学習を防ぐのに役立ちます。より実用的な設定で決定木を使用する際には、これらのハイパーパラメータも調整することをお勧めします。(実際に決定木を使用する際の注意点についてもっと詳しく知りたい方は、ドキュメンテーションを参照して下さい。)

リソース

StatQuest with Josh Starmer. 2020. How to Prune Regression Trees, Clearly Explained!!!. YouTube.