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

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

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

Где d — евклидово расстояние между двумя точками. Мы хотим найти разбиения, минимизирующие L. Рассмотрим задачу более подробно. Предположим, вы хотите разделить 4 точки на 2 кластера. Сколько таких разделов у нас может быть? Для каждой точки у нас есть два варианта, и мы не рассматриваем все точки в одном кластере и ни одну точку в кластере. Получается 2²/2. Мы можем увеличить количество точек до n и количество кластеров до K, чтобы общее количество разделов стало [K^(n-K)]/K!

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

Все решения в этом случае на самом деле являются субоптимальными решениями.

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

На диаграмме выше мы хотим назначить красную точку одному из кластеров. Мы можем вычислить его расстояние от y1 и y2 и назначить его соответствующим образом. Мы также можем провести серединный перпендикуляр к прямой линии, соединяющей y1 и y2. Тогда все точки, лежащие по одну сторону от биссектрисы, принадлежат одному из кластеров. По сути, мы создаем наборы под названием полупространства. Эти полупространства выпуклы. Для этого есть аналитическое доказательство, но если вы возьмете любые две точки в полупространстве и соедините их отрезком, все точки на отрезке будут полностью содержаться в этом полупространстве. Теперь, если у нас больше двух кластеров, у нас будет больше полупространств. И пересечение этих полупространств снова будет выпуклым. Таким образом, этот метод обеспечивает кластеры выпуклой формы. Следует отметить, что речь пока не идет о форме конечного числа точек в кластере.

Здесь есть и более тонкий момент. Почему мы использовали норму L₂ вместо нормы L₁ для расчета расстояния между двумя точками в функции потерь? Как видно из предыдущего примера, в случае двумерного пространства полупространство легко получается серединным перпендикуляром к линии, соединяющей центры кластеров. Линия имеет нулевую меру в смысле Лебега. В случае нормы L₁ будет много точек, находящихся на одинаковом расстоянии от обоих центров кластера, и такая поверхность имеет бесконечную меру Лебега.

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

from sklearn.datasets import make_moons
from sklearn.cluster import KMeans
X, y = make_moons(500, noise=.1, random_state=0)
labels = KMeans(2, random_state=0).fit_predict(X)
fig, ax = plt.subplots(1, 2, sharey=True)
ax[0].scatter(X[:, 0], X[:, 1],edgecolor='k')
ax[1].scatter(X[:, 0], X[:, 1], c=labels,
            s=50, cmap='plasma', edgecolors='k')

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

import numpy as np
cov = [[20,0],[0,1]]
x_1, y_1 = np.random.multivariate_normal((1,2), cov, 500).T
x_2, y_2 = np.random.multivariate_normal((1,-3), cov, 500).T
X_1 = np.array([x_1,y_1]).T
X_2 = np.array([x_2,y_2]).T
X = np.vstack((X_1,X_2))
labels = KMeans(2, random_state=0).fit_predict(X)
fig, ax = plt.subplots(1, 2, sharey=True)
ax[0].scatter(X[:, 0], X[:, 1], edgecolors='k')
ax[1].scatter(X[:, 0], X[:, 1], c=labels, cmap='plasma', edgecolors='k')

Центр одной гауссианы равен (1,2), а другой — (1, -3). Теперь в идеале это должны были быть и центры кластеров. Но вместо этого мы получили кое-что другое. Если мы поместим центры кластеров в гауссовы центры, сумма расстояний разных точек от их соответствующих центров будет больше, чем если бы кластеры были размещены в точках (-5, 0) и (5,0), как на изображении справа. Поскольку разброс в направлении x больше, чем разброс в направлении y. Таким образом, хотя эти два распределения Гаусса могут быть заключены в выпуклые кластеры, кластеры, которые мы получаем из KMeans, все равно не те, которые нам нужны.

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

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