DOI: https://doi.org/10.15588/1607-3274-2020-2-10

LOGICAL RECOGNITION TREE CONSTRUCTION ON THE BASIS OF A STEP-TO-STEP ELEMENTARY ATTRIBUTE SELECTION

I. F. Povhan

Abstract


Context. A general problem of constructing logical recognition/classification trees has been analyzed. Logical classification trees are the object of the present study. The subject of the study are the relevant methods and algorithms of logical classification trees. 

Objective. The goal of this work is to develop a simple and efficient method of constructing logical tree-like models on the basis of classification trees for training discrete information selection characterized by a structure of constructed logical classification trees from elementary attributes estimated on the basis of their informativeness calculation functional. 

Method. A general method of constructing logical classification trees is suggested that constructs a tree-like structure for a given initial training selection comprising a set of elementary attributes estimated at each step of constructing a model according to the above selection. In other words, a method of constructing logical classification trees is suggested with the main idea of approximating the initial selection of an arbitrary volume by the elementary attribute set. This method during the current logical tree (node) vertex formation provides selecting the most informative (high-quality) elementary attributes from the initial set. Such approach at constructing the resulting classification tree allows one to reduce essentially the tree size and complexity (i.e. the total number of branches and structural layers) and increase the quality of its further analysis (interpretability). The method of constructing logical classification trees suggested by us enables one to construct the tree-like models for a wide class of artificial intellect theory problems. 

Results. The method developed and presented in this work has received a software realization and was studied when solving a problem of classifying the geological type data characterized by a large-dimension attribute space. 

Conclusions. Experiments carried out in this work have confirmed the efficiency of the software suggested and demonstrate the possibility of its use for solving a wide spectrum of applied recognition and classification problems. The outlook of the further studies may be related to creating a limited method of logical classification tree by introducing the stopping criterion for the logical tree construction procedure according to the structure depth, its program realization optimization, as well as to the experimental study of this method in a wider circle of applied problems. 


Keywords


Logical classification tree, image recognition, classification, attribute, branching criterion.

Full Text:

PDF

References


Quinlan J.R. Induction of Decision Trees, Machine Learning, 1986, No. 1, pp. 81–106.

Vasilenko Y. A., Vasilenko E. Y., Povkhan I. F. Conceptual basis of image recognition systems based on the branched feature selection method, European Journal of Enterprise Technologies, 2004, No. 7(1), pp. 13–15.

Povhan I. General scheme for constructing the most complex logical tree of classification in pattern recognition discrete objects, Collection of scientific papers Electronics and information technologies. Lviv, 2019, Vol. 11, pp. 112– 117.

Srikant R., Agrawal R. Mining generalized association rules, Future Generation Computer Systems, 1997, Vol. 13, No. 2, pp. 161–180.

Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Berlin, Springer, 2008, 768 p.

Povhan I. Designing of recognition system of discrete objects, IEEE First International Conference on Data Stream Mining & Processing (DSMP). Lviv, 2016, Ukraine. Lviv, 2016, pp. 226–231.

Povhan I. F. The problem of general estimation of the complexity of the maximum constructed logical classification tree, Bulletin of the national technical University Kharkiv Polytechnic Institute, 2019, No. 13, pp. 104−117.

Breiman L. L., Friedman J. H., Olshen R. A., Stone C. J. Classification and regression trees. Boca Raton, Chapman and Hall/CRC, 1984, 368 p.

Vasilenko Y.A., Vasilenko E.Y., Povkhan I.F. Branched feature selection method in mathematical modeling of multilevel image recognition systems, Artificial Intelligence, 2003, No. 7, pp. 246−249.

Povkhan I.F. The problem of functional evaluation of a training sample in discrete object recognition problems, Scientific notes of the Tauride national University. Series: technical Sciences, 2018, Vol. 29(68), No. 6, 2018, pp. 217– 222.

Bodyanskiy Y., Vynokurova O., Setlak G. and Pliss I. Hybrid neuro-neo-fuzzy system and its adaptive learning algorithm, Xth Scien. and Tech. Conf. “Computer Sciences and Information Technologies” (CSIT), 2015. Lviv, 2015, pp. 111–114.

Laver V. O., Povkhan I. F. The algorithms for constructing a logical tree of classification in pattern recognition problems, Scientific notes of the Tauride national University. Series: technical Sciences, 2019, Vol. 30(69), No. 4, pp. 100–106.

Vasilenko Y. A., Vashuk F. G., Povkhan I. F. The problem of estimating the complexity of logical trees recognition and a general method for optimizing them, Scientific and technical journal “European Journal of Enterprise Technologies”, 2011, 6/4(54), pp. 24–28.

Vasilenko Y. A., Vashuk F. G., Povkhan I. F. General estimation of minimization of tree logical structures, European Journal of Enterprise Technologies, 2012, 1/4(55), pp. 29–33.

Vasilenko Y. A., Vashuk F. G., Povkhan I. F., Kovach M. Y., Nikarovich O. D. Minimizing logical tree structures in image recognition tasks, European Journal of Enterprise Technologies, 2004, 3(9), pp. 12–16.

Vtogoff P.E. Incremental Induction of Decision Trees, Machine Learning, 1989, No. 4, pp. 161−186.

Subbotin S.A. Construction of decision trees for the case of low-information features, Radio Electronics, Computer Science, Control, 2019, No. 1, pp. 121–130.

Deng H., Runger G., Tuv E. Bias of importance measures for multi-valued attributes and solutions, Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN), 2011, pp. 293–300.

Kamiński B., Jakubczyk M., Szufel P. A framework for sensitivity analysis of decision trees, Central European Journal of Operations Research, 2017, No. 26 (1), pp. 135– 159.

Karimi K., Hamilton H. J. Generation and Interpretation of Temporal Decision Rules, International Journal of Computer Information Systems and Industrial Management Applications, 2011, Vol. 3, pp. 314–323.

Kotsiantis S. B. Supervised Machine Learning: A Review of Classification Techniques, Informatica, 2007, No. 31, pp. 249–268.

Povkhan I. F. Features random logic of the classification trees in the pattern recognition problems, Scientific notes of the Tauride national University. Series: technical Sciences, 2019, Vol. 30(69), No. 5, 2019, pp. 152–161.

Povkhan I. F. 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, 2019, pp. 169–174.

Vasilenko Y. A., Vasilenko E. Y., Povkhan I. F. Defining the concept of a feature in pattern recognition theory, Artificial Intelligence, 2002, No. 4, pp. 512–517.

Subbotin S., Oliinyk A. The dimensionality reduction methods based on computational intelligence in problems of object classification and diagnosis, Recent Advances in Systems, Control and Information Technology, [eds.: R. Szewczyk, M. Kaliczyńska]. Cham, Springer, 2017, pp. 11– 19. (Advances in Intelligent Systems and Computing, Vol. 543).

Subbotin S. A. Methods and characteristics of localitypreserving transformations in the problems of computational intelligence, Radio Electronics, Computer Science, Control, 2014, No. 1, pp. 120–128.

Koskimaki H., Juutilainen I., Laurinen P., Roning J. Twolevel clustering approach to training data instance selection: a case study for the steel industry, Neural Networks: International Joint Conference (IJCNN-2008), Hong Kong, 1-8 June 2008 : proceedings. Los Alamitos, IEEE, 2008, pp. 3044–3049. DOI: 10.1109/ijcnn.2008.4634228

Subbotin S. The neuro-fuzzy network synthesis and simplification on precedents in problems of diagnosis and pattern recognition, Optical Memory and Neural Networks (Information Optics), 2013, Vol. 22, No. 2, pp. 97–103. DOI: 10.3103/s1060992x13020082

Subbotin S.A. Methods of sampling based on exhaustive and evolutionary search, Automatic Control and Computer Sciences, 2013, Vol. 47, No. 3, pp. 113–121. DOI: 10.3103/s0146411613030073

De Mántaras R. L. A distance-based attribute selection measure for decision tree induction, Machine learning, 1991, Vol. 6, No. 1, pp. 81–92.

Deng H., Runger G., Tuv E. Bias of importance measures for multi-valued attributes and solutions, 21st International Conference on Artificial Neural Networks (ICANN), Espoo, 14–17 June 2011 : proceedings. Berlin, Springer-Verlag, 2011, Vol. 2, pp. 293–300.

Painsky A., Rosset S. Cross-validated variable selection in tree-based methods improves predictive performance, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, Vol. 39, No. 11, pp. 2142–2153. DOI:10.1109/tpami.2016.2636831

Miyakawa M. Criteria for selecting a variable in the construction of efficient decision trees, IEEE Transactions on Computers, 1989, Vol. 38, No. 1, pp. 130–141.


GOST Style Citations


1. Quinlan J. R. Induction of Decision Trees / J. R. Quinlan / Machine Learning. – 1986. − № 1. – P. 81–106.

2. Василенко Ю. А. Концептуальна основа систем розпізнавання образів на основі метода розгалуженого вибору ознак / Ю. А. Василенко, Е. Ю. Василенко, І. Ф. Повхан // European Journal of Enterprise Technologies. – 2004. – №7(1). – С. 13–15.

3. Povhan I. General scheme for constructing the most complex logical tree of classification in pattern recognition discrete objects / I. Povhan // Електроніка та інформаційні технології : зб. наук. пр. – Львів, 2019. – Вип. 11. – С. 112–117.

4. Srikant R. Mining generalized association rules / R. Srikant, R. Agrawal // Future Generation Computer Systems. – 1997. – Vol. 13, № 2. – P. 161–180.

5. Hastie T. The Elements of Statistical Learning / T. Hastie, R. Tibshirani, J. Friedman. – Berlin : Springer, 2008. – 746 p.

6. Povhan I. Designing of recognition system of discrete objects / I. Povhan // 2016 IEEE First International
Conference on Data Stream Mining & Processing (DSMP), Lviv, 2016, Ukraine. – Lviv, 2016. – P. 226–231.

7. Повхан І. Ф. Задача загальної оцінки складності максимального побудованого логічного дерева класифікації / І. Ф. Повхан // Вісник національного технічного університету «Харьківський політехнічний інститут». – 2019. – №13. – С. 104–117.

8. Classification and regression trees / [L. L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone]. – Boca Raton : Chapman and Hall/CRC, 1984. – 368 p.

9. Василенко Ю. А. Метод розгалуженого вибору ознак в математичному конструюванні багаторівневих систем розпізнавання образів / Ю. А. Василенко, Е. Ю. Василенко, І. Ф. Повхан // Штучний Інтелект. – 2003. –  №7. – С. 246–249.

10. Повхан І. Ф. Проблема функціональної оцінки навчальної вибірки в задачах розпізнавання дискретних об‘єктів / І. Ф. Повхан // Вчені записки Таврійського національного університету. Серія : технічні науки. – 2018. – Т. 29 (68), № 6. – С. 217–222.

11. Hybrid neuro-neo-fuzzy system and its adaptive learning algorithm / [Y. Bodyanskiy, O. Vynokurova, G. Setlak and I. Pliss] // Computer Sciences and Information Technologies (CSIT) : Xth  Scien. and Tech. Conf., Lviv, 2015. – Lviv, 2015. – P. 111–114.

12. Лавер В. О. Алгоритми побудови логічних дерев класифікації в задачах розпізнавання образів / В. О. Лавер, І. Ф. Повхан // Вчені записки Таврійського національного університету. Серія : технічні науки. 2019. Т. 30 (69), № 4. – С. 100–106.

13. Ващук Ф. Г. Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації / Ф. Г. Ващук, Ю. А. Василенко, І. Ф. Повхан // European Journal of Enterprise  Technologies. –  2011. – 6/4 (54). – С. 24–28.

14. Ващук Ф. Г. Загальна оцінка мінімізації деревоподібних логічних структур / Ф. Г. Ващук, Ю. А. Василенко, І. Ф. Повхан // European Journal of Enterprise  Technologies. – 2012. – 1/4 (55). – С. 29–33.

15. Мінімізація логічних деревоподібних структур в задачах розпізнавання образів / Ю. А. Василенко, Е. Ю. Василенко, М. Й. Ковач, О. Д. Нікарович, І. Ф. Повхан // European Journal of Enterprise  Technologies. – 2004. – 3 (9). – С. 12–16.

16. Vtogoff P. E. Incremental Induction of Decision Trees / P. E. Vtogoff // Machine Learning. – 1989. – № 4. – P. 161−186.

17. Суботин С. А. Построение деревьев решений для случая малоинформативных признаков / С. А. Суботин // Radio Electronics, Computer Science, Control. – 2019. – № 1. – P. 121–130.

18. Deng H. Bias of importance measures for multi-valued attributes and solutions / H. Deng, G. Runger, E. Tuv // Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). – 2011. – P. 293–300.

19. Kamiński B. A framework for sensitivity analysis of decision trees / B. Kamiński, M. Jakubczyk, P. Szufel // Central European Journal of Operations Research. – 2017. – №26 (1). – P. 135–159.

20. Karimi K. Generation and Interpretation of Temporal Decision Rules / K. Karimi, H. J. Hamilton // International Journal of Computer Information Systems and Industrial Management Applications. – 2011. – Vol. 3. – P. 314–323.

21. Kotsiantis S. B. Supervised Machine Learning: A Review of Classification Techniques / S. B. Kotsiantis // Informatica. – 2007. – №31. – P. 249–268.

22. Повхан І. Ф. Особливості випадкових логічних дерев класифікації в задачах розпізнавання образів / І. Ф. Повхан // Вчені записки Таврійського національного університету. Серія : технічні науки. – 2019. – Т. 30 (69). – № 5. – С. 152–161.

23. Повхан І. Ф. Особливості синтезу узагальнених ознак при побудові систем розпізнавання за методом логічного дерева / І. Ф. Повхан // Інформаційні технології та комп’ютерне моделювання ІТКМ-2019 : матеріали міжнародної науково-практичної конференції, Івано-Франківськ, 2019.  – С. 169–174.

24. Василенко Ю. А. Визначення поняття ознаки в теорії розпізнавання образів / Ю. А. Василенко, Е. Ю. Василенко, І. Ф. Повхан // Штучний Інтелект. – 2002. – № 4. – С. 512–517.

25. Subbotin S. The dimensionality reduction methods based on computational intelligence in problems of object classification and diagnosis / S. Subbotin, A. Oliinyk // Recent Advances in Systems, Control and Information Technology / [eds.: R. Szewczyk, M. Kaliczyńska]. – Cham : Springer, 2017. – P. 11–19. – (Advances in Intelligent Systems and Computing, vol. 543).

26. Subbotin S. A. Methods and characteristics of localitypreserving transformations in the problems of computational intelligence / S. A. Subbotin // Radio Electronics, Computer Science, Control. – 2014. – № 1. – P. 120–128.

27. Two-level clustering approach to training data instance selection: a case study for the steel industry / [H. Koskimaki, I. Juutilainen, P. Laurinen, J. Roning] // Neural Networks : International Joint Conference (IJCNN-2008), Hong Kong, 1–8 June 2008 : proceedings. – Los Alamitos : IEEE, 2008. – P. 3044–3049. DOI: 10.1109/ijcnn.2008.4634228 

28. Subbotin S. The neuro-fuzzy network synthesis and simplification on precedents in problems of diagnosis and pattern recognition / S. Subbotin // Optical Memory and Neural Networks (Information Optics). – 2013. – Vol. 22, № 2. – P. 97–103. DOI: 10.3103/s1060992x13020082

29. Subbotin S. A. Methods of sampling based on exhaustive and evolutionary search / S. A. Subbotin // Automatic Control and Computer Sciences. – 2013. – Vol. 47, № 3. – P. 113–121. DOI: 10.3103/s0146411613030073 

30. De Mántaras R. L. A distance-based attribute selection measure for decision tree induction / R. L. De Mántaras // Machine learning. – 1991. – Vol. 6, № 1. – P. 81–92.

31. Deng H. Bias of importance measures for multi-valued attributes and solutions / H. Deng, G. Runger, E. Tuv // 21st International Conference on Artificial Neural Networks (ICANN), Espoo, 14–17 June 2011 : proceedings. – Berlin : Springer-Verlag, 2011. – Vol. 2. – P. 293–300.

32. Painsky A. Cross-validated variable selection in tree-based methods improves predictive performance / A. Painsky, S. Rosset // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2017. – Vol. 39, № 11. – P. 2142– 2153. DOI:10.1109/tpami.2016.2636831

33. Miyakawa M. Criteria for selecting a variable in the construction of efficient decision trees / M. Miyakawa // IEEE Transactions on Computers. – 1989. – Vol. 38, № 1. – P. 130–141.  







Copyright (c) 2020 I. F. Povhan

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.