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

Материал из MachineLearning.

Версия от 18:53, 30 октября 2010; Dmitry (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Анализ формальных понятий (АФП) – прикладная ветвь алгебраической теории решеток.

Содержание

1 Основные определения
2 Прикладные задачи
3 Программное обеспечение
4 Библиография и ссылки

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

Определение 1. Формальный контекст $\mathbb{K}$ есть тройка $(G, M, I)$ , где $G$ – множество, называемое множеством объектов, $M$ – множество, называемое множеством признаков, $I\subseteq G\times M$ – отношение инцидентности.

Отношение $I$ интерпретируется следующим образом: для $g\in G$ , $m\in M$ имеет место $gIm$ , если объект $g$ обладает признаком $m$ .

Для формального контекста $\mathbb{K} = (G, M, I)$ и произвольных $A\subseteq G$ и $B\subseteq M$ определена пара отображений:

$A^{\prime} \stackrel{\mathrm{def}}{=} \{m\in M\mid gIm \mbox{ for all } g\in A},$

$B^{\prime} \stackrel{\mathrm{def}}{=} \{g\in G\mid gIm \mbox{ for all } m\in B},$

которые задают соответствие Галуа между частично упорядоченными множествами $(2^G,\subseteq)$ и $(2^M,\subseteq)$ , а оператор $(\cdot)^{\prime\prime}$ является оператором замыкания на $G\dot\cup M$ – дизъюнктном объединении $G$ и $M$ , т.е. для произвольного $A\subseteq G$ или $A\subseteq M$ имеют место следующие соотношения:

$A\subseteq A^{\prime\prime}$ (экстенсивность),
$A^{\prime\prime\prime\prime} = A^{\prime\prime}$ (идемпотентность),
если $A\subseteq C$ , то $A^{\prime\prime}\subseteq C^{\prime\prime}$ (изотонность).

Множество $A$ называется замкнутым если $A^{\prime\prime} = A$ .

Определение 2. Формальное понятие формального контекста $\mathbb{K} = (G, M, I)$ есть пара $(A, B)$ , где $A\subseteq G$ , $B\subseteq M$ , $A^{\prime} = B$ и $B^{\prime} = A$ . Множество $A$ называется объёмом, а $B$ – содержанием понятия $(A, B)$ .

Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.

Множество формальных понятий контекста $\mathbb{K}$ , которое мы будем обозначать посредством $\mathfrak{B}(G,M,I)$ , частично упорядочено по вложению объёмов: формальное понятие $X = (A, B)$ является менее общим (более частным), чем понятие $Y = (C, D)$ , $(A, B) \leq (C, D)$ , если $A\subseteq C$ , что эквивалентно $D\subseteq B$ ( $Y$ – обобщение $X$ ).

В работе Г. Биркгоф, 1989 было показано, что подмножества произвольного множества, замкнутые относительно заданной на нем операции замыкания, образуют полную решётку, а в работах Wille, 1982, Ganter & Wille, 1999 было показано, что множество всех понятий формального контекста $\mathbb{K}$ образует полную решётку.

Определение 3. Множество понятий контекста $\mathfrak{B}(G,M,I)$ образует решётку $\underline{{\mathfrak B}}(G,M,I) \stackrel{\mathrm{def}}{=} (\mathfrak{B}(G,M,I),\wedge,\vee)$ , где $(A_1, B_1)\wedge (A_2, B_2) = (A_1\cap A_2, (A_1\cap A_2)^{\prime})$ и $(A_1, B_1)\vee (A_2, B_2) = ((B_1\cap B_2)^{\prime}, B_1\cap B_2)$ . Такие решётки называют решётками понятий или решётками Галуа (см. Ganter & Wille, 1999).