Обрезка — это метод сжатия данных в алгоритмах машинного обучения и поиска , который уменьшает размер деревьев решений путем удаления некритических и избыточных для классификации экземпляров разделов дерева. Обрезка уменьшает сложность конечного классификатора и, следовательно, повышает точность прогнозирования за счет снижения переобучения .
Один из вопросов, возникающих в алгоритме дерева решений, — оптимальный размер конечного дерева. Слишком большое дерево рискует переобучить обучающие данные и плохо обобщить новые образцы. Маленькое дерево может не захватывать важную структурную информацию о пространстве образцов. Однако трудно сказать, когда алгоритм дерева должен остановиться, поскольку невозможно сказать, значительно ли уменьшит ошибку добавление одного дополнительного узла. Эта проблема известна как эффект горизонта . Распространенная стратегия заключается в том, чтобы наращивать дерево до тех пор, пока каждый узел не будет содержать небольшое количество экземпляров, а затем использовать обрезку для удаления узлов, которые не предоставляют дополнительной информации. [1]
Обрезка должна уменьшить размер обучающего дерева без снижения точности прогнозирования, измеряемой набором перекрестной проверки . Существует много методов обрезки деревьев, которые различаются по измерению, используемому для оптимизации производительности.
Процессы обрезки можно разделить на два типа (предварительная и последующая обрезка).
Процедуры предварительной обрезки предотвращают полную индукцию обучающего набора, заменяя критерий остановки () в алгоритме индукции (например, макс. глубина дерева или прирост информации (Attr) > minGain). Методы предварительной обрезки считаются более эффективными, поскольку они не индуцируют весь набор, а деревья остаются небольшими с самого начала. Методы предварительной обрезки имеют общую проблему — эффект горизонта. Это следует понимать как нежелательное преждевременное прекращение индукции критерием остановки ().
Пост-обрезка (или просто обрезка) — наиболее распространенный способ упрощения деревьев. Здесь узлы и поддеревья заменяются листьями для уменьшения сложности. Обрезка может не только значительно уменьшить размер, но и повысить точность классификации невидимых объектов. Может случиться так, что точность назначения на наборе поездов ухудшится, но точность свойств классификации дерева в целом увеличится.
Процедуры различаются в зависимости от подхода к дереву (сверху вниз или снизу вверх).
Эти процедуры начинаются с последнего узла в дереве (самая нижняя точка). Следуя рекурсивно вверх, они определяют релевантность каждого отдельного узла. Если релевантность для классификации не указана, узел удаляется или заменяется листом. Преимущество в том, что при использовании этого метода не могут быть потеряны никакие релевантные поддеревья. К этим методам относятся Reduced Error Pruning (REP), Minimum Cost Complexity Pruning (MCCP) или Minimum Error Pruning (MEP).
В отличие от метода снизу вверх, этот метод начинается с корня дерева. Следуя приведенной ниже структуре, выполняется проверка релевантности, которая решает, является ли узел релевантным для классификации всех n элементов или нет. При обрезке дерева во внутреннем узле может случиться так, что целое поддерево (независимо от его релевантности) будет отброшено. Одним из таких представителей является пессимистическая обрезка ошибок (PEP), которая дает довольно хорошие результаты с невидимыми элементами.
Одной из самых простых форм обрезки является обрезка с уменьшенной ошибкой. Начиная с листьев, каждый узел заменяется своим самым популярным классом. Если точность прогнозирования не затронута, то изменение сохраняется. Несмотря на некоторую наивность, обрезка с уменьшенной ошибкой имеет преимущество простоты и скорости .
Сложность сокращения стоимости генерирует ряд деревьев , где — это начальное дерево, а — это только корень. На шаге дерево создается путем удаления поддерева из дерева и замены его листовым узлом со значением, выбранным как в алгоритме построения дерева. Удаляемое поддерево выбирается следующим образом:
Функция определяет дерево, полученное путем обрезки поддеревьев из дерева . После создания ряда деревьев выбирается лучшее дерево по обобщенной точности, измеренной с помощью обучающего набора или перекрестной проверки.
Обрезка может быть применена в схеме сжатия алгоритма обучения для удаления избыточных деталей без ущерба для производительности модели. В нейронных сетях обрезка удаляет целые нейроны или слои нейронов.
