Деревья решений

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

Данный раздел посвящен одному из методов анализа решений - деревьям решений и классификаций.

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

В качестве примера дерева классификации рассмотрим модель принятия решений руководителем, которая была первоначально описана Виктором Врумом (Victor Н. Vroom) и Филиппом Йеттоном (Philip Yetton) в 1973 г. в их книге «Лидерство и принятие решений» («Leadership and Decision Making»).

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

1.	Сформулировано ли требование достижения определенного качества решения так, чтобы можно было отдать предпочтение одному из множества вариантов решений?
2.	Имеется достаточно информации для принятия решения?
3.	Структурирована ли проблема?
4.	Имеет ли принципиальное значение согласие подчиненных с принимаемым решением?
5.	Получит ли поддержку автократическое решение?
6.	Высока ли мотивация подчиненных на выполнение задачи?
7.	Высока ли вероятность конфликта между подчиненными при выборе варианта решения?

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

Стили лидерского поведения по В. Вруму и Ф. Йеттону

Обозначение	Стиль	Характеристика
А I	Автократический I	Руководитель принимает решение сам, используя имеющуюся у него на данное время информацию.
А II	Автократический II	Руководитель получает необходимую информацию от своих подчиненных и затем сам принимает решение. Работники привлекаются только на этапе сбора информации. Выработку решения и его принятие осуществляет руководитель
CI	Консультативный I	Руководитель на индивидуальной основе делится соображениями по проблеме с имеющими к ней отношение подчиненными с целью получения от них идей и предложении, не собирая при этом их в группу. Затем он сам принимает решение, которое может основываться на вкладе подчиненных, а может и нет
CII	Консультативный II	Руководитель делится соображениями по проблеме с подчиненными, собрав их вместе. В ходе совещания он собирает их идеи и предложения. Затем он принимает решение, которое может либо отражать, либо не отражать мнение большинства
G	Групповой	Руководитель делится соображениями по проблеме с подчиненными. Они совместно оценивают альтернативы и пытаются достичь консенсуса относительно решения. Роль, выполняемая при этом руководителем, больше похожа на роль председателя собрания, координирующего дискуссию, концентрирующего внимание на проблеме и делающего все для того, чтобы рассматривались наиболее важные аспекты проблемы. Руководитель не пытается влиять на группу с тем, чтобы она приняла его решение, и проявляет готовность принять и выполнить любое решение, получившее поддержку всей группы

Понятия и определения.

Пусть дана обучающая выборка \(\mathcal{D} = \left\{\textbf{x}_i, y_i\right\}^n_{i = 1}\) из \(n\) точек в \(d\)-мерном пространстве, причем \(y_i\) является меткой класса для точки \(\textbf{x}_i\). Предположим, что атрибуты \(X_j\) являются числовыми или категориальными и что существует \(k\) различных классов,таких, что \(y_i \in {c_1, c_2, ..., c_k}\).

Классификатор дерева решений - это рекурсивный алгоритм, основанный на модели дерева, который предсказывает класс \(y_i\) для каждой точки \(x_i\). Обозначим через \(\mathcal{R}\) пространство данных, включающее в себя множество входных точек \(\mathcal{D}\). Дерево решений использует ось-параллель гиперплоскости, чтобы разбить пространство данных \(\mathcal{R}\) на два результирующих полупространства или области, например \(\mathcal{R}_1\) и \(\mathcal{R}_2\), что индуцирует разбиение входных точек на множества \(\mathcal{D}_1\) и \(\mathcal{D}_2\), соответственно. Каждая из этих областей рекурсивно расщепляется через параллельные осевые гиперплоскости, до тех пор, пока точки внутри индуцированного раздела не будут относительно чисты в терминах класса их метки, то есть большинство точек будет принадлежать одному классу. Полученная иерархия разделенного решения составляет модель дерева решений, с листовыми узлами, помеченными как мажоритарный класс. Чтобы классифицировать новую контрольную точку, нужно рекурсивно оценивать, какому полупространству она принадлежит, пока не достигнем листового узла в дереве решений, и в этот момент прогнозируем класс, к которому она принадлежит, как метку листа.

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

Гиперплоскость \(h (\textbf{x})\) определяется как множество всех точек \(\textbf{x}\), удовлетворяющих уравнению \[ h (\textbf{x}): w^T \textbf{x} + b = 0. \] Здесь \(w \in R^d\) - весовой вектор, перпендикулярный к гиперплоскости, а \(b\) - смещение гиперплоскости от начала координат. Дерево решений рассматривает только ось-параллель гиперплоскости, т. е. весовой вектор должен быть параллелен одному из исходных осей или осей \(X_j\). Иначе говоря, весовой вектор \(w\) по направлению априори ограничен одним из векторов базиса \(\{e_1, e_2,. , , , e_d\}\), где \(e_i \in R^d, \|e_i\|=1 \). Если \(\textbf{x} = (x_1, x_2, ..., x_d)^T\) и \(w = e_j\), то \[ h (\textbf{x}): e^T_j \textbf{x} + b = 0, \] откуда следует, что \[ h (\textbf{x}): \textbf{x}_j + b = 0, \] где выбор смещения \(b\) дает разные гиперплоскости вдоль размерности \(X_j\).

Гиперплоскость определяет решение или точку расщепления (сплит-точку - split-point), поскольку она разделяет пространство данных \(\mathcal{R}\) на два полупространства. Все точки \(\textbf{x}\) такие, что \(h (\textbf{x}) \le 0\) находятся с одной стороны гиперплоскости, тогда как все точки такие, что \(h (\textbf{x})\gt 0\) находятся на другой стороне. Разделительная точка, связанная с ось-параллельной гиперплоскостью может быть записана как \(h (\textbf{x}) \le 0\), откуда следует, что \(\textbf{x}_i + b \le 0\) или \(x_i \le -b\). Так как \(\textbf{x}_i\) некоторое значение из \(X_j\) и смещение \(b\) может принимать любое значение, то общая форма разделительной точки для числового атрибута \(X_j\) дается как \(X_j \le v\), где \(v = -b\) - некоторое значение из области атрибута \(X_j\). Решение или точка расщепления \(X_j \le v\) разделяет пространство входных данных \(\mathcal{R}\) на две области \(\mathcal{R}_{Yes}\) и \(\mathcal{R}_{No}\), которые обозначают множество всех возможных точек, удовлетворяющих решению, и тех, которые этого не делают.

Каждое разбиение \(\mathcal{R}\) на две области \(\mathcal{R}_{Yes}\) и \(\mathcal{R}_{No}\) также индуцирует разбиение соответствующих входных данных \(\mathcal{D}\). Таким образом, точка расщепления \(X_j \le v\) индуцирует деление данных на два раздела \[ \mathcal{D}_{Yes} = \{\textbf{x} | \textbf{x} \in \mathcal{D}, \textbf{x}_j \le v\}, \mathcal{D}_{No} = \{\textbf{x} | \textbf{x} \in \mathcal{D}, \textbf{x}_j \gt v\}, \] где \(\mathcal{D}_{Yes}\) - подмножество точек данных, которые лежат в области \(\mathcal{R}_{Yes}\), а \(\mathcal{D}_{No}\) - подмножество входных точек из \(\mathcal{R}_{No}\).

Чистота области \(\mathcal{R}_j\) определяется в терминах смеси классов для точек в соответствующем множестве данных \(\mathcal{D}_j\). Формально чистота - это доля точки с меткой большинства в \(\mathcal{D}_j\), т.е. \[ purity (\mathcal{D}_j) = \max_i\left\{\frac{n_{ji}}{n_j}\right\} \] где \(n_j = |\mathcal{D}_j|\) - общее число точек данных в области \(\mathcal{R}_j\), а \(n_{ji}\) - количество точек в \(\mathcal{D}_j\) с меткой класса \(c_i\).

Дерево решений может обрабатывать не только числовые атрибуты, но и категориальные данные. Для категориального атрибута \(X_j\), точки расщепления или решения имеют вид \(X_j \in V\), где \(V \subset dom (X_j)\) и \(dom (X_j)\) обозначает область значений \(X_j\). Интуитивно это расщепление можно считать категориальным аналогом гиперплоскости. Результат его использования также приводит к двум «полупространствам», одной области \(\mathcal{R}_{Yes}\), состоящей из точек \(\textbf{x}\), которые удовлетворяют условию \(\textbf{x}_i \in V\), а другая область \(\mathcal{R}_{No}\) содержит точки, которые ему не удовлетворяют, то есть такие, что \(\textbf{x}_i \notin V\).

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

Приведем алгоритм построения дерева классификаций.

\(n \leftarrow |\mathcal{D}_j|\) //число разбиений
\(n_i \leftarrow |\{x_j|x_j \in \mathcal{D}, y_j = c_i\}| \)// Размер класса \(c_i\)
\(purity(\mathcal{D}) \leftarrow \max_i \left\{\frac{n_i}{n}\right\}\)
if n ≤ η or purity(\(\mathcal{D}\)) ≥ π then // условие завершения построения дерева
- \(c^* \leftarrow arg max_i\left\{\frac{n_i}{n}\right\} \)// мажоритарный класс
- создать листовой узел и пометить его классом \(c^*\)
return
(split-point*, score*)\( \leftarrow (\emptyset, 0)\) // инициализировать лучшую точку расщепления
foreach (attribute \(X_j\)) do
- if (\(X_j\) is numeric) then
  - \((v, score) \leftarrow\) Оценка числовых атрибутов \((\mathcal{D}, X_j)\)
  - if score > score* then (split-point*, score*) \(\leftarrow (X_j \le v, score)\)
- else if (\(X_j\) is categorical) then
  - \((V, score) \leftarrow \) Оценка категориальных атрибутов \((\mathcal{D}, X_j)\)
  - if score > score∗ then (split-point*, score*) \(\leftarrow (X_j \in V, score)\)
// разбиение \(\mathcal{D}\) на \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\) использует split-point* (рекурсия)
\(\mathcal{D}_{Yes} \leftarrow \{\textbf{x} \in \mathcal{D} | \textbf{x} \) обеспечивает split-point*}
\(\mathcal{D}_{No} \leftarrow \{\textbf{x} \in \mathcal{D} | \textbf{x} \) не обеспечивает split-point*}
Создаем внутренний узел split-point*, с двумя дочерними узлами,\(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\)
DecisionTree( \(\mathcal{D}_{Yes}\)); DecisionTree(\(\mathcal{D}_{No}\)).

В качестве входных данных требуется обучающая выборка \(\mathcal{D}\) и два параметра η и π, где η - размер листа и π порог чистоты листа. Различные точки рсщепления оцениваются для каждого атрибута из \(\mathcal{D}\). Числовые значения имеют вид \(X_j \le v\) для некоторого \(v\) из диапазона значений атрибута \(X_j\), а категориальные, имеют вид \(X_j \in V\) для некоторого подмножества из области значений \(X_j\). Лучшая точка расщепления выбирается для разделения данных на два подмножества: \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\), где \(\mathcal{D}_{Yes}\) соответствует всем точкам \(\textbf{x}\in \mathcal{D}\), которые удовлетворяют разрешенному решению, а \(\mathcal{D}_{No}\) соответствует всем точкам, которые не удовлетворяют.
Для остановки рекурсивного разбиения можно использовать несколько условий. Простейшее условие основано на размере разбиения \(\mathcal{D}\). Если число \(n\) точек, попавших в \(\mathcal{D}\) меньше заданного пользователем порога размера η, тогда процесс разбиения завершается и строится лист.

Иллюстрация дерева классификации.

Меры оценки расщепления.

Получение точки расщепления для условия \(X_j \le v\) или \(X_j \in V\) то есть, соответственно, для числового или категориального атрибута, требует объективный критерий. Интуитивно хотим выбрать точку расщепления, которая дает лучшее разделение между классами с разными метками.

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

Энтропия набора помеченных точек \(\mathcal{D}\) определяется следующим образом \[ H(\mathcal{D})=-\sum_{i=1}^kP(c_i|\mathcal{D})\log_aP(c_i|\mathcal{D}), \] где \(P(c_i|\mathcal{D})\) - вероятность попадания класса \(c_i\) в \(\mathcal{D}\), а \(k\) - число классов и \(a\)-разрядность используемой системы исчисления, как правило, берут \(a=2\).
Если область чиста, т.е. имеет точки из одного и того же класса, то энтропия равна нулю. С другой стороны, если все классы смешаны, и каждый из них появляется с равной вероятностью \(P(c_i|\mathcal{D})=k^{-1}\), то энтропия имеет максимальное значение, \(H(\mathcal{D})=\log_2k\).
Пусть точка расщепления разбивает \(\mathcal{D}\) на \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\). Определим энтропию расщепления как взвешенную энтропию каждого из результирующих разделов \[ H\left(\mathcal{D}_{Yes},\mathcal{D}_{No}\right)=\frac{n_{Yes}}{n}H\left(\mathcal{D}_{Yes}\right)+\frac{n_{No}}{n}H\left(\mathcal{D}_{No}\right), \] где \(n = |\mathcal{D}|\) - число точек \(\mathcal{D}\), а \(n_{Yes} = |\mathcal{D}_{Yes}|\) и \(n_{No} = |\mathcal{D}_{No}|\) соответственно, количество точек \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\).
Чтобы увидеть, приводит ли использование данной точки расщепления к уменьшению общей энтропии (то есть повышению информационности, точности попадания в соответствующий класс), найдем прирост информации (коэффициент усиления) \[ Gain \left(\mathcal{D},\mathcal{D}_{Yes},\mathcal{D}_{No}\right) = H\left(\mathcal{D}\right) - H\left(\mathcal{D}_{Yes},\mathcal{D}_{No}\right) \] Чем выше коэффициент усиления информации, тем больше уменьшается энтропия и тем лучший результат дает точка расщепления. Таким образом, можем оценивать каждую точку расщепления и выбирать ту, которая дает максимальный выигрыш в информации.

Еще одна распространенная мера для измерения качества расщепления - это Gini-index, характеристика, во многом интуитивная, определяемая следующим образом \[ G(\mathcal{D})=1-\sum_{i=1}^kP^2(c_i|\mathcal{D}). \]

Коррадо Джини (Corrado Gini), известный итальянский статистик, демограф и социолог. Наибольшую известность ему принесла разработка "коэффициента Джини", статистического показателя, свидетельствующего о степени расслоения общества данной страны или региона по отношению к какому-либо изучаемому признаку. В работе "Научное основание фашизма" он возражал против экономической поддержки больших семей как бесполезного и опасного подталкивания к рационализации репродуктивных функций. Следуя данным (http://poslezavtra.com.ua/ekonomicheskoeneravenstvo-v-ukraine/), индекс Джини для Украины чуть выше чем у Китая, и немного ниже Нигерии.

Если раздел чист, то вероятность мажоритарного класса равна 1, а вероятность всех остальных классов равна 0, и, следовательно, индекс Джини равен 0. С другой стороны, если каждый класс представлен одинаково, с вероятностью \(P(c_i|\mathcal{D})=k^{-1}\), то индекс Джини имеет значение \((k-1)k^{-1}\). Таким образом, более высокие значения индекса Джини указывают на больший беспорядок и более низкие значения указывают, что порядка больше (с точки зрения меток классов). Значение индекса Джини внесенное точкой расщепления равно \[ G\left(\mathcal{D}_{Yes},\mathcal{D}_{No}\right)=\frac{n_{Yes}}{n}G\left(\mathcal{D}_{Yes}\right)+\frac{n_{No}}{n}G\left(\mathcal{D}_{No}\right), \] где \(n = |\mathcal{D}|\) - число точек \(\mathcal{D}\), а \(n_{Yes} = |\mathcal{D}_{Yes}|\) и \(n_{No} = |\mathcal{D}_{No}|\) соответственно, количество точек \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\).
Чем ниже значение индекса Джини, тем лучше точка расщепления.

Кроме энтропии и индекса Джини для оценки расщепления могут использоваться и другие меры, так, например, показатель классификации и регрессии (CART -Classification And Regression Trees), определяемый следующим образом \[ CART\left(\mathcal{D}_{Yes},\mathcal{D}_{No}\right)=2\frac{n_{Yes}}{n}\frac{n_{No}}{n} \sum_{i=1}^k\left|P(c_i|\mathcal{D}_{Yes})-P(c_i|\mathcal{D}_{No})\right|. \] Эта мера предпочитает точку расщепления, которая максимизирует разницу между вероятностями классов для двух разделов - чем выше показатель CART, тем лучше результат разделения.

Еще один критерий DKM - это критерий разбиения на основе примесей, предназначенный для атрибутов двоичного класса (Dietterich et al., 1996) и (Kearns and Mansour, 1999). В этом случае мера на основе примесей будет иметь вид: \[ DKM\left(c_i,\mathcal{D}_{Yes},\mathcal{D}_{No}\right)=2\sqrt{P(c_i|\mathcal{D}_{Yes})\times P(c_i|\mathcal{D}_{No})}. \] Теоретически было доказано (Kearns and Mansour, 1999), что для достижения заданной погрешности, для этого критерия требуются меньшие деревья, чем при использовании других критериев, основанных на примесях (коэффициент усиления информации и индекс Джини).

Описанные критерии предвзято относится к атрибутам доменов с большими размерами, отдавая им предпочтения по сравнению с атрибутами доменов с меньшими размерами. По этой причине полезно при их использовании вначале провести нормализацию, так вместо прироста информации (коэффициента усиления), использовать \[ GainRatio\left(\mathcal{D},\mathcal{D}_{Yes},\mathcal{D}_{No}\right)=\frac{Gain \left(\mathcal{D},\mathcal{D}_{Yes},\mathcal{D}_{No}\right)} {H\left(\mathcal{D}\right)}=\frac{H\left(\mathcal{D}\right) - H\left(\mathcal{D}_{Yes},\mathcal{D}_{No}\right)}{H\left(\mathcal{D}\right)}. \] Однако и тут не все так просто, прежде всего, это отношение не определено, в случае, когда знаменатель равен нулю, да и вообще, \(GainRatio\left(\mathcal{D},\mathcal{D}_{Yes},\mathcal{D}_{No}\right)\) имеет склонность к атрибутам, для которых знаменатель очень мал.
Для того, чтобы постараться все учесть (Quinlan,1988) построение дерева предлагается проводить в два этапа. Сначала вычисляется коэффициент усиления информации для всех атрибутов и принимая во внимание только атрибуты, которые выполнялись, по крайней мере, так же хорошо, как средний коэффициент усиления информации, выбирается атрибут, который получил наилучшее соотношение коэффициента усиления.

Ортогональный (ОРТ -Orthogonal Criterion) критерий был представлен Fayyad and Irani (1992). Этот двоичный критерий определяется следующим образом: \[ ORT \left(c_i,\mathcal{D}_{Yes},\mathcal{D}_{No}\right) = 1 -\cos{\theta \left(P(c_i|\mathcal{D}_{Yes}), P(c_i|\mathcal{D}_{No})\right)}, \] где \(\theta(\textbf{a},\textbf{b})\) - угол между двумя векторами \(\textbf{a}\) и \(\textbf{b}\).

Байесовские деревья

Числовые атрибуты

Пусть \(X\) является числовым атрибутом и необходимо оценить точки расщепления \(X \le v\). Ясно, что даже если ограничиваемся условием, что \(v\) лежит в пределах диапазона значений атрибута \(X\), то существует бесконечное число значений для выбора \(v\). Один из подходов состоит в том, чтобы рассматривать только средние точки между двумя последовательными различными значениями для X в выборке \(\mathcal{D}\). Это связано с тем, что сплит-точки \(X \le v\), для \(v \in [x_a, x_b)\), где \(x_a\) и \(x_b\) - два последовательных различных значения из \(X\) в \(\mathcal{D}\), порождают такое же разбиение \(\mathcal{D}\) на \(\mathcal{D}_{Yes}\) и \(\mathcal{D}_{No}\) и, следовательно, дают одинаковые оценки. Так как для \(X\) может быть не более \(n\) различных значений, то и средних точек не более \(n - 1\).
Обозначим через \(\{v_1, ..., v_m\}\) множество всех средних точек, таких, что \(v_1 \lt v_2 \lt \ldots \lt v_m\) Для каждой сплит-точки \(X \le v\) нужно оценить класс \[ P (c_i | \mathcal{D}_{Yes}) = P (c_i | X \le v), P (c_i | \mathcal{D}_{No}) = P (c_i | X \gt v). \] Пусть \(I (\cdot)\) - индикаторная переменная, которая принимает значение 1 только тогда, когда его аргумент равен true и равно 0 в противном случае. Используя теорему Байеса, имеем \[ P (c_i | X \le v) = \frac{P (X \le v |c_i) P(c_i)}{P(X\le v)} = \frac{P (X \le v |c_i) P(c_i)}{\sum_{j=1}^kP(X\le v|c_j)P(c_j)}, \] где \(P(c_i)\) априорная вероятность выпадения класса \(c_i\) из \(\mathcal{D}\) \[ P(c_i)=\frac{1}{n}\sum_{j=1}^nI(u_j=c_i)=\frac{n_i}{n}, \] здесь \(u_j\) - класс для точки \(\textbf{x}_j, n = | \mathcal{D} |\) - общее число точек, а \(n_i\) - число точек из \(\mathcal{D}\), принадлежащих классу \(c_i\). Пусть \(N_{vi}\) число точек \(x_j \le v\) из класса \(c_i\), где \(x_j\) - значение атрибута \(X\) точки данных \(\textbf{x}_j\): \[ N_{vi}=\frac{1}{n}\sum_{j=1}^nI(x_j\le v \& u_j=c_i)=\frac{n_i}{n}, \] Тогда мы можем оценить \(P (X \le v | c_i)\) \[ P (X \le v | c_i) = \frac{P (X \le v \& c_i)}{P(c_i)}= \left(\frac{1}{n}\sum_{j=1}^nI(x_j\le v \& u_j=c_i)\right)/\left(\frac{n_i}{n}\right) =\frac{N_{vi}}{n_i}. \] Из полученных соотношений следует равенство \[ P (c_i | \mathcal{D}_{Yes}) = P (c_i | X \le v) = \frac{N_{vi}}{\sum_{j=1}^kN_{vj}}. \] Тогда можно оценить \(P (X\gt v | c_i)\) \[ P (X\gt v | c_i) = 1 - P (X \le v | c_i) = 1 - \frac{N_{vi}}{n_i}=\frac{n_i-N_{vi}}{n_i}. \] Соответственно, \[ P (c_i | \mathcal{D}_{No}) = P (c_i | X \gt v) =\frac{P (X\gt v | c_i) P(c_i)}{\sum_{j=1}^kP(X>v|c_j)P(c_j)}= \frac{n_i-N_{vi}}{\sum_{j=1}^k(n_j-N_{vj})}. \]

Категориальные атрибуты.

Если \(X\) является категориальным атрибутом, то точки расщепления (сплит-точки) будут \(X \in V\), где \(V \subset dom (X)\) и \(V \neq \varnothing\). Так как точка \(X \in V\) дает то же разделение, что и \(X \in \bar{V}\), где \(\bar{V} = dom (X) \setminus V\) является дополнением к \(V\), то общее число различных разбиений растет в экспоненциальной зависимости от \(m\), где \(m = | dom (X) |\). Поэтому перебор возможных точек расщепления, если \(m\) велико, достаточно проблематичен.
Одно из упрощений состоит в том, чтобы ограничить \(V\). Ясно, что существует только \(m\) сплит-точек вида \(X_j \in \{v\}\), где \(v \in dom (X_j)\). Чтобы оценить заданную точку \(X \in V\), вычислим \[ P (c_i | \mathcal{D}_{Yes}) = P (c_i | X \in V), P (ci | \mathcal{D}_{No}) = P (c_i | X \notin V). \] Пользуясь теоремой Байеса, имеем \[ \frac{P (X \in V | c_i) P (c_i)}{P (X \in V)}=\frac{P (X \in V | c_i) P (c_i)}{\sum_{j=1}^kP (X \in V | c_j) P (c_j)}. \] Заметим, что данная точка \(\textbf{x}\) может принимать только одно значение из области \(X\), и, следовательно, значения \(v \in dom (X)\) являются взаимоисключающими. Поэтому \[ P (X \in V | c_i) = \sum_{v\in V}P(X=v|c_i) \] и мы можем переписать \(P (c_i | \mathcal{D}_{Yes})\) \[ P (c_i | \mathcal{D}_{Yes})=\frac{ \sum_{v\in V}P(X=v|c_i)P(c_i)}{\sum_{j=1}^k\sum_{v\in V}P(X=v|c_j)P(c_j)}. \] Пусть \(n_{vi}\) число точек \(\textbf{x}_j\in \mathcal{D}\), со значением \(x_j = v\) для атрибута X и класса \(u_j = c_i\) \[ n_{vi} =\sum_{j=1}^nI (x_j = v \& u_j = c_i), \] и \[ P (X = v | c_i) = \frac{P (X = v\& c_i)}{P(c_i)}=\frac{1}{n_i}\sum_{j=1}^nI (x_j = v \& u_j = c_i)=\frac{n_{vi}}{n_{i}}. \] Заметим, что \(P (c_i) = n_i / n\). Таким образом, класс для разбиения \(\mathcal{D}_{Yes}\) точкой \(X \in V\) задается так \[ P (c_i | \mathcal{D}_{Yes}) =\frac{\sum_{v\in V}P(X=v|c_i)P(c_i)}{\sum_{j=1}^k\sum_{v\in V}P(X=v|c_j)P(c_j)}= \frac{\sum_{v\in V}n_{vi}}{\sum_{j=1}^k\sum_{v\in V}n_{vj}}. \] Аналогичным образом для \(\mathcal{D}_{No}\) получаем \[ P (c_i | \mathcal{D}_{No}) =P(c_i|X\notin V)=\frac{\sum_{v\notin V}n_{vi}}{\sum_{j=1}^k\sum_{v\notin V}n_{vj}}. \]

Пример использования дерева квалификации.

Предположим, что некоторое предприятие владеет акциями стоимостью 1000 USD (заметим, что данные можно изменить и посмотреть как изменится результат).
Существует три варианта решений:

- Дополнительно купить акции на сумму 500 USD.
- Держать акции без движения.
- Продать акции.

Вероятность роста курса акции на 20% составляет P1 = 0.6, а вероятность снижения курсовой стоимости P2 = 0.4.

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

Проведем анализ возможных решений.
В случае дополнительной покупки акций имеем:
   P1: 1000 + 500 + 0.2 * 1500 = 1800 USD;
   P2: 1000 + 500 - 0.2 * 1500 = 1200 USD;
В случае дальнейшего хранения акций имеем:
   P1: 1000 + 0.2 * 1000 = 1200 USD;
   P2: 1000 - 0.2 * 1000 = 800 USD;
Ожидаемое значение в вершине А составляет:
0.6 * 1800 + 0.4 * 1200 = 1560 USD;
Ожидаемое значение в вершине B составляет:
  0.6 * 1200 + 0.4 * 800 = 1040 USD;
Прибыль при различных вариантах стратегий имеет следующие размеры:
Вариант 1 (купить дополнительные акции):
П1 = 1560 - 500 = 1060 USD;
Вариант 2 (продать все акции):
П2 = 0 + 1000 = 1000 USD;
Вариант 3 (продолжать держать все акции):
П3 = 1040 + 0 = 1040 USD;
Итак, на основании метода дерева решений, оптимальным вариантом является покупка дополнительных акций, которая приводит к максимально возможной прибыли в 1060 USD;

Существует достаточно много алгоритмов, реализующих деревья решений, среди которых наиболее популярны алгоритмы CART и ID3 (с его расширением C4.5), на которых мы и остановимся.

Пример построения дерева решения по алгоритму ID3 и его расширению C4.5.

Берег/Лодка	Удочка/Спиннинг	Ветрено/Тихо	Дождь/Сухо	Улов
Б	У	Т	Д	Нет
Б	У	В	С	Да
Б	У	Т	С	Да
Л	С	В	С	Нет
Л	У	В	С	Да
Б	С	Т	Д	Нет
Л	У	В	Д	Да
Л	С	Т	С	?

Берег/Лодка	Ветрено/Тихо	Дождь/Сухо	Улов
Б	Т	Д	Нет
Б	В	С	Да
Б	Т	С	Да
Л	В	С	Да
Л	В	Д	Да

Берег/Лодка	Дождь/Сухо	Улов
Б	Д	Нет
Б	С	Да

Берег/Лодка	Удочка/Спиннинг	Ветрено/Тихо	Дождь/Сухо	Температура	Улов
Б	У	Т	Д	22	Нет
Б	У	В	С	24	Да
Б	У	Т	С	22	Да
Л	С	В	С	20	Нет
Л	У	В	С	22	Да
Б	С	Т	Д	26	Нет
Л	У	В	Д	20	Да
Л	С	Т	С	18	Да

	18	20	22	24	26
Интервал	≤	>	≤	>	≤	>	≤	>	≤	>
Да	1	4	2	3	4	1	5	0	5	0
Нет	0	3	1	2	2	1	2	1	3	0
Entropy
Info
Gain

С другой стороны, введение нечетких множеств и нечеткой логики (Zadeh, 1965) позволило получить общую методологию, позволяющую рассматривать понятия неопределенности и неточности. Деревья принятия решений на основе теории нечетких множеств объединяют преимущества деревьев решений и способность нечеткого представления обрабатывать неточные и неопределенные данные.
Однако, если отличительной чертой деревьев решений является тот факт, что каждый пример обучающей выборки принадлежит конкретному узлу дерева, то в нечетком случае это не так. Для каждого атрибута необходимо выделить несколько его лингвистических значений и определить степени принадлежности к ним примеров обучающей выборки. Вместо количества примеров конкретного узла нечеткое дерево решений группирует их степень принадлежности. Коэффициент – это соотношение примеров \(D_j\in S^N\) узла \(N\) для целевого значения \(i\), вычисляемый следующим образом: \begin{equation}\label{f:1} P^N_i=\sum_{S^N}\min\left\{\mu_N(D_j),\mu_i(D_j)\right\}, \end{equation} где \(\mu_N(D_j)\)– степень принадлежности примера \(D_j\) к узлу \(N\), \(\mu_i(D_j)\)– степень принадлежности примера относительно целевого значения \(i\), \(S^N\) – множество всех примеров узла \(N\). Таким образом, атрибуты присваиваются узлам на основе самого низкого уровня неопределенности классификации.
Следующим шагом будет определение коэффициента \(P^N\), который отвечает за общие характеристики примеров узла \(N\). В стандартном алгоритме дерева решений определяется отношение числа примеров, принадлежащих конкретному атрибуту, к общему числу примеров. Для нечетких деревьев используется отношение \(P_i^N/P^N\), для расчета которого учитывается степень принадлежности.
Выражение \begin{equation}\label{f:2} E\left(S^N\right)=-\sum_{i}\frac{P^N_i}{P^N}\times \log_2\frac{P^N_i}{P^N} \end{equation} даёт оценку среднего количества информации для определения класса объекта из множества \(P^N\).
На следующем шаге построения нечеткого дерева решений находим значение энтропии для разбиения по атрибуту \(A\) со значениями \(a_j\): \begin{equation}\label{f:3} E\left(S^N,A\right)=\sum_{j}\frac{P^{N|j}}{P^N}E\left(S^{N|j}\right) \end{equation} где узел \(N|j\) – дочерний для узла \(N\).
Процесс построения дерева начинается с нахождения атрибута условия, который определяет корневой узел (далее этот процесс повторяется итерационно). Для этого необходимо рассчитать классификационную неоднозначность каждого атрибута условия. Определение классификационной неоднозначности по нечеткому разбиению сводится к выбору атрибута \(A^\times\) с максимальным приростом информации: \begin{equation}\label{f:4} G\left(S^N,A\right)=E\left(S^N\right)-E\left(S^N,A\right), A^\times=arg \max_A G\left(S,A\right) \end{equation} Узел \(N\) разбивается на несколько подузлов \(N|j\). Степень принадлежности примера \(D_k\) узла \(N|j\) вычисляется пошагово из узла \(N\) следующим образом \begin{equation}\label{f:6} \mu_{N|j}(e_k)=\min\left\{\mu_{N|j}(D_k),\mu_{N|j}(D_k,a_j)\right\}, \end{equation} где \(\mu_{N|j}(D_k,a_j)\) показывает степень принадлежности \(D_k\) к атрибуту \(a_j\).
Подузел \(N|j\) удаляется, если все примеры в нем имеют степень принадлежности равную нулю. Алгоритм повторяется до тех пор, пока все примеры узла не будут классифицированы, либо пока не будут использованы все атрибуты.
Принадлежность к целевому классу для новой записи находится из равенства \begin{equation}\label{f:7} \sigma_j=\frac{\sum_i\sum_kP^i_k\mu_i(D_j)\chi_k}{\sum_i\left(\mu_i(D_j)\sum_kP^i_k\right)} \end{equation} здесь

\(P^i_k\) – коэффициент соотношения примеров листа дерева \(\ell\) для значения целевого класса k,
\(\mu_i(D_j)\) – степень принадлежности примера к узлу \(\ell\),
\(\chi_k\) – принадлежность значения целевого класса \(k\) к положительному (или отрицательному) значению исхода классификации.

Пример построения нечеткого дерева решения.

Пример использования нечетких деревьев решений

Обучающая выборка.

Функции принадлежности

Новые данные

№	Квалификация	Зарплата	Рейтинг
	\(d_0\)	\(d_1\)	\(d_2\)
0	0	9	0
1	1	16	0
2	4	22	0.1
3	4.5	27	0.3
4	6	17	0.7
5	7.7	28	0.9
6	9	50	1

	Квалификация	Зарплата
№	Начинающий	Специалист	Эксперт	Низкая	Средняя	Высокая
0	1	0	0	0.5	0.5	0
1	1	0	0	0	1	0
2	0.5	0.5	0	0	0.8	0.2
3	0.25	0.75	0	0	0.3	0.7
4	0	1	0	0	1	0
5	0	0.3	0.7	0	0.2	0.8
6	0	1	0	0	0	1
\(\Sigma\)	2.75	2.55	1.7	0.5	3.8	2.7

	Начинающий	Специалист	Эксперт
\(P_{да}\)	0.35	1.4	1.7
\(P_{нет}\)	2.75	1.6	0.1
Энтропия	0.509	0.997	0.31

	Низкая	Средняя	Высокая
\(P_{да}\)	0	1.3	2.2
\(P_{нет}\)	0.5	3	1
Энтропия	0	0.884	0.896

Квалификация	Начинающий	Эксперт	Специалист
Зарплата	Низкая	Средняя	Высокая	Низкая	Средняя	Высокая	Низкая	Средняя	Высокая
0	0.5	0.5	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0
2	0	0.5	0.2	0	0.5	0.2	0	0	0
3	0	0.25	0.25	0	0.3	0.7	0	0	0
4	0	0	0	0	1	0	0	0	0
5	0	0	0	0	0.2	0.3	0	0.2	0.7
6	0	0	0	0	0	0	0	0	1

	Начинающий	Специалист	Эксперт
Низкая	0/0.5	0/0	0/0
Средняя	0.35/2.25	1.3/1.2	0.2/0.1
Высокая	0.35/0.45	0.7/1	1.7/0.1

Задачи для самостоятельной работы.

Задача 1.

Руководство ГП «Антонов» при производстве перспективной модели самолета пытается решить, покупать или производить некоторую деталь.
При покупке деталь стоила бы 1,50 долларов США за штуку. Если спроектировать и произвести эту деталь самостоятельно, это приведет к стоимости 0,75 долларов США за штуку. Проектные инвестиции составят 50 000 долларов США. Кроме того, есть 30% вероятность того, что необходимо будет вложить дополнительные инвестиции в размере 50 000 долл. США.
В любом случае для производства ГП «Антонов» потребуется 100 000 этих частей.

Используя анализ деревьев решений, решить проблему для ГП «Антонов».

Задача 2.

У инвестора на счете было 2 000 000 долларов и он хочет инвестировать эти деньги в сельское хозяйство.
У него была идея инвестиционного плана на 1 месяц, 3 месяца, 6 месяцев и 1 год соответственно.

инвестировать 27% средств на план 3 месяца,
24% - на план на 6 месяцев,
21% на годовой план и
28% на месячный план.

У инвестора есть желание получить как минимум 20% прибыли от любого из этих инвестиционных планов.
Риски достижения этой цели - 94% для первого плана, 96% для второго, 97% для третьего и 98% для четвертого.

Постройте дерево решений и сообщите инвестору о соответствующем инвестиционном плане.

Задача 3.

Автомобильная компания планирует выпуск новой модели джипов. Руководители компании оценивают две альтернативы.

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

Jeep - новая модель для рынка, продажи трудно предсказать. Однако компания прогнозирует, что около 60%, что продажи могут составлять 100 000 единиц в год, и 40% - продажи на 150000 единиц в год. Выручка от продажи одного автомобиля составляет 30000 долларов США.
Себестоимость производства для обеих альтернатив производства зависит от уровня продаж. Себестоимость одного автомобиля на существующем заводе в городе Х, при среднем объеме продаж, составляет 16 000 долларов США и при максимальном, 24 000 долларов США.
Новый завод в городе Y, при среднем объеме продаж обеспечивает себестоимость в размере 22 000 долларов США, при максимальном спросе, в размере 20000 долларов США.
Постоянные годовые издержки для нового завода (включая постоянно снижающиеся расходы на новое строительство), составляют 400 миллионов долларов независимо от уровня продаж. В то время как постоянные годовые затраты на существующий завод, не зависимо от объема продаж, составляют 300 миллионов долларов.

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

Задача 4.

Джеки Чанг является владельцем небольшой компании по производству электроники. В течении шести месяцев ожидается предложение о создании электронной системы синхронизации для будущих Олимпийских игр.
На протяжении нескольких лет компания Chang Electronic разрабатывает новый микропроцессор, который является важнейшим компонентом в системе синхронизации, который будет превосходить любой продукт, который в настоящее время присутствует на рынке. Тем не менее, прогресс в исследованиях и разработках был медленным, и Чанг не уверен, сможет ли персонал компании своевременно произвести микропроцессор.
Если им удастся завершить работу над новым микропроцессором (вероятность 0.6), есть отличная вероятность (вероятность 0.8), что компания Чанга выиграет олимпийский контракт на 1 миллион долларов.
Если они этого не сделают, есть небольшой шанс (вероятность 0.2), что компания все равно сможет выиграть тот же контракт с альтернативной, но более ранней системой синхронизации, которая уже была разработана.
Если компания продолжит проект, Чанг должен инвестировать 200 000 долларов в исследования и разработки. Кроме того, ( если R&D (НИОКР) проходят успешно), требуется разработка прототипа системы синхронизации за дополнительную плату. Эта дополнительная стоимость составляет 50 000 долл. США, если R & D будет успешным (чтобы она могла разработать новую систему синхронизации), и это 40 000 долл. США, если НИОКР не увенчались успехом (так что компании нужно выходить с более старой системой синхронизации).
Наконец, если Chang Electronic выиграет контракт, то для производства готового продукта нужно дополнительно вложить 150 000 долларов США.

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

Задача 5.

В таблице приведены данные по концентрации уксусной кислоты, H2S и молочной кислоты в 30 образцах зрелого сыра чеддер. Кроме того, предоставляется субъективная ценность вкуса.

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

Задача 6.

По известным материалам кредитования физических лиц получить рекомендуемое решение

Товар	Стаж кредитной истории (в годах)	Размер кредита (тыс. UAH)	Аванс (тыс. UAH)	Срок кредитования (в годах)	Месячный доход плательщика (тыс UAH)	Возраст плательщика (в годах)	Принятое решение
Дом	10	5000000	3000000	10	50000	32	Да
Автомобиль	2	200000	80000	1	15000	50	Да
Автомобиль	6	350000	150000	5	8000	55	Нет
Квартира	5	2000000	1000000	20	12000	36	Да
Автомобиль	1	375000	203000	5	7000	60	Нет
Квартира	12	1000000	300000	5	25000	45	Да
Дом	20	4000000	2000000	2	30000	65	Нет
Автомобиль	12	200000	120000	1	35000	62	Да
Квартира	8	800000	300000	4	20000	36	Да
Автомобиль	11	500000	150000	10	18000	30	Да
Квартира	10	800000	150000	5	17000	40	Нет
Автомобиль	7	500000	100000	3	25000	52	?

Decision trees