Сокращение - это метод сжатия данных в алгоритмах машинного обучения и поиска, который уменьшает размер деревьев решений за счет удаления некритических и избыточных участков дерева для классификации экземпляров. Обрезка снижает сложность окончательного классификатора и, следовательно, повышает точность прогнозов за счет уменьшения переобучения .
Один из вопросов, который возникает в алгоритме дерева решений, - это оптимальный размер конечного дерева. Слишком большое дерево рискует переобучить обучающие данные и плохо обобщить для новых выборок. Небольшое дерево может не захватывать важную структурную информацию о пространстве выборки. Однако трудно сказать, когда алгоритм дерева должен остановиться, потому что невозможно сказать, приведет ли добавление одного дополнительного узла к значительному уменьшению ошибки. Эта проблема известна как эффект горизонта . Распространенной стратегией является рост дерева до тех пор, пока каждый узел не будет содержать небольшое количество экземпляров, а затем использовать сокращение для удаления узлов, не предоставляющих дополнительной информации. [1]
Сокращение должно уменьшать размер дерева обучения без снижения точности прогнозов, измеренной с помощью набора перекрестной проверки . Существует множество методов обрезки деревьев, которые различаются по показателям, используемым для оптимизации производительности.
Методы [ править ]
Процессы обрезки можно разделить на два типа (до и после обрезки).
Процедуры предварительной обрезки предотвращают полную индукцию обучающего набора, заменяя критерий stop () в алгоритме индукции (например, максимальная глубина дерева или информационный прирост (Attr)> minGain). Методы предварительной обрезки считаются более эффективными, потому что они не вызывают весь набор, а скорее деревья остаются небольшими с самого начала. У методов предварительной обрезки есть общая проблема - эффект горизонта. Это следует понимать как нежелательное преждевременное прекращение индукции по критерию stop ().
Пост-обрезка (или просто обрезка) - наиболее распространенный способ упрощения деревьев. Здесь узлы и поддеревья заменены листьями для повышения сложности. Обрезка может не только значительно уменьшить размер, но и повысить точность классификации невидимых объектов. Может случиться так, что точность присвоения тестового набора ухудшится, но точность классификационных свойств дерева в целом возрастет.
Процедуры различаются в зависимости от их подхода в дереве (сверху вниз или снизу вверх).
Подрезка снизу вверх [ править ]
Эти процедуры начинаются с последнего узла в дереве (самой нижней точки). Следуя рекурсивно вверх, они определяют релевантность каждого отдельного узла. Если релевантность для классификации не указана, узел удаляется или заменяется листом. Преимущество этого метода в том, что никакие соответствующие поддеревья не могут быть потеряны. Эти методы включают сокращение с уменьшением количества ошибок (REP), сокращение сложности с минимальной стоимостью (MCCP) или сокращение с минимальной ошибкой (MEP).
Обрезка сверху вниз [ править ]
В отличие от метода «снизу вверх», этот метод начинается с корня дерева. Следуя приведенной ниже структуре, выполняется проверка релевантности, которая определяет, является ли узел релевантным для классификации всех n элементов или нет. При обрезке дерева на внутреннем узле может случиться так, что все поддерево (независимо от его релевантности) будет отброшено. Одним из таких представителей является пессимистическая обрезка ошибок (PEP), которая дает неплохие результаты с невидимыми элементами.
Алгоритмы сокращения [ править ]
Уменьшение количества ошибок при сокращении [ править ]
Одна из простейших форм обрезки - это сокращение количества ошибок. Начиная с листьев, каждый узел заменяется самым популярным классом. Если точность прогноза не изменяется, изменение сохраняется. Хотя это несколько наивно, но уменьшение количества ошибок имеет преимущество в простоте и скорости .
Сокращение сложности затрат [ править ]
Обрезка сложности по стоимости генерирует серию деревьев, где - исходное дерево, а только корень. На шаге дерево создается путем удаления поддерева из дерева и его замены листовым узлом со значением, выбранным в алгоритме построения дерева. Удаляемое поддерево выбирается следующим образом:
- Определите частоту ошибок дерева по набору данных как .
- Поддерево, которое минимизируется , выбирается для удаления.
Функция определяет дерево, полученное путем отсечения поддеревьев от дерева . После создания серии деревьев выбирается лучшее дерево по обобщенной точности, измеренной с помощью обучающего набора или перекрестной проверки.
См. Также [ править ]
Ссылки [ править ]
- Жемчуг, Иудея (1984). Эвристика . Эддисон-Уэсли.
- Мансур, Ю. (1997). «Пессимистическая обрезка дерева решений на основе размера дерева» . Proc. 14-я Международная конференция по машинному обучению . С. 195–201.
- Бреслоу, штат Луизиана; Ага, DW (1997). «Упрощение деревьев решений: обзор». Обзор инженерии знаний . 12 (1): 1–47. DOI : 10.1017 / S0269888997000015 .
- Куинлан, младший (1986). «Индукция деревьев решений» . Машинное обучение . Kluwer Academic Publishers. 1 : 81–106. DOI : 10.1007 / BF00116251 .
- ^ Хасти, Тревор; Тибширани, Роберт; Фридман, Джером (2001). Элементы статистического обучения . Springer. С. 269–272. ISBN 0-387-95284-5.
Дальнейшее чтение [ править ]
- Обрезка дерева решений на основе MDL
- Обрезка дерева решений с использованием нейронных сетей с обратным распространением
Внешние ссылки [ править ]
- Быстрый алгоритм обрезки дерева решений снизу вверх
- Введение в обрезку дерева решений
