В «Введении в статистическое обучение с приложениями в R» авторы пишут, что подгонка дерева решений происходит очень быстро, но для меня это не имеет смысла. Алгоритм должен пройти через каждую функцию и разделить ее всеми возможными способами, чтобы найти оптимальное разбиение. Для числовых объектов с наблюдениями это может привести к разделам для каждого объекта.
Я неправильно понимаю, как работает двоичное разбиение? Или есть причина, по которой этот алгоритм не займет много времени?
Ответы:
Алгоритмы деревьев решений не вычисляют все возможные деревья, когда они соответствуют дереву. Если бы они это сделали, они бы решали NP-хардпроблема. Алгоритмы подбора дерева решений обычно принимают жадные решения в процессе подбора - на каждом этапе они оптимизируют подзадачу для нахождения оптимального разделения с данными в данном узле и продолжают двигаться вперед в процессе подбора. Кроме того, по мере углубления в дерево решений у вас будет меньший набор данных, который попал в данный узел, так что вы будете оптимизировать правило разделения по меньшему подмножеству данных. Все эти варианты являются линейным сканированием данных в данном узле. Это не сложно сделать, но может стать несколько дорогим в вычислительном отношении, если у вас есть большое количество наблюдений или большое количество ковариат, на которые можно разделить. Тем не менее, большая часть работы может быть разделена и отправлена на разные машины для работы, так что есть способы выстроить свою вычислительную архитектуру для ее увеличения.
источник
Есть некоторые различия между алгоритмами CART и C4.5 для построения деревьев решений. Например, CART использует Gini Impurity для выбора функций, в то время как C.4.5 использует энтропию Шеннона. Я не думаю, что различия имеют отношение к ответу, поэтому я не буду различать их.
Что делает деревья решений быстрее, чем вы думаете:
and
приведет к лучшему дереву. Это означает, что вы должны быть очень осторожны / умны при разработке функций. Например, скажем, вы пытаетесь предсказать, сколько людей пьют, возможно, вы захотите представить такие вещи, как инженерnew_feature = hour > 22 & hour < 4 & (friday_night | saturday_night)
. Деревья решений могут пропускать такие правила или придавать им меньшее значение, чем должны.X <= 1
X <= 1.5
X <= 2
X <= 1
X <= 1.5
xgboost
быстрыми. Повышение градиента является последовательным и не может быть распараллелено, но сами деревья могут.источник
Просто чтобы обогатить ответы,
Иерархические оси параллельных решений быстро (CART, C4.5), но есть и другие альтернативы, такие как неиерархические деревья решений или те, которые выполняют косые разбиения, которые не являются, хотя они могут быть более точными. Проверьте следующие ссылки, если вы заинтересованы (они не являются исчерпывающим выбором).
Non-иерархическая:
Грубингер, Т., Зейлейс, А. и Пфайффер, К.-., 2014. Evtree: Эволюционное изучение глобально оптимальных деревьев классификации и регрессии в RJStat.Software 61 (1), 1-29.
Косой раскол:
Мурти, С. К., Касиф, С. и Зальцберг, С., 1994. Система для индукции косых деревьев решений. J. Artif. Интелл. Местожительство 2 (1), 1-32. http://dx.doi.org/doi:10.1613/jair.63 . Cantú-Paz, E. and Kamath, C., 2003. Индуцирование наклонных деревьев решений с помощью эволюционных алгоритмов. IEEE Trans. Evol. Вычи. 7 (1), 54-68. http://dx.doi.org/10.1109/TEVC.2002.806857 . Хит, Д., Касиф, С. и Зальцберг, С., 1993. Индукция косых деревьев решений. J. Artif. Интелл. Местожительство 2 (2), 1002-1007.
Удачи!
источник