В статье приводится метод анализа вакансий по поисковому запросу «Python» с помощью модели кластеризации Gaussian Mixture Model (GMM). По каждому выделенному кластеру будут приведены наиболее востребованные навыки и диапазон заработных плат.

Для чего проводилось данное исследование? Мне хотелось узнать:

• В каких прикладных направлениях используется Python
• Какие требуются знания: базы данных, библиотеки, фреймворки
• Насколько востребованы специалисты каждого направления
• Какие зарплаты предлагают

Загрузка данных

Вакансии загружались с сайта hh.ru, с использованием API: dev.hh.ru. По запросу «Python» было загружено 1994 вакансии (регион Москва), которые были разделены на обучающий и тестовый наборы, в пропорции 80% и 20%. Размер обучающего набора — 1595, размер тестового — 399. Тестовый набор будет использован только в разделах «Топ/Антитоп навыков» и «Классификация вакансий».

Признаки

По тексту загруженных вакансий были сформированы две группы наиболее часто встречающихся n-грамм слов:

• 2-граммы на кириллице и латинице
• 1-граммы на латинице

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

После отбора n-грамм первая группа содержала 81 2-граммы, а вторая 98 1-граммы:

Разбиение вакансий на кластеры было решено сделать по следующим критериям в порядке приоритета:

Определение к какой группе критериев относится n-грамма, и какой вес ей присвоить, происходило на интуитивном уровне. Приведу пару примеров:

1. С первого взгляда «Docker» можно отнести ко второй группе критериев с весом от 4 до 6. Но упоминание «Docker» в вакансии, скорей всего говорит о том, что вакансия будет на должность «DevOps инженер». Поэтому «Docker» попал в первую группу и получил вес равный 7.
   
2. «Java» тоже попадает в первую группу, т.к. в большинстве рассматриваемых вакансий с присутствием слова «Java» ищут Java-разработчика с пунктом «будет дополнительным преимуществом знание Python». Бывают и вакансии с поиском «человека-оркестра». Как первые, так и вторые вакансии меня не интересуют, поэтому их я хочу отделить от остальных вакансий, соответственно присваиваю «Java» наибольший вес 9.
   

Чем больше вес у n-граммы — тем сильней будут группироваться вакансии по данному признаку.

Преобразование данных

Для вычислений каждая вакансия была преобразована в вектор с размерностью 179 (число отобранных признаков) из целых чисел от 0 до 9, где 0 означает что i-ая n-грамма отсутствует в вакансии, а числа от 1 до 9 означают присутствие i-ой n-граммы и ее вес. Далее в тексте под точкой понимается вакансия представленная таким вектором.

Пример:
Допустим список n-грамм содержит всего три значения:

№	n	n-грамма	Вес	Вакансии
1	2	на python	8	258
2	2	понимание принципов	8	221
3	1	sql	5	490

Тогда для вакансии с текстом.

Требования:

• Опыт разработки на python от 3-х лет.
• Хорошее знание sql

вектор равен [8, 0, 5].

Метрика

Для работы с данными нужно иметь представление о них. В нашем случае хотелось бы увидеть, есть ли какие-то скопления точек, которые мы и будем считать кластерами. Для этого я использовал алгоритм t-SNE, чтобы перевести все векторы в двухмерное пространство. 

Суть метода в том, чтобы понизить размерность данных, при этом максимально сохранить пропорции расстояний между точками множества.  Понять по формулам, как работает t-SNE довольно сложно. Но мне понравился один пример найденный где-то на просторах интернета: допустим у нас есть шарики в трехмерном пространстве. Каждый шарик мы соединяем со всеми остальными шариками невидимыми пружинами, которые никак не пересекаются и не мешают друг другу при пересечении. Пружины действуют в две стороны, т.е. они сопротивляются как отдалению, так и приближению шариков друг к другу. Система находится в стабильном состоянии, шарики неподвижны. Если мы возьмем один из шариков и оттянем его, а затем отпустим — то за счет силы пружин он вернется в исходное состояние. Далее мы берем две большие пластины, и сжимаем шарики в тонкий слой, при этом не мешая шарикам двигаться в плоскости между двумя пластинами. Начинают действовать силы пружин, шарики перемещаются и в итоге останавливаются, когда силы всех пружин становятся уравновешенными. Пружины будут действовать так, что шарики, которые находились близко друг к другу, останутся относительно близко и на плоскости. Также и с удаленными шариками — они будут удалены друг от друга. С помощью пружин и пластин мы перевели трехмерное пространство в двухмерное, сохранив в каком-то виде расстояния между точкам!

Алгоритм t-SNE использовался мною только для визуализации множества точек. Он помог выбрать метрику, а также подбирать весы для признаков.

Если использовать метрику Евклида, которую мы используем в нашей повседневной жизни, то расположение вакансий будет выглядеть следующим образом:


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

Существует большое множество метрик (способов определения расстояния между двумя точками), которые будут хорошо работать на исследуемых данных. Я выбрал в качестве меры расстояние Жаккара, с учетом весов n-грамм. Мера Жаккара простая для понимания, при этом хорошо работает для решения рассматриваемой задачи.

Пример:
Вакансия 1 содержит n-граммы: «на python», «sql», «docker»
Вакансия 2 содержит n-граммы: «на python», «sql», «php»
Веса:
«на python» — 8
«sql» — 5
«docker» — 7
«php» — 9
Пересечение множеств (n-грамма встречается в 1-ой и 2-ой вакансии):  «на python», «sql» = 8 + 5 = 13
Объединение множеств (все n-граммы из 1-ой и 2-ой вакансии):  «на python», «sql», «docker», «php» = 8 + 5 + 7 + 9 = 29
Расстояние =1 — (Пересечение множеств / Объединение множеств) = 1 — (13 / 29) = 0.55

Была вычислена матрица расстояний между всеми парами точек, размер матрицы 1595 х 1595. Всего 1 271 215 расстояний между уникальными парами. Среднее расстояние получилось равным 0.96, между 619 659 расстояние равно 1 (т.е. сходства нет совсем). Следующая диаграмма показывает, что в целом вакансии имеют мало сходства:


При использовании метрики Жаккара наше пространство теперь выглядит так:


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

Кластеризация

В качестве алгоритма кластеризации была выбрана модель Gaussian Mixture Model (GMM). Алгоритм получает на вход данные в виде векторов, и параметр n_components — число кластеров, на которые надо разбить множество. О том, как работает алгоритм, можно посмотреть здесь (на английском языке). Я использовал готовую реализацию GMM из библиотеки scikit-learn: sklearn.mixture.GaussianMixture.

Отмечу, что GMM не использует метрику, а делает разделение данных только по набору признаков и их весам. В статье расстояние Жаккара используется для визуализации данных, подсчета компактности кластеров (за компактность я принял среднее расстояние между точками кластера), и определения центральной точки кластера (типичная вакансия) — точка с наименьшим средним расстоянием до других точек кластера. Многие алгоритмы кластеризации использует именно расстояние между точками. В разделе «Другие методы» будет рассказано о других видах кластеризаций, которые основываются на метрике и тоже дают хорошие результаты.

В предыдущем разделе на глаз было определено, что кластеров скорей всего будет шесть. Так выглядят результаты кластеризации при n_components = 6:



На рисунке с выводом кластеров по отдельности, кластеры располагаются в порядке убывания числа точек слева направо, сверху вниз: кластер 4 — самый большой, кластер 5 — самый маленький. В скобках для каждого кластера указана его компактность.

На вид кластеризация получилась не очень хорошей, даже если учитывать, что алгоритм t-SNE не идеален. При анализе кластеров результат тоже не обрадовал.

Для нахождения оптимального числа кластеров n_components, воспользуемся критериями AIC и BIC, о которых можно прочитать здесь. Расчет данных критериев встроен в метод sklearn.mixture.GaussianMixture. Так выглядит график критериев:


При n_components = 12 критерий BIC имеет наименьшее (наилучшее) значение, критерий AIC тоже имеет значение близкое к минимуму (минимум при n_components = 23). Произведем разделение вакансий на 12 кластеров:



Теперь кластеры имеют более компактные формы, как на вид, так и в числовом выражении. При ручном анализе вакансии оказались разбиты на характерные группы для понимания человека. На рисунке выведены названия кластеров. Кластеры под номерами 11 и 4 помечены как и <Trash 2>:

1. В кластере 11 все признаки имеют приблизительно одинаковые суммарные веса.
2. Кластер 4 выделен по признаку Java. Тем не менее вакансий на должность Java Developer в кластере мало, часто знание Java требуется как «будет дополнительным плюсом».

Кластеры

После удаления двух неинформативных кластеров под номерами 11 и 4 в итоге получилось 10 кластеров:


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

Обозначения:

S — доля вакансий, в которых встречается признак, умноженная на вес признака
% — процент вакансий, в которых встречается признак/2-грамма
Типичная вакансия кластера — вакансия, с наименьшим средним расстоянием до других точек кластера

Data Analyst

Кол-во вакансий: 299

Типичная вакансия: 35805914

С++ Developer

Кол-во вакансий: 139
Типичная вакансия: 39955360

Linux/DevOps Engineer

Кол-во вакансий: 126
Типичная вакансия: 39533926

Python Developer

Кол-во вакансий: 104
Типичная вакансия: 39705484

Data Scientist

Кол-во вакансий: 98
Типичная вакансия: 38071218

Frontend Developer

Кол-во вакансий: 97
Типичная вакансия: 39681044

Backend Developer

Кол-во вакансий: 93
Типичная вакансия: 40226808

DevOps Engineer

Кол-во вакансий: 78
Типичная вакансия: 39634258

Data Engineer

Кол-во вакансий: 77
Типичная вакансия: 40008757

QA Engineer

Кол-во вакансий: 56
Типичная вакансия: 39630489

Зарплаты

Зарплаты указаны только в 261 (22%) вакансии из 1167 попавших в кластеры.

При расчете зарплат:

1. Если указывался диапазон «от … и до ...», то использовалось среднее значение
2. Если указывалось только «от ...» или только «до ...», то это значение и бралось
3. При расчетах использовалась(или приводились) ЗП после уплаты налогов (NET)

На графике:

1. Кластеры идут в порядке убывания медианной зарплаты
2. Вертикальная черта в коробке — медиана
3. Коробка — диапазон [Q1, Q3],  где Q1 (25%) и Q3 (75%) перцентили. Т.е. в коробку попадают 50% зарплат
4. В «усы» попадают зарплаты из диапазона [Q1 — 1.5*IQR, Q3 + 1.5*IQR], где IQR = Q3 — Q1 — интерквартильный размах
5. Отдельные точки — аномалии, не попавшие в усы. (Есть аномалии не попавшие и на диаграмму)

Топ/Антитоп навыков

Диаграммы строились по всем 1994 загруженным вакансиям. Зарплаты указаны в 443 (22%) вакансиях. Для расчета по каждому признаку отбирались вакансии, где этот признак присутствует, и на их основе вычислялась медианная ЗП.

Классификация вакансий

Кластеризацию можно было сделать гораздо проще, не прибегая к сложным математическим моделям: составить топ наименований вакансий, и разбить их по группам. Далее анализировать каждую группу на топ n-грамм, и средние зарплаты. Не нужно выделять признаки и присваивать им веса.

Такой подход хорошо бы работал (в какой-то мере) для запроса «Python». А вот для запроса «Программист 1С» такой подход работать не будет, т.к. для программистов 1С в наименовании вакансий редко указывают конфигурации 1С или прикладные направления. А направлений где используется 1С много: бухгалтерия, расчет ЗП, расчет налогов, расчет себестоимости на производственных предприятиях, складской учет, бюджетирование, ERP системы, розничная торговля, управленческий учет, и т.д.

Для себя я вижу две задачи по анализу вакансий:

1. Понять, где используется язык программирования, о котором я мало знаю (как в этой статье).
2. Фильтровать новые опубликованные вакансии.

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

Если использовать встроенный в sklearn.mixture.GaussianMixture метод predict(), то ничего хорошего не получается. Большинство вакансий он относит к большим кластерам, а два кластера из первых трех являются неинформативными. Я использовал другой подход: 

1. Берем вакансию, которую хотим классифицировать. Векторизуем ее и получаем точку в нашем пространстве.
2. Рассчитываем расстояние от этой точки до всех кластеров. Под расстоянием между точкой и кластером я принял среднее расстояние от этой точки до всех точек кластера.
3. Кластер с наименьшим расстоянием и является предсказанным классом для выбранной вакансии. Расстояние до кластера указывает надежность такого предсказания.
4. Для увеличения точности модели я выбрал расстояние 0.87 как пороговое, т.е. если расстояние до ближайшего кластера больше 0.87, то модель не классифицирует вакансию.

Для оценки модели случайным образом отобраны 30 вакансий из тестового набора. В колонке вердикт:

N/a: модель не классифицировала вакансию (расстояние > 0.87)
+: правильная классификация
-: неправильная классификация  

Итого: на 12 вакансиях нет результата, на 2 вакансиях — ошибочная классификация, на 16 вакансиях — правильная классификация. Полнота модели — 60%, точность модели — 89%.

Слабые стороны

Первая проблема — возьмем две вакансии:

Вакансия 1 — «Ведущий программист C++»
«Требования:

• Опыт разработки на C++ от 5-ти лет.
• Дополнительным плюсом будет знание Python»

Вакансия 2 — «Ведущий программист Python»
«Требования:

• Опыт разработки на Python от 5-ти лет.
• Дополнительным плюсом будет знание C++»

С точки зрения модели эти вакансии идентичны. Я пробовал корректировать веса признаков на порядок их нахождения в тексте. Ни к чему хорошему это не привело.

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

Другие методы

На странице cluster comparison хорошо продемонстрированы различные алгоритмы кластеризации. GMM — единственный, который дал хорошие результаты.
Остальные алгоритмы либо не работали, либо давали очень скромные результаты.

Из реализованных мной, хорошие результаты были в двух случаях:

1. Выбирались точки с большой плотностью в некоторой окрестности, стоящие на удаленном расстоянии друг от друга. Точки становились центрами кластеров. Далее на основе центров начинался процесс формирования кластеров — присоединение соседних точек.
2. Агломеративная кластеризация — итерационное слияние точек и кластеров. В библиотеке scikit-learn этот вид кластеризации представлен, но работает плохо. В своей реализации я менял матрицу соединений после каждой итерации слияния. Процесс останавливался по достижению некоторых граничных параметров — по факту дендрограммы не помогают понять процесс слияния, если кластеризуются 1500 элементов.

Заключение

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