Деревья решений обычно используются для задач классификации и регрессии в машинном обучении. Короче говоря, они изучают иерархию вопросов «если/иначе», что в конечном итоге позволяет им принять решение. Эти вопросы больше похожи на вопросы, которые мы задаем в игре из 20 вопросов. Давайте представим, мы хотим различать четырех животных, таких как — медведи, ястребы, пингвины и дельфины. Ваша цель — найти ответ, задавая как можно меньше вопросов, если это возможно. Мы можем начать с вопроса, есть ли у животных перья, этот вопрос сужает возможность до двух. Если ответ «да». Мы также можем спросить, может ли животное летать или нет, чтобы отличить ястреба от пингвина. Если у животного нет перьев, возможны правильные ответы — дельфины и медведи, и необходимо задать дополнительные вопросы, чтобы получить правильное животное из обоих вариантов, например — наличие плавников и т. д.
Мы можем выразить эту серию вопросов в виде дерева решений следующим образом:
На этой диаграмме каждый узел в дереве представляет собой вопрос или конечный узел, также называемый листом, содержащим ответ. Ребра узла или листа соединяются с ответами на вопрос со следующим вопросом, который нужно задать.
В мире машинного обучения мы построили модель, позволяющую различать четыре класса животных, как упоминалось выше, с использованием трех признаков «имеет перья», «умеет летать» и «имеет плавники». Эти модели можно изучать с помощью обучения с учителем, а не вручную.
Как построить деревья решений?
Теперь мы поймем процесс построения дерева решений для набора данных 2D-классификации, показанного на рисунке 2. Набор данных содержит две формы полумесяца, где каждый класс состоит из 75 точек данных. Этот набор данных называется two_moons. Как мы упоминали ранее, изучение дерева решений означает изучение последовательности вопросов if/else, которые быстрее всего приведут нас к правильному ответу. В формате машинного обучения эти вопросы называются тестами (не путайте их с наборами тестов, которые представляют собой данные, которые мы используем для проверки, чтобы увидеть, насколько обобщаема наша модель). Данные не поступают в виде бинарных признаков «да/нет», как в приведенном выше примере с животными, а вместо этого часто представляются в виде непрерывных признаков, таких как набор 2D-данных, показанный на рисунке 2.
Когда мы строим дерево решений, алгоритм проходит через все возможные тесты и находит тот, который наиболее информативен в отношении целевой переменной. На рисунке 2 показан первый выбранный тест. Когда мы делим набор данных по вертикали при x[1]=0,0596, это дает наиболее ценные данные и лучше всего отделяет точки в классе 1 от класса 2. Верхний узел, известный как корень, представляет весь набор данных, где 75 точек принадлежат класс 0 и 75 баллов относятся к классу 1.
Набор данных делится путем проверки того, соответствует ли x[1] ‹= 0,0596, что обозначено черной линией. Если тест верен, точка присваивается левому узлу, который содержит 2 точки, принадлежащие классу 0, и 32 точки, принадлежащие классу 1. В противном случае точка присваивается правому узлу, который содержит 48 точек, принадлежащих классу 1. к классу 0 и 18 точек, принадлежащих классу 1. Эти два узла соответствуют верхней и нижней областям, показанным на рисунке 3. Несмотря на то, что первое разделение хорошо разделило два класса, нижняя область все еще содержит точки, принадлежащие классу 0, а верхняя область по-прежнему содержит точки, принадлежащие классу 1. Мы можем построить более точную модель, повторив процесс поиска наилучшего теста в обеих областях. Рисунок 4 показывает, что наиболее информативное следующее разделение для левой и правой областей основано на x[0].
Этот процесс называется рекурсивным, который дает бинарное дерево решений, в котором каждый узел состоит из теста. С другой стороны, каждый тест можно рассматривать как деление части данных, которая в настоящее время рассматривается, по одной оси. Это создает иерархический раздел алгоритма. Поскольку каждый тест касается только одного объекта, области в результирующем разделе всегда будут иметь границы, параллельные осям. Мы повторяем рекурсивное разбиение данных до тех пор, пока каждая область в разделе не будет иметь только одно целевое значение. Лист дерева решений, состоящий из точек данных, имеющих одинаковое целевое значение, называется чистым. Когда мы делаем прогноз для новой точки данных, проверяя, в какой области раздела пространства признаков находится точка, а затем прогнозируя основную цель в этой области. Область можно найти, обходя дерево от корня и двигаясь влево или вправо, в зависимости от того, выполнен ли тест или нет. Мы также можем использовать деревья решений для регрессии, используя точно такую же методологию. Чтобы сделать прогноз, мы проходим по дереву на основе тестов в каждом узле и находим лист, в который попадает новая точка данных. Результатом для этой точки данных является средняя цель точек обучения в этом листе дерева решений.