[ЗАСТАВКА] В этом видео мы поговорим о способах борьбы с переобучением решающих деревьев, а именно про критерии останова и про стрижку деревьев. Критерий останова показывает, нужно ли останавливать процесс построения дерева. Например, когда мы разбили дерево до какой-то степени и находимся в определенной вершине, мы хотим понять, нужно ли ее разбивать дальше или же стоит оделить ее листом? Критерий останова должен отвечать на этот вопрос. Как мы с вами уже обсуждали, худший случай решающего дерева — это дерево, у которого каждый лист соответствует одному объекту обучающей выборки. В этом случае дерево будет максимально переобученным, оно не будет обобщать информацию, полученную из обучающей выборки. Критерий останова, грамотно подобранный критерий останова — это способ борьбы с таким переобучением. Самый простой критерий останова проверяет, все ли объекты, которые находятся в данной вершине, относятся к одному классу. Понятно, что это работает только для классификации. Это простой и понятный критерий останова, но при этом он будет выполнятся в нетривиальных случаях только на простых выборках. Если выборка и зависимости в ней сложные, то, скорее всего, этот критерий сработает только тогда, когда в каждом листе останется по одному объекту. Гораздо более устойчивый и полезный критерий проверяет, сколько объектов оказалось в данной вершине. Если их больше, чем n, то разбиение продолжается, а если меньше или равно, чем n, то процесс построения останавливается в этой вершине, и n — это некоторый параметр, который нужно подбирать. Если n = 1, мы получаем худший случай с деревом, где в каждом листе по одному объекту. Выбирать n нужно так, чтобы по n объектам, которые попали в вершину, можно было устойчиво построить прогноз, можно было надежно оценить, какой прогноз выдавать на этих объектах. Существует рекомендация, что n нужно брать равным 5, по идее, при 5 точках, если у нас 5 объектов попали в вершину, можно уже более или менее надежно оценить, какой ответ на них нужно выдавать. Еще один критерий, гораздо более грубый — это ограничение на глубину дерева. Если мы видим, что эта вершина находится на 5-м уровне дерева и максимальная глубина равна 5, мы останавливаем построение независимо ни от чего — ни от распределения классов в этой вершине, ни от числа объектов в ней — просто останавливаем построение. Критерий довольно грубый, но при этом он хорошо себя зарекомендовал при построении композиций, то есть когда мы объединяем много решающих деревьев в один сложный алгоритм. Мы об этом будем говорить позже в этом модуле. Существует и другой подход к борьбе с переобучением деревьев, а именно стрижка. Это заключается в следующем: мы строим решающее дерево максимальной сложности, максимальной глубины, никак не ограничивая его, то есть строим его до тех пор, пока в каждой конечной вершине не окажется по одному объекту обучающей выборки. После этого мы начинаем удалять, стричь листья в этом дереве по некоторому критерию. Например, можно стричь их до тех пор, пока улучшается качество на некоторой отложенной выборке. Существует мнение, и это подкреплено многими экспериментами, что стрижка работает гораздо лучше, чем простые критерии, о которых мы говорили раньше. В то же время стрижка — это довольно трудоемкая процедура. Например, она может требовать вычисления качества дерева на некоторой валидационной выборке на каждом шаге, что может быть очень сложно. На самом деле, деревья сами по себе практически не используются на сегодняшний день, они нужны лишь для построения композиции, для объединения большого числа деревьев в один алгоритм. И в случае с композициями такие сложные подходы к борьбе с переобучением уже не нужны, оказывается достаточно простых критериев останова вроде ограничения на глубину или число объектов в каждом листе. Итак, мы с вами обсудили, что деревья сами по себе получаются переобученные и зачастую нужно бороться с их переобучением. К этому есть два подхода. Первый — использование простых критериев останова, таких как: ограничение на глубину дерева или ограничение на число объектов в каждом листе дерева. Также есть подход, который называется стрижкой деревьев, который дает более высокое качество, но при этом гораздо более сложный в применении. В следующем видео мы поговорим о том, как использовать категориальные признаки в решающих деревьях.