Вимоги до даних

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

Інформація про об'єкти, які необхідно класифікувати, повинна бути представлена у вигляді кінцевого набору ознак (атрибутів), кожен з яких має дискретне або числове значення. Такий набір атрибутів назвемо прикладом. Для всіх прикладів кількість атрибутів і їх склад мають бути постійними.

Безліч класів, на які будуть розбиватися приклади, повинно мати кінцеве число елементів, а кожен приклад має однозначно ставитися до конкретного класу. Для випадків з нечіткою логікою, коли приклади належать до класу із певною ймовірністю, C4.5 непридатний.

У навчальній вибірці кількість прикладів повинна бути значно більше кількості класів, до того ж кожен приклад має бути заздалегідь асоційований зі своїм класом. З цієї причини C4.5 є варіантом машинного навчання з учителем.

Побудова дерева

Нехай є Т – навчальна вибірка прикладів, а С – множина класів, що складається з k - елементів. Для кожного прикладу з T відома його приналежність до якогось із класів C1…Ck

Побудова дерева рішень алгоритмом C4.5 принципово не відрізняється від його побудови в ID3. На першому кроці є корінь і асоційована з ним множина Т, яку необхідно розбити на підмножини. Для цього необхідно вибрати один з атрибутів в якості перевірки.

Обраний атрибут А має n значень, що дає розбиття на n підмножин. Далі створюються n нащадків кореня, кожному з яких поставлено у відповідність своя підмножина, отримана при розбитті Т. Процедура вибору атрибута і розбиття по ньому рекурсивно застосовується до всіх n нащадків і зупиняється в двох випадках:

після чергового розгалуження в вершині опиняються приклади з одного класу (тоді вона стає листом, а клас, якому належать її приклади, буде рішенням аркуша),

вершина виявилася асоційованою з порожньою множиною (тоді вона стає листом, а в якості рішення вибирається клас,який найбільш часто зустрічається у безпосереднього предка цієї вершини).

Застосування дерев рішень для задач класифікації