Деревья решений и алгоритмы их построения

Сегодня мы поговорим об одном из классических методов интеллектуального анализа данных (англ. data mining) – построении деревьев решений, расскажем о его основных принципах и подробнее остановимся на алгоритмах его реализации.

Что такое дерево принятия решений?

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

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

Пример использования

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

Как пример, представим случай, когда необходимо принять решение о выдаче кредита (целевая функция может принимать значения «да» и «нет») на основе информации о клиенте (несколько переменных: возраст, семейное положение, уровень дохода и так далее). К примеру, переменная «возраст» с атрибутом «менее 21 одного года = да» сразу приведет от корневого узла дерева к его листу, причем целевая функция «выдача кредита» примет значение «нет». Если возраст составляет более 21 года, то ветвь приведет нас к очередному узлу, который, к примеру, «спросит» нас об уровне дохода клиента. Таким образом, классификация каждого нового случая происходит при движении вниз до листа, который и укажет нам значение целевой функции в каждом конкретном случае.

Общий алгоритм построения дерева принятия решения

Предлагаем рассмотреть на нашем примере общий алгоритм построения дерева, чтобы затем перейти к его частным случаям:

• Вначале необходимо выбрать атрибут Q (в нашем случае, допустим: уровень дохода > 500$ в месяц) и поместить его в корневой узел.
• Затем, из наших тестовых примеров (или набора данных) для каждого значения атрибута i (в нашем случае их два – «да» и «нет») выбираем только те, для которых Q=i.
• Далее, рекурсивно строим дерево принятия решений.

Основная проблема, очевидно, кроется в первом шаге – на каком основании выбирается каждый следующий атрибут Q? На этот вопрос существует несколько ответов в виде частных алгоритмов принятия решений – главными из которых являются алгоритмы ID3, C4.5 и CART

Основные частные алгоритмы

1. ID3. В основе этого алгоритма лежит понятие информационной энтропии – то есть, меры неопределенности информации (обратной мере информационной полезности величины). Для того чтобы определить следующий атрибут, необходимо подсчитать энтропию всех неиспользованных признаков относительно тестовых образцов и выбрать тот, для которого энтропия минимальна. Этот атрибут и будет считаться наиболее целесообразным признаком классификации.
2. C5. Этот алгоритм – усовершенствование предыдущего метода, позволяющее, в частности, «усекать» ветви дерева, если оно слишком сильно «разрастается», а также работать не только с атрибутами-категориями, но и с числовыми. В общем-то, сам алгоритм выполняется по тому же принципу, что и его предшественник; отличие состоит в возможности разбиения области значений независимой числовой переменной на несколько интервалов, каждый из которых будет являться атрибутом. В соответствии с этим исходное множество делится на подмножества. В конечном итоге, если дерево получается слишком большим, возможна обратная группировка – нескольких узлов в один лист. При этом, поскольку перед построением дерева ошибка классификации уже учтена, она не увеличивается.
3. CART. Алгоритм разработан в целях построения так называемых бинарных деревьев решений – то есть тех деревьев, каждый узел которых при разбиении «дает» только двух потомков. Грубо говоря, алгоритм действует путем разделения на каждом шаге множества примеров ровно напополам – по одной ветви идут те примеры, в которых правило выполняется (правый потомок), по другой – те, в которых правило не выполняется (левый потомок). Таким образом, в процессе «роста» на каждом узле дерева алгоритм проводит перебор всех атрибутов, и выбирает для следующего разбиения тот, который максимизирует значение показателя, вычисляемого по математической формуле и зависящего от отношений числа примеров в правом и левом потомке к общему числу примеров.

Резюме

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