Обзор развития алгоритмов деревьев решений

  • Анна Наильевна Сулейманова Национальный исследовательский университет «Высшая школа экономики» asuleymanova@hse.ru ORCID ID https://orcid.org/0000-0002-4379-3835

Аннотация

Деревья решений – метод классификации и предсказания, распространенный в прикладных исследованиях в силу простоты применения и интерпретации. Ввиду большого количества самих алгоритмов, разрозненности литературы и программного обеспечения для работы с ними выбор одного из методов представляет собой непростую задачу. В результате исследователи предпочитают использовать хорошо знакомые и давно использующиеся алгоритмы, несмотря на их явные недостатки. Обзор ставит целью выделить и описать актуальные направления развития этого класса методов и систематизировать новации в его применении за 2014–2019 гг. Для выделения актуальных тематических направлений развития методов используется построение библиографической сети на ключевых словах. Обзор позволит упростить навигацию в растущем избытке алгоритмов и дополнить данные, представленные в предыдущих обзорах.
Ключевые слова:
деревья решений, деревья классификации, деревья регрессии, библиографический анализ, сеть ключевых слов, большие данные

Биография автора

Анна Наильевна Сулейманова, Национальный исследовательский университет «Высшая школа экономики»
Аспирант школы по социологическим наукам, преподаватель кафедры методов сбора и анализа социологической информации, факультет социальных наук, Национальный исследовательский университет «Высшая школа экономики», Москва, Россия

Литература

1. Жучкова С.В. Поиск многомерной связи категориальных признаков: сравнение CHAID, логлинейного анализа и множественного анализа соответ¬ствий / С.В. Жучкова, А.Н. Ротмистров // Мониторинг общественного мнения: экономические и социальные перемены. 2019. № 2. C. 32–53.

2. Loh W. Fifty Years of Classification and Regression Trees // International Statistical Review. 2014. Vol. 82. No. 3. P. 329–348.

3. Rusch T. Discussion of Fifty Years of Classification and Regression Trees / T. Rusch, A. Zeileis // International Statistical Review. 2014. Vol. 82. No. 3. P. 361–367.

4. Morgan J. Problems in the Analysis of Survey Data, and a Proposal / J. Morgan, J. Sonquist // Journal of American Statistical Association. 1963. Vol. 58. No. 302. P. 415–434.

5. Моисеев С.П. Отбор источников для систематического обзора литературы: сравнение экспертного и алгоритмического подходов / С.П. Моисеев, Д.В. Маль¬цева // Социология: методология, методы, математическое моделирование. 2018. № 47. С. 7–43.

6. Batagelj V. Pajek: Program for Large Network Analysis / V. Batagelj, A. Mrvar // Connections. 1998. Vol. 21. No. 2. P. 47–57.

7. Quinlan J.R. C4.5: Programs for Machine Learning. San Francisco: Morgan Kaufmann Publishers Inc., 1993.

8. An Up-to-date Comparison of State-of-the-art Classification Algorithms / C. Liu, X. Zhang, G. Almpanidis // Expert Systems with Applications. Vol. 82. P. 128–150.

9. King R. Statlog: Comparison of Classification Algorithms on Large Real-world Problems / R. King, C. Feng, A. Sutherland // Applied Artificial Intelligence. 1995. Vol. 9. No. 3. P. 289–333.

10. Lim T. Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-three Old and New Classification Algorithms / T. Lim, W. Loh, Y. Shih // Machine Learning. 2000. Vol. 40. No. 3. P. 203–228.

11. Бильгаева Л.П. Исследование моделей деревьев решений в задаче клас¬сификации / Л.П. Бильгаева, В.В. Ларин, Д.А. Маслюк // Экспериментальные и теоретические исследования в XXI веке: проблемы и перспективы развития. Материалы XIII Всероссийской научно-практической конференции. Ростов н/Д.: ИУБиП, 2018. P. 38–51.

12. Witten I. Data Mining: Practical Machine Learning Tools and Techniques / I. Witten, E. Frank, M. Hall. 3rd ed. San Francisco: Morgan Kaufmann Publishers Inc., 2011.

13. Trabelsi A. Decision Tree Classifiers for Evidential Attribute Values and Class Labels / A. Trabelsi, Z. Elouedi, E. Lefevre // Fuzzy Sets and Systems. 2019. Vol. 366. P. 46–62.

14. Fuzzy Rule Based Decision Trees / X. Wang, X. Liu, W. Pedrycz, I. Zhang // Pattern Recognition. 2015. Vol. 48. No. 1. P. 50–59.

15. Jin C. A Generalized Fuzzy ID3 Algorithm Using Generalized Information Entropy / C. Jin, F. Li, Y. Li // Knowledge-Based Systems. 2014. Vol. 64. P. 13–21.

16. Prati R. A First Approach towards a Fuzzy Decision Tree for Multilabel Classification / R. Prati, F. Charte, F. Herrera // 2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Naples, 2017. P. 1–6.87

17. Баранов Л.Т. Нечеткие множества в экспертном опросе / Л.Т. Баранов, А.И. Птушкин, А.В. Трудов // Социология: методология, методы, математическое моделирование. 2004. № 19. С. 142–157.

18. Мухатдинова О.Р. Построение и анализ социограмм на основе нечеткой логики // Социология: методология, методы, математическое моделирование. 2000. № 12. P. 154–172.

19. Chang R. Fuzzy Decision Tree Algorithms / R. Chang, T. Pavlidis // IEEE Transactions on Systems, Man, and Cybernetics. 1977. Vol. 7. No. 1. P. 28–35.

20. Olaru C. A Complete Fuzzy Decision Tree Technique / C. Olaru, L. Wehenkel // Fuzzy Sets and Systems. 2003. Vol. 138. No. 2. P. 221–254.

21. Cintra M. A Fuzzy Decision Tree Algorithm Based on C4.5 / M. Cintra, M. Monard, H. Camargo // Mathware & Soft Computing. Vol.20. No. 1. 2013. P. 56–62.

22. Zeinalkhani M. Comparing Different Stopping Criteria for Fuzzy Decision Tree Induction through IDFID3 / M. Zeinalkhani, M. Eftekhari // Iranian Journal on Fuzzy Systems. 2014. Vol. 11. No. 1. P. 27–48.

23. Bergmeir C. frbs: Fuzzy Rule-based Systems for Classification / C. Bergmeir, M. Ben // Journal of Statistical Software. 2015. Vol. 65. No. 6. P. 1–30.

24. Implementing Algorithms of Rough Set Theory and Fuzzy Rough Set Theory in the R Package “roughSets” / L. Riza, A. Janusz, C. Bergmeir [et al.] // Information Sciences. 2014. Vol. 287. P. 68–89.

25. Chipman H. Bayesian CART Model Search / H. Chipman, E. George, R. McCulloch // Journal of American Statistical Association. 1998. Vol. 93. No. 443. P. 935–948.

26. Denison D. A Bayesian CART Algorithm / D. Denison, B. Mallick, A. Smith // Biometrika. 1998. Vol. 85. No. 2. P. 363–377.

27. Pratola M. Efficient Metropolis-Hastings Proposal Mechanisms for Bayesian Regression Tree Models // Bayesian Analysis. 2016. Vol. 11. No. 3. P. 885–911.

28. Parallel Bayesian Additive Regression Trees / M. Pratola, H. Chipman, J. Gattiker [et al.] // Journal of Computational and Graphical Statistics. 2014. Vol. 23. No. 3. P. 830–852.

29. Linero A. Bayesian Regression Trees for High-dimensional Prediction and Variable Selection // Journal of American Statistical Association. 2018. Vol. 112. No. 522. P. 626–636.

30. Xu D. A Bayesian Nonparametric Approach to Causal Inference on Quantiles / D. Xu, M. Daniels, A. Winterstein // Biometrics. 2018. Vol. 74. No. 3. P. 986–996.

31. Kapelner A. bartMachine: Machine Learning with Bayesian Additive Regression Trees / A. Kapelner, J. Bleich // Journal of Statistical Software. 2013. Vol. 70. No. 4. P. 1–40.

32. Gramacy R. tgp: An R Package for Bayesian Nonstationary, Semiparametric Nonlinear Regression and Design by Treed Gaussian Process Models // Journal of Statistical Software. 2007. Vol. 19. No. 9. P. 1–46.

33. Gibaja E. A Tutorial on Multilabel Learning / E. Gibaja, S. Ventura // ACM Computing Surveys. 2015. Vol. 47. No. 3. P. 1–38.

34. Li P. An Incremental Decision Tree for Mining Multilabel Data / Li P., X. Wu, X. Hu, H. Wang // Applied Artificial Intelligence. 2015. Vol. 29. No. 10. P. 992–1014.

35. Bi W. Bayes-optimal Hierarchical Multilabel Classification / W. Bi, J. Kwok // IEEE Transactions on Knowledge and Data Engineering. 2015. Vol. 27. No. 11. P. 2907–2918.

36. An Extensive Evaluation of Decision Tree-based Hierarchical Multilabel Classification Methods and Performance Measures / R. Cerri, G. Pappa, A. Carvalho, A. Freitas // Computational Intelligence. 2015. Vol. 31. No. 1. P. 1–46.

37. Rivolli A. The Utiml Package: Multi-label Classification in R / A. Rivolli, A. de Carvalho // R Journal. 2019. Vol. 10. No. 1. 2. P. 24-37.

38. Blockeel H. Top-down Induction of Clustering Trees / H. Blockeel, L. de Raedt, J. Ramon // ICML ’98 Proceedings of the 15th International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers Inc., 1998. P. 55–63.

39. Semi-supervised Trees for Multi-target Regression / J. Levatić, D. Kocev, M. Ceci, S. Dzeroski // Information Sciences. 2018. Vol. 450. P. 109–127.

40. Osojnik A. Comparison of Tree-based Methods for Multi-target Regression on Data Streams / A. Osojnik, P. Panov, S. Dzeroski // Proceedings of the 4th International Conference on New Frontiers in Mining Complex Patterns (NFMCP'15). Berlin: Springer International Publishing. 2015. P. 17–31.

41. Osojnik A. Option Predictive Clustering Trees for Multi-target Regression / A. Osojnik, S. Dzeroski, D. Kocev // Computer Science and Information Systems. 2017. Vol. 17. No. 2. P. 118–133.

42. Blockeel H. Efficient Algorithms for Decision Tree Cross-validation / H. Blockeel, J. Struyf // Journal of Machine Learning Research. 2003. Vol. 3. No. 4–5. P. 621–650.

43. Lee J. AUC4.5: AUC-based C4.5 Decision Tree Algorithm for Imbalanced Data Classification // IEEE Access. 2019. Vol. 7. P. 106034–106042.

44. Wu C. Cost-sensitive Decision Tree with Multiple Resource Constraints / C. Wu, Y. Chen, K. Tang // Applied Intelligence. 2019. Vol. 49. No. 10. P. 3765–3782.

45. A Compact Evolutionary Interval-valued Fuzzy Rule-based Classification System for the Modeling and Prediction of Real-world Financial Applications with Imbalanced Data / J. Sanz, D. Bernardo, F. Herrera [et al.] // IEEE Transactions on Fuzzy Systems. 2015. Vol. 23. No. 4. P. 973–990.

46. Bahnsen A.C. Example-dependent Cost-sensitive Decision Trees / A.C. Bahnsen, D. Aouada, B. Ottersten // Expert Systems with Applications. 2015. Vol. 42. No. 19. P. 6609–6619.

47. Fu W. Unbiased Regression Trees for Longitudinal and Clustered Data / W. Fu, J. Simonoff // Computational Statistics and Data Analysis. 2015. Vol. 88. P. 53–74.89

48. Kim J. Seemingly Unrelated Regression Tree / J. Kim, H. Cho // Journal of Applied Statistics. 2019. Vol. 46. No. 7. P. 1177–1195.

49. Hothorn T. Unbiased Recursive Partitioning: A Conditional Inference Framework / T. Hothorn, K. Hornik, A. Zeileis // Journal of Computational and Graphical Statistics. 2006. Vol. 15. No. 3. P. 651–674.

50. Sun H. Attribute Selection for Decision Tree Learning with Class Constraint / H. Sun, X. Hu // Chemometrics and Intelligent Laboratory Systems. 2017. Vol. 163. P. 16–23.

51. Zhang X. A New Strategy of Cost-free Learning in the Class Imbalance Problem / X. Zhang, B. Hu // IEEE Transactions on Knowledge and Data Engineering. 2014. Vol. 26. No. 12. P. 2872–2885.

52. Sardari S. Hesitant Fuzzy Decision Tree Approach for Highly Imbalanced Data Classification / S. Sardari, M. Eftekhari, F. Afsari // Applied Soft Computing Journal. 2017. Vol. 61. P. 727–741.

53. Kim H. Classification Trees with Unbiased Multiway Splits / H. Kim, W. Loh // Journal of American Statistical Association. 2009. Vol. 96. No. 454. P. 589–604.

54. Жучкова С.В. Возможность работы с пропущенными данными при ис¬пользовании CHAID: результаты статистического эксперимента / С.В. Жучкова, А.Н. Ротмистров // Социология: методология, методы, математическое модели¬рование. 2018. № 46. P. 85–122.

55. Little R. The Analysis of Social Science Data with Missing Values / R. Little, D. Rubin // Sociological Methods and Research. 1989. Vol. 18. P. 292–326.

56. A New Variable Importance Measure for Random Forests with Missing Data / A. Hapfelmeier, T. Hothorn, K. Ulm, C. Strobl // Statistics and Computing. 2014. Vol. 24. No. 1. P. 21–34.

57. An Alternative Pruning Based Approach to Unbiased Recursive Partitioning / A. Alvarez-Iglesias, J. Hinde, J. Ferguson, J. Newell // Computational Statistics and Data Analysis. 2017. Vol. 106. P. 90–102.

58. Pereira C. TS-stream: Clustering Time Series on Data Streams / C. Pereira, R. de Mello // Journal of Intelligent Information Systems. 2014. No. 42. P. 531–566.

59. Gomes C. Presenting the Regression Tree Method and its Application in a Large-scale Educational dataset / C. Gomes, E. Jelihovschi // International Journal of Research & Method in Education. 2020. Vol. 43. No. 2. P. 201–221.

60. Sorensen L. “Big Data” in Educational Administration: An Application for Predicting School Dropout Risk // Educational Administration Quaterly. 2019. Vol. 55. No. 3. P. 404–446.

61. Губа К. Большие данные в социологии: новые данные, новая социология? // Социологическое обозрение. 2018. Т. 17. № 1. P. 213–236.

62. Varian H. Big Data: New Tricks for Econometrics // Journal of Economic Perspectives. 2014. Vol. 28. No. 2. P. 3–28.

63. Prati R. Emerging Topics and Challenges of Learning from Noisy Data in Nonstandard Classification: a Survey beyond Binary Class Noise / R. Prati, J. Luengo, F. Herrera // Knowledge and Information Systems. 2018. Vol. 60. No. 1. P. 1–35.

64. Кавеева А.Д. Локальные сети дружбы «ВКонтакте»: восстановление про¬пущенных данных о городе проживания пользователей / А.Д. Кавеева, К.Е. Гурин // Мониторинг общественного мнения: экономические и социальные перемены. 2018. Т. 3. № 145. P. 78–90.

65. Mantas C. Credal-C4.5: Decision Tree Based on Imprecise Probabilities to Classify Noisy Data / C. Mantas, J. Abellán // Expert Systems with Applications. 2014. Vol. 41. No. 10. P. 4625–4637.

66. Classification Tree Methods for Panel Data Using Wavelet-transformed Time Series / X. Zhao, S. Barber, C. Taylor, Z. Milan // Computational Statistics and Data Analysis. 2018. Vol. 127. P. 204–216.

67. Classification of Time Series by Shapelet Transformation / J. Hills, J. Lines, E. Baranauskas [et al.] // Data Mining and Knowledge Discovery. 2014. Vol. 28. P. 851–881.

68. Петровский М.И. Метод многотемной (multi-label) классификации на основе попарных сравнений с отсечением наименее релевантных классов / М.И. Петровский, В.В. Глазкова // Математические методы распознавания образов: 13-я Всероссийская конференция. Т. 13. М.: МАКС Пресс, 2007. С. 197–200.
Статья

Поступила: 01.06.2020

Опубликована: 11.04.2021

Раздел
ПРАКТИКИ СБОРА И АНАЛИЗА ФОРМАЛИЗОВАННЫХ ДАННЫХ