Алгоритм покрытия

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

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

После построения дерева для одного класса таким же образом строятся деревья для других классов.

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

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

Области применения деревьев решений

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

Деревья решений успешно применяются для решения практических задач в следующих областях:

• Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
• Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т.д.
• Медицина. Диагностика различных заболеваний.
• Молекулярная биология. Анализ строения аминокислот.