Оглавление

Введение в деревья принятия решений

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

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

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

Проще всего, оттолкнуться от примера.

Пример входных данных для построения дерева принятия решений

Пусть мы решаем задачу: мужчина перед нами или женщина. У нас есть несколько критериев:

Пусть у нас есть такие наблюдения:

S H V  sex
y y y  F
y y n  F
y n y  F
y n n  M
n y y  M
n n y  M

Это наши обучающие данные.

Построение дерева принятия решений (примитивный подход)

Дерево принятия решений состоит из

Вы можете заглянуть в конец заметки и посмотреть на наше результирующее дерево.

Построение оптимального дерева принятия решений

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

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

Чтобы построить оптимальное дерево, мы должны оттолкнуться именно от информативности, нам понадобится энтропия.

Определение энтропии

Формально, можно дать такое определение: Пусть у нас есть множество из N элементов. Есть некое свойство S, которое может принимать два значения (значений может быть сколько угодно, но мы не будем здесь сильно углубляться; рассмотрим простейший случай). M этих элементов обладают свойством S='y'. Соответственно, оставшиеся N-M элементов обладают свойством S='n'. Тогда энтропия нашего множества по отношению к свойству S выражается формулой:

H(S) = -Σpᵢlog₂(pᵢ) = -( m/n * log₂(m/n) + (m-n)/n * log₂((m-n)/n) )

Формула с вероятностями pᵢ — это как раз общая формула, для случая, когда S может принимать несколько значений.

Чаще всего, логарифм берётся двоичный, но, строго говоря, основание логарифма не имеет большого значения. Если вы используете основание 2, то смысл энтропии в том, сколько надо бит для хранения вашей информации. Но если вы используете натуральный логарифм, то вы получаете «сколько нужно разрядов в системе счисления с основанием e». Может звучать странно, но именно это основание обеспечивает максимальную «вместимость» системы счисления. Это, — совершенная система счисления. Хотя, это уже немного другая история.

Не очень понятно? Давайте рассмотрим пример. Пусть у нас есть буквы русского алфавита (33 штуки). Есть какая-то их последовательность, где каждая буква встречается с равной вероятностью (1/33). Выберем свойство S. Допустим, будем считать свойством S гласность буквы. Тогда наша последовательность букв принимает вид гласная-гласная-негласная-гласная… Энтропия этого потока (не потока букв, а потока свойства S) вычисляется по формуле:

H(S) = - ( 10/33*log₂(10/33) + 23/33*log₂(23/33) ) = 0.885…

Это и есть энтропия нашего потока по отношению к свойству S.

То есть на запись одной буквы (вернее её признака S), при таких статистических свойствах последовательности, нам надо минимум 0.885 бит.

Здесь уместен вопрос, а что делать, если буквы в последовательности встречаются не с равной вероятностью? Этот вопрос будет рассмотрен применительно к Бейсовским классификаторам.

В наших задачах, «свойство» — это искомое свойство, которое должно определять дерево. То есть — пол.

Следующее, что нам понадобится — оценка информационного вклада атрибута.

Информационный вклад атрибута

Пусть у нас есть атрибут Q, который (для простоты) принимает два значения.

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

G(Q) = H(S) - p₁H₁(S) - p₂H₂(S)

где p₁ — доля данных с первым значение Q, p₂ — со вторым значением Q. Hᵢ — энтропия, рассчитанная на данном подмножестве.

Теперь мы можем оценить информационный вклад разных свойств:

Свойство            вклад
--------            -----
юбка (S)            0.553
длинные волосы (H)  0.057
высокий голос (V)   0

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

Кстати, обратите внимание, что голос не дал нам никакой новой информации. Действительно: с высоким голосом мы имеем двое мужчин и двое женщин, и с низким голосом одного мужчину и одну женщину. На основе этого параметра ничего сказать невозможно. (Пока.)

Начнём строительство дерева именно с признака «юбка». Мы получаем две подзадачи: построить два дерева для тех кто в юбке и тех, кто — нет.

Подзадача «есть»

Здесь у нас остаются только четыре обучающих случая:

S H V  sex
y y y  F
y y n  F
y n y  F
y n n  M

Даже просто глядя на эту табличку становится ясно, что оба параметра одинаково информативны (gain = 0.216). Действительно, вклад от y-случая и от n-случая одинаков. Посмотрите и посчитайте варианты.

То есть, нам всё равно, какой из атрибутов выбрать, давайте выберем «волосы».

Теперь мы получаем снова пару совсем простых подзадач:

S=y, H=y     S=y, H=n
----------   ----------
S H V  sex   S H V  sex
y y y  F     y n y  F
y y n  F     y n n  M

Тут уже всё однозначно: в H=y-случае мы можем только сказать — «женщина», а в случае H=n осталось проанализировать V (в этом контексте он уже может дать информацию).

Подзадача «нет»

Тут тоже осталось сделать одно действие:

S H V  sex
n y y  M
n n y  M

Тут видно, что ни V, ни даже H, не дают никакой информации.

Результирующее дерево принятия решений

           есть ли юбка?
           -+---------+-
            |         |
 .--  нет --'         `-- есть --.
 |                               v
 v                         длинные ли волосы?
 мужчина                   --+------------+--
                             |            |
                   .-- нет --'            да
                   |                      |
                   v                      v
            высокий ли голос?          женщина
            --+-----------+--
              |           |
    .-- нет --'           да
    |                     |
    v                     v
 мужчина               женщина

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

Что осталось за скобками

Мы тут только вскользь упомянули явление переобученности. Оно начинает играть очень большую роль, если данные зашумлены, а параметров много. Дерево начинает разрастаться, причём, длинные ветки становятся бесполезными.

То есть, дерево становится «занудой»: оно задаёт очень много вопросов, но качество ответов от этого не увеличивается.

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

Второй вопрос, что делать, если обучающие патерны противоречивы? Например, у нас было два человека с одинаковым набором наших атрибутов, но одни — мужчина, а другой — женщина. В этом случае в ответе будет фигурировать или вероятность или (и это не редко) берётся просто ответ, правильно описывающий большее количество обучающих патернов.

И мы ничего не сказали о вероятностях. Решающие деревья с ними и не оперируют. Я постараюсь раскрыть этот вопрос отдельно.

Кроме того, когда вы начнёте сами делать решающие деревья, вы столкнётесь с рядом чисто практических проблем. Скажем, в наших данных могли быть не только одежда/волосы/голос, но и «рост в миллиметрах». Этот последний параметр оказался бы самым информативным (с точки зрения информационного вклада), но понятно, что на самом деле, он бесполезен.

Чтобы избежать таких проблем используется gain ratio, которое учитывает ещё и количество информации, требуемое для разделения по данному атрибуту. Используется так же индекс Гини. Про это же, возможно, расскажу отдельно.