Машинное обучение - это проблема компромиссов. Классический вопрос - это чрезмерная посадка или недостаточная посадка. Чрезмерная подгонка происходит, когда модель настолько хорошо запоминает свои обучающие данные, что обучается шуму поверх сигнала. Недостаточная подгонка - это противоположное событие: модель слишком проста, чтобы найти закономерности в данных.
Излишняя подгонка приводит к более сложным деревьям решений, чем это необходимо, ошибка обучения больше не дает точной оценки того, насколько хорошо дерево будет работать с ранее невидимыми данными.
В машинном обучении и интеллектуальном анализе данных сокращение - это метод, связанный с деревьями решений. Один из вопросов, который возникает в алгоритме дерева решений, - это оптимальный размер конечного дерева. Слишком большое дерево может привести к чрезмерному подгонке обучающих данных и плохому обобщению для новых выборок. Небольшое дерево может не захватывать важную структурную информацию о пространстве выборки. Однако трудно сказать, когда алгоритм дерева должен остановиться, потому что невозможно сказать, приведет ли добавление одного дополнительного узла к значительному уменьшению ошибки. Эта проблема известна как эффект горизонта. Распространенной стратегией является рост дерева до тех пор, пока каждый узел не будет содержать небольшое количество экземпляров, а затем использовать сокращение для удаления узлов, не предоставляющих дополнительной информации. Из всех алгоритмов машинного обучения деревья решений наиболее подвержены чрезмерной подгонке, и эффективное сокращение может снизить эту вероятность.
Сокращение должно уменьшать размер дерева обучения без снижения точности прогнозов, измеряемой набором перекрестной проверки. Существует множество методов обрезки деревьев, которые различаются по показателям, используемым для оптимизации производительности. В этом блоге мы поговорим о сокращении сложности затрат, или сокращении самых слабых ссылок. Обрезка может производиться сверху вниз или снизу вверх. Отсечение сверху вниз будет проходить по узлам и обрезать поддеревья, начиная с корня, а отсечение снизу вверх начнется с узловых листьев. Сокращение количества ошибок и сокращение затрат - это два популярных алгоритма сокращения.
Давайте возьмем для примера разные дозировки лекарств по оси абсцисс и эффективность лекарств по оси ординат. На графике ниже мы видим, что когда дозировка лекарства была слишком низкой или слишком высокой, то лекарство не было эффективным. Средние дозировки были очень эффективными, а умеренно высокие - умеренно эффективными.
Когда мы подгоним дерево регрессии к обучающим данным, мы получим соответствующее дерево. Где каждый лист соответствовал средней эффективности лекарства из другого кластера. Это дерево хорошо справляется с обучающими данными, что, если мы протестируем его на тестовых данных (красные кружки)? Остатки для первого и четвертого кластеров довольно близки к прогнозируемым значениям. Так что их остатки, разница между прогнозируемыми и фактическими значениями не очень велика. Однако остатки для наблюдений третьего кластера больше, чем раньше, а остатки для наблюдений второго кластера намного больше. Эти наблюдения (второй кластер) на основе данных обучения со 100% эффективностью лекарственного средства теперь выглядят как выбросы. Это означает, что мы можем слишком подогнать дерево регрессии к обучающим данным.
Один из способов предотвратить чрезмерную подгонку дерева регрессии к обучающим данным - удалить некоторые листья и заменить разбиение листом, который является средним для большого количества наблюдений. Теперь все наблюдения между 14,5 и 29 см. В крайнем правом углу. Большие остатки говорят нам о том, что новое дерево не соответствует обучающим данным так хорошо, как раньше. Но новое поддерево намного лучше справляется с данными тестирования.
Примечание.. Если мы хотим еще больше обрезать дерево, мы могли бы удалить два последних листа и заменить разделенный лист листом, который является средним из большого количества наблюдений. И снова мы могли бы удалить последние два листа и заменить разделение листом, который представляет собой среднее значение всех наблюдений.
Тогда как нам решить, какое дерево использовать? Здесь мы решим эту проблему, используя сокращение затратной сложности.
Первым шагом в сокращении сложности затрат является вычисление суммы квадратов остатка (SSR) для каждого дерева. Начнем с оригинального дерева в натуральную величину.
SSR для наблюдений с дозировками ‹14,5 составляет (25–14,2) ² + (25–14,2) ² + (25–14,2) ² + (25–14,2) ² + (20–14,2) ² + (5–14,2) ² = 584,84.
Аналогичным образом SSR для наблюдений с дозировками ›= 29 составляет 75.
SSR для наблюдений с дозировками ›= 23,5 и‹ 29 составляет 148,8.
А SSR для наблюдений с дозировками ›= 14,5 и‹ 23,5 равно 0.
Таким образом, общая сумма квадратов остатка для всего дерева составляет 584,84 + 75 + 148,8 + 0 = 808,64.
Теперь давайте рассчитаем SSR для поддерева с одним листом меньше.
SSR для дозировок
Но SSR для дозировки от 14,5 до 29 составляет 5099,8. Таким образом, общее SSR для поддерева с 3 листьями равно = 584,84 + 75 + 5099,8 = 5759,64.
Точно так же SSR для поддерева с двумя листьями составляет 19 243,7. Наконец, SSR для поддерева с одним листом составляет 25 597,2.
Сумма квадратов остатка относительно мала для исходного полноразмерного дерева. Но каждый раз, когда мы удаляем лист, сумма квадратов остатка увеличивается.
Это произошло потому, что вся идея заключалась в том, чтобы обрезанное дерево не соответствовало обучающим данным. Итак, следующий вопрос: как мы можем сравнивать эти деревья? Удаление слабейших ссылок осуществляется путем расчета оценки дерева, который основан на сумме квадратов остатков для дерева или поддерева и штрафа за сложность дерева , который является функцией количества листьев в дереве или поддереве. Штраф за сложность дерева компенсирует разницу в количестве листьев.
Оценка дерева = сумма квадратов остатка + αT
α (альфа) - параметр настройки, который мы находим с помощью перекрестной проверки.
А пока давайте возьмем α = 10 000 и посчитаем оценку дерева для каждого дерева.
Оценка дерева для оригинального полноразмерного дерева составляет 40 808,64. [Оценка дерева = 808,64 + 10,000 * 4].
Теперь подсчитайте оценку дерева для поддерева с одним листом меньше. SSR для этого поддерева составляет 5 759,64, а лист равен 3. Таким образом, общая оценка дерева = 35 759,64.
Оценка дерева за поддерево с 2 листьями составляет 39 243,7. Наконец. оценка дерева для поддерева с одним листом составляет 35597,2.
Поскольку α = 10 000, штраф за сложность дерева для дерева с 1 листом составлял 10 000, а штраф за сложность дерева для дерева с 2 листьями составлял 20 000. И так далее, таким образом, чем больше листьев, тем больше штраф. После того, как мы подсчитали количество деревьев для всех деревьев. Мы выбираем второе поддерево, потому что у него самый низкий балл по дереву.
Но если мы установим α = 22000 и вычислим оценки дерева, то мы будем использовать поддерево только с одним листом, потому что у него самый низкий рейтинг дерева. Таким образом, значение α имеет значение при выборе поддерева.
Теперь посмотрим, как найти лучшее значение для α. Во-первых, используя все данные, создайте полноразмерное дерево регрессии (это полноразмерное дерево соответствует всем данным, а не только данным обучения). Еще одна важная вещь заключается в том, что это полноразмерное дерево имеет самый низкий балл дерева при α = 0. Это потому, что, когда α = 0, штраф за сложность дерева становится равным 0, а оценка дерева является просто суммой квадратных остатков.
Итак, давайте положим здесь α = 0, чтобы напомнить нам, что это дерево имеет самый низкий балл, когда α = 0. Теперь мы будем увеличивать α до тех пор, пока обрезка листьев не даст нам более низкий балл дерева. В этом случае, когда α = 10 000, мы получим меньшую оценку дерева, если удалим последние 2 листа.
Теперь мы снова увеличиваем α до тех пор, пока обрезка листьев не даст нам более низкий балл дерева. В этом случае, когда α = 15000, мы получим меньшую оценку дерева, если удалим последние 2 листа. А когда α = 22000, мы получим меньшую оценку дерева, если удалим последние 2 листа.
В конце концов, разные значения α дают нам последовательность деревьев, от полноразмерных до простого листа.
Теперь вернитесь к полному набору данных и создайте полноразмерное дерево регрессии (это полноразмерное дерево отличается от предыдущего, потому что оно подходит для всех данных, а не только для данных обучения). Разделите данные на наборы данных для обучения и тестирования. Просто используя обучающие данные, используйте найденные ранее значения α, чтобы построить полное дерево и последовательность поддеревьев, которые минимизируют оценку дерева.
Теперь вычислите сумму квадратов остатка для каждого нового дерева, используя только данные тестирования. В этом случае дерево с α = 10 000 имело наименьшую сумму квадратов остатка для данных тестирования.
Теперь вернитесь и создайте новые данные обучения и новые данные тестирования. Постройте новую последовательность деревьев, от полноразмерных до листа. используя значения α, которые мы нашли ранее. Затем мы вычисляем сумму квадратов остатков, используя новые данные тестирования. На этот раз α = 0 имело наименьшую сумму квадратов остатков. Просто продолжайте повторять, пока мы не проведем 10-кратную перекрестную проверку. И значение α такое, в среднем. дают нам наименьшую сумму квадратов остатка с данными тестирования. - окончательное значение для α.
В этом случае оптимальные деревья, построенные с α = 10 000, имели в среднем наименьшую сумму квадратных остатков. Таким образом, окончательное значение - α = 10,000. Наконец, мы возвращаемся к исходным деревьям и поддеревьям, созданным из полных данных, и выбираем дерево, которое соответствует выбранному нами значению α (α = 10 000). Это поддерево будет последним обрезанным деревом.
использованная литература
