Abstract

Random Forest (RF) is an ensemble supervised machine learning technique. Based on bagging and random feature selection, number of decision trees (base classifiers) is generated and majority voting is taken among them. The size of RF is subjective and varies from one dataset to another. Furthermore due to the randomization induced during creation, and its huge size, RF has at best been described as black-box. Various changes based on the experimental results have been proposed in the algorithm since then to optimize the performance of RF. To this end, we aim to find a subset, having accuracy comparable to original RF but having a much smaller size. In this paper, we show that the problem of selection of optimal subset of random forest follows the dynamic programming paradigm. Applying this approach to various UCI data-sets, corresponding subsets are obtained and studied. We conclude that such subsets do exist and that they are not unique. Moreover the size of these subsets is small fraction of the original RF (in the range of tens) and that accuracy of these subsets is a discrete valued function over its range.

References

• Leo Brieman, "Random Forests", Machine Learning, 45, 5-32, (2001)
• Ho, T. : "The random subspace method for constructing decision forests" – IEEE Transactions on Pattern Analysis and Machine Intelligence (1998)
• Breiman, L. : "Bagging Predictors" – Machine Learning (1996)
• Simon Bernard, Laurent Heutte, and Sebastien Adam, "On the Selection of Decision Trees in Random Forest", Proceedings of International Joint Cobference on Neural Networks, Atlanta, Georgia, USA, June 14-19, pp 302-307, (2009)
• Bernard, S. , Heutte, L. , Adam, S. : "Towards a Better Understanding of Random Forests Through the Study of Strength and Correlation" – 2009
• Heping Zhang, Minghui Wang, "Search for the smallest Random Forest", Statistics and Its Interface Volume 2, pp 381-388, (2009)
• Boinee P, Angelis A and Foresti G, Meta Random Forest, International Journal of Computational Intelligence 2, (2006)
• Tsymbal A, Pechenizkiy M and Cunningham P, Dynamic Integration with Random Forest, ECML, LNAI, 801-808, Springer-Verlag (2006)
• Robnik M, Sikonja, Improving Random Forests, J F Boulicaut et al (eds): Machine Learning, ECML 2004 Proceedings, Springer, Berlin, (2004)
• E Tripoli, D Fotiadis, G Manis, " Dynamic Construction of Random Forests: Evaluation using Biomedical Engineering Problems", IEEE 2010
• Vrushali Kulkarni, Pradeep Sinha, Aashu Singh,: Heuristic Based Improvements for Effective Random Forest Classifier, Proceedings of International Conference on Computational Intelligence (published by Springer), Chennai, India, 2012
• I. H. Witten, E. Frank, Weka : Practical machine learning tools and techniques, Morgan Kaufmann publisher, (2005)
• Grahn H, Lavesson N, Lapajne M and Slat D, A CUDA implementation of Random Forest Early Results, Master Thesis Software Engineering,School of Computing, Blekinge Institute of Technology, Sweden
• Saffari A, Leistner C, Santner J, Godec M and Bischof H, On-line Random Forests, ICCV IEEE, Conference Proceedings 1393-1400, (2009)
• Wang A, Wan G, Cheng Z and Li S, An Incremental Extremely Random Forest Classifier for Online Learning and Tracking, 16th IEEE International Conference on Image Processing,1449-1452, (2009)
• Chain C, Liaw A and Breiman L, Using Random forest to Learn Imbalanced Data, Technical Report, Department of Statistics, U. C. Berkley (2004)
• Kosorok M and Ma S, Marginal Asymptotics for the Large p Small n paradigm: With Applications to Microarray Data, Ann Statist 35, 1456-1486, (2007)
• Bonissone P, Cadenas J, Garrido M and Diaz-Valladares R, A Fuzzy Random Forest, International Journal of Approximate Reasoning, 51, 729-747, (2010)
• Leistner C, Saffari A, Santner J, Godec M and Bischof H, Semi- Supervised Random Forests, ICCV IEEE, Conference Proceedings, 506-513 (2009)
• Patrice, L. , Olivier, D. , Christine, D. : "Limiting the Number of Trees in Random Forests" – 2nd International Workshop on Multiple Classifier Systems – MCS, Cambridge, UK (2001)
• Cormen, T. , Leiserson, C. , Rivest, R. , Stein, C. : "Introduction To Algorithms" – 2nd Edition.
• Vrushali Y Kulkarni, Pradeep K Sinha, "Random Forest Classifiers: A Survey and Future research Directions", International Journal of Advanced Computing, Vol 36, Issue 1, 1144-1153 (2013)