Алгоритмы деревьев принятия решений: обзор. Часть 1.

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

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

Было показано, что деревья решений (ДР) имеют хорошие показатели качества и предоставляют релевантную информацию о том, почему принимается решение [2]. Эксперты используют ДР для многих прикладных направлений - в медицине [3], образовании [4], химической промышленности [5], социальной сфере [6], информационной безопасности [7].

Дерево решений – средство поддержки принятия решений для прогнозных моделей [1].

Суть его работы заключается в последовательном разбиении множества данных на непересекающиеся классы, которые в свою очередь также подвергаются разбиению по каким-либо критериям с оценкой эффективности разбиения. Как правило, дерево решений состоит из «узлов», «листьев» и «веток». «Ветки» содержат записи атрибутов, от которых зависит целевая функция, «листья» – значения целевой функции, а «узлы» – остальные атрибуты, по которым происходит классификация [1]. Чаще всего выделяют два типа деревьев: для классификации (в этом случае предсказываемый результат – класс, которому принадлежат данные) и для регрессии (результат – прогнозируемое значение целевой функции).

В общем, стандартная процедура, используемая для индукции ДР из данного обучающего набора S, делится на две фазы - фазы роста и обрезки. При этом S разбивается на две части, A и Y, где A представляет входной набор функций, а Y представляет целевой набор функций. Некоторые из наиболее популярных алгоритмов ДР выполняют обе фазы, например, Iterative Dichotomiser 3 (ID3) , C4.5, деревья классификации и регрессии (CART), χ2Automatic Interaction Detection (CHAID), KLDDT и дерево принятия решений по расстоянию Хеллингера (HDDT) (см. [8, 9] и ссылки в них). Помимо S (A и Y), алгоритм для индукции ДР включает четыре основных компонента: три компонента составляют фазу роста (growth phase), и один компонент составляет фазу обрезки (pruning phase) [9]. Каждый компонент представляет из себя отдельную функцию, поскольку существует несколько способов выполнения определенного действия. Общий алгоритм ДР составлен из четырех компонентов: функции критерия разбиения (splitting criterion function, σ), функции критерия оценки (evaluation measure function, δ), функциии критерия остановки (stopping criterion function, ψ) и функции обрезки (pruning method function, ξ)[9].

Первой фазой индукции DT является фаза роста дерева решений, приведенная в алгоритме 1 (рис.1).

Рис.1 Алгоритм фазы роста ДР [9].

Краткое описание алгоритма.

Алгоритм начинается с создания нового дерева (decision tree, DT) с одним единственным узлом t (корневым узлом), содержащим все объекты в S. После этого идет проверка, выполнено ли условие остановки (строка 2, параметры состояния могут варьировать). Если это так, узел в t помечается с использованием определенного правила (например, пометить конечный узел мажоритарным классом), которое зависит от критерия остановки (строка 3). Например, если все объекты связаны с одним классом cj ∈ Y, то t становится конечным узлом, помеченным как cj. В противном случае алгоритм начинает генерировать набор P возможных пар признаков/вариантов разбиения на подмножества (далее для краткости называем их «парами») в соответствии с заданным критерием разделения (строка 5). Каждая пара состоит из входного признака (ai ∈ A) и соответствующим вариантом разбиения на подмножества p(S). Затем алгоритм определяет наилучшую пару в P, используя заданную функцию критерия оценки (строка 6). После обнаружения лучшая пара (ai,p(S))∗ в узле t помечается значением, содержащимся во входном признаке ai (строка 7). Затем запускается рекурсивный процесс путем связывания полученного узла с другими, сгенерированными по тому же алгоритму (строки 8–13). Наконец, алгоритм возвращает дерево решений (строка 15).