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

C4.5 — це алгоритм, розроблений Росом Куінланом^[en], який використовується для генерації дерев рішень у машинному навчанні^[1]. C4.5 є розширенням ID3 — попереднього алгоритму Куінлана. Дерева рішень, сформовані за допомогою C4.5, можуть бути використані для класифікації, та саме цьому C4.5 часто називають статистичним класифікатором.

Алгоритм став досить популярним після того, як він зайняв перше місце у видатній статті Top 10 Algorithms in Data Mining, яка була опублікована компанією Springer LNCS^[en] у 2008 році^[2].

Алгоритм

C4.5 будує дерева рішень з набору навчальних даних так само, як ID3, використовуючи концепцію інформаційної ентропії. Навчальні дані — це набір ${\displaystyle S={s_{1},s_{2},...}}$ вже класифікованих зразків. Кожний зразок ${\displaystyle s_{i}}$ складається з p-мірного вектора ${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$, де ${\displaystyle x_{j}}$ представляють значення атрибутів або ознаки зразків, а також клас, до якого належить ${\displaystyle s_{i}}$.

На кожному вузлі дерева C4.5 вибирає атрибут даних, який найбільш ефективно розбиває свій набір зразків на підмножини, які належать до одного класу або до іншого. Критерієм розбиття є нормалізований інформаційний приріст^[en] (тобто різниця ентропії). Атрибут з найбільшим нормалізованим інформаційним приростом вибирається для прийняття рішення. Потім алгоритм C4.5 повторюється на розбитих підмножинах.

Цей алгоритм має декілька базових випадків.

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

Псевдокод

У псевдокоді загальний алгоритм побудови дерев рішень має такий вигляд^[3]:

1. Перевірити наявність вищезазначених базових випадків.
2. Для кожного атрибута ${\displaystyle a}$ знайти коефіцієнт нормалізованого інформаційного приросту від розбиття множини за цим атрибутом.
3. Нехай ${\displaystyle a_{best}}$ — атрибут з найбільшим нормалізованим інформаційним приростом.
4. Створити вузол рішення ${\displaystyle node}$, який розбиває множину за ${\displaystyle a_{best}}$.
5. Повторити на підсписках, які були отримані розбиттям за ${\displaystyle a_{best}}$, та додати ці вузли у якості дітей ${\displaystyle node}$.

Реалізації

J48 — це реалізація алгоритму C4.5 з відкритим вихідним кодом на мові програмування Java у інструменті для добування даних Weka.

Покращення алгоритму ID3

Докладніше: ID3 (алгоритм)

C4.5 зробив ряд удосконалень алгоритму ID3:

• Обробка як неперервних, так і дискретних атрибутів. Для того, щоб обробляти неперервні атрибути, C4.5 створює поріг, а потім розбиває набір даних на ті елементи, чиє значення атрибута перевищує поріг, і ті, які менше або дорівнюють йому^[4].
• Обробка навчальних даних з відсутніми значеннями атрибутів. У C4.5 атрибути можуть помічатись як ${\displaystyle$ ?} у разі, якщо значення відсутнє. Відсутнє значення атрибутів просто не використовується в обчисленнях коефіцієнтів приросту та ентропії.
• Обробка атрибутів з різними витратами.
• Обрізання дерев. Після створення дерева C4.5 повертається назад і намагається видалити гілки, які не допомагають приймати рішення, замінюючи їх на листові вузли.

Алгоритми C5.0 та See5

Куінлан надалі розробив C5.0 та See5 (C5.0 для Unix/Linux, See5 для Windows), які він розповсюджує на комерційній основі. C5.0 пропонує ряд покращень до C4.5. Серед них^[5][6]:

• Швидкість: C5.0 значно швидше, ніж C4.5 (на декілька порядків).
• Використання пам'яті: C5.0 ефективніше використовує пам'ять, ніж C4.5.
• Менші дерева рішень: C5.0 отримує схожі результати з C4.5 зі значно меншими деревами рішень.
• Підтримка підсилювання: підсилення покращує дерева і надає їм більшу точність.
• Зважування: C5.0 дозволяє зважувати різні випадки та типи неправильної класифікації.
• Winnowing^[en]: опція C5.0 автоматично застосовує winnow алгоритм^[en] для видалення безкорисних атрибутів.

Вихідний код для однопоточної версії Linux C5.0 доступний під ліцензією GPL.

Див. також

• Дерева рішень у машинному навчанні
• Модель дерева рішень
• ID3 (алгоритм)

Примітки

1. Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
2. Umd.edu — Top 10 Algorithms in Data Mining (PDF) (англ.). Архів оригіналу (PDF) за 23 листопада 2018. Процитовано 15 квітня 2019.
3. S.B. Kotsiantis, «Supervised Machine Learning: A Review of Classification Techniques», Informatica 31(2007) 249—268, 2007
4. J. R. Quinlan. Improved use of continuous attributes in c4.5. Journal of Artificial Intelligence Research, 4:77-90, 1996.
5. Is See5/C5.0 Better Than C4.5? (англ.). Архів оригіналу за 19 квітня 2019. Процитовано 15 квітня 2019.
6. M. Kuhn and K. Johnson, Applied Predictive Modeling, Springer 2013

Посилання

• Початкова реалізація алгоритму на домашній сторінці Роса Куінлана: http://www.rulequest.com/Personal/ [Архівовано 3 травня 2019 у Wayback Machine.]
• See5 та C5.0 [Архівовано 17 квітня 2019 у Wayback Machine.]