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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Прикладные задачи)
(→Программное обеспечение)
Строка 67: Строка 67:
==Программное обеспечение==
==Программное обеспечение==
 +
 +
* Concept Explorer – http://conexp.sourceforge.net/
 +
 +
* Lattice Miner – http://sourceforge.net/projects/lattice-miner/
 +
==Библиография и ссылки==
==Библиография и ссылки==

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

В работе Г. Биркгоф, 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), особенно в анализе данных и обработке знаний. Кратко перечислим некоторые прикладные задачи, которые успешно решались различными исследователями и практиками с помощью АФП:

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

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

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

  1. Биркгоф Г. Теория решеток. — М.: Наука, 1989.
  2. B. Ganter, R. Wille Formal Concept Analysis: Mathematical Foundations. — Springer, 1999.
  3. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concepts // Ordered Sets / Ed. by I. Rival. — Dordrecht; Boston:: Reidel, 1982. — С. 445–470..
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»
Личные инструменты