В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен. О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.
Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.
Понятие кластеризации
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.
Меры расстояний
Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта — как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.
Классификация алгоритмов
Объединение кластеров
Обзор алгоритмов
Алгоритмы иерархической кластеризации
Среди алгоритмов иерархической кластеризации выделяются два основных типа: восходящие и нисходящие алгоритмы. Нисходящие алгоритмы работают по принципу «сверху-вниз»: в начале все объекты помещаются в один кластер, который затем разбивается на все более мелкие кластеры. Более распространены восходящие алгоритмы, которые в начале работы помещают каждый объект в отдельный кластер, а затем объединяют кластеры во все более крупные, пока все объекты выборки не будут содержаться в одном кластере. Таким образом строится система вложенных разбиений. Результаты таких алгоритмов обычно представляют в виде дерева – дендрограммы. Классический пример такого дерева – классификация животных и растений.
Для вычисления расстояний между кластерами чаще все пользуются двумя расстояниями: одиночной связью или полной связью (см. обзор мер расстояний между кластерами).
К недостатку иерархических алгоритмов можно отнести систему полных разбиений, которая может являться излишней в контексте решаемой задачи.
Алгоритмы квадратичной ошибки
Задачу кластеризации можно рассматривать как построение оптимального разбиения объектов на группы. При этом оптимальность может быть определена как требование минимизации среднеквадратической ошибки разбиения:
где cj — «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).
К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.
Нечеткие алгоритмы
Алгоритмы, основанные на теории графов
Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.
Алгоритм выделения связных компонент
В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» больше R. Соединенными остаются только наиболее близкие пары объектов. Смысл алгоритма заключается в том, чтобы подобрать такое значение R, лежащее в диапазон всех «расстояний», при котором граф «развалится» на несколько связных компонент. Полученные компоненты и есть кластеры.
Для подбора параметра R обычно строится гистограмма распределений попарных расстояний. В задачах с хорошо выраженной кластерной структурой данных на гистограмме будет два пика – один соответствует внутрикластерным расстояниям, второй – межкластерным расстояния. Параметр R подбирается из зоны минимума между этими пиками. При этом управлять количеством кластеров при помощи порога расстояния довольно затруднительно.
Алгоритм минимального покрывающего дерева
Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов.
Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: и . Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.
Послойная кластеризация
Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами , то .
Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами:
Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
Содержание
Постановка задачи кластеризации [ править ]
Множество [math]Y[/math] в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.
Решение задачи кластеризации объективно неоднозначно по ряду причин:
Теорема невозможности Клейнберга [ править ]
Для формализации алгоритмов кластеризации была использована аксиоматическая теория. Клейнберг постулировал три простых свойства в качестве аксиом кластеризации и доказал теорему, связывающую эти свойства.
Определение:
Алгоритм кластеризации [math]a[/math] является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния [math]\rho[/math] и любой константы [math]\alpha \gt 0[/math] результаты кластеризации с использованием расстояний [math]\rho[/math] и [math]\alpha\cdot\rho[/math] совпадают.
Первая аксиома интуитивно понятна. Она требует, чтобы функция кластеризации не зависела от системы счисления функции расстояния и была нечувствительна к линейному растяжению и сжатию метрического пространства обучающей выборки.
Определение:
Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.
Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.
Примеры преобразований с сохранением кластеров
Исходное расположение объектов и их кластеризация
Пример масштабной инвариантности. Уменьшен масштаб по оси ординат в два раза.
Пример допустимого преобразования. Каждый объект в два раза приближен к центроиду своего класса. Внутриклассовое расстояние уменьшилось, межклассовое увеличилось.
Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:
Теорема (Клейнберга, о невозможности):
Типология задач кластеризации [ править ]
Типы входных данных [ править ]
Вычисление матрицы расстояний по признаковому описанию объектов может быть выполнено бесконечным числом способов в зависимости от определения метрики между объектами. Выбор метрики зависит от обучающей выборки и поставленной задачи.
Цели кластеризации [ править ]
Методы кластеризации [ править ]
Меры качества кластеризации [ править ]
Подробнее про меры качества можно прочитать в статье оценка качества в задаче кластеризации.
Применение [ править ]
Биология и биоинформатика [ править ]
Медицина [ править ]
Маркетинг [ править ]
Кластеризация широко используется при изучении рынка для обработки данных, полученных из различных опросов. Может применяться для выделения типичных групп покупателей, разделения рынка для создания персонализированных предложений, разработки новых линий продукции.
Интернет [ править ]
Компьютерные науки [ править ]
Псевдокод некоторых алгоритмов кластеризации [ править ]
Метод K-средних (Алгоритм Ллойда) [ править ]
Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния.
DBSCAN [ править ]
Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
На вход алгоритму подаётся набор точек, параметры [math]\epsilon[/math] (радиус окружности) и [math]m[/math] (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.
Основная точка вместе со всеми достижимыми из нее точками формирует кластер. В кластер будут входить как основные, так и неосновные точки. Таким образом, каждый кластер содержит по меньшей мере одну основную точку.
На выходе получаем разбиение на кластеры и шумовые объекты. Каждый из полученных кластеров [math]C_j[/math] является непустым множеством точек и удовлетворяет двум условиям:
DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей — в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для сегментации изображений.
Кластеризация поисковых запросов — что это такое, лучшие бесплатные и платные способы группировки, как ускорить процесс в 3 раза
Некачественная кластеризация запросов семантического ядра способна свести на нет все старания по продвижению сайта. Чтобы этого не произошло разберем на конкретных примерах, что она из себя представляет и какие платные и бесплатные методы группировки наиболее эффективны.
Также, спалю метод, которым пользуются передовые SEO-агенства. Он позволяет ускорить процесс распределения ключевых фраз в 3-4 раза.
Что такое SEO-кластеризация простым языком
Предположим вы собрались в поход и выбираете из шкафа с разными вещами и предметами, то снаряжение, которое пригодится. То есть, берете с собой все то, что поможет вам закрыть все потребности во время путешествия. Такая же история и с кластеризацией запросов.
Сначала на основе поискового спроса выявляются основные потребности людей в выбранной тематике. Затем для каждой проблемы или задачи подбираются фразы из семантического ядра, характеризующие ее с разных сторон. Далее они объединяются в одну группу или смысловой кластер. А затем копирайтер, ориентируясь на них, дает полноценный ответ на соответствующей странице сайта.
Зачем нужна кластеризация
Пользователи поисковых систем, вбивая в Яндекс или Гугл свой запрос хотят получить ответ именно на него. Чтобы посетитель сайта был удовлетворен и нашел у вас, то что искал — нужно все что касается одной потребности положить рядом. Также, как в супермаркете лежат тематические товары: все для дачи, шашлыков, праздника.
Второй момент — широта ассортимента. Покупатель, приходя в магазин за стиральным порошком для своей старенькой стиральной машинки не будет доволен ассортиментом из 3-х наименований. Какими бы популярными они не были. Ему же нужен тот порошок, который идеально подходит конкретно для его стиралки. Магазин, в котором он найдет желаемое, точно станет для него самым лучшим и регулярно посещаемым!
С поисковыми запросами та же история. Если мы ограничиваемся сбором семантики по верхам и кластеризацией ее автоматическими методами по принципу “и так сойдет” — посетитель сайта не будет удовлетворен. Поставьте себя на место пользователя. Будете ли вы лояльны к веб-ресурсу, если потратили на нем время, “продирались” через тонну не целевой информации и в результате не нашли ответа на свой вопрос.
Что будет, если не сделать группировку ключевых слов
Считаете, что неудовлетворенность посетителей не такая большая проблема, чтобы делать кластеризацию? Тогда добавьте к этому алгоритмы и фильтры поисковых систем, которые выступают в роли ревизоров. Оценивая качество раскрытия темы на странице сайта, они выносят вердикт какого места в топе вы достойны.
Если хотите, чтобы посещаемость веб-ресурса росла и не было проблем с ранжированием, рекомендую уделить время и сделать качественную разгруппировку ядра. К тому же, целевой трафик намного проще монетизировать, предлагаю людям, то зачем они пришли.
Методы кластеризации
Глядя, на ключевую фразу не всегда можно логически понять о чем думал человек, вбивая ее. Фразы могут быть очень близкими синтаксически, но совершенно разные по потребностям (интенту). Особенно — это касается ключей, состоящих из одного или двух слов.
Например, запросы “программа” и “программы” отличаются только словоформой, а выдача для них будет совершенно разная. В первом случае имеется в виду программа передач, а во втором — софт.
Для того, чтобы распределить ключевики по группам нужно точно понимать, что именно имелось в виду. И в этом нам помогут сами пользователи поисковых систем.
Переходя на сайт по разным запросам люди оставляют обратную связь. Логично, что если человек не находит на странице ответ на свой вопрос, он не будет проводить на ней много времени. Скорее всего сразу закроет ее и продолжит анализировать выдачу дальше. Поисковые системы учитывают такие сигналы. И если по совокупности факторов они видят, что пользователь удовлетворен ответом, который он нашел на странице, то повышают ее в выдаче. Если нет — понижают. Конечно, это происходит не сразу, а по мере накопления статистики посещений.
Нахождение одной и той же страницы в ТОП 10 Яндекса по разным фразам говорит о том, что эти запросы связаны одной потребностью. Чем больше общих урлов есть между фразами, тем эта связь сильнее.
Мы подошли к пониманию того, что анализ позиций поисковых запросов по выдаче позволяет получить более точные данные для распределения поисковых запросов. В зависимости от целей и задач различают разные методы кластеризации. Поговорим более подробно о каждом из них.
Soft-кластеризацию еще часто называют не строгой. Ее суть в том, что выбирается одна фраза, как правило самая частотная и все остальные ключевики, которые образуют с ней одну группу должны содержать N-ое количество общих урлов, При этом между собой они могут быть не связаны и пересечения не обязательно должны быть по одним и тем же адресам.
N — это порог кластеризации, который показывает сколько должно быть пересечений по выдаче, чтобы их можно было сгруппировать.
Разберем на простом примере — свадьба друга. Жених приглашает всех своих знакомых на торжество. Они могут не знать друг друга, но при этом все хорошо знают виновника мероприятия.
Такой метод объединения запросов хорошо работает для информационных сайтов и при работе по стратегии трафикового продвижения.
Hard-кластеризация или жесткая группировка. В основе этого метода лежит принцип, объединения в кластер фраз, которые имеют N общих урлов друг с другом.
Где N — порог кластеризации и показывает какое количество совпадений по адресам должно быть в ТОП-10 между фразами, чтобы можно было их сгруппировать.
Приведу аналогию. Допустим существует закрытый клуб, в который принимают только тех кто умеет играть в покер, достиг совершеннолетнего возраста и имеет стабильный доход от 50 тысяч рублей. То есть, критерий объединения — соблюдение 3-х условий.
Этот метод хорош для работы с коммерческой выдачей и высококонкурентными запросами, а также когда выбрана стратегия продвижения по позициям.
Как правильно сделать группировку ключевых фраз из семантического ядра
Существуют 4 основных метода кластеризации ключевых фраз: вручную, в автоматическом режиме, через Кей Коллектор и по маркерам. Для тестов я собрал поисковые запросы на тему “Как класть приборы после еды в ресторане”. На выходе получился такой набор фраз. Разберем на конкретном примере правильный порядок действий для каждого из методов, а также их плюсы и минусы.
Вручную, с использованием вспомогательных инструментов
Преимущество работы с ключевыми фразами в Excel и его бесплатных аналогах (OpenOffice, LibreOffice, docs.google.com) только в удобном представлении информации и наличии фильтров для сортировки запросов. Они не уменьшают высокую вероятность ошибки при ручной группировке. Особенно — это заметно в коммерческих тематиках. Поэтому для получения качественного результата необходимо проверять выдачу по всем спорным запросам.
Инструкция:
В автоматическом режиме
Если при ручной группировке ключевых слов мы сами распределяли запросы, то в этом методе все делают специализированные программы и онлайн сервисы. Разберем пошаговый порядок действий для получения качественных результатов при работе, как с платными, так и с бесплатными инструментами.
Бесплатно
Из всех группировщиков ключевых фраз этой категории, рекомендую два — от Кулакова и свой собственный. Они оба распределяют запросы, ориентируясь на ТОП-10 выдачи поисковой системы Яндекс.
Сервис Кулакова
Кластеризатор Кулакова не всегда точно распределяет фразы, но для черновой группировки лучшее решение из бесплатных. Его основными преимуществами являются: простейший интерфейс, неплохое качество работы и возможность посмотреть какие страницы лидируют по видимости в Яндексе.
Инструкция:
Группировщик от Altblog — версия 1 и 2
Хорошо работает в паре с инструментом Кулакова. Благодаря, высокой точности кластеризации помогает быстро очистить, получившиеся кластеры от левых запросов. Также хорош, как чистильщик групп от всего лишнего в Кей Коллекторе. В качестве полноценного самостоятельного кластеризатора для больших ядер, рекомендую использовать версию, начиная с 3-ой. Там нет ограничений на количество входных фраз, значительно расширен функционал и есть возможность загрузки файла, экспортируемого из Кей Коллектора в один клик.
1-ая и 2-ая версия группировщика обрабатывают за раз не более 100 запросов. Для семантических ядер это мало, поэтому используйте связку «Кулаков — Altblog (1,2)».
Порядок действий:
Платно
Из платных кластеризаторов тестировал много разных инструментов. Адекватно работают 2 сервиса и 2 программы. Сервисы, дающие высокую точность: Джаст Мэджик и Раш Аналитикс. Пользоваться ими просто, но с учётом стоимости группировки — ядра будут золотыми. Для разовых проверок и когда нужно определить входные ключи для текстового анализатора конечно стоит использовать.
На больших объемах проще и выгодней использовать программу Key Assort и кластеризатор от Altblog (от 3 версии и выше). При правильных настройках оба инструмента показывают отличные результаты. О тонкостях работы с ними мы и поговорим дальше.
Rush Analytics и JustMagic
Простое решение для тех кто не хочет заморачиваться. Пополнил баланс, загрузил список фраз, выбрал регион продвижения и порог группировки, получил результат.
Принцип работы сервисов Раш Аналитикс и Джаст Мэджик очень похож, поэтому разберем порядок действий на примере одного из них. В сервисе Rush Analytics сразу после регистрации вы получаете 200 лимитов, которые можно потратить на любые нужды. Этого вполне хватит для кластеризации 363 фраз, если нужно больше придется покупать тарифный план. Их стоимость начинается от 999 рублей.
Инструкция:
Key Assort
Отличный инструмент, который подойдет для разгруппировки ядер даже в несколько сотен тысяч ключей. Работает в 3-х режимах: Soft, Hard и Medium. Для анализа используются данные поисковой выдачи Яндекса. Также важно, что есть возможность добавить в исключения сервисы Яндекса и различные трастовые домены и агрегаторы, которые часто присутствуют в топе по нескольким кластерам.
Инструкция
Altblog — кластеризатор
Моя собственная разработка в которой были учтены все нюансы работы с семантикой. Когда ежедневно занимаешься сбором ключевых фраз, видишь все недостатки сервисов группировки. Одни хороши для коммерции, другие лучше подходят для контентных проектов. А простого инструмента в котором было бы все сбалансировано с минимумом ручных правок просто нет. Необходимость упростить и автоматизировать работу с семантикой и привела к созданию “Altblog-кластеризатора”. Полный обзор инструмента смотрите на этой странице. В этом материале рассмотрим порядок действий и итоговый результат для тестового примера.
Инструкция:
Группировка по маркерам ( экспертный метод)
Обычно после автоматической кластеризации принято просматривать группы вручную. Чистить их от лишних запросов или наоборот объединять несколько кластеров в один. Более эффективная тактика — перед сбором семантического ядра составить черновую структуру по конкурентам. По ней собрать семантику, а затем в тех кластерах, что получились выбрать один основной запрос. Тот под который будет продвигаться страница. Его отмечаем маркером. Далее делаем перегруппировку по всем маркерным запросам. Так распределение ключевых фраз получается намного более качественным и значительно сокращается время ручной работы. Эта методика позволяет сократить время группировки запросов в 3-4 раза. Ей пользуются передовые SEO-компании, а теперь думаю, что и вы.
Если считаешь, что в СЕО больше не осталось секретов —не подписывайсяна мою закрытую группу вконтакте. Продвигайся как все!
Работу с маркерами поддерживают сервисы Just Magic, Rush Analitics и 2 программы — Key Assort и Altblog-кластеризатор. Я рекомендую пользоваться именно софтом — выходит дешевле и проще.
В Key Collector
Программа используется для сбора семантического ядра и чистки его от стоп-слов, фраз пустышек. Основной принцип объединения ключевиков — близость слов по написанию. Такой метод не подходит при работе с интентом, потому что словоформы одного и того же слова могут содержать разные смыслы. Например, “мобильник” и “мобильники”. В первом случае, люди ищут фильм, во втором — интересуются телефонами.
Использовать Кей Коллектор стоит только для группировки информационных запросов. В коммерческой выдаче без кластеризации по ТОПу сложно точно определить потребность пользователя.
Инструкция:
Выводы
От качества кластеризации зависит успех продвижения и конверсия всего сайта. Если страница продвигается по запросам из разных кластеров — это увеличивает количество отказов и уменьшает КПД ее оптимизации. В результате требуется больше усилий, чтобы вывести в ТОП заветные ключевые фразы. А без понимания интента, в конечном итоге они могут вообще оказаться не самыми целевыми для вашего бизнеса.
Я рекомендую при группировке ключей для коммерческих сайтов ориентироваться на поисковую выдачу и использовать инструменты, проверенные на практике: Altblog (3 версия и выше) или Key Assort с маркерами. Для информационных ресурсов можно подготовить семантику и бесплатными методами, с помощью связки Кулаков-ALtblog или Кей-Коллектора, но все-таки лучше не экономить — особенно, если вы работаете в конкурентных нишах.
, то 
.
,
