Кластеризация графов и поиск сообществ. часть 1: введение, обзор инструментов и волосяные шары

Внутренняя отметка

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

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

Описание

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

Таким образом, любое наблюдение (объект) принадлежит ко всем кластерам, но с разной вероятностью. Объект должен быть отнесен к тому кластеру, для которого данная вероятность выше.

Что делать после кластеризации

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

Каждой группе соответствует отдельная страница сайта. Для каждой страницы нужно подготовить Title, Description, H1 и URL, в которых будут использованы поисковые запросы из кластера, а также атрибут alt для тега img и предусмотреть использование запросов в других зонах.

Некластеризованные запросы

Запросы, которые не были включены ни в один кластер, удалять не нужно. Вы можете добавить их на отдельные страницы сайта (например, в разделах «Статьи» или «Блог») или включить в какой-то из имеющихся кластеров по смыслу.

Финальная проверка

Финальная проверка делается на этапе составления контент-плана – определяется соответствие запросов в кластере интентам пользователей и возможная полнота раскрытия темы.

Примечания

  1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  2. Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. — 176 с.
  3. Хайдуков Д. С. Применение кластерного анализа в государственном управлении// Философия математики: актуальные проблемы. — М.: МАКС Пресс, 2009. — 287 с.
  4. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  5. Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. — С. 10.
  6. Tryon R.C. Cluster analysis. — London: Ann Arbor Edwards Bros, 1939. — 139 p.
  7. Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
  8. Дюран Б., Оделл П. Кластерный анализ. — М.: Статистика, 1977. — 128 с.
  9. Вятченин Д. А. Нечёткие методы автоматической классификации. — Минск: Технопринт, 2004. — 219 с.
  10. Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989—215 с.

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

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

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

Таблица 1 — Оценка сложности для 19 мер качества кластеризации.

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

Обзор инструментов

Очень модный и развивающийся нынче . Его нужно было написать первым элементом в списке, но как таковых готовых алгоритмов кластеризации там пока нет (версия 1.4.1). Есть подсчет треугольников и связных компонент, что, вкупе с стандартными операциями над Spark RDD, можно использовать для написания своих алгоритмов. Пока что у GraphX есть апи только для scala, что также может усложнить его использование.
Библиотека для Apache Giraph под названием Okapi использует несколько алгоритмов, в том числе достаточно новый алгоритм собственной разработки под названием , основанный на label propagation. Giraph — это надстройка над Hadoop, предназначенная для обработки графов. В ней почти нет машинного обучения, и для компенсации этого в компании Telefonica и был создан Okapi. Вероятно, сейчас Giraph выглядит уже не так перспективно на фоне GraphX, но сам алгоритм Spinner хорошо ложится и на парадигму Spark. Про Spinner можно прочитать здесь.
Библиотека graph-tool для питона содержит несколько новейших алгоритмов кластеризации и очень быстро работает. Мы использовали её для сличения URL, соответствующих одному и тому же товару

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

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

В последнее время проект вновь ожил и ожидается версия 0.9

GraphLab Create. Это питоновская обертка над C++, позволяющая прогонять машинное обучение как локально, так и распределенно (на Yarn). Кластеризации графов там все ещё нет, только .
Хваленый networkX, несмотря на обилие алгоритмов, не умеет кластеризовать графы, но только анализировать связные компоненты и клики. Вдобавок он намного медленнее graph-tool, и по части визуализации уступает тому же graph-tool и gephi.
Реализация алгоритма марковской кластеризации (MCL) от его изобретателя. Автор снизил сложность обычного MCL в худшем случае с до , где — число узлов, а — максимальная степень узла, и обижается, когда алгоритм MCL называют немасштабируемым.Также он добавил фишки для регулировки числа кластеров. Однако у MCL было несколько других серьезных проблем, и непонятно, решены ли они. Например, проблема нестабильности размера кластеров (наш небольшой эксперимент выдал одну гигантскую связную компоненту и много маленьких кластерочков по 2-3 узла, но, возможно, мы не нашли нужную ручку). Последняя новость на сайте датируется 2012 годом, что не очень хорошо.
Разные реализации одного из самых популярных алгоритмов Louvain: для C, для Python, ещё для Python. Классическая статья про этот алгоритм: ссылка.
Сайт, посвященный алгоритму Infomap и его модификациям, от авторов метода. Как и везде, есть открытый код. Помимо хорошей поддержки и документации, есть изумительные демки, иллюстрирующие работу алгоритма: вот и вот. Узнать, как работает алгоритм, можно здесь.
Пакет для R под названием igraph. В нем реализовано довольно много алгоритмов кластеризации, но мы не можем сказать ничего конкретного о них, поскольку не изучали пакет.

Формальная постановка задачи кластеризации

Пусть X{\displaystyle X} — множество объектов, Y{\displaystyle Y} — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами ρ(x,x′){\displaystyle \rho (x,x’)}. Имеется конечная обучающая выборка объектов Xm={x1,…,xm}⊂X{\displaystyle X^{m}=\{x_{1},\dots ,x_{m}\}\subset X}. Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике ρ{\displaystyle \rho }, а объекты разных кластеров существенно отличались. При этом каждому объекту xi∈Xm{\displaystyle x_{i}\in X^{m}}
приписывается номер кластера yi{\displaystyle y_{i}}.

Алгоритм кластеризации — это функция aX→Y{\displaystyle a\colon X\to Y}, которая любому объекту x∈X{\displaystyle x\in X} ставит в соответствие номер кластера y∈Y{\displaystyle y\in Y}. Множество Y{\displaystyle Y} в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация (обучение без учителя) отличается от классификации (обучения с учителем) тем, что метки исходных объектов yi{\displaystyle y_{i}} изначально не заданы, и даже может быть неизвестно само множество Y{\displaystyle Y}.

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

  • не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. Следовательно, для определения качества кластеризации требуется эксперт предметной области, который бы мог оценить осмысленность выделения кластеров.
  • число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. Это справедливо только для методов дискриминации, так как в методах кластеризации выделение кластеров идёт за счёт формализованного подхода на основе мер близости.
  • результат кластеризации существенно зависит от метрики, выбор которой, как правило, также субъективен и определяется экспертом. Но стоит отметить, что есть ряд рекомендаций к выбору мер близости для различных задач.

Кластеризация на основе плотности

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

Наиболее популярным методом кластеризации на основе плотности является DBSCAN (алгоритм пространственной кластеризации с присутствием шума). В отличие от многих новых способов он имеет четко определенную кластерную составляющую, называемую «достижимость плотности». Подобно кластеризации на основе связей, она основана на точках соединения в пределах определенных порогов расстояния. Однако такой метод собирает только те пункты, которые удовлетворяют критерию плотности. В исходном варианте, определенном как минимальное количество других объектов в этом радиусе, кластер состоит из всех предметов, связанных плотностью (которые могут образовывать группу произвольной формы, в отличие от многих других методов), а также всех объектов, которые находятся в пределах допустимого диапазона.

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

Основной недостаток DBSCAN и OPTICS заключается в том, что они ожидают некоторого падения плотности для обнаружения границ кластера. Например, в наборах данных с перекрывающимися распределениями Гаусса — распространенный случай использования искусственных объектов — границы кластеров, создаваемые этими алгоритмами, часто выглядят произвольно. Происходит это, поскольку плотность групп непрерывно уменьшается. А в наборе данных, состоящем из смесей гауссианов, эти алгоритмы почти всегда превосходят такие методы, как EM-кластеризация, которые способны точно моделировать системы такого типа.

Среднее смещение — это кластерный подход, при котором каждый объект перемещается в самую плотную область в окрестности на основе оценки всего ядра. В конце концов, объекты сходятся к локальным максимумам непроницаемости. Подобно кластеризации методом к-средних, эти «аттракторы плотности» могут служить представителями для набора данных. Но среднее смещение может обнаруживать кластеры произвольной формы, аналогичные DBSCAN. Из-за дорогой итеративной процедуры и оценки плотности среднее перемещение обычно медленнее, чем DBSCAN или k-Means. Кроме того, применимость алгоритма типичного сдвига к многомерным данным затруднена из-за неравномерного поведения оценки плотности ядра, что приводит к чрезмерной фрагментации хвостов кластеров.

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

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

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

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

Пусть .

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

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

Индекс 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 отвечает оптимальной кластеризации.

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

В поиске самых популярных сервисов очень помог доклад Александра Ожгибесова на 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%

Теорема невозможности Клейнберга[править]

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

Определение:
Алгоритм кластеризации является масштабно инвариантным (англ. scale-invariant), если для любой функции расстояния и любой константы результаты кластеризации с использованием расстояний и совпадают.

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

Определение:
Полнота (англ. Richness). Множество результатов кластеризации алгоритма в зависимости от изменения функции расстояния должно совпадать со множеством всех возможных разбиений множества объектов .

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

Определение:
Функция расстояния является допустимым преобразованием функции расстояния , если

  1. , если и лежат в одном кластере;
  2. , если и лежат в разных кластерах.
Определение:
Алгоритм кластеризации является согласованным (англ. consistent), если результат кластеризации не изменяется после допустимого преобразования функции расстояния.

Третья аксиома требует сохранения кластеров при уменьшении внутрикластерного расстояния и увеличении межкластерного расстояния.

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

Исходя из этих аксиом Клейнберг сформулировал и доказал теорему:

Теорема (Клейнберга, о невозможности):
Для множества объектов, состоящего из двух и более элементов, не существует алгоритма кластеризации, который был бы одновременно масштабно-инвариантным, согласованным и полным.

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

События мыши в кластеризованных точках данныхMouse events on clustered data points

Когда на слое, на котором содержатся кластеризованные точки данных, возникают события мыши, кластеризованная точка данных возвращается в событие в виде объекта признака точки GeoJSON.When mouse events occur on a layer that contains clustered data points, the clustered data point return to the event as a GeoJSON point feature object. Этот признак точки будет иметь следующие свойства:This point feature will have the following properties:

Имя свойстваProperty name ТипType ОписаниеDescription
Логическоеboolean Указывает, представляет ли компонент кластер.Indicates if feature represents a cluster.
строкаstring Уникальный идентификатор кластера, который можно использовать с методами , и для DataSource.A unique ID for the cluster that can be used with the DataSource , , and methods.
numbernumber Число точек, содержащихся в кластере.The number of points the cluster contains.
строкаstring Строка, которая сокращает значение , если оно длинное.A string that abbreviates the value if it’s long. (например, 4000 преобразуется в 4K).(for example, 4,000 becomes 4K)

В этом примере используется слой пузырьков, который визуализирует точки кластера и добавляет событие щелчка.This example takes a bubble layer that renders cluster points and adds a click event. При срабатывании события щелчка код вычисляет и масштабирует карту до следующего уровня масштаба, при котором кластер разбивается.When the click event triggers, the code calculates and zooms the map to the next zoom level, at which the cluster breaks apart. Эта функция реализуется с помощью метода класса и свойства кластеризованной точки данных, которую щелкнули.This functionality is implemented using the method of the class and the property of the clicked clustered data point.

Примечания

  1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  2. Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. — 176 с.
  3. Хайдуков Д. С. Применение кластерного анализа в государственном управлении// Философия математики: актуальные проблемы. — М.: МАКС Пресс, 2009. — 287 с.
  4. Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  5. Мандель И. Д. Кластерный анализ. — М.: Финансы и статистика, 1988. — С. 10.
  6. Tryon R.C. Cluster analysis. — London: Ann Arbor Edwards Bros, 1939. — 139 p.
  7. Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
  8. Дюран Б., Оделл П. Кластерный анализ. — М.: Статистика, 1977. — 128 с.
  9. Вятченин Д. А. Нечёткие методы автоматической классификации. — Минск: Технопринт, 2004. — 219 с.
  10. Олдендерфер М. С., Блэшфилд Р. К. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И. С. Енюкова. — М.: Финансы и статистика, 1989—215 с.

Заключение

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

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

Автоматическая кластеризация не дает 100% точного результата, в большинстве случаев кластеры необходимо дорабатывать вручную. Но она существенно упрощает работу оптимизатора, позволяет создать максимально правильную структуру сайта и подготовить грамотные ТЗ.

Материалы по теме:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector