Пошаговое руководство по обрезке деревьев решений для лучшей генерализации

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

Это руководство обеспечивает подробный переход от основной теории к практическим шагам реализации. Независимо от того, строите ли вы дерево с нуля или настраиваете модель в библиотеке, такой как scikit-learn, понимание того, когда и как обрезать, имеет решающее значение для достижения надежной производительности. Мы рассмотрим как предварительную, так и послеобрезку, углубимся в обрезку с учетом затрат (наиболее широко используемый метод постобрезки), обсудим стратегии оценки и поделимся передовым опытом, чтобы избежать распространенных ошибок. К концу вы будете оснащены для уверенной обрезки деревьев решений и создания моделей, которые обеспечивают правильный баланс между предвзятостью и дисперсией.

Посмотреть Дерево решений

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

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

Почему обрезка? Стоимость переобучения

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

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

Типы обрезки: предварительная обрезка против постобрезки

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

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

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

Механика пост-обрезки: пошаговое руководство

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

Шаг 1: вырастить полностью развитое дерево решений

Первый шаг - обучить дерево решений данным обучения без каких-либо ограничений по глубине или размеру листа. Позвольте дереву расти до тех пор, пока каждый лист не будет чистым (или как можно более чистым) или пока дальнейшее разделение не сможет уменьшить меру примеси (например, примеси Джини или энтропии). Это «максимальное» дерево будет иметь много внутренних узлов и листьев. Это почти наверняка переобучение данных обучения, но это приемлемо - шаг обрезки исправит его.

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

Шаг 2: Оцените результативность дерева

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

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

Шаг 3: обрезать дерево с помощью обрезки с учетом затрат

Обрезка с наименьшей сложностью затрат (также известная как обрезка с наименьшей сложностью ссылок) является стандартным методом постобрезки, используемым библиотеками, такими как scikit-learn и R's rpart. Он работает, вводя штраф за сложность дерева. Для данного дерева T, определите меру сложности затрат R_α(T) = R(T) + α * |T |, где R(T) - скорость неправильной классификации (или сумма квадратных ошибок) на данных обучения, |T | - количество листовых узлов (прокси для сложности), а α (альфа) - параметр неотрицательной сложности. По мере увеличения α стоимость наличия большего количества листьев растет, поэтому алгоритм предпочитает меньшие деревья.

Процесс обрезки начинается с полного дерева (α=0). Затем он идентифицирует «слабое звено» — внутренний узел, удаление которого дает наименьшее увеличение R(T) на удаленный лист. Этот узел обрезается (преобразуется в лист), и записывается новое дерево. Процесс повторяется, производя последовательность вложенных поддеревьев (каждый потомок предыдущего) по мере увеличения α. Для каждого α существует соответствующее оптимальное поддеревье, которое минимизирует R_α(T).

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

Пример практического осуществления

В scikit-learn’s вы можете получить доступ к обрезке с учётом сложности затрат по параметру . Библиотека предоставляет метод , который возвращает эффективные альфа- и соответствующие примеси. Затем вы тренируете дерево с выбранным . Полный код прост и хорошо документирован в документации по обрезке с учётом сложности затрат .

Шаг 4: Проверить обрезанное дерево

После выбора оптимального α обучить конечное дерево на полном обучающем наборе (или комбинированный поезд + вал, если вы использовали один валидационный сплит) с использованием этого α. Затем оценить его производительность на отдельном тестовом наборе, который никогда не использовался для обрезки решений. Эта окончательная оценка дает вам объективную оценку того, насколько хорошо обрезное дерево будет обобщать в производстве.

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

Сокращение издержек в деталях

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

Ключевая математическая идея — критерий «слабейшей связи». На каждом этапе алгоритм вычисляет для каждого внутреннего узла значение g(t) = (R(t) − R(T_)]t[1]), где R(t) — скорость неправильной классификации, если узел t был превращен в лист, R(T_]t — скорость неправильной классификации поддеревья, корнями уходящего в t, и |T_t — количество листьев в этом поддереве. Узел с наименьшим g(t) — самое слабое звено — это способствует наименьшему уменьшению ошибок на лишний лист. Обрезка, которую узел даёт следующему поддереву в последовательности для α = g(t). По мере прогрессирования алгоритма α увеличивается монотонно, а деревья становятся меньше.

Этот метод имеет прочные теоретические основы. Он гарантирует, что последовательность поддеревьев является оптимальной в том смысле, что для любого α, поддеревья, которое минимизирует R_α(T) можно найти, следуя этому пути обрезки слабейшей линии связи. На практике практикующие часто выстраивают ошибку проверки против log(α) для идентификации области, где ошибка стабилизируется. Увеличение α за пределами этой точки приводит к недооборудованию, в то время как уменьшение его приводит к переоборудованию.

Выбор альфа с перекрестной валидацией

Надежный способ выбора α - это использование перекрестной валидации на данных обучения. Для каждой складки вычислите полное дерево и его путь обрезки, затем оцените каждое поддеревье на удерживаемой складке. Усредните ошибки проверки по складкам для каждого значения α, затем выберите α, которая минимизирует среднюю ошибку. Общая эвристика - выбрать самую большую α в пределах одной стандартной ошибки минимума (правило 1-SE) в пользу более простых моделей. Это правило особенно полезно, когда кривая ошибок плоская вблизи минимума, поскольку она защищает от переподгонки к набору проверки.

После выбора α переобучите дерево на всем обучающем наборе с этим . Полученное дерево будет окончательной, обрезанной моделью. Эта процедура реализована во многих статистических учебных библиотеках; например, Введение в статистическое обучение обеспечивает отличную обработку обрезки с учетом сложности затрат с примерами в R.

Оценка обрезанных деревьев

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

• Сравните с полным деревом : Сообщите о производительности как полного дерева, так и обрезанного дерева на тестовом наборе. Обрезанное дерево должно показывать меньший разрыв между обучением и точностью тестирования (что указывает на снижение переобучения). Если обрезанное дерево работает хуже, чем полное дерево на тестовом наборе, обрезка может быть слишком агрессивной.
• Использовать кривые обучения: Ошибка обучения и проверки участка в зависимости от размера дерева или α. Расширяющийся разрыв между двумя кривыми сигнализирует о переобучении; обрезка должна закрыть этот разрыв. Контролируя формы этих кривых, можно определить оптимальный диапазон сложности.
• Сложность измерения непосредственно: Подсчитайте количество листьев и глубину конечного дерева. Хорошо изрезанное дерево могло бы иметь, например, 20 листьев вместо 200, что значительно облегчает объяснение. Сообщите эти показатели вместе с точностью, чтобы дать полную картину.
• Проверка на множественные случайные сплиты: Поскольку на решения обрезки влияет сплит обучения/валидации, попробуйте несколько случайных сплит или повторную перекрестную валидацию. Если оптимальное α широко варьируется, данные могут быть слишком шумными, и вам следует рассмотреть другие подходы к моделированию.

Толкование срезанного дерева

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

Лучшие практики для эффективной обрезки

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

• Всегда используйте отдельный набор валидации или перекрестную валидацию при обрезке. Никогда не используйте производительность тренировочного набора, чтобы решить, сколько срезать; это приведет к оптимистическому уклону.
• Эксперимент как с предварительной, так и с постпранинговой .В то время как постпранинг, как правило, превосходит, сочетание мягкого предпраунингового предела (например, минимальных образцов на лист 5-10) с последующей постпранинговой подготовкой может сократить время обучения без ущерба для качества.
• Сложность и точность баланса. Цель состоит не в том, чтобы достичь максимально возможной точности на обучающем наборе, а в том, чтобы минимизировать ошибку обобщения. Используйте кривые валидации, чтобы найти точку, где добавление большего количества узлов дает уменьшающуюся отдачу.
• Избегать чрезмерной обрезки . Дерево, которое обрезано слишком сильно, может не соответствовать, отсутствуя важные узоры. Если обрезное дерево имеет значительно худшую точность испытания, чем немного большее дерево, рассмотрите возможность ослабления прочности обрезки (например, выбирая меньшую α).
• Используйте знания домена, когда они доступны. Если известно, что некоторые функции не имеют отношения к делу или ненадежны, вы можете вручную исключить их из раздельных кандидатов. Но обрезка часто автоматически удаляет расколы на слабых функциях.
• Документировать стратегию обрезки. В производственных системах записывать выбранное α, количество листьев и результаты перекрестной валидации. Эта документация помогает с циклами мониторинга и переподготовки моделей.

Распространенные подводные камни в обрезке деревьев решений

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

• Обрезка без перекрестной валидации: Использование одного набора валидации для руководства обрезкой может привести к переоборудованию этого набора валидации (иногда называемого «переобучением набора валидации»).
• Игнорирование пути сложности затрат: Прыжок непосредственно к определённой α без изучения всего пути обрезки может привести к тому, что вы пропустите лучшее поддеревье. Всегда генерируйте полную последовательность альфа-фаз и оценивайте каждую.
• Применение обрезки к чрезвычайно небольшим наборам данных: Когда данных мало, любой раскол может быть ненадежным. Рассмотрим использование предварительной обрезки (неглубокое дерево) вместо постобрезки или используйте альтернативную модель, которая лучше обрабатывает небольшие образцы.
• Использование ненадлежащих мер по примесям: Джини и энтропия обычно дают аналогичные результаты, но для деревьев регрессии снижение дисперсии является стандартным.
• Забыв переквалифицироваться после обрезки : После выбора α через перекрестную валидацию, вы должны переквалифицировать дерево на весь набор данных обучения с этим α. Некоторые практикующие ошибочно используют поддеревья из одной сгиба перекрестной валидации, что вводит предвзятость.

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

Заключение

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

Преимущества обрезки выходят за рамки точности: меньшие деревья быстрее оцениваются, легче развертываются и более надежны в средах с высокими ставками. Кроме того, процесс обрезки заставляет вас противостоять компромиссу смещения-вариантности напрямую, углубляя ваше понимание того, как ведет себя модель. По мере приобретения опыта вы будете развивать интуицию для правильного уровня обрезки, но всегда полагаться на данные проверки для подтверждения своего выбора.

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