Мы только что увидели, как работает дерево решений на высоком уровне: сверху вниз оно создаёт последовательность правил, которые сегментируют данные на хорошо отделённые области для классификации. Но при наличии множества возможных вариантов, как алгоритм определяет, где именно разделять данные? Прежде чем ответить, нам нужно понять, что такое энтропия.
Энтропия измеряет количество информации о некоторой переменной или событии. Мы будем использовать её для идентификации областей, состоящих из схожих (чистых) или различных (нечистых) элементов.
Учитывая набор событий с вероятностями , общая энтропия вычисляется как:
\[ H = -\sum_{i} p_i \log_2(p_i) \]
Это количество обладает рядом ключевых свойств:
Свойства энтропии
- Минимальное значение: Энтропия равна нулю, если одна из вероятностей \( p_i \) равна 1, а все остальные равны 0. Это соответствует ситуации полной определённости, когда выборка состоит из элементов одного класса, и результат предсказуем.
- Максимальное значение: Энтропия достигает максимума, когда все вероятности \( p_i \) равны (например, \( p_i = \frac{1}{n} \) для \( n \) классов). Это соответствует максимальной неопределённости, или «нечистоте», когда классы равномерно распределены.
- Чувствительность к распределению: Любое изменение вероятностей \( p_i \), приводящее к их выравниванию (т.е. к более равномерному распределению), увеличивает энтропию , отражая рост неопределённости.
Эти свойства делают энтропию эффективным инструментом для количественной оценки чистоты набора данных в задачах классификации.
Энтропия может быть использована для количественной оценки нечистоты набора помеченных точек данных: узел, содержащий несколько классов, является нечистым, тогда как узел, включающий только один класс, является чистым.
Выше вы можете вычислить энтропию набора помеченных точек данных, принадлежащих двум классам, что типично для задач бинарной классификации. Нажмите на кнопки Добавить и Удалить, чтобы изменить состав пузыря.
Заметили, что чистые выборки имеют нулевую энтропию, а нечистые — высокие значения? Это то, что делает энтропия: измеряет, насколько чист (или нечист) набор выборок. Мы будем использовать её в алгоритме для обучения деревьев решений, определяя информационный выигрыш.
С интуицией, полученной из приведённой выше анимации, мы теперь можем описать логику обучения деревьев решений. Информационный выигрыш измеряет количество информации, которое мы получаем. Он делает это с помощью энтропии. Идея состоит в том, чтобы вычесть из энтропии наших данных до разделения энтропию каждого возможного разделения после. Затем мы выбираем разделение, которое даёт наибольшее снижение энтропии, или, что эквивалентно, наибольший прирост информации.
Информационный выигрыш рассчитывается как:
\[ Gain(S, A) = Entropy(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v) \]
где \( S \) — набор данных, \( A \) — признак, а \( S_v \) — подмножество данных для значения \( v \) признака \( A \).
Основной алгоритм для вычисления информационного выигрыша называется ID3. Это рекурсивная процедура, которая начинается с корневого узла дерева и итерируется сверху вниз по всем нелистовым ветвям в жадной манере, вычисляя на каждой глубине разницу в энтропии.
Шаги алгоритма ID3
- Вычислить энтропию, связанную с каждым признаком набора данных.
- Разделить набор данных на подмножества, используя различные признаки и пороговые значения. Для каждого вычислить информационный выигрыш \( Gain \) как разницу в энтропии до и после разделения, используя формулу выше. Для общей энтропии всех дочерних узлов после разделения использовать взвешенное среднее, учитывающее \( |S_v|/|S| \), т.е. долю выборок, попадающих на каждую дочернюю ветвь.
- Определить разделение, которое приводит к максимальному информационному выигрышу. Создать узел принятия решения на этом признаке и значении разделения.
- Когда дальнейшее разделение подмножества невозможно, создать листовой узел и пометить его наиболее распространённым классом точек данных в нём (для классификации) или средним значением (для регрессии).
- Рекурсивно выполнять на всех подмножествах. Рекурсия останавливается, если после разделения все элементы в дочернем узле принадлежат одному типу. Могут быть наложены дополнительные условия остановки, такие как минимальное число выборок на лист или достижение заданной максимальной глубины дерева.
Чтение шагов алгоритма не всегда интуитивно. Чтобы упростить понимание, вернёмся к тому, как информационный выигрыш использовался для определения первого узла принятия решения в нашем дереве.
Вспомни наше первое разделение узла принятия решения при диаметре ≤ 0.45. Как мы выбрали это условие? Это было результатом максимизации информационного выигрыша.
Каждое из возможных разделений данных по двум признакам (диаметр и высота) и пороговым значениям даёт разное значение информационного выигрыша.
Линейная диаграмма показывает различные значения разделения для признака диаметр. Перемещай границу решения самостоятельно, чтобы увидеть, как точки данных на верхней диаграмме назначаются левому или правому дочернему узлу. Внизу ты можешь увидеть значения энтропии обоих дочерних узлов и общий информационный выигрыш.
Алгоритм ID3 выберет точку разделения с наибольшим информационным выигрышем, показанную как пик чёрной линии на нижней диаграмме в 0.574 при диаметре = 0.45.
Вспомни наше первое разделение узла принятия решения при диаметре ≤ 0.45. Как мы выбрали это условие? Это было результатом максимизации информационного выигрыша.
Каждое из возможных разделений данных по двум признакам (диаметр и высота) и пороговым значениям даёт разное значение информационного выигрыша.
Визуализация справа позволяет попробовать разные значения разделения для признака диаметр. Перемещай границу решения самостоятельно, чтобы увидеть, как точки данных на верхней диаграмме назначаются левому или правому дочернему узлу. Внизу ты можешь увидеть значения энтропии обоих дочерних узлов и общий информационный выигрыш.
Алгоритм ID3 выберет точку разделения с наибольшим информационным выигрышем, показанную как пик чёрной линии на нижней диаграмме в 0.574 при диаметре = 0.45.
Альтернативой энтропии для построения деревьев решений является индекс Джини. Эта величина также является мерой информации и может рассматриваться как вариация энтропии Шеннона. Деревья решений, обученные с использованием энтропии или индекса Джини, сопоставимы, и только в редких случаях результаты существенно различаются. Для несбалансированных наборов данных энтропия может быть предпочтительнее, но индекс Джини обучается быстрее, так как не использует логарифмы.
Давай подведём итоги. Во-первых, мы увидели, как дерево решений классифицирует данные, многократно разделяя пространство признаков на области в соответствии с последовательными правилами. Во-вторых, мы узнали о энтропии, метрике для измерения чистоты набора данных. В-третьих, мы разобрались, как деревья решений используют энтропию в информационном выигрыше и алгоритме ID3 для выбора оптимальных правил. Эти разделы описывают типичный алгоритм дерева решений.
Чтобы закрепить концепции, посмотрим на наше дерево решений с другой перспективы.
Дерево ниже соответствует дереву из раздела Как построить дерево решений. Вместо отображения пространства признаков рядом со структурой дерева, мы покажем разделённые точки данных и их энтропию в каждом узле:
Сверху вниз набор точек данных уменьшается, разделяясь на узлы принятия решений и листовые узлы. Мы могли бы проследить путь любой обучающей точки данных. Обратите внимание, что не все листовые узлы чисты: как обсуждалось ранее, слишком глубокие деревья плохо обобщаются на новых данных.
Деревья решений обладают множеством преимуществ: они просты в интерпретации, быстро обучаются и требуют минимальной предварительной обработки данных. Однако их серьёзным недостатком является чувствительность к выбросам. Небольшие аномалии в обучающих данных могут радикально изменить структуру дерева, приводя к нестабильным предсказаниям.
Убедитесь сами, как добавление выбросов (например, случайных аномалий в 5% обучающих данных) создаёт совершенно разные деревья решений:
В своей базовой форме деревья решений склонны к переобучению из-за высокой чувствительности к выбросам. Алгоритм ID3, если его не ограничивать, будет разделять данные до полной чистоты листовых узлов, создавая сложные и глубокие деревья. Такие модели плохо обобщаются, так как слишком зависят от аномалий в данных.
Для предотвращения чрезмерного роста деревьев применяются методы обрезки: ограничение максимальной глубины, количества листьев или минимального числа элементов в листе. Однако проблема выбросов требует дополнительных подходов, таких как использование ансамблевых методов, например, случайных лесов.
Один из способов смягчить нестабильность, вызванную выбросами, — ввести случайность в процесс обучения. Это достигается созданием ансамблей деревьев решений, обученных на слегка разных версиях набора данных. Объединённые предсказания таких деревьев менее подвержены высокой дисперсии. Этот подход лежит в основе случайных лесов — одного из самых успешных алгоритмов машинного обучения.