Объединение Machine Learning и анализа социальных сетей для выявления организационных структур

Machine learning можно рассматривать как приложение искусственного интеллекта, которое предоставляет системам способность автоматически обучаться и совершенствоваться на основе опыта без явного программирования Jordan and Mitchell (2015). Набор инструментов, полученных из области статистики, дает возможность выполнять множество задач, значительно превосходящих человеческие способности или простые алгоритмы в различных дисциплинах, начиная от анализа текста, компьютерного зрения, медицины и других. В machine learning классификация — это подход обучения с учителем, при котором алгоритм обучается на предоставленных ему входных данных, а затем использует это обучение для классификации новых наблюдений. Здесь под обучением с учителем мы подразумеваем предоставление алгоритму примеров объектов, которые были отнесены к определенному классу, и требование к нему разработать метод для адекватной классификации других объектов с неизвестным классом. Для достижения этой цели за последние десятилетия было разработано и настроено множество алгоритмов, таких как логистическая регрессия Hosmer Jr et al. (2013), наивный байесовский классификатор Maron (1961), метод ближайших соседей Altman (1992), Support Vector Machines Cortes and Vapnik (1995), деревья решений Utgoff (1989), случайные леса Breiman (2001) или нейронные сети Ayodele (2010). Каждый из этих методов по-разному подходит к задаче. Что касается методов, используемых в данной работе, деревья решений строят дерево, состоящее из проверок признаков: каждая ветвь представляет результат проверки, а каждый листовой узел представляет метку класса. Случайный лес расширяет концепцию деревьев решений, создавая их множество и выводя класс, который является модой классов отдельных деревьев. О чем можно сказать в отношении этих двух методов, так это о том, что правила классификации прозрачны и легко интерпретируемы. Что касается двух других методов, оцениваемых в этой работе, Support Vector Machine строит гиперплоскость или набор гиперплоскостей в пространстве высокой или бесконечной размерности, которые могут быть использованы для классификации. Нейронные сети пытаются имитировать человеческий мозг с точки зрения того, как информация передается и анализируется. Здесь нейронная сеть основана на совокупности соединенных единиц или узлов, называемых нейронами. Каждое соединение, подобно синапсам в биологическом мозге, может передавать сигнал другим нейронам. Искусственный нейрон, который получает сигнал, затем обрабатывает его и может подавать сигнал нейронам, соединенным с ним. Нейроны сгруппированы в слои, и сигнал, проходящий через слои, преобразуется нейронами в тот, на основе которого на конечном (выходном) слое будет принято решение о принадлежности к классу. Это создает архитектуру нейронной сети. В отличие от деревьев решений и случайных лесов, Support Vector Machines и нейронные сети не так легко интерпретируемы с точки зрения важности признаков Molnar (2019).

Все эти методы объединяет то, что они обычно требуют соблюдения принципа IID, а именно: выборки должны быть независимыми и одинаково распределенными. К сожалению, это не всегда так, особенно когда речь идет о любых данных, связанных с сетями. Например, в социальных сетях люди склонны объединяться в группы по схожим интересам McPherson et al. (2001) или менять свое мнение под влиянием мнения других Friedkin and Johnsen (1990). В этом случае сложно считать выборки IID, поэтому был разработан другой набор подходов: коллективная классификация, которая пытается использовать сетевую структуру данных Sen et al. (2008).

Другой проблемой классификации является то, что экземпляры редко распределены по всем классам равномерно. Эта проблема называется несбалансированными данными, и существует множество методов для ее решения, которые в основном относятся к одной из двух групп: уменьшение выборки и увеличение выборки Sun et al. (2009); Krawczyk (2016). При уменьшении выборки доминирующие группы сокращаются до уровня ранее недопредставленных классов. Напротив, увеличение выборки генерирует синтетические экземпляры, принадлежащие к недопредставленному классу, что приводит к более сбалансированным данным. Одним из наиболее заметных методов увеличения выборки является SMOTE, который основан на ближайших соседях, определяемых по евклидову расстоянию между точками данных в пространстве признаков, и выполняет векторные операции для генерации новых точек данных Chawla et al. (2002); Fernández et al. (2018). Использование этого метода обеспечивает более репрезентативные и менее смещенные выборки по сравнению со случайным увеличением выборки.

В разделе 2.6 можно найти информацию о том, какие алгоритмы классификации были использованы в этой работе, а раздел 2.7 содержит более подробную информацию о том, как мы использовали collective classification для выявления организационной структуры из социальной сети.

Область анализа социальных сетей может быть понята как набор методов, извлекающих знания о человеческих взаимоотношениях на основе связей, которые они формируют — обычно являясь членами социальных сетей различного рода. Эти сети могут относиться к семье, друзьям, компаниям или организациям, сотрудниками или членами которых они являются, либо к социальным сетям, в которых они участвуют. Более формально, социальная сеть состоит из конечного множества или множеств акторов и отношения или отношений, определенных на них Wasserman et al. (1994). Чтобы помочь понять это определение социальной сети, следует объяснить некоторые другие понятия, которые в данном случае являются фундаментальными. Актор — это отдельная индивидуальная, корпоративная или коллективная социальная единица Wasserman et al. (1994). Это может быть человек в группе людей, отдел внутри компании или нация в мировой системе. Акторы связаны друг с другом социальными узами, и эти отношения составляют ядро подхода социальных сетей. Социальные сети представляются с использованием графовых структур, где узлы — это акторы, а рёбра — это связи между ними. Следовательно, могут быть применены все методы и измерения теории графов. Граф может быть неориентированным, что означает отсутствие различия между двумя вершинами, связанными с каждым ребром, или его рёбра могут быть направленными от одной вершины к другой. Граф обычно определяется как упорядоченная пара $G:=(V,E)$, где $V$ — это вершины или узлы, а $E$ — это рёбра. В дополнение к этому множество методов используется для извлечения знаний о членах сети или самой сети, таких как меры центральности Friedkin (1991), обнаружение сообществ Pujol et al. (2006), моделирование эволюции Michalski et al. (2011) или обнаружение влиятельных узлов Michalski and Kazienko (2015). Как описано в Разделе 1, анализ социальных сетей также стал применяться в организациях, где его часто называют организационным сетевым анализом Michalski and Kazienko (2014).

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

Сеть была построена на основе обмена электронной почтой ее участников, где узлами являлись сотрудники, а ребрами — сообщения. Было решено использовать ориентированный граф, определяемый следующим образом: Социальная сеть представляет собой кортеж $SN~=~(V,E)$, где $V~=~\{v_{1},\ldots,v_{n}\},n\in\mathbb{N}_{+}$ — множество вершин, а $E~=~\{e_{1},\ldots,e_{k^{e}}\},k^{e}\in\mathbb{N}_{+}$ — множество ребер между ними. Каждая вершина $v_{i}\in V$ представляет отдельного сотрудника $v_{i}^{e}$, и каждое ребро $e_{ij}$ соответствует направленным социальным отношениям от $v_{i}$ к $v_{j}$, таким что $E~=~\{(v_{i},v_{j},w_{ij}):v_{i}\in V,v_{j}\in V,v_{i}~=~v^{e}_{i},v_{j}~=~v^{e}_{j}$ и $w_{ij}\in[0,1]\}$. Веса ребер определяются в соответствии со следующей формулой:

где $\sum e_{ij}$ представляет собой сумму сообщений, отправленных от узла $i$ к узлу $j$, а $\sum e_{i}$ — общую сумму сообщений, отправленных от узла $i$. Все петли (self loops) были удалены.

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

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

• ⟦• центральность по входящей степени:

  $$C_{IN}(v_{i})~=~|e_{ji}\in E|,j\neq i,$$

  (1)

  где $e_{ji}$ представляет собой ребро, идущее от каждого узла $v_{j}$ к оцениваемому узлу $v_{i}$.
• ⟦• исходящая центральность:

  $$C_{OUT}(v_{i})~=~|e_{ij}\in E|,i\neq j,$$

  (2)

  где $e_{ij}$ — это ребро, идущее от оцениваемого узла $v_{i}$ к каждому другому узлу $v_{j}$ в сети.
• ⟦• посредническая центральность:

  $$C_{B}(v_{i})~=~\sum_{v_{s}\neq v_{i}\neq v_{d}}\frac{\sigma_{v_{s}v_{d}}(v_{i})}{\sigma_{v_{s}v_{d}}},$$

  (3)

  где $\sigma_{v_{s}v_{d}}(v_{i})$ — количество кратчайших путей между узлами $v_{s}$ и $v_{d}$, проходящих через узел $v_{i}$, а $\sigma_{v_{s}v_{d}}$ — количество всех кратчайших путей между $v_{s}$ и $v_{d}$⟧.
• ⟦• близость центральности:

  $$C_{C}(v_{i})~=~\frac{N}{\sum_{v_{y}}d(v_{y},v_{i})},$$

  (4)

  где $N$ — количество вершин в сети, а $d(v_{y},v_{i})$ — расстояние между вершинами $v_{y}$ и $v_{i}$⟧.
• ⟦• собственная центральность:

  $$C_{E}(v_{i})~=~\frac{1}{\lambda}\sum_{k}a_{v_{k},v_{i}}\,C_{E}(v_{k}),$$

  (5)

  где $A~=~(a_{i,j})$ — матрица смежности графа, а $\lambda\neq 0$ — константа.
• ⟦• page rank:

  $$C_{PR}(v_{i})~=~\alpha\sum_{k}\frac{a_{v_{k},v_{i}}}{d_{k}}\,C_{PR}(v_{k})+\beta,$$

  (6)

  где $\alpha$ и $\beta$ являются константами, а $d_{k}$ — это исходящая степень узла $v_{k}$, если такая степень положительна, или $d_{k}~=~1$, если исходящая степень узла $v_{k}$ равна нулю. Опять же, $A~=~(a_{i,j})$ — это матрица смежности графа.
• ⟦• центральность хаба:

  $$C_{HUB}(v_{i})~=~\beta\sum_{k}a_{v_{i},v_{k}}\,C_{AUT}(v_{k}),$$

  (7)

  где $A~=~(a_{i,j})$ — матрица смежности графа, а $C_{AUT}(v_{k})$ — центральность авторитетности узла (см. уравнение (8)), $\beta$ — константа.
• ⟦• центральность авторитетности:

  $$C_{AUT}(v_{i})~=~\alpha\sum_{k}a_{v_{k},v_{i}}\,C_{HUB}(v_{k}),$$

  (8)

  где $A~=~(a_{i,j})$ — матрица смежности графа, а $C_{HUB}(v_{k})$ — центральность хаба узла (см. уравнение (7)), $\alpha$ — константа.

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

где $m_{v_{i}}$ — это количество пар соседей узла $v_{i}$, которые соединены между собой. В формуле это связано с количеством возможных пар соседей узла $v_{i}$, которое равно $\frac{k_{v_{i}}(k_{v_{i}}-1)}{2}$, где $k_{v_{i}}$ — это степень узла $v_{i}$⟧.

Кликой называется полностью связный подграф, что означает, что каждый узел имеет направленные связи со всеми остальными узлами в клике. Первый признак — это общее количество клик, в которые включен сотрудник, а второй — размер самой большой клики для конкретного узла. В источнике Barabási and Posfai (2016) содержится более подробная информация обо всех представленных выше показателях..

Следующие признаки были основаны на вариативности соседства, которая определяется тремя способами: вариативность отправленного соседства, вариативность полученного соседства и общая вариативность соседства. В целом, вариативность соседства определяется как разница между множествами соседей, с которыми конкретный узел взаимодействует в предыдущем и следующем месяце. Вариативность отправленного соседства учитывает множество соседей, которым данный узел отправлял сообщения. Вариативность полученного соседства рассматривает множество соседей, от которых данный узел получал сообщения. Общая вариативность соседства использует множество соседей, с которыми узел взаимодействует, не различая отправку и получение сообщений. Коэффициент Jaccard использовался для вычисления разницы между множествами, поэтому коэффициент принимает значения от 0 до 1, где 0 означает полностью различные множества, а 1 означает идентичные множества. Коэффициент Jaccard вычислялся для каждой пары чередующихся месяцев. Более того, если сотрудник не был активен в непосредственно следующем месяце, рассматривался ближайший следующий месяц. Например: сотрудник был активен в январе, но не в феврале, и снова был активен в марте; следовательно, коэффициент вычислялся бы между множествами соседей в январе и марте. Кроме того, вариативность соседства вычислялась как средний коэффициент Jaccard для каждого узла на основе предыдущих частных коэффициентов. Формально, показатель вариативности отправки может быть определен следующим образом:

где $N_{snt_{v_{i},m-1}}$ — это множество соседей, которым определенный узел $v_{i}$ отправлял сообщения в месяце $m-1$, а $N_{snt_{v_{i},m}}$ — это множество соседей, которым определенный узел $v_{i}$ отправлял сообщения в месяце $m$, или, если в $m$ сообщения не отправлялись, то рассматриваются $m+1,m+2,\ldots,m_{max}$. Аналогичным образом можно определить показатели изменчивости полученных и общих соседских связей, заменив множества соседей на соседей, которые либо отправляли сообщения узлу $v_{i}$ (изменчивость полученных), либо на множество соседей, с которыми контакт происходил в любом направлении и включал $v_{i}$ (общая изменчивость)).

Кроме того, учитывались такие признаки, как количество отработанных выходных и объем сверхурочной работы. Для сверхурочной работы учитывалось время с 16:00 до 06:00. Следует отметить, что сверхурочная работа рассчитывалась только для набора данных производственной компании. Из-за ограниченности знаний о наборе данных Enron было невозможно узнать, следует ли учитывать разные часовые пояса, поскольку даты были заданы в формате POSIX, а у Enron были филиалы, расположенные в разных часовых поясах..

В качестве резюме все использованные для классификации признаки представлены в таблице 3.

Задача классификации выполнялась с использованием алгоритмов Decision Tree Utgoff (1989), Random Forest, Neural Network (многослойный перцептрон) с оптимизатором L-BFGS и SVM с полиномиальным ядром для различных настроек следующих параметров эксперимента: количества распознаваемых групп сотрудников, минимального количества активных месяцев, а также процента используемых признаков.

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

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

Третий параметр исследует влияние исключения наиболее значимых признаков. Для этого параметра эксперимент проводился девять раз, начиная со всех признаков и доходя до десяти процентов признаков с постоянным уменьшением на десять процентов. Важность признаков для алгоритмов Decision Tree и Random Forest определялась на основе параметра важности Джини из предварительно обученной модели. Алгоритмы Neural Network и SVM не так легко интерпретируемы, и важность признаков не может быть получена из результатов модели. В этом случае важность признаков должна определяться до обучения модели. Для этой цели использовался метод одномерного отбора признаков на основе критерия хи-квадрат.

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

В общем, для каждой комбинации вышеупомянутых параметров модель обучалась с использованием алгоритма поиска по сетке с 5-кратной перекрестной проверкой, поэтому все возможные комбинации из диапазона заданных значений были протестированы, и была возвращена лучшая по f-мере макросредней. Пространство поиска гиперпараметров показано в Таблице 26, а также лучшие для каждой модели в Таблицах 27–30⟧.

Коллективное классифицирование представляет собой иной способ выявления корпоративной иерархии с точки зрения графов. Этот подход использует связи между узлами для распространения меток по всей сети. Алгоритм распространения веры с петлями является примером коллективного классифицирования, подробно описанным в литературе Sen et al. (2008); Kajdanowicz et al. (2016). Поэтому в данной работе представлена упрощенная версия этого алгоритма для сравнения со стандартными алгоритмами классифицирования.

Предложенный метод коллективного классифицирования представлен в виде алгоритма 1. Первым шагом этого алгоритма является выбор оценки полезности и сортировка всех узлов в соответствии с ней (строка 1). Оценка полезности может быть одним из вычисленных признаков из предыдущего раздела. Следующим шагом является раскрытие меток для заданного процента узлов каждого класса $l_{i}\in L$ с наивысшей оценкой полезности (строка 2). Эти узлы отмечаются как известные (их метки постоянны) и получают метки $V^{L}$, в то время как остальные узлы рассматриваются как неизвестные $V^{UK}$ и неразмеченные. Кроме того, распространение меток начинается в цикле до тех пор, пока не будет выполнено условие остановки или пока количество итераций не превысит заданное максимальное число итераций. За одну итерацию каждый размеченный узел отправляет сообщение всем своим соседям, рассматривая ребра как неориентированные (строка 5); более того, все полученные метки на данной итерации сохраняются для каждого узла $v_{i}$ в счетчике $c_{v_{i}}$ (строка 6). Обновление меток начинается после того, как все узлы отправят сообщение своим соседям, поэтому порядок отправки не влияет на результат. Если узел $v_{i}$ получал одну метку чаще остальных (строка 13), эта метка будет присвоена ему (строка 14), и узел дополнительно будет считаться размеченным (строка $v_{i}\in V^{L}$) (строка 15), в противном случае для этого узла счетчик $u_{v_{i}}$ будет увеличен (строка 18). Если $u_{v_{i}}$ превышает максимальное значение (строка 20), он будет сброшен (строка 26), и узлу будет присвоена метка с наивысшей позицией в иерархии компании среди меток с наибольшим количеством (строки 22 – 24). В конце итерации всегда проверяются условия остановки, и они определяются как разница между наборами предыдущих и текущих меток, поэтому, если коэффициент Жаккара больше заданного минимального значения Жаккара и всем узлам назначена метка, алгоритм завершится (строка 29). Кроме того, в случае несбалансированных классов алгоритм позволяет определить $threshold$. На этапе подсчета того, сколько раз каждая метка была получена узлом, результат для мажоритарного класса будет разделен на этот порог для предотвращения доминирования данного класса. (строка 11)

Алгоритм коллективной классификации был запущен с тремя параметрами: количеством распознанных групп сотрудников, минимальным количеством активных месяцев и процентным соотношением известных узлов. Первые два идентичны параметрам из предыдущего раздела, но последний определяет процент известных (размеченных) узлов. Девять значений этого параметра использовались в диапазоне от 90% до 10% с шагом уменьшения в десять процентов. Набор данных производственной компании требовал установки порогового значения, в отличие от набора данных Enron, где это было не нужно. Кроме того, для поиска наилучшего показателя полезности был проведен эксперимент для всех рассчитанных признаков, а также выбраны наилучшее значение по Jaccard и пороговое значение из диапазона различных величин. Пространство поиска гиперпараметров показано в Таблице 31, а также лучшие из них для каждой модели в Таблицах 33–41.