Деревья решений: листовое (лучшее-первое) и горизонтальное дерево

14

Выпуск 1:

Меня смущает описание LightGBM относительно способа расширения дерева.

Они заявляют:

Большинство алгоритмов обучения дерева решений растут по дереву по уровню (глубине), как показано на следующем рисунке:

введите описание изображения здесь

Вопросы 1 : Какие «большинство» алгоритмов реализованы таким образом? Насколько я знаю, C4.5 и CART используют DFS. XGBoost использует BFS. Какие другие алгоритмы или пакеты используют BFS для деревьев решений?

Выпуск 2:

LightGBM заявляет:

LightGBM выращивает дерево по листьям (лучше сначала). Он будет выбирать лист с максимальной потерей дельты для роста. При выращивании одного и того же листа, пошаговый алгоритм может уменьшить больше потерь, чем пошаговый алгоритм.

введите описание изображения здесь

Вопрос 2 : Правильно ли говорить, что деревья роста по уровню будут иметь одинаковую глубину для всех листьев?

Вопросы 3: Если Вопрос 2 не верен, то деревья, расположенные по уровню и по листьям, будут выглядеть одинаково в конце обхода (без обрезки и т. Д.). Это правильное утверждение?

Вопросы 4: Если вопрос 3 является правильным, как «листовой алгоритм может уменьшить больше потерь, чем поэтапный алгоритм»? Связано ли это с алгоритмом после сокращения?

Екатерина Кокатюхха
источник

Ответы:

11

Если вы вырастите полное дерево, наилучшее первое (по листьям) и первое по глубине (по уровню) приведет к одному и тому же дереву. Разница заключается в порядке, в котором дерево раскрывается. Поскольку мы обычно не вырастаем деревья до их полной глубины, порядок имеет значение: применение критериев ранней остановки и методов обрезки может привести к очень разным деревьям. Поскольку в конечном итоге выбирает расщепления на основе их вклада в глобальные потери, а не только потери в конкретной ветви, часто (не всегда) деревья с меньшими ошибками будут изучать «быстрее», чем по уровням. Т.е. для небольшого числа узлов, лист, вероятно, будет превосходить уровень. Когда вы добавляете больше узлов, не останавливаясь и не сокращая их, они будут сходиться с одинаковой производительностью, потому что в конечном итоге они буквально построят одно и то же дерево.

Ссылка:

Ши, Х. (2007). Best-first Learning Tree Learning (дипломная работа, магистр наук). Университет Вайкато, Гамильтон, Новая Зеландия. Получено с https://hdl.handle.net/10289/2317


РЕДАКТИРОВАТЬ: Относительно вашего первого вопроса, C4.5 и CART являются примерами глубины, а не лучше. Вот некоторые соответствующие материалы из ссылки выше:

1.2.1 Стандартные деревья решений

Стандартные алгоритмы, такие как C4.5 (Quinlan, 1993) и CART (Breiman et al., 1984), для индукции деревьев решений сверху вниз расширяют узлы в порядке первой глубины на каждом шаге, используя стратегию «разделяй и властвуй». Обычно в каждом узле дерева решений тестирование включает только один атрибут, а значение атрибута сравнивается с константой. Основная идея стандартных деревьев решений заключается в том, что, во-первых, выберите атрибут для размещения в корневом узле и сделайте несколько ветвей для этого атрибута на основе некоторых критериев (например, информации или индекса Джини). Затем разделите обучающие экземпляры на подмножества, по одному для каждой ветви, простирающейся от корневого узла. Количество подмножеств равно количеству ветвей. Затем этот шаг повторяется для выбранной ветви, используя только те экземпляры, которые действительно достигают ее. Фиксированный порядок используется для расширения узлов (обычно слева направо). Если в любое время все экземпляры в узле имеют одинаковую метку класса, которая называется чистым узлом, разбиение прекращается, и узел превращается в конечный узел. Этот процесс строительства продолжается до тех пор, пока все узлы не станут чистыми. Затем следует процесс обрезки для уменьшения переоснащения (см. Раздел 1.3).

1.2.2 Деревья решений «лучший первый»

Другая возможность, которая до сих пор, по-видимому, оценивалась только в контексте алгоритмов повышения (Friedman et al., 2000), заключается в расширении узлов в порядке наилучшего первого порядка вместо фиксированного порядка. Этот метод добавляет «лучший» разделенный узел к дереву на каждом шаге. «Лучший» узел - это узел, который максимально уменьшает примеси среди всех узлов, доступных для разделения (т.е. не помечен как терминальные узлы). Хотя это приводит к тому же полностью выращенному дереву, что и стандартное расширение в глубину, оно позволяет нам исследовать новые методы сокращения дерева, которые используют перекрестную проверку для выбора количества расширений. Таким образом можно выполнить как предварительную, так и последующую обрезку, что позволяет провести справедливое сравнение между ними (см. Раздел 1.3).

Деревья решений с наилучшим первым построением построены по принципу «разделяй и властвуй», аналогично стандартным деревьям принятия решений с глубиной. Основная идея о том, как построить дерево с лучшим первым, заключается в следующем. Сначала выберите атрибут для размещения в корневом узле и сделайте несколько веток для этого атрибута на основе некоторых критериев. Затем разделите обучающие экземпляры на подмножества, по одному для каждой ветви, простирающейся от корневого узла. В этом тезисе рассматриваются только двоичные деревья решений, и, таким образом, число ветвей равно двум. Затем этот шаг повторяется для выбранной ветви, используя только те экземпляры, которые действительно достигают ее. На каждом шаге мы выбираем «лучшее» подмножество среди всех подмножеств, доступных для расширений. Этот процесс построения продолжается до тех пор, пока все узлы не станут чистыми или не будет достигнуто определенное количество расширений. Фигура 1. На фиг.1 показана разница в порядке разбиения между гипотетическим двоичным деревом с наилучшими первыми числами и гипотетическим двоичным деревом с первыми глубинами. Обратите внимание, что для дерева с первым лучшим выбором могут быть выбраны другие порядки, в то время как порядок всегда в первом случае глубины.

Дэвид Маркс
источник
Можете ли вы также ответить на первый вопрос?
Екатерина Кокатюхха
Обновил мой ответ. Короткая версия заключается в том, что и C4.5, и CART являются примерами глубины, а не лучших.
Дэвид Маркс
Мой первый вопрос не был об определении или объяснении лучшего-первого или DFS. И я сам заявил, что C4.5 и CART - это DFS. Первый вопрос был о том, «какие« большинство »алгоритмов реализованы по уровням? [...] Какие другие алгоритмы или пакеты используют BFS для деревьев решений?»
Екатерина Кокатюхха
1
Рост дерева в глубину зависит от уровня. Это то, что я пытался тебе сказать. Прочитайте выдержку, которую я выделил для вас. Не следует путать обход DFS и BFS в графе с ростом дерева «Глубина первая» и «лучший сначала». Они не одинаковы, и глубинный рост относится к тому, что вы называете «BFS», а не «DFS».
Дэвид Маркс
Это была критическая точка, которую я все время упускал. Спасибо.
Екатерина Кокатюхха