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

Перейти к навигацииПерейти к поиску

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

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

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

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

Контекстом в АФП называют тройку K = (G, M, I), где G — множество объектов, M — множество признаков, а отношение I ⊆ G × M говорит о том, какие объекты какими признаками обладают[1]. Для произвольных 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 год)[2], хотя есть более ранние работы французских исследователей Барбю и Монжарде[3], которые использовали соответствие Галуа и получали то, что называется решёткой Галуа или решёткой формальных понятий.

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

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

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

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

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

Примечания

  1. ↑ Ganter, Bernhard. Formal Concept Analysis: Mathematical Foundations / Bernhard Ganter, Rudolf Wille. — Springer, 1999. — ISBN 3-540-62771-5.
  2. ↑ 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:10.1007/978-94-009-7798-3., reprinted in Formal Concept Analysis: 7th International Conference, ICFCA 2009 Darmstadt, Germany, May 21–24, 2009 Proceedings. — Springer, 2009-05-12. — P. 314. — ISBN 978-364201814-5.
  3. ↑ M. Barbut & B. Monjardet. Ordre et Classification (2 tomes). — Paris : HACHETTE UNIVERSITE, 1970.
  4. ↑ Kuznetsov, S.; Obiedkov, S. (2002). "Comparing Performance of Algorithms for Generating Concept Lattices". Journal of Experimental and Theoretical Artificial Intelligence. 14 (2—3): 189—216. doi:10.1080/09528130210164170. S2CID 10784843. Архивировано 30 апреля 2023. Дата обращения: 30 апреля 2023.
  5. ↑ Ganter, Bernhard. Conceptual Exploration / Bernhard Ganter, Sergei Obiedkov. — Springer, 2016. — ISBN 978-3-662-49290-1. Архивная копия от 30 апреля 2023 на Wayback Machine
  6. ↑ Неполный перечень программного обеспечения для АФП можно найти на сайте: Formal Concept Analysis Software and Applications. Дата обращения: 10 июня 2010. Архивировано из оригинала 16 апреля 2010 года.
  7. ↑ The Concept Explorer. Conexp.sourceforge.net. Дата обращения: 27 декабря 2018. Архивировано 24 июля 2011 года.
  8. ↑ ToscanaJ: Welcome. Toscanaj.sourceforge.net. Дата обращения: 27 декабря 2018. Архивировано 2 мая 2023 года.
  9. ↑ 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
  10. ↑ The Coron System. Coron.loria.fr. Дата обращения: 27 декабря 2018. Архивировано 16 августа 2022 года.
  11. ↑ FcaBedrock Formal Context Creator. SourceForge.net. Дата обращения: 27 декабря 2018. Архивировано 30 апреля 2023 года.
  12. ↑ GALACTIC GAlois LAttices, Concept Theory, Implicational system and Closures. galactic.univ-lr.fr. Дата обращения: 2 февраля 2021. Архивировано 30 апреля 2023 года.

Ссылки