このページは Cloud Translation API によって翻訳されました。

ディシジョンツリーの拡大

すべての教師あり ML モデルと同様に、ディシジョンツリーは一連のトレーニングサンプルを最もよく説明するようにトレーニングされます。ディシジョンツリーの最適なトレーニングは NP 難しい問題ですしたがって、トレーニングは通常、ヒューリスティックを使用して行われます。ヒューリスティックは、簡単に作成できる学習アルゴリズムで、最適ではないものの、最適に近いディシジョンツリーを提供します。

ディシジョンツリーのトレーニングに使用されるほとんどのアルゴリズムは、欲張りな分割統治戦略で機能します。このアルゴリズムは、まず単一のノード（ルート）を作成し、ディシジョンツリーを再帰的かつ強引に拡大します。

各ノードで、考えられるすべての条件が評価され、スコアが付けられます。このアルゴリズムは、「最良」の条件、つまり最も高いスコアを持つ条件を選択します。今のところは、スコアはタスクと相関する指標であり、その指標を最大化する条件が選択されていることだけを覚えておいてください。

たとえば、Palmer Penguins データセット（このコースの後半のコード例で使用します）では、ほとんどの Adelie ペンギンと Chinstrap ペンギンのくちばしの長さは 16 mm を超えていますが、Gentoo ペンギンのほとんどはくちばしが小さいです。したがって、bill_length_mm ≥ 16 という条件は、ジェントゥーペンギンについてはほぼ完璧な予測を行いますが、アデリースとチンストラップを区別することはできません。アルゴリズムはおそらく、この条件を選択します。

1 つの状態から 2 つのリーフが発生します。条件は「bill_length_mm >= 16」です。
「はい」の場合、葉は「Adelie or Chinstrap」です。そうでない場合、葉は「Gentoo」です。

図 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: ルートを作成します。

疑問符付きのノード。