В эфире уже практически традиционная рубрика «базовые алгоритмы ML». Сегодня мы поговорим про решающие деревья.
Вы наверняка уже встречались с методом решающих деревьев в машинном обучении. Причём, скорее всего, в максимально далёких от ML областях: в инструкциях по обслуживанию оборудования, психологических тестах, детских журналах… Это похоже на игру: вы делаете выбор, переходите по стрелке, делаете новый выбор — пока не доберётесь до результата в конце страницы.
В широком смысле решающее дерево в Python — это связный ориентированный граф без циклов, где:
● внутренние узлы — функции от признаков объекта;
● исходящие из узла рёбра — значения, которые может принимать функция;
● листья — все возможные решения задачи.
Звучит сложно, но по большому счёту деревья «думают» примерно так же, как мы с вами: один за другим отвечая на вопросы и отсекая неподходящие варианты.
Представьте, что можете добраться до работы тремя разными способами — и каждое утро выбираете один из них. Если погода скверная, сразу вызываете такси. Если хорошая — прикидываете, успеете ли вовремя на велосипеде. Если уже опаздываете, то прыгаете в автобус.
Чтобы автоматизировать процесс принятия такого решения, достаточно вручную написать мини-дерево из пары условий if / else. Но что делать, если и признаков, и ответов на задачу намного больше? Конечно же, обучать модель.
Смысл в том, что алгоритм должен выполнить построение решающих деревьев на основе обучающей выборки. Здесь есть важный нюанс, связанный с иерархией признаков.
Скажем, мы хотим определить, кто из членов британской королевской семьи стоит у нас за спиной. Конечно, можно первым делом спросить: «Вам больше 90 лет?» — но если это не Елизавета II, мы практически не продвинемся в поиске. Куда разумнее будет начать с фундаментального: «Вы мужчина или женщина?» — и сразу отсечь половину кандидатов.
То есть при построении решающих деревьев в каждом новом узле следует выбирать не случайный, а оптимальный признак. Часто для этого применяют «критерий информативности»: после разбиения должны получаться максимально упорядоченные подвыборки (например, с самой маленькой энтропией или средней квадратической ошибкой).
Разбиения можно продолжать, пока все объекты в каждой концевой вершине не будут принадлежать к одному классу. Но это не всегда нужно! Такое дерево, скорее всего, окажется переученным — то есть при идеальных результатах на обучающей выборке оно будет некорректно работать на незнакомых данных.
Чтобы модели вовремя прекращали обучение, существуют так называемые «критерии останова». Это значения, по достижении которых алгоритм глохнет: определённая глубина дерева, число объектов в листе, количество листьев.
В реальном ML мы чаще всего имеем дело не с отдельными решающими деревьями, а с их ансамблями — это когда куча деревьев собираются вместе и устраивают голосование :) На ансамблях строятся такие методы, как бэггинг, бустинг, случайный лес — но все они, конечно, заслуживают отдельных постов.
