Анализ формальных понятий
Материал из MachineLearning.
(→Библиография и ссылки) |
(→Прикладные задачи) |
||
Строка 46: | Строка 46: | ||
==Прикладные задачи== | ==Прикладные задачи== | ||
+ | |||
+ | АФП нашел широкое применение в информатике (Computer Science), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП: | ||
+ | |||
+ | * Изучение эпистемических (научных) сообществ | ||
+ | * Анализ политических блогов | ||
+ | * Поиск сходства текстовых документов | ||
+ | * Анализ данных генной экспрессии | ||
+ | * Построение таксономий пользователей Интернет-ресурсами | ||
+ | * Формирование рекомендаций (рекомендательные системы) | ||
+ | * Задачи классификации (машинное обучение) по положительным и отрицательным примерам | ||
+ | * Задачи анализа данных медицинской диагностики | ||
+ | * Создание систем ИТ-безопасности | ||
+ | * и т.п. | ||
+ | |||
==Программное обеспечение== | ==Программное обеспечение== | ||
==Библиография и ссылки== | ==Библиография и ссылки== |
Версия 19:20, 30 октября 2010
Анализ формальных понятий (АФП) – прикладная ветвь алгебраической теории решеток.
Содержание |
Основные определения
Определение 1.
Формальный контекст есть тройка
, где
– множество, называемое множеством объектов,
– множество, называемое множеством признаков,
– отношение инцидентности.
Отношение интерпретируется следующим образом: для
,
имеет место
, если объект
обладает признаком
.
Для формального контекста и произвольных
и
определена пара отображений:
которые задают соответствие Галуа между частично упорядоченными
множествами и
, а оператор
является оператором замыкания на
– дизъюнктном объединении
и
, т.е. для произвольного
или
имеют место следующие соотношения:
(экстенсивность),
(идемпотентность),
- если
, то
(изотонность).
Множество называется замкнутым если
.
Определение 2.
Формальное понятие формального контекста есть
пара
, где
,
,
и
. Множество
называется объёмом, а
– содержанием понятия
.
Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста , которое мы будем
обозначать посредством
, частично упорядочено по вложению
объёмов: формальное понятие
является менее общим
(более частным), чем понятие
,
,
если
, что эквивалентно
(
– обобщение
).
В работе Г. Биркгоф, 1989 было показано, что подмножества
произвольного множества, замкнутые относительно заданной на нем
операции замыкания, образуют полную решётку, а в работах
Wille, 1982, Ganter & Wille, 1999 было показано, что множество
всех понятий формального контекста образует полную решётку.
Определение 3.
Множество понятий контекста образует решётку
, где
и
. Такие решётки
называют решётками понятий или решётками Галуа (см. Ganter & Wille, 1999).
Прикладные задачи
АФП нашел широкое применение в информатике (Computer Science), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП:
- Изучение эпистемических (научных) сообществ
- Анализ политических блогов
- Поиск сходства текстовых документов
- Анализ данных генной экспрессии
- Построение таксономий пользователей Интернет-ресурсами
- Формирование рекомендаций (рекомендательные системы)
- Задачи классификации (машинное обучение) по положительным и отрицательным примерам
- Задачи анализа данных медицинской диагностики
- Создание систем ИТ-безопасности
- и т.п.
Программное обеспечение
Библиография и ссылки
- Биркгоф Г. Теория решеток. — М.: Наука, 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..