C4.5

C4.5 — алгоритм для построения деревьев решений, разработанный Джоном Квинланом (Шаблон:Lang-en). C4.5 является усовершенствованной версией алгоритма ID3 того же автора. В частности, в новую версию были добавлены отсечение ветвей (Шаблон:Lang-en), возможность работы с числовыми атрибутами, а также возможность построения дерева из неполной обучающей выборки, в которой отсутствуют значения некоторых атрибутов.

Требования к данным

Для того, чтобы с помощью C4.5 построить решающее дерево и применять его, данные должны удовлетворять нескольким условиям.

Информация об объектах, которые необходимо классифицировать, должна быть представлена в виде конечного набора признаков (атрибутов), каждый из которых имеет дискретное или числовое значение. Такой набор атрибутов назовём примером. Для всех примеров количество атрибутов и их состав должны быть постоянными.

Множество классов, на которые будут разбиваться примеры, должно иметь конечное число элементов, а каждый пример должен однозначно относиться к конкретному классу. Для случаев с нечёткой логикой, когда примеры принадлежат к классу с некоторой вероятностью, C4.5 неприменим.

В обучающей выборке количество примеров должно быть значительно больше количества классов, к тому же каждый пример должен быть заранее ассоциирован со своим классом. По этой причине C4.5 является вариантом машинного обучения с учителем.

Построение дерева

Пусть имеется $T$ — обучающая выборка примеров, а $C$ — множество классов, состоящее из $k$ элементов. Для каждого примера из $T$ известна его принадлежность к какому-либо из классов $C_1\dots C_k$.

Построение дерева решений алгоритмом C4.5 принципиально не отличается от его построения в ID3. На первом шаге имеется корень и ассоциированное с ним множество $T$, которое необходимо разбить на подмножества. Для этого необходимо выбрать один из атрибутов в качестве проверки. Выбранный атрибут $A$ имеет $n$ значений, что даёт разбиение на $n$ подмножеств. Далее создаются $n$ потомков корня, каждому из которых поставлено в соответствие своё подмножество, полученное при разбиении $T$. Процедура выбора атрибута и разбиения по нему рекурсивно применяется ко всем $n$ потомкам и останавливается в двух случаях:

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

Реализации

• J48 — реализация на языке Java, входит в пакет Weka.
• C5.0 (для Linux) / See5 (для Windows) — реализация Квинлана на языке C.

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга Шаблон:Ref-en
• Шаблон:Статья

Ссылки

• Шаблон:Cite web