Алгоритми побудови ансамблю дерева рішень та їх порівняльний аналіз
Анотація
Ансамблі дерев рішень вважають одними з найбільш ефективних засобів класифікації. У літературі запропоновано значну кількість алгоритмів для їх побудови, проте на практиці актуальним лишається питання вибору алгоритму, який забезпечує найвищу точність класифікації. У зв’язку з цим у роботі було поставлено задачу порівняти точність класифікації ансамблями дерев рішень, побудованими найбільш популярними та потужними алгоритмами.Для виконання цієї задачі було створено програмне забезпечення, в якому реалізовано наступні алгоритми: випадковий ліс, стекінг з використанням генетичного алгоритму, алгоритми побудови ансамблів надзвичайно випадкових дерев та досконалих випадкових дерев, а також використано 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).
DOI: http://dx.doi.org/10.15421/431806
Посилання
- Поки немає зовнішніх посилань.
Контактна інформація:
Байбуз Олег Григорович - відповідальний редактор
Тел: (056) 766-49-52
Mail: olegbaybuz68@gmail.com
Україна, 49010, м. Дніпро, пр. Гагаріна, 72
--------------------------------------------------------------------
Дніпровський національний університет імені Олеся Гончара
National Library of Ukraine Vernadsky
Bielefeld Academic Search Engine
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.