Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Конференция «Технологии управления данными 2018»
СУБД, платформы, инструменты, реальные проекты.
29 ноября 2018 г.
2008 г.

Методы бикластеризации для анализа интернет-данных

Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ

Назад Содержание Вперёд

2.1.2. Формальный анализ понятий (ФАП)

Определение 2.11   Формальный контекст есть тройка , где — множество, называемое множеством объектов, — множество, называемое множеством признаков, — отношение.

Отношение интерпретируется следующим образом: для , имеет место , если объект обладает признаком .

Для формального контекста и произвольных и определена пара отображений:

которые задают соответствие Галуа между частично упорядоченными множествами и (см. Раздел 2.1.1), а оператор является оператором замыкания на — дизъюнктном объединении и , т.е. для произвольного или имеют место следующие соотношения [1]:
  1. (экстенсивность),
  2. (идемпотентность),
  3. если , то (изотонность).

Множество называется замкнутым, если [1].

Определение 2.12   Формальное понятие формального контекста есть пара , где , , и . Множество называется объёмом, а содержанием понятия .

Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.

Множество формальных понятий контекста , которое мы будем обозначать посредством , частично упорядочено по вложению объёмов: формальное понятие является менее общим (более частным), чем понятие , , если , что эквивалентно ( обобщение ).

В работе [1] было показано, что подмножества произвольного множества, замкнутые относительно заданной на нем операции замыкания, образуют полную решётку, а в работах [83,33] — что множество всех понятий формального контекста образует полную решётку.

Определение 2.13   Множество понятий контекста образует решётку , где . и . Такие решётки называют решётками понятий, или решётками Галуа [33].

Любая полная решётка изоморфна решётке понятий некоторого формального контекста [33]. В качестве объектов этого контекста нужно выбрать -неразложимые элементы, а в качестве признаков — -неразложимые элементы исходной решётки. Тогда объект в контексте будет обладать признаком , если элемент решётки, соответствующий , находится "под" элементом, соответствующим .

Определение 2.14   Строчно- (столбцево-)редуцированным называется такой формальный контекст, в котором всякое объектное (признаковое) понятие является -неразложимым ( -неразложимым). Редуцированным называется формальный контекст, являющийся одновременно строчно- и столбцево-редуцированным.

Определение 2.15   Пусть дан — формальный контекст и , тогда выражение называется импликацией (на множествах признаков), если (или ), т.е. все объекты из , обладающие множеством признаков , обладают также множеством признаков .

Аналогичным образом определяются импликации на множествах объектов. Наличие импликации в контексте соответствует тому, что в диаграмме решётки формальное понятие находится ниже формального понятия .

Импликации формального контекста удовлетворяют аксиомам Армстронга [33] для произвольных :

  1. ;
  2. если то ;
  3. если и то .

Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:

Определение 2.16   Многозначный формальный контекст есть четвёрка , где , , — множества (объектов, признаков и значений признаков, соответственно), а — тернарное отношение , задающее значение признака , причём:     и     влечёт .

Многозначные признаки могут рассматриваться как отображения , таким образом, можно обозначать вместо .

Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.

Определение 2.17   Шкала для признака многозначного контекста есть (однозначный) контекст такой, что . Объекты в шкале называются значениями шкалы, а признаки — признаками шкалы.

Определение 2.18   Пусть задан многозначный контекст и шкалы , тогда производным контекстом будем называть контекст , где множество признаков ( ) и отношение и .

В нашей работе для построения таксономии алгоритмов использовалось два варианта шкалирования — порядковое шкалирование и номинальное шкалирование. Порядковая шкала используется для признаков, значения которых упорядочены относительно некоторого порядка , а обладание объектом некоторым значением признака влечёт обладание всеми меньшими значениями признака. С помощью номинальной шкалы представляют несравнимые между собой значения признаков, например, цвет.

Возможные виды шкалирования рассмотрены в [33].

Назад Содержание Вперёд

Новости мира IT:

Архив новостей

Последние комментарии:

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...