ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ПОБУДОВИ ДЕРЕВ РІШЕНЬ (ID3, C4.5 ТА CHAID) - Наукові конференції
Головна
UA RU EN

Вас вітає Інтернет конференція!

Вітаємо на нашому сайті

Рік заснування видання - 2011

ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ПОБУДОВИ ДЕРЕВ РІШЕНЬ (ID3, C4.5 ТА CHAID)

05.04.2022 21:27

[3. Технічні науки]

Автор: Голько Надія Андріївна, студентка 1 курсу магістратури, Львівський національний університет ім. Івана Франка


У сучасному світі дуже важливо приймати правильні рішення і дерева рішень якраз допомагають це зробити. Їх основне завдання – це класифікація даних та прогнозування результату, щоб вибрати найкраще рішення для певної проблеми. 

Об’єкти, які потрібно класифікувати, найкраще подати у вигляді таблиці (табл. 1). Кожен атрибут має деякі значення. Останній стовпець це мітки класів рішення. 

Таблиця 1.

Вигляд об’єктів для класифікації





На основі цієї таблиці будується дерево, в якого кожна вершина відповідає за атрибут, кожне ребро за можливі значення того атрибуту, а листки дерева відображають результат класифікації [2]. 

Загальна схема побудови дерева рішень виглядає так: спочатку у кореневій вершині вибирається найбільш інформативний атрибут. На кожній ітерації проводиться розбиття множини за цим атрибутом. Алгоритм продовжує рекурсивно виконуватись на кожній підмножині, враховуючи лише ті атрибути, які раніше не були вибрані. Кінцевий результат – дерево рішень, в якому кожна вершина представляє можливий сценарій прийняття рішення, а кожен листок – результат.

Тут постає логічне питання: як вибрати черговий атрибут? Для цього існує багато алгоритмів і кожен використовує свій метод вибору чергового атрибуту. У своїй роботі я досліджую алгоритми Id3, C4.5 та CHAID.  

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

 C4.5 — цей алгоритм розроблений також Росом Куінланом у 1993 році. C4.5 вважають покращеним алгоритмом ID3 [4], бо він має ряд доповнень, а саме: обробка як неперервних, так і дискретних атрибутів, обробка навчальних даних з відсутніми значеннями атрибутів, обрізання дерев. Цей алгоритм використовує нормалізований інформаційний прибуток[5].  

CHAID – назва алгоритму походить від абревіатури Chi Squared Automatic Interaction Detection. Він був запропонований в 1980 році Гордоном В. Кассом. Для класифікації даних CHAID використовує критерій хі-квадрат [6]. 

Таблиця 2.

Дані про оцінку кредитного ризику






Під час дослідження, для кожного алгоритму розв’язано задачу, вхідні дані взято з [3]. 

Умова: у табл. 2 наведено дані про оцінку кредитного ризику на підставі доходу, кредитної історії, поточного боргу та наявності поруки. Побудуйте дерево рішень використовуючи алгоритми ID3, C4.5 та CHAID.

Розв'язавши поставлену задачу, я також розробила програмну реалізацію алгоритмів на мові Python, яка підтвердила мої обчислення (рис. 1-2). 





Бачимо, що дерева дещо відрізняються, бо для значення Середній(middle) атрибуту Дохід(Income) алгоритми ID3 та CHAID наступним домінуючим атрибутом обрали Кредитну Історію(Credit), натомість C4.5 обрав Борг(Debt). 

На основі роботи зроблено наступні висновки:

- алгоритм Id3 простий в реалізації і він є в основі багатьох інших алгоритмів. Для цього алгоритму дуже важливу роль має навчальний набір даних, який він отримує. Якщо ці дані сильно зашумлені, містять помилки чи їх недостатньо для розв’язку задачі, то id3 не гарантує правильність висновків. В розрахунках використовується Інформаційний прибуток;

- алгоритм C4.5 дуже схожий на попередній алгоритм, адже створюючи C4.5 автор намагався покращити Id3. Даний алгоритм має ряд покращень, що дозволило розширити можливості розв’язку задач класифікації та прогнозування, а саме обробка неперервних даних, обробка навчальних даних з відсутніми значеннями атрибутів, обрізання дерев. В розрахунках використовується Нормалізований інформаційний прибуток;

- алгоритм CHAID – один з перших алгоритмів побудови дерев рішень, проте і досі часто використовується. Для великих наборів даних алгоритм CHAID витрачає значно більше часу ніж попередні алгоритми, проте дерева будує ефективніше. В розрахунках використовується Критерій Хі-квадрат.

Література

1. Quinlan, J. R. Machine Learning. Induction of decision trees. 1986. 81–106 с. 

URL: https://link.springer.com/content/pdf/10.1023/A:1022643204877.pdf

2. Ю.В. Нікольский, В.В. Пасічник, Ю.М. Щербина. Системи штучного інтелекту. Львів, “Магнолія”. 2013. 217 с.

3. Люгер Д. Искусственный интеллект. 2003. 392-400 с.

4. Building Classification Models: ID3 and C4.5. College of Science and Technology Temple University.

URL: https://cis.temple.edu/~ingargio/cis587/readings/id3-c45.html

5. C4.5 Decision Tree Example 

URL: https://sefiks.com/2018/05/13/a-step-by-step-c4-5-decision-tree-example/

6. CHAID Decision Tree Example 

URL: https://sefiks.com/2020/03/18/a-step-by-step-chaid-decision-tree-example/

___________________

Науковий керівник: Заболоцький Тарас Миколайович, доктор економічних наук, доцент, Львівський національний університет ім. Івана Франка








Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Інші наукові праці даної секції

Конференції

Конференції 2024

Конференції 2023

Конференції 2022

Конференції 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення