Application of graph models in project management

Full Text

Введение

Задачи управления кадрами организации по степени важности стоят в одном ряду с задачами производства и сбыта продукции. Всё больше компаний становятся проектно-ориентированными, выполняя работы в рамках проектов [1]. Успешность нового проекта в любой сфере деятельности напрямую зависит от компетентности выбранных исполнителей, от того, правильно ли распределены между членами команды отдельные задачи проекта [2]. В данной работе рассматривается задача распределения работ проекта между потенциальными исполнителями и исследуется возможность применения для её решения графовых моделей (ГМ). Использование ГМ позволяет построить структурную схему исследуемой предметной области (ПрО), наглядно и понятно представить то, как связаны и взаимодействуют её объекты. Использование современного математического аппарата при анализе ГМ позволяет устанавливать ранее не известные связи, зависимости и закономерности, отслеживать изменения различных характеристик. Особая ценность ГМ заключается в том, что они предоставляют формальный аппарат для плохоформализуемых задач, требующих учёта как количественных, так и качественных параметров, в т.ч. в условиях неопределённости. В последнее время для решения прикладных задач используют такие ГМ, как байесовские сети, марковские цепи, когнитивные модели (карты), искусственные нейронные сети, графы знаний (ГЗ), онтологии и др. Вероятностные ГМ используются в компьютерном зрении, биоинформатике, принятии решений, робототехнике и др. [3]. Построение ГМ, как правило, осуществляется путём привлечения экспертов. В этом случае ГМ есть субъективное представление эксперта о ПрО в виде схемы взаимодействия её объектов. Кроме привлечения экспертов, ГМ могут выводиться из данных на основе методов машинного обучения (МО) [3].

В данной работе исследуется возможность применения ГМ и ГЗ к решению одной из задач проектного управления.

1. Онтологическая модель проекта

Далее приведены определения ГМ, используемые в работе.

Обобщённый граф или просто граф G состоит из непустого конечного множества V(G) элементов, называемых вершинами, и конечного семейства E(G) пар (не обязательно различных) элементов из V(G),  именуемых рёбрами; использование слова «семейство» допускает существование кратных рёбер. Если пары вершин семейства E(G) не упорядочены, то граф называется неориентированным, если упорядочены – ориентированным графом (орграфом). B простом графе имеется не более одного ребра, соединяющего пару вершин, а также отсутствуют петли (рёбра, соединяющие вершину с самой собой) [4].

ГЗ – это орграф, который может содержать кратные рёбра и петли, каждое из рёбер относится к одному из возможных типов; каждому заданному типу ребра соответствует некоторое отношение между объектами ПрО, а вершинам – объекты ПрО.

Онтология – это формальная, явная спецификация общей концептуализации, состоящая  из иерархии понятий ПрО, связей между ними и ограничений, которые действуют в рамках этой модели. Термин «онтология» связывают с термином «ГЗ», поскольку при наполнении онтологии экземплярами происходит её превращение в ГЗ [5].

Онтология есть кортеж , где L – лексикон, т.е. множество терминов понятий ($L^C$), отношений ($L^P$), атрибутов ($L^A$), значений атрибутов ($L^{VA}$); $C$ – множество понятий; $P=C\times C$ – множество отношений между понятиями; $A=C\times L^{VA}$ – множество атрибутов понятий; $F=L^C\to C$ – функция связи лексикона с понятиями; $G=L^P\to P$ – функция связи лексикона с отношениями; $J=L^A\to A$ – функция связи лексикона с атрибутами; $H^C=C\times C$ – таксономическая иерархия классов; $H^P=P\times P$ – иерархия отношений, $I$ – множество экземпляров (понятий единичного объёма) [6].

Применение онтологического подхода позволяет [7, 8]: совместное использование пользователями знаний в рассматриваемой ПрО; установление общей терминологии, определение её смысла и причинно-следственных связей, получение семантического базиса в определении содержания информации, циркулирующей в системе; повторное использование знаний в ПрО; получение логической теории, на основе которой осуществляется вывод новых знаний, явно не заложенных в онтологии и расширяющих её функциональные возможности и класс решаемых задач.

ГМ используются в проектном управлении (например, [9]), в т.ч. в управлении человеческими ресурсами, управлении рисками проекта и т.д. Основная ценность применения онтологических моделей в проектном управлении заключается в том, что подобные модели могут стать основной частью базы знаний интеллектуальной системы поддержки принятия управленческих решений, а также основой системы управления знаниями проектной организации. На основе результатов анализа работ, посвящённых онтологическому моделированию проектной работы [10-12], была разработана онтология проекта. Разработанный ГЗ реализован средствами редактора онтологий Protégé[1], фрагмент иерархии классов онтологии проекта представлен на рисунке 1.

 

Рисунок 1 – Фрагмент иерархии классов онтологии проекта

 

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

Для определения групп оцениваемых компетенций использованы группы компетенций и компетенции инженеров, приведённые в работе [13].

При накоплении достаточного объёма данных о реализуемых проектах, частных работах, результатах научно-исследовательских проектов полученные результаты могут быть использованы при прогнозировании значимости компетенций при подготовке специалистов в соответствующей области, при корректировке соответствующих образовательных программ [14]. Особенно это актуально для ВУЗов, функционирующих в моногородах и обеспечивающих кадрами градообразующие предприятия.

В таблице 1 приведены примеры отношений между некоторыми классами онтологии проекта.

 

Таблица 1 – Примеры отношений между классами онтологии проекта

Класс-субъект	Отношение	Класс-объект
Работа Проекта	Требует Компетенцию	Компетенция
Проект	Включает Работу	Работа Проекта
Работник	Владеет Компетенцией	Компетенция
Работа Проекта	Включает Разработку	Математическая Модель, Компьютерная Модель
Цель Проекта, Математическая Модель	Описывает Объект	Объект
Проект	Имеет Цель	Цель Проекта, Математическая Модель
Работник	Выполняет Работу	Работа Проекта
Проект	Имеет Объект	Объект
Компетенция	Является Родителем Для	Компетенция

 

2. МО и анализ графов

Алгоритмы МО способны обучаться на наборах данных, описывающих исследуемые объекты или процессы и отражающие их свойства и закономерности [15, 16]. Для применения методов МО необходимо иметь векторные представления данных с действительными значениями, т.е. к ГМ можно применить существующие алгоритмы получения векторных представлений их вершин и отношений. Перечень некоторых задач, базирующихся на ГМ рассматриваемой ПрО, которые можно решить с применением методов МО [17], и некоторые возможные применения этих задач для проектного управления представлены ниже.

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

Для построения векторных представлений вершин и отношений простого графа можно использовать такие алгоритмы, как DeepWalk [18], Node2Vec [19], нейросетевые алгоритмы и др. Существуют алгоритмы, которые позволяют каждой вершине и каждому отношению ГЗ ставить в соответствие уникальный вектор (TransE, DistMult, RESCAL и др.) [20]. Алгоритмы отличаются в т.ч. используемой функцией $f\left(x,r,y\right)$ оценки отношения r экземпляров x и y, которая позволяет оценить его правдоподобность; функцией потерь, значение которой минимизируется в процессе обучения модели. Некоторые алгоритмы имеют геометрическую интерпретацию (например, TransE), некоторые алгоритмы не позволяют работать с определёнными свойствами отношений (симметричность, антисимметричность и т.п.).

3. Анализ нового проекта с помощью ГМ и МО

3.1. Онтология и задача распределения работ

В качестве примера рассматривается задача определения возможных исполнителей работ по проекту, исходные данные, требования к исполнителям представлены в виде упрощённого орграфа с типизированными рёбрами (рисунок 2). Данный граф является подграфом онтографа проекта (рисунок 1) и в качестве вершин включает экземпляры объектов ПрО (классов онтологии), а именно таких классов, как Проект, Объект, МатематическаяМодель, Работник, РаботаПроекта, Компетенция.

 

Рисунок 2 – Фрагмент упрощённого орграфа для задачи распределения работы проекта

 

Граф включает завершённые проекты Проект1 и Проект2. Проект3 – это новый проект. Одной из целей Проекта2 и Проекта3 является построение некой модели одного и того же объекта Объект1.

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

3.2 Меры семантической близости в онтологии и задача распределения работ

Для оценки сходства пар объектов в онтологической модели разработаны и используются различные меры семантической близости ($S\left(x,y\right)\in \left[\mathrm{0,1}\right]$), которые позволяют использовать различные смысловые характеристики сравниваемых объектов (понятий, терминов), их свойства (атрибуты и отношения с другими объектами), анализ структуры и взаимное положение в онтологической иерархии [6].

Оценка соответствия работника требованиям к исполнителю работы проекта может быть определена через соотношение количества одинаковых свойств сравниваемых объектов ( $A\cap B$, A и B – множества свойств этих объектов) к общему числу свойств этих объектов ($A\cup B$). В качестве сравниваемых объектов в рассматриваемой задаче могут быть выбраны уже выполненные работы (с известными исполнителями) и новая работа, цели этих работ (в примере это некие модели); ключевые слова (с учётом их преемственности), описывающие работы, модели, компетенции работников. Для поиска одинаковых и/или различных свойств можно построить SPARQL-запросы² и/или правила логического вывода SWRL ³. Для автоматизации расчётов может быть использована библиотека Python Owlready2 ⁴ [21].

3.3. ГМ и задача распределения работ

Для применения алгоритмов получения векторных представлений для простых графов с однородными вершинами и однотипными отношениями необходимо сначала построить такой граф на основе онтологии. Общая схема построения графа и выбора проектной группы представлена на рисунке 3. Первым этапом является формирование неориентированного графа, вершинам которого соответствуют исполнители, а наличие связи между исполнителями означает их участие в одном и/или схожем уже реализованном проекте. Далее необходимо применить один из алгоритмов построения векторных представлений вершин простого графа. Полученные векторные представления потенциальных исполнителей затем могут быть использованы для формирования групп (кластеров) исполнителей c помощью известных алгоритмов кластеризации [16]. Далее осуществляется выбор кластера, исполнители в котором обладают всеми требуемыми компетенциями на достаточном уровне, для этого используются оценки компетенций исполнителей, а также их значимость (на рисунке 3: w_ij  – оценка j-й компетенции i-го исполнителя, z_j – значимость j-й компетенции для проекта; $w_{ij},z_j\in [0;1]$).

 

Рисунок 3 – Общая схема формирования графа исполнителей и выбора проектной группы

 

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

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

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

3.4. ГЗ и задача распределения работ

Пусть для заданного множества объектов ПрО E и множества отношений между этими объектами R построен ГЗ $K\subseteq E\times R\times E$, который содержит тройки $(h,r,t)\in K$; $h,t\in E$ представляют соответственно субъект («голова») и объект («хвост») отношения $r\in R$, которое описывает некоторое взаимодействие между объектами ПрО [20]. Задача предсказания связи определяется как предсказание субъекта или объекта для троек (?, r, t) или (h, r, ?) соответственно. Так, в примере на рисунке 2 определяется наиболее вероятный субъект в тройке (?, «ВыполняетРаботу», «Работа3»).

Каждый алгоритм построения векторных представлений элементов графа использует некоторую функцию оценки отношения $f:E\times R\times E\to R$, позволяющую оценить правдоподобность тройки $(h,r,t)\in K$. Эта оценка должна в идеале принимать максимальные значения для $(h,r,t)\in K$ и минимальные для $(h,r,t)\notin K$. Например, алгоритмы RESCAL и DistMult, основанные на факторизации разреженного тензора смежности ГЗ [17], моделируют объекты в виде векторов $h,t{\in }^d$, а отношения – в виде матриц $W_r\in R^{d\times d}$, в DistMult эти матрицы являются диагональными. Функция оценки отношения $(h,r,t)\in K$ задаётся формулой [20]:

$f(h,r,t)=h^T{W}_{r}t=\sum _{i=1}^d\sum _{j=1}^d{w}_{ij}^{\left(r\right)}{h}_i{t}_j$

Обучение модели, как правило, осуществляется путём минимизации некоторой функции потерь, так, в алгоритме DistMult функция потерь может иметь вид [22]:

$L=\sum _{(h,r,t)\in K}\sum _{(h^{\text{'}},r,t^{\text{'}})\in K^{\text{'}}}\max \left\{f(h^{\text{'}},r,t^{\text{'}})-f(h,r,t)+\mathrm{1,}0\right\}$,

где $K^{\text{'}}$ – множество «негативных» троек:

$K^{\text{'}}=\left\{(h^{\text{'}},r,t)|h^{\text{'}}\in E,(h^{\text{'}},r,t)\notin K\right\}\cup \left\{(h,r,t^{\text{'}})|t^{\text{'}}\in E,(h,r,t^{\text{'}})\notin K\right\}$.

В качестве оптимизатора модели может быть использован мини-пакетный стохастический градиентный спуск [22].

Для работы с ГЗ использовались готовые функции библиотеки Python PyKEEN ⁶. После обучения модели (например, DistMult, TransE, ConvE, RotatE) получены оценки различных отношений $f\left(x,r,y\right)$ экземпляров x и y, чем выше оценка, тем больше вероятность того, что рассматриваемое отношение окажется верным. При этом минимальное значение оценки, чтобы отношение было определено как точно верное, отсутствует.

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

Заключение

В работе приведены возможные подходы к применению ГМ при решении задачи распределения работ проекта между потенциальными исполнителями. Рассмотрены онтологии, ГЗ и простые графы. Выделены возможные направления применения векторного представления ГЗ и простых графов в проектном управлении. Средствами редактора онтологий Protégé реализована онтология проекта. Представление элементов графа в виде числовых векторов позволяет применить к исследованию ПрО методы МО. На примере решения задачи формирования рабочей группы проекта осуществлён выбор исполнителя проектной работы. Все расчёты осуществлены средствами соответствующих функций библиотек Owlready2 и PyKEEN языка Python. Полученные результаты не противоречат ожидаемым экспертным оценкам.

 

¹ Protégé – A free, open-source ontology editor and framework for building intelligent systems. https://protege.stanford.edu/.

² SPARQL 1.1 Query Language. https://www.w3.org/TR/sparql11-query/.

³ SWRL rules - Owlready2 documentation. https://owlready2.readthedocs.io/en/latest/rule.html.

⁴ Owlready2 documentation. https://owlready2.readthedocs.io/en/latest/.

⁵ Python3 implementation of the node2vec algorithm. https://github.com/eliorc/node2vec.

⁶ PyKEEN 1.10.0 documentation. https://pykeen.readthedocs.io/en/stable/index.html.

About the authors

Askhat Z. Asanov

Institute of Cybernetics of MIREA, Russian Technological University

Author for correspondence.
Email: asanov@mirea.ru
ORCID iD: 0000-0001-6724-0816
Scopus Author ID: 7003438319

D. Sc. Eng., Professor, Professor of the Automatic Systems Departmentin the Institute of Artificial Intelligence of MIREA, Russian Technological University

Russian Federation, Moscow

Irina Yu. Myshkina

Naberezhnye Chelny Institute (branch) of Kazan (Volga Region) Federal University

Email: mirinau@mail.ru
ORCID iD: 0000-0003-4309-3350
Scopus Author ID: 57189268396
ResearcherId: M-4899-2015

Ph.D., Associate Professor of the Department of Systems Analysis and Informatics of the Naberezhnye Chelny Institute (branch) of Kazan (Volga Region) Federal University

Russian Federation, Naberezhnye Chelny

Larisa Yu. Grudtsyna

Naberezhnye Chelny Institute (branch) of Kazan (Volga Region) Federal University

Email: larisa_u_g@mail.ru
ORCID iD: 0000-0003-1307-6605
Scopus Author ID: 57189270650
ResearcherId: M-6037-2015

Senior Lecturer at the Department of System Analysis and Informatics of the Naberezhnye Chelny Institute (branch) of Kazan (Volga Region) Federal University

Russian Federation, Naberezhnye Chelny

References

Supplementary files