FDET Algorithm for Building Space of Classification Patterns in Graph Model

About the authors:

Yurij A. Egorov, Postgraduate Student, University of Tyumen; y.a.egorov@utmn.ru

Marina S. Vorobyova, Cand. Sci. (Tech.), Associate Professor, Department of Software, University of Tyumen; m.s.vorobeva@utmn.ru

Artem M. Vorobyov, Senior Lecturer, Department of Software, University of Tyumen; a.m.vorobev@utmn.ru

Abstract:

This paper considers the graph model of the complex objects classification. Within this model’s framework the authors consider gBoost algorithm for solving the classification problem. A classification problem solution is a set of patterns which are valuable for classification of the training sample objects. A pattern is some subgraph included in at least one graph from the training sample and whose presence or absence allows to classify the object.

The authors propose FDET for classification patterns space building algorithm. The input data are graphs from the training sample. The output data is the subgraph tree with the unique classification patterns space element in each node. The paper provides the input data constraints, algorithm description and computational complicity.

The algorithm was developed and tested for solving the open courses in applied geology and oil and gas business classification problem.

References:

1. Vorobyova M. S., Vorobyov A. M., Egorov Yu. A. 2017. “Postroyeniye raspredelennogo algoritma poiska strukturnyh razlichiy v kategoriyah izomorfizma” [Construction of Distributed Algorithm for Structural Difference in Isomorphism Catecories]. Mezhdunarodniy nauchno-issledovatelskiy zhurnal [International Research Journal], no 4 (58), vol 4, pp. 24-28.
2. Egorov Yu. A. 2016. Modifikaciya algoritma Ulmana dlya mnogoprocessornyh system [Ullmann Algorithm Improvement for Multiprocessor Systems]. Proceedings of the 17th All-Russian Conference for Young Researchers “po matematicheskomu modelirovaniju i informacionnym tehnologiyam” [On Mathematical Modeling and Information Technologies], pp. 86-87.
3. Zakharova I. G., Muravyev I. A. 2015. “Algoritm poiska minimalnogo puti v grafe s dinamicheski izmenyayuzchimisya vesami” [The Algorithm for Finding the Minimum Path in a Graph with Dynamically Changing Weights]. In: TSU Publishing House. Matematicheskoe i informacionnoye modelirovaniye [Mathematical and Informational Modeling], pp. 173-179. Tyumen State University Publishing House.
4. Demiriz A., Bennett K. P., Shawe-Taylor J. 2002. “Linear Programming Boosting via Column Generation”. Machine Learning, vol. 46, pp. 225-254. DOI: 10.1023/A:1012470815092
5. Saigo H., Nowozin S., Kadowaki T. 2009. “gBoost: A Mathematical Programming Approach to Graph Classification and Regression”. Machine Learning, vol. 75, pp. 69-89. DOI: 10.1007/s10994-008-5089-z