Table of Contents

Введение: деревья решений и потребность в чистоте

Деревья решений являются одним из наиболее интуитивно понятных и широко используемых контролируемых алгоритмов обучения в машинном обучении. Они моделируют решения как древовидную структуру, где внутренние узлы представляют собой тесты на функции, ветви представляют результаты этих тестов, а узлы листьев представляют окончательные прогнозы. Независимо от того, классифицируете ли вы электронную почту как спам или прогнозируете цены на жилье, деревья решений предлагают прозрачный, понятный для человека подход.

Основная задача при построении дерева решений — это решение , где разделить данные на каждом узле. Алгоритм должен выбрать функцию и значение разделения, которое лучше всего разделяет целевые классы. Вот где появляется энтропия. Энтропия, заимствованная из теории информации, обеспечивает математическую меру неопределенности или примеси в наборе данных. Минимизируя энтропию после каждого разделения, деревья решений создают все более однородные подмножества, что приводит к точным и эффективным моделям.

Что такое энтропия? - Мера расстройства

В повседневном языке энтропия относится к случайности или хаосу.В контексте деревьев решений энтропия количественно определяет количество непредсказуемости в наборе данных относительно целевой переменной.Если все примеры в узле принадлежат к одному классу, узел является чистым и его энтропия равна нулю.Наоборот, если классы равномерно перемешаны, энтропия достигает своего максимума.

Для задачи бинарной классификации (например, положительной против отрицательной) энтропия определяется как:

Энтропия = -p+ log2(p+) - p− log2(p−)

где p+ - доля положительных примеров и p−=1 - p+. Логарифмическое основание 2 используется потому, что информация в битах измеряется в двоичном. Когда существует более двух классов, формула обобщает:

Энтропия = —Σ pi log2(pi) для всех классов i.

Полученное значение колеблется от 0 (совершенно чистое) до log2(k) для k классов (максимальная примесь). Для двоичного случая максимальная энтропия составляет 1,0 при p+ = p− = 0,5.

Быстрый пример

Рассмотрим набор данных из 10 образцов с 5 положительными и 5 отрицательными. Энтропия = -0,5 log2(0,5) - 0,5 log2(0,5) = -0,5 * (-1) - 0,5 * (-1) = 0,5 + 0,5 = 1,0. Теперь рассмотрим набор данных с 9 положительными и 1 отрицательными: энтропия = -0,9 log2 (0,9) - 0,1 log2 (0,1) ≈ -0,9 * (-0,152) - 0,1 * (-3,322) ≈ 0,137 + 0,332 = 0,469. Второй набор данных гораздо более предсказуем.

Почему именно 2-я база?

Выбор базы 2 коренится в информационной теории Клода Шеннона. Бит — фундаментальная единица информации, представляющая двоичный выбор. Использование базы 2 означает, что энтропия даёт среднее количество битов, необходимых для кодирования класса случайной выборки. Если вы уже знаете распределение, более низкая энтропия означает, что для передачи результата требуется меньше битов.

Получение информации: как энтропия разделяется

Простого расчета энтропии недостаточно; цель состоит в том, чтобы уменьшить после расщепления. Прирост информации (IG) измеряет ожидаемое снижение энтропии, вызванное разделением данных в соответствии с признаком. Для узла выбираются признак и значение расщепления, которые дают наибольший прирост информации.

Формула получения информации заключается в следующем:

Информационный прирост = энтропия (родитель) — Σ ( |Si | / |S |) * Энтропия (Si)

где S — родительский набор данных, Si — дочерние подмножества после разделения, и |. | обозначает количество образцов. Сумма — средневзвешенное значение энтропий детей.

Работающий пример

Представьте себе родительский узел с 30 образцами: 16 класса А и 14 класса В. Энтропия (родитель) = -(16/30) log2(16/30) - (14/30) log2(14/30) ≈ 0,996.

Теперь рассмотрим разделение на Функцию X, которая создает двух детей: Ребенок1 имеет 20 образцов (15 А, 5 В) → энтропия = -0,75 log2 (0,75) - 0,25 log2 (0,25) ≈ 0,811; Ребенок2 имеет 10 образцов (1 А, 9 В) → энтропия = -0,1 log2 (0,1) - 0,9 log2 (0,9) ≈ 0,469. Весовая детская энтропия = (20/30)*0,811 + (10/30)*0,469 ≈ 0,541 + 0,156 = 0,697. Информационный прирост = 0,996 - 0,697 = 0,299.

Если другой сплит дает более высокий IG, этот сплит предпочтителен. Алгоритм оценивает все функции и возможные пороги сплита, чтобы найти лучший.

Ограничения получения информации

Информационный прирост имеет тенденцию благоприятствовать функциям со многими различными значениями (например, уникальная колонка ID), потому что разделение на такой функции создает много чистых детей, что приводит к высокому IG. Это может привести к переоборудованию. Чтобы противостоять этому, варианты, такие как Gain Ratio (используемый в C4.5) нормализуют IG внутренней информацией разделения. Другой подход заключается в использовании Gini примеси , которая вычислительно дешевле и часто дает аналогичные результаты.

Сравнение энтропии с примесями Джини

Примеси Джини — альтернативный критерий расщепления, используемый в алгоритме CART (Classification and Regression Trees). Он измеряет вероятность неправильной классификации случайно выбранной выборки, если она была помечена случайным образом в соответствии с распределением классов в узле. Формула:

Джини = 1 — Σ pi2

Для двоичного случая Джини = 2p+(1 – p+). Максимальный Джини составляет 0,5 (сбалансированные классы) и минимальный 0 (чистый).

И энтропия, и примесь Джини — выпуклые функции, то есть на практике они ведут себя одинаково. Выбор между ними часто сводится к вычислительной эффективности: Джини не требует логарифмов, поэтому может быть немного быстрее. Однако энтропия имеет более сильное информационно-теоретическое обоснование. Многие библиотеки, в том числе scikit-learn, можно выбрать либо; эмпирически различия невелики.

Энтропия в деревьях регрессии

Дерево решений может также решать задачи регрессии (прогнозирование непрерывных значений). В регрессии энтропия неуместна, потому что цель не категорична. Вместо этого алгоритм использует снижение дисперсии или среднюю квадратную ошибку (MSE) в качестве критерия расщепления. Идея аналогична: на каждом узле мы расщепляемся, чтобы минимизировать взвешенную сумму дисперсий детских узлов. Это максимизирует однородность целевых значений в каждой области.

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

Построение дерева решений: от корня до листа

Теперь, когда мы понимаем энтропию и получение информации, давайте рассмотрим, как типичный алгоритм обучения дерева решений (например, ID3, C4.5 или CART) строит дерево:

  1. Начните со всего набора данных в корневом узле.
  2. Вычислить примеси корня с помощью энтропии (для классификации) или дисперсии (для регрессии).
  3. Для каждой функции, оценить каждую возможную точку разделения (для числовых функций, сортировать значения и рассмотреть средние точки между последовательными различными значениями; для категориальных признаков рассмотреть подмножества или одногорячее кодирование).
  4. Вычислить коэффициент усиления информации (или коэффициент усиления, уменьшение Джини и т.д.) для каждого разбиения.
  5. [[ФЛТ:0]]Выберите раздвоение [[ФЛТ:1]], которое приносит наибольшую прибыль.
  6. Разделите данные и повторяйте шаги 2-5 для каждого узла ребенка.
  7. Критерии остановки (FLT:0) предотвращают бесконечный рост: максимальная глубина, минимальные образцы на лист, минимальное уменьшение примесей или когда все образцы в узле принадлежат к одному классу.
  8. Прун Дерево (либо предварительное сканирование с помощью гиперпараметров, либо после скручивания путем сокращения ветвей, которые не улучшают производительность на наборе проверки) для борьбы с переобучением.

Обработка категориальных и численных особенностей

Расщепление на основе энтропии работает для обоих типов функций, но подход отличается:

  • Численные особенности: Алгоритм сортирует уникальные значения и проверяет каждый возможный порог.Для эффективности он часто рассматривает только пороги между последовательными сортированными значениями, где изменяется ярлык класса.
  • Категорические особенности: Для бинарных разбиений алгоритм может рассматривать группирование категорий на два подмножества. Для многосторонних разбиений (как в ID3) каждая категория становится ветвью. Однако многосторонние разбиения фрагментируют данные быстро и склонны к переоборудованию, поэтому большинство современных реализаций используют бинарные разбиения даже для категориальных признаков.

Устранение недостающих ценностей

Наборы данных в реальном мире часто содержат недостающие значения. Деревья решений могут обрабатывать их несколькими способами:

  • Суррогатное разделение : При разделении на функцию резервная функция, которая лучше всего имитирует разделение, используется для образцов, в которых отсутствует основная функция.
  • Фракциональные экземпляры: Назначение выборки для нескольких детей с весами, пропорциональными вероятности каждого ребенка на основе непропущенных данных.
  • Простая вычисление : Заменить недостающие значения режимом или медианой перед постройкой дерева.

Многие библиотеки, такие как scikit-learn, не обрабатывают отсутствующие значения внутри и ожидают, что они будут вменены заранее. XGBoost и LightGBM, однако, изучают лучшее направление для отсутствующих значений во время обучения.

Переоборудование и обрезка

Дерево решений, выращенное до максимальной глубины, отлично запоминает данные обучения, включая шум, что приводит к плохому обобщению. Снижение энтропии продолжается до тех пор, пока каждый лист не станет чистым, но это редко приносит пользу производительности теста. Две основные стратегии контроля над переобучением:

Ранний останов (Early Stopping)

Остановить рост дерева до того, как оно перевыполнится, применяя ограничения: ограничить максимальную глубину, потребовать минимальное количество образцов на лист или потребовать минимального уменьшения примеси (например, уменьшение энтропии должно быть > 0,01).

Пост-пранинг (Cost-Complexity Pruning)

Выращивайте дерево полностью, затем удаляйте ветви, которые добавляют небольшую ценность. Алгоритм рассматривает компромисс между сложностью дерева (количество листьев) и ошибкой обучения. Параметр сложности (альфа) наказывает дополнительные листья. Scikit-learn's предлагает обрезку с учетом сложности затрат через .

Обе техники обрезки помогают гарантировать, что энтропийные расщепления не слишком гранулярны и что дерево остается интерпретируемым при правильном обобщении.

Энтропия в методах ансамбля

Хотя одно дерево решений может быть нестабильным (небольшие изменения в данных могут привести к совершенно другому дереву), энтропия остается основополагающим понятием в ансамбле методов:

  • Случайные леса: Постройте много деревьев, используя образцы бутстрапа и случайные подмножества признаков. Каждое дерево обычно использует энтропию или Джини для разделения. Лес усредняет прогнозы, уменьшая дисперсию.
  • Градиентное увеличение: Деревья строятся последовательно для исправления ошибок предыдущих деревьев.Энтропия используется в качестве цели (через кросс-энтропийную потерю) для классификации лесов в библиотеках, таких как XGBoost.

Понимание энтропии помогает понять, почему определенный раскол был выбран в любом отдельном дереве, что важно для отладки модели и анализа важности признаков.

Практические соображения при использовании энтропии

Во-первых, вычислить энтропию с использованием логарифмов осторожно - избежать неопределенного log(0) путем определения 0 log2(0) как 0. Во-вторых, имейте в виду, что вычисления энтропии чувствительны к дисбалансу классов; узел с 99% одного класса и 1% другого имеет низкую энтропию, но может не указывать на хорошее разделение, если класс меньшинства важен.

Кроме того, деревья решений с энтропией могут быть интенсивными для памяти больших наборов данных, потому что они оценивают все функции и точки разделения. Библиотеки используют алгоритмы, такие как , чтобы вычислить энтропию для числовых функций во времени O(n log n).

Внешние ссылки для более глубокого чтения:

За пределами классификации: энтропия и получение информации при выборе функций

Энтропия используется не только внутри деревьев решений — она также поддерживает методы выбора признаков. Взаимная информация между признаком и целью напрямую связана с получением информации. Вы можете ранжировать функции по их взаимной информации, чтобы уменьшить размерность перед обучением других моделей. Это нелинейная альтернатива корреляционному анализу.

Например, если функция X имеет высокую взаимную информацию с целью Y, то знание X существенно снижает неопределенность относительно Y. Это именно то снижение энтропии, которое достигается путем разделения на X. Библиотеки, такие как scikit-learn, предоставляют и .

Ограничения деревьев решений на основе энтропии

Несмотря на свою силу, деревья решений, построенные с помощью энтропии, имеют некоторые недостатки:

  • Нестабильность: Небольшие изменения набора данных могут резко изменить структуру дерева.
  • Биас к функциям со многими уровнями: Получение информации благоприятствует функциям с высокой степенью кардинальности. Соотношение выигрыша или использование только бинарных разбиений помогает.
  • Плохое обращение с аддитивной структурой: Деревья являются по частям постоянными моделями, поэтому они изо всех сил пытаются изучить линейные отношения.
  • Жадность : Алгоритм делает локально оптимальные расщепления, которые могут быть не глобально оптимальными.

На практике сочетание деревьев решений на основе энтропии с надлежащими методами настройки гиперпараметров и ансамблей дает надежные модели для многих табличных наборов данных.

Вывод: Энтропия как основа для проницательных расколов

Энтропия обеспечивает принципиальный, информационно-теоретический способ оценки качества раскола при построении дерева решений. Измеряя расстройство в наборе данных и стремясь уменьшить его на каждом шаге, мы можем строить деревья, которые эффективно и точно разделяют пространство функций. Независимо от того, являетесь ли вы студентом, изучающим машинное обучение или практиком, развертывающим модели, понимание энтропии углубляет ваше понимание того, как деревья решений «думают». Это также связано с более широкими концепциями, такими как взаимная информация, выбор функций и даже сжатие данных.

Применяя деревья решений, помните, что энтропия — это инструмент, а не конец. Совместите ее с надлежащими методами проверки, обрезки и ансамбля, чтобы раскрыть весь ее потенциал. И если вы управляете конвейерами данных для машинного обучения, такие инструменты, как Directus, могут помочь вам собирать, организовывать и обслуживать высококачественные наборы данных, от которых зависят деревья решений.