Обрезка дерева решений

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

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

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

Техники

Процессы обрезки можно разделить на два типа (до и после обрезки).

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

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

Процедуры различаются в зависимости от их расположения в дереве (сверху вниз или снизу вверх).

Обрезка снизу вверх

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

Обрезка сверху вниз

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

Алгоритмы обрезки

Уменьшение количества ошибок

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

Снижение сложности затрат

Сокращение сложности затрат создает серию деревьев ⁠ $T_{0}\dots T_{m}$ ⁠ где ⁠ $T_{0}$ ⁠ — исходное дерево и ⁠ $T_{m}$ ⁠ — это только корень. На шаге ⁠ $i$ ⁠ дерево создается путем удаления поддерева из дерева ⁠ $i-1$ ⁠ и заменив его листовым узлом со значением, выбранным как в алгоритме построения дерева. Поддерево, которое удаляется, выбирается следующим образом:

Определите частоту ошибок дерева ⁠ $T$ ⁠ над набором данных ⁠ $S$ ⁠ как ⁠ $\operatorname {err} (T,S)$ ⁠ .
Поддерево $t$ что сводит к минимуму ${\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}$ выбран для удаления.

Функция ⁠ $\operatorname {prune} (T,t)$ ⁠ определяет дерево, полученное обрезкой поддеревьев ⁠ $t$ ⁠ с дерева ⁠ $T$ ⁠ . После создания серии деревьев лучшее дерево выбирается на основе обобщенной точности, измеренной с помощью обучающего набора или перекрестной проверки.

Примеры

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

См. также

Ссылки

Перл, Иудея (1984). Эвристика: стратегии интеллектуального поиска для решения компьютерных задач . Аддисон-Уэсли. ISBN 978-0-201-05594-8 .
Мансур, Ю. (1997). «Обрезка дерева пессимистических решений в зависимости от размера дерева» . Учеб. 14-я Международная конференция по машинному обучению . стр. 195–201.
Бреслоу, Луизиана; Ага, Д.В. (1997). «Упрощение деревьев решений: опрос». Обзор инженерии знаний . 12 (1): 1–47. дои : 10.1017/S0269888997000015 . S2CID 18782652 .
Куинлан, младший (1986). «Индукция деревьев решений» . Машинное обучение . 1 . Клювер: 81–106. дои : 10.1007/BF00116251 .

^ Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2001). Элементы статистического обучения . Спрингер. стр. 269–272. ISBN 0-387-95284-5 .

Дальнейшее чтение

Внешние ссылки

[tib-1] Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2001). Элементы статистического обучения . Спрингер. стр. 269–272. ISBN 0-387-95284-5 .

[1]