Как определяется ошибка кластеризации

  Перевод

  Ссылка на автора

Введение

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

1. Наше предположение о количестве (реальных) кластеров неверно.
2. Особенность пространства очень размерна.
3. Кластеры бывают странной или неправильной формы.

Все эти условия могут привести к проблемам с K-Means, так что давайте посмотрим.

Неверное количество кластеров

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

from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs, make_circles, make_moons
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
import pandas as pd
import itertools
def compare(N_features, C_centers, K_clusters, dims=[0, 1],*args):
    data, targets = make_blobs(
      n_samples=n_samples if 'n_samples' in args else 400,
      n_features=N_features,
      centers=C_centers,
      cluster_std=cluster_std if 'cluster_std' in args else 0.5,
      shuffle=True,
      random_state=random_state if 'random_state' in args else 0)



  


                       
  






    FEATS = ['x' + str(x) for x in range(N_features)]
    X = pd.DataFrame(data, columns=FEATS)
    X['cluster'] = 
		KMeans(n_clusters=K_clusters, random_state=0).fit_predict(X)
    fig, axs = plt.subplots(1, 2, figsize=(12, 4))
    axs[0].scatter(data[:, dims[0]], data[:, dims[1]],
        c='white', marker='o', edgecolor='black', s=20)
    axs[0].set_xlabel('x{} [a.u.]'.format(dims[0]))
    axs[0].set_ylabel('x{} [a.u.]'.format(dims[1]))
    axs[0].set_title('Original dataset')
    axs[1].set_xlabel('x{} [a.u.]'.format(dims[0]))
    axs[1].set_ylabel('x{} [a.u.]'.format(dims[1]))
    axs[1].set_title('Applying clustering')
    colors = itertools.cycle(['r', 'g', 'b', 'm', 'c', 'y'])
    for k in range(K_clusters):
        x = X[X['cluster'] == k][FEATS].to_numpy()
        axs[1].scatter(
		x[:, dims[0]], 
		x[:, dims[1]], 
		color=next(colors),
		edgecolor='k', 
		alpha=0.5
	)
    plt.show()

Слишком мало кластеров

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

Слишком много кластеров

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

Высокие (er) размерные данные

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

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

fig = plt.figure(figsize=(14, 8))
ax = fig.add_subplot(111, projection='3d')
data, targets = make_blobs(
    n_samples=400,
    n_features=3,
    centers=3,
    cluster_std=0.5,
    shuffle=True,
    random_state=0)
ax.scatter(data[:, 0], data[:, 1], 
    zs=data[:, 2], zdir='z', s=25, c='black', depthshade=True)
ax.set_xlabel('x0 [a.u.]')
ax.set_ylabel('x1 [a.u.]')
ax.set_zlabel('x2 [a.u.]')
ax.set_title('Original distribution.')
plt.grid()
plt.show()

Хотя существует множество способов проецировать этот 3D-набор данных на 2D, существует три основных ортогональных подпространства:

Глядя наx2 : x0проекция, набор данных выглядит так, как если бы он имел только два кластера. Нижний правый «суперкластер» на самом деле представляет собой две отдельные группы, и даже если мы предполагаем,Кправильно(К = 3)Это выглядит как очевидная ошибка, несмотря на то, что кластеры очень локализованы.

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

Это имеет больше смысла!

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

СлучайN, N> 3особенности, мы быне сможет построить весь набор данныхи число 2D проекций будет масштабироваться квадратично сN:

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

Нерегулярные наборы данных

До сих пор мы упоминали о проблемах, которые «на нашей стороне». Мы посмотрели на очень «хорошо себя ведущий» набор данных и обсудили проблемы в области аналитики. Однако что делать, если набор данных не соответствует нашему решению или нашемуРешение проблемы не подходит?Это как раз тот случай, когда распределение данных происходит в странных или неправильных формах.

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

fig, axs = plt.subplots(1, 3, figsize=(14, 4))
# unequal variance
X, y = make_blobs(n_samples=1400,
    cluster_std=[1.0, 2.5, 0.2],
    random_state=2)
y_pred = KMeans(n_clusters=3, random_state=2).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]
axs[0].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[0].set_title("Unequal Variance")



  


                       
  



# anisotropically distributed data
X, y = make_blobs(n_samples=1400, random_state=156)
transformation = [
	[0.60834549, -0.63667341],
	[-0.40887718, 0.85253229]
]
X = np.dot(X, transformation)
y_pred = KMeans(n_clusters=3, random_state=0).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]


axs[1].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[1].set_title("Anisotropicly Distributed Blobs")
# irregular shaped data
X, y = make_moons(n_samples=1400, shuffle=True, 
	noise=0.1, random_state=120)
y_pred = KMeans(n_clusters=2, random_state=0).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]
axs[2].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[2].set_title("Irregular Shaped Data")
plt.show()

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

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

Выводы

В этом посте мы обсудили три основные причины, по которым алгоритм K-Means Clustering дает нам неправильные ответы.

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

Зная эти три ошибки, KMC остается полезным инструментом, особенно при проверке данных или создании меток.

Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:

• Теорема невозможности Клейнберга — не существует оптимального алгоритма кластеризации.
• Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.

Методы оценки качества кластеризации

Метод оценки качества кластеризации — инструментарий для количественной оценки результатов кластеризации.

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

• Внешние (англ. External) меры основаны на сравнении результата кластеризации с априори известным разделением на классы.
• Внутренние (англ. Internal) меры отображают качество кластеризации только по информации в данных.

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

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

Обозначения

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

Пусть .

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

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

Индекс Rand

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

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

Индекс Adjusted Rand

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

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

Индекс Жаккара (англ. Jaccard Index)

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

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

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

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

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

Hubert Г statistic

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

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

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

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

Индекс Phi

Классическая мера корреляции между двумя переменными:

Minkowski Score

Индекс Гудмэна-Крускала (англ. Goodman-Kruskal Index)

Entropy

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

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

Purity

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

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

F-мера

F-мера представляет собой гармоническое среднее между точностью (precision) и полнотой (recall).

Variation of Information

Данная мера измеряет количество информации, потерянной и полученной при переходе из одного кластера в другой.

Внутренние меры оценки качества

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

Компактность кластеров (англ. Cluster Cohesion)

Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.

Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений:

, где — количество кластеров.

Отделимость кластеров (англ. Cluster Separation)

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

Поэтому здесь стоит задача максимизации суммы квадратов отклонений:

, где — количество кластеров.

Индекс Данна (англ. Dunn Index)

Индекс Данна имеет множество вариаций, оригинальная версия выглядит следующим образом:

,

где:

— межкластерное расстояние (оценка разделения), ,

— диаметр кластера (оценка сплоченности), .

Обобщенный Индекс Данна (gD31, gD41, gD51, gD33, gD43, gD53)

Все эти вариации являются комбинациями 3 вариантов вычисления оценки разделения и оценки компактности

Оценки разделения:

,

,

.

Оценки компактности:

,

.

Обобщенный индекс Данна, как и обычный, должен возрастать вместе с улучшением качества кластеризации.

Индекс S_Dbw

Основан на вычислении Евклидовой нормы

и стандартных отклонений

,

.

Сам индекс определяется формулой:

.

Здесь

,

,

, если и в ином случае.

Должен снижаться с улучшением кластеризации.

Силуэт (англ. Silhouette)

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

Оценка для всей кластерной структуры:

,

где:

— среднее расстояние от до других объектов из кластера (компактность),

— среднее расстояние от до объектов из другого кластера (отделимость).

Можно заметить, что

.

Чем ближе данная оценка к 1, тем лучше.

Есть также упрощенная вариация силуэта: и вычисляются через центры кластеров.

Индекс Calinski–Harabasz

Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость — на расстоянии от центроид кластеров до глобального центроида. Должен возрастать.

Индекс C

Индекс C представляет собой нормализованную оценку компактности:

,

где:

,

— сумма минимальных (максимальных) расстояний между парами всех объектов во всем датасете.

Индекс Дэвиcа-Болдуина (англ. Davies–Bouldin Index)

Это, возможно, одна из самых используемых мер оценки качества кластеризации.
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость — как расстояние между центроидами.

,

где:

Существует еще одна вариация данной меры, которая была предложена автором вместе с основной версией:

C-индекс и индекс Дэвиcа-Болдуина должны минимизироваться для роста кластеризации.

Score function

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

,

где:

,

Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.

Индекс Gamma

где:

— число пар таких, что (1) и принадлежат разным кластерам, и (2) ,

.

Индекс COP

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

.

Индекс CS

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

.

Чем меньше значение данного индекса, тем выше качество кластеризации.

Индекс Sym

.

Здесь — дистанция симметрии для точки из кластера .

Чем выше данное значение, тем лучше.

Индексы SymDB, SymD, Sym33

Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно.

SymDB вычисляется аналогично DB с изменением вычисления на:

.

Данная оценка должна уменьшаться для улучшения качества кластеризации.

В SymD переопределена функция :

.

в Sym33 аналогично SymD переопределена :

.

Последние две оценки должны расти для улучшения качества кластеризации.

Negentropy increment

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

.

Здесь , — определитель ковариационной матрицы кластера , — определитель ковариационной матрицы всего датасета.

Данная оценка должна уменьшаться пропорционально росту качества кластеризации.

Индекс SV

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

.

Данная оценка должна увеличиваться.

Индекс OS

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

.

Где

.

при , и в ином случае.

Функции и определены следующим образом:

.

.

Данная оценка, как и предыдущая, должна возрастать.

Сравнение

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

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

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

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

См. также

• Кластеризация
• Оценка качества в задачах классификации и регрессии^{[на 28.01.19 не создан]}

Источники информации

1. Wikipedia — Category:Clustering criteria
2. Сивоголовко Е. В. Методы оценки качества четкой кластеризации
3. Cluster Validation
4. Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.
5. Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp.847-857.

Примечания

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

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

Сегодня мы разберем:

• Что скрывается за страшным словом «кластеризация».
• Какой поисковый интент у «поискового интента».
• Как выйти победителем при первой в своей жизни кластеризации.

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

Если вы не путаете «SEO» и «СЕО», но еще не знаете про разницу между Soft и Hard группировкой, то попали по адресу.
Погнали!

Определяем поисковый интент

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

Первый этап сортировки поисковых запросов начинается с определения интента.

Поисковый интент — это цель, намерение пользователя, которое вкладывается в запрос при поиске.

Поисковый интент используется Google и «Яндексом» для формирования релевантной выдачи, когда сайты сортируются в
поиске с учетом смысловой содержательности поискового запроса и намерения пользователя. Интент может быть
коммерческим, когда намерение пользователя — найти товар или заказать услуги, или информационным, где основная цель —
узнать информацию о продукте.

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

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

Разберем тонкости проверки на примере условно-бесплатного Arsenkin Tools Commerce. Сервис позволяет бесплатно проверять до 100 ключевых слов в день, также можно приобрести подписку за 549 рублей на 1 месяц и проверять до 2 500 запросов. Для проверки достаточно вставить семантическое ядро, выбрать регион и запустить анализ.

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

Коммерческость поискового запроса — это доминирование коммерческого интента у пользователя, вводящего запрос в браузерной строке.

Запросы с коммерческостью менее 35 % имеют информационный интент и подходят для публикации в блоге, FAQ или гайдах, от 60 % — в каталоге товаров и коммерческих страницах. Поисковые запросы с коммерческостью в 35–60 % имеют смешанный интент — использовать их требуется аккуратно, иначе есть риск размыть релевантность страницы.

Для сортировки результаты копируем в таблицу Excel или «Google Таблицы», после чего выделяем столбец с процентным показателем комммерческости и сортируем.

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

Выбираем подходящий метод кластеризации

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

Логическая кластеризация

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

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

Кластеризация по семантической схожести

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

Пример. Группа в семантическом ядре формируется, если у всех поисковых запросов есть пересечение с ключевым словом. Например, “lada check engine”, “купить коврики lada”, и ”как почистить коврики lada” попадут в одну группу, при этом 2 последних поисковых запроса сформируют еще один отдельный кластер.

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

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

Наиболее правильный и популярный способ группировки семантики. Смысл кластеризации заключается в объединении поисковых запросов в кластеры согласно семантической базе сайтов, находящихся в топе выдачи «Яндекс» и Google.

Из популярных программ для кластеризации стоит выделить KeyClusterer, AllSubmitter, а также Key Collector. В отличие от онлайн-сервисов с оплатой по подписке, десктопное ПО приобретается единоразово по лицензии, а скорость кластеризации зависит от производительности компьютера.

Логика метода заключается в поиске пересечений ключевых слов на страницах сайтов, находящихся в топе поисковых систем. Обычно проводится кластеризация по топ-3 или топ-10, реже учитываются список из 50 сайтов в рейтинге.

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

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

Подбираем алгоритм кластеризации семантического ядра по топам

Для корректной кластеризации даже для небольшого сайта рекомендуется сначала провести группировку семантики по топам поисковой выдачи и лишь затем сегментировать спорные ключевые слова вручную. Кластеризация на основании анализа поисковой выдачи может проводиться тремя способами-уровнями: Soft, Middle, Hard. Рассмотрим каждый из них.

Soft-кластеризация

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

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

Soft-кластеризация подойдет небольшим информационным сайтам или интернет-магазинам с маленьким ассортиментом товаров.

Soft-кластеризация может использоваться для сегментирования семантического ядра сайтов-визиток.

Hard-кластеризация

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

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

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

Middle-кластеризация

Middle-кластеризация — компромисс между слабой точностью Soft-метода и жесткостью к отбору Hard-группировки. Выбирается главный тематико-задающий поисковый запрос, к которому привязываются остальные ключевые слова, прошедшие порог кластеризации по количеству URL в выдаче Google или «Яндекс». При этом кластеризатор сравнивает все зависимые с главным запросом ключевые слова друг с другом.

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

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

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

Для кластеризации семантики по анализу поисковых топов можно использовать десктопное ПО или онлайн-сервисы. Различие — в скорости, функциональности и цене. Рассмотрим, какой вариант кластеризации предпочтительнее исходя из задач оптимизатора.

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

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

Наиболее популярным софтом для кластеризации считаются AllSubmitter, KeyClusterer и Key Collector.

Пример кластеризации запросов в Key Collector

Рассмотрим пример группировки семантического ядра на основе анализа поисковой выдаче на примере Key Collector — пожалуй, обязательного инструмента для SEO-специалистов.

Прежде чем приступить к кластеризации, в программу требуется загрузить все семантическое ядро. Если данные собирались в Key Collector, нужно открыть сохраненный файл программы, если со сторонней программы — нужен импорт. Для импорта файлом или добавления вручную скопированных поисковых запросов переходим в раздел «Главная», где выбираем «Добавить фразы». Далее вставляем скопированную семантику или указываем адрес к файлу на компьютере:

Для группировки важно собрать по всем фразам частотность — это можно сделать здесь же в программе

Отмечаем галочкой все поисковые запросы и переходим в раздел «Данные», где нажимаем «Анализ групп». Теперь выбираем параметр «По поисковой выдаче (улучшенная)», отмечаем поисковые системы и количество URL в выдаче для анализа. Далее нужно выбрать силу SERP для кластеризации — для семантики, где преобладают двух- или трехсловные поисковые запросы, будет достаточно порога в 3 пересечения.

На скриншоте показан пример Soft-кластеризации методом «объединения» запросов. Для проведения Hard-кластеризации режим группировки в настройках нужно заменить на «пересечение». При обновлении семантического ядра процедуру кластеризации придется повторить.

Онлайн-сервисы для кластеризации

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

Наиболее популярные сервисы для кластеризации — Coolakov, Semantist и SeoQuick.

Пример онлайн кластеризации запросов в SeoQuick

Для примера рассмотрим SeoQuick — это наиболее доступный и функциональный сервис. Он позволяет сделать за день 4 кластеризации с семантическим ядром до 5 000 ключевых слов.

Затем открываем «Расширенные функции». Также можно импортировать файлы txt, xls, xlsx, csv.

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

Разбираем основные ошибки при кластеризации семантического ядра

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

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

Грамотная кластеризация специалистов агентства Kokoc Group позволила сегментировать семантику после крупного обновления товарного ассортимента, помогла улучшить ранжирование сайта в поиске и увеличить количество уникальных визитов.

Это дало бонус при ранжировании и положительно повлияло на поведенческие факторы.

Если вам требуется помощь с кластеризацией большого семантического ядра или комплексное SEO-продвижение сайта, обращайтесь к специалистам Kokoc Group.

Кластеризация  неразмеченных данных можно выполнить с помощью модуля sklearn.cluster.

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

2.3.1. Обзор методов кластеризации

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

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

Методы трансдуктивной кластеризации (в отличие отметодов индуктивной кластеризации) не предназначены для применения к новым, невидимым данным.

2.3.2. K-средних

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

Алгоритм k-средних делит набор $N$ образцы $X$ в $K$ непересекающиеся кластеры $C$, каждый из которых описывается средним $mu_j$ образцов в кластере. Средние значения обычно называют «центроидами» кластера; обратите внимание, что это, как правило, не баллы из $X$, хотя они живут в одном пространстве.

Алгоритм K-средних нацелен на выбор центроидов, которые минимизируют инерцию или критерий суммы квадратов внутри кластера : $$sum_{i=0}^{n}min_{mu_j in C}(||x_i — mu_j||^2)$$

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

• Инерция предполагает, что кластеры выпуклые и изотропные, что не всегда так. Он плохо реагирует на удлиненные кластеры или коллекторы неправильной формы.
• Инерция — это не нормализованная метрика: мы просто знаем, что более низкие значения лучше, а ноль — оптимально. Но в очень многомерных пространствах евклидовы расстояния имеют тенденцию становиться раздутыми (это пример так называемого «проклятия размерности»). Выполнение алгоритма уменьшения размерности, такого как анализ главных компонентов (PCA) перед кластеризацией k-средних, может облегчить эту проблему и ускорить вычисления.

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

K-средних эквивалентно алгоритму максимизации ожидания с маленькой, все равной диагональной ковариационной матрицей.

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

По прошествии достаточного времени K-средние всегда будут сходиться, однако это может быть локальным минимумом. Это сильно зависит от инициализации центроидов. В результате вычисление часто выполняется несколько раз с разными инициализациями центроидов. Одним из способов решения этой проблемы является схема инициализации k-means++, которая была реализована в scikit-learn (используйте init='k-means++'параметр). Это инициализирует центроиды (как правило) удаленными друг от друга, что, вероятно, приводит к лучшим результатам, чем случайная инициализация, как показано в справочнике.

K-means++ также может вызываться независимо для выбора начальных значений для других алгоритмов кластеризации, sklearn.cluster.kmeans_plusplus подробности и примеры использования см. В разделе .

Алгоритм поддерживает выборочные веса, которые могут быть заданы параметром sample_weight. Это позволяет присвоить некоторым выборкам больший вес при вычислении центров кластеров и значений инерции. Например, присвоение веса 2 выборке эквивалентно добавлению дубликата этой выборки в набор данных $X$.

Метод K-средних может использоваться для векторного квантования. Это достигается с помощью метода преобразования обученной модели KMeans.

2.3.2.1. Низкоуровневый параллелизм

KMeans преимущества параллелизма на основе OpenMP через Cython. Небольшие порции данных (256 выборок) обрабатываются параллельно, что, кроме того, снижает объем памяти. Дополнительные сведения о том, как контролировать количество потоков, см. В наших заметках о параллелизме .

2.3.2.2. Мини-партия K-средних

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

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

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

2.3.3. Распространения близости (Affinity Propagation)

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

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

Главный недостаток метода Распространения близости — его сложность. Алгоритм имеет временную сложность порядка $O(N^2 T)$, где $N$ количество образцов и $T$ — количество итераций до сходимости. Далее, сложность памяти порядка $O(N^2)$ если используется плотная матрица подобия, но может быть сокращена, если используется разреженная матрица подобия. Это делает метод Распространения близости наиболее подходящим для наборов данных малого и среднего размера.

Описание алгоритма: сообщения, отправляемые между точками, относятся к одной из двух категорий. Во-первых, это ответственность $r(i,k)$, которое является накопленным свидетельством того, что образец $k$ должен быть образцом для образца $i$. Второе — доступность $a(i,k)$ что является накопленным свидетельством того, что образец $i$ следует выбрать образец $k$ быть его образцом, и учитывает значения для всех других образцов, которые $k$ должен быть образцом. Таким образом, образцы выбираются по образцам, если они (1) достаточно похожи на многие образцы и (2) выбираются многими образцами, чтобы быть репрезентативными.

Более формально ответственность за образец $k$ быть образцом образца i дан кем-то: $$r(i, k) leftarrow s(i, k) — max [ a(i, k’) + s(i, k’) forall k’ neq k ]$$

Где $s(i,k)$ сходство между образцами $i$ а также $k$. Наличие образца $k$ быть образцом образца $i$ дан кем-то: $$a(i, k) leftarrow min [0, r(k, k) + sum_{i’~s.t.~i’ notin {i, k}}{r(i’, k)}]$$

Начнем с того, что все значения для $r$ и $a$ aустановлены в ноль, и расчет каждой итерации повторяется до сходимости. Как обсуждалось выше, чтобы избежать числовых колебаний при обновлении сообщений, коэффициент демпфирования $lambda$ вводится в итерационный процесс: $$r_{t+1}(i, k) = lambdacdot r_{t}(i, k) + (1-lambda)cdot r_{t+1}(i, k)$$ $$a_{t+1}(i, k) = lambdacdot a_{t}(i, k) + (1-lambda)cdot a_{t+1}(i, k)$$

где $t$ указывает время итерации.

2.3.4. Средний сдвиг

MeanShift кластеризация направлена ​​на обнаружение капель в образцах с плавной плотностью. Это алгоритм на основе центроидов, который работает, обновляя кандидатов в центроиды, чтобы они были средними точками в данном регионе. Затем эти кандидаты фильтруются на этапе постобработки, чтобы исключить почти дубликаты и сформировать окончательный набор центроидов.

Учитывая центроид кандидата $x_i$ для итерации $t$, кандидат обновляется в соответствии со следующим уравнением: $$x_i^{t+1} = m(x_i^t)$$

Где $N(x_i)$ это соседство образцов на заданном расстоянии вокруг $x_i$ а также $m$ — вектор среднего сдвига, который вычисляется для каждого центроида, который указывает на область максимального увеличения плотности точек. Это вычисляется с использованием следующего уравнения, эффективно обновляющего центроид до среднего значения выборок в его окрестности: $$m(x_i) = frac{sum_{x_j in N(x_i)}K(x_j — x_i)x_j}{sum_{x_j in N(x_i)}K(x_j — x_i)}$$

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

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

Маркировка нового образца выполняется путем нахождения ближайшего центроида для данного образца.

2.3.5. Спектральная кластеризация

SpectralClustering выполняет низкоразмерное встраивание матрицы аффинности между выборками с последующей кластеризацией, например, с помощью K-средних, компонентов собственных векторов в низкоразмерном пространстве. Это особенно эффективно с точки зрения вычислений, если матрица аффинности является разреженной, а amgрешатель используется для проблемы собственных значений (обратите внимание, amg что решающая программа требует, чтобы был установлен модуль pyamg ).

Текущая версия SpectralClustering требует, чтобы количество кластеров было указано заранее. Это хорошо работает для небольшого количества кластеров, но не рекомендуется для многих кластеров.

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

similarity = np.exp(-beta * distance / distance.std())
См. Примеры такого приложения.

2.3.5.1. Различные стратегии присвоения меток

Могут использоваться различные стратегии присвоения меток, соответствующие assign_labels параметру SpectralClustering. "kmeans" стратегия может соответствовать более тонким деталям, но может быть нестабильной. В частности, если вы не контролируете random_state, он может не воспроизводиться от запуска к запуску, так как это зависит от случайной инициализации. Альтернативная "discretize" стратегия воспроизводима на 100%, но имеет тенденцию создавать участки довольно ровной и геометрической формы.

2.3.5.2. Графики спектральной кластеризации

Спектральная кластеризация также может использоваться для разбиения графов через их спектральные вложения. В этом случае матрица аффинности является матрицей смежности графа, а SpectralClustering инициализируется с помощью affinity='precomputed':

>>> from sklearn.cluster import SpectralClustering
>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,
...                         assign_labels='discretize')
>>> sc.fit_predict(adjacency_matrix) 

2.3.6. Иерархическая кластеризация

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

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

• Ward минимизирует сумму квадратов разностей во всех кластерах. Это подход с минимизацией дисперсии, и в этом смысле он аналогичен целевой функции k-средних, но решается с помощью агломеративного иерархического подхода.
• Максимальное (Maximum) или полное связывание (complete linkage) сводит к минимуму максимальное расстояние между наблюдениями пар кластеров.
• Среднее связывание (Average linkage) минимизирует среднее расстояние между всеми наблюдениями пар кластеров.
• Одиночная связь (Single linkage) минимизирует расстояние между ближайшими наблюдениями пар кластеров.

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

2.3.6.1. Различные типы связи: Ward, полный, средний и одиночный связь

AgglomerativeClustering поддерживает стратегии Ward, одиночного, среднего и полного связывания.

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

2.3.6.2. Визуализация кластерной иерархии

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

2.3.6.3. Добавление ограничений связи

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

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

Ограничения связности накладываются через матрицу связности: scipy разреженную матрицу, которая имеет элементы только на пересечении строки и столбца с индексами набора данных, которые должны быть связаны. Эта матрица может быть построена из априорной информации: например, вы можете захотеть сгруппировать веб-страницы, объединяя только страницы со ссылкой, указывающей одну на другую. Это также можно узнать из данных, например, используя sklearn.neighbors.kneighbors_graph для ограничения слияния до ближайших соседей, как в этом примере , или с помощью, sklearn.feature_extraction.image.grid_to_graphчтобы разрешить слияние только соседних пикселей на изображении, как в примере с монетой.

2.3.6.4. Варьируя метрику

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

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

Рекомендации по выбору метрики — использовать метрику, которая максимизирует расстояние между выборками в разных классах и минимизирует его внутри каждого класса.

2.3.7. DBSCAN

Алгоритм DBSCAN рассматривает кластеры , как участки высокой плотности , разделенных районах с низкой плотностью. Из-за этого довольно общего представления кластеры, обнаруженные с помощью DBSCAN, могут иметь любую форму, в отличие от k-средних, которое предполагает, что кластеры имеют выпуклую форму. Центральным компонентом DBSCAN является концепция образцов керна , то есть образцов, находящихся в областях с высокой плотностью. Таким образом, кластер представляет собой набор образцов керна, каждый из которых находится близко друг к другу (измеряется с помощью некоторой меры расстояния), и набор образцов, не относящихся к керну, которые близки к образцу керна (но сами не являются образцами керна). В алгоритме есть два параметра, min_samples и eps, которые формально определяют, что мы имеем в виду, когда говорим «плотный» . Выше min_samples или ниже eps указывают на более высокую плотность, необходимую для формирования кластера.

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

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

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

На рисунке ниже цвет указывает на принадлежность к кластеру, а большие кружки обозначают образцы керна, найденные алгоритмом. Меньшие кружки — это неосновные образцы, которые все еще являются частью кластера. Более того, выбросы обозначены ниже черными точками.

2.3.8. ОПТИКА

В OPTICS акции алгоритма много общих с DBSCAN алгоритмом, и можно рассматривать как обобщение DBSCAN, что расслабляет epsтребование от одного значения до диапазона значений. Ключевое различие между DBSCAN и OPTICS заключается в том, что алгоритм OPTICS строит граф достижимости , который назначает каждой выборке reachability_ расстояние и точку в ordering_ атрибуте кластера ; эти два атрибута назначаются при подборе модели и используются для определения принадлежности к кластеру. Если OPTICS запускается со значением по умолчанию inf, установленным для max_eps, то извлечение кластера в стиле DBSCAN может выполняться повторно за линейное время для любого заданного eps значения с использованием этого cluster_optics_dbscan метода. Параметр max_eps более низкое значение приведет к сокращению времени выполнения, и его можно рассматривать как максимальный радиус окрестности от каждой точки для поиска других потенциальных достижимых точек.

Расстояния достижимости, генерируемые OPTICS, позволяют извлекать кластеры с переменной плотностью в пределах одного набора данных. Как показано на приведенном выше графике, объединение расстояний достижимости и набора данных ordering_ дает график достижимости , где плотность точек представлена ​​на оси Y, а точки упорядочены таким образом, что соседние точки являются смежными. «Вырезание» графика достижимости по одному значению дает результаты, подобные DBSCAN; все точки над «вырезом» классифицируются как шум, и каждый раз, когда есть перерыв при чтении слева направо, означает новый кластер. При извлечении кластеров по умолчанию с помощью OPTICS анализируются крутые уклоны на графике, чтобы найти кластеры, и пользователь может определить, что считается крутым уклоном, используя параметр xi. Существуют также другие возможности для анализа на самом графике, такие как создание иерархических представлений данных с помощью дендрограмм графика достижимости, а иерархия кластеров, обнаруженных алгоритмом, может быть доступна через cluster_hierarchy_ параметр. Приведенный выше график имеет цветовую кодировку, поэтому цвета кластеров в плоском пространстве соответствуют кластерам линейных сегментов на графике достижимости. Обратите внимание, что синий и красный кластеры находятся рядом на графике достижимости и могут быть иерархически представлены как дочерние элементы более крупного родительского кластера.

2.3.9. BIRCH (сбалансированное итеративное сокращение и кластеризация с использованием иерархий — balanced iterative reducing and clustering using hierarchies)

Для Birch заданных данных он строит дерево, называемое деревом функций кластеризации (CFT). Данные по существу сжимаются с потерями до набора узлов Clustering Feature (CF Nodes). Узлы CF имеют ряд подкластеров, называемых подкластерами функций кластеризации (подкластеры CF), и эти подкластеры CF, расположенные в нетерминальных узлах CF, могут иметь узлы CF в качестве дочерних.

Подкластеры CF содержат необходимую информацию для кластеризации, что избавляет от необходимости хранить все входные данные в памяти. Эта информация включает:

• Количество образцов в подкластере.
• Линейная сумма — n-мерный вектор, содержащий сумму всех выборок.
• Squared Sum — сумма квадратов нормы L2 всех выборок.
• Центроиды — чтобы избежать пересчета линейной суммы / n_samples.
• Квадратная норма центроидов.

Алгоритм BIRCH имеет два параметра: порог и коэффициент ветвления. Фактор ветвления ограничивает количество подкластеров в узле, а порог ограничивает расстояние между входящей выборкой и существующими подкластерами.

Этот алгоритм можно рассматривать как экземпляр или метод сокращения данных, поскольку он сокращает входные данные до набора подкластеров, которые получаются непосредственно из конечных точек CFT. Эти сокращенные данные могут быть дополнительно обработаны путем подачи их в глобальный кластеризатор. Этот глобальный кластеризатор может быть установлен с помощью n_clusters. Если n_clusters установлено значение None, подкластеры из листьев считываются напрямую, в противном случае шаг глобальной кластеризации помечает эти подкластеры в глобальные кластеры (метки), а выборки сопоставляются с глобальной меткой ближайшего подкластера.

Описание алгоритма:

• Новый образец вставляется в корень дерева CF, который является узлом CF. Затем он объединяется с подкластером корня, который имеет наименьший радиус после объединения, ограниченный пороговыми условиями и условиями фактора ветвления. Если у подкластера есть дочерний узел, то это повторяется до тех пор, пока он не достигнет листа. После нахождения ближайшего подкластера в листе свойства этого подкластера и родительских подкластеров рекурсивно обновляются.
• Если радиус подкластера, полученного путем слияния новой выборки и ближайшего подкластера, больше квадрата порога, и если количество подкластеров больше, чем коэффициент ветвления, то для этой новой выборки временно выделяется пространство. Берутся два самых дальних подкластера, и подкластеры делятся на две группы на основе расстояния между этими подкластерами.
• Если у этого разбитого узла есть родительский подкластер и есть место для нового подкластера, то родительский подкластер разбивается на два. Если места нет, то этот узел снова делится на две части, и процесс продолжается рекурсивно, пока не достигнет корня.

BIRCH или MiniBatchKMeans?

• BIRCH не очень хорошо масштабируется для данных большого размера. Как правило, если n_features оно больше двадцати, лучше использовать MiniBatchKMeans.
• Если количество экземпляров данных необходимо уменьшить или если требуется большое количество подкластеров в качестве этапа предварительной обработки или иным образом, BIRCH более полезен, чем MiniBatchKMeans.

Как использовать partial_fit?

Чтобы избежать вычисления глобальной кластеризации, при каждом обращении partial_fit пользователя рекомендуется

1. Установить n_clusters=None изначально
2. Обучите все данные несколькими вызовами partial_fit.
3. Установите n_clusters необходимое значение с помощью brc.set_params(n_clusters=n_clusters.
4. Вызов, partial_fit наконец, без аргументов, т.е. brc.partial_fit() который выполняет глобальную кластеризацию.

2.3.10. Оценка эффективности кластеризации

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

2.3.10.1. Индекс Rand 

Учитывая знания о назначениях базовых классов истинности labels_true и назначениях нашим алгоритмом кластеризации одних и тех же выборок labels_pred, (скорректированный или нескорректированный) индекс Рэнда — это функция, которая измеряет сходство двух назначений, игнорируя перестановки:

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.rand_score(labels_true, labels_pred)
0.66...

Индекс Rand не гарантирует получение значения, близкого к 0,0 при случайной маркировке. Скорректированный индекс Rand вносит поправку на случайность и дает такую ​​основу.

>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...

Как и в случае со всеми метриками кластеризации, можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить ту же оценку:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.rand_score(labels_true, labels_pred)
0.66...
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24...

Более того, оба rand_score adjusted_rand_score они симметричны : замена аргумента не меняет оценок. Таким образом, их можно использовать в качестве критериев консенсуса:

>>> metrics.rand_score(labels_pred, labels_true)
0.66...
>>> metrics.adjusted_rand_score(labels_pred, labels_true)
0.24...

Идеальная маркировка оценивается в 1,0:

>>> labels_pred = labels_true[:]
>>> metrics.rand_score(labels_true, labels_pred)
1.0
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

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

>>> labels_true = [0, 0, 0, 0, 0, 0, 1, 1]
>>> labels_pred = [0, 1, 2, 3, 4, 5, 5, 6]
>>> metrics.rand_score(labels_true, labels_pred)
0.39...
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
-0.07...

2.3.10.1.1. Преимущества

• Интерпретируемость : нескорректированный индекс Рэнда пропорционален количеству пар выборок, метки которых одинаковы в обоих labels_predи / labels_true или различаются в обоих.
• Случайные (единообразные) присвоения меток имеют скорректированный балл индекса Rand, близкий к 0,0 для любого значения n_clustersи n_samples (что не относится, например, к нескорректированному индексу Rand или V-мере).
• Ограниченный диапазон : более низкие значения указывают на разные маркировки, аналогичные кластеры имеют высокий (скорректированный или нескорректированный) индекс Rand, 1,0 — это оценка идеального соответствия. Диапазон оценок составляет [0, 1] для нескорректированного индекса Rand и [-1, 1] для скорректированного индекса Rand.
• Не делается никаких предположений о структуре кластера: (скорректированный или нескорректированный) индекс Rand может использоваться для сравнения всех видов алгоритмов кластеризации и может использоваться для сравнения алгоритмов кластеризации, таких как k-средних, который предполагает изотропные формы капли с результатами спектрального анализа. алгоритмы кластеризации, которые могут найти кластер со «сложенными» формами.

2.3.10.1.2. Недостатки

• Вопреки инерции, (скорректированный или нескорректированный) индекс Рэнда требует знания основных классов истинности, что почти никогда не доступно на практике или требует ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения). Однако (скорректированный или нескорректированный) индекс Rand также может быть полезен в чисто неконтролируемой настройке в качестве строительного блока для консенсусного индекса, который может использоваться для выбора модели кластеризации (TODO).
• Нескорректированный индекс Rand часто близко к 1,0 , даже если самим кластеризациям существенно различаются. Это можно понять, интерпретируя индекс Рэнда как точность маркировки пар элементов, полученную в результате кластеризации: на практике часто существует большинство пар элементов, которым присваивается different метка пары как при прогнозируемой, так и при базовой кластеризации истинности, что приводит к высокой доля парных меток, которые согласны, что впоследствии приводит к высокой оценке.

2.3.10.1.3. Математическая постановка

Если C — это наземное присвоение класса истинности, а K — кластеризация, давайте определим $a$ и $b$ в виде:

• $a$, количество пар элементов, которые находятся в одном наборе в C и в одном наборе в K
• $b$, количество пар элементов, которые находятся в разных наборах в C и в разных наборах в K

Затем нескорректированный индекс Рэнда рассчитывается следующим образом: $$text{RI} = frac{a + b}{C_2^{n_{samples}}}$$

где $C_2^{n_{samples}}$ — общее количество возможных пар в наборе данных. Не имеет значения, выполняется ли расчет для упорядоченных пар или неупорядоченных пар, если расчет выполняется последовательно.

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

Чтобы противостоять этому эффекту, мы можем дисконтировать ожидаемый RI. $E[text{RI}]$ случайных маркировок путем определения скорректированного индекса Rand следующим образом: $$text{ARI} = frac{text{RI} — E[text{RI}]}{max(text{RI}) — E[text{RI}]}$$

2.3.10.2. Оценки на основе взаимной информации

Учитывая знания о назначениях базовых классов истинности labels_true и назначениях нашим алгоритмом кластеризации одних и тех же выборок labels_pred, взаимная информация — это функция, которая измеряет согласованность двух назначений, игнорируя перестановки. Доступны две различные нормализованные версии этой меры: нормализованная взаимная информация (NMI) и скорректированная взаимная информация (AMI) . NMI часто используется в литературе, в то время как AMI был предложен совсем недавно и нормируется на случайность :

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...

Можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить тот же результат:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
0.22504...

Все, mutual_info_score, adjusted_mutual_info_scoreи normalized_mutual_info_scoreявляется симметричным: замена аргумента не меняет рейтинг. Таким образом, их можно использовать в качестве меры консенсуса :

>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)  
0.22504...

Идеальная маркировка оценивается в 1,0:

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
1.0

>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)  
1.0

Это неверно mutual_info_score, поэтому судить о них труднее:

>>> metrics.mutual_info_score(labels_true, labels_pred)  
0.69...

Плохие (например, независимые маркировки) имеют отрицательные оценки:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)  
-0.10526...

2.3.10.2.1. Преимущества

• Случайные (унифицированные) присвоения меток имеют оценку AMI, близкую к 0,0 для любого значения n_clusters и n_samples (что не относится, например, к необработанной взаимной информации или V-мере).
• Верхняя граница 1 : значения, близкие к нулю, указывают на два назначения меток, которые в значительной степени независимы, а значения, близкие к единице, указывают на значительное согласие. Кроме того, AMI, равный ровно 1, указывает, что два присвоения меток равны (с перестановкой или без нее).

2.3.10.2.2. Недостатки

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

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

• NMI и MI не подвергаются случайной корректировке.

2.3.10.2.3. Математическая постановка

Предположим, что два присвоения метки (одних и тех же N объектов), $U$ а также $V$. Их энтропия — это величина неопределенности для набора разбиений, определяемая следующим образом:

$$H(U) = — sum_{i=1}^{|U|}P(i)log(P(i))$$

где $P(i) = |U_i| / N$ вероятность того, что объект выбран наугад из $U$ попадает в класс $U_i$. Аналогично дляV:

$$H(V) = — sum_{j=1}^{|V|}P'(j)log(P'(j))$$

С участием $P'(j) = |V_j| / N$. Взаимная информация (MI) между $U$ и $V$ рассчитывается по:

$$text{MI}(U, V) = sum_{i=1}^{|U|}sum_{j=1}^{|V|}P(i, j)logleft(frac{P(i,j)}{P(i)P'(j)}right)$$

где $P(i, j) = |U_i cap V_j| / N$ вероятность того, что случайно выбранный объект попадает в оба класса $U_i$ а также $V_j$.

Это также может быть выражено в формулировке множества элементов:

$$text{MI}(U, V) = sum_{i=1}^{|U|} sum_{j=1}^{|V|} frac{|U_i cap V_j|}{N}logleft(frac{N|U_i cap V_j|}{|U_i||V_j|}right)$$

Нормализованная взаимная информация определяется как

$$text{NMI}(U, V) = frac{text{MI}(U, V)}{text{mean}(H(U), H(V))}$$

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

Ожидаемое значение для взаимной информации можно рассчитать с помощью следующего уравнения [VEB2009] . В этом уравнении $a_i = |U_i|$ (количество элементов в $U_i$) а также $b_j = |V_j|$ (количество элементов в $V_j$).

$$E[text{MI}(U,V)]=sum_{i=1}^{|U|} sum_{j=1}^{|V|} sum_{n_{ij}=(a_i+b_j-N)^+ }^{min(a_i, b_j)} frac{n_{ij}}{N}log left( frac{ N.n_{ij}}{a_i b_j}right) frac{a_i!b_j!(N-a_i)!(N-b_j)!}{N!n_{ij}!(a_i-n_{ij})!(b_j-n_{ij})! (N-a_i-b_j+n_{ij})!}$$

Используя ожидаемое значение, скорректированная взаимная информация может быть затем рассчитана с использованием формы, аналогичной форме скорректированного индекса Rand:

$$text{AMI} = frac{text{MI} — E[text{MI}]}{text{mean}(H(U), H(V)) — E[text{MI}]}$$

Для нормализованной взаимной информации и скорректированной взаимной информации нормализующее значение обычно представляет собой некоторое обобщенное среднее энтропий каждой кластеризации. Существуют различные обобщенные средства, и не существует твердых правил предпочтения одного по сравнению с другим. Решение в основном принимается отдельно для каждого поля; например, при обнаружении сообществ чаще всего используется среднее арифметическое. Каждый метод нормализации обеспечивает «качественно похожее поведение» [YAT2016] . В нашей реализации это контролируется average_methodпараметром.

Vinh et al. (2010) назвали варианты NMI и AMI методом их усреднения [VEB2010] . Их средние «sqrt» и «sum» являются средними геометрическими и арифметическими; мы используем эти более общие имена.

2.3.10.3. Однородность, полнота и V-мера

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

В частности, Розенберг и Хиршберг (2007) определяют следующие две желательные цели для любого кластерного задания:

• однородность : каждый кластер содержит только членов одного класса.
• полнота : все члены данного класса относятся к одному кластеру.

Мы можем превратить эти концепции в партитуры homogeneity_score и completeness_score. Оба ограничены снизу 0,0 и выше 1,0 (чем выше, тем лучше):

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66...

>>> metrics.completeness_score(labels_true, labels_pred)
0.42...

Их гармоническое среднее значение, называемое V-мерой , вычисляется по формуле v_measure_score:

>>> metrics.v_measure_score(labels_true, labels_pred)
0.51...

Формула этой функции выглядит следующим образом:

$$v = frac{(1 + beta) times text{homogeneity} times text{completeness}}{(beta times text{homogeneity} + text{completeness})}$$

beta по умолчанию используется значение 1.0, но для использования значения менее 1 для бета-версии:

>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
0.54...

больший вес будет приписан однородности, а использование значения больше 1:

>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
0.48...

больший вес будет приписан полноте.

V-мера фактически эквивалентна описанной выше взаимной информации (NMI), при этом функция агрегирования является средним арифметическим [B2011] .

Однородность, полнота и V-мера могут быть вычислены сразу, используя homogeneity_completeness_v_measure следующее:

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.66..., 0.42..., 0.51...)

Следующее назначение кластеризации немного лучше, поскольку оно однородное, но не полное:

>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(1.0, 0.68..., 0.81...)

homogeneity_score(a, b) == completeness_score(b, a)

2.3.10.3.1. Преимущества

• Ограниченные баллы : 0,0 — это настолько плохо, насколько это возможно, 1,0 — идеальный балл.
• Интуитивная интерпретация: кластеризацию с плохой V-мерой можно качественно проанализировать с точки зрения однородности и полноты, чтобы лучше понять, какие «ошибки» допускаются при задании.
• Не делается никаких предположений о структуре кластера : может использоваться для сравнения алгоритмов кластеризации, таких как k-среднее, которое предполагает изотропные формы капли, с результатами алгоритмов спектральной кластеризации, которые могут находить кластер со «сложенными» формами.

2.3.10.3.2. Недостатки

• Ранее введенные метрики не нормализованы в отношении случайной маркировки : это означает, что в зависимости от количества выборок, кластеров и основных классов истинности полностью случайная маркировка не всегда будет давать одинаковые значения для однородности, полноты и, следовательно, v-меры.

В частности, случайная маркировка не даст нулевых оценок, особенно когда количество кластеров велико. Эту проблему можно спокойно игнорировать, если количество выборок больше тысячи, а количество кластеров меньше 10. Для меньших размеров выборки или большего количества кластеров безопаснее использовать скорректированный индекс, такой как Скорректированный индекс ранда (ARI) .

• Эти метрики требуют знания основных классов истинности, хотя почти никогда не доступны на практике или требуют ручного назначения аннотаторами-людьми (как в условиях контролируемого обучения).

2.3.10.3.3. Математическая постановка

Оценки однородности и полноты формально даются по формуле:

$$h = 1 — frac{H(C|K)}{H(C)}$$
$$c = 1 — frac{H(K|C)}{H(K)}$$

где $H(C|K)$ является условной энтропией классов с учетом кластерных назначений и определяется выражением:
$$H(C|K) = — sum_{c=1}^{|C|} sum_{k=1}^{|K|} frac{n_{c,k}}{n} cdot logleft(frac{n_{c,k}}{n_k}right)$$

а также $H(C)$ — энтропия классов и определяется выражением:
$$H(C) = — sum_{c=1}^{|C|} frac{n_c}{n} cdot logleft(frac{n_c}{n}right)$$

с участием n общее количество образцов, $n_c$ а также $n_k$ количество образцов, соответственно принадлежащих к классу c и кластер $k$, и наконец $n_{c, k}$ количество образцов из класса c назначен кластеру k.

Условная энтропия кластеров данного класса $H(C|K)$ и энтропия кластеров $H(K)$ определены симметричным образом.

Розенберг и Хиршберг далее определяют V-меру как гармоническое среднее однородности и полноты:
$$v = 2 cdot frac{h cdot c}{h + c}$$

2.3.10.4. Результаты Фаулкса-Мэллоуса

Индекс Фаулкса-Мэллоуса ( sklearn.metrics.fowlkes_mallows_score) может использоваться, когда известны наземные присвоения классов истинности выборкам. FMI по шкале Fowlkes-Mallows определяется как среднее геометрическое для попарной точности и отзыва:
$$text{FMI} = frac{text{TP}}{sqrt{(text{TP} + text{FP}) (text{TP} + text{FN})}}$$

Где TP— количество истинных положительных результатов (True Positive) (т.е. количество пар точек, принадлежащих одним и тем же кластерам как в истинных, так и в предсказанных метках), FP— это количество ложных положительных результатов (False Positive) (то есть количество пар точек, принадлежащих к одинаковые кластеры в истинных метках, а не в предсказанных метках) и FN является количеством ложно-отрицательных (False Negative) (т. е. количеством пар точек, принадлежащих одним и тем же кластерам в предсказанных метках, а не в истинных метках).

Оценка варьируется от 0 до 1. Высокое значение указывает на хорошее сходство между двумя кластерами.

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140...

Можно переставить 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить тот же результат:

>>> labels_pred = [1, 1, 0, 0, 3, 3]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140...

Идеальная маркировка оценивается в 1,0:

>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
1.0

Плохие (например, независимые маркировки) имеют нулевые баллы:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.0

2.3.10.4.1. Преимущества

• Случайное (единообразное) присвоение меток имеет оценку FMI, близкую к 0,0 для любого значения n_clusters и n_samples (что не относится, например, к необработанной взаимной информации или V-мере).
• Верхний предел — 1 : значения, близкие к нулю, указывают на два назначения меток, которые в значительной степени независимы, а значения, близкие к единице, указывают на значительное согласие. Кроме того, значения ровно 0 указывают на чисто независимые присвоения меток, а FMI ровно 1 указывает, что два назначения меток равны (с перестановкой или без нее).
• Не делается никаких предположений о структуре кластера : может использоваться для сравнения алгоритмов кластеризации, таких как k-среднее, которое предполагает изотропные формы капли, с результатами алгоритмов спектральной кластеризации, которые могут находить кластер со «сложенными» формами.

2.3.10.4.2. Недостатки

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

2.3.10.5. Коэффициент силуэта

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

• a : Среднее расстояние между образцом и всеми другими точками того же класса.
• b : Среднее расстояние между образцом и всеми другими точками в следующем ближайшем кластере .

Тогда коэффициент силуэта s для одного образца определяется как:
$$s = frac{b — a}{max(a, b)}$$

Коэффициент силуэта для набора образцов дается как среднее значение коэффициента силуэта для каждого образца.

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

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

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
0.55...

2.3.10.5.1. Преимущества

• Оценка ограничена от -1 за неправильную кластеризацию до +1 за высокоплотную кластеризацию. Баллы около нуля указывают на перекрывающиеся кластеры.
• Оценка выше, когда кластеры плотные и хорошо разделенные, что относится к стандартной концепции кластера.

2.3.10.5.2. Недостатки

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

2.3.10.6. Индекс Калински-Харабаса

Если наземные метки достоверности неизвестны, индекс Калински-Харабаса ( sklearn.metrics.calinski_harabasz_score) — также известный как критерий отношения дисперсии — можно использовать для оценки модели, где более высокий балл Калински-Харабаса относится к модели с более определенными кластерами.

Индекс представляет собой отношение суммы дисперсии между кластерами и дисперсии внутри кластера для всех кластеров (где дисперсия определяется как сумма квадратов расстояний):

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

При обычном использовании индекс Калински-Харабаса применяется к результатам кластерного анализа:

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabasz_score(X, labels)
561.62...

2.3.10.6.1. Преимущества

• Оценка выше, когда кластеры плотные и хорошо разделенные, что относится к стандартной концепции кластера.
• Счет быстро подсчитывается.

2.3.10.6.2. Недостатки

• Индекс Калински-Харабаса обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены с помощью DBSCAN.

2.3.10.6.3. Математическая постановка

Для набора данных $E$ размера $n_E$ который был сгруппирован в $k$ кластеры, оценка Калински-Харабаса $s$ определяется как отношение средней дисперсии между кластерами и дисперсии внутри кластера:
$$s = frac{mathrm{tr}(B_k)}{mathrm{tr}(W_k)} times frac{n_E — k}{k — 1}$$

где $tr(B_k)$ является следом межгрупповой дисперсионной матрицы и $tr(W_k)$ является следом матрицы дисперсии внутри кластера, определяемой следующим образом:
$$W_k = sum_{q=1}^k sum_{x in C_q} (x — c_q) (x — c_q)^T$$
$$B_k = sum_{q=1}^k n_q (c_q — c_E) (c_q — c_E)^T$$

с участием $C_q$ набор точек в кластере $q$, $c_q$ центр кластера $q$, $c_E$ центр $E$, а также $n_q$ количество точек в кластере $q$.

2.3.10.7. Индекс Дэвиса-Болдина

Если наземные метки истинности неизвестны, для оценки модели можно использовать индекс Дэвиса-Болдина (sklearn.metrics.davies_bouldin_score), где более низкий индекс Дэвиса-Болдина относится к модели с лучшим разделением между кластерами.

Этот индекс означает среднее «сходство» между кластерами, где сходство — это мера, которая сравнивает расстояние между кластерами с размером самих кластеров.

Ноль — это наименьший возможный результат. Значения, близкие к нулю, указывают на лучшее разделение.

При обычном использовании индекс Дэвиса-Болдина применяется к результатам кластерного анализа следующим образом:

>>> from sklearn import datasets
>>> iris = datasets.load_iris()
>>> X = iris.data
>>> from sklearn.cluster import KMeans
>>> from sklearn.metrics import davies_bouldin_score
>>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans.labels_
>>> davies_bouldin_score(X, labels)
0.6619...

2.3.10.7.1. Преимущества

• Вычисление Дэвиса-Боулдина проще, чем оценка Силуэта.
• В индексе вычисляются только количества и характеристики, присущие набору данных.

2.3.10.7.2. Недостатки

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

2.3.10.7.3. Математическая постановка

Индекс определяется как среднее сходство между каждым кластером. $C_i$ для $i=1, …, k$ и его самый похожий $C_j$. В контексте этого индекса сходство определяется как мера $R_{ij}$ что торгуется:

• $s_i$, среднее расстояние между каждой точкой кластера $i$ и центроид этого кластера — также известный как диаметр кластера.
• $d_{ij}$, расстояние между центрами скоплений $i$ а также $j$.

Простой выбор для построения $R_{ij}$ так что он неотрицателен и симметричен:
$$R_{ij} = frac{s_i + s_j}{d_{ij}}$$

Тогда индекс Дэвиса-Болдина определяется как:
$$DB = frac{1}{k} sum_{i=1}^k max_{i neq j} R_{ij}$$

2.3.10.8. Матрица непредвиденных обстоятельств

Матрица непредвиденных обстоятельств ( sklearn.metrics.cluster.contingency_matrix) сообщает мощность пересечения для каждой истинной / прогнозируемой пары кластеров. Матрица непредвиденных обстоятельств обеспечивает достаточную статистику для всех метрик кластеризации, где выборки независимы и одинаково распределены, и нет необходимости учитывать некоторые экземпляры, которые не были кластеризованы.

Вот пример:

>>> from sklearn.metrics.cluster import contingency_matrix
>>> x = ["a", "a", "a", "b", "b", "b"]
>>> y = [0, 0, 1, 1, 2, 2]
>>> contingency_matrix(x, y)
array([[2, 1, 0],
       [0, 1, 2]])

Первая строка выходного массива указывает, что есть три образца, истинный кластер которых равен «a». Из них два находятся в предсказанном кластере 0, один — в 1 и ни один — в 2. И вторая строка указывает, что есть три выборки, истинный кластер которых равен «b». Из них ни один не находится в прогнозируемом кластере 0, один — в 1, а два — в 2.

Матрица неточностей для классификации является квадратной матрицей непредвиденной где порядок строк и столбцов соответствует списку классов.

2.3.10.8.1. Преимущества

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

2.3.10.8.2. Недостатки

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

2.3.10.9. Матрица неточности пар 

Матрица смешения пар ( sklearn.metrics.cluster.pair_confusion_matrix) представляет собой матрицу подобия 2×2

$$begin{split}C = left[begin{matrix}
C_{00} & C_{01}
C_{10} & C_{11}
end{matrix}right]end{split}$$

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

В нем есть следующие записи:

$C_{00}$: количество пар с обеими кластерами, в которых образцы не сгруппированы вместе
$C_{10}$: количество пар с истинной кластеризацией меток, в которых образцы сгруппированы вместе, но в другой кластеризации образцы не сгруппированы вместе
$C_{01}$: количество пар с истинной кластеризацией меток, в которых образцы не сгруппированы вместе, а другая кластеризация содержит образцы, сгруппированные вместе
 $C_{11}$: количество пар с обеими кластерами, имеющими образцы, сгруппированные вместе

Если рассматривать пару образцов, сгруппированных вместе как положительную пару, то, как и в бинарной классификации, количество истинных отрицательных значений равно $C_{00}$, ложноотрицательные $C_{10}$, истинные положительные стороны $C_{11}$ а ложные срабатывания $C_{01}$.

Идеально совпадающие метки имеют все ненулевые записи на диагонали независимо от фактических значений меток:

>>> from sklearn.metrics.cluster import pair_confusion_matrix
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])
array([[8, 0],
       [0, 4]])

>>> pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0])
array([[8, 0],
       [0, 4]])

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

>>> pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1])
array([[8, 2],
       [0, 2]])

Матрица не симметрична:

>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])
array([[8, 0],
       [2, 2]])

Если члены классов полностью разделены по разным кластерам, назначение полностью неполное, следовательно, матрица имеет все нулевые диагональные элементы:

>>> pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3])
array([[ 0,  0],
       [12,  0]])

  Перевод

  Ссылка на автора

Введение

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

1. Наше предположение о количестве (реальных) кластеров неверно.
2. Особенность пространства очень размерна.
3. Кластеры бывают странной или неправильной формы.

Все эти условия могут привести к проблемам с K-Means, так что давайте посмотрим.

Неверное количество кластеров

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

from sklearn import datasets
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs, make_circles, make_moons
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
import pandas as pd
import itertools
def compare(N_features, C_centers, K_clusters, dims=[0, 1],*args):
    data, targets = make_blobs(
      n_samples=n_samples if 'n_samples' in args else 400,
      n_features=N_features,
      centers=C_centers,
      cluster_std=cluster_std if 'cluster_std' in args else 0.5,
      shuffle=True,
      random_state=random_state if 'random_state' in args else 0)
    FEATS = ['x' + str(x) for x in range(N_features)]
    X = pd.DataFrame(data, columns=FEATS)
    X['cluster'] = 
		KMeans(n_clusters=K_clusters, random_state=0).fit_predict(X)
    fig, axs = plt.subplots(1, 2, figsize=(12, 4))
    axs[0].scatter(data[:, dims[0]], data[:, dims[1]],
        c='white', marker='o', edgecolor='black', s=20)
    axs[0].set_xlabel('x{} [a.u.]'.format(dims[0]))
    axs[0].set_ylabel('x{} [a.u.]'.format(dims[1]))
    axs[0].set_title('Original dataset')
    axs[1].set_xlabel('x{} [a.u.]'.format(dims[0]))
    axs[1].set_ylabel('x{} [a.u.]'.format(dims[1]))
    axs[1].set_title('Applying clustering')
    colors = itertools.cycle(['r', 'g', 'b', 'm', 'c', 'y'])
    for k in range(K_clusters):
        x = X[X['cluster'] == k][FEATS].to_numpy()
        axs[1].scatter(
		x[:, dims[0]], 
		x[:, dims[1]], 
		color=next(colors),
		edgecolor='k', 
		alpha=0.5
	)
    plt.show()

Слишком мало кластеров

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

Слишком много кластеров

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

Высокие (er) размерные данные

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

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

fig = plt.figure(figsize=(14, 8))
ax = fig.add_subplot(111, projection='3d')
data, targets = make_blobs(
    n_samples=400,
    n_features=3,
    centers=3,
    cluster_std=0.5,
    shuffle=True,
    random_state=0)
ax.scatter(data[:, 0], data[:, 1], 
    zs=data[:, 2], zdir='z', s=25, c='black', depthshade=True)
ax.set_xlabel('x0 [a.u.]')
ax.set_ylabel('x1 [a.u.]')
ax.set_zlabel('x2 [a.u.]')
ax.set_title('Original distribution.')
plt.grid()
plt.show()

Хотя существует множество способов проецировать этот 3D-набор данных на 2D, существует три основных ортогональных подпространства:

Глядя наx2 : x0проекция, набор данных выглядит так, как если бы он имел только два кластера. Нижний правый «суперкластер» на самом деле представляет собой две отдельные группы, и даже если мы предполагаем,Кправильно(К = 3)Это выглядит как очевидная ошибка, несмотря на то, что кластеры очень локализованы.

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

Это имеет больше смысла!

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

СлучайN, N> 3особенности, мы быне сможет построить весь набор данныхи число 2D проекций будет масштабироваться квадратично сN:

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

Нерегулярные наборы данных

До сих пор мы упоминали о проблемах, которые «на нашей стороне». Мы посмотрели на очень «хорошо себя ведущий» набор данных и обсудили проблемы в области аналитики. Однако что делать, если набор данных не соответствует нашему решению или нашемуРешение проблемы не подходит?Это как раз тот случай, когда распределение данных происходит в странных или неправильных формах.

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

fig, axs = plt.subplots(1, 3, figsize=(14, 4))
# unequal variance
X, y = make_blobs(n_samples=1400,
    cluster_std=[1.0, 2.5, 0.2],
    random_state=2)
y_pred = KMeans(n_clusters=3, random_state=2).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]
axs[0].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[0].set_title("Unequal Variance")
# anisotropically distributed data
X, y = make_blobs(n_samples=1400, random_state=156)
transformation = [
	[0.60834549, -0.63667341],
	[-0.40887718, 0.85253229]
]
X = np.dot(X, transformation)
y_pred = KMeans(n_clusters=3, random_state=0).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]
axs[1].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[1].set_title("Anisotropicly Distributed Blobs")
# irregular shaped data
X, y = make_moons(n_samples=1400, shuffle=True, 
	noise=0.1, random_state=120)
y_pred = KMeans(n_clusters=2, random_state=0).fit_predict(X)
colors = [['r', 'g', 'b'][c] for c in y_pred]
axs[2].scatter(X[:, 0], X[:, 1], 
	color=colors, edgecolor='k', alpha=0.5)
axs[2].set_title("Irregular Shaped Data")
plt.show()

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

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

Выводы

В этом посте мы обсудили три основные причины, по которым алгоритм K-Means Clustering дает нам неправильные ответы.

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

Зная эти три ошибки, KMC остается полезным инструментом, особенно при проверке данных или создании меток.

From Wikipedia, the free encyclopedia

Clustered standard errors (or Liang-Zeger standard errors)^[1] are measurements that estimate the standard error of a regression parameter in settings where observations may be subdivided into smaller-sized groups («clusters») and where the sampling and/or treatment assignment is correlated within each group.^[2][3] Clustered standard errors are widely used in a variety of applied econometric settings, including difference-in-differences^[4] or experiments.^[5]

Analogous to how Huber-White standard errors are consistent in the presence of heteroscedasticity and Newey–West standard errors are consistent in the presence of accurately-modeled autocorrelation, clustered standard errors are consistent in the presence of cluster-based sampling or treatment assignment. Clustered standard errors are often justified by possible correlation in modeling residuals within each cluster; while recent work suggests that this is not the precise justification behind clustering,^[6] it may be pedagogically useful.

Intuitive motivation[edit]

Clustered standard errors are often useful when treatment is assigned at the level of a cluster instead of at the individual level. For example, suppose that an educational researcher wants to discover whether a new teaching technique improves student test scores. She therefore assigns teachers in «treated» classrooms to try this new technique, while leaving «control» classrooms unaffected. When analyzing her results, she may want to keep the data at the student level (for example, to control for student-level observable characteristics). However, when estimating the standard error or confidence interval of her statistical model, she realizes that classical or even heteroscedasticity-robust standard errors are inappropriate because student test scores within each class are not independently distributed. Instead, students in classes with better teachers have especially high test scores (regardless of whether they receive the experimental treatment) while students in classes with worse teachers have especially low test scores. The researcher can cluster her standard errors at the level of a classroom to account for this aspect of her experiment.^[7]

While this example is very specific, similar issues arise in a wide variety of settings. For example, in many panel data settings (such as difference-in-differences) clustering often offers a simple and effective way to account for non-independence between periods within each unit (sometimes referred to as «autocorrelation in residuals»).^[4] Another common and logically distinct justification for clustering arises when a full population cannot be randomly sampled, and so instead clusters are sampled and then units are randomized within cluster. In this case, clustered standard errors account for the uncertainty driven by the fact that the researcher does not observe large parts of the population of interest.^[8]

Mathematical motivation[edit]

A useful mathematical illustration comes from the case of one-way clustering in an ordinary least squares (OLS) model. Consider a simple model with N observations that are subdivided in C clusters. Let be an vector of outcomes, a matrix of covariates, an vector of unknown parameters, and an vector of unexplained residuals:

As is standard with OLS models, we minimize the sum of squared residuals to get an estimate :

From there, we can derive the classic «sandwich» estimator:

Denoting yields a potentially more familiar form

While one can develop a plug-in estimator by defining and letting , this completely flexible estimator will not converge to as . Given the assumptions that a practitioner deems as reasonable, different types of standard errors solve this problem in different ways. For example, classic homoskedastic standard errors assume that is diagonal with identical elements , which simplifies the expression for . Huber-White standard errors assume is diagonal but that the diagonal value varies, while other types of standard errors (e.g. Newey–West, Moulton SEs, Conley spatial SEs) make other restrictions on the form of this matrix to reduce the number of parameters that the practitioner needs to estimate.

Clustered standard errors assume that is block-diagonal according to the clusters in the sample, with unrestricted values in each block but zeros elsewhere. In this case, one can define and as the within-block analogues of and and derive the following mathematical fact:

By constructing plug-in matrices , one can form an estimator for that is consistent as the number of clusters becomes large. While no specific number of clusters is statistically proven to be sufficient, practitioners often cite a number in the range of 30-50 and are comfortable using clustered standard errors when the number of clusters exceeds that threshold.

Further reading[edit]

• Alberto Abadie, Susan Athey, Guido W Imbens, and Jeffrey M Wooldridge. 2022. «When Should You Adjust Standard Errors for Clustering?» Quarterly Journal of Economics.

References[edit]

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

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

В далёком 2013 году мне повезло поучаствовать в разработке очень сложного алгоритма кластеризации. Требовалось с очень высоким качеством кластеризовать сотни тысяч объектов и делать это быстро: за десятки секунд на одной машине. Первым делом нужно было построить систему оценки качества, и в этой статье я расскажу именно о ней.

Когда речь заходит об оценке качества, начинать нужно, конечно же, с метрик.

Алгоритм кластеризации можно и нужно оценивать с позиции сервиса, частью которого этот алгоритм является: рост качества кластеризации должен приводить к росту числа пользователей, конверсий, возвращаемости и так далее, так что классическое А/Б-тестирование вполне уместно. Вместе с тем любой большой системе нужны метрики, специфичные для каждого из её компонентов. Кластеризация — не исключение.

1. Метрики и их свойства

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

Обсуждение метрик стоит предварить обсуждением принципов, которым эти метрики должны удовлетворять. В статье Amigo et. al, 2009. A comparison of Extrinsic Clustering Evaluation Metrics based on Formal Constraints очень подробно разбирается ряд принципов, их корректность и то, как различные классы метрик удовлетворяют этим принципам.

1.1. Cluster Homogeneity, однородность кластеров

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

1.2. Cluster Completeness, полнота кластеров

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

1.3. Rag Bag

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

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

1.4. Size vs Quantity

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

2. Метрики качества кластеризации

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

Будем считать заданным конечное множество объектов . Множеством кластеров будем называть всякую совокупность его непересекающихся непустых подмножеств. Таким образом, — множество кластеров, если

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

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

2.1. Метрики, основанные на подсчёте пар (классификационные)

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

Иллюстрация ниже поясняет это определение. Восемь объектов разбиты на три эталонных кластера размеров 3 («жёлтый»), 3 («фиолетовый») и 2 («синий»). Эти же объекты кластеризованы алгоритмом так: «синий» кластер собран абсолютно верно, а вот один из «фиолетовых» объектов ошибочно отнесён в кластер к «жёлтым».

Тогда здесь суммарно пар объектов, из них:
— положительных;
— отрицательных.

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

В терминах качества бинарной классификации получается, что:
— пар определены как положительные и при этом являются положительными;
— пар определены как положительные, но ими не являются;
— пар определены как отрицательные и при этом являются отрицательными;
— пары определены как отрицательные, но ими не являются.

Теперь можно вычислить точность, полноту и любые другие метрики:

В процессе вычислений можно учитывать тот факт, что матрица симметрична: это вносит изменения в получаемые значения.

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

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

2.2. Метрики, основанные на сопоставлении множеств

Для определения метрик этого класса вначале вводятся метрики точности и полноты соответствия между кластером и эталоном:

Пример ниже содержит два эталонных кластера: «жёлтый» (y) и «фиолетовый» (v). Единственный алгоритмический кластер содержит 25 жёлтых точек и 10 фиолетовых. Точность соответствия этого кластера жёлтому кластеру составляет 25/35, а фиолетовому — 10/35. Вне кластера находятся ещё пять жёлтых и две фиолетовых точки. Значит, всего имеется 30 жёлтых и 12 фиолетовых точек, поэтому полнота соответствия жёлтому кластеру равна 25/30, фиолетовому — 10/12.

Физический смысл введённых величин прост: точность равна вероятности выбрать элемент эталонного кластера при выборе случайного элемента из алгоритмического кластера, полнота равна вероятности выбрать элемент алгоритмического кластера при выборе случайного элемента из эталонного кластера. Показатели двойственны:

Далее можно определить и F-меру:

Теперь необходимо определить интегральный показатель. Самый известный способ определить его через показатели отдельных соответствий приводит к метрике «чистоты» кластеров, Purity:

Вводится и двойственная метрика, в которой суммирование и нормировка производятся по эталонным кластерам:

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

Для примера можно взять , , , . Кластер полностью находится внутри , поэтому:

Отсюда можно вычислить метрики точности для соответствий:

Из этого уже ясно, что показатели Purity и InversePurity высоки для каждого из алгоритмических и эталонных кластеров соответственно. Аккуратное вычисление даёт:

Обе величины близки к единице, хотя для кластера в действительности нет ни одного хорошего представителя из числа алгоритмических кластеров. Метрики не заметили этого, т. к. при подсчёте Purity кластеру соответствовал кластер , а при подсчёте InversePurity — кластер . При вычислении двух различных показателей в качестве оптимальных были выбраны различные соответствия!

Отчасти с этой проблемой помогает справиться F-мера:

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

2.3. BCubed-метрики

Этот класс метрик предлагает взглянуть на кластеризацию с точки зрения одного отдельного элемента. Предположим, пользователь изучает конкретный документ внутри новостного сюжета. Какова доля документов этого сюжета, относящихся к той же теме, что и изучаемый документ? А какую долю документы по этой теме в сюжете составляют от числа всех документов по теме?

Вполне законные вопросы, и ответ на них приводит к BCubed-метрикам точности и полноты. Они определены для конкретного объекта:

Интегральные показатели определяются усреднением по элементам:

BCubed Precision удовлетворяет свойствам Cluster Homogeneity и Rag Bag, а BCubed Recall — свойствам Cluster Completeness и Size vs Quantity. Сводный показатель — F-мера — удовлетворяет всем четырём свойствам:

3. Метрики эталонных кластеров

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

Рассмотрим, как это работает, на следующем примере. Пусть множество объектов состоит из девяти элементов, образующих два эталонных кластера и («зелёный» и «жёлтый» соответственно).

Алгоритмические кластеры не повторяют эталонные в точности: , .

3.1. BCubed

Введём BCubed-метрики для отдельных эталонных кластеров:

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

Отсюда метрики точности эталонных кластеров:

Аналогично для полноты:

Средневзвешенные по всем эталонным кластерам значения BCP и BCR будут такими:

Именно эти характеристики мы и использовали при оценке качества кластеризации.

3.2. Expected Cluster Completeness

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

Стандартный способ — F-мера — подходит лишь в ограниченном смысле. Это действительно один показатель, но является ли его значение подходящим для принятия решений? Вовсе не факт.

В конечном счёте требование к алгоритму заключается в том, чтобы каждому эталонному кластеру сопоставить некоторый уникальный алгоритмический кластер, который служил бы для эталона «представителем». Алгоритмический кластер может представлять только один эталонный кластер. При этом из всех сопоставлений важно лишь одно — самое удачное. Такой ход рассуждений является естественным для многих приложений: например, при анализе поисковых запросов судить о содержании кластера проще всего по тексту типичного представителя, то есть единственного запроса.

Сопоставление — функция из множества алгоритмических кластеров в множество эталонных кластеров:

Тогда для конкретного эталона и сопоставления можно вычислить характеристику полноты (cluster completeness):

Среднее значение полноты:

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

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

Теперь вероятность выбора функции определяется через произведение вероятностей выбора всех её значений:

Теперь можно вычислить ожидаемое покрытие для эталонного кластера:

Интегральный показатель можно определить так:

Либо эквивалентно:

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

Кластер выбирается в соответствие эталону с вероятностью

При этом покрытие будет равно

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

Если же для кластера выбрано другое сопоставление, то с вероятностью эталону будет сопоставлен кластер . Тогда покрытие окажется равным . Это рассуждение можно продолжить, и в конце концов мы получим, что математическое ожидание покрытия равняется

Код для вычисления метрики ECC для конкретного эталонного кластера получается очень простым. Вектор sortedMatchings состоит из всех кластеров, которые пересекаются с эталоном, он отсортирован по неубыванию полноты. Точность и полноту каждого соответствия эталону можно вычислить при помощи методов Precision() и Recall() соответственно. Тогда:

double ExpectedClusterCompleteness(const TMatchings& sortedMatchings) {
    double expectedClusterCompleteness = 0.;
    double probability = 1.;
    for (const TMatching& matching : sortedMatchings) {
        expectedClusterCompleteness += matching.Recall() * matching.Precision() * probability;
        probability *= 1. - matching.Precision();
    }
    return expectedClusterCompleteness;
}

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

Вычислим теперь ECC для эталонных кластеров, с которых начался пункт 3. Максимальное покрытие эталону обеспечивает кластер , а эталону — . Поэтому:

Интегральное значение вычисляется как среднее значение по всем эталонам, поэтому:

4. Реализация

Метрики, описанные в пункте 3, реализованы на C++ и выложены под лицензией MIT на GitHub. Реализация компилируется и запускается как на Linux, так и на Windows.

Программу легко собрать:

git clone https://github.com/yandex/cluster_metrics/ .
cmake .
cmake --build .

После этого её можно запустить для того же примера, что разбирался в пункте 3. Расчёты из статьи совпадают с показаниями программы!

./cluster_metrics samples/sample_markup.tsv samples/sample_clusters.tsv
ECC   0.61250 (0.61250)
BCP   0.65125 (0.65125)
BCR   0.65250 (0.65250)
BCF1  0.65187 (0.65187)

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

5. Как понять, что метрики работают

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

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

В центре экрана находился эталонный кластер: были перечислены все документы, отнесённые к нему в процессе разметки. С двух сторон от него отображались кластеры, построенные двумя соревнующимися алгоритмами, имеющие непустое пересечение с эталоном. Стороны для алгоритмов выбирались случайным образом, чтобы асессор не знал, с какой стороны находится старый алгоритм, а с какой — новый. Порядок кластеров для каждого алгоритма определялся сортировкой по произведению точности на полноту соответствия — совсем как в метрике ECC!

Зелёным помечались документы, относящиеся к выбранному эталонному кластеру, красным — относящиеся к другому эталонному кластеру. Серым обозначались неразмеченные документы.

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

Такую процедуру мы использовали в течение нескольких месяцев, пока не обнаружили, что асессоры всегда выбирают тот алгоритм, для которого выше значение метрики ECC! Если показатели ECC различались хотя бы сколько-то существенно, асессоры всегда выбирали тот же вариант, что и метрика, это происходило буквально в 100% случаев. Поэтому со временем мы отказались от процедуры ручной приёмки и принимали решения просто по метрикам.

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

^{_{Пример сравнения двух разбиений на кластеры для свойства Cluster Completeness}}

Далее сорок асессоров выносили вердикты о том, какой из двух способов лучше, и их ответы сравнивались с вердиктами правил. Оказалось, что с каждым из правил Cluster Homogeneity, Cluster Completeness, Rag Bag не согласился только один из сорока асессоров, а свойству Size vs Quantity не противоречил никто.

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

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

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