CART（Classification and Regression Trees）の名称の由来と仕組みを解説
山崎講師こんにちは。ゆうせいです。
機械学習の分野で広く使われているアルゴリズムに決定木があります。その決定木を作成する代表的な手法の一つがCARTです。アルゴリズムの名称は一見すると複雑に見えますが、命名の背景を知ることで手法が担う機能や役割を整理できます。この記事では、CARTという名称の成り立ちとその処理の枠組みについて解説します。
CARTという名称の構成
CARTは、英語のClassification And Regression Treesの頭文字を並べた略称です。それぞれの単語は、この手法が実行できる具体的な計算処理を表しています。
分類を表すClassification
Classificationは日本語で分類を意味します。与えられた対象がどのグループに属するかを判定するタスクです。身近な例に置き換えると、果物の選別作業に似ています。ベルトコンベアを流れてくる果物の重さや色をセンサーで測定し、最終的にリンゴなのかミカンなのかを判断する処理が分類に該当します。CARTでは、集めたデータを段階的に振り分けて指定のグループへ割り当てます。
回帰を表すRegression
Regressionは日本語で回帰を意味します。ある数値を別の数値に基づいて予測するタスクです。先ほどの果物の例を用いると、果物の糖度を予測する処理にあたります。重さや日照時間といった測定値をもとに、糖度が14.5度になるか15.2度になるかといった具体的な連続する数値を算出します。CARTはグループ分けだけでなく、こうした数値予測にも対応しています。
木構造を表すTrees
Treesは複数の木を指す言葉であり、データ分析では木構造というデータの配置形式を表します。木構造は、学校や会社の組織図、あるいはトーナメント表を上下逆さまにした形状をしています。1つの頂点から枝分かれが始まり、下に向かって分岐を繰り返しながら最終的な判断へと至る構造です。
CARTの特徴と仕組み
CARTは、1984年にレオ・ブレイマンらの研究グループによって提案されました。分類と回帰の双方を同一のフレームワークで扱える点が特徴です。
二分木による条件分岐
CARTの大きな特徴は、すべての分岐が必ず2つに分かれる二分木を採用している点です。各分岐地点では、常に「Aの値は特定の基準より大きいか小さいか」という形式で判断が下されます。
分割の基準を決定する際には、純度と呼ばれる指標を用います。純度とは、分かれたグループの中に同じ種類のデータがどれだけ揃っているかを示す度合いです。分類タスクではジニ不純度と呼ばれる計算式が用いられ、グループ内の混ざり合いが最も少なくなる境界値が選ばれます。ジニ不純度の算出式は以下の通りです。グループ内のデータの種類数をK、各種類が出現する確率をp_{i}とします。
回帰タスクの場合は、グループ内の数値のばらつきを示す分散が最も小さくなる境界値が選ばれます。
CARTの利点と留意点
CARTには、構造上の特徴から生じる明確な利点と留意点が存在します。
利点
- 樹形図として可視化できるため、どのような条件分岐を経て結論に至ったかの追跡が容易です。
- データの値の大小関係のみを利用して分割を行うため、データの事前正規化を必須としません。
- カテゴリ変数の予測と連続数値の予測の双方に同一の枠組みで適用できます。
留意点
- 学習データに対して細かく分岐を作りすぎると、未知のデータに対する予測性能が低下する過学習を起こしやすくなります。
- 直交する直線でデータを区切る性質上、斜め方向の滑らかな境界を捉えるには多数の分割が必要になります。
- データのわずかな変動によって、生成される木の分岐構造が大きく変化する場合があります。
過学習を抑制するため、木を作成した後に不要な枝を切り落とす枝刈りという処理を適用するのが一般的です。
まとめ
CARTは、分類（Classification）と回帰（Regression）の両方を木構造（Trees）を用いて実行できる点からその名が付けられました。名称そのものが手法の機能と構造を端的に表しています。
CARTの理解を深めるための学習手順は以下の通りです。
- 二分木によるデータの分岐手順と、ジニ不純度による分割基準の計算法を確認する。
- 小規模なサンプルデータを用いて手計算で決定木を作成し、分類と回帰の分岐基準の差異を把握する。
- 過学習を防ぐための手法であるコスト複雑さ枝刈りのアルゴリズムを調べる。
- 単一の木を組み合わせる応用手法であるランダムフォレストや勾配ブースティングへの展開を学ぶ。
セイ・コンサルティング・グループでは新人エンジニア研修のアシスタント講師を募集しています。
投稿者プロフィール
