Дмитрий Игнатов выступил на вебинаре компании НТР

15 ноября 2022 г. состоялся вебинр компании НТР, в котором принял участие заведующий научно-учебной лабораторией моделей и методов вычислительной прагматики, доцент департамента анализа данных и искусственного интеллекта факультета компьютерных наук Дмитрий Игнатов.

Речь шла о том, как методы майнинга данных и анализа формальных понятий помогают решать комбинаторные задачи из алгебраической теории решеток и устанавливалать эквивалентность между казалось бы не связанными алгебраическими объектами.

15 ноября 2022 г. состоялся вебинар компании НТР, на котором Дмитрий Игнатов представил свой доклад по теме "О криптоморфизме между решетками подмножеств Дэвиса, атомистическими решетками, системами замкнутых множеств при выполнении аксиомы отделимости T1". 

Речь шла о семействах замкнутых множеств (известных как семейства Мура) для случая, когда все одноэлементные множества семейства замкнуты. Задача порождения таких семейств для объектно-признаковых или транзакционных данных хорошо известна в майнинге данных как поиск частых (замкнутых) множеств товаров (Frequent Itemset Mining).  В частности, нами приводится количество таких строгих (включающих пустое множество) и нестрогих семейств для 6 элементов (признаков). Мы также приводим количество таких неэквивалентных семейств Мура относительно всех перестановок базового множества вплоть до n=6. Поиск в OEIS и существующей литературе показал совпадение найденных чисел (с учетом изоморфизма семейств) с числом решеток на основе объединения множеств, полученным Д.М. Дэвисом (последовательность OEIS A235604, до n=5), и c |L_n| (без учета изоморфизма) – числом атомистических решеток на n атомах, найденным С. Мейпс (до n=6), соответственно. Нами  установлено взаимно-однозначные соответствия между этими тремя типами решеток на основе соответствий Галуа и анализа формальных понятий (Formal Concept Analysis). Кратко обсуждаются два использованных перечислительных алгоритма, а также дополнительные результаты их работы наибольший размер семейства множеств без пересечений для n=6, наша гипотеза для n=7, верхняя граница числа атомистических решеток L_n и некоторые структурные свойства L_n, основанные на теории экстремальных решеток.

Рассматриваемые алгоритмы можно использовать в майнинге данных для перечисления всех возможных транзакционных таблиц на n элементах (товарах) и всех частых (замкнутых) множеств товаров в таких таблицах.

Ранее материал излагался в рамках приглашенного доклада на конференции DAMDID 2022.

Оригинальная статья, послужившая основой для рассказа
Статья профессора Дэвиса
Туториал по анализу формальных понятий

Исследуемые автором последовательности OEIS: 
https://oeis.org/A334254
https://oeis.org/A334255
https://oeis.org/A235604
https://oeis.org/A355517

Презентация (PDF, 12,74 Мб)