Кластеризация и k-means

Самый известный алгоритм кластеризации — k-means — на простом примере, который вы запустите сами.

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

Идея k-means в двух шагах

k-means («k средних») ищет k групп. Алгоритм держит по одной «центральной точке» (центроиду) на каждый кластер и повторяет два шага, пока всё не устаканится:

Присвоение. Каждый объект относим к ближайшему центроиду.
Пересчёт. Центроид сдвигаем в среднее всех «своих» объектов.

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

k-means руками

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

# Данные: два явных скопления
points = [1.0, 1.5, 2.0, 8.0, 9.0, 10.0]

# Стартовые центры (взяты намеренно неудачно)
c1, c2 = 1.0, 10.0

for step in range(3):
    # Шаг 1: присвоение к ближайшему центру
    g1, g2 = [], []
    for p in points:
        if abs(p - c1) <= abs(p - c2):
            g1.append(p)
        else:
            g2.append(p)
    # Шаг 2: пересчёт центров как среднего группы
    c1 = sum(g1) / len(g1)
    c2 = sum(g2) / len(g2)
    print(f"Шаг {step+1}: центр1={round(c1,2)}, центр2={round(c2,2)}")

print("Кластер 1:", g1)
print("Кластер 2:", g2)

Вывод:

Шаг 1: центр1=1.5, центр2=9.0
Шаг 2: центр1=1.5, центр2=9.0
Шаг 3: центр1=1.5, центр2=9.0
Кластер 1: [1.0, 1.5, 2.0]
Кластер 2: [8.0, 9.0, 10.0]

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

Тонкости k-means

Число k задаёте вы. Алгоритм не знает, сколько групп «правильно». Если групп на деле три, а вы попросили две, он всё равно поделит на две. Подбирают k экспериментом.
Зависимость от старта. При неудачных начальных центрах результат может быть хуже, поэтому на практике запускают несколько раз с разной инициализацией.
Масштаб признаков. Как и kNN, k-means считает расстояния — признаки нужно нормализовать.
Форма кластеров. k-means хорошо находит «круглые» компактные скопления и хуже — вытянутые или вложенные.

На практике

В scikit-learn это пара строк (иллюстрация):

# Иллюстрация (scikit-learn в браузере не запустится)
from sklearn.cluster import KMeans

X = [[1], [1.5], [2], [8], [9], [10]]
model = KMeans(n_clusters=2, n_init=10)
model.fit(X)

print(model.labels_)            # к какому кластеру отнесён каждый объект
print(model.cluster_centers_)   # координаты центров

Итог

k-means повторяет два шага: присвоить объекты к ближайшему центру и сдвинуть центры в среднее группы.
Число кластеров k задаёт человек; алгоритм его не выбирает.
Результат зависит от старта и масштаба признаков — отсюда нормализация и несколько запусков.
Метод находит группы в данных без меток.