Алгоритм C4.5 (Algorithm C4.5)

Разделы: Алгоритмы

Алгоритм построения деревьев решений, являющийся улучшенной модификацией алгоритма ID3. Так же, как и ID3, алгоритм С4.5 использует критерий информационной энтропии, или прироста информации (information gain). Обучающий набор данных для алгоритма C4.5 представляет собой множество примеров , для которых предварительно задана метка класса. Каждый пример представляет собой p-мерный вектор значений атрибутов .

В каждом узле дерева решений производится выбор атрибута, который позволяет разбить множество попавших в него примеров на подмножества, максимально «чистые» по классовому составу. Чем однороднее полученные подмножества, тем больше их информация и меньше энтропия.

Следовательно, атрибут, выбираемый для разбиения в узле, должен обеспечивать максимальный прирост информации, или уменьшение энтропии, в результирующих подмножествах. Алгоритм рекурсивно продолжает процедуру разбиения до тех пор, пока в листьях не останутся примеры одного класса. Затем производится упрощение дерева решений путем отсечения ветвей.

Алгоритм С4.5 имеет следующие отличия от ID3:

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

Алгоритм С4.5 разработан Дж. Р. Куинленом (John Ross Quinlan), который является также автором алгоритма ID3.