У компании есть еще похожие вакансии

2 марта я выступал с докладом на Data Science Meetup, который проходил в нашем офисе. Я рассказал об опыте создания алгоритма по схлопыванию похожих вакансий в поисковой выдаче. По ссылке вы можете ознакомиться с отчетом о прошедшей встрече, там же будут доступны записи выступлений и ссылки на презентации. Для тех же, кто предпочитает воспринимать информацию в текстовом виде, я написал эту статью.

Мы столкнулись с проблемой, когда в поиске по вакансиям выдача заполнялась одинаковыми вакансиями от одного работодателя. Например, по запросу «водитель» посетитель мог получить 30—40 вариантов одной и той же вакансии на одну и ту же позицию.

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

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

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

Это помогло бы решить проблему соискателя и избавило бы нас от недовольства клиентов. Как этого можно добиться?

• Необходимо было научиться оценивать сходство вакансий.
• Объединить похожие вакансии в группы.
• Показывать в выдаче самого релевантного представителя группы.

Разберем каждый пункт подробнее.

Что представляет из себя вакансия?

Это полуструктурированный текст, части которого — заголовок, требования, обязанности и т.д., плюс такие атрибуты, как зарплата, адрес работы, график работы и прочее.

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

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

LSH

Locality-sensitive hashing (LSH) функции — это такие функции, целью которых является максимизация вероятности коллизии схожих аргументов функции. Незначительное изменение аргумента функции, например, текста вакансии, должно приводить к незначительному же изменению результата функции хеширования.

Одними из наиболее часто используемых представителей LSH-функций являются функции SimHash и Minhash. Это алгоритмы хеширования, преобразующие текст в список значений, который в итоге представляет из себя сигнатуру этого текста.

В случае SimHash список значений — это просто список битов (значения 0 или 1).

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

Основным же отличием обоих алгоритмов является вероятность коллизий. В случае SimHash она равна косинусному сходству векторов частотности слов в документах, а в случае MinHash — сходству Жаккара.

Я встречал еще такое мнение, что MinHash лучше детектирует копипасту, в то время как SimHash — плагиат.

Мы решили, что косинусное сходство более соответствует нашим требованиям к определению сходства вакансий, и остановили свой выбор на SimHash алгоритме.

Описание SimHash алгоритма:

1. Определяем размер симхеша.
2. Создаем массив целых чисел, заполненный нулями, с размером, равным длине хеша в битах.
   

   hash = [0,0,0,0,0,0,0,0]

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

   doc = [“водитель”,“такси”,“авто”] doc = [01111001, 00110101, 00101110]

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

   01111001 00110101 00101110 + hash =[-3,-1,3,1,1,1,-1,1]

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

   hash =[ 0, 0,1,1,1,1, 0,1] simhash(doc) = 00111101

Что теперь с этим можно сделать? Можно определить, насколько похожи документы, используя только их сигнатуры.

Для этого достаточно их «проксорить», в результате чего мы получим число позиций, в которых эти сигнатуры различаются.

    00111101 XOR 00111000   = 00000101

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

Similarity index = 6/8 = 0.75 (75%)

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

Например, если мы найдем для h1 такие хеши,

h1 = 00111101 h2 = 00111000 h3 = 00001101

то обнаружим, что h2 отличается от h3 более чем на 2 бита.

Т.е. хеши в группе могут отличаться друг от друга сильнее, чем нам хотелось бы. Это означает, что хеши будут попадать в другие группы и группы будут иметь пересечения.

Поэтому определим, какими свойствами должны обладать группы похожих вакансий:

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

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

Иерархическая кластеризация методом полной связи (дальнего соседа) позволяет выполнить все три пункта.

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

Есть один минус — сложность иерархической кластеризации O(n^3). Но, так как кластеризовать мы будем вакансии одного клиента, мы можем позволить себе не обращать на это внимания в надежде, что количество вакансий у одного клиента будет ограничиваться разумными значениями.

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

Как на ее основе получить кластеры похожих вакансий определенной степени похожести?

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

Для этого можно применить стандартный прием с максимизацией второй производной функции зависимости количества кластеров от длины разреза дендрограммы.

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

Если мы решим объединять в кластеры похожие друг на друга на 80% ±5% вакансии, достаточно найти максимальное значение второй производной в этом диапазоне и в этом месте разделить дендрограмму на кластеры.

Реализация

При создании или изменении вакансии отправляем задачу в очередь в rabbitmq на вычисление simhash. После чего в другой очереди выполняем задачу кластеризации вакансий клиента. Каждой вакансии присваиваем идентификатор кластера, в который она попала. Полный цикл по вычислению симхешей и кластеризации вакансий всех клиентов от начала и до конца занимает 5 минут.

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

В конечном счете мы добились требуемого результата.

Результаты

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

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

Также мы выяснили, что в 75% поисков возможна группировка похожих вакансий и в 66% поисков пользователь видел похожие вакансии.

ссылка на оригинал статьи https://habrahabr.ru/post/325014/