Анализ формальных понятий
Материал из MachineLearning.
(→Основные определения) |
|||
(7 промежуточных версий не показаны.) | |||
Строка 42: | Строка 42: | ||
'''Определение 3.''' | '''Определение 3.''' | ||
Множество понятий контекста <tex>\mathfrak{B}(G,M,I)</tex> образует решётку <tex>\underline{{\mathfrak B}}(G,M,I) | Множество понятий контекста <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> | + | \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). | называют ''решётками понятий'' или ''решётками Галуа'' (см. Ganter & Wille, 1999). | ||
==Прикладные задачи== | ==Прикладные задачи== | ||
+ | |||
+ | АФП нашел широкое применение в информатике (Computer Science), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП: | ||
+ | |||
+ | * Изучение эпистемических (научных) сообществ | ||
+ | * Анализ политических блогов | ||
+ | * Поиск сходства текстовых документов | ||
+ | * Анализ данных генной экспрессии | ||
+ | * Построение таксономий пользователей Интернет-ресурсами | ||
+ | * Формирование рекомендаций (рекомендательные системы) | ||
+ | * Задачи классификации (машинное обучение) по положительным и отрицательным примерам | ||
+ | * Задачи анализа данных медицинской диагностики | ||
+ | * Создание системы менеджмента ИТ-безопасности | ||
+ | * Анализ управления полетами авиарейсов | ||
+ | * Создание системы менеджмента электронной почты | ||
+ | * Создание метапоисковой системы для Интернет-поиска | ||
+ | * Компьютерная лингвистика | ||
+ | * Проектирование баз данных | ||
+ | * Программная инженерия | ||
+ | * и т.п. | ||
+ | |||
==Программное обеспечение== | ==Программное обеспечение== | ||
+ | |||
+ | * Concept Explorer – http://conexp.sourceforge.net/ | ||
+ | |||
+ | * Lattice Miner – http://sourceforge.net/projects/lattice-miner/ | ||
+ | |||
==Библиография и ссылки== | ==Библиография и ссылки== | ||
Строка 52: | Строка 77: | ||
#{{книга | #{{книга | ||
|автор = Биркгоф Г. | |автор = Биркгоф Г. | ||
- | |||
|заглавие = Теория решеток | |заглавие = Теория решеток | ||
|место = М. | |место = М. | ||
Строка 58: | Строка 82: | ||
|год = 1989 | |год = 1989 | ||
}} | }} | ||
- | |||
#{{книга | #{{книга | ||
|автор = B. Ganter, R. Wille | |автор = B. Ganter, R. Wille | ||
Строка 64: | Строка 87: | ||
|издательство = Springer | |издательство = Springer | ||
|год = 1999 | |год = 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 | ||
}} | }} | ||
Строка 72: | Строка 132: | ||
[[Категория:Алгебраический анализ данных]] | [[Категория:Алгебраический анализ данных]] | ||
+ | [[Категория:Энциклопедия анализа данных]] |
Текущая версия
Анализ формальных понятий (АФП) – прикладная ветвь алгебраической теории решеток.
Содержание |
Основные определения
Определение 1.
Формальный контекст есть тройка
, где
– множество, называемое множеством объектов,
– множество, называемое множеством признаков,
– отношение инцидентности.
Отношение интерпретируется следующим образом: для
,
имеет место
, если объект
обладает признаком
.
Для формального контекста и произвольных
и
определена пара отображений:
которые задают соответствие Галуа между частично упорядоченными
множествами и
, а оператор
является оператором замыкания на
– дизъюнктном объединении
и
, т.е. для произвольного
или
имеют место следующие соотношения:
(экстенсивность),
(идемпотентность),
- если
, то
(изотонность).
Множество называется замкнутым если
.
Определение 2.
Формальное понятие формального контекста есть
пара
, где
,
,
и
. Множество
называется объёмом, а
– содержанием понятия
.
Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста , которое мы будем
обозначать посредством
, частично упорядочено по вложению
объёмов: формальное понятие
является менее общим
(более частным), чем понятие
,
,
если
, что эквивалентно
(
– обобщение
).
В работе Г. Биркгоф, 1989 было показано, что подмножества
произвольного множества, замкнутые относительно заданной на нем
операции замыкания, образуют полную решётку, а в работах
Wille, 1982, Ganter & Wille, 1999 было показано, что множество
всех понятий формального контекста образует полную решётку.
Определение 3.
Множество понятий контекста образует решётку
, где
и
. Такие решётки
называют решётками понятий или решётками Галуа (см. 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.