О чем думают деревья?

Это статья из цикла про основы машинного обучения.

• Часть 1. О машинном обучении простым языком
• Часть 2. Линейная регрессия — проще некуда
• Часть 3. О чем думают деревья?

В прошлой статье мы начали рассматривать самые простые методы машинного обучения на примере линейной регрессии. Сегодня посмотрим на еще одну модель, но уже для задачи классификации.

Классификация vs регрессия

Для начала вспомним первую статью и сформулируем для себя задачу. Входные данные у нас прежние: число или вектор чисел, как и раньше обозначим его $X$. А вот выходные данные — $\widehat{y}$ — теперь изменятся. Раньше это было просто число. Для линейной регрессии вообще без ограничений как на значения, так и на диапазон. Теперь же $\widehat{y}$ сможет принимать не любое значение, а только одно из заданных заранее. Такие значения будем называть классами. Также для наших данных есть заведомо правильные ответы, их будем обозначать $y$ (без крышки).

Давайте вернемся к примеру из прошлой статьи про определение веса по росту. Если раньше мы определяли точный вес в килограммах, то теперь мы, скорее, будем в роли судей перед боксерскими поединками. То есть нам не важен точный вес, а важна категория (легкая, средняя, тяжелая и так далее).

Еще один вариант — бинарная классификация, когда класса всего два. Обычно это означает, что мы отвечает на какой-то вопрос словами «да» или «нет». Например, в случае с тем же ростом и весом мы можем попробовать ответить на вопрос «Выше/тяжелее ли этот человек, чем в среднем по городу?». Именно бинарную классификацию мы и будем рассматривать дальше.

Как классифицировать?

Итак, у нас есть входной вектор $X$ и всего два возможных варианта ответа. Давайте обозначим ответ «да» как единицу, а ответ «нет» как ноль.

Возьмем самый простой случай, когда $X$ — это одно число. Линейная регрессия нам здесь не подойдет, так как она выдает ответ из непрерывного множества (спойлер: есть способ заставить регрессию решать нашу текущую задачу, но это тема следующей статьи). Поэтому давайте пока придумывать что-то другое.

Визуализируем наши данные. Они одномерные, поэтому легко отображаются на числовой оси. Обозначим синими точками данные, для которых правильный ответ — 0, и красными для которых ответ — 1.

В таком случае все просто. Мы можем выбрать какое-то значение на прямой, и если наше входное число меньше этого значения, то ответ 0, а если больше — 1. Как нам выбрать такое число. Давайте будем перебирать все варианты, как разделить выборку. Обычно делят в середине между двумя точками. У нас, таким образом, будет 8 вариантов:

Теперь проверим, сколько правильных ответов позволяет получить каждый из вариантов. Очевидно, что в этом конкретном случае у нас есть вариант, который позволяет получить все правильные ответы:

Но так бывает не всегда. Изменим начальные условия:

В таком случае мы не можем полностью правильно разделить наши данные. Но можно минимизировать ошибку. Если разделить данные там, где это делалось в прошлый раз, мы получим 7 правильных ответов из 8. И это лучшее, чего мы можем достичь одним разделением.

Строим деревья

Но бывают случаи, когда невозможно достичь нормального качества только одним разделением. Например, такой:

Здесь при одном разделении у нас будет максимум 5 правильных ответов из 8, что не очень хорошо. Поэтому надо придумывать что-то еще.

Решение выглядит интуитивным: делить не один раз, а несколько. Например, мы можем сначала поделить вот так:

После такого деления, мы считаем, что все объекты меньше этого значения имеют класс 1. Оставшуюся часть мы делим еще раз (точки, закрашенные белым, мы определили на предыдущем шаге, и их можно не рассматривать):

В итоге получаем алгоритм, который нам нужно выполнить, чтобы классифицировать любой элемент:

Такой алгоритм и называется деревом решений. У дерева есть корень -- это то место, с которого начинается алгоритм. А точки, где он заканчивается, то есть места, где мы получаем класс (на рисунке выше это цветные цифры — метки классов) называют листьями дерева. А все промежуточные точки (прямоугольники на рисунке) называют узлами. Именно узел описывает разделение значений на две части.

Остается понять, как такое дерево строить. Итак, в самом начале узлов и листьев нет. Нам нужно сделать первое разделение данных, то есть создать узел. Снова выберем точки — кандидаты для разделения. Это будут середины отрезков между соседними точками исходных данных (как и в примере про самый простой случай):

Теперь нужно решить, какой кандидат самый подходящий. И просто посчитать количество правильных ответов тут уже не получится. Дело в том, что, если мы постараемся получить максимум правильных ответов на первом шаге (в программировании это называется жадным алгоритмом), мы можем усложнить себе задачу на следующих. То есть надо оптимизировать все решение, а не только первый шаг.

Поэтому придется действовать чуть сложнее. Мы по-прежнему будем перебирать всех кандидатов по очереди, но метрика будет другой. Итак, в первую очередь считаем, сколько элементов оказываются справа и слева от нашего разделения:

Эти значения пока отложим, они пригодятся чуть позже. Теперь нужно посчитать, насколько хорошо разделены данные слева и справа. Другими словами, насколько качественно мы разделили объекты на два класса. Для этого будем использовать критерий Джини. Он считается по формуле

$G = 1 - \left( p_{0}^{2} + p_{1}^{2} \right)$

где $p_{0}$ и $p_{1}$ — это доли классов ноль и один в нашем разделении.

Допустим, у нас слева три нуля и одна единица. Тогда

$G_{left} = 1 - \left( \left( \frac{3}{4} \right)^{2} + \ \left( \frac{1}{4} \right)^{2} \right) = 1 - 0.625 = 0.375$

Чем меньше критерий, тем лучше. Например, если слева только единицы или только нули, значение критерия будет равно нулю. Это значит, что с этой стороны мы идеально отделили один из классов.

Посчитаем критерии для всех наших кандидатов:

Нам остается посчитать только финальную метрику для каждого кандидата. Считается она как взвешенная сумма. Вспомним, что мы считали количество элементов справа и слева от суммы. Весами будут как раз эти количества, деленные на суммарное количество элементов $|S|$. У нас всего 8 элементов, то есть $|S| = 8$. Итоговая формула:

$M = \ \frac{\left| S_{left} \right|}{|S|}G_{left} + \frac{\left| S_{right} \right|}{|S|}G_{right}$

Считаем для всех наших кандидатов:

Лучшая метрика у нас для точек C и E. Делить можно по любой, разделим по C.

Теперь смотрим, что у нас получилось. Слева только класс 1. Значит, тут у нас будет лист и дальше мы ничего не делим. Справа есть разные классы. Значит тут не лист, а еще один узел. Повторяем разделение для этого узла:

После расчетов увидим, что делить нужно по E. Слева у нас будет класс 0. Справа класс 1. То есть все объекты распределены по классам. Добавляем два листа. Дерево построено.

Итоговый алгоритм (изначально дерево пустое):

1. Добавляем узел в корень
2. Делаем разделение в узле
3. Если слева все объекты одного класса, создаем лист, иначе создаем узел
4. Если справа все объекты одного класса, создаем лист, иначе создаем узел
5. Повторяем пункты 2-4 пока в дереве есть хоть один узел

Когда дерево построено, мы для каждого нового объекта просто проходим по нему от корня, пока не дойдем до листа. Класс в листе и будет классом для нашего объекта.

Больше размерностей

Мы научились строить деревья для входных данных размерности 1, то есть для единичных чисел. Например, с помощью дерева, описанного в предыдущей главе, можно попробовать определить, яблоко перед нами или груша по одному параметру. Например, по диаметру. Однако, такая классификация будет очень неточной. Один диаметр почти ничего не говорит о том, груша это или яблоко.

На всех рисунках дальше яблоки будем обозначать яблоки красным цветом, а груши — синим. По рисунку видно, что разбить данные на группы больше одного элемента невозможно.

Ситуация радикально меняется, если мы добавим вторую размерность. Теперь каждый фрукт мы будем описывать не одним параметром, а двумя: ширина (или диаметр) и высота. Добавление второго параметра позволит гораздо эффективнее отличать яблоки от груш.

Обратите внимание, по оси X ничего не изменилось. Но теперь данные очень хорошо разделены по оси Y.

Если классификацию проводил бы человек, то он смотрел бы на вытянутость (отличие высоты от ширины). Чтобы сделать нечто подобное с помощью машинного обучения можно снова использовать решающие деревья. Осталось разобраться, как построить дерево для нашего случая.

На самом деле алгоритм будет почти таким же. Мы на каждом шаге делим данные на две части. Основное отличие в том, что раньше нам не нужно было выбирать, по какому параметру делить, так как параметр был один единственный. Теперь параметров два и сначала нам нужно решить, по какому из параметров проводить разделение. После этого все сводится к выбору точки разделения, а это мы уже научились делать в предыдущей главе.

Как будут выглядеть такие разделения на графике? Раньше у нас была только одна ось, и мы просто ставили точку, левее которой все объекты попадают в одну ветку дерева, а правее — в другую. Теперь у нас осей две. И первый шаг — это выбор, по какой оси мы производим разделение. Если мы выбираем ось X, то это будет вертикальная линия, если Y — горизонтальная.

Оранжевым и зеленым цветами показаны разделения по разным признакам (осям).

На втором этапе мы выбираем, где именно такая линия будет проходить. После этого, объекты по разную сторону от линии (выше/ниже или левее/правее) попадают в разные ветки дерева.

Осталось разобраться, как же именно нам выбирать ось. На самом деле все очень просто. Мы перебираем теперь не только кандидатов на разделение по одному признаку, а по всем. И выбираем лучший из всех вариантов. А когда на втором шаге нам нужно сделать разделение по выбранной оси, мы уже знаем, где это сделать, так как посчитали это на первом шаге. Если визуализировать работу дерева на графике, получим такой результат:

Итоговый алгоритм будет выглядеть так:

1. Добавляем узел в корень
2. Находим лучшее разделение по каждому из признаков
3. Делаем разделение в узле по лучшему из признаков
4. Если слева все объекты одного класса, создаем лист, иначе создаем узел
5. Если справа все объекты одного класса, создаем лист, иначе создаем узел
6. Повторяем пункты 2-5 пока в дереве есть хоть один узел

Если посмотреть на этот алгоритм, станет понятно, что нам ничего не мешает работать с данными больших размерностей. Например, для трехмерных данных мы будет разделять их не линией, а плоскостью. Такой вариант еще можно визуализировать. А вот для четырех и более размерностей наглядной визуализации нет, так как там разделять данные будет гиперплоскость.

Переобучение и что с ним делать

Пока мы строили дерево до тех пор, пока все объекты не будут правильно классифицированы. На первый взгляд кажется, что такой вариант единственно правильный, ведь нам не нужно допускать ошибки. Однако это только на первый взгляд. Перфекционизм в машинном обучении чаще вредит, чем помогает.

Вернемся к примеру с яблоками и грушами и представим, что к нам в обучающую выборку попалось дефектное вытянутое яблоко. И дерево решений, если оставить все как есть, будет строить ветви, чтобы точно классифицировать этот объект как яблоко, хотя вокруг будут одни груши. В итоге, когда мы будем делать классификацию с помощью этого дерева, есть риск, что нормальная груша будет классифицирована как яблоко.

Что с этим делать? Нужно заставить дерево не реагировать на единичные странные примеры. Есть несколько способов это сделать:

1. Ограничить глубину дерева. Например, мы можем сделать не более трех разделений. После трех разделений крайние узлы считаются листьями.
2. Ограничить минимальное количество данных в листе. Например, если в узле четыре или менее объектов, этот узел автоматически считается листом и больше не делится
3. Ограничить само число листов. Если лимит исчерпан, новые разделения не происходят, а все крайние узлы считаются листьями.

Каждый из этих способов может помочь бороться с переобучением. Но универсального рецепта нет. Обычно применяют комбинацию из методов, а параметры подбирают экспериментально.

Для таких экспериментов (причем не только для решающих деревьев, а и для многих других моделей машинного обучения) очень полезно наличие тестовой выборки. Что это такое? Мы до начала обучения выделяем 10-20 процентов данных как тестовые. И дальше в процессе обучения их не используем. Это очень важный момент, тестовые данные ни в коем случае не должны быть видны модели в процессе обучения.

Когда обучение закончено, мы прогоняем через модель эти тестовые данные и смотрим, насколько хорошо она с ними работает. Если на тренировочных данных все очень хорошо, а на тестовых плохо, скорее всего это как раз переобучение и нужно принимать меры. Обычно стараются, чтобы процент правильных ответов на тренировочной и тестовой выборках был примерно одинаковым.