Деревья решений

Основы деревьев решений

Здравствуйте и вновь добро пожаловать на занятия по теме «Обработка данных: машинное обучение с учителем на языке Python».

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

Воснове своей дерево решений можно рассматривать как ряд вложенных условныхоператоров. Рассмотрим для примера вновь классификатор спама. Мы можем указать:если документ содержит слово «деньги», тогда если документ содержит слово«бесплатно», классифицировать его как спам, в противном случае – спамом несчитать.

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

Ключевымпризнаком деревьев решений является то, что при проверке условияпросматривается лишь один атрибут или одна единица входных данных в каждыймомент времени. Один атрибут соответствует одному столбцу матрицы X. Они тоже называются входными признаками, ноприменительно к деревьям решений их иногда ещё называют атрибутами. Такимобразом, например, если для принятия решения используется рост человека, тоусловие будет выглядеть примерно так: «если рост меньше 5, перейти к левомуузлу, иначе – к правому».

Очём это говорит с геометрической точки зрения? Пусть по оси x откладываетсярост, а по оси y– вес. Тогда если мы проведём разделительную прямую x = 5, то всё, что слева от неё, ведёт к одномурешению, а всё, что справа, – к другому. Таким образом, в то время как линейныеклассификаторы могут создавать разделительные линии, проходящие под любымиуглами к осям координат, деревья решений разделяют данные только прямыми,перпендикулярными к осям координат. Хотя это вовсе не означает, что мыограничены принципом «всё, что по одну сторону, – класс 1, всё, что по другую –класс 2». Поскольку мы работаем с деревьями, то можем проводить разбиения накаждом этапе, так что конечное решение, полученное при помощи дерева решения,может быть очень и очень нелинейным.

Другойаспект деревьев решений заключается в том, что поскольку мы пользуемсядеревьями, то по существу перед нами стоит задача рекурсии. Узел дерева имеетдочерние узлы, и, базируясь на тот или ином критерии, мы выбираем, к какому из дочернихузлов перейти. Дочерний же узел имеет свои дочерние узлы, и мы повторяемоперацию, пока не достигнем конечного узла-листа, в результате чего и будетсделан прогноз.

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

Допустиму нас есть объект TreeNode, содержащийпеременные <условие>, <левый_узел>, <правый_узел>,<левый_прогноз>, <правый_прогноз>:

Class TreeNode:

   Self.left_node

   Self.right_node

   Self.left_prediction

   Self.right_prediction

Еслиузел не является узлом-листом, то левый и правый узлы будут также узламидерева; если же узел окажется узлом-листом, то левого и правого узла не будет,но <левый_прогноз> и <правый_прогноз> получат наиболее предпочтительноезначение.

Такимобразом, базовый алгоритм для прогноза на основе одно примера состоит вследующем. Сначала мы проверяем условие x. Если оно истинно, то мы проверяем наличие левогоузла; если таковой имеется, то вопрос значения прогноза переходит к этомулевому узлу; в противном случае это узел-лист и возвращается значение <левый_прогноз>.Если же условие xложно, то это значит, что мы должны проверить наличие правого узла. Еслитаковой имеется, прогноз будет составляться на его основе, в противном случаеэто узел-лист и возвращается значение <правый _прогноз>:

def predict_one(x):

    ifself.condition(x):

        ifself.left_node:

           return self.left_node.predict_one(x)

        else:

           return self.left_prediction

    else:

        ifself.right_node:

           return self. right_node.predict_one(x)

        else:

            returnself. right_prediction

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

Информационная энтропия

В этом разделе мы рассмотрим теорию, лежащую в основе выбора лучших разделителей в нашем дереве решений. На более высоком уровне нам необходимо найти разделение, которое максимизирует уменьшение неопределённости. Например, если у нас есть разделитель, позволяющий перейти от 50%-й уверенности к 100%-й, – это лучше, чем переход от 50%-й уверенности к 75%-й.

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

Информационнаяэнтропия выражается следующим уравнением:

Этосоответствует ожидаемому значению логарифма p(x).

Каквидите, здесь используется распределение вероятностей по x, как и вдисперсии. Так же можно видеть, что значение энтропии всегда будет больше илиравно нулю, поскольку p(x) всегда находится между 0 и 1, аотрицательный логарифм числа между нулём и единицей больше или равен нулю.Обратите внимание, что когда речь идёт об энтропии, то неявно подразумеваетсялогарифм с основой 2.

Рассмотримдля определённости двоичную переменную. Обозначим вероятность 1 через p, а вероятность0 – через 1 – p.Тогда выражение для энтропии будет иметь вид

Этосоответствует ожидаемому значению логарифма p(x).

Каквидите, здесь используется распределение вероятностей по x, как и вдисперсии. Так же можно видеть, что значение энтропии всегда будет больше илиравно нулю, поскольку p(x) всегда находится между 0 и 1, аотрицательный логарифм числа между нулём и единицей больше или равен нулю.Обратите внимание, что когда речь идёт об энтропии, то неявно подразумеваетсялогарифм с основой 2.

Рассмотримдля определённости двоичную переменную. Обозначим вероятность 1 через p, а вероятность0 – через 1 – p.Тогда выражение для энтропии будет иметь вид

Возникаетвопрос: при каком значении p энтропия становится максимальной? Для нахожденияэтого значения мы берём производную от H(p) относительно p, приравниваемеё к нулю и, решив относительно p, находим: p = 0,5.

Еслипостроить график зависимости H(p) от p, то можно видеть, что H(p) = 0, когда p равно 0 или 1, и достигает пиковогозначения H(p) = 1, когда p = 0,5.

Теперьзадумаемся о значении энтропии. Если вероятность двоичной переменной равна 0,5,то не существует никакого способа сделать удовлетворительный прогноз о еёпоявлении. Независимо от способов прогнозирования, у нас всегда будет 50%-явероятность оказаться правым и такая же 50%-я вероятность ошибиться.

Теперьрассмотрим значение, отличное от 0,5; скажем, p = 0.8. Тогда если мы хотим предсказать значениеданной случайной величины, то всегда должны выбирать 1, поскольку это даётнаилучшие шансы оказаться правым.

Энтропия – это мера количества информации, которую мы получаем от нахождения значения случайной величины. Если мы подбрасываем монетку с вероятностью выпадения орла, равную 0,8, и при этом выпадает орёл, то мы не получим много информации, поскольку уже и так имели 80-процентную уверенность в выпадении орла. Но если мы подбрасываем монетку с вероятностью выпадения орла, равную 0,5, и при этом выпадает орёл, то мы получаем максимально возможное количество информации, поскольку до этого мы были максимально не осведомлены о значении, которое получится. В общем случае распределение вероятностей, дающее максимальную энтропию, – это равномерное распределение.

Максимизация прироста информации

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

АлгоритмID3 работает следующим образом. Мы должны найтиатрибут, который бы наилучшим образом разделял данные, основываясь на максимумеполучения информации за один раз. Разделив данные, этот атрибут больше никогдане используется, а все наши дочерние узлы должны максимизировать получениеинформации, основываясь на оставшихся атрибутах и с учётом полученногоразделения данных. Разделения, применяемые в алгоритме ID3,не требуют обязательно двоичных данных, как наш. К примеру, одним из атрибутовможет быть результат броска игральной кости, который может принимать значенияот 1 до 6. Это значит, что у узла может быть 6 потомков.

Вреализуемой нами версии будут отличия в отношении следующих двух аспектов.Прежде всего, нам не требуется, чтобы атрибут использовался для разделениятолько однажды. С геометрической точки зрения это позволяет нам переходить,скажем, от зелёного к синему и обратно к зелёному. Например, это полезно прирешении «проблемы пончика». Другая причина, по которой при разделении мы будемиспользовать один и тот же атрибут более одного раза, заключается в том, чтокаждый узел дерева будет иметь двух потомков. Вы увидите, что это упрощаетситуацию, когда мы рассмотрим базу данных MNIST.Она будет рассматриваться как набор непрерывных данных, что позволит нам простоопределить порог для разделения на левое и правое, вместо того чтобы иметьпотомков для всех 256 дискретных значений.

Итак,зная базовый алгоритм, выберем лучший атрибут с точки зрения приростаинформации. Как вообще подсчитать её прирост? В этом главной частью данныхявляются метки. Вначале рассмотрим полный набор данных. Предположим, половинаданных относится к классу 1, а половина – к классу 0. В этом случае нашаэнтропия равна 1. Далее предположим, что у нас есть входной атрибут, которыйидеально разделяет данные: всё, что меньше нуля, – класс 0, а всё, что большенуля, – класс 1. Разумеется, мы должны разделять по этому атрибуту, посколькуон даёт нам идеальный классификатор с точностью 100%. Итак, мы нашли пороговоезначение – 0, и теперь энтропия для и левого потомка, и для правого равна нулю.Таким образом, полученная нами информация равна значению исходной энтропии (тоесть 1) минус энтропия для левого потомка, умноженная на 0,5, минус энтропиядля правого потомка, умноженная на 0,5: 1 – 0,5*0 – 0,5*0 = 1 – что являетсямаксимумом, который только можно получить.

Конечноже, данные не всегда так хороши. Намного вероятнее, что нет, после разделениякое-что всё равно останется неправильно классифицированным. Рассмотрим пример сдвумя входными переменными X1 и X2 (см. слайд). Прежде всего мы видим, что энтропия Y здесь равна 1, поскольку шансы на получение нуляили единицы равны 50%.

Теперь,если мы разделим X1 между 1 и 2,то нам нужно рассмотреть подмножество данных, где X1= 1, и подмножество данных, где X1 = 2. Можемвидеть, что энтропия Y для X1 = 1 будет равна0,811, а для X1 = 2 будет равна 0,918:

Такимобразом, прирост информации равен 1 минус 0,4 (согласно размеру первойтаблицы), умноженной на 0,811, минус 0,6 (согласно размеру второй таблицы),умноженному на 0,918:

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

Сделаемтеперь то же самое для столбца с X2. Нам нужнорассмотреть строки, где X2 = 5, и строки,в которых X2 = 10:

Каквидим, обе подтаблицы имеют одинаковую энтропию, равную её максимальновозможному значению, то есть 1. Тогда общий прирост информации составляет 0:

Каквидим, обе подтаблицы имеют одинаковую энтропию, равную её максимальновозможному значению, то есть 1. Тогда общий прирост информации составляет 0:

Следовательно,от разделения по столбцу X2 мы ничего невыигрываем, а значит – мы не должны проводить разделение по этому столбцу, аразделять по столбцу X1.

Впсевдокоде наша функция fit может выглядетьпримерно так:

def fit(X, Y):

    best_IG = 0

   best_attribute = None

    for c incolumns:

       condition = find_split(X, Y, c)

        Y_left = Y[X[c] соответствуетусловию]

        Y_right = Y[X[c] несоответствует условию]

        bnformation_gain = H(Y) – p(левое)H(Y_left) – p(правое)H(Y_right)

        ifinformation_gain > best_IG:

           best_IG = information_gain

           best_attribute = c

            …

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

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

def fit(X, Y):

    best_IG =…

   best_attribute = …

    X_left,Y_left, X_right, Y_right = разделение по best_attribute

   Self.left_node = TreeNode()

   self.left_node.fit(X_left, Y_left)

   Self.right_node = TreeNode()

   self.right_node.fit(X_left, Y_left)

Единственное,чего не хватает, – мы не проверили предельные случаи, которые, конечно же,потребуются при проведении рекурсии. Поскольку это был псевдокод, он давалсялишь для того, чтобы дать общее представление о том, происходит. Но, конечно,ещё нужно рассмотреть предельные случаи.

Содним из них мы уже сталкивались: если прирост информации равен нулю, то ничегонельзя сделать для увеличения точности; это просто должен быть узел-лист. Еслиже это и есть узел-лист, то мы должны выбрать наиболее вероятный класс: еслиединиц больше, чем нулей, то прогнозом должен быть класс 1; если же нулейбольше, чем единиц, то прогноз – класс 0.

Темне менее есть ещё несколько предельных случаев, которые необходимо рассмотреть.Один из них – мы должны избегать переобученности. Можете представить, как сдеревом решений любой глубины мы с лёгкостью можем достичь 100% точности научебном наборе, но, как вы знаете, это может и не привести к хорошему обобщениюи на проверочный набор. Один из способов избежать этого – ограничитьмаксимальную глубину дерева решений. Достигнув максимальной глубины, мы простоостанавливаем рекурсию и преобразуем текущий узел в узел-лист. Следовательно,нам нужно указывать узлу дерева его текущую глубину и какой должна бытьмаксимальная глубина всего дерева.

Последние предельные случаи, которые стоит рассмотреть, наиболее тривиальны. Если есть только один пример, то может быть только один прогноз, так что мы просто в качестве прогноза выдаём метку этого примера. Аналогично если у нас более одного примера, но все они принадлежат одному классу, то мы всё равно должны указать метку, соответствующую этому классу.

Выбор лучшего разделителя

Впредыдущем рассмотренном нами примере было весьма легко выбрать число, покоторому проводить разделение: X1 принимал лишьдва значения – 1 и 2, так что нам просто нужно было собрать все единицы в однутаблицу, а все двойки – в другую. То же касалось X2.А что делать с базой данных MNIST, в которойзначения будут рассматриваться как непрерывные? В случае непрерывных переменныхсуществует бесконечное количество возможных разделений. И мы их всех должныпросмотреть? Или можно найти некоторые правила, приводящие к меньшемуколичеству решений? Конечно, можно!

Первоеправило состоит в том, что нужно рассматривать только середину между любымидвумя упорядоченными точками. Почему так? Потому что разделение в любом другомместе между ними не изменит энтропию. Рассмотрим простейший случай, когда у насесть точки 0, 1, 2, 3 с метками 1, 0, 1, 0. Предположим, мы хотим разделитьмежду 1 и 2. Мы выбираем 1,5 как середину. Энтропия слева равна 1, энтропиясправа – тоже 1. Выбор любого другого разделения между 1 и 2, скажем, 1,75 неизменит энтропию – она по-прежнему будет 1 и 1.

Следующееправило: необходимо рассматривать только границы между разными метками. Так, кпримеру, пусть у нас есть ряд упорядоченных меток: 2 единицы, 6 нулей, 6единиц, 2 нуля. Предположим, мы создаём разделение точно посередине. Это даётнам шесть правильных ответов из восьми для преобладающего класса с каждой изсторон. Общая энтропия при этом равна 1,62:

Теперьпередвинем границу на одну метку влево. Получим 2/7 и 5/7 слева и 3/9 и 6/9справа, что даёт нам общую энтропию, равную 1,78:

Теперьпередвинем границу на одну метку влево. Получим 2/7 и 5/7 слева и 3/9 и 6/9справа, что даёт нам общую энтропию, равную 1,78:

Этобольшее значение энтропии, приводящее к меньшему приросту информации, еслиразделять именно здесь.

Передвинемсяещё на разряд влево. Теперь у нас получается 2/6 и 4/6 слева и 4/10 и 6/10справа, что даёт нам общее значение энтропии 1,89:

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

Итак,процесс поиска лучшего разделителя по данному столбцу следующий. Вначале нужноотсортировать все X в данном столбце в порядке возрастания, а такжеотсортировать в том же порядке соответствующие им Y. Далее необходимо найти пограничные точки, где Y переходит изодного класса в другой. Затем вычисляется прирост информации при разделении вкаждой из этих пограничных точек, являющихся серединами между двумя смежными.После чего берётся та из них, которая обеспечивает максимальный приростинформации.

Ипоследнее. Обратите внимание, что наш код никоим образом не оптимизирован иработает куда медленнее, чем должен: он включает в себя ряд циклов for, особенно когда нужно найти максимум приростаинформации, будь то поиск лучшего разделителя или лучшего столбца. А как мызнаем, цикл for языка Python работает оченьмедленно.

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: