Logical classification based on finding regular representative elementary classifiers

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

An approach to the supervised classification problem based on the apparatus of discrete mathematics (logical methods of data analysis) is considered. The possibility of time costs reducing at the stage of correct logical classifier training is investigated. New models of classifiers are proposed. These models are based on finding frequently occurring fragments of a special type in the descriptions of precedents — regular elementary classifiers. Descriptions of classifier models are given using the concepts of logical functions theory. To construct sought fragments, the authors have developed and implemented an original algorithm. The effectiveness of proposed classifier models has been experimentally substantiated and confirmed by theoretical estimates of their training complexity. An upper asymptotic estimate of the typical number of regular elementary classifiers is obtained.

Full Text

Restricted Access

About the authors

N. Dragunov

Federal Research Center «Computer Science and Control» of the Russian Academy of Sciences

Author for correspondence.
Email: nikitadragunovjob@gmail.com
Russian Federation, Moscow

E. Djukova

Federal Research Center «Computer Science and Control» of the Russian Academy of Sciences

Email: nikitadragunovjob@gmail.com
Russian Federation, Moscow

A. Djukova

Federal Research Center «Computer Science and Control» of the Russian Academy of Sciences

Email: nikitadragunovjob@gmail.com
Russian Federation, Moscow

References

  1. Crama Y., Hammer P.L., Ibaraki T. Cause-effect Relationships and Partially Defined Boolean Functions // Ann. Oper. Res. 1988. V. 16. Iss. 1. P. 299–325.
  2. Журавлёв Ю.И., Рязанов В.В., Сенько О.В. Распознавание. Математические методы. Программная система. Практические применения. М.: ФАЗИС, 2006. 159 с.
  3. Масич И.С. Метод оптимальных логических решающих правил для задач распознавания и прогнозирования // Системы управления и информационные технологии. 2019. Т. 75. № 1. С. 31–37.
  4. Бонгард М.М., Вайнцвайг М.Н., Губерман Ш.А., Извекова М.Л., Смирнов М.С. Использование обучающейся программы для выявления нефтеносных пластов // Геология и геофизика. 1966. № 6.
  5. Баскакова Л.В., Журавлёв Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств // ЖВМ и МФ. 1981. Т. 21. № 5. С. 1264–1275.
  6. Дюкова Е.В., Журавлёв Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // ЖВМ и МФ. 2000. Т. 40. №8. С. 1264–1278.
  7. Яблонский С.В., Чегис И.А. О тестах для электрических схем // УМН. 1955. Т. 10. Вып. 4(66). С. 182–184.
  8. Дюкова Е.В., Журавлёв Ю.И. Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений // ЖВМ и МФ. 2018. Т. 58. № 12. С. 2153–2168.
  9. Дюкова Е.В., Инякин С.А. Об асимптотически оптимальном построении тупиковых покрытий целочисленной матрицы // Математические вопросы кибернетики. 2008. № 17. С. 247–262.
  10. Дюкова Е.В., Прокофьев П.А. Об асимптотически оптимальных алгоритмах дуализации // ЖВМ и МФ. 2015. Т. 55. № 5. С. 895–910.
  11. Dragunov N., Djukova E., Djukova. А. Supervised Classification and Finding Frequent Elements in Data // 8th Intern. Conf. on Information Technology and Nanotechnology Proceedings. N.J.: IEEE, 2022. P. 5.
  12. Johnson D.S., Yannakakis M., Papadimitriou C.H. On Generating All Maximal Independent Sets // Information Processing Letters. 1988. V. 27. Iss. 3.
  13. Дюкова Е.В., Песков Н.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания // ЖВМ и МФ. 2002. Т. 42. № 5. С. 741–753.
  14. Дюкова Е. В., Дюкова А. П. О числе решений некоторых специальных задач логического анализа целочисленных данных // Изв. РАН. ТиСУ. 2023. № 5. С. 57–66.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Formula

Download (56KB)
Indexing metadata
3. Fig. 1. Dependence of the training time of models on the number of features when

Download (145KB)
Indexing metadata
4. Fig. 2. Dependence of the training time of models on the number of precedents at

Download (115KB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences