Растущие деревья решений

Как и все модели машинного обучения с учителем, деревья решений обучаются так, чтобы лучше объяснять набор обучающих примеров. Оптимальное обучение дерева решений является NP-трудной задачей. Поэтому обучение обычно проводится с использованием эвристики — простого в создании алгоритма обучения, который дает неоптимальное, но близкое к оптимальному дерево решений.

Большинство алгоритмов, используемых для обучения деревьев решений, работают с жадной стратегией «разделяй и властвуй». Алгоритм начинается с создания одного узла (корня) и рекурсивно и жадно увеличивает дерево решений.

В каждом узле оцениваются и оцениваются все возможные условия. Алгоритм выбирает «лучшее» условие, то есть условие с наивысшим баллом. А пока просто знайте, что оценка — это метрика, которая коррелирует с задачей, и условия выбираются для максимизации этой метрики.

Например, в наборе данных Palmer Penguins (используемом для примеров кода далее в этом курсе) у большинства пингвинов Адели и Чинстрап длина клюва превышает 16 мм, тогда как у большинства пингвинов Генту клюв меньше. Следовательно, условие bill_length_mm ≥ 16 дает почти точные прогнозы для пингвинов Папуа, но не позволяет различить Адели и антарктических пингвинов. Алгоритм, вероятно, выберет это условие.

One condition leading to two leaves. The condition is 'bill_length_mm >= 16'.
If yes, the leaf is 'Adelie or Chinstrap'.  If no, the leaf
is '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: Создайте корень:

A node with a question mark.

Шаг 2: Вырастите узел №1. Было обнаружено условие «x1 ≥ 1». Создаются два дочерних узла:

A root node
   leading to two undefined nodes.

Шаг 3: Вырастите узел №2. Удовлетворительных условий не обнаружено. Итак, превратим узел в лист:

A root
   node leading to two undefined nodes.

Шаг 4: Вырастите узел №3. Было обнаружено условие «x2 ≥ 0,5». Создаются два дочерних узла.

A root node, a
condition, and three leaves.

Существуют и другие методы выращивания деревьев решений. Популярной альтернативой является глобальная оптимизация узлов вместо использования стратегии «разделяй и властвуй».

Код YDF
В YDF деревья решений по умолчанию выращиваются с использованием алгоритма «жадного разделяй и властвуй», описанного выше. Альтернативно вы можете включить глобальный рост с помощью параметра growing_strategy="BEST_FIRST_GLOBAL" . Более подробную информацию смотрите в документации .

В зависимости от количества и типа входных объектов количество возможных условий для данного узла может быть огромным, а иногда и бесконечным. Например, при заданном пороговом условии $\mathrm{feature}_i \geq t$ комбинация всех возможных пороговых значений для $t \in \mathbb{R}$ бесконечна.

Процедура, отвечающая за поиск наилучшего состояния, называется сплиттером . Поскольку необходимо проверить множество возможных условий, сплиттеры являются узким местом при обучении дерева решений.

Максимальный результат сплиттера зависит от задачи. Например:

Существует множество алгоритмов разделения, каждый из которых имеет разную поддержку:

  • Тип функций; например, числовой, категориальный, текстовый
  • Задача; например, бинарная классификация, многоклассовая классификация, регрессия
  • Тип состояния; например, пороговое условие, установленное условие, наклонное условие
  • Критерии регуляризации; например, точные или аппроксимированные разветвители для пороговых условий

Кроме того, существуют эквивалентные варианты разделителя с различными компромиссами в отношении использования памяти, использования ЦП, распределения вычислений и т. д.

Код YDF
В YDF сплиттеры выбираются неявно на основе автоматически обнаруженного (или заданного вручную) типа функции, гиперпараметров и предполагаемой скорости каждого сплиттера (во время обучения YDF запускает небольшую модель для прогнозирования скорости каждого сплиттера-кандидата).