Detailing fuzzy cognitive map models through clustering and nesting for complex concepts

Full Text

1. ВВЕДЕНИЕ

В последние годы все большую популярность приобретают нечеткие когнитивные карты. Нечеткие когнитивные карты можно определить как тип рекуррентной нейронной сети, несущей в себе основные идеи нечеткой логики. Модели нечетких когнитивных карт особенно полезны для моделирования сложных систем и принятия решений внутри этих систем. Они были использованы в различных областях, например, в анализе влияния социальных аспектов на бездомность [1], в анализе надежности систем [2], для разработки расчетных моделей оснований [3], для расчета эффективности работы банковской системы [5]. Так же нечеткие когнитивные карты зарекомендовали себя как хороший инструмент при моделировании сложных систем [4]. Именно в этом направлении данная работа завивает область применения нечетких когнитивных карт.

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

Основная задача данного исследование – разработка метода, который позволит добавить вложенность в модели нечетких когнитивных карт, позволит более подробно и детально рассматривать изменения сложных концепций за счет повышения их вложенности и позволит представить сложные данные более понятным образом. Вложенность подразумевает возможность углубить понимание и анализ каждой концепции когнитивной карты верхнего уровня, преобразования концепции в отдельную нечеткую когнитивную карту. Для реализации данного, для начала необходимо совместить концепции, на основе сходства между ними в единый кластер. В данном исследовании предлагается использовать метод кластеризации k-средних для решения данной проблемы [7]. Следующей задачей стал поиск основных взаимосвязей между концепциями нечеткой когнитивной карты и определения их весовых коэффициентов. Существуют два эволюционных алгоритма позволяющих достичь необходимого результата. Генетический алгоритм с вещественным кодированием(ГАВК) [8] и генетический алгоритм структурной оптимизации (ГАСО). Данные алгоритмы применяются независимо от уровнял вложенности и обеспечивают выделения основных взаимосвязей между концепциями.

Инновационность данной работы заключается в следующих аспектах.

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

2. НЕЧЕТКИЕ КОГНИТИВНЫЕ КАРТЫ

Нечеткая когнитивная карты напоминает собой ориентированный граф ребра которого могут принимать значения в диапазоне [–1, 1]. Ее концепции подобны узлам графа, а взаимосвязи между ними его ребрам. Основным отличием нечеткой когнитивной карты от графа заключается в том, что взаимосвязи указывают на причинно-следственную связь между концепциями. На рис. 1 представлен пример нечеткой когнитивной карты для изучения влияния различных сфер на проблему национальной безопасности [10].

 

Рис. 1. Влияние различных сфер на проблемы национальной безопасности

Fig. 1. The impact of various spheres on national security issues

 

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

$X_i\left(t+1\right)=F\left[X_i\left(t\right)+\sum _{j=1, j\ne 1}^n{X}_j\left(t\right){\omega }_{j,i}\right],$ (1)

где X_i(t) – значение i-й концепции на t-й итерации;

t – дискретное время;

i, j = 1, 2, … , n;

n – количество концепций;

w_{j, i} – вес, определяющий силу связи между j-м и i-м понятием, принимающий значение в интервале [–1, 1];

F(x) – функция сигмоидального преобразования, нормализующая значения понятия к диапазону [0, 1].

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

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

${\mathrm{fitness}}_p\left({\mathrm{error}}_l\right)=\frac{1}{a·{\mathrm{error}}_l+1},$ (2)

где p – количество особей в популяции, p = 1, … , P;

P – размер популяции;

l – количество поколений, l = 1, … , L;

L – максимальное количество поколений;

a – параметр;

error – ошибка обучения, которую можно описать следующим образом:

${\mathrm{error}}_l=\frac{1}{T}\sum _{t=1}^T{\left(Z\left(t\right)-X\left(t\right)\right)}^2$ (3)

где t = 1, … , T;

T – количество обучающих записей;

X(t) – прогнозируемое значение концепции принятия решения на t-й итерации;

Z(t) – фактическое нормализованное значение концепции принятия решения на t-й итерации.

Генетический алгоритм структурной оптимизации представляет собой частичное расширение алгоритма генетического алгоритма с вещественным кодированием. ГАСО позволяет оптимизировать структуру нечетких когнитивных карт путем отсеивания наименее влияющих на конечный результат концепций и взаимосвязей. Каждая связь в ГАСО представлена вектором с плавающей запятой, содержащим значения весов взаимосвязей между понятиями, и двоичным вектором размера n, содержащим информацию о понятиях, включенных в модель. Оценка модели кандидата основана на новой ошибке обучения. Большое количество понятий и ненулевые соотношения между ними увеличивают сложность карты, что приводит к появлению новой ошибки обучения. Ошибка обучения определяется следующей функцией (4):

${\mathrm{error}}_l^{\text{'}}={\mathrm{error}}_l+b_1\frac{n_r}{n^2}{\mathrm{error}}_l+b_2\frac{n_c}{n}{\mathrm{error}}_l,$ (4)

где error – это тип ошибки обучения;

b₁, b₂ – параметры;

n_r – количество взаимосвязей;

n_c – количество концепций на конкретном уровне вложенности;

n – количество всех понятий.

3. ПРЕДЛАГАЕМЫЙ ПОДХОД К ПОСТРОЕНИЮ ВЛОЖЕННОЙ СТРУКТУРЫ НА ОСНОВЕ НЕЧЕТКИХ КОГНИТИВНЫХ КАРТ

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

3.1. Кластеризация данных

Первым этапом предлагаемого подхода является кластеризация атрибутов данных (понятий) на основе сходства между их значениями с использованием кластеризации по методу k-средних [7]. Он содержит следующие этапы:

1. определение будущего количества кластеров;
2. выведение конечного, искомого результата в отдельный кластер;
3. поиск расстояния между значениями концепция и выделенными из доступных данных центрами кластера:

$d\left(A, C\right)=\sqrt{\sum _{t=1}^T\left(x_A\left(t\right)-x_C\left(t\right)\right)}$

где t = 1, … , T;

T – количество записей;

x_A(t) – значение понятия A на t-й итерации;

x_C(t) – значение центра кластера C на t-й итерации;

4. выделение ближайших к центру кластера концепций;
5. обновление центров кластера на основе присвоенных им значений;
6. повторение шагов 4–6 до достижения сходимости.

3.2. Основной уровень модели нечеткой когнитивной карты

Далее необходимо построить основную часть модели нечеткой когнитивной карты. На данном этапе не рассматривается вложенность, а происходит именно первоначальное построение.

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

$x_k\left(t\right)=\frac{1}{n_k}\sum _{i=1}^{n_k}{x}_i^k\left(t\right),$ (5)

где t = 1, … , T;

T – количество записей;

x_k(t) – общее значение k-го кластера на t-й итерации;

k = 1, … , K;

K – количество кластеров;

x_i^k(t) – значение i-го понятия, присвоенного k-му кластеру на t-й итерации;

i = 1, … , n_k;

n_k – количество понятий, присвоенных k-му кластеру.

2. Полученные значения необходимо привести к интервалу, используемого для нечетких когнитивных карт. Если не рассматривать модификации нечетких когнитивных карт, то данный интервал [0, 1]. Для получения необходимого результата можно использовать стандартную нормализацию.
3. Построение основной нечеткой когнитивной карты на основе полученных кластеров и их значений.
4. Обучение полученной карты с использованием ГАВК и ГАСО.

3.3. Построение вложенной нечеткой когнитивной карты

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

$Z^p\left(t+1\right)=F\left(Z^p\left(t\right)+\sum _{i=1}^{n_p}{Z}_i\left(t\right){\omega }_{i, o}+\sum _{j=1, j\ne k}^{K-1}{Z}_j\left(t\right){\omega }_{i, o}\right),$

где Z_p(t) – значение выходной концепции на t-й итерации;

t = 1, … , T;

T – количество обучающих записей;

i = 1, 2, … , n_p;

n_p – количество концепций, присвоенных p-му кластеру;

w_{i, o} – вес, определяющий силу взаимосвязи между i-й концепцией и выходной концепцией в p-й модели;

Z_i(t) – значение i-й концепции в p-й модели;

j = 1, 2, … , K – 1;

K – количество кластеров;

w_{j, o} – вес, который определяет силу взаимосвязи между j-й общей концепцией (кластер j) и выходной концепцией в k-й модели;

Z_j(t) – это значение j-й концепции первого уровня на t-й итерации.

Для обучения карт на данном уровне вложенности, так же как и при построении первого уровня модели используются алгоритмы ГАВК и ГАСО.

В качестве эксперимента была взята готовая нечеткая когнитивная карта влияния социальных аспектов на бездомность (рис. 2) [1], и при помощи кластеризации и описанных ранее алгоритмов построена новая когнитивная карта с большей вложенностью (рис. 3).

 

Рис. 2. Влияние социальных факторов на бездомность

Fig. 2. The impact of social factors on homelessness

 

Рис. 3. Оптимизированная когнитивная карта с вложенностью

Fig. 3. Optimized cognitive map with nesting

 

Анализ предложенного подхода к построению вложенных нечетких когнитивных карт был реализован в ISEMK (Интеллектуальной экспертной системе на основе когнитивных карт), программном средстве, разработанном для построения и анализа когнитивных карт. ISEMK – это приложение на C#, которое позволяет пользователям создавать нечеткие когнитивные карты с использованием эволюционных алгоритмов.

4. РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

Приведем наиболее важные преимущества предлагаемой вложенной архитектуры:

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

About the authors

Maxim A. Saenko

MIREA – Russian Technological University

Author for correspondence.
Email: xerokan@mail.ru
SPIN-code: 2783-1881

postgraduate student

Russian Federation, Moscow

Viktor Ya. Tsvetkov

MIREA – Russian Technological University

Email: cvj7@mail.ru
ORCID iD: 0000-0003-1359-9799
SPIN-code: 3430-2415
Scopus Author ID: 000313599799
ResearcherId: J-5446-2013

Dr. Sci. (Eng.), Professor

Russian Federation, Moscow

References

Supplementary files