Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

METHODS OF FUZZY SET ANALYSIS AND MODELING OF SOCIAL GRAPHS

Tselykh A.N. 1 Kotov E.M. 1
1 Southern Federal University
This paper is a state-of-the art review of the formal methods of decision-making processes in social systems. We consider the concept of a fuzzy semantic network represented by a fuzzy directed social graph. This model is applied when it is necessary to define a membership of a current situation to this or that class of situations, or to find the nearest situation from the set of situations available in a database. We suggest a model to search for optimal decisions using fuzzy semantic network based on the definition of membership degree of a current situation to this or that class of reference situations on the basis of degree of fuzzy similarity. Under the fuzzy similarity we assume the relation of fuzzy inclusion in possession of transitivity property. The value of relevance score (degree of fuzzy similarity) is computed based on the method of minimal value.
semantic network
social graph

Введение

Семантические сети являются универсальной структурной моделью формализации процесса принятия решений [7]. Особенность семантической сети как модели заключается в целостности системы поиска решений, выполненной на ее основе, позволяющей не разделять базу знаний и механизмы выводов [5].

Базовым функциональным элементом семантической сети служит структура, состоящая из узлов и связывающих их дуг. Каждый узел представляет некоторое понятие, а дуга – отношение между парами понятий. Каждая такая пара отношений определяет некоторое утверждение, являющееся функциональным элементом семантической сети. Узлы помечаются именами соответствующего отношения.

Дуги имеют направленность, благодаря чему между понятиями в рамках некоторого утверждения определено отношение типа «субъект – объект». Каждый узел может быть соединен с любым числом других узлов, в результате чего обеспечивается формирование сети утверждений.

С позиции алгебры логики базовую структуру семантической сети можно рассматривать в качестве эквивалента предиката (дуги) с двумя аргументами (узлами). При выборе различных обозначений для описания отношений можно представлять самые различные совокупности утверждений.

При описании ситуаций в виде семантических сетей особый практический интерес имеет связь вида «являться», отражающая принадлежность объекта к некоторому классу. К другим видам связей, нашедшим конкретное применение при отражении общих представлений об объекте, относятся связи: вида «иметь», указывающая на то, что один объект представляет часть другого, и вида «есть», указывающая на то, что одно понятие служит атрибутом другого. Пользуясь подобными отношениями, можно представлять иерархические совокупности утверждений. Из утверждений можно строить различные иерархические структуры, увеличивая количество понятий и связей. Иерархия, построенная на основе наследования свойств, обеспечивает эффективный способ представления знаний, сокращающий объем информации, которая требуется для описания каждого конкретного утверждения. Это дает возможность упростить процесс обработки знаний, а также извлекать нужную информацию с помощью запросов.

Поиск оптимальных решений с использованием нечетких семантических сетей

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

Выделяют два основных типа запросов: на существование и на перечисление. Запрос на существование не содержит переменных и предусматривает ответ типа «да», если изоморфное вложение графа запроса в семантическую сеть удалось найти, и «нет» в противоположном случае. При обработке перечисляющего запроса происходит поиск всех возможных изоморфных графу запроса подграфов в семантической сети, а также конкретизация переменных.

Частным случаем нечеткой семантической сети, описывающей некоторую совокупность объектов или явлений (ситуаций), является семантическая сеть, рассмотренная в [2].

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

.

Из этого определения следует, что сила связей вершин задана силой наиболее слабой связи. Социальный граф строится экспертом данной предметной области и позволяет в сжатом виде описывать либо все множество объектов или ситуаций ПР, либо лишь эталоны – представители классов ситуаций. Социальный граф задает нечеткое отношение включения на множестве вершин .

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

Логический вывод сводится к определению пути с максимальной оценкой между вершиной – запросом Z, соответствующей классифицируемой ситуации, и всеми вершинами – объектами (заключениями) на социальном графе , образованном присоединением вершины Z, соответствующей текущей ситуации, к социальному графу , задающему поле знаний. При этом присоединяемая вершина Z соединяется с вершинами – концептами , ориентированными ребрами , с весами , соответствующими степеням принадлежности конкретного концепта (признака, свойства, фактора) в описании исходной (классифицируемой) ситуации (поискового образа). Степень соответствия некоторого объекта (заключения, ситуации) , определяется оценкой пути, полученного в результате логического вывода.

Рассмотренная модель применяется в тех случаях, когда необходимо определить принадлежность текущей ситуации к тому или иному классу ситуаций или же для некоторой желаемой ситуации найти ближайшую из множества реально имеющихся в базе данных. Очевидно, что в обоих случаях приходится вычислять степень нечеткого сходства сравниваемых ситуаций. Под нечетким сходством здесь будем понимать отношение нечеткого включения, обладающее свойством транзитивности [3]

.

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

В частности (рис. 1), если признак не вошел в описание ситуации у, но ассоциативно связан с признаком , вошедшим в описание у , где то это означает, что в социальном графе отсутствует ребро , но присутствуют ребра т.е. В силу транзитивности можно в граф ввести ребра с весом

Если же в социальном графе имеется еще одна вершина , связанная с вершиной у ребром с весом , а с вершиной – ребром с весом то в социальный граф можно ввести ребро с весом

Рис. 1. Пример наличия семантически обусловленных ассоциативных связей

Вводя дуги на основе свойства транзитивности, мы фактически применяем операцию транзитивного замыкания.

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

Рис. 2. Граф нечеткого соответствия

Процедура нахождения транзитивного замыкания нечеткого отношения включения выполняется в результате последовательного осуществления операций максиминной композиции матрицы смежности R социального графа и матрицы , где 1, 2, …, и операции объединения по формуле

.

Причем, если для некоторого имеем , то

[3]. (1)

Результат операции определяется функцией принадлежности

(2)

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

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

Способы определения значения нечеткой релевантности

Процедуры сравнения нечетких описаний искомого объекта (ситуации) и эталонных объектов, хранящихся в базе знаний, лежат в основе построения интеллектуальных информационно-поисковых систем [6], систем принятия решений на основе определения сходства ситуаций [1], ситуационных советующих систем [4] и т.п.

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

Чтобы описать правила вывода для поиска, введем следующие предикаты [8]:

Z(z,x) – «запрос z описывается концептом x»; Y(y,x) – «ситуация y описывается концептом x»; L(xi,xj) – «концепт xi связан ассоциативно с концептом xj»; RX(y,x) – «ситуация y релевантна концепту x»; RX(y,z) – «ситуация y релевантна запросу z»; RZX(z,x) – «запрос z релевантен концепту x». Значение истинности для этих предикатов варьируется в интервале [0;1]. В дальнейшем, без потери общности, будем полагать, что запрос описывается лишь одним концептом, хотя на самом деле он описывается несколькими концептами из множества . Предлагается следующее правило поиска:

.

Если запрос и ситуация описываются концептом , то данная ситуация считается релевантной концепту . Правило ограничивает рамки возможных значений истинности предиката интервалом, заданным

. (3)

Затем поиск расширяется по сети, начиная с концепта , в соответствии с правилом:

Даже если ситуация не описывается концептом , ситуация считается настолько релевантной , насколько существует связь между и , а описывается концептом . Это ограничивает возможное значение истинности предиката интервалом

. (4)

Для каждого концепта из множества, связанного с концептом существуют значения истинности, выведенные по последнему правилу. Задавая

получим .

Для определения релевантности ситуации концепту используется соотношение

. (5)

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

Эти значения используются для оценки общей релевантности d ситуации у запросу z. Если предполагать, что концепты не соединены связками и/или, то можно использовать усредненную функцию

(6)

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

(7)

С целью ограничения множества релевантных ситуаций величиной релевантности можно взять уровень , и тогда получим нечеткое множество ситуаций.

.

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

В результате для каждой ситуации получаем нечеткое подмножествоконцептов, описывающее ситуацию , где

.

С другой стороны, запрос (классифицируемая ситуация) также нечетко описывается концептами и задается нечетким множеством

.

Определение значения релевантности (степени нечеткого сходства) ситуации запросу осуществляется по формуле (6). Будем называть рассмотренный способ оценки релевантности методом минимального значения.

Заключение

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

Работа выполнена в рамках гранта Южного федерального университета № 213.01-24/2013-79 «Разработка и исследование методов нечетко-множественного анализа и моделирования социальных графов».

Рецензенты:

Гуда А.Н., д.т.н., профессор, проректор по научной работе, зав. кафедрой «Информатика» ФГБОУ ВПО «Ростовский государственный университет путей сообщения», г. Ростов-на-Дону.

Курейчик В.В., д.т.н., профессор, заведующий кафедрой систем автоматизированного проектирования ФГАОУ ВПО «Южный федеральный университет», г. Ростов-на-Дону.