すべての教師あり ML モデルと同様に、ディシジョン ツリーは最適なトレーニング 一連のトレーニング例を説明しますディシジョン ツリーの最適なトレーニングは、 問題になります。そのため、トレーニングは通常、ヒューリスティックを使用して行われます。 最適ではないものの、より現実に近い 決定します
ディシジョン ツリーをトレーニングするために使用されるアルゴリズムのほとんどは、貪欲な除算と 獲得戦略です。アルゴリズムはまず単一のノード（ルート）を作成し、 反復的かつ貪欲にディシジョン ツリーを成長させます。
各ノードで、考えられるすべての条件が評価され、スコアが付けられます。「 アルゴリズムで「最も良い」つまり、最も優先度が高い スコアです。とりあえず、スコアは指標と相関関係にあることを その指標が最大になるように条件が選択されます。
たとえば、Palmer ペンギン （このコースの後半のコードサンプルで使用）、Adelie と Chinstrap のほとんどの ペンギンはくちばしの長さが 16 mm を超える。 ペンギンはくちばしが小さいから。したがって、条件は bill_length_mm ≥ 16 であれば、 ジェンツー ペンギンだが、区別できない アデリーズとチンストラップの差です。アルゴリズムはおそらくこの条件を選択します。
<ph type="x-smartling-placeholder"></ph> 図 7：樹木を育てるための最初のステップ。 で確認できます。
このアルゴリズムは、両方の子ノードで再帰的に独立して繰り返されます。 満たす条件が見つからなければ、そのノードはリーフになります。リーフ サンプルの中で最も代表的なラベル値として決定されます。
アルゴリズムは次のとおりです。
def train_decision_tree(training_examples):
root = create_root() # Create a decision tree with a single empty root.
grow_tree(root, training_examples) # Grow the root node.
return root
def grow_tree(node, examples):
condition = find_best_condition(examples) # Find the best condition.
if condition is None:
# No satisfying conditions were found, therefore the grow of the branch stops.
set_leaf_prediction(node, examples)
return
# Create two childrens for the node.
positive_child, negative_child = split_node(node, condition)
# List the training examples used by each children.
negative_examples = [example for example in examples if not condition(example)]
positive_examples = [example for example in examples if condition(example)]
# Continue the growth of the children.
grow_tree(negative_child, negative_examples)
grow_tree(positive_child, positive_examples)
特定のディシジョン ツリーをトレーニングする手順を 詳しく見ていきます。
ステップ 1: ルートを作成します。
ステップ 2: ノード #1 を拡張します。条件「x1 ≥ 1」見つかりました。 次の 2 つの子ノードが作成されます。
ステップ 3: ノード #2 を拡張します。満たす条件が見つかりませんでした。したがって、ノードを 次のように置き換えます。
ステップ 4: ノード #3 を拡張します。x2 ≥ 0.5 という条件見つかりました。子ども 2 人 ノードが作成されます。
ディシジョン ツリーを成長させる方法は他にもあります。一般的な代替手段としては、 分割統治戦略を使用せずにノードをグローバルに最適化する。
growing_strategy="BEST_FIRST_GLOBAL" パラメータを指定して増加させることもできます。
<ph type="x-smartling-placeholder"></ph>をご覧ください。
ドキュメントをご覧ください。
入力特徴の数と種類に応じて、入力特徴の数は ある特定のノードについて考えられる条件は巨大になる可能性があり、通常は無限です。 たとえば、しきい値の条件が $\mathrm{feature}_i \geq t$ であるとすると、 組み合わせた 可能性 しきい値を $t \in \mathbb{R}$ は無限大です。
最適な状態を見つけるルーティンのことを、 splitter を使用します。スプリッターは、考えられる多くの条件をテストする必要があるため、 ディシジョン ツリーをトレーニングする際のボトルネックになります。
スプリッターによって最大化されるスコアは、タスクによって異なります。次に例を示します。
スプリッター アルゴリズムは数多くあり、それぞれが以下をサポートしています。
- 特徴のタイプ例: 数値、カテゴリ、テキスト
- タスクたとえば、バイナリ分類、マルチクラス 分類、回帰
- 条件のタイプ。たとえば、しきい値条件、セット内の条件、 傾斜条件
- 正則化の基準正確なスプリッターや近似スプリッターなど、 （しきい値条件）
さらに、トレードオフが異なる同等のスプリッター バリアントもある CPU 使用率、計算分散などです。