Loading AI tools
Из Википедии, свободной энциклопедии
C4.5 — алгоритм для построения деревьев решений, разработанный Джоном Квинланом (англ. John Ross Quinlan). C4.5 является усовершенствованной версией алгоритма ID3 того же автора. В частности, в новую версию были добавлены отсечение ветвей (англ. pruning), возможность работы с числовыми атрибутами, а также возможность построения дерева из неполной обучающей выборки, в которой отсутствуют значения некоторых атрибутов.
Для того, чтобы с помощью C4.5 построить решающее дерево и применять его, данные должны удовлетворять нескольким условиям.
Информация об объектах, которые необходимо классифицировать, должна быть представлена в виде конечного набора признаков (атрибутов), каждый из которых имеет дискретное или числовое значение. Такой набор атрибутов назовём примером. Для всех примеров количество атрибутов и их состав должны быть постоянными.
Множество классов, на которые будут разбиваться примеры, должно иметь конечное число элементов, а каждый пример должен однозначно относиться к конкретному классу. Для случаев с нечёткой логикой, когда примеры принадлежат к классу с некоторой вероятностью, C4.5 неприменим.
В обучающей выборке количество примеров должно быть значительно больше количества классов, к тому же каждый пример должен быть заранее ассоциирован со своим классом. По этой причине C4.5 является вариантом машинного обучения с учителем.
Пусть имеется — обучающая выборка примеров, а — множество классов, состоящее из элементов. Для каждого примера из известна его принадлежность к какому-либо из классов .
Построение дерева решений алгоритмом C4.5 принципиально не отличается от его построения в ID3. На первом шаге имеется корень и ассоциированное с ним множество , которое необходимо разбить на подмножества. Для этого необходимо выбрать один из атрибутов в качестве проверки. Выбранный атрибут имеет значений, что даёт разбиение на подмножеств. Далее создаются потомков корня, каждому из которых поставлено в соответствие своё подмножество, полученное при разбиении . Процедура выбора атрибута и разбиения по нему рекурсивно применяется ко всем потомкам и останавливается в двух случаях:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.