Алгоритм кластеризации поисковых запросов

Евгений Халин

Руководитель проекта AdDigger

Кластеризация – задача разбиения объектов на подмножества (кластеры), так, чтобы внутри одного кластера находились схожие объекты, причем объекты в разных кластерах должны отличаться.

Решения задачи кластеризации можно свести к следующим этапам:

1. Определение характеристик(признаков) каждого объекта.
2. Вычисление меры сходства между объектами.
3. Применение алгоритмов кластеризации.

Задача кластеризации поисковых запросов часто возникает у SEO специалиста. Обычно это связано с тем, что требуется разбить все запросы по страницам для дальнейшего продвижения. Большинство сервисов, которые есть на рынке, используют различные меры сходства выдачи по запросам. Это может быть, например, доля пересечений адресов в топ 10 выдачи. Особенностью такой кластеризации является то, что самый хороший вариант – это когда запросы на одной странице максимально похожи. Но при таком разбиении разные модели одной марки будут находиться в разных группах, а количество групп будет достаточно велико. Для нашей задачи это не очень хорошо, потому что если показать человеку вместо 1000 запросов 400, то это не сильно упростит ему восприятие. Идеальным вариантом, было бы разбиение на небольшое количество кластеров. Например, один кластер про холодильники, другой про стиральные машины и т.д. В этом случае, человек легко сможет проанализировать все группы, какие-то вычеркнуть как очень дорогие и не конверсионные, а какие-то наоборот расширить, если увидит, что это приоритетный товар или услуга, но запросов внутри группы не очень много.

Порядок исследования

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

TF-IDF – статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов или корпуса.

TF – частота слова, позволяет оценить важность слова в пределах одного документа.

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

Таким образом алгоритм кластеризации выглядит так:

1. Все слова из запросов нормализуются, удаляются служебные части речи (предлоги, союзы и т.п.)
2. Каждый запрос преобразуется в вектор чисел. Делается это с помощью TfidfVectorizer в библиотеке sklearn.
3. Полученные вектора кластеризуются с помощью метода MiniBatchKMeans из библиотеки sklearn. MINI-BATCH K-MEANS является вариацией алгоритма K-MEANS, который использует мини-партии для сокращения времени вычисления, при этом работает незначительно хуже стандартного алгоритма. Так же как и KMeans метод принимает на вход количество кластеров.

Стоит напомнить, что кластеризация — это задача обучения без учителя, в которой нет правильных или неправильных ответов. Есть метрики, которые позволяют оценить качество кластеризации, но нам было важно, чтобы результат устраивал клиента, поэтому качество кластеризации оценивалось людьми. Результат кластеризации при каждом запуске может быть разный, т.к. при запуске алгоритма используются случайные величины в качестве начальных состояний. Это не является проблемой, т.к. в реальности происходит тоже самое: разные люди могут разбить одно и тоже СЯ совсем по-разному. Более того, специалист в процессе работы с инструментом, может сделать перерасчет, если по каким-то причинам ему не понравился результат.

Ниже приведены примеры кластеризации одного СЯ:

В описанном подходе есть несколько проблем:

1. От специалиста (пользователя инструмента кластеризации) требуется вводить количество кластеров. Для маленьких СЯ можно достаточно быстро подобрать оптимальное число кластеров, учитывая, что специалист сам подбирал эти запросы, он знает приблизительное количество групп. Но когда число запросов превышает несколько тысяч, итеративно увеличивать количество требуемых кластеров, пока не получиться удовлетворительный результат – очень долго, т.к. требуется время, чтобы оценить качество каждого кластера.

2. Синонимы и близкие по смыслу слова могут оказаться в одной группе в очень редких случаях, когда их TF-IDF будет в рамках СЯ очень похож. А хотелось бы, чтобы такие слова объединялись в группы как можно чаще

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

Чтобы научить алгоритм находить похожие слова по смыслу, а не по частоте их употребления (проблема №2), вместо TF-IDF, можно использовать Word2Vec. Этот инструмент был разработан Google в 2013 году. Алгоритм обучается на большом объеме текста, а затем его можно использовать для получения векторного представления слова. При этом векторные представления близких по смыслу слов будут похожи. Именно это позволяет находить синонимы, сокращения и т.д.

Для тестирования решили не обучать новую модель, а взять готовую. Обученная модель была взята на сайте https://zenodo.org/record/400631. Слова в этой модели не нормализованы, каждое слово представляет собой вектор из 300 элементов.

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

Формула для сложения N векторов:

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

Но рассмотрим пример, когда у нас есть 3 запроса:

• купить машину
• купить автомобиль
• купить квартиру

Вектора слов «машина» и «автомобиль» будут более схожи, чем вектора слов «машина» и «квартира», поэтому при суммировании мы получим векторное представление, по которому запрос «купить квартиру» будет отличаться от двух других запросов достаточно сильно, чтобы выделить его в отдельный кластер. Очевидно, что полученное векторное представление для запроса «купить машину» может быть получено суммирование нескольких других слов, которые по тематике очень далеки от автомобиля, но этим можно пренебречь, т.к. обычно семантическое ядро состоит из тематически связанных запросов, в которых нет такого разнообразия лексики, которое создавало случаи, объединения совершенно непохожих запросов в одну группу.

Ниже примеры кластеризации СЯ с использованием Word2Vec:

В этом примере получились 3 группы: группа запросов со странами, группа запросов про букеты кому-то в подарок, группа запросов с названиями цветов.

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

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

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

Пример кластеризации запросов с названиями групп:

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

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

Одно из возможных решений – найти зависимость числа кластеров от количества запросов.

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

Другое решение – подобрать допустимый диапазон расстояний между векторами. Увеличивать количество кластеров, если среднее расстояние между векторами больше максимального значения диапазона и уменьшать – если среднее расстояние меньше минимального. Проблема такого подхода в том, что есть клиенты, у которых только один товар, и его кластеры будут является разновидностями этого товара. В этом случае расстояние будет очень маленьким. Попытка склеивания этих групп до допустимого диапазона приведет к формированию одного кластера. А есть клиенты, у которых интернет магазин, и в одном кластере бытовая техника, а в другом ювелирные изделия. В таком случае расстояние будет очень большим, разбиение же до допустимого диапазона даст очень большое число кластеров.

Для другого решения можно использовать название групп, а точнее количество слов и словосочетаний, которые это название формируют. Интуитивно понятно, что чем меньше слов или словосочетаний присутствует в названии группы, тем больше похожи запросы внутри группы. Если среднее число слов и словосочетаний в СЯ очень большое, это значит, что внутри каждой группы собралось очень много тем/предметов/услуг. И количество кластеров нужно увеличивать. При это если требовать, чтобы каждое название содержало ровно 1 слово или словосочетание, то это приведет к тому, что синонимичные понятия не будут объединяться в одну группу. Поэтому экспериментально был подобрал коэффициент, при достижении которого можно больше не увеличивать число кластеров. Этот коэффициент равен 1.3. Подобный подход работает достаточно хорошо для любых СЯ.

Общий алгоритм работы полученного инструмента:

1. Очистка и нормализация запросов.
2.   Получение векторного представления запросов с помощью Word2Vec.
3. Кластеризация полученных векторов с заданным числом кластеров (по умолчанию = 3).
4. Получение названий всех кластеров.
5. Расчет среднего значения количества слов и словосочетаний в названиях кластеров. Если полученное значение больше 1.3, то возврат на пункт 3 с изменением числа кластеров (шаг увеличения = 3).
6. Склейка исходных форм с базовой (одной нормальной форме может соответствовать несколько исходных) и вывод пользователю результатов.

Результат кластеризации с автоматическим определением числа кластеров: