Анализ формальных понятий
Материал из 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> имеют место следующие соотношения | + | множествами <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> \ | + | Множество <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.
Формальный контекст есть тройка
, где
– множество, называемое множеством объектов,
– множество, называемое множеством признаков,
– отношение инцидентности.
Отношение интерпретируется следующим образом: для
,
имеет место
, если объект
обладает признаком
.
Для формального контекста и произвольных
и
определена пара отображений:
которые задают соответствие Галуа между частично упорядоченными
множествами и
, а оператор
является оператором замыкания на
– дизъюнктном объединении
и
, т.е. для произвольного
или
имеют место следующие соотношения:
(экстенсивность),
(идемпотентность),
- если
, то
(изотонность).
Множество называется замкнутым если
.
Определение 2.
Формальное понятие формального контекста есть
пара
, где
,
,
и
. Множество
называется объёмом, а
– содержанием понятия
.
Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста , которое мы будем
обозначать посредством
, частично упорядочено по вложению
объёмов: формальное понятие
является менее общим
(более частным), чем понятие
,
,
если
, что эквивалентно
(
– обобщение
).
Прикладные задачи
Программное обеспечение
Библиография и ссылки
- Биркгоф Г. Теория решеток. — М.: Наука, 1989.
- B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.