- Код статьи
- S3034533S0044466925080115-1
- DOI
- 10.7868/S303453325080115
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 65 / Номер выпуска 8
- Страницы
- 1443-1450
- Аннотация
- Исследуются вопросы сложности корректного обучения процедур классификации по прецедентам, базирующихся на применении методов логического анализа данных. Изучаются метрические (количественные) свойства информативных фрагментов признаковых описаний прецедентов в случае, когда число признаков существенно больше числа прецедентов. Приведена асимптотика типичного числа часто встречающихся в описаниях прецедентов фрагментов, различающих объекты из разных классов и называемых правильными представительными элементарными классификаторами. Указана типичная длина искомого фрагмента. Технические основы приводимых оценок опираются на методику получения аналогичных оценок для труднорешаемой дискретной задачи перечисления тупиковых покрытий целочисленной матрицы, формулируемой в работе как задача поиска минимальных нечастых элементарных классификаторов. Новые результаты по изучению сложности реализации логических классификаторов позволяют теоретически обосновать эффективность процедуры обучения на основе поиска правильных представительных элементарных классификаторов и подтвердить перспективность подхода в плане временных затрат. Библ. 17.
- Ключевые слова
- логический анализ данных классификация по прецедентам правильный представительный элементарный классификатор тупиковое покрытие целочисленной матрицы труднорешаемая дискретная задача асимптотически оптимальный алгоритм
- Дата публикации
- 22.05.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 15
Библиография
- 1. Дюкова Е.В., Масляков Г.О., Дюкова А.П. Логические методы корректной классификации данных // Информатика и ее приложения. 2023. Т. 17. Вып. 3. С. 64–70.
- 2. Дюкова Е.В., Журавлев Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. №8. С. 1264–1278.
- 3. Anisimova D., Djukova E., Djukova A. Supervised Classification Problem: Searching for Maximum Patterns // In Proc. of the 2024 X Internat. Conference on Information Technology and Nanotechnology (ITNT), Samara, Russian Federation, 2024. P. 1–4.
- 4. Ковшов Н.В., Моисеев В.Л., Рязанов В.В. Алгоритмы поиска логических закономерностей в задачах распознавания //Ж. вычисл. матем. и матем. физ. 2008. Т. 48. №2. C. 329–344.
- 5. Кузнецов С.О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки // Научно-техническая информация. Сер. 2. Информационные процессы и системы. 1993. №1. С. 17–20.
- 6. Финн В.К. О возможности формализации правдоподобных рассуждений средствами многозначных логик // Всесоюзн. симп. по логике и методологии науки. Киев: Наукова думка, 1976. С. 82–83.
- 7. Gnatyshak D.V., Ignatov D.V., Kuznetsov S.O., Mirkin B.G. Triadic Formal Concept Analysis and triclustering: searching for optimal patterns // Mach Learn. 2015. V. 101. P. 271–302.
- 8. Драгунов Н.А., Дюкова Е.В., Дюкова А.П. Логическая классификация на основе поиска правильных представительных элементарных классификаторов // Изв. РАН. Теория и системы управления. 2024. №4. С. 86–92. https://doi.org/10.31857/S0002338824040027
- 9. Дюкова А.П., Дюкова Е.В. О числе решений некоторых специальных задач логического анализа целочисленных данных // Изв. РАН. Теория и системы управления. 2023. №5. С. 57–66. https://doi.org/10.31857/S0002338823050050
- 10. Дюкова Е.В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости // Ж. вычисл. матем. и матем. физ. 1995. Т. 35. №1. C. 123–134.
- 11. Носков В.Н., Слепян В.А. О числе тупиковых тестов для одного класса таблиц // Кибернетика. 1972. №1. С. 60–65.
- 12. Johnson D., Yannakakis M., Papadimitriou C. On generating all maximal independent sets // Inform. Process. Lett. 1988. V. 27. №3. P. 119–123.
- 13. Fredman M.L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // J. Algorithms. 1996. V. 21. P. 618–628.
- 14. Murakami K., Uno T. Efficient algorithms for dualizing large-scale hypergraphs // Discrete Appl. Math. 2014. V. 170. P. 83–94.
- 15. Boros E., Gurvich V., Elbassioni K., Khachiyan L. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension // Parallel Proc. Lett. 2000. V. 10. №4. Р. 253–266.
- 16. Дюкова Е.В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // Докл. АН СССР. 1977. Т. 233. №4. С. 527–530.
- 17. Дюкова Е.В., Прокофьев П.А. Об асимптотически оптимальных алгоритмах дуализации // Ж. вычисл. матем. и матем. физ. 2015. Т. 55. №5. С. 895–910. https://doi.org/10.7868/S0044466915050105
