Алгоритми побудови ансамблю дерева рішень та їх порівняльний аналіз

O. Matsuga, B. Nashylnyk

Анотація


Ансамблі дерев рішень вважають одними з найбільш ефективних засобів класифікації. У літературі запропоновано значну кількість алгоритмів для їх побудови, проте на практиці актуальним лишається питання вибору алгоритму, який забезпечує найвищу точність класифікації. У зв’язку з цим у роботі було поставлено задачу порівняти точність класифікації ансамблями дерев рішень, побудованими найбільш популярними та потужними алгоритмами.Для виконання цієї задачі було створено програмне забезпечення, в якому реалізовано наступні алгоритми: випадковий ліс, стекінг з використанням генетичного алгоритму, алгоритми побудови ансамблів надзвичайно випадкових дерев та досконалих випадкових дерев, а також використано open-source реалізації випадкового лісу з пакету Accord та градієнтного бустінгу з пакету XGBoost. Програмне забезпечення розроблене на мові C# у середовищі Microsoft Visual Studio у вигляді настільного додатку. За його допомогою проведено обчислювальні експерименти на 10 реальних наборах даних різних обсягів та розмірностей, взятих з UCI Machine Learning Repository.Суть експерименту на кожному наборі даних полягала в наступному. Набір даних випадковим чином було розбито на 2 частини: початкову та тестову. Навчальну використано для побудови ансамблю з 50 дерев, а тестову – для оцінювання точності класифікації. Випадкове розбиття набору й оцінку точності класифікації було виконано 30 разів, після чого обчислено середнє значення точності класифікації та його середньоквадратичне відхилення. Тоді було проведено порівняння середніх за допомогою двохвибіркового t тесту на рівні значущості 0,05. За результатами обчислювальних експериментів найкращий результат показав алгоритм побудови ансамблю надзвичайно випадкових дерев: побудований ансамбль мав найвищу точність класифікації на 7 наборах даних і на більшості наборів переміг або не програв іншим ансамблям. Трохи гірші результати показали випадковий ліс та градієнтний бустинг з пакету XGBoost, які виявилися кращими на 5 та 4 наборах відповідно та не часто поступалися за точністю класифікації іншим алгоритмам. Стекінг з використанням генетичних алгоритмів, ансамбль досконалих випадкових дерев та випадковий ліс із пакету Accord показали найнижчу точність класифікацію на більшості наборів.


Ключові слова


класифікація, дерево рішень, ансамбль дерев рішень, точність класифікації, обчислювальний експеримент

Повний текст:

PDF

Посилання


Rokach L., Maimon D. Data mining with decision trees. Theory and applications. 2nd ed. Singapore: World Scientific Publishing Company. 2015. 305 p.

Breiman L. Bagging Predictors. Machine Learning. 1996. Vol. 24.

P. 123-140.

Breiman L. Random Forests. Machine Learning. 2001. Vol. 45.

P. 5-32.

Geurts P., Ernst D., Wehenkel L. Extremely randomized trees. Machine Learning. 2006. Vol. 63. P. 3-42.

Cutler A., Zhao G. PERT – Perfect Random Tree Ensembles. Computing Science and Statistics. 2001. Vol. 33. P. 490-497.

Friedman J.H. Greedy Function Approximation: A Gradient Boosting Machine. The Annals of Statistics. 2001. Vol. 29, № 5. P. 1189-1232.

Chen T., Guestrin C. XGBoost: A Scalable Tree Boosting System. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016. P. 785-794.

Sikora R., Al-laymoun O. A Modified Stacking Ensemble Machine Learning Algorithm Using Genetic Algorithms. Journal of International Technology and Information Management. 2014. Vol. 23, Issue 1, Article 1.

Accord.NET Machine Learning Framework. URL: http://accord-framework.net/index.html (дата звернення: 09.09.18).

Бабак В.П., Білецький А.Я., Приставка О.П., Приставка П.О. Статистична обробка даних. К.: МІВВЦ, 2001. 388 с.

UCI Machine Learning Repository. URL: http://archive.ics.uci.edu/ml/ (дата звернення: 09.09.18).


Посилання

  • Поки немає зовнішніх посилань.


Контактна інформація:

Байбуз Олег Григорович - відповідальний редактор 

Тел: (056) 766-49-52

Mail: obaybuz@ua.fm

Україна, 49010, м. Дніпро, пр. Гагаріна, 72

--------------------------------------------------------------------

Дніпровський національний університет імені Олеся Гончара

National Library of Ukraine Vernadsky

Google Scholar

Open Academic Journals Index

Bielefeld Academic Search Engine

Open Archives

  Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.


Open Science in Ukraine - website development