Informatics and Applications
2025, Volume 19, Issue 4, pp 43-52
REGULAR REPRESENTATIVE ELEMENTARY CLASSIFIERS OVER THE PRODUCT OF PARTIAL PRODUCTS
- N. A. Dragunov
- E. V. Djukova
Abstract
The authors consider the issues of creating algorithmic support for supervised classification problem which is the one of the central tasks of machine learning. Original procedures of logical analysis and classification of integer data represented as a set of elements of Cartesian product of finite partially ordered sets (product of partial orders) are constructed and investigated. At the training stage of the proposed procedures, the search for so-called regular representative elementary classifiers (special fragments in feature descriptions of precedents that distinguish objects belonging to different classes) is performed. An asymptotically optimal algorithm for enumerating the required elementary classifiers over a product of antichains is constructed and the results of its testing on real-world tasks are presented. Theoretical and experimental justifications for the efficiency of the new classification procedures are provided for the case when linear orders on sets of feature values are defined.
The theoretical conclusions are based on the study of the metric (quantitative) properties of the set of regular representative elementary classifiers.
[+] References (21)
- 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.V., G.O. Maslyakov, and P. A. Prokofyev. 2018. Dualization problem over the product of chains: Asymptotic estimates for the number of solutions. Dokl. Math. 98(3):564-567. doi: 10.1134/S1064562418070086. EDN: AQBBNJ.
- Djukova, E.V., G.O. Maslyakov, and P.A. Prokofyev. 2019. On the logical analysis of partially ordered data in the supervised classification problem. Comp. Math. Math. Phys. 59(9):1542-1552. doi: 10.1134/S0965542519090082. EDN: KMZRFX.
- Djukova, A. P., and E. V Djukova. 2023. Number of solutions for some special logical analysis problems of integer data. J. Comput. Sys. Sc. Int. 62(5):817-826. doi: 10.1134/s1064230723050052. EDN: BJDEZZ.
- Djukova, E. V., G. O. Maslyakov, and A. P. Djukova. 2023. Logicheskie metody korrektnoy klassifikatsii dannykh [Logical methods of correct data classification]. Informatika iee Primeneniya - Inform. Appl. 17(3):64-70. doi: 10.14357/19922264230309. EDN: OZHXOX.
- Dragunov, N. A. 2024. O metricheskikh (kolichestvennykh) svoystvakh logicheskikh klassifikatorov [On metric (numerical) properties of logical classifiers]. Trudy ISA RAN [Proceedings of the Institute for Systems Analysis of the Russian Academy of Sciences] 74(4):14-19. doi: 10.14357/20790279240402. EDN: KADXXE.
- Dragunov, N. A., E. V Djukova, and A. P. Djukova. 2024. Logical classification based on finding regular representative elementary classifiers. J. Comput. Sys. Sc. Int. 63(4):634-641. doi:10.1134/S1064230724700461. EDN: EOPZET.
- Hammer, P. L., A. Kogan, A. Simeone, and B. Szedmak. 2004. Pareto-optimal patterns in logical analysis of data. Discrete Appl. Math. 144(1-2):79-102. doi: 10.1016/j.dam.2003.08.013.
- Zhuravlev, Yu. I., V. V. Ryazanov, and O. V. Senko. 2006. Raspoznavanie. Matematicheskie metody. Programmnaya sistema. Prakticheskie primeneniya [Recognition. Mathematical methods. Software system. Practical applications]. Moscow: FAZIS. 159 p. EDN: QMPOMP.
- Masich, I. S. 2019. Metod optimal'nykh logicheskikh reshayushchikh pravil dlya zadach raspoznavaniya i prognozirovaniya [The method of optimal logical decision rules for recognition and prediction problems]. Sistemy upravleniya i informatsionnye tekhnologii [Control Systems and Information Technology] 1(75):31-37. EDN: YYHUWL.
- Anisimova, D., E. Djukova, and A. Djukova. 2024. Supervised classification problem: Searching for maximum patterns. 10th Conference (International Information Technology and Nanotechnology Proceedings. IEEE. Art. 10582366. 4 p. doi: 10.1109/IT- NT60778.2024.10582366. EDN: FDXQWU.
- Finn, V. K. 1976. O vozmozhnosti formalizatsii pravdopodobnykh rassuzhdeniy sredstvami mnogoznachnykh logik [On the possibility of formalizing plausible reasoning by means of multivalued logics]. Vsesoyuzn. simpozium po logike i metodologii nauki [All-Union Symposium on the Logic and Methodology of Science]. Kiev: Naukova dumka. 82-83.
- Wille, R. 1982. Restructuring lattice theory: An approach based on hierarchies of concepts. Ordered sets. Ed. I. Rival. NATO Advanced Study Institutes ser. Dordrecht, Netherlands: Springer. 83:445-470. doi: 110.1007/978- 94009-7798-3.15.
- Gnatyshak, D.V., D. I. Ignatov, S.O. Kuznetsov, and B. G. Mirkin. 2015. Triadic formal concept analysis and triclustering: Searching for optimal patterns. Mach. Learn. 101:271-302. doi: 10.1007/s10994-015-5487-y.
- Djukova, E.V., G.O. Masliakov, and D. S. Ianakov. 2024. Korrektnaya klassifikatsiya po pretsedentam: DSM- metod nad proizvedeniem chastichnykh poryadkov [Correct supervised classification: JSM-method over product of partial orders]. Informatika i ee Primeneniya - Inform. Appl. 18(3):61-68. doi: 10.14357/19922264240308. EDN: ZJHDMY.
- Johnson, D., M. Yannakakis, and C. Papadimitriou. 1988. On generating all maximal independent sets. Inform. Process. Lett. 27(3):119-123. doi: 10.1016/0020- 0190(88)90065-8.
- Fredman, M., and L. Khachiyan. 1996. On the complexity of dualization of monotone disjunctive normal forms. J. Algorithm. 21(3):618-628. doi: 10.1006/jagm.1996.0062.
- Boros, E., V. Gurvich, K. Elbassioni, and L. Khachiyan. 2000. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Processing Letters 10(4):253-266. doi: 10.1142/S0129626400000251.
- Djukova, E.V., and P.A. Prokofjev. 2015. Asymptotically optimal dualization algorithms. Comput. Math. Math. Phys. 55(5):891-905. doi: 10.1134/S0965542515050103. EDN: UFZQRB.
- UC Irvine machine learning repository. Available at: https://archive.ics.uci.edu (accessed November 28, 2025).
- Djukova, A. P, and E.V Djukova. 2024. Recognition of specific genome regions using machine learning methods. Pattern Recognition Image Analysis 34(4):924-929. doi: 10.1134/S1054661824700883. EDN: MBKOZJ.
[+] About this article
Title
REGULAR REPRESENTATIVE ELEMENTARY CLASSIFIERS OVER THE PRODUCT OF PARTIAL PRODUCTS
Journal
Informatics and Applications
2025, Volume 19, Issue 4, pp 43-52
Cover Date
2025-30-12
DOI
10.14357/19922264250405
Print ISSN
1992-2264
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
supervised classification; correct logical classifier; regular representative elementary classifier; partially ordered data; Cartesian product of partial orders; metric (quantitative) properties of the set of elementary classifiers
Authors
N. A. Dragunov  and E. V. Djukova
Author Affiliations
Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
|