Методы бикластеризации для анализа интернет-данных
Дмитрий Игнатов,
кафедра анализа данных и искусственного интеллекта ГУ-ВШЭ
2.1.2. Формальный анализ понятий (ФАП)
есть тройка 
, где 
—
множество, называемое множеством объектов, 
— множество,
называемое множеством признаков,
—
отношение.
Отношение 
интерпретируется следующим образом: для 
, 
имеет место 
, если объект 
обладает признаком 
.
Для формального контекста
и произвольных
и
определена пара отображений:
и
(см.
Раздел 2.1.1), а оператор
является оператором замыкания на
— дизъюнктном
объединении
и
, т.е. для произвольного
или
имеют место следующие
соотношения [1]:
-
(экстенсивность),
-
(идемпотентность),
- если
, то
(изотонность).
Множество 
называется замкнутым, если
[1].
есть
пара 
, где
,
,
и
. Множество
называется объёмом, а 
— содержанием понятия
.Очевидно, что объем и содержание произвольного формального понятия являются замкнутыми множествами.
Множество формальных понятий контекста
, которое мы будем
обозначать посредством
, частично упорядочено по вложению
объёмов: формальное понятие
является менее общим
(более частным), чем понятие
,
,
если
, что эквивалентно
(
— обобщение 
).
В работе [1] было показано, что подмножества
произвольного множества, замкнутые относительно заданной на нем
операции замыкания, образуют полную решётку, а в работах
[83,33] — что множество
всех понятий формального контекста
образует полную решётку.
образует решётку
, где
. и
. Такие решётки
называют решётками понятий, или решётками
Галуа [33].
Любая полная решётка изоморфна решётке понятий некоторого формального
контекста [33]. В качестве объектов этого контекста
нужно выбрать 
-неразложимые элементы, а в качестве признаков
— 
-неразложимые элементы исходной решётки. Тогда объект
в
контексте будет обладать признаком
, если элемент решётки,
соответствующий ,
находится "под" элементом, соответствующим
.
-неразложимым
(
-неразложимым). Редуцированным называется
формальный контекст, являющийся одновременно строчно- и
столбцево-редуцированным.
— формальный контекст и
,
тогда
выражение 
называется импликацией (на множествах
признаков), если
(или
), т.е. все объекты из
, обладающие
множеством признаков
, обладают также множеством признаков
.
Аналогичным образом определяются импликации на множествах объектов.
Наличие импликации
в контексте
соответствует тому, что в
диаграмме решётки
формальное понятие
находится ниже формального понятия
.
Импликации формального контекста удовлетворяют аксиомам
Армстронга [33] для произвольных 
:
;
- если
то
;
- если
и
то
.
Помимо определённых выше однозначных (one-valued) формальных контекстов в анализе формальных понятий изучаются многозначные (many-valued) контексты:
,
где ,
,
— множества (объектов,
признаков и значений признаков, соответственно), а 
— тернарное
отношение
,
задающее значение 
признака ,
причём:
и 
влечёт 
.
Многозначные признаки могут рассматриваться как отображения 
,
таким образом, можно обозначать 
вместо
.
Процедура сведения многозначных контекстов к однозначным называется шкалированием (scaling). Для шкалирования каждый признак многозначного контекста представляется формальным контекстом, называемым шкалой.
многозначного контекста
есть (однозначный) контекст
такой, что
. Объекты в шкале называются значениями
шкалы, а признаки — признаками шкалы.
и шкалы
, тогда производным контекстом будем называть контекст
, где множество признаков
(
) и отношение
и 
.
В нашей работе для построения таксономии алгоритмов использовалось два варианта шкалирования —
порядковое шкалирование и номинальное шкалирование. Порядковая шкала
используется для признаков, значения которых упорядочены относительно
некоторого порядка 
, а обладание объектом некоторым значением
признака влечёт обладание всеми меньшими значениями признака. С помощью номинальной шкалы
представляют несравнимые между собой значения признаков, например, цвет.
Возможные виды шкалирования рассмотрены в [33].