Метод дерева принятия решений.

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

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

Пример дерева принятия решений для анализа кредитоспособности заемщика показан на рисунке 2.

Рисунок 2

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

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

Способ, которым алгоритм дерева принятия решений строит дерево для дискретного прогнозируемого столбца, можно продемонстрировать на примере. На рисунке 3 показана гистограмма для прогнозируемого столбца "Покупатели велосипедов" в зависимости от входного столбца "Возраст". Гистограмма показывает, что возраст человека влияет на то, купит ли человек велосипед.

Рисунок 3

Корреляция, показанная на диаграмме, приведет к тому, что алгоритм дерева принятия решений создаст новый узел в модели (рисунок 4).

Рисунок 4

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

Для непрерывных атрибутов метод использует линейную регрессию для определения узла разбиения дерева решений.

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

Рисунок 5

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

Рисунок 6

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

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

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

Типы содержимого входных столбцов	Непрерывные, циклические, дискретные, дискретизированные, табличные и упорядоченные
Типы содержимого прогнозируемых столбцов	Непрерывные, циклические, дискретные, дискретизированные, табличные и упорядоченные

Алгоритм дерева решений поддерживает несколько параметров, влияющих на производительность и точность получаемых результатов. В частности, можно задать метод, используемый для вычисления коэффициента разбиения (энтропия, априорный метод Байеса с K2 или априорный эквивалент Дирихле метода Байеса (BDE)), метод, используемый для разбиения узла (двоичный, полный или оба), минимальное количество конечных вариантов, необходимых для формирования разбиения в дереве решений и др.