Деревья решений. Bagging. Random Forest. Boosting. Лекция 6

2 основных вида
CART (Classification and Regression Tree) – это алгоритм построения бинарного дерева решений. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии. Используется в scikit-learn.
C4.5 – алгоритм построения дерева решений, количество потомков у узла не ограничено. Решает только задачи классификации.

Терминология

Жадные:
«берут все, что дают, не отдают»
Большинство из известных алгоритмов являются "жадными алгоритмами".
Перебирают все признаки и все возможные значения в выборке.
Если один раз был выбран атрибут, и по нему было произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение.
И поэтому на этапе построения нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение.
По https://basegroup.ru/community/articles/description

Алгоритм
Первое множество (корень) : есть ли такие два подмножества, которые улучшат предсказания? Подмножества определим по какому-то признаку и его значению. Делим первое множество.
И так поступаем далее. Однако если улучшения нет, или достигли порог ошибки, или решили остаться на этой глубине дерева, то это лист.

Критерии разбиения:
Классификация
https://habr.com/en/company/ods/blog/322534/#kak-stroitsya-derevo-resheniy

Критерии разбиения: Регрессия.
«Улучшат предсказания».

Bagging, Random Forests, Boosting
Random forest Grow many deep regression trees to randomized versions of the training data, and average them. Here “randomized” is a wide ranging term, and includes bootstrap sampling (bagging) and/or subsampling of the observations, as well as subsampling of the variables.
Boosting Repeatedly grow shallow trees to the residuals, and hence build up an additive model consisting of a sum of trees.
https://web.stanford.edu/~hastie/CASI_files/PDF/casi.pdf

Random Forest лучше Lasso, Tree, Bagging
в этом показательном примере

Boosting бьет Random Forest
в этом показательном примере
As is often the case, boosting slightly outperforms a random forest here, but at a price. Careful tuning of boosting requires considerable extra work, with time-costly rounds of cross-validation, whereas random forests are almost automatic.