Аннотация:
Исследуются вопросы сложности корректного обучения процедур классификации по прецедентам, базирующихся на применении методов логического анализа данных. Изучаются метрические (количественные) свойства информативных фрагментов признаковых описаний прецедентов в случае, когда число признаков существенно больше числа прецедентов. Приведена асимптотика типичного числа часто встречающихся в описаниях прецедентов фрагментов, различающих объекты из разных классов и называемых правильными представительными элементарными классификаторами. Указана типичная длина искомого фрагмента. Технические основы приводимых оценок опираются на методику получения аналогичных оценок для труднорешаемой дискретной задачи перечисления тупиковых покрытий целочисленной матрицы, формулируемой в работе как задача поиска минимальных нечастых элементарных классификаторов. Новые результаты по изучению сложности реализации логических классификаторов позволяют теоретически обосновать эффективность процедуры обучения на основе поиска правильных представительных элементарных классификаторов и подтвердить перспективность подхода в плане временных затрат.
Библ. 17.
Ключевые слова:
логический анализ данных, классификация по прецедентам, правильный представительный элементарный классификатор, тупиковое покрытие целочисленной матрицы, труднорешаемая дискретная задача, асимптотически оптимальный алгоритм.
УДК:519.7
Поступила в редакцию: 18.03.2025 Принята в печать: 22.05.2025
