KMeans

KMeans — один из самых известных алгоритмов кластеризации.

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

Что делает алгоритм

Главная идея KMeans — разбить данные на заранее заданное число кластеров $k$. Объекты внутри одного кластера должны быть близки друг к другу, а объекты из разных кластеров — находиться далеко друг от друга.

Когда использовать

KMeans хорошо подходит, когда в данных ожидаются компактные группы объектов вокруг центров.

Например, его можно использовать, чтобы:

• найти группы похожих точек на плоскости;
• разделить объекты на несколько сегментов по числовым признакам;
• получить первое приближённое разбиение данных на группы.

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

Центроиды

У каждого кластера есть центроид — центр кластера.

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

Например, если кластер состоит из $m$ точек на плоскости, то координаты центроида вычисляются так:

$$c_x = \frac{x_1 + x_2 + \ldots + x_m}{m}$$ $$c_y = \frac{y_1 + y_2 + \ldots + y_m}{m}$$

То есть центроид можно понимать как «среднюю точку» кластера.

Как работает алгоритм KMeans

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

1. Задать число кластеров

Сначала выбирается число кластеров $k$.

Например, если нужно найти три группы объектов, задаём $k = 3$.

2. Выбрать начальные центроиды

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

3. Распределить объекты по кластерам

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

4. Пересчитать центроиды

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

5. Повторять до остановки

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

KMeans можно представить как процесс постепенного уточнения центров групп.

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

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

Пример кластеризации

uses MLABC, PlotML;

begin
  var (X, trueLabels) := Datasets.MakeBlobs(
    n := 300,
    centers := 3,
    clusterStd := 0.8,
    seed := 42);

  var model := new KMeans(3, seed := 42);

  var labels := model.FitPredict(X);

  var (xs, ys) := X.Cols(0, 1);

  Plot.Points(xs, ys, labels, size := 4);
  Plot.Title := 'KMeans: найденные кластеры';

  Print(model.Centers);

  Plot.Points(model.Centers, color := Colors.Black, size := 6, marker := MarkerType.Diamond);
end.

Вывод и смысл результата

Вывод:

[[1.8,-3.52],[-3.7,0.375],[-3.36,-2.34]]

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

В реальной задаче истинные метки trueLabels обычно неизвестны. Поэтому KMeans получает только матрицу признаков X и сам находит кластеры.

Основные параметры

• k — число кластеров — сколько кластеров нужно найти;
• seed — фиксирует случайный выбор начальных центров;
• maxIter — максимальное число итераций;
• tol — насколько мало должны изменяться центры, чтобы остановить алгоритм.

Главный параметр — число кластеров. Его нужно выбрать заранее.

Ограничения KMeans

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

Но у метода есть ограничения:

• нужно заранее знать число кластеров k;
• плохо работает с кластерами сложной формы;
• чувствителен к масштабу признаков;
• чувствителен к выбросам;
• результат может зависеть от начальных центроидов.

Что дальше

Перед использованием KMeans часто стоит выполнить масштабирование признаков.

Если кластеры имеют сложную форму или есть шумовые точки, попробуйте DBSCAN.