Анализ взаимосвязи навыков с помощью графов в R

Интересно, но такая область как профессиональное развитие остается немного в стороне от шума из-за data science. Стартапы в сфере HRtech только начинают наращивать обороты и увеличивать свою долю, замещая традиционный подход в сфере работы с профессионалами или, теми, кто хочет стать профессионалом.

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

Постановка задачи и входные данные

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

Для анализа мы брали данные с портала Работа в России, доступные на data.gov.ru. Здесь представлены все вакансии, доступные на портале с описанием, зарплатой, регионом и прочими деталями. Далее мы распарсили описания и выделили из них навыки. Это отдельное исследование и этой статьей не покрывается. Однако уже размеченные данные можно также взять с API hh.ru.

Таким образом, исходные данные представлены матрицей со значениями 0/1, в которой X — навыки, а объекты — вакансии. Всего 164 признака и 841 объект.

Подбор метода поиска групп навыков

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

Решая задачу в лоб, можно предположить, что если одна группа навыков встречается у одной группы вакансий, а другая группа навыков — у другой группы вакансий, то это группа навыков и есть специализация. И можно разделить навыки с помощью метрических методов (k-means и модификации). Но проблема как раз была в том, что одна вакансия могла иметь несколько специализаций. И в итоге как бы не менялся алгоритм, он относил 90% навыков к одному кластеру и еще с десяток кластеров по 1-2 навыка. Поразмыслив, начали переписывать k-means под задачу таким образом, чтобы вместо классического евклидово расстояния выбрал меру смежности навыков, то есть частоту встречаемости двух навыков:

library(data.table)
grid<-as.data.table(expand.grid(skill_1=names(skills_clust),skill_2=names(skills_clust)))
grid<-grid[grid$skill_1 != grid$skill_2,]
for (i in c(1:nrow(grid))){
  grid$value[i]<-sum(skills_clust[,grid$skill_1[i]]*skills_clust[,grid$skill_2[i]])
}

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

Построение и анализ графа навыков

Для того чтобы построить граф мы воспользуемся пакетом igraph (такой же есть и в python, и в C/C++) и прежде всего мы создадим матрицу смежности из таблицы, которую мы начали считать для k-means (grid). Затем отнормируем смежность навыков в диапазоне от 0 до 1:

grid_clean<-grid[grid$value>1,] # пары навыков встречающиеся <=1 раза исключаются
grid_cast<-dcast(grid_clean,skill_1~skill_2)
grid_cast[,skill_1:=NULL]
grid_cast_norm<-grid_cast/colSums(grid_cast,na.rm=T)
grid_cast_norm[is.na(grid_cast_norm)]<-0
grid_cast_norm<-as.matrix(grid_cast_norm) 
grid_cast_norm[grid_cast_norm<=0.02] <-0 # пары навыков встречающиеся <=2% исключаются

Смежность навыка i и навыка j мы нормируем как долю от общей встречаемости навыка i. Изначально мы нормировали матрицу как долю от максимальной встречаемости всех навыков, но затем перешли к этой формуле. Идея в том, что, к примеру, навык i встречается с навыком j 10 раз, и больше ни с каким другим навыком не встречается. Можно предположить, что такая связь будет более весомой (например 100%), чем если бы мы смотрели эту встречаемость от максимальной в данной матрице (например, 100 — 10%).

Также для очистки матрицы смежности от случайных связей, мы убрали пары встречающиеся меньше 2-х раз или 2% от общей встречаемости данного навыка. К сожалению, это сократило набор навыков с 164 до 87, однако, сделала сегменты более логичными и понятными.

Затем мы создаем ненаправленный взвешенный граф из матрицы смежности:

library(igraph)
library(RColorBrewer)
skills_graph<-graph_from_adjacency_matrix(grid_cast_norm, mode = "undirected",weighted=T)
E(skills_graph)$width <- E(skills_graph)$weight
plot(skills_graph, vertex.size=7,vertex.label.cex=0.8, layout=layout.auto, 
     vertex.label.color="black",vertex.color=brewer.pal(max(V(skills_graph)$group),"Set3")[1])

igraph нам также позволяет посчитать основные статистики по вершинам:

closeness(skills_graph) # Центральность вершины на основании расстояния до других вершин
betweenness(skills_graph) # Количество самых коротких путей, проходящих через вершину
degree(skills_graph) # Количество связанных вершин с данной вершиной

Далее можем вывести лист смежности для каждого навыка. Этот лист в дальнейшем может стать основой рекомендательной системы для выбора новых навыков:

get.adjlist(skills_graph)

Выделение сообществ методом Multilevel

На тему поиска сообществ в графах есть отличная работа Славнова Константина. Эта статья раскладывает по полочкам основные метрики качества выделения сообществ, методы выделения сообществ и агрегирования результатов работы этих методов.

Когда истинное разбиение на сообщества не известно для оценки качества используется значение функционала модулярности (modularity). Это самая популярная и общепризнанная мера качества для данной задачи. Функционал был предложен Ньюманом и Гирваном в ходе разработки алгоритма кластеризации вершин графа. Если говорить простым языком, то эта метрика оценивает разность плотностей связей внутри сообществ и между сообществами. Основной недостаток данного функционала в том, что он не видит маленькие сообщества. Для задачи выделения специализаций, где сообществом может стать комбинация из 2-3 вершин, эта проблема может стать критичной, однако, может обходиться путем добавления дополнительного параметра масштаба в оптимизируемый функционал.

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

На наших данных этот алгоритм также показал один из лучших результатов:

В пакте igraph алгоритм Multilevel реализуется функцией cluster_louvain():

fit_cluster<-cluster_louvain(skills_graph)
V(skills_graph)$group <- fit_cluster$membership

Результаты

Как мы видим, удалось выявить 8 специализаций (названия даны субъективно автором статьи):

• Обслуживание серверов и сетей — включает знание Microsoft Hyper-V, VMware vSphere, ремонт и отстройка техники. Требуется также знание английского языка;
• Разработчик промышленных систем/контроллеров — тут целый набор от C/C++ до Java включая Assembler и SCADA;
• Разработчик ERP-систем (1С, SAP) — здесь помимо 1C, SAP, ABAP требуется еще знание основ бухгалтерского, управленческого учета и навыки техподдержки пользователей;
• Программирование станков — в этой специализации требуются навыки составления программ для станков с ЧПУ, программирование на Unigraphics NX и знание систем управления станков;
• Общие навыки программирования — включает знание ГОСТ, структурного программирования, навыки написания ТЗ и почему-то знание китайского языка (наверное кому-то очень нужен);
• Разработчик под Microsoft со знанием БД — C#, .NET Framework, MS SQL Server, FoxPro, опыт работы с чужим кодом, умение проводить рефакторинг;
• Веб-разработчик — JavaScript, HTML, СSS, PLPG/SQL (PostgreSQL), jQuery, PHP и пр. Интересно, что именно в этой специализации чаще всего требуются такие навыки как знание концепции ООП, Agile и владение системами контроля версий;
• Разработчик мобильных приложений — знание Swift, опыт разработки Android/iOS приложений;

Специализации довольно тесно взаимосвязаны. Это объясняется нашим основным предположением, что одна вакансия может иметь несколько специализаций. Так, например, в специализации “Разработчик мобильных приложений” требуется “Знание сетевых протоколов” (71), которое в свою очередь взаимосвязано с “Администрирование локальных сетей” (32) из специализации “Обслуживание серверов и сетей”.

Также следует понимать, что источник данных это портал “Работа в России”, выборка вакансий на котором отличается от hh.ru или superjob.ru — вакансии смещены в сторону вакансий с более низкой квалификацией. Плюс выборка ограничена 841 вакансией (из них только 585 имели отметки о каких-либо навыках), из-за этого большое количество навыков не было проанализировано и не попало в специализации.

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

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

Автор: finnfromfinland

Источник