[БЕЗ_ЗВУКА] Эта лекция будет посвящена важному классу методов машинного обучения, которые называются решающими деревьями. Это методы предназначены исходно для решения задач классификации, а также есть их специальные варианты, приспособленные для решения задач регрессии, хотя это некая экзотика. Но исходно решающие деревья возникли как попытка формализовать тот способ мышления, который используют люди при принятии решений. И например, это хорошо иллюстрируется логикой работы врача, когда он говорит с пациентом и задает один за другим уточняющие вопросы, и буквально за 4–5 вопросов он, имея ответы пациента, либо ставит диагноз, либо дает ему какие-то советы. Но если вообразить себе всю ту информацию, которую использует врач при таких опросах, то это, конечно, не 3–4 пункта, это огромное такое разветвленное дерево, и каждый ответ пациента отправляет врача в очередную веточку этого дерева. И таким образом, мы имеем, рассматривая диалог врача с пациентом, только один путь от корня дерева к листовой вершине. И вот эта вот аналогия всей информации, которой пользуется врач, вот как она у него сидит в голове, и тем, как можно было бы автоматически принимать решения, вот она и приводит к вот этой конструкции решающих деревьев. Итак, напомню, что мы в общем случае занимаемся задачами обучения с учителем. У нас есть обучающая выборка, объекты, заданные n признаками, и каждому объекту соответствует какой-то правильный ответ. И наша задача — построить алгоритм классификации, который был бы способен классифицировать новые объекты. Но при этом мы этот алгоритм классификации будем строить в виде дерева, то есть в виде какой-то вот последовательности принимаемых решений. Давайте введем более строгие определения. Давайте начнем с определения бинарного решающего дерева. Ну, во-первых, бинарное дерево — это ациклический граф, в котором есть два типа вершин: либо вершина соединена с двумя дочерними вершинами, либо она не соединена ни с одной вершиной, и тогда она называется листовой вершиной. То есть вершины двух типов: внутренние вершины и листовые (или терминальные). Так вот в бинарном решающем дереве определенная дополнительная информация связана с каждой внутренней вершиной и с каждой листовой. Во внутренней вершине у нас располагается некоторый предикат, мы его будем обозначать βV, где V — это внутренняя вершина. Предикат способен, взяв объект, сказать, дальше мы его отправим в левую ветвь или в правую ветвь дерева. В каждой листовой вершине мы будем записывать имя или метку одного из классов, то есть элемент множества Y. Вот предикаты, которые будут находиться во внутренних вершинах дерева, мы будем брать из какого-то множества бинарных предикатов. В простейшем случае, если все признаки бинарны — это просто исходные признаки. Ну, например, если признаки вещественные, то мы будем предикаты строить в виде такого вот бинарного условия: значение признака больше или равно, чем некое пороговое значение θ. И, собственно, принятие решений бинарным решающим деревом выглядит в виде простого алгоритма. Мы имеем наш объект x и имеем дерево, и начинаем пропускать этот объект через наше дерево, начиная с корня. И в каждой внутренней вершине мы проверяем значение предиката на данном объекте. Если это значение равно 1, то объект переходит в правую дочернюю вершину, а в противном случае он переходит в левую дочернюю вершину. И так происходит до тех пор, пока объект не упрется в какую-то листовую вершину, в которой сидит метка класса, и тогда решающее дерево относит этот объект к этому классу. Вот так вот просто выглядит алгоритм принятия решения. И он копирует ту самую логику врача, который, разговаривая с пациентом, задает ему те самые вопросы, которые записаны во внутренних вершинах бинарного решающего дерева. Давайте рассмотрим пример. Это та самая задача Фишера о классификации цветков ириса на 3 класса. Вот мы взяли те самые два признака, в пространстве которых эта задача просто на взгляд очень легко решается, 3 класса очень хорошо разделимы друг от друга. Ну и можно несложно нарисовать просто даже вручную, глядя на эту картинку, бинарное решающее дерево. Сначала мы отсекаем тот класс, который лежит в нижней области, и получаем первую классификацию по вот этому условию: длина лепестка меньше, чем 2,5. Вот, дальше мы отсекаем правую часть, множество вот этих зеленых точек надежно отделяется. И все, что мы в конце имеем — это вот отделить желтые точки от нескольких зеленых, которые расположены выше. То есть вот 3 шага буквально понадобилось для того, чтобы в виде решающего дерева представить алгоритм классификации вот этой выборки данных. Ну и даже видно, что мы допустили только 3 ошибки при этом. Замечу, что существует и альтернативный способ представления решающего дерева в виде списка правил. Поскольку дерево нам разделило вот это вот пространство двух признаков на 4 куска, мы могли бы отдельно записать условия, которые ограничивают эти 4 куска, и проверять их по отдельности. И если каждое из этих условий проверить, то одно и только одно из них будет выполнено. Это и происходит из-за того, что решающее дерево делит все пространство на непересекающиеся области. Вот такие вот правила они называются логическими закономерностями, и часто они характеризуются тем, что каждое такое правило выделяет какую-то область в пространстве объектов, в которой находятся объекты либо только одного какого-то класса, либо преимущественно объекты одного класса, вот как в данном случае получилось с красными точками — одним из видов ириса, который на первом же шаге надежно отделился. То есть это еще один способ представлять решающее дерево, мы всегда можем его представить в виде такого вот покрывающего набора конъюнкций. Да, почему это конъюнкция? Потому что когда объект спускается от корня дерева к листу, все внутренние вершины, которые он прошел, можно взять предикаты, находящиеся в этих внутренних вершинах, и если из них образовать конъюнкцию, то это и будет то самое правило, логическая закономерность, которая доводит этот объект до данной листовой вершины. Это уже готовое правило классификации. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА]