Обрезка дерева решений - Decision tree pruning

До и после обрезки

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

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

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

Методы

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

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

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

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

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

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

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

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

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

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

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

Стоимость усложнения обрезки

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

1. Определите частоту ошибок дерева ${displaystyle T}$ по набору данных ${displaystyle S}$ в качестве ${displaystyle operatorname {err} (T,S)}$.
2. Поддерево, которое минимизирует ${displaystyle {frac {operatorname {err} (operatorname {prune} (T,t),S)-operatorname {err} (T,S)}{leftvert operatorname {leaves} (T)ightvert -leftvert operatorname {leaves} (operatorname {prune} (T,t))ightvert }}}$ выбрано для удаления.

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

Смотрите также

• Альфа-бета обрезка
• Искусственная нейронная сеть
• Эвристика с нулевым ходом

Рекомендации

• Жемчужина Иудеи, Эвристика, Эддисон-Уэсли, 1984
• Пессимистическая обрезка дерева решений на основе размера дерева^[2]
• Л. А. Бреслоу и Д. В. Аха, Упрощение деревьев принятия решений: обзор, Обзор инженерии знаний, том 12 (1), 1997 г., стр. 1–47.
• Дж. Р. Куинлан, Индукция деревьев решений, Машинное обучение 1, Kluwer Academic Publishers, 1986, стр. 81–106.

1. Тревор Хасти, Роберт Тибширани и Джером Фридман. Элементы статистического обучения. Springer: 2001, стр. 269-272.
2. Мансур, Ю. (1997), «Пессимистическая обрезка дерева решений на основе размера дерева», Proc. 14-я Международная конференция по машинному обучению: 195–201

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

• Обрезка дерева решений на основе MDL
• Обрезка дерева решений с использованием нейронных сетей с обратным распространением

внешняя ссылка

• Быстрый алгоритм обрезки дерева решений снизу вверх
• Введение в обрезку дерева решений