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

Анализ формальных понятий (АФП) (англ. 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 год), хотя есть более ранние работы французских исследователей Барбю и Монжарде, которые использовали соответствие Галуа и получали то, что называется решёткой Галуа или решёткой формальных понятий.

СсылкиПравить

• С. А. Евтушенко Алгоритмы рисования линейных диаграмм
• Анализ формальных понятий на сайте machinelearning.ru