Formal Concept Analysis (FCA) in socially-oriented geoinformation systems

Full Text

В мире уделяется особое внимание решению проблемы создания безбарьерной среды и улучшению качества жизни людей с ограниченными возможностями. Маломобильные граждане сталкиваются с двумя основными проблемами в перемещении: первая связана с физической недоступностью объектов социальной инфраструктуры (далее ОСИ), которая решается установкой конструкций на объекты застройки, вторая проблема заключается в недоступности информации о каждом объекте ОСИ [1, 2].

Цель данной работы состоит в описании методики построения математической модели социально-ориентированной геоинформационной системы (далее ГИС), направленной на удовлетворение информационных потребностей маломобильных групп населения (далее МГН). В исследовании предлагается формализовать систему ОСИ и множества их признаков в терминах теории анализа формальных понятий (АФП) [3, 4].

В ходе исследования были построены бинарные матрицы объектов и их признаков, а затем с помощью операторов Галуа определено множество формальных понятий. Для наглядного представления результатов использовались диаграммы Хассе для построения решеток формальных понятий, объектов и их признаков [5, 6, 7].

Были введены следующие обозначения:

O – Объекты социальной инфраструктуры, ОСИ, к примеру магазины, больницы, муниципальные учреждения, музеи, театры и др.

P – Признаки, описывающие ОСИ, например количество этажей зданий или является ли данный ОСИ жилым зданием.

I – Отношение между ними, например обладает ли определенным признаком тот или иной ОСИ.

I={<oi, pj>}

Пара <oi,pj> показывает, что объект oi обладает признаком pj.

Формальный контекст – это тройка K=(O,P,I).

Множество объектов O и их множество признаков P (формальный контекст) можно представить в виде бинарной матрицы. Имея два множества (объекты и их признаки), а также отношение между ними, с помощью операторов Галуа можно сформировать формальные понятия.

Операторы Галуа:

Для  и .

A' = {p ∈ P | ∀o ∈ A: (o I p)}

B'= {o ∈ O | ∀p ∈ B: (o I p)}

A' – множество признаков, которыми обладают все объекты из множества A.

B' – множество объектов, которые обладают всеми признаками из множества B.

Формальное понятие (A, B) состоит из множества объектов  и множества признаков , таких что B’=A и A’=B.

A – называется объемом формального понятия (все объекты, написанные напротив данного понятия и всех понятий, менее общих, чем оно).

B – называется содержанием понятия формального понятия (признаки, написанные напротив данного понятия и более общих понятий).

 

Таблица 1. Пример бинарной матрицы объектов и их признаков

	P1	P2	P3	P4
O1	1	1	0	1
O2	0	0	1	1
O3	1	1	1	1
O4	0	0	0	1

 

Построение решетки понятий начинается с удаления тривиальных признаков, которыми обладают все объекты (P4), а также тех объектов, которые не обладают ни одним из рассматриваемых нетривиальных признаков (O4). В результате такой редукции бинарная матрица приобретает вид:

 

Таблица 2. Редуцированная бинарная матрица объектов и их признаков

	P1	P2	P3
O1	1●	1●	0
O2	0	0	1●
O3	1●●	1●●	1●●

 

Затем находятся формальные понятия, то есть группы объектов и признаков взаимно плотно определяющие друг друга. В матрице контекста формальные понятия представляют собой максимальные подматрицы, состоящие из единиц, в данном случае максимальные подматрицы ([o1, o3], [p1, p2]) и ([o2, o3], [p3]). Формальное понятие с подписью O3 имеет объем [o1, o3] и содержание [p1, p2, p3]. В Таблице 3 формальные понятия помечены фиолетовым, красным и зеленым цветом, а также представлены на рисунке 1 с помощью диаграмм Хассе.

 

Рисунок 1 – Пример решетки формальных понятий

 

Каждая вершина решетки – это формальное понятие. Рядом с понятием пишутся объекты, которых нет в менее общих понятиях (находящихся под данным понятием), и признаки, которых нет в более общих понятиях. Находятся такие формальные понятия алгоритмом «замыкай по одному». Функция начинает работать с самого общего формального понятия, которое содержит все объекты и чаще всего ни одного признака. Затем находятся все остальные понятия рекурсивным добавлением признаков. Объем формального понятия – все объекты, написанные напротив данного понятия и всех понятий, менее общих, чем оно. Содержание формального понятия – признаки, написанные напротив данного понятия и более общих понятий.

Рассмотрим построение решетки формальных понятий на примере множества ОСИ и их признаков ГИС, направленной на удовлетворение информационных потребностей МГН.

 

Таблица 3. Таблица ОСИ и их признаков

№	O – Объекты P – признаки	P1 Здание	P2 Дорога	P3 Социальный	P4 Жилой	P5 Доступный для МГН
O1	Окружная клиническая больница	1	0	1	0	1
O2	ЮГУ	1	0	1	0	1
O3	Торговый центр «Гостиный двор»	1	0	1	0	0
O4	Улица Мира	0	1	1	0	1
O5	Мира, д. 100	1	0	1	1	0
O6	Светофор Красноармейская/Чехова	0	1	1	0	1
O7	Калинина, д. 26	1	0	0	1	1

 

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

 

Рисунок 2 – Формальные понятия ГИС для МГН

 

Представлено теоретическое обоснование подходов к разработке социально-ориен-тированных геоинформационных систем на основе теории АФП посредством создания динамически обновляемого тезауруса знаний и представлений об объектах предметной области и представления в виде решеток формальных понятий. На основании данной методики возможно решение задач отбора необходимых пространственно-ориентированных данных, организации функции интеллектуального поиска и иных задач по информационному обеспечению маломобильных групп населения [8, 9].

About the authors

Sergey P. Semenov

Yugra State University

Author for correspondence.
Email: ssp@ugrasu.ru

Candidate of Physical and Mathematical Sciences, Head of the Department of Сomputer simulation and Information technologies, Institute of Control Systems and Information Technology, Yugra State University

Russian Federation, 16, Chehova street, Khanty-Mansiysk, 628012

Viktor V. Slavsky

Yugra State University

Email: slavsky2004@mail.ru

Doctor of Physical and Mathematical Sciences, Professor of the Department of Higher Mathematics, Institute of Control Systems and Information Technology, Yugra State University

Russian Federation, 16, Chehova street, Khanty-Mansiysk, 628012

Artyom O. Tashkin

FGO «Main state expertise»

Email: anozer_sky@mail.ru

Chief Specialist FGO «Main state expertise»

Russian Federation, Khanty-Mansiysk

References

Supplementary files