Теория принятия решений

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

30

Теория принятия решений

1. Предпочтение и полезность

Теория предпочтения базируется на понятии бинарного отношения. Бинарное отношение R на непустом множестве X есть подмножество множества всех упорядоченных пар элементов из X. Множество упорядоченных пар задается декартовым произведением X * X = {(x, y)/ x X, y Y}. Запись xRy означает, что пара (x, y) R X*X, означает

Для бинарных отношений устанавливаются следующие свойства:

1. Рефлексивность. Если xRx для каждого x X; нерефликсивность: для каждого x X.

2. Симметричность, если из xRy следует yRx. Ассиметричность, если из xRy следует

3. Транзитивность, если из xRy и yRz следует xRz. Отрицательная транзитивность: если из и следует .

4. Связность, если xRy или yRx (полная); слабая: если из x y следует xRy или yRx.

В теории предпочтений используется два основных бинарных отношения на множестве X:

1. Отношение нестрогого предпочтения (x y; x либо предпочтительнее y, либо безразлично к x; y не предпочтительнее x).

2. Отношение предпочтения ( x предпочтительнее y).

Отношения предпочтения и безразличия могут быть определены через нестрогое предпочтение следующим образом:

т. и т.т. к. и неверно, что .

xy т. и т. т. к. xy и yx.

Если за основу берется отношение , тогда и можно определить:

xy тогда и только тогда, когда неверно xy и yx.

xy тогда и только тогда, когда xy, или неверно xy и неверно yx.

Для отношения целесообразно предположить, что оно ассиметрично. Для отношения - связность. Из ассиметричности отношения следует, что отношение безразличия рефлексивно (xx) и симметрично по определению. Отношение предпочтения на X транзитивно, если из того, что xy, и yz следует, что xz. Однако, это может быть не всегда.

Для того, чтобы работать с предпочтением вводится специальная вещественная функция u, определенная на X, которая называется функцией полезности для отношения предпочтения на X, если u(x)>u(y) для любого x и y, таких что xy и называется совершенной функцией полезности для отношения на X, если для всех x и y справедливо неравенство u(x)>u(y) тогда и только тогда, когда xy.

1.1 Data Mining

Data Mining - это процесс обнаружения в данных:

1. Ранее неизвестных

2. Нетривиальных

3. Практически полезных

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

Обычно выделяют пять стандартных типов закономерностей, которые позволяют определять методы Data Mining:

1. Ассоциация.

2. Последовательность

3. Классификация.

4. Кластеризация

5. Прогнозирование

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

Обычно выделяют восемь классов систем Data Mining:

1. Предметно-ориентированные системы. Ориентированы на предметную область. Обычно минимально используют математический аппарат (300 - 1000$).

2. Деревья решений (1000-10000$).

3. Статистические методы. Включают корреляционный, дисперсионный, регрессионный, факторный и т.д. анализ (Statistica) (1000 - 15000$).

4. Нейронные сети (1500 - 8000$).

5. Системы рассуждений на основе аналогий или метода ближайшего соседа.

6. Эволюционное программирование. В таких системах гипотезы о виде зависимости целевой переменной от других переменных строится как эволюция в мире программ. Когда система находит программу более или менее удовлетворяющую искомой зависимости, она начинает вносить в нее небольшие изменения и отбирает среди построенных дочерних программ, те которые повышают точность (до 5000).

7. Генетические алгоритмы (около 10000)

8. Алгоритмы ограниченного перебора. Эти алгоритмы вычисляют частоты простых логических событий в подгруппах данных (около 4000$).

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

На рис. № графически представлена задача принятия решений в виде дерева решений.

Двигаясь по дереву решений сверху вниз, лицо, принимающее решение, должно сначала либо выбрать эксперимент стоимостью , либо не проводить экспериментов, что обозначается через , а соответствующие затраты (нулевые) - через . При условии выбора данного эксперимента наблюдается исход . Эксперимент приводит к различным исходам, вероятности появления которых описываются с помощью распределения условных вероятностей . Если исход известен, должно быть выбрано следующее решение . После такого выбора наличие внешних условий задается распределением условных вероятностей , где индекс r относится к эксперименту, t обозначает исход, а i - решение. В результате всех этих шагов получается исход x. Вероятность различных исходов численно выражается через распределение условных вероятностей , где индекс j относится к внешним условиям. Относительная предпочтительность возможных исходов задается функцией полезности .

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

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

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

.

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

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

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

.

Пусть выбран эксперимент и реализовался исход ; тогда оптимальное решение определяется с помощью выражения:

.

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

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

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

предпочтениями, отдаваемыми им различным возможным исходам.

Чтобы учесть оба фактора потребуется представить в виде цифр а) суждения о возможных последствиях (опираясь на понятие субъективной вероятности) и б) высказывания о предпочтениях (используя теорию полезности).

Алгоритм CLS

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

Рассмотрим следующий пример. Проводится антропологический анализ лиц людей двух национальностей по 16 признакам.

Х1 (голова) - круглая - 1, овальная - 0.

Х2 (уши) - оттопыренные - 1, прижатые - 0.

Х3 (нос) - круглый -1, длинный - 0.

Х4 (глаза) - круглые - 1, узкие - 0.

Х5 (лоб) - с морщинами -1, без морщин - 0.

Х6(носогубная складка) - есть - 1, нет - 0.

Х7(губы) - толстые - 1, тонкие - 0.

Х8 (волосы) - есть - 1, нет -...