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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Основные определения)
Строка 3: Строка 3:
==Основные определения==
==Основные определения==
'''Определение 1.'''
'''Определение 1.'''
-
''Формальный контекст'' <tex>\mathbb{K}</tex> есть тройка <tex>(G, M, I)</tex>, где <tex>G</tex> – множество, называемое множеством ''объектов'', <tex>M</tex> – множество, называемое множеством ''признаков'', <tex>I\subseteq G\times M</tex> отношение инцидентности.
+
''Формальный контекст'' <tex>\mathbb{K}</tex> есть тройка <tex>(G, M, I)</tex>, где <tex>G</tex> – множество, называемое множеством ''объектов'', <tex>M</tex> – множество, называемое множеством ''признаков'', <tex>I\subseteq G\times M</tex> – отношение инцидентности.
Отношение <tex>I</tex> интерпретируется следующим образом: для <tex>g\in G</tex>, <tex>m\in M</tex> имеет место <tex>gIm</tex>, если объект <tex>g</tex> обладает признаком <tex>m</tex>.
Отношение <tex>I</tex> интерпретируется следующим образом: для <tex>g\in G</tex>, <tex>m\in M</tex> имеет место <tex>gIm</tex>, если объект <tex>g</tex> обладает признаком <tex>m</tex>.
Для формального контекста <tex>\mathbb{K} = (G, M, I)</tex> и произвольных <tex>A\subseteq G</tex> и <tex>B\subseteq M</tex> определена пара отображений:
Для формального контекста <tex>\mathbb{K} = (G, M, I)</tex> и произвольных <tex>A\subseteq G</tex> и <tex>B\subseteq M</tex> определена пара отображений:
-
<tex>A^{\prime} = \{m\in M\mid gIm \mbox{ for all } g\in A},</tex>
+
::<tex>A^{\prime} \stackrel{\mathrm{def}}{=} \{m\in M\mid gIm \mbox{ for all } g\in A},</tex>
-
<tex>B^{\prime} = \{g\in G\mid gIm \mbox{ for all } m\in B},</tex>
+
::<tex>B^{\prime} \stackrel{\mathrm{def}}{=} \{g\in G\mid gIm \mbox{ for all } m\in B},</tex>
-
которые задают''соответствие Галуа'' между частично упорядоченными
+
которые задают ''соответствие Галуа'' между частично упорядоченными
-
множествами <tex>(2^G,\subseteq)</tex> и <tex>(2^M,\subseteq)</tex> , а оператор <tex>(\cdot)^{\prime\prime}</tex> является ''оператором замыкания'' на <tex>G\dot\cup M</tex> – дизъюнктном объединении <tex>G</tex> и <tex>M</tex>, т.е. для произвольного <tex>A\subseteq G</tex> или <tex>A\subseteq M</tex> имеют место следующие соотношения~\cite{1989:Birkhoff:TLrus}:
+
множествами <tex>(2^G,\subseteq)</tex> и <tex>(2^M,\subseteq)</tex> , а оператор <tex>(\cdot)^{\prime\prime}</tex> является ''оператором замыкания'' на <tex>G\dot\cup M</tex> – дизъюнктном объединении <tex>G</tex> и <tex>M</tex>, т.е. для произвольного <tex>A\subseteq G</tex> или <tex>A\subseteq M</tex> имеют место следующие соотношения:
#<tex>A\subseteq A^{\prime\prime}</tex> (экстенсивность),
#<tex>A\subseteq A^{\prime\prime}</tex> (экстенсивность),
Строка 17: Строка 17:
#если <tex>A\subseteq C</tex>, то <tex>A^{\prime\prime}\subseteq C^{\prime\prime}</tex> (изотонность).
#если <tex>A\subseteq C</tex>, то <tex>A^{\prime\prime}\subseteq C^{\prime\prime}</tex> (изотонность).
-
Множество <tex>A</tex> называется ''замкнутым'' если <tex>A^{\prime\prime} = A</tex> \cite{1989:Birkhoff:TLrus}.
+
Множество <tex>A</tex> называется ''замкнутым'' если <tex>A^{\prime\prime} = A</tex>.
 +
 
 +
'''Определение 2.'''
 +
''Формальное понятие'' формального контекста <tex>\mathbb{K} = (G, M, I)</tex> есть
 +
пара <tex>(A, B)</tex>, где <tex>A\subseteq G</tex>, <tex>B\subseteq M</tex>, <tex>A^{\prime} = B</tex>
 +
и <tex>B^{\prime} = A</tex>. Множество <tex>A</tex> называется ''объёмом'', а <tex>B</tex>
 +
– ''содержанием'' понятия <tex>(A, B)</tex>.
 +
 
 +
Очевидно, что объем и содержание произвольного формального понятия
 +
являются замкнутыми множествами.
 +
 
 +
Множество формальных понятий контекста <tex>\mathbb{K}</tex>, которое мы будем
 +
обозначать посредством <tex>\mathfrak{B}(G,M,I)</tex>, частично упорядочено по вложению
 +
объёмов: формальное понятие <tex>X = (A, B)</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>).
==Прикладные задачи==
==Прикладные задачи==
==Программное обеспечение==
==Программное обеспечение==
==Библиография и ссылки==
==Библиография и ссылки==
 +
 +
 +
#{{книга
 +
|автор = Биркгоф Г.
 +
 +
|заглавие = Теория решеток
 +
|место = М.
 +
|издательство = Наука
 +
|год = 1989
 +
}}
 +
 +
#{{книга
 +
|автор = B. Ganter, R. Wille
 +
|заглавие = Formal Concept Analysis: Mathematical Foundations
 +
|издательство = Springer
 +
|год = 1999
 +
 +
}}
 +
 +
{{stub}}
[[Участник:Dmitry|machine]] 17:33, 30 октября 2010 (MSD)
[[Участник:Dmitry|machine]] 17:33, 30 октября 2010 (MSD)
[[Категория:Алгебраический анализ данных]]
[[Категория:Алгебраический анализ данных]]

Версия 18:42, 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).

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

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

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

  1. Биркгоф Г. Теория решеток. — М.: Наука, 1989.
  1. B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.
machine 17:33, 30 октября 2010 (MSD)
Источник — «http://www.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»
Личные инструменты