Informatics and Applications
2022, Volume 16, Issue 4, pp 57-62
0N THE C0MPLEXITY 0F L0GICAL CLASSIFICATI0N LEARNING PR0CEDURES
- E. V. Djukova
- A. P. Djukova
Abstract
The issues of integer data logical analysis complexity are investigated. For special tasks of searching in data for frequent and infrequent elements, on the solution of which logical supervised classification procedures are based, asymptotics of a typical number of solutions are given. The technical foundations for obtaining these estimates are based on methods for obtaining similar estimates for intractable discrete problem of constructing (enumerating) irredundant coverings of integer matrix formulated in the paper as the problem of finding "minimal" infrequent elements. The new results mainly concern the study of metric (quantitative) properties of frequent elements. The obtained estimates for the typical number of frequently occurring fragments in precedent descriptions allow one to conclude that the use of algorithms for finding such fragments at the stage of training logical classifiers of the "Kora" type is promising.
[+] References (12)
- Aggarwal, C. 2014. Frequent pattern mining. Heidelberg: Springer. 467 p.
- Weinzweig, M. N. 1973. Algoritm obucheniya raspozna- vaniyu obrazov "Kora" [Algorithm for learning pattern recognition "Kora"]. Algoritmy obucheniya raspozna- vaniyu obrazov [Algorithms for learning pattern recog-nition]. Ed. V. N. Vapnik. Moscow: Sovetskoe radio. 110-116.
- Zhuravlev, Yu. I. 1978. 0b algebraicheskom podkhode k resheniyu zadach raspoznavaniya i klassifikatsii [0n the algebraic approach to solving recognition and classification tasks]. Problemy kibernetiki [Problems of Cybernetics] 33:5-68.
- Baskakova, L., and Yu. Zhuravlev. 1981. A model of recognition algorithms with representative samples and systems of supporting sets. USSR Comp. Math. Math. 21(5):189- 199.
- Djukova, E. V. 1989. Algoritmy raspoznavaniya tipa "Kora": slozhnost' realizatsii i metricheskie svoystva [Kora- type recognition algorithms: Implementation complexity and metric properties]. Raspoznavanie, klassifikatsiya, prognoz [Recognition, classification, and prediction] . Moscow: Nauka. 2:99-125.
- Djukova, E., and Y. Zhuravlev. 2000. Discrete analysis of feature descriptions in recognition problems of high dimensionality. Comp. Math. Math. Phys. 40(8):1214-1227.
- Djukova, E., andN. Peskov. 2002. Search for informative fragments of object descriptions in discrete recognition procedures. Comp. Math. Math. Phys. 42(5):711-723.
- Fredman, M., and L. Khachiyan. 1996. 0n the complexity of dualization of monotone disjunctive normal forms. J. Algorithm. 21(3):618-628.
- Djukova, E., and P. Prokofyev. 2015. Asymptotically optimal dualization algorithms. Comp. Math. Math. Phys. 55(5):891-905.
- Alekseev, V B. 1976. Deciphering of some classes of monotonic many-valued functions. Comp. Math. Math. Phys. 16(1):180-189.
- Noskov, V. N., and V. A. Slepyan. 1972. Number of dead-end tests for a certain class of tables. Cybern. Syst. Anal. 8(1):64-71.
- Dragunov, N., E. Djukova, and A. Djukova. 2022. Supervised classification and finding frequent elements in data. 8th Conference (International) on Information Technology and Nanotechnology Proceedings. Piscataway, NJ: IEEE. 9848521. 5 p. doi: 10.1109/ITNT55410. 2022.9848521.9848521.
[+] About this article
Title
0N THE C0MPLEXITY 0F L0GICAL CLASSIFICATI0N LEARNING PR0CEDURES
Journal
Informatics and Applications
2022, Volume 16, Issue 4, pp 57-62
Cover Date
2022-12-30
DOI
10.14357/19922264220409
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
attribute; frequent elementary fragment; infrequent elementary fragment; monotone dualization; irredundant covering of integer matrix; supervised classification; classifier of "Kora" type
Authors
E. V. Djukova  and A. P. Djukova
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|