Кластеризация и ее методы

Кластеризация – группировка большого массива данных в кластеры для ускорения и упрощения исследования. Объекты разделяются на группы на основании схожих параметров, при этом разница между двумя типами должна быть значительной. Так, например, разделение товаров в супермаркете на «мясо», «бытовую химию», бакалею и т.д. является простейшим примером кластеризации. Разница разбивки и классификации заключается в том, что при разбивке нет заданного списка групп. Он определяется в процессе проведения анализа.

Использование методов кластеризаций может быть представлено в поэтапном виде.

1. Подбор выборки объектов.
2. Выявление количества переменных, являющихся основой выборки. Если есть потребность, то проводится нормализация значений.
3. Определение степени сходства объектов.
4. Использование кластеризации для разбития объектов на группы с похожими параметрами.
5. Описание результатов проведенного анализа.

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

Как выявляется схожесть объектов? Прежде всего необходимо выстроить векторы расстояний для объектов в выборке. Чаще всего их приводят к числовым значениям. Некоторые алгоритмы предназначены для анализа не количественных, а качественных параметров. 

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

Между парами объектов вычисляется «расстояние» (этим словом характеризуется степень схожести). Среди существующих метрик можно отметить:

1. Евклидово расстояние
2. Квадрат евклидова расстояния
3. Расстояние городских кварталов
4. Расстояние Чебышева
5. Степенное расстояние

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

Стоит учесть, что точность результатов supervised-методов является более высокой, поэтому при сборе обучающей выборки на первом плане стоят именно задачи классификации.

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

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

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

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

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

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

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

Чтобы выполнить задачу, нужно простроить граф на основании точек, данные о которых имеются: точки, расстояние между которыми не превышает трех метров, следует объединить ребрами. Компоненты связности в данном графе – это кластеры.

Методика расчета имеет свои недостатки. Так, можно на выходе получить цепочку большой длины, в которой попарное расстояние между целым рядом точек будет не превышать 3 метра. Эта цепь также относится к одной компоненте связности. В результате отсечка по трем метрам относится к диаметрам кластера косвенно, а кластеры в свою очередь будут иметь слишком большие размеры. Помимо этого недостатка имеется и другой: выбор расстояния отсечки нелогичен. Если важно не только само решение поставленной задачи, но и разработка общего способа разбивки, то нужно определиться с конкретными значениями метода.

Данный метод предполагает не строить ребра в графе, а удалять их. Для этого надо начать строить минимальное остовное дерево, при этом необходимо рассчитывать промежуток между точками веса ребер. В таком случае, удалив N ребер с максимальным весом, в результате получаем N+1 компоненту связности. По аналогии с предыдущими методами расчета, принимаем ее за кластер.

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

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

1. Выполняется разбивка объектов.
2. Производится пересчет центров кластеров.

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

Сбор и группирование ключевых запросов начинается с определения трех основных характеристик.

1. Масштаба анализа кластера – содержит ли он все требуемые слова и фразы.
2. Соответствует ли он потребностям пользователя.
3. Являются ли запросы внутри кластера совместимыми.

Принципы группировки слов могут подбираться на основе одного из способов.

1. Разбивка по ТОП-10 поисковой выдачи. Вариант, который используется чаще всего. Он подразумевает сбор URL с первой страницы поисковика для всех ключевых запросов. После этого происходит сравнение фраз друг с другом для нахождения общих URL. В дальнейшем происходит группирование общих адресов в один кластер.
2. Разбивка по словоформе – слова, корни которых одинаковы, группируются. Главным недостатком способа является то, что не учитывается смысловая нагрузка при проведении разбивки. В результате увеличивается риск попадания слов и фраз, несущих разную смысловую нагрузку в один кластер.
3. Кластеризация вопрос/ответ. Чаще всего используется в качестве инструмента для сервисов быстрых ответов. Разделение проводится по принципу: является ли ключевая фраза вопросом.

Этот вид группировки поисковых запросов разделяется еще на 3 способа: Soft, Moderate и Hard:

1. Soft разбивка – подразумевает использование в качестве основы самого частотного ключа с дальнейшим подбором к нему остальных. Например, запрос: «купить смартфон Самсунг» – основной. Дальше следуют запросы с «хвостами»: «купить смартфон Самсунг в Москве», «купить смартфон Самсунг цена». После этого необходимо изучить ТОП-10 выдачи и проверить число пересечений с главным ключом. Если порог пройден, то ключ становится частью кластера. В итоге объединение ключей происходит с привязкой к главному частотному запросу. Такой подход может использоваться для информационных сайтов и онлайн-магазинов с простой структурой.
2. Moderate (Middle). Хард и софт разбивка объединены в этой методике. Основой выступает самая частотная фраза, после этого происходит сравнение с ней остальных по числу общих УРЛов. Это принцип софт кластеризации. Однако после этого продолжается работа и ключевики сравниваются между собой и, в случаях, когда число пересекающиеся УРЛов достигло порога, происходит образование кластера. В итоге получается связать все запросы из одного кластера попарно.
3. Хард кластеризация – методика, при которой выполняется сравнение самого частотного слова и идущего следом. Критерий сравнения – количество общих УРЛов из ТОП-10, а после этого ведется сравнение попарно всех остальных фраз друг с другом и образование пар. То есть, кластер образуется, когда пересечение достигает своего порога. Жесткий способ хорош для ниш с высокой конкуренцией, а также при предоставлении тяжелых услуг, вроде страхования, кредитования и т.д. Хард разбивка является более точной, но с меньшим количеством данных.

Различные исследования гласят, что хард разбивка показывает от 90% точности при установленном пороге в 3 УРЛа. Даже опытный оптимизатор в процессе ручной разбивки может демонстрировать точность около 70%, и это считается отличным результатом без использования дополнительных инструментов. Если же новичок должен будет объединить запросы вручную, его точность чаще всего не будет превышать 30%. При этом полнота данных хард оптимизации чаще всего не превышает 40%. Но при сравнении с ручной работой, максимум, на что можно рассчитывать – 20%.

Софт разбивка выдает более полные данные, однако их точность достаточно низкая. Для продвижения запросов требуется порог хотя бы в 5 URl, но при этом происходит снижение полноты до 23%. 

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

Плюсы:

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

Минусы:

• постоянные изменения ТОПа поисковой выдачи могут приводить к тому, что сделанная ранее группировка теряет свою актуальность, кроме того, падает ее эффективность;
• объемная семантика нуждается в глубинном семантическом анализе, который отнимает много времени, более того, необходима дополнительная проверка кластеров;
• даже с помощью автоматизированных сервисов кластеризаций нельзя распределить все запросы разом. Как правило, формируется список запросов, которые не попали под кластеризацию и требуют ручной доработки;
• часто в состав кластеров включаются близкие по тематике фразы, которые означают нетематические предметы или объекты.