[ЗАСТАВКА] В этом видео мы обсудим, как использовать категориальные признаки в решающих деревьях. Напомню, что до этого мы обсуждали вот такие условия, которые используются в каждой вершине решающего дерева. В них берется значение j-го признака и сравнивается с порогом t. Если значение меньше или равно этого порога, то объект отправляется в левое поддерево, если больше этого порога, то в правое поддерево. Понятно, что это работает только для вещественных и бинарных признаков, поскольку их мы можем сравнивать с некоторыми числами. Для категориальных признаков это не так, поскольку они принимают значения из некоторого неупорядоченного множества, значения, которые мы не можем сравнивать между собой. Рассмотрим подход, который позволяет включить категориальные признаки в деревья. Он состоит в том, чтобы строить не бинарные, а n-арные деревья, у которых из каждой вершины может выходить вплоть до n ребер. Итак, допустим, мы находимся в некоторой вершине m и хотим разбить ее по некоторому признаку. Для вещественных и бинарных признаков все еще будем рассматривать простые условия, которые сравнивают значения j-го признака с некоторым порогом t. Что же делать в случае с категориальными признаками? Итак, допустим, есть j-й признак, который категориальный и принимает n возможных значений, которые будем обозначать, как c1, …, cn, в этом случае мы будем разбивать эту вершину не на две вершины, как было раньше, а на n вершин, каждая будет соответствовать своему значению категориального признака. Соответственно, в i-ю вершину будут отправляться те объекты, на которых значения j-го признака равно ci. Итак, допустим, мы построили такое разбиение и разбили вершину m на n частей, в i-ю часть отправляется множество объектов xi — это те объекты, на которых категориальный признак принимает значение ci. Как оценить ошибку такого разбиения? В случае с вещественными или бинарными признаками, мы вычисляли взвешенную сумму критериев информативности. В этом случае поступим так же, только слагаемых будет не 2, а n штук. Каждое слагаемое устроено аналогично. Мы вычисляем долю объектов из вершины m, которые идут в i-е поддерево и умножаем на значение критерия информативности для подвыборки xi — той, которая отправилась в i-е поддерево, в i-ю дочернюю вершину. И находим такой категориальный признак, для которого эта сумма оказывается минимальной, Итак, мы рассматриваем все вещественные, бинарные и категориальные признаки, которые есть в выборке. Для категориальных мы вычисляем значение критерия ошибки так, как только что обсудили, для вещественных и бинарных так, как обсуждали в прошлых видео. И выбираем тот признак и тот порог, при которых значения критерия ошибки получаются минимальным, и именно по этому признаку и порогу строим разбиение данной вершины. Заметим, что в случае с категориальными признаками мы генерируем больше дочерних вершин, скорей всего в них будет достигаться более высокое качество и будет получаться более низкое значение критерия информативности. Поэтому, скорей всего, при таком подходе предпочтения почти всегда будут отдаваться разбиению по категориальным признакам с большим числом возможных значений. В результате получится очень много листьев в дереве, что, почти гарантировано, может привести к переобучению. Однако это не всегда так. Если у нас выборки очень большие и даже при разбиении по категориальному признаку у нас будет оказываться много объектов в каждом поддереве, то такой подход будет работать очень неплохо, поскольку он будет восстанавливать сложные зависимости и при этом не переобучаться, при использовании должного критерия останова. Есть и другой подход, который не требует строить такие сложные деревья и продолжает работать с бинарными деревьями. Итак, допустим, j-й признак категориальный и нам нужно как-то разбить по нему данную вершину. Построим некоторое разбиение множества значений этого признака C на два подмножества, которые не пересекаются: C1 и C2. В объединении они должны давать все множество значений j-го признака C. После того как такое разбиение построено, а как именно мы его строим, мы обсудим чуть позже, так вот, если оно построено, то условие в данной вершине будет выглядеть просто — оно проверяет, в какое из этих двух подмножеств попадает значение j-го признака на данном объекте. Если оно попадает в подмножество C1 — отправляем объект влево, если в C2 — отправляем его вправо, дерево остается бинарным. Итак, главный вопрос: как же именно разбить C на два подмножества? Всего возможных разбиений — 2 в степени n. Это очень много, мы не можем себе позволить устроить такой перебор, но оказывается это и не нужно. Есть одна хитрость, которая позволяет избежать полного перебора. В чем она заключается? Для начала отсортируем все возможные значения категориального признака, а их n штук, по некоторому принципу. Будем обозначать минимальное значение как C с индексом (1), второе по минимальности, как C с индексом (2), и так далее до C индексом (n) — это будет максимальное значение. После этого заменим i-е, по порядку значение категориального признака, на число i, то есть перейдем от категориального признака к вещественному и дальше будем работать именно с этим вещественным признаком. Строить для него разбиение, просто выбирая порог. Понятно, что это гораздо быстрее. Порогов столько, сколько различных значений, в нашем случае n штук. Поговорим о том, как нужно сортировать значения категориального признака. Это делается по вот такому очень сложному принципу. Давайте разберемся, что здесь написано. Итак, в числители дроби записана сумма по всем объектам из подвыборки xm — это объекты, которые попали в данную вершину. Для каждого объекта мы вычисляем индикаторы, которые будут равны 1, если j-й признак, тот который нас интересует, на данном объекте принимает значение c какое-то конкретное, и при этом сам объект относится к первому классу. Мы говорим о задаче бинарной классификации. В знаменателе записано число объектов подвыборки xn, у которых значения категориального признака равняется c. По сути, смысл этой дроби в следующем: она показывает, какая доля объектов, для которых значения категориального признака равно c, относится к первому классу. Как много объектов первого класса среди тех, у которых значение категориального признака равно c. Дальше мы сортируем по значению этой дроби все значения категориального признака. Следственно, чем меньше объектов для данного значения относится к первому классу, тем левее данное значение будет в этой цепочке, тем меньше будет данное значение в нашем порядке. Для регрессии все вычисляется аналогично. Только на этот раз мы вычисляем не долю объектов положительного класса с данным значением категориального признака, а средний ответ по всем объектам, у которых значение категориального признака равно c. И сортируем по этому среднему значению. При этом, чем меньше среднее значение при данном значении категориального признака, тем левее будет оно в этой цепочке. Главная особенность этого подхода состоит в том, что если бы мы перебирали все возможные разбиения множества C на два подмножества и искали оптимальное, с точки зрения, например, критерия Джини, то при таком подходе мы найдем то же самое разбиение. То есть такой подход позволяет перебирать всего n возможных разбиений вместо 2 в степени n, но при этом среди этих n будет самое оптимальное. Таким образом, благодаря этому трюку мы можем сократить перебор с экспоненциального до линейного. При этом это условие выполнено для критерия среднеквадратичной ошибки, для критерия Джини и для энтропийного критерия. Итак, мы обсудили два подхода к использованию категориальных признаков в решающих деревьях. Первый основан на построении n-арных решающих деревьев, в которых бы разбиваем вершину на столько поддеревьев, сколько значений у категориального признака. Второй подход работает с бинарными деревьями, там мы разбиваем множество значений категориального признака на два подмножества и отправляем объект влево или вправо, в зависимости от того, в какое из подмножеств выпадает значение категориального признака на этом объекте. На этом мы заканчиваем урок про решающие деревья, а дальше будем говорить о том, как строить композиции решающих деревьев, как объединить большое количество решающих деревьев в один сильный алгоритм.