RUS  ENG
Полная версия
ЖУРНАЛЫ // Информатика и её применения // Архив

Информ. и её примен., 2022, том 16, выпуск 1, страницы 82–87 (Mi ia778)

О поиске максимальных частых и минимальных нечастых наборов произведения частичных порядков

Н. А. Драгунов, Е. В. Дюкова

Федеральный исследовательский центр «Информатика и управление» Российской академии наук

Аннотация: Исследованы актуальные вопросы снижения временных затрат, возникающие при логическом анализе данных с элементами из декартова произведения конечных частично упорядоченных множеств. Для задачи поиска по базе транзакций максимальных частых и минимальных нечастых наборов произведения частичных порядков предложен оригинальный метод, основанный на решении сложной дискретной задачи, называемой дуализацией над произведением частичных порядков. Метод представляет собой синтез двух других известных методов, один из которых достаточно очевиден, а другой использует идею инкрементального перечисления искомых наборов и поэтому представляет в основном теоретический интерес. Проведено экспериментальное исследование предложенного подхода к решению рассматриваемой задачи в случае произведения конечных цепей, выявлены условия его эффективности и для проводимого анализа данных показана целесообразность применения асимптотически оптимальных алгоритмов дуализации над произведением частичных порядков.

Ключевые слова: максимальные частые наборы, минимальные нечастые наборы, дуализация над произведением частичных порядков, асимптотически оптимальный алгоритм дуализации.

Поступила в редакцию: 15.01.2021

DOI: 10.14357/19922264220112



© МИАН, 2024