Алгоритм C4.5

Представляет собой усовершенствованный вариант алгоритма ID3. Среди улучшений стоит отметить следующие:

Возможность работать не только с категориальными атрибутами, но также с числовыми. Для этого алгоритм разбивает область значений независимой переменной на несколько интервалов и делит исходное множество на подмножества в соответствии с тем интервалом, в который попадает значение зависимой переменной.
После построения дерева происходит усечение его ветвей. Если получившееся дерево слишком велико, выполняется либо группировка нескольких узлов в один лист, либо замещение узла дерева нижележащим поддеревом. Перед операцией над деревом вычисляется ошибка правила классификации, содержащегося в рассматриваемом узле. Если после замещения (или группировки) ошибка не возрастает (и не сильно увеличивается энтропия), значит замену можно произвести без ущерба для построенной модели.

Один из недостатков алгоритма ID3 является то, что он некорректно работает с атрибутами, имеющими уникальные значения для всех объектов из обучающей выборки. Для таких объектов информационная энтропия равна нулю и никаких новых данных от построенного дерева по данной зависимой переменной получить не удасться. Поскольку получаемые после разбиения подмножества буду содержать по одному объекту.
Алгоритм C4.5 решает эту проблему путём введения нормализации.
Оценивается не количество объектов того или иного класса после разбиения, а число подмножеств и их мощность (число элементов).
Выражение оценивает потенциальную информацию, получаемую при разбиении множества Т на m подмножеств.
Критерием выбора переменной для разбиения будет выражение: или .
При условии, что имеется k классов и n - число объектов в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен log₂k, а знаменатель максимально равен log₂n. Если предположить, что количество объектов знаведомо больше количества классов, то знаменатель растёт быстрее, чем числитель и, соответственно, значение выражения будет небольшим.
В обучающей выборке могут присутствовать объекты с пропущенными значениями атрибутов. В этом случае их либо отбрасывают (что влечёт за собой риск потерять часть данных), либо применить подход, предполагающий, что пропущенные значения по переменной вероятностно распределены пропорционально частоте появления существующих значений.