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

МЕНЮ


Новости ИИ
Поиск

ТЕМЫ


Внедрение ИИНовости ИИРобототехника, БПЛАТрансгуманизмЛингвистика, рбработка текстаБиология, теория эволюцииВиртулаьная и дополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информации

АРХИВ


Июнь 2017
Май 2017
Апрель 2017
Март 2017
Февраль 2017
Январь 2017
Декабрь 2016
Ноябрь 2016
Октябрь 2016
Сентябрь 2016
Август 2016
Июль 2016
Июнь 2016
Май 2016
Апрель 2016
Март 2016
Февраль 2016
Январь 2016
0000

RSS


RSS новости
птичий грипп

Новостная лента форума ailab.ru

Интересно, но такая область как профессиональное развитие остается немного в стороне от шума из-за 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])

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

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

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

get.adjlist(skills_graph)

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

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

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

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

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

N Algorithm Modularity Number of communities
1 Betweenness 0.223 6
2 Fastgreedy 0.314 8
3 Multilevel 0.331 8
4 LabelPropogation 0.257 15
5 Walktrap 0.316 10
6 Infomap 0.315 13
7 Eigenvector 0.348 8

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

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

Результаты

skills_cluster

Как мы видим, удалось выявить 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 имели отметки о каких-либо навыках), из-за этого большое количество навыков не было проанализировано и не попало в специализации.

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

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


Источник: habrahabr.ru