WikiSort.ru - Не сортированное

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

Ссылки

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

Это заготовка статьи об искусственном интеллекте. Вы можете помочь проекту, дополнив её.

В другом языковом разделе есть более полная статья Formal concept analysis (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.

В другом языковом разделе есть более полная статья Formale Begriffsanalyse (нем.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.