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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Библиография и ссылки)
(→Библиография и ссылки)
Строка 52: Строка 52:
#{{книга
#{{книга
|автор = Биркгоф Г.
|автор = Биркгоф Г.
-
 
|заглавие = Теория решеток
|заглавие = Теория решеток
|место = М.
|место = М.
Строка 58: Строка 57:
|год = 1989
|год = 1989
}}
}}
-
 
#{{книга
#{{книга
|автор = B. Ganter, R. Wille
|автор = B. Ganter, R. Wille
Строка 64: Строка 62:
|издательство = Springer
|издательство = Springer
|год = 1999
|год = 1999
-
 
}}
}}
-
 
#{{книга
#{{книга
|автор = Wille R.
|автор = Wille R.
Строка 75: Строка 71:
|издательство = Reidel
|издательство = Reidel
|страницы = 445–470.
|страницы = 445–470.
-
 
}}
}}
 +
{{stub}}
{{stub}}

Версия 19:01, 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.
  2. B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.
  3. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht; Boston:: Reidel, 1982. — С. 445–470..
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»
Личные инструменты