2015-02-04
2978
Дерево решений – это графическое изображение процесса принятия решений, в котором отражены альтернативные решения и состояния среды, соответствующие вероятности и выигрыши для любых комбинаций альтернатив и состояний среды.
Деревья решений - один из методов автоматического анализа данных, основные идеи которого восходят к работам П. Ховленда (Р. Hoveland) и Е. Ханта (Е. Hunt) конца 50-х годов XX в.
Дерево решений применяют, когда нужно принять несколько решений в условиях неопределенности, когда каждое решение зависит от исхода предыдущего решения или исходов испытания. Такое представление облегчает описание процесса принятия решений. Но деревья решений, реализуя только последовательный перебор признаков, принципиально не могут находить «лучшие» (наиболее полные, особенно, многокритериальные оптимальные и т.п.) решения.
Для генерации различных вариантов решений и их оценки наибольшее распространение получили деревья решений, содержащие два типа вершин: вершины, в которых решение принимает эксперт (ЛПР) и вершины, где решение принимает «случай», выходящие из вершины дуги задают определенные вероятности направлений принятия решения.
Все задачи, решаемые с помощью деревьев решений, могут быть сведены к следующим трем типам:
1. описание данных, содержащее их характеристику;
2. классификация, т.е. отнесение объекта к одному из заранее известных классов;
3. регрессия, устанавливающая зависимость целевой переменной от независимых (входных) данных.
В случаях когда алгоритмы построения деревьев решений дают сложные деревья (переполненные данными, имеют много узлов и ветвей, в которых трудно разобраться) бывает удобнее разбить дерево на несколько деревьев решений.
Деревья решений поддержаны следующими программными комплексами:
1. система MiniSet содержит визуализатор деревьев (TreeVisualizer) и визуализатор правил (Rule Visualizer);
2. специально для работы с деревьями решений созданы программные системы Clementine (Integral Solution, Великобритания), SIPINA (Лионский университет, Франция) и др.;
3. программа SuperTree.
Правила построения дерева решений:
1. Рисуют деревья слева направо.
2. Деревья решений состоят из вершин (круги, квадраты и треугольники) и ветвей (линии). Места, где принимают решения, будем обозначать квадратами. Места появления исходов – кругами. Возможные решения – пунктирными линиями. Возможные исходы – сплошными линиями.
3. Вершины соответствуют определенным моментам времени. Вершины-решения (квадраты) соответствуют моментам времени, когда лицо, принимающее решение, (ЛПР) принимает решение. Вершины-вероятности (круги) соответствуют моментам времени, когда разрешается одна из неопределенностей. Конечные вершины (треугольники) соответствуют окончанию задачи, когда все решения приняты, все неопределенности разрешились и все платежи произошли.
4. Ветви, идущие из вершин-решений, соответствуют различным возможным решениям. Ветви, идущие из вершин-вероятностей, соответствуют различным возможным вариантам разрешения неопределенности и не являются объектом чьего-либо управления.
5. Вероятности соответствуют ветвям, исходящим из вершин вероятностей. Сумма вероятностей по всем ветвям, исходящим из одной вершины, равна 1;
6. Каждой конечной вершине соответствуют два числовых значения. Первое – это вероятность прихода в данную конечную вершину и второе – значение платежа, соответствующее данному сценарию развития событий.
7. Для каждой альтернативы считается ожидаемая стоимостная оценка – максимальная из сумм оценок выигрышей, умноженная на вероятность реализации выигрышей для всех возможных вариантов (EMV).
Деревья решений являются прекрасным инструментом в системах поддержки принятия решений, интеллектуального анализа данных (data mining).
Области применения деревьев решений для решения практических задач:
1. Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
2. Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т.д.
3. Медицина. Диагностика различных заболеваний.
4. Молекулярная биология и т.д.
