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, використовуючи концепцію інформаційної ентропії. Навчальні дані — це набір $S={s_{1},s_{2},...}$ вже класифікованих зразків. Кожний зразок $s_{i}$ складається з p-мірного вектора $(x_{1,i},x_{2,i},...,x_{p,i})$ , де $x_{j}$ представляють значення атрибутів або ознаки зразків, а також клас, до якого належить $s_{i}$ .

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

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

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

Псевдокод[ред. | ред. код]

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

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

Реалізації[ред. | ред. код]

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

Покращення алгоритму ID3[ред. | ред. код]

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

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

Обробка як неперервних, так і дискретних атрибутів. Для того, щоб обробляти неперервні атрибути, C4.5 створює поріг, а потім розбиває набір даних на ті елементи, чиє значення атрибута перевищує поріг, і ті, які менше або дорівнюють йому^[4].
Обробка навчальних даних з відсутніми значеннями атрибутів. У C4.5 атрибути можуть помічатись як $?$ у разі, якщо значення відсутнє. Відсутнє значення атрибутів просто не використовується в обчисленнях коефіцієнтів приросту та ентропії.
Обробка атрибутів з різними витратами.
Обрізання дерев. Після створення дерева 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.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

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

[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

[1]

[2]

[3]

[4]

[5]

[6]