Раздел 5 · 4 балла

Свой kMeans

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

Игрушечные данные

Ноутбук сам генерирует 3 облака по 50 точек на плоскости:

np.random.normal(loc, scale, size)

Случайные точки вокруг loc с разбросом scale, как выстрелы вокруг центра мишени.

Попробуй руками

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

Подпункт 1: kmeans_predict

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

import scipy
from scipy.spatial.distance import cdist


def kmeans_predict(X, clusters):
    # расстояния от каждой точки до каждого центра: таблица (число точек) x (число центров)
    distances_to_centers = cdist(X, clusters)
    # номер ближайшего центра для каждой точки
    labels = distances_to_centers.argmin(axis=1)
    return labels

1. cdist(X, clusters) таблица 150 × 3: строка = точка, столбец = центр, в клетке расстояние.
2. .argmin(axis=1) в каждой строке номер самого маленького числа, то есть номер ближайшего центра (0, 1 или 2).
3. return labels 150 номеров. Метка (label) = номер кластера точки.

Пример: точка (1, 1), центры (0, 0), (5, 5), (−2, 4).

Подпункт 2: обновление центров

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

for i in range(iters):
    labels = kmeans_predict(X, centroids)
    new_centroids = centroids.copy()
    for j in range(k):
        if np.any(labels == j):  # если в кластер не попало ни одной точки, центр не двигаем
            new_centroids[j] = X[labels == j].mean(axis=0)
    centroids = new_centroids
    centroids_history.append(centroids)

1. labels = kmeans_predict(...) каждая точка выбирает ближайший центр.
2. centroids.copy() копия, чтобы не испортить старые центры: они уже лежат в истории.
3. for j in range(k) по очереди для каждого из 3 кластеров.
4. labels == j маска «точки кластера j».
5. np.any(...) есть ли в кластере хоть одна точка. Среднее пустого множества посчитать нельзя.
6. X[labels == j].mean(axis=0) среднее точек кластера: отдельно по x и по y (axis=0 = вниз по столбцам). Это новый центр.
7. centroids_history.append(...) сохраняем кадр.

Подпункт 3: kmeans_fit_predict

loss здесь означает «на сколько суммарно сдвинулись центры за шаг». Пока центры едут, loss большой; когда встали, loss = 0.

def kmeans_fit_predict(x, k=8, max_iter=100, tol=0.001, low=0.0, high=1.0, print_progress=False):
    n_features = x.shape[1]
    clusters = np.random.uniform(low, high, size=(k, n_features))  # случайные стартовые центры
    loss_history = []

    for i in range(max_iter):
        labels = cdist(x, clusters).argmin(axis=1)

        new_clusters = np.empty_like(clusters)
        for j in range(k):
            points = x[labels == j]
            if len(points) > 0:
                new_clusters[j] = points.mean(axis=0)
            else:
                new_clusters[j] = np.random.uniform(low, high, size=n_features)

        loss = np.linalg.norm(new_clusters - clusters, axis=1).sum()
        loss_history.append(loss)
        if print_progress:
            print(f'Итерация = {i}, loss = {loss}')

        clusters = new_clusters
        if loss < tol:  # центры почти не двигаются: алгоритм сошёлся
            break

    labels = cdist(x, clusters).argmin(axis=1)  # метки для финальных центров
    return clusters, labels, loss_history

1. x.shape[1] сколько координат у точки (у нас 2).
2. np.random.uniform(low, high, size=(k, 2)) k случайных центров, любое число от low до high одинаково вероятно.
3. cdist(...).argmin(axis=1) то же, что kmeans_predict: каждая точка к ближайшему центру.
4. np.empty_like(clusters) заготовка под новые центры такой же формы.
5. if len(points) > 0 ... else ... если кластер пуст, по условию даём ему новый случайный центр, чтобы он снова «поймал» точки.
6. new_clusters - clusters на сколько сдвинулся каждый центр по x и y.
7. np.linalg.norm(..., axis=1) длина сдвига каждого центра (тот же Пифагор). .sum() складываем по всем центрам.
8. if loss < tol: break центры встали: выходим из цикла раньше.
9. После цикла ещё раз считаем метки, чтобы они точно соответствовали финальным центрам.

Пример вывода (у тебя числа будут другие, старт случайный):

Итерация = 0, loss = 5.265
Итерация = 1, loss = 5.256
Итерация = 2, loss = 2.128
Итерация = 3, loss = 1.059
Итерация = 4, loss = 0.187
Итерация = 5, loss = 0.0

Вопросы на защите