Interested Article - Анализ формальных понятий

Анализ формальных понятий (АФП) ( англ. Formal Concept Analysis, FCA ) — ветвь прикладной алгебраической теории решёток , метод анализа данных . Традиционно АФП относят к области концептуальных структур в искусственном интеллекте .

С помощью метода АФП могут быть визуализированы объектно-признаковые зависимости. Это достигается построением диаграммы решётки формальных понятий. Основная математическая идея анализа формальных понятий — возможность построения полной решётки по любому бинарному отношению и формализация описания понятия в виде пары (объём, содержание).

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

Основные определения

Контекстом в АФП называют тройку K = (G, M, I) , где G — множество объектов, M — множество признаков, а отношение I ⊆ G × M говорит о том, какие объекты какими признаками обладают . Для произвольных A ⊆ G и B ⊆ M определены операторы Галуа:

A' = {m ∈ M | ∀ g ∈ A (g I m)},

B' = {g ∈ G | ∀ m ∈ B (g I m)} .

Оператор ″ (двукратное применение оператора ′) является оператором замыкания: он идемпотентен ( A″″ = A″ ), монотонен ( A ⊆ B влечет A″ ⊆ B″ ) и экстенсивен ( A ⊆ A″ ). Множество объектов A ⊆ G, такое , что A″ = A , называется замкнутым. Аналогично для замкнутых множеств признаков — подмножеств множества M . Пара множеств (A, B) , таких, что A ⊆ G, B ⊆ M, A′ = B и B′ = A , называется формальным понятием контекста K . Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A , а замкнутое множество A″ является кластером сходных объектов (с множеством общих признаков A′ ). Отношение ″быть более общим понятием″ задается следующим образом: (A, B) ≥ (C, D) тогда и только тогда, когда A ⊇ C .

Понятия формального контекста K = (G, M, I) , упорядоченные по вложению объемов образуют решетку B (G, M, I) , называемую решеткой понятий. Для визуализации решеток понятий используют так называемые диаграммы Хассе , то есть граф покрытия отношения «быть более общим понятием».

История

Анализ формальных понятий (АФП, англ. Formal Concept Analysis, FCA ) был предложен (англ.) ( в 1981 году (сама работа вышла в 1982 году , также указывается и 1984 год ) , хотя есть более ранние работы французских исследователей Барбю и Монжарде , которые использовали соответствие Галуа и получали то, что называется или решёткой формальных понятий.

В рамках российских исследований научной школы В. К. Финна АФП применялся для быстрого порождения классификационных гипотез в ДСМ-методе .

Алгоритмы и программные инструменты

Существует немало простых и быстрых алгоритмов порождения формальных понятий и построения их решетки для заданного формального контекста. Экспериментальное сравнение алгоритмов может быть найдено в обзоре С. О. Кузнецова и С. А. Объедкова , а в книге Б. К. Гантера и С. А. Объедкова представлены псевдокоды и примеры работы некоторых базовых алгоритмов. Так как число формальных понятий может быть экспоненциально большим от размера входа (числа объектов или признаков), то временная алгоритмическая сложность часто приводится в терминах размера выхода. Решетки понятий, содержащие несколько миллионов элементов могут быть порождены без серьезных затруднений.

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

Большая часть инструментов является свободно-распространяемым программным обеспечением, разработанным в научном сообществе:

ConExp
ToscanaJ
Lattice Miner
Coron
FcaBedrock
GALACTIC

Примечания

Ganter, Bernhard. Formal Concept Analysis: Mathematical Foundations / Bernhard Ganter, Rudolf Wille. — Springer, 1999. — ISBN 3-540-62771-5 .
Wille, Rudolf. Restructuring lattice theory: An approach based on hierarchies of concepts // Ordered Sets. Proceedings of the NATO Advanced Study Institute held at Banff, Canada, August 28 to September 12, 1981. — Springer, 1982. — Vol. 83. — P. 445–470. — ISBN 978-94-009-7800-3 . — doi : . , reprinted in Formal Concept Analysis: 7th International Conference, ICFCA 2009 Darmstadt, Germany, May 21–24, 2009 Proceedings. — Springer, 12 May 2009. — P. 314. — ISBN 978-364201814-5 .
M. Barbut & B. Monjardet. Ordre et Classification (2 tomes). — Paris : HACHETTE UNIVERSITE, 1970.
Kuznetsov, S.; Obiedkov, S. (2002). . Journal of Experimental and Theoretical Artificial Intelligence . 14 (2—3): 189—216. doi : . S2CID .
Ganter, Bernhard. / Bernhard Ganter, Sergei Obiedkov. — Springer, 2016. — ISBN 978-3-662-49290-1 .
Неполный перечень программного обеспечения для АФП можно найти на сайте: . Дата обращения: 10 июня 2010. Архивировано из 16 апреля 2010 года.
. Conexp.sourceforge.net . Дата обращения: 27 декабря 2018. 24 июля 2011 года.
. Toscanaj.sourceforge.net . Дата обращения: 27 декабря 2018. 2 мая 2023 года.
Boumedjout Lahcen and Leonard Kwuida. «Lattice Miner: A Tool for Concept Lattice Construction and Exploration». In: Supplementary Proceeding of International Conference on Formal concept analysis (ICFCA’10), 2010
. Coron.loria.fr . Дата обращения: 27 декабря 2018. 16 августа 2022 года.
. SourceForge.net . Дата обращения: 27 декабря 2018. 30 апреля 2023 года.
. galactic.univ-lr.fr . Дата обращения: 2 февраля 2021. 30 апреля 2023 года.