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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Основные определения)
Строка 33: Строка 33:
(''более частным''), чем понятие <tex>Y = (C, D)</tex>, <tex>(A, B) \leq (C, D)</tex>,
(''более частным''), чем понятие <tex>Y = (C, D)</tex>, <tex>(A, B) \leq (C, D)</tex>,
если <tex>A\subseteq C</tex>, что эквивалентно <tex>D\subseteq B</tex> (<tex>Y</tex> – ''обобщение'' <tex>X</tex>).
если <tex>A\subseteq C</tex>, что эквивалентно <tex>D\subseteq B</tex> (<tex>Y</tex> – ''обобщение'' <tex>X</tex>).
 +
 +
В работе Г. Биркгоф, 1989 было показано, что подмножества
 +
произвольного множества, замкнутые относительно заданной на нем
 +
операции замыкания, образуют полную решётку, а в работах
 +
Wille, 1982, Ganter & Wille, 1999 было показано, что множество
 +
всех понятий формального контекста <tex>\mathbb{K}</tex> образует полную решётку.
 +
 +
'''Определение 3.'''
 +
Множество понятий контекста <tex>\mathfrak{B}(G,M,I)</tex> образует решётку <tex>\underline{{\mathfrak B}}(G,M,I)
 +
\stackrel{\mathrm{def}}{=} (\mathfrak{B}(G,M,I),\wedge,\vee)</tex>, где <tex>(A_1, B_1)\wedge (A_2, B_2) = (A_1\cap A_2, (A_1\cap A_2)^{\prime})</tex>. и <tex>(A_1, B_1)\vee (A_2, B_2) = ((B_1\cap B_2)^{\prime}, B_1\cap B_2)</tex>. Такие решётки
 +
называют ''решётками понятий'' или ''решётками Галуа'' (см. Ganter & Wille, 1999).
==Прикладные задачи==
==Прикладные задачи==

Версия 18:52, 30 октября 2010

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

Содержание

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

Определение 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 имеют место следующие соотношения:

  1. A\subseteq A^{\prime\prime} (экстенсивность),
  2. A^{\prime\prime\prime\prime} = A^{\prime\prime} (идемпотентность),
  3. если 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).

Прикладные задачи

Программное обеспечение

Библиография и ссылки

  1. Биркгоф Г. Теория решеток. — М.: Наука, 1989.
  1. B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.
machine 17:33, 30 октября 2010 (MSD)
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%BF%D0%BE%D0%BD%D1%8F%D1%82%D0%B8%D0%B9»
Личные инструменты