Алгоритм заключается в построении деревьев решений для каждого класса по отдельности. На каждом этапе генерируется проверка узла дерева, который покрывает несколько объектов обучающей выборки.
На каждом шаге алгоритма выбирается значение переменной, которое разделяет множество на два подмножества. Разделение должно выполняться так, чтобы все объекты класса, для которого строится дерево, принадлежали одному подмножеству. Такое разбиение производится до тех пор, пока не будет построено подмножество, содержащее только объекты одного класса.
Для выбора независимой переменной и её значения, которое разделяет множество, выполняются следующие действия:
Из построенного на предыдущем этапе подмножества (для первого этапа это вся обучающая выборка), включающего объекты, относящиеся к выбранному классу для каждой независимой переменной, выбираются все значения, встречающиеся в этом подмножестве.
Для каждого значения каждой переменной подсчитывается количество объектов, удовлетворяющих этому условию и относящихся к выбранному классу.
Выбираются условия, покрывающие наибольшее количество объектов выбранного класса.
Выбранное условие является условием разбиения подмножества на два новых.
После построения дерева для одного класса таким же образом строятся деревья для других классов.
Преимущества использования деревьев решений:
- — быстрый процесс обучения;
- — генерация правил в областях, где эксперту трудно формализовать свои знания;
- — извлечение правил на естественном языке;
- — интуитивно понятная классификационная модель;
- — высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети).
