Алгоритм дерева решений 🌴
Сегодня рассмотрим довольно важную тему, потому что деревья решений входят в такие модели как случайные леса, градиентный бустинг, зная как строятся деревья, вы сможете понимать и грамотно применять данные алгоритмы. Деревья решений применяют как для задачи классификации, так и для регрессии.
👩🔬 Но для начала вспомним пару моментов про линейные модели:
⁃ Легко обучаются
⁃ Хорошо восстанавливают простые (линейные) зависимости
⁃ Можно усложнять при помощи спрямляющих пространств
Но, если в данных мы имеем сложные, нетривиальные зависимости, то линейные модели не смогут их восстановить 👎
В этом случае на помощь приходят деревья решений. Дерево решений можно представить в виде диаграммы (бинарного дерева), отражающей варианты действий, смотрите на картинки ☝️
До какой глубины лучше строить решающее дерево мы с вами поговорим позже, так это напрямую влияет на переобучение и как итог на результат.
‼️А теперь переходим к алгоритму:
1. Берется обучающая выборка, а также критерий ошибки (обсудим в следующих постах). На основании данного критерия подбираем оптимальный порог t, проходясь по всем значением для каждого из признаков;
2. Отыскав наилучшее значение порога t и признака, в котором достигалось наилучшее разделение, разбиваем корневую вершину (все объекты train) на левое и правое поддерево, где объекты меньшие или равные данному порогу уходят в левое поддерево, остальные в правое;
3. Для каждой из этих подвыборок процедура повторяется рекурсивно, строятся дочерние вершины, тем самым углубляется наше дерево;
4. В каждой вершине мы проверяем выполнение условия останова (например глубину дерева, кол-во объектов в листе) — и если оно выполнилось, то прекращаем разбиение и объявляем эту вершину листом;
5. Когда дерево построено, каждому листу ставится в соответствие ответ: если это задача регрессии, то усредняем значения по объектам в листе, если классификация, ищем самый часто встречаемый класс.
❓ Значений много, и можно потратить много времени на поиск наилучшего разбиения. Тогда вопрос к вам, если у нас очень много значений в признаке, то как бы вы перебирали все значения на этапе поиска оптимального порога?
Сегодня рассмотрим довольно важную тему, потому что деревья решений входят в такие модели как случайные леса, градиентный бустинг, зная как строятся деревья, вы сможете понимать и грамотно применять данные алгоритмы. Деревья решений применяют как для задачи классификации, так и для регрессии.
👩🔬 Но для начала вспомним пару моментов про линейные модели:
⁃ Легко обучаются
⁃ Хорошо восстанавливают простые (линейные) зависимости
⁃ Можно усложнять при помощи спрямляющих пространств
Но, если в данных мы имеем сложные, нетривиальные зависимости, то линейные модели не смогут их восстановить 👎
В этом случае на помощь приходят деревья решений. Дерево решений можно представить в виде диаграммы (бинарного дерева), отражающей варианты действий, смотрите на картинки ☝️
До какой глубины лучше строить решающее дерево мы с вами поговорим позже, так это напрямую влияет на переобучение и как итог на результат.
‼️А теперь переходим к алгоритму:
1. Берется обучающая выборка, а также критерий ошибки (обсудим в следующих постах). На основании данного критерия подбираем оптимальный порог t, проходясь по всем значением для каждого из признаков;
2. Отыскав наилучшее значение порога t и признака, в котором достигалось наилучшее разделение, разбиваем корневую вершину (все объекты train) на левое и правое поддерево, где объекты меньшие или равные данному порогу уходят в левое поддерево, остальные в правое;
3. Для каждой из этих подвыборок процедура повторяется рекурсивно, строятся дочерние вершины, тем самым углубляется наше дерево;
4. В каждой вершине мы проверяем выполнение условия останова (например глубину дерева, кол-во объектов в листе) — и если оно выполнилось, то прекращаем разбиение и объявляем эту вершину листом;
5. Когда дерево построено, каждому листу ставится в соответствие ответ: если это задача регрессии, то усредняем значения по объектам в листе, если классификация, ищем самый часто встречаемый класс.
❓ Значений много, и можно потратить много времени на поиск наилучшего разбиения. Тогда вопрос к вам, если у нас очень много значений в признаке, то как бы вы перебирали все значения на этапе поиска оптимального порога?