|

Binary Decision Tree Construction using the Hybrid Swarm Intelligence

Authors: Lebedev B.K., Lebedev O.B., Zhiglaty A.A. Published: 02.07.2021
Published in issue: #2(135)/2021  
DOI: 10.18698/0236-3933-2021-2-52-65

 
Category: Informatics, Computer Engineering and Control | Chapter: Theoretical Computer Science, Cybernetics  
Keywords: classification, decision tree, particle swarm, genetic evolution, hybridization, integer parameter values, chromosome structures, directed mutation operator

Solving the problem of a classification model construction is presented in the form of a sequence of considered attributes and values thereof included in the Mk route from the root to the dangling vertex. Decision tree developed interpretation is presented as a pair of chromosomes (Sk, Wk). The Sk chromosome list of genes corresponds to the list of all attributes included in the Mk route in the decision tree. The Wk chromosome gene values correspond to the attribute values included in the Mk route. Unification of data structures, search space and modernization of integrable algorithms was carried out for hybridization. Hybrid algorithm operators are using the integer parameters and synthesize new integer parameter values. Method was developed to account for simultaneous attraction of the αi particle to three xi (t), x*i (t), x*(t) attractors dislocating from the xi (t) position to the xi (t + 1) position. Modified hybrid metaheuristic of the search algorithm is proposed for constructing a classification model using recombination of swarm and genetic search algorithms. The first approach uses genetic algorithm initially and then the particle swarm algorithm. The second approach uses the high-level nesting hybridization method based on combination of genetic algorithm and particle swarm algorithm. The proposed approach to constructing a modified paradigm uses chromosomes with integer parameter values in the indicated hybrid algorithm and operators, which assist chromosomes to evolve according to the rules of particle swarm and genetic search

This work was performed with financial support provided by the Russian Foundation for Basic Research (grant no. 20-07-00260 a)

References

[1] Witten I.H., Frank E., Hall M.A. Data mining. San Francisco, Morgan Kaufmann, 2011.

[2] Zhuravlev Yu.I., Ryazanov V.V., Sen’ko O.V. Raspoznavanie. Matematicheskie metody. Programmnaya sistema. Prakticheskie primeneniya [Recognition. Mathematical methods. Software system. Practical applications]. Moscow, Fazis Publ., 2006.

[3] Berikov V.S., Lbov G.S. [Modern trends in cluster analysis]. Vserossiyskiy konkursnyy otbor obzorno-analiticheskikh statey po prioritetnomu napravleniyu "Informatsionno-telekommunikatsionnye sistemy" [All-Russian competitive selection of review and analytical articles in the priority area of "Information and Telecommunication Systems"]. Moscow, Informika Publ., 2008, art. 126 (in Russ.).

[4] Barsegyan A.A., Kupriyanov M.S., Stepanenko V.V., et al. Metody i modeli analiza dannykh: OLAP i Data Mining [Methods and models of data analysis: OLAP and Data Mining]. St. Petersburg, BKhV-Peterburg Publ., 2004.

[5] Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy [Modern search optimization algorithms. Algorithms inspired by nature]. Moscow, Bauman MSTU Publ., 2014.

[6] Wang X. Hybrid nature-inspired computation method for optimization. Doc. Diss. Helsinki University of Technology, 2009.

[7] Lebedev B.K., Lebedev O.B., Lebedev V.B. Mechanisms of the roving algorithm for finding the solution of the problem of distribution of connections. Programmnye produkty, sistemy i algoritmy [Software Journal: Theory and Applications], 2017, no. 4 (in Russ.). Available at: http://swsys-web.ru/en/mechanisms-of-the-roving-algorithm-for-finding-the-solution-of-the-problem-of-distribution-of-connections.html

[8] Lebedev B.K., Lebedev O.B. Hybrid bioinspired algorithm for solving symbolic regression problem. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, no. 6 (167), pp. 28--41 (in Russ.).

[9] Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika [Search adaptation: theory and practice]. Moscow, FIZMATLIT Publ., 2006.

[10] Lebedev B.K., Lebedev O.B., Lebedeva E.M. Distribution of resources based on hybrid models of swarm intelligence. Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and Technical Journal of Information Technologies, Mechanics and Optics], 2017, vol. 17, no. 6, pp. 1063--1073 (in Russ.). DOI: https://doi.org/10.17586/2226-1494-2017-17-6-1063-1073

[11] Kureychik V.V., Kureychik Vl.Vl. The architecture of hybrid search for design. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, no. 7 (132), pp. 22--27 (in Russ.).

[12] Clerc M. Particle swarm optimization. London, ISTE, 2006.

[13] Lebedev B.K., Lebedev V.B. The evolutionary learning procedure for pattern recognition. Izvestiya TSREU [Izvestiya TRTU], 2004, no. 8 (43), pp. 83--84 (in Russ.).

[14] Lebedev B.K., Lebedev V.B., Lebedev O.B. The solution of the symbolic regression problem by genetic search methods. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, no. 2 (163), pp. 212--225 (in Russ.).

[15] Kennedy J., Eberhart R.C. Particle swarm optimization. Proc. ISNN, 1995, pp. 1942--1948. DOI: https://doi.org/10.1109/ICNN.1995.488968

[16] Lebedev B.K., Lebedev O.B., Lebedeva E.M. Partition a class method alternative collective adaptation. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, no. 7 (180), pp. 89--101 (in Russ.).

[17] Cong J., Romesis M., Xie M. Optimality, scalability and stability study of partitioning and placement algorithms. Proc. ISPD, 2003, pp. 88--94.