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

Cover Page

Abstract


This article describes how to use capacity of the theory of formal concept analysis (AFP) to create a mathematical model of information resource focused on people with disabilities. Describes methods of constructing formal concept grids using Galois operators in relation to data socially-oriented geographic information systems (GIS).


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

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

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

Viktor V. Slavsky

Yugra State University

Email: slavsky2004@mail.ru

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

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

Artyom O. Tashkin

FGO «Main state expertise»

Email: anozer_sky@mail.ru

Russian Federation, Khanty-Mansiysk

Chief Specialist FGO «Main state expertise»

References

  1. Игнатов, Д. И. Разработка данных систем совместного пользования ресурсами: от трипонятий к трикластерам [Текст] / Д. И. Игнатов, С. О. Кузнецов, Й. Пульманс // Математические методы распознавания образов: 15-я Всероссийская конференция. Сборник докладов. – М. : МАКС Пресс, 2011. – 618 с.
  2. Семенов, С. П. Анализ информационных ресурсов, направленных на удовлетворение информационных потребностей людей с ограниченными возможностями [Текст] / С. П. Семенов, В. В. Славский, А. О. Ташкин // Вестник НГУ Серия: Информационные технологии. – 2016. – Том 14, Выпуск № 1. – С. 115. – ISSN 1818-7900.
  3. Семенов, С. П. Интерактивная геоинформационная система для маломобильных граждан [Текст] / С. П. Семенов, А. О. Ташкин // Сборник научных статей международной конференции «Ломоносовские чтения на Алтае: фундаментальные проблемы науки и образования». Барнаул, 20–24 октября, 2015. – Барнаул : Изд-во Алт. ун-та, 2015. – 3797 с. – С. 1007–1010.
  4. Семенов, С. П. Методика разработки геоинформационной системы для маломобильных граждан [Электронный ресурс] / С. П. Семенов, А. О. Ташкин // Современные проблемы науки и образования. – 2014. – № 1. Режим доступа : http://www.science-education.ru/115-12206 (дата обращения: 15.03.2016).
  5. Семенов, С. П. Применение фолксономического подхода в разработке социально-ориентированных геоинформационных систем [Текст] / С. П. Семенов, А. О. Ташкин // Вестник ЮГУ. – 2014 г. – № 2 (33). – С. 94–99.
  6. Семенов, С. П. Создание социально-ориентированных геоинформационных систем с применением возможностей фолксономического подхода [Текст] / С. П. Семенов, С. П. Кононенко, А. О. Ташкин // Материалы III международной научно-практической конференции Шестой технологический уклад: механизмы и перспективы развития 13–14 ноября 2015 г, г. Ханты-Мансийск. – Ханты-Мансийск : РИО ЮГУ, 2015.
  7. Ташкин, А. О. Автоматизированная система предоставления услуг населению г. Ханты-Мансийска [Текст] / А. О. Ташкин // Материалы IV Международного IT-форума, г. Екатеринбург. – Екатеринбург : Изд-во Уральского университета, 2011 – С. 192–193.
  8. Ташкин, А. О. Методика создания объединенной геопространственной базы данных для исследования анализа динамики экологических демографических и иных процессов [Текст] / А. О. Ташкин // Материалы Всероссийской научно-практической конференции «Геоинформационные технологии в решении задач рационального природопользования», Югорский научно-исследовательский институт информационных технологий. – Ханты-Мансийск : ООО Изд-во Юграфика, 2013. – 385 с. – С 39–41.
  9. Ташкин, А. О. Разработка геоинформационной системы для решения задач информационного обеспечения людей с ограниченными возможностями [Текст] / А. О. Ташкин, С. П. Семенов // Электронный сборник материалов II Международной научно-практической конференции «Шестой технологический уклад: механизмы и перспективы развития» – Ханты-Мансийск : Изд. Югорского гос. ун-та, 2013. – 149 с. – С. 105–107.

Supplementary files

Supplementary Files Action
1.
Figure 1 - An example of a lattice of formal concepts

Download (24KB) Indexing metadata
2.
Figure 2 - Formal concepts of GIS for MGN

Download (308KB) Indexing metadata

Statistics

Views

Abstract - 294

PDF (Russian) - 176

Cited-By


Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2016 Semenov S.P., Slavsky V.V., Tashkin A.O.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies