Простейшие деревья принятия решений хороши, пожалуй, только своей наглядностью. Они не оперируют вероятностями или весами. Для решения реальных задач часто используют усложнённые и дополненные модификации деревьев принятия решений.
Тем не менее, знакомство в деревьями принятия решений — это хороший первый шаг в машинном обучении. На их примере можно увидеть, какие бывают проблемы и подходы к решению этих проблем.
Задача деревьев принятия решений состоит в том, чтобы продлить булеву функцию, построенную по заданным точкам, на неизвестные точки.
Проще всего, оттолкнуться от примера.
Пусть мы решаем задачу: мужчина перед нами или женщина. У нас есть несколько критериев:
Пусть у нас есть такие наблюдения:
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, которое учитывает ещё и количество информации, требуемое для разделения по данному атрибуту. Используется так же индекс Гини. Про это же, возможно, расскажу отдельно.