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

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (18:37, 22 декабря 2013) (править) (отменить)
 
(13 промежуточных версий не показаны.)
Строка 2: Строка 2:
==Основные определения==
==Основные определения==
 +
'''Определение 1.'''
 +
''Формальный контекст'' <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} \stackrel{\mathrm{def}}{=} \{m\in M\mid gIm \mbox{ for all } g\in A},</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>A\subseteq A^{\prime\prime}</tex> (экстенсивность),
 +
#<tex>A^{\prime\prime\prime\prime} = A^{\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>.
 +
 +
'''Определение 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)
 +
 +
[[Категория:Алгебраический анализ данных]]
 +
[[Категория:Энциклопедия анализа данных]]

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

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

Содержание

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

Определение 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.
  4. 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.
  5. 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.
  6. 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://www.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»
Личные инструменты