Article

Article title ANT ALGORITHMS BUILD A BINARY DECISION TREE
Authors B.K. Lebedev, O.B. Lebedev, E.M. Lebedeva
Section SECTION II. BIOINSPIRED SEARCH
Month, Year 07, 2016 @en
Index UDC
DOI DOI 10.18522/2311-3103-2016-7-7488
Abstract The paper deals with the classification task is to find models or features that describe and distinguish classes in order to be able to predict the class of any given object with known attributes, but an unknown class label. The resulting model is based on a training sample analysis, ie a set of objects whose class label is known for. To solve the problems of classification method based on the construction of a decision tree. The decision tree (DR) – the tree in which each internal vertex there corresponds an attribute, each branch coming out of this summit, corresponds to one of the possible values of the attribute, and each tree leaf is associated a specific class or set of classes of probability. To classify a new object, it is necessary to move the tree top down starting at the root. At each internal node of the tree is selected the branch, which corresponds to the actual value of the corresponding attribute. Reaching the tree leaf, we get the class to which the object belongs according to the classifying rule. We study the dichotomous classification model generated by the algorithm of constructing a binary decision tree. Each node of the tree in the division has only two children. This paper considers the ant algorithm for constructing decision tree based on the use of an effective evaluation function to select an attribute. A general rule for selecting an attribute can be summarized as follows: The selected attribute splits the set so that the result obtained in the subset composed of objects belonging to the same class, or were as close as possible to it. In general, the search for solutions to the problem of constructing the DR team made ants Z = {zk | k = 1,2, ..., l}. At each iteration of the algorithm, each ant zk ant builds his particular solution to the problem of constructing DT Mk route represented in the graph G = (X, U). We use the cyclic (ant-cycle) method of ant systems. In this case, the agents pheromones deposited on the edges and vertices after the complete formation of solutions. In the first phase of each iteration of each k-th ant creates its own route Mk. The process of building the route Mk by agent zk are in-cremental push-pull. At each step t the agent zk uses probabilistic rules for selecting the next vertex (attribute) and edges (the attribute value) to be included in the generated route Mk (t). The memory stores the information agent: number of executed steps – t; Mk(t)route, built in t steps; vertex xi (attribute Ai) selected and included in the route Mk (t) at step t; Afi value of attribute Ai (vertex xi), selected at step t. At the second stage, all the ants lay pheromone. In the third step, the pheromone evaporation. Search for solution of the problem is carried out on a complete solutions-oriented graph G (X, U), where X = {xi | i = 1,2, ..., n} are the set of vertices corresponds to a set of attributes A, U - set of binary edges of a complete graph, the corresponding attribute values. Each pair of vertices (xi, xk) is associated with two binary oriented edges. One binary edge exits from xi and enters to xk, another opposite exits from xk and enters to xi. For all k the binary edge uik, emanating from this node xi, used to simulate two attribute values Ai. Each binary edge may be in one of two states, corresponding to two values of the attribute. Status of edge uik, connecting a pair of vertices (xi, xk), is secured by Vik parameter. If Vik = 1, then uik edge is at the respective first value A1i of attribute Ai. If Vik = 2, then uik edge is at a second value corresponding to attribute Ai. If Vik = 0, then the edge is not included in the route. To account for the assessment of the state of the edges uik (the amount of deferred pheromone), introduced two counters H1ik and H2ik. The decision task of building the DT is represented as a code - a route Mk, including the vertices and "binary" edges with selected states in the decision graph G (X, U). To obtain the required DT decoding procedure. DT is formed sequentially in accordance with the built route M, from the initial input unnamed peaks. At each step t of route M decoding chosen another couple - vertice xi and edge uik which coming out of her, for which the fixed value of the parameter Vik. If Vik = 1, the edge uik corresponds to the first value A1i of attribute Ai. If Vik = 2, the edge uik corresponds to the second value A2i of attribute Ai.The time complexity of this algorithm depends on the lifetime of colonies l (number of iterations) and the number n of the graph and the vertices of ants m, and is defined as O (l * n2 * m).

Download PDF

Keywords Pattern recognition; classification; decision tree; ant colony; making the search graph route.
References 1. Han J., Kamber M. Data mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001.
2. Ian H. Witten, Eibe Frank and Mark A. Hall Data Mining: Practical Machine Learning Tools and Techniques. 3rd Edition. Morgan Kaufmann, 2011.
3. Zhuravlev Yu.I., Ryazanov V.V., Sen'ko O.V. Raspoznavanie. Matematicheskie metody. Pro-grammnaya sistema. Prakticheskie primeneniya [Recognition. Mathematical methods. Software system. Practical application]. Moscow: Fazis, 2006, 159 p.
4. Shlezinger M., Glavach V. Desyat' lektsiy po statisticheskomu i strukturnomu raspoznavaniyu [Ten lectures on statistical and structural recognition]. Kiev: Naukova dumka, 2004, 545 p.
5. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2001. COMPACT - Comparative Package for Clustering Assessment. A free Matlab package, 2006.
6. Berkhin P. Survey of Clustering Data Mining Techniques, Accrue Software, 2002.
7. Radchenko S.G. Metodologiya regressionnogo analiza: monografiya [Methodology regression analysis: monograph]. Kiev: Korniychuk, 2011, 376 p.
8. Berikov V.S., Lbov G.S. Sovremennye tendentsii v klasternom analize [Modern trends in cluster analysis], Vserossiyskiy konkursnyy otbor obzorno-analiticheskikh statey po prioritetnomu napravleniyu «Informatsionno-telekommunikatsionnye sistemy», 2008 [all-Russian competitive selection of survey and analytical articles on priority direction "Information-telecommunication systems", 2008], 26 p.
9. Barsegyan A.A., Kupriyanov M.S., Stepanenko V.V., Kholod I.I. Metody i modeli analiza dannykh: OLAP i Data Mining [Methods and models of data analysis: OLAP and Data Min-ing]. St. Petersburg: BKhV-Peterburg, 2004, 336 p.
10. Lebedev B.K., Lebedev V.B. Evolyutsionnaya protsedura obucheniya pri raspoznavanii obrazov [The evolutionary procedure learning for image recognition], Izvestiya TRTU [Izvestiya TSURE], 2004, No. 8 (43), pp. 83-88.
11. Konar A. Artificial intelligence and soft computing: behavioral and cognitive modeling of the human brain. CRC Press LLC. Boca Raton, Florida, 2000.
12. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika [Search adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 272 p.
13. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya murav'inoy kolonii pri poiske resheniy, interpretiruemykh derev'yami [Modelling of an ant colony adaptive behaviour by search of the decisions interpreted by trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-35.
14. Kureychik V.V., Kureychik V.M., Gladkov L.A., Sorokoletov P.V. Bionspirirovannye metody v optimizatsii [Inspirowanie methods in optimization]. Moscow: Fizmalit, 2009, 384 p.
15. Kureychik V.M., Lebedev B.K., Lebedev O.B. Razbienie na osnove modelirovaniya adaptivnogo povedeniya biologicheskikh sistem [Partitioning based on simulation of adaptive behavior of biological systems], Neyrokomp'yutery: razrabotka, primenenie [Neurocomputers: development, application], 2010, No. 2, pp. 28-34.
16. Lebedev V.B., Lebedev O.B. Roevoy intellekt na osnove integratsii modeley adaptivnogo povedeniya murav'inoy i pchelinoy koloniy [Swarm intelligence on the basis of the adaptive behaviour models integration of the ant and beer colonies], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 41-47.
17. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proektirovaniya [Models of adaptive behaviour of ant colony in task design]. Taganrog: Izd-vo YuFU, 2013.
18. Dorigo M. and Stützle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
19. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Reshenie odnorodnoy raspredelitel'noy zadachi na osnove modeley adaptivnogo povedeniya murav'inoy kolonii [The solution of the homogeneous distribution of tasks based on models of adaptive behavior ant colony], Vestnik RGUPS [Bulletin of the Rostov state transport University], 2016, No. 2 (62), pp. 71-77.
20. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, 2005.

Comments are closed.