Частые (замкнутые) множества признаков
Задача поиска частых множеств признаков (frequent itemsets mining) является одной из центральных тем в DataMining. Первоначально необходимость поиска частых множества признаков возникла при выявлении часто покупаемых вместе товаров в базах данных транзакций. Неформально ее можно описать так: дана большая база данных транзакций (покупок); необходимо найти все часто покупаемые наборы товаров, число покупок которых превышает заданный пользователем порог.
В настоящее время набор приложений, в которых основным этапом является построение частых множеств признаков, существенно расширился, например, это поиск ассоциативных правил (см. раздел2.6), сильных правил (strong rules), корреляций, секвенциальных правил, эпизодов (episodes), многомерных образов (multidimensional patterns) и многие другие задачи анализа данных [36].
Среди частых множеств признаков выделяют так называемые частые замкнутые множества признаков, которые полезны для их более компактного представления. Такое представление осуществляется без потерь информации о поддержке собственных частых подмножеств данных частых замкнутых множеств признаков.
Хорошо известным фактом для сообщества DataMining является то, что все замкнутые частые множества признаков (т.е. при
) образуют решетку; эта решетка изоморфна решетке понятий контекста для соответствующей базы данных. Более того, все замкнутые множества признаков образуют в точности решетку содержаний понятий такого контекста [86].Ниже будут даны основные определения; для единства изложения и общности понимания которых будем использовать терминологию, принятую в ФАП. Приведем также классический алгоритм для поиска частых множеств признаков Apriori [9], который не утратил своей актуальности и стал отправной точкой для огромного числа других алгоритмов. Обсудим также связь ФАП и поиска частых замкнутых множеств признаков, которая позволяет рассматривать оба метода в контексте бикластеризации.