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

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

(Различия между версиями)

Текущая версия

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

Содержание

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).

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

АФП нашел широкое применение в информатике (Computer Science), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП:

Изучение эпистемических (научных) сообществ
Анализ политических блогов
Поиск сходства текстовых документов
Анализ данных генной экспрессии
Построение таксономий пользователей Интернет-ресурсами
Формирование рекомендаций (рекомендательные системы)
Задачи классификации (машинное обучение) по положительным и отрицательным примерам
Задачи анализа данных медицинской диагностики
Создание системы менеджмента ИТ-безопасности
Анализ управления полетами авиарейсов
Создание системы менеджмента электронной почты
Создание метапоисковой системы для Интернет-поиска
Компьютерная лингвистика
Проектирование баз данных
Программная инженерия
и т.п.

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

Concept Explorer – http://conexp.sourceforge.net/

Lattice Miner – http://sourceforge.net/projects/lattice-miner/

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

Биркгоф Г. Теория решеток. — М.: Наука, 1989.
B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.
Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht; Boston:: Reidel, 1982. — С. 445–470.
Jonas Poelmans, Sergei O. Kuznetsov, Dmitry I. Ignatov, Guido Dedene Formal Concept Analysis in knowledge processing: A survey on models and techniques. // Expert Syst. Appl.. — 2013 T. 40(16). — С. 6601-6623.
Jonas Poelmans, Dmitry I. Ignatov, Sergei O. Kuznetsov, Guido Dedene Formal concept analysis in knowledge processing: A survey on applications // Expert Syst. Appl.. — 2013 T. 40(16). — С. 6538-6560.
Jonas Poelmans, Dmitry I. Ignatov, Stijn Viaene, Guido Dedene, Sergei O. Kuznetsov Text Mining Scientific Papers: A Survey on FCA-Based Information Retrieval Research // (ICDM 2012) Advances in Data Mining. — Berlin Heidelberg: Springer, 2012. — T. Lecture Notes in Computer Science, Volume 7377. — С. 273-287.

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

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»

Категории: Незавершённые статьи | Алгебраический анализ данных | Энциклопедия анализа данных

@@ Строка 3: / Строка 3: @@
 ==Основные определения==
 '''Определение 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>\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> (экстенсивность),
@@ Строка 17: / Строка 17: @@
 #если <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  было показано, что подмножества
+произвольного множества, замкнутые относительно заданной на нем
+операции замыкания, образуют полную решётку, а в работах
+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).
 ==Прикладные задачи==
+АФП нашел широкое применение в информатике (Computer  Science), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП:
+* Изучение эпистемических (научных) сообществ
+* Анализ политических блогов
+* Поиск сходства текстовых документов
+* Анализ данных генной экспрессии
+* Построение таксономий пользователей Интернет-ресурсами
+* Формирование рекомендаций (рекомендательные системы)
+* Задачи классификации (машинное обучение) по положительным и отрицательным примерам
+* Задачи анализа данных медицинской диагностики
+* Создание системы менеджмента ИТ-безопасности
+* Анализ управления полетами авиарейсов
+* Создание системы менеджмента электронной почты
+* Создание метапоисковой системы для Интернет-поиска
+* Компьютерная лингвистика
+* Проектирование баз данных
+* Программная инженерия
+* и т.п.
 ==Программное обеспечение==
+* Concept Explorer – http://conexp.sourceforge.net/
+* Lattice Miner – http://sourceforge.net/projects/lattice-miner/
 ==Библиография и ссылки==
+#{{книга
+|автор        = Биркгоф Г.
+|заглавие     = Теория решеток
+|место        = М.
+|издательство = Наука
+|год          = 1989
+}}
+#{{книга
+|автор        = B. Ganter, R. Wille
+|заглавие     = Formal Concept Analysis: Mathematical Foundations
+|издательство = Springer
+|год          = 1999
+}}
+#{{книга
+|автор        = Wille R.
+|часть        = Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts
+|заглавие     = Ordered Sets / Ed. by I. Rival
+|год          = 1982
+|место        = Dordrecht; Boston:
+|издательство = Reidel
+|страницы     = 445–470
+}}
+#{{книга
+|автор        = Jonas Poelmans, Sergei O. Kuznetsov, Dmitry I. Ignatov, Guido Dedene
+|часть        = Formal Concept Analysis in knowledge processing: A survey on models and techniques.
+|заглавие     = Expert Syst. Appl.
+|год          = 2013
+|том          = 40(16)
+|страницы     = 6601-6623
+|ссылка       = http://www.sciencedirect.com/science/article/pii/S0957417413002935
+}}
+#{{книга
+|автор        = Jonas Poelmans, Dmitry I. Ignatov, Sergei O. Kuznetsov, Guido Dedene
+|часть        = Formal concept analysis in knowledge processing: A survey on applications
+|заглавие     = Expert Syst. Appl.
+|год          = 2013
+|том          = 40(16)
+|страницы     = 6538-6560
+|ссылка       = http://www.sciencedirect.com/science/article/pii/S0957417413002959
+}}
+#{{книга
+|автор        = Jonas Poelmans, Dmitry I. Ignatov, Stijn Viaene, Guido Dedene, Sergei O. Kuznetsov
+|часть        = Text Mining Scientific Papers: A Survey on FCA-Based Information Retrieval Research
+|заглавие     = (ICDM 2012) Advances in Data Mining
+|год          = 2012
+|место        = Berlin Heidelberg
+|издательство = Springer
+|том          = Lecture Notes in Computer Science, Volume 7377
+|страницы     = 273-287
+|ссылка       = http://link.springer.com/chapter/10.1007%2F978-3-642-31488-9_22
+}}
+{{stub}}
 [[Участник:Dmitry|machine]] 17:33, 30 октября 2010 (MSD)
 [[Категория:Алгебраический анализ данных]]
+[[Категория:Энциклопедия анализа данных]]

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

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

Текущая версия

Содержание

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

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

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

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

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты