Открытый курс машинного обучения. тема 7. обучение без учителя: pca и кластеризация

Плотностные алгоритмы

Другой класс алгоритмов – плотностные. Они так называются потому, что
определяют кластер как группу объектов,расположенных достаточно кучно. Под
кучностью понимают то, что в эпсилон-окрестности точки есть некоторое
минимальное количество других объектов: d(x_i,x_j)
для некоторого количества j > Minpts.

Алгоритм DBSCAN

Алгоритм DBSCAN обычно проводится над данными, упорядоченными в R-деревья
(для удобства выборки окрестных точек). Но в общем случае этого не требует.

0. Выбираем окрестность ε, в которой мы будем
требовать наличия Minpts объектов, и сам Minpts.

1. Берем произвольный еще не обработанный объект. Проверяем для него, что в
эпсилон-окрестности точки есть некоторое минимальное количество других объектов:
d(x_i,x_j)
для некоторого количества j > Minpts. Если это не так, то
очевидно, что эта точка – шум. Берем следующую.

2. Если это не так, то помечаем эту точку как принадлежащую кластеру. Это так
называемая корневая точка. Заносим окружающие ее точки в отдельную категорию.

2.1. Для каждой еще не обработанной точки из этой категории сначала помечаем
ее как принадлежащую кластеру, а затем проверяем то же самое: что в
эпсилон-окрестности точки есть некоторое минимальное количество других объектов:
d(x_i,x_j)
для некоторого количества j > Minpts. Если это так, то заносим
эти точки в эту же категорию.

2.2. После проверки выносим точку из этой временной категории. Очевидно, что
рано или поздно точки в данной категории кончатся (мы достигнем границ кластера,
где правило кучности не выполняется). Тогда переходим к шагу 1. Иначе
возвращаемся к шагу 2.1.

Этот алгоритм имеет сложность O(NlogN). Очевидно, что основным его
недостатком является неспособность связывать кластеры через узкие места, где
правило плотности не выполняется.

Сравнение[править]

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

В Таблице 1 приведены оценки сложности мер качества кластеризации ( — число объектов в рассматриваемом наборе данных):

Из всех рассмотренных мер, меры , , и наиболее полно соответствуют когнитивному представлению асессоров о качестве кластеризации.

Внешние меры оценки качества[править]

Данные меры используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д.

Обозначенияправить

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

Пусть .

Также рассмотрим пары из элементов кластеризуемого множества . Подсчитаем количество пар, в которых:

• Элементы принадлежат одному кластеру и одному классу —
• Элементы принадлежат одному кластеру, но разным классам —
• Элементы принадлежат разным кластерам, но одному классу —
• Элементы принадлежат разным кластерам и разным классам —

Индекс Randправить

Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.

Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.

Индекс Adjusted Randправить

где — значения из таблицы сопряженности.

В отличие от обычного , индекс Adjusted Rand может принимать отрицательные значения, если .

Индекс Жаккара (англ. Jaccard Index)править

Индекс Жаккара похож на , только не учитывает пары элементов находящиеся в разные классах и разных кластерах ().

Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.

Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index)править

Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.

Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.

Hubert Г statisticправить

Данная мера отражает среднее расстояние между объектами разных кластеров:

где , — матрица близости, а

Можно заметить, что два объекта влияют на , только если они находятся в разных кластерах.

Чем больше значение меры — тем лучше.

Entropyправить

Энтропия измеряет “чистоту” меток классов:

Стоит отметить, что если все кластера состоят из объектов одного класса, то энтропия равна 0.

Purityправить

Чистота ставит в соответствие кластеру самый многочисленный в этом кластере класс.

Чистота находится в интервале , причём значение = 1 отвечает оптимальной кластеризации.

Зачем нужны сервисы кластеризации?

В один кластер должны быть объединены только такие запросы, которые имеют хорошие шансы выйти в топ-10 поисковых систем с общей релевантной страницей. То есть, если по двум запросам в выдаче все страницы сайтов разные и нет пересечений, то следует относить их к разным кластерам. Также и наоборот: если два запроса возможно продвинуть на одной статье, то не следует разносить их на разные кластеры, чтобы не писать лишнего – бюджет на контент не резиновый.

Общая схема составления ТЗ на написание SEO-статьи следующая:

Сбор семантики – статистика поисковых систем, базы семантики, внутренняя статистика проекта;
Кластеризация автоматическая – сервис или программа для кластеризации по подобию топов;
«Посткластеризация» ручная – обработка того что не удалось кластеризовать автоматически;
Приоритезация – определение важности полученных запросов в каждом кластере;
Оформление ТЗ для копирайтера – лемматизация, LSI и различные указания для написания статей, по статье на каждый кластер.

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

Методика сравнения

Суть сравнения сервисов в следующем: выбрать идеально кластеризованный список запросов – эталонное ядро. Сравнить результаты кластеризации каждого сервиса с эталонным.

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

Было взято ядро на 2500+ ключевых фраз, которое отслеживается уже много месяцев. Из него выбраны только запросы вышедшие в топ-5 Яндекса. И из них взяты только те которые имеют релевантной страницу одного из широких разделов (категория вопроса, тема вопроса, категория документа, страница с формой «задать вопрос»), а не узкую страницу вопроса с ответами. Запросы были сгруппированы по релевантной странице. Оставлены только группы в которых более чем 4 запроса. В итоге получилось 292 запроса разбитых на 22 кластера.

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

Сравнение сервисов

В поиске самых популярных сервисов очень помог доклад Александра Ожгибесова на BDD-2017, к тем, что у него было добавлено еще несколько сервисов, получился такой список:

1. Топвизор
2. Pixelplus
3. Serpstat
4. Rush Analytics
5. Just Magic
6. Key Collector
7. MindSerp
8. Semparser
9. KeyAssort
10. coolakov.ru

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

Но только такого сравнения не достаточно. Сервисы делятся на два подхода к некластеризованному остатку фраз:

• сделать для них общую группу «Некластеризованные»;
• сделать для каждой некластеризованной фразы группу из нее одной.

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

Результаты сравнения:

• Топвизор
  • разные группы эталона в одной по сервису – 4%
  • одна группа эталона в разных по сервису – 7%
• Pixelplus
  • разные группы эталона в одной по сервису – 0%
  • одна группа эталона в разных по сервису – 7%
• Serpstat
  • разные группы эталона в одной по сервису – 0%
  • одна группа эталона в разных по сервису – 3%
• Rush Analytics (132 фразы, demo)
  • разные группы эталона в одной по сервису – 11%
  • одна группа эталона в разных по сервису – 8%
• Just Magic
  • разные группы эталона в одной по сервису – 0%
  • одна группа эталона в разных по сервису – 9%
• Key Collector
  • разные группы эталона в одной по сервису – 12%
  • одна группа эталона в разных по сервису – 16%
• MindSerp – не удалось получить демо, не выходят на связь
• Semparser
  • разные группы эталона в одной по сервису – 1%
  • одна группа эталона в разных по сервису – 3%
• KeyAssort
  • разные группы эталона в одной по сервису – 1%
  • одна группа эталона в разных по сервису – 1%
• coolakov.ru
  • разные группы эталона в одной по сервису – 0%
  • одна группа эталона в разных по сервису – 18%

Классификация алгоритмов

• Иерархические алгоритмы;
  • Агломеративные алгоритмы;
  • Дивизимные алгоритмы.
• Неиерархические алгоритмы
  • По методу
    • Итеративные
    • Плотностные
    • Модельные
    • Концептуальные
    • Сетевые.

Принято делить все алгоритмы кластеризации на иерархические и
неиерархические. Деление это происходит по выдаваемым на выходе данным.
Иерархические алгоритмы на выходе выают некую иерархию кластеров, и мы вольны
выбрать любой уровень этой иерархии для того, чтобы интерпретировать результаты
алгоритма. Неиерархические – это, фактически, все алгоритмы, которые на выходе
иерархию не выдают (или выбор интерпретации происходит не по уровню иерархии).

Инструменты кластеризации семантического ядра

Выделяют несколько видов семантических ядер:

• Семантическое ядро, помогающее в разработке контентного плана.
• Семантическое ядро для снятия позиций сайта.
• Семантическое ядро для Директа (или для вообще любой системы контекстной рекламы не только Яндекс.Директ, но и Гугл.ЭдВордс).

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

• Кластеризация по близости поисковых выдач (SERP-ов).
• Кластеризация запросов по принципу «вопрос / не вопрос».
• Кластеризация по «сложности ключевого слова» (keyword difficulty).
• Кластеризация по частотности запросов.

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

• Topvisor.ru. Осуществляет кластеризацию по близости поисковых выдач (SERP-ов).
• SerpStat.com. Помогает вычленить из большого набора фраз те, которые являются вопросами, тем самым осуществив кластеризацию по принципу «вопрос / не вопрос». Кроме того, позволяет отфильтровать фразы с топонимами. Напомним, что кроме этого, основным предназначением сервиса является сбор семантических ядер конкурентов.
• Ahrefs.com. Позволяет оценить «сложность завоевания ключевого слова» (keyword difficulty – KD). Целесообразно использовать этот параметр вместе с частотностью фразы: это позволяет отобрать самые простые (легкие для завоевания) и одновременно сочные запросы из имеющихся, таким образом осуществив кластеризацию по принципу «легкие и среднечастотные / все остальные». Такой анализ семантического ядра сайта представляется очень перспективным в долгосрочной перспективе.

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

• Полнота («равномерность») кластеризации.
• Быстрота создания программы-минимум.
• Акцент на трафик.
• Акцент на конверсию из трафика в покупатели.

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

Список источников

• bourabai.ru