Formal Concept Analysis (FCA) in socially-oriented geoinformation systems
- Authors: Semenov S.P.1, Slavsky V.V.1, Tashkin A.O.2
-
Affiliations:
- Yugra State University
- FGO «Main state expertise»
- Issue: Vol 12, No 2 (2016)
- Pages: 57-60
- Section: Articles
- Published: 15.06.2016
- URL: https://vestnikugrasu.org/byusu/article/view/7401
- DOI: https://doi.org/10.17816/byusu201612257-60
- ID: 7401
Cite item
Full Text
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).
Keywords
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, 628012Viktor 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, 628012Artyom O. Tashkin
FGO «Main state expertise»
Email: anozer_sky@mail.ru
Chief Specialist FGO «Main state expertise»
Russian Federation, Khanty-MansiyskReferences
- Игнатов, Д. И. Разработка данных систем совместного пользования ресурсами: от трипонятий к трикластерам [Текст] / Д. И. Игнатов, С. О. Кузнецов, Й. Пульманс // Математические методы распознавания образов: 15-я Всероссийская конференция. Сборник докладов. – М. : МАКС Пресс, 2011. – 618 с.
- Семенов, С. П. Анализ информационных ресурсов, направленных на удовлетворение информационных потребностей людей с ограниченными возможностями [Текст] / С. П. Семенов, В. В. Славский, А. О. Ташкин // Вестник НГУ Серия: Информационные технологии. – 2016. – Том 14, Выпуск № 1. – С. 115. – ISSN 1818-7900.
- Семенов, С. П. Интерактивная геоинформационная система для маломобильных граждан [Текст] / С. П. Семенов, А. О. Ташкин // Сборник научных статей международной конференции «Ломоносовские чтения на Алтае: фундаментальные проблемы науки и образования». Барнаул, 20–24 октября, 2015. – Барнаул : Изд-во Алт. ун-та, 2015. – 3797 с. – С. 1007–1010.
- Семенов, С. П. Методика разработки геоинформационной системы для маломобильных граждан [Электронный ресурс] / С. П. Семенов, А. О. Ташкин // Современные проблемы науки и образования. – 2014. – № 1. Режим доступа : http://www.science-education.ru/115-12206 (дата обращения: 15.03.2016).
- Семенов, С. П. Применение фолксономического подхода в разработке социально-ориентированных геоинформационных систем [Текст] / С. П. Семенов, А. О. Ташкин // Вестник ЮГУ. – 2014 г. – № 2 (33). – С. 94–99.
- Семенов, С. П. Создание социально-ориентированных геоинформационных систем с применением возможностей фолксономического подхода [Текст] / С. П. Семенов, С. П. Кононенко, А. О. Ташкин // Материалы III международной научно-практической конференции Шестой технологический уклад: механизмы и перспективы развития 13–14 ноября 2015 г, г. Ханты-Мансийск. – Ханты-Мансийск : РИО ЮГУ, 2015.
- Ташкин, А. О. Автоматизированная система предоставления услуг населению г. Ханты-Мансийска [Текст] / А. О. Ташкин // Материалы IV Международного IT-форума, г. Екатеринбург. – Екатеринбург : Изд-во Уральского университета, 2011 – С. 192–193.
- Ташкин, А. О. Методика создания объединенной геопространственной базы данных для исследования анализа динамики экологических демографических и иных процессов [Текст] / А. О. Ташкин // Материалы Всероссийской научно-практической конференции «Геоинформационные технологии в решении задач рационального природопользования», Югорский научно-исследовательский институт информационных технологий. – Ханты-Мансийск : ООО Изд-во Юграфика, 2013. – 385 с. – С 39–41.
- Ташкин, А. О. Разработка геоинформационной системы для решения задач информационного обеспечения людей с ограниченными возможностями [Текст] / А. О. Ташкин, С. П. Семенов // Электронный сборник материалов II Международной научно-практической конференции «Шестой технологический уклад: механизмы и перспективы развития» – Ханты-Мансийск : Изд. Югорского гос. ун-та, 2013. – 149 с. – С. 105–107.
![](/img/style/loading.gif)