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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Ссылки[править | править вики-текст]