Алгоритм C4.5 для Data Mining

Алгоритм C4.5
Усовершенствование простого алгоритма индуцирования знаний.
Основнoе отличие: следующий условный атрибут, по которому проводится разбиение, определяется по критерию минимизации энтропии.
Теперь алгоритм не зависит от порядка следования атрибутов таблицы данных.

Общее описание
алгоритма C4.5
Алгоритм работает для таких таблиц данных, в которых атрибут класса (целевой атрибут) может иметь конечное множество значений.
Обозначения
T — множество примеров (таблица или подтаблица данных);
m — количество условных атрибутов
(столбцов таблицы)

Общее описание алгоритма C4.5 (продолжение)
Обозначения (продолжение)
|T | — мощность множества примеров (количество строк в таблице или подтаблице данных);
C1 , C2 , …, Ck — значения, принима-емые атрибутом класса;
X — текущий условный атрибут, по
которому мы хотим провести разбиение

Общее описание алгоритма C4.5 (окончание)
Обозначения (окончание)
A1 , A2 , …, AN — значения, принима-емые текущим условным атрибутом;

Выбор условного атрибута для разбиения
Пусть рассматриваем условный атрибут X, принимающий n значений A1, A2 ... An. Тогда разбиение множества (таблицы) T по атрибуту X даст нам подмножества (подтаблицы) T1, T2 ... Tn.
Пусть freq(Cj,T ) — количество примеров из множества T, в которых атрибут класса равен Cj

Выбор условного атрибута для разбиения (продолжение)
Тогда вероятность того, что случайно выбранная строка из таблицы T будет принадлежать классу Cj, равна
Например, вероятность того, что прибыль будет расти, составляет P = 5 / 10 = 0,5

Выбор условного атрибута для разбиения (продолжение)
Согласно теории информации, количество содержащейся в сообщении информации зависит от её вероятности log2(1/P).
Количество информации измеряется в битах.

Выбор условного атрибута для разбиения (продолжение)
Энтропия таблицы T, то есть среднее количество информации, необходимое для определения класса, к которому относится строка из таблицы T:

Выбор условного атрибута для разбиения (продолжение)
Энтропия таблицы T после её разбиения по атрибуту X на n подтаблиц:

Выбор условного атрибута для разбиения (окончание)
Критерий для выбора атрибута X – следующего атрибута для разбиения: