· Дерево решений – это графическое представление всех возможных решений решения, основанного на определенных условиях.
· Деревья решений — это универсальные алгоритмы машинного обучения, которые могут выполнять как задачи классификации, так и регрессии, и даже задачи с несколькими выходами. Они наиболее широко используются для контролируемого обучения.
· Это мощные алгоритмы, способные работать со сложными наборами данных.
· Деревья решений работают по алгоритму CART (деревья классификации и регрессии)
Терминология дерева решений
Прежде чем мы перейдем к тому, как работает дерево решений, нам нужно понять некоторые термины дерева решений.
· Корневой узел: Это самый верхний узел, из которого строится дерево решений. Он представляет всю совокупность/выборку и далее делится на два или более узла (фиолетовый корневой узел на рисунке выше).
· Родительский/дочерний узел: корневой узел является родительским узлом, а все другие узлы, ответвляющиеся от родительского/корневого узла, называются дочерними узлами.
· Филиал/поддерево: Формируется путем разделения дерева/узла.
· Разделение: разделение корневого/подузла на разные части на основе некоторого условия.
· Конечный узел: Узел, который не может быть далее разделен/отделен, например. Оранжевый узел (самый нижний) на рисунке выше.
· Обрезка: удаление ненужных ветвей с дерева.
Алгоритм CART
Алгоритм CART (деревья классификации и регрессии) структурирован как последовательность вопросов, ответы на которые определяют, каким должен быть следующий вопрос, если он вообще должен быть. И результатом этих вопросов является древовидная структура, где концы являются листовыми/конечными узлами, где больше нет вопросов.
Построение деревьев решений зависит от следующего.
· Энтропия. Это мера случайности данных.
· Формула: Энтропия(ы) = -P(да)log2P(да)-P(нет)log2P(нет)
S - общее пространство выборки
Р(да) — вероятность утвердительного ответа, а Р(нет) — вероятность отрицательного ответа.
Если количество ответов «да» = количество ответов «нет», то, т. е. P(s) = 0,5, тогда энтропия (s) = 1
Если данные содержат только да или только нет, то есть P(s) = 1 или 0, тогда Entropy(s) = 0
· Прирост информации. Прирост информации измеряет снижение энтропии. Это решает, какой атрибут следует выбирать для разделения на каждом этапе построения дерева решений прямо из корневого узла.
Формула: прирост информации = энтропия (ы) — [(средневзвешенное значение) * энтропия (каждая функция)]
Где (средневзвешенное значение)*энтропия(каждая функция) — это информация о каждой функции.
Дерево должно быть простым для понимания, и для этого нам нужно выбрать чистое расщепление. Обычно используемой мерой чистоты является информация. Информационное значение говорит нам, сколько информации дает нам функция. Разделение с наибольшим приростом информации выбирается в качестве первого разделения, и процесс продолжается.
· Примесь Джини: сначала давайте разберемся, что такое чистый и нечистый, чистый означает, что данные выбранной выборки принадлежат к одному и тому же классу. И нечистый означает, что данные содержат смесь разных классов.
Примесь Джини — это измерение вероятности неправильной классификации. Если набор данных чистый, то вероятность неправильной классификации равна 0, в противном случае она будет высокой.
Как построить дерево решений
· Узнайте энтропию всего набора данных, используя зависимую переменную.
· Узнайте информационный прирост каждой из функций (независимых переменных) и выберите функцию с наибольшим информационным приростом в качестве корневого узла.
· Сформируйте дерево и повторите шаги, чтобы получить все дерево решений.
Теперь вы построили дерево, и пришло время протестировать его на тестовых данных, и вы обнаружите, что дерево на самом деле переобучило данные, это один из основных недостатков дерева решений. Чтобы избежать переобучения, мы удаляем ветки, использующие маловажные признаки. Этот метод называется Обрезка или Постобрезка. Он снижает сложность дерева и повышает точность тестирования. Другой метод называется ранняя остановка или предварительная обрезка. Здесь мы пытаемся остановить процесс построения дерева раньше, чем он даст листья. Одна из проблем с предварительной обрезкой заключается в том, что если мы остановимся слишком рано, мы можем недооценить данные.
Преимущества дерева решений
· Легко понять
· Может обрабатывать как категориальные, так и числовые данные
· Устойчивость к выбросам
Недостаток дерева решений
· Склонен к переоснащению
· Необходимо быть осторожным с настройкой параметров
· Может создавать предвзятые обучаемые деревья, если некоторые классы доминируют
Вопросы интервью в дереве решений
· Что такое дерево решений и как оно работает?
· Каково влияние выбросов на дерево решений?
· Как избежать переобучения в дереве решений?
· Как дерево решений работает с категориальными и числовыми признаками в одном наборе данных?
· Какие библиотеки используются для построения дерева решений?
