Estimation of general complexity of the procedure for constructing a binary logical classification tree for an arbitrary case

DOI:10.31673/2412-4338.2020.021100

Abstract

We propose an upper estimate of the complexity of the binary logical tree synthesis procedure for classifying an arbitrary case (for conditions of weak and strong separation of classes in the training sample). The solution to this question is of a fundamental nature, regarding the assessment of the structural complexity of classification models (in the form of tree structures) of discrete objects for a wide range of applied classification and recognition problems in terms of developing promising schemes and methods for their final optimization (minimization) of the structure. This research is relevant not only for the constructions of logical classification trees, but also allows us to extend the complexity estimation scheme itself to the general case of algorithmic structures of classification trees (concepts of algorithm trees and generalized feature trees).
The current issue of complexity of the general procedure for constructing a logical classification tree based on the concept of step-by-step selection of sets of elementary features (their possible heterogeneous sets and combinations), which for a given initial training sample (an array of discrete information) builds a tree structure (classification model), from a set of elementary features (basic attributes) evaluated at each stage of the model construction scheme for this sample.
Thus, modern information technologies based on mathematical models of pattern recognition (logical and algorithmic classification trees) are widely used in socio-economic, environmental and other systems of primary analysis and processing of large amounts of information. This is due to the fact that this approach allows you to eliminate a set of existing disadvantages of well-known classical methods and schemes and achieve a fundamentally new result. The work is devoted to the problems of classification tree models (decision trees), and offers an assessment of the complexity of logical tree structures (classification tree models), which consist of selected and ranked sets of elementary features built on the basis of the General concept of branched feature selection. This method, when forming the current vertex of the logical tree (node), provides the selection of the most informative (qualitative) elementary features from the source set. This approach allows you to significantly reduce the size and complexity of the tree (the total number of branches and tiers of the structure) and improve the quality of its subsequent analysis.

Keywords: logical classification tree, pattern recognition, classification, discrete attribute.

References
1. Srikant, R., Agrawal, R. (1997) Mining generalized association rules. Future Generation Computer Systems, Vol.13, №2, 61–180.
2. Vasilenko, Y.A., Vasilenko, E.Y., Povkhan, I.F, Vashchuk, F.G. (2004) Conceptual basis of pattern recognition systems based on the method of branched feature selection. Scientific and technical journal “European Journal of Enterprise Technologies”, №7[1], 13-15.
3. Vasilenko, Y.A., Vashchuk, F.G, Povkhan, I.F. (2011) The problem of estimating the complexity of the logic trees, recognition, and a general method of optimization. Scientific and technical journal “European Journal of Enterprise Technologies”, 6/4(54), 24-28.
4. Vasilenko, Y. A., Povkhan, I.F., Vashchuk, F.G. (2012) General estimation of tree logical structures minimization. Scientific and technical journal “European Journal of Enterprise Technologies”, 1/4 (55), 29-33.
5. Povkhan, I. (2019) General scheme for constructing the most complex logical tree of classification in pattern recognition of discrete objects. Collection of scientific papers "electronics and information technology", Lviv, Issue 11, 112-117.
6. Vasilenko, Y.A., Vasilenko, E.J., Povkhan, I.F., Kovacs, M.J., Nickovic, O.D. (2004) Minimization of logic tree structures in pattern recognition problems. Scientific and technical journal “European Journal of Enterprise Technologies”, 3[9], 12-16.
7. Laver, V.O., Povkhan, I.F. (2019) Algorithms for constructing logical classification trees in pattern recognition problems. Scientific notes of Tauride national University. Series: technical Sciences, Volume 30(69) No. 4 - 2019, 100-106.
8. Vtogoff, P.E. (2009) Incremental Induction of Decision Trees. Machine Learning, № 4, 61−186.
9. Povkhan, I.F. (2018) The problem of functional evaluation of the training sample in the problems of recognition of discrete objects. Scientific notes of Taurida national University. Series: technical Sciences, Volume 29(68) №.6, 217-222.
10. Whitley D. (2001) An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology, Vol.43, №14, P. 817–831.
11. Povhan I. (2016) Designing of recognition system of discrete objects, IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, Ukraine. Lviv, pp. 226–231.
12. Kotsiantis S.B. (2007) Supervised Machine Learning: A Review of Classification Techniques, Informatica, No. 31, pp. 249–268
13. Subbotin S.A. (2019) Construction of decision trees for the case of low-information features, Radio Electronics, Computer Science, Control, No. 1, pp. 121–130.
14. Deng H., Runger G., Tuv E. (2011) Bias of importance measures for multi-valued attributes and solutions, Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN), pp. 293–300.
15. Povkhan I.F. (2019) Features of synthesis of generalized features in the construction of recognition systems using the logical tree method, Materials of the international scientific and practical conference “Information technologies and computer modeling ІТКМ-2019”. Ivаnо-Frаnkivsk, pp. 169–174.
16. Povkhan I.F. (2019) Features random logic of the classification trees in the pattern recognition problems, Scientific notes of the Tauride national University. Series: technical Sciences, Vol. 30(69), No. 5, pp. 152–161.
17. Povhan I. (2019) Generation of elementary signs in the general scheme of the recognition system based on the logical tree. Electronics and information technologies. Lviv, 2019, Vol. 12. P. 20-29.
18. Povhan I. (2020) Question of the optimality criterion of a regular logical tree based on the concept of similarity. Electronics and information technologies. Lviv, 2020, Vol. 13. P. 19-27.