Если вы вырастите полное дерево, наилучшее первое (по листьям) и первое по глубине (по уровню) приведет к одному и тому же дереву. Разница заключается в порядке, в котором дерево раскрывается. Поскольку мы обычно не вырастаем деревья до их полной глубины, порядок имеет значение: применение критериев ранней остановки и методов обрезки может привести к очень разным деревьям. Поскольку в конечном итоге выбирает расщепления на основе их вклада в глобальные потери, а не только потери в конкретной ветви, часто (не всегда) деревья с меньшими ошибками будут изучать «быстрее», чем по уровням. Т.е. для небольшого числа узлов, лист, вероятно, будет превосходить уровень. Когда вы добавляете больше узлов, не останавливаясь и не сокращая их, они будут сходиться с одинаковой производительностью, потому что в конечном итоге они буквально построят одно и то же дерево.
Ссылка:
Ши, Х. (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 показана разница в порядке разбиения между гипотетическим двоичным деревом с наилучшими первыми числами и гипотетическим двоичным деревом с первыми глубинами. Обратите внимание, что для дерева с первым лучшим выбором могут быть выбраны другие порядки, в то время как порядок всегда в первом случае глубины.
