Журнал: Социология: методология, методы, математическое моделирование (Социология:4М)Сулейманова А. Н.Обзор развития алгоритмов деревьев решений

Институт социологии
ФНИСЦ РАН

Журнал: Социология: методология, методы, математическое моделирование (Социология:4М)

Сулейманова А. Н.

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


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

Полный текст

Открыть текст

Ссылка при цитировании:

Сулейманова А. Н. Обзор развития алгоритмов деревьев решений // Социология: методология, методы, математическое моделирование (Социология:4М). 2020. № 50-51. С. 63-96.

Рубрика:

ПРАКТИКИ СБОРА И АНАЛИЗА ФОРМАЛИЗОВАННЫХ ДАННЫХ

Аннотация:

Деревья решений – метод классификации и предсказания, распространенный в прикладных исследованиях в силу простоты применения и интерпретации. Ввиду большого количества самих алгоритмов, разрозненности литературы и программного обеспечения для работы с ними выбор одного из методов представляет собой непростую задачу. В результате исследователи предпочитают использовать хорошо знакомые и давно использующиеся алгоритмы, несмотря на их явные недостатки. Обзор ставит целью выделить и описать актуальные направления развития этого класса методов и систематизировать новации в его применении за 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.

Содержание выпуска

>> Содержание выпуска 2020. № 50-51.
>> Архив журнала