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

Зачем это нужно

Размеченных данных всегда мало, неразмеченных — океан. обучение без учителяобучение без учителяEN unsupervised learningМеток нет; ищем структуру в данных — кластеры, главные направления, плотность. ищет в данных структуру без подсказок: какие объекты похожи, вдоль каких направлений данные на самом деле меняются. В мире LLM эти инструменты встречаются на каждом шагу:

• Смотреть на эмбеддинги. Модель выдала векторы размерности 1024 для тысячи документов. Разделились ли темы? Нет ли среди них мусора? Ответ даёт карта на плоскости, построенная методами снижения размерности.
• Чистить данные. Похожие документы в корпусе предобучения находят через кластеры эмбеддингов: это помогает удалять смысловые дубликаты и балансировать темы (о дедупликации — в уроке 5.1.2).
• Быстрый поиск. Векторные базы данных для RAG разбивают миллионы векторов на кластеры k-means, чтобы не сравнивать запрос с каждым (ступень 8 и «Китайский угол» ниже).
• Сжатие. Метод главных компонент — это SVD центрированных данных. На той же математике низкого ранга стоят LoRA и MLA в DeepSeek (урок 1.1.3).

Как проходить этот урок

Обязательное ядро: алгоритм k-means и пример с шестью точками на прямой (его проверяет задание), почему $k$ нельзя выбирать по минимуму inertia, PCA на пяти точках и доля объяснённой дисперсии, предупреждения про картинки t-SNE. Раздел «Почему собственные векторы», связь PCA с низким рангом и устройство t-SNE изнутри — для любознательных: их можно пробежать глазами. PCA опирается на собственные числа и SVD из урока 1.1.3 — если они забылись, загляните туда перед второй половиной урока.

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

кластеризациякластеризацияEN clustering — разбить объекты на группы так, чтобы внутри группы они были похожи, а между группами различались. Меток нет: сколько групп и какие они, алгоритм решает сам или с подсказкой — числом $k$.

Целевая функция

метод k-среднихметод k-средних (k-means)EN k-means описывает каждый кластер одной точкой — центроидомцентроидEN centroid $\mu_j$ («центром масс» кластера: среднее всех его точек; у точек 1, 2 и 3 центроид — 2) и минимизирует сумму квадратов расстояний от точек до центроидов их кластеров. Эту сумму называют inertia:

$$J = \sum_{i=1}^{n} \lVert x_i - \mu_{c(i)} \rVert^2 ,$$

где $c(i)$ — номер кластера точки $i$, а $\mu_{c(i)}$ — центроид этого кластера. Словами: для каждой точки берём квадрат расстояния до «её» центра и всё складываем. Чем меньше $J$, тем теснее точки прижаты к своим центрам. Точный минимум искать NP-трудно (как построение лучшего дерева в прошлом уроке), поэтому используют алгоритм Ллойда.

Алгоритм Ллойда

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

Почему это работает? Оба шага не увеличивают $J$. На шаге назначения каждое слагаемое либо уменьшается, либо остаётся прежним: мы выбрали ближайший центроид. На шаге обновления среднее — именно та точка, которая минимизирует сумму квадратов расстояний до точек кластера (производная $\sum_i \lVert x_i - \mu \rVert^2$ по $\mu$ обнуляется при $\mu = \bar x$). Если на шаге назначения хоть одна точка сменила кластер, $J$ строго уменьшился: точку переносят, только когда другой центроид строго ближе (при равенстве расстояний она остаётся на месте). Значит, ни одно разбиение не может повториться. Способов разбить $n$ точек на $k$ групп конечное число, поэтому алгоритм обязательно остановится.

Пример. Точки на прямой: 1, 2, 3, 10, 11, 12, $k = 2$. Неудачный старт: центроиды 1 и 2. Пройдём алгоритм руками.

• Старт. Точка 1 ближе к центроиду 1, все остальные — к центроиду 2. $J = 0^2 + (0^2 + 1^2 + 8^2 + 9^2 + 10^2) = 246$.
• Итерация 1. Обновление: центроид первого кластера — среднее $\{1\}$, то есть 1; второго — среднее $(2 + 3 + 10 + 11 + 12) / 5 = 7.6$. Назначение: 1, 2, 3 ближе к 1, а 10, 11, 12 — к 7.6. $J = (0 + 1 + 4) + (2.4^2 + 3.4^2 + 4.4^2) = 5 + 36.68 = 41.68$.
• Итерация 2. Обновление: центроиды 2 и 11. Назначение не изменилось — алгоритм сошёлся, $J = 1 + 0 + 1 + 1 + 0 + 1 = 4$.

То же в таблице:

Шаг	Центроиды	Кластеры	$J$
старт	1, 2	{1} и {2, 3, 10, 11, 12}	246
итерация 1	1, 7.6	{1, 2, 3} и {10, 11, 12}	41.68
итерация 2	2, 11	{1, 2, 3} и {10, 11, 12}	4

На второй итерации назначения не изменились — сошлись. Ровно этот пример проверяет задание ниже: ваша функция вернёт историю inertia [41.68, 4.0] — по числу на итерацию, без стартовой строки.

Локальные минимумы и k-means++

Алгоритм гарантирует остановку, но не глобальный минимум. Пусть облаков точек три и $k = 3$. Если два стартовых центроида попали в одно облако, а третий — между двумя другими, k-means может так и остаться: первое облако разрезано пополам, два других слиты в один кластер. Два средства:

• k-means++ (Артур и Васильвицкий, 2007). Первый центроид — случайная точка. Каждый следующий выбирается с вероятностью, пропорциональной квадрату расстояния до ближайшего уже выбранного центроида. Далёкие точки выбираются чаще, центроиды разбегаются по данным.
• Несколько запусков с разными стартами, оставляем решение с наименьшим $J$. В scikit-learn за это отвечает параметр n_init.

Как выбрать k

Нельзя выбирать $k$ по минимуму $J$: inertia монотонно падает с ростом $k$ и при $k = n$ равна нулю, каждая точка — свой кластер. Это та же ловушка, что ошибка на train в уроке 2.1.2. Обычно смотрят на «локоть»: после него добавление кластеров почти не уменьшает $J$. Ещё используют коэффициент силуэта: насколько точка ближе к своему кластеру, чем к соседнему. Часто же $k$ диктует задача: «нужно 5 сегментов клиентов для 5 рассылок».

Ограничения

k-means неявно считает кластеры «круглыми» и примерно одного размера, ведь он использует евклидово расстояние до центра. Вытянутые облака, полумесяцы из прошлого урока, кольца он режет неправильно. Он чувствителен к масштабу признаков (стандартизируйте!) и к выбросам: одна далёкая точка тянет за собой центроид. Альтернативы: DBSCAN ищет плотные области и умеет объявлять точки шумом; иерархическая кластеризация строит дерево вложенных групп; гауссовы смеси — «мягкий» k-means, где каждая точка принадлежит кластерам с вероятностями. Одна итерация k-means стоит $O(n \cdot k \cdot d)$. Для миллионов точек есть mini-batch вариант.

Снижение размерности и PCA

снижение размерностиснижение размерностиEN dimensionality reduction нужно, чтобы увидеть данные (из 1024 измерений в 2), сжать их, убрать шум и ускорить другие алгоритмы. Самый важный метод — метод главных компонентметод главных компонент (PCA)EN principal component analysis (PCA).

Интуиция на пяти точках

Возьмём точки $(1, 2.2), (2, 3.8), (3, 6.1), (4, 8.3), (5, 9.6)$. Они почти лежат на прямой $y \approx 2x$. Двумерные данные фактически одномерны: всё, что происходит, — движение вдоль этой прямой, остальное — шум. PCA находит это направление автоматически.

Сначала одно новое понятие. Ковариация двух признаков (она уже встречалась в уроке 2.2.1) — среднее произведение их отклонений от средних. Она положительна, если признаки растут вместе, и отрицательна, если один растёт, когда другой падает. Ковариационная матрица $C$ — таблица ковариаций всех пар признаков. На её диагонали стоят ковариации признака с самим собой, то есть просто дисперсии (разброс каждого признака), а вне диагонали — ковариации разных признаков.

1. Центрируем: среднее $(3, 6)$ вычитаем из всех точек. Получаем $(-2, -3.8), (-1, -2.2), (0, 0.1), (1, 2.3), (2, 3.6)$.
2. Считаем ковариационную матрицу $C = \frac{1}{n-1} X^\top X = \begin{pmatrix} 2.5 & 4.825 \\ 4.825 & 9.385 \end{pmatrix}$. Например, левый верхний элемент — дисперсия первой координаты: $(4 + 1 + 0 + 1 + 4) / 4 = 2.5$. (Делим на $n - 1 = 4$, а не на 5, — так принято для оценки по выборке; на результат PCA это не влияет.)
3. Её собственные числа (урок 1.1.3) — 11.87 и 0.015, собственный вектор первого — $v_1 = (0.458,\ 0.889)$. Это и есть направление прямой: $0.889 / 0.458 \approx 1.94$. Собственное число здесь — дисперсия данных вдоль своего направления: вдоль прямой точки разбросаны сильно (11.87), поперёк — почти никак (0.015).
4. Доля объяснённой дисперсии — какая часть всего разброса данных приходится на это направление. У первой компоненты это $11.87 / (11.87 + 0.015) = 99.87\%$.
5. Проекции точек на $v_1$ (скалярное произведение центрированной точки на $v_1$): для первой точки $-2 \cdot 0.458 + (-3.8) \cdot 0.889 \approx -4.29$, для всех пяти: $-4.29,\ -2.41,\ 0.09,\ 2.50,\ 4.12$. Пять пар чисел превратились в пять чисел почти без потери информации.

Для любознательных: почему собственные векторы

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

Для центрированных данных дисперсия проекции на единичное направление $v$ равна

$$\frac{1}{n-1}\lVert Xv \rVert^2 = v^\top C\, v .$$

Нужно найти единичный вектор $v$, при котором $v^\top C v$ максимально. Матрица $C$ симметрична, а у симметричной матрицы собственные векторы можно выбрать единичными и попарно перпендикулярными (вспомните матрицу $\begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ из урока 1.1.3 с собственными направлениями $(1, 1)$ и $(1, -1)$). Обозначим их $u_1, \dots, u_d$, а собственные числа — $\lambda_1 \ge \dots \ge \lambda_d \ge 0$. Разложим $v = a_1 u_1 + \dots + a_d u_d$, где $a_1^2 + \dots + a_d^2 = 1$. Тогда

$$v^\top C v = \lambda_1 a_1^2 + \lambda_2 a_2^2 + \dots + \lambda_d a_d^2 .$$

Это взвешенное среднее собственных чисел с весами $a_i^2$, которые в сумме дают 1. Оно максимально, когда весь вес отдан наибольшему: $v = u_1$, и дисперсия вдоль него равна $\lambda_1$. В нашем примере это 11.87. Первая главная компонента — собственный вектор с наибольшим $\lambda$, вторая — со следующим (она ортогональна первой), и так далее. Тот же ответ, $Cv = \lambda v$, даёт метод множителей Лагранжа, если вы с ним знакомы.

PCA через SVD

На практике ковариационную матрицу не строят, а делают SVD центрированных данных из урока 1.1.3. Напомним: SVD раскладывает любую матрицу в произведение $U \Sigma V^\top$, где на диагонали $\Sigma$ стоят сингулярные числа $\sigma_1 \ge \sigma_2 \ge \dots$ — коэффициенты растяжения, упорядоченные по важности. Связь с ковариационной матрицей:

$$X = U \Sigma V^\top \quad\Rightarrow\quad C = \frac{1}{n-1} V \Sigma^2 V^\top .$$

Отсюда весь рецепт:

Что нужно	Как получить из SVD
главные направления	строки $V^\top$ (столбцы $V$)
дисперсия вдоль $i$-й компоненты	$\sigma_i^2 / (n-1)$
доля объяснённой дисперсии	$\sigma_i^2 / \sum_j \sigma_j^2$
координаты в $k$ компонентах	$Z = X V_k = U_k \Sigma_k$
восстановление	$\hat X = Z V_k^\top$ + среднее

SVD численно устойчивее, чем явное перемножение $X^\top X$.

Связь с низким рангом (для любознательных). По теореме Эккарта — Янга $\hat X$ — лучшее приближение центрированных данных матрицей ранга $k$. Ошибка восстановления (сумма квадратов всех отклонений $X - \hat X$) равна сумме отброшенных $\sigma_i^2$. В примере с пятью точками это $\sigma_2^2 \approx 0.061$ — против $\sigma_1^2 \approx 47.5$ у оставленной компоненты. Значит, PCA отвечает на вопрос «в каком $k$-мерном подпространстве живут данные?». Та же идея работает в LoRA (обновление весов низкого ранга) и в MLA DeepSeek-V2, где ключи и значения сжимаются в латентный вектор малой размерности. Отличие одно: там проекцию не вычисляют по SVD, а обучают вместе с моделью.

Практические замечания. Сколько компонент оставить — по накопленной доле дисперсии (например, 95%) или 2–3 для картинки. Признаки в разных единицах (рубли и годы) сначала стандартизируют, иначе первая компонента просто укажет на признак с самым большим разбросом. Знак компоненты произволен: $v$ и $-v$ — одно направление. Не удивляйтесь, если на другом компьютере картинка отразится зеркально.

Визуализация эмбеддингов: t-SNE и UMAP

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

t-SNEt-SNE (стохастическое вложение соседей)EN t-distributed stochastic neighbor embedding (t-SNE)Метод визуализации, сохраняющий соседство точек. Размеры кластеров и расстояния между далёкими кластерами на картинке t-SNE почти ничего не значат. (ван дер Маатен и Хинтон, 2008). Главное, что нужно знать: t-SNE раскладывает точки на плоскости так, чтобы соседи остались соседями, и подбирает раскладку градиентным спуском. Как именно он это делает, описано ниже — для любознательных:

1. Для каждой точки превращаем расстояния до остальных в вероятности «быть соседом» с помощью гауссова ядра (формулы «колокола» из урока 1.3.1: чем дальше точка, тем меньше вероятность). Ширину ядра подбирают так, чтобы perplexity распределения равнялась заданной (обычно 5–50). Это то же понятие perplexity, что в уроке 1.3: эффективное число соседей.
2. На плоскости считаем похожие вероятности, но с распределением Стьюдента. Его тяжёлые хвосты дают далёким точкам разойтись и спасают от «скучивания» в центре.
3. Двигаем точки на плоскости градиентным спуском, минимизируя KL-дивергенцию между двумя распределениями.

UMAP (Макиннес, Хили, Мелвилл, 2018) строит граф $k$ ближайших соседей (каждую точку соединяет линиями с её $k$ ближайшими соседями, как в kNN из прошлого урока) и ищет плоскую раскладку, сохраняющую этот граф. Работает заметно быстрее t-SNE, масштабируется до миллионов точек и, по мнению авторов, лучше сохраняет глобальную структуру. Главные параметры — n_neighbors и min_dist.

flowchart LR
A["Тексты<br/>на разных языках"] --> B["Модель эмбеддингов<br/>например, BGE"]
B --> C["Векторы<br/>1024 измерения"]
C --> D["PCA<br/>до 50 измерений"]
D --> E["t-SNE / UMAP<br/>до 2 измерений"]
E --> F["Точечный график,<br/>цвет — известная тема"]

Стандартный конвейер визуализации эмбеддингов

Как не обмануться картинкой t-SNE

• Размеры кластеров ничего не значат. t-SNE раздувает плотные кластеры и сжимает разреженные.
• Расстояния между далёкими кластерами почти ничего не значат. Близость двух островов на карте ещё не говорит о близости тем.
• Картинка зависит от perplexity и случайного старта. Постройте несколько вариантов. При маленькой perplexity даже чистый шум распадается на «кластеры».
• Не кластеризуйте координаты t-SNE. Кластеризуйте исходные векторы, а картинку используйте для проверки.

Интерактивные примеры всех этих эффектов — в статье «How to Use t-SNE Effectively» на Distill.

	PCA	t-SNE	UMAP
Тип	линейный	нелинейный	нелинейный
Что сохраняет	глобальную дисперсию	локальное соседство	соседство, частично глобальную структуру
Скорость	очень быстро (SVD)	медленно на больших данных	быстро
Новые точки	проекция одной формулой	нужно пересчитывать	есть приближённое преобразование
Детерминизм	да (с точностью до знака)	нет	нет
Для чего	сжатие, предобработка, первый взгляд	красивые карты кластеров	большие карты эмбеддингов

Практика

Задание: k-means с нуля

Реализуйте назначение, обновление центроидов, inertia и полный алгоритм Ллойда на NumPy. Особое внимание — пустому кластеру: среднее пустого массива даёт nan («не число»), и он отравит все следующие итерации. Кнопка «Запустить» прогоняет пример с шестью точками из урока: сверяйте вывод с таблицей выше.

Формы массивов: точки X — таблица $(n, d)$, по строке на точку; центроиды C — $(k, d)$; метки labels — $n$ целых чисел от 0 до $k - 1$, номер кластера каждой точки. В примере из урока $d = 1$, поэтому точки записаны как [[1.0], [2.0], ...].

k-means с нуляnumpy · нужен интернет7 тестов

import numpy as np


def assign(X, C):
    """Номер ближайшего центроида для каждой точки.

    X: (n, d) — точки, C: (k, d) — центроиды. Вернуть массив формы (n,) с числами 0..k−1.
    """
    # TODO: ваш код (подсказка: X[:, None, :] - C[None, :, :] даёт все попарные разности)
    ...


def update(X, labels, C_old):
    """Новые центроиды: для каждого кластера j — среднее точек с labels == j.

    Если в кластер не попало ни одной точки, оставьте старый центроид C_old[j].
    """
    # TODO: ваш код
    ...


def inertia(X, C, labels):
    """Сумма квадратов расстояний от каждой точки до центроида её кластера (float)."""
    # TODO: ваш код
    ...


def kmeans(X, C_init, max_iter=100):
    """Алгоритм Ллойда.

    1) labels = assign(X, C_init);
    2) в цикле: C = update(...), new_labels = assign(...), добавить inertia в history;
       если new_labels совпали с labels — выйти (сошлись), иначе labels = new_labels.
    Вернуть (C, labels, history).
    """
    # TODO: ваш код
    ...


# «Запустить»: шесть точек на прямой и неудачный старт
X = np.array([[1.0], [2.0], [3.0], [10.0], [11.0], [12.0]])
result = kmeans(X, C_init=np.array([[1.0], [2.0]]))
if result is None:
    print("Допишите функции выше — kmeans пока ничего не возвращает.")
else:
    C, labels, history = result
    print("центроиды:", C.ravel(), "метки:", labels, "inertia по итерациям:", [round(h, 2) for h in history])

ЗапуститьПроверитьПодсказкаСбросить

PCA и k-means++ на «эмбеддингах»

Запустите локально. Мы сгенерируем синтетические 64-мерные «эмбеддинги» двенадцати слов из трёх тем (центр темы плюс шум), спроецируем их PCA на плоскость и найдём темы k-means с инициализацией k-means++.

import numpy as np

rng = np.random.default_rng(0)
topics = {
    "фрукты":   ["яблоко/apple", "банан/banana", "груша/pear", "апельсин/orange"],
    "животные": ["кошка/cat", "собака/dog", "панда/panda", "тигр/tiger"],
    "города":   ["Москва/Moscow", "Пекин/Beijing", "Шанхай/Shanghai", "Казань/Kazan"],
}
# Синтетические «эмбеддинги» размерности 64: центр темы + личный шум слова
words, vecs = [], []
for topic, ws in topics.items():
    center = rng.normal(0, 1, 64)
    for w in ws:
        words.append(w)
        vecs.append(center + rng.normal(0, 0.5, 64))
X = np.array(vecs)                                   # (12, 64)

# ── PCA через SVD ─────────────────────────────────────────────
Xc = X - X.mean(axis=0)                              # 1) центрируем: вычитаем среднее каждого столбца
U, S, Vt = np.linalg.svd(Xc, full_matrices=False)    # 2) Xc = U · diag(S) · Vt (S — сингулярные числа)
explained = S**2 / (S**2).sum()                      # 3) доля дисперсии компонент: σᵢ² / Σσⱼ²
Z = Xc @ Vt[:2].T                                    # 4) проекция на PC1, PC2: каждое слово → 2 числа
print("доля дисперсии PC1, PC2:", np.round(explained[:2], 3))
for (a, b), w in zip(Z, words):
    print(f"{a:6.2f} {b:6.2f}  {w}")

# ── k-means++ и алгоритм Ллойда в 64-мерном пространстве ─────
def kmeans_pp_init(X, k, rng):
    """Стартовые центроиды k-means++: каждый следующий — скорее подальше от уже выбранных."""
    C = [X[rng.integers(len(X))]]                    # первый центр — случайная точка
    for _ in range(k - 1):
        # для каждой точки — квадрат расстояния до БЛИЖАЙШЕГО из уже выбранных центров
        d2 = np.min([((X - c) ** 2).sum(1) for c in C], axis=0)
        # rng.choice с вероятностями p: точка с бо́льшим d2 выбирается чаще
        C.append(X[rng.choice(len(X), p=d2 / d2.sum())])  # далёкие точки вероятнее
    return np.array(C)

def kmeans(X, C, n_iter=100):
    """Алгоритм Ллойда (то же, что в задании, только компактнее)."""
    for _ in range(n_iter):
        labels = ((X[:, None] - C[None]) ** 2).sum(-1).argmin(1)    # назначение: ближайший центроид
        # обновление: среднее точек кластера; пустой кластер сохраняет старый центроид
        C_new = np.array([X[labels == j].mean(0) if (labels == j).any() else C[j] for j in range(len(C))])
        if np.allclose(C_new, C):                    # центроиды почти не сдвинулись — сошлись
            break
        C = C_new
    return C, labels

C, labels = kmeans(X, kmeans_pp_init(X, 3, rng))
for j in range(3):
    print(f"кластер {j}:", ", ".join(w for w, l in zip(words, labels) if l == j))

доля дисперсии PC1, PC2: [0.447 0.329]
 -3.73   4.14  яблоко/apple
 -3.80   4.42  банан/banana
 -5.26   4.52  груша/pear
 -4.24   4.49  апельсин/orange
 -1.97  -5.26  кошка/cat
 -2.91  -5.21  собака/dog
 -1.92  -5.87  панда/panda
 -2.42  -5.21  тигр/tiger
  6.61   0.87  Москва/Moscow
  6.02   1.30  Пекин/Beijing
  6.96   0.43  Шанхай/Shanghai
  6.68   1.37  Казань/Kazan
кластер 0: Москва/Moscow, Пекин/Beijing, Шанхай/Shanghai, Казань/Kazan
кластер 1: яблоко/apple, банан/banana, груша/pear, апельсин/orange
кластер 2: кошка/cat, собака/dog, панда/panda, тигр/tiger

Знаки координат и номера кластеров на вашей машине могут отличаться. Это нормально: направление компоненты определено с точностью до знака, а номера кластеров — просто имена. Заметьте: три темы уместились в две компоненты с 78% дисперсии. Три центра в любом пространстве лежат в одной плоскости. Настоящие эмбеддинги (ступень 4) устроены сложнее, но этот конвейер вы будете применять к ним без изменений.

Китайский угол: k-means внутри векторных баз и китайские эмбеддинги

Milvus — одна из самых популярных открытых векторных баз данных. Её создала компания Zilliz, основанная в 2017 году в Шанхае. Milvus открыли в 2019 году, в 2021-м проект стал проектом верхнего уровня фонда LF AI & Data. Индексы семейства IVF (IVF_FLAT, IVF_PQ) — прямое применение k-means. При построении индекса векторы разбиваются на nlist кластеров. При поиске запрос сравнивается с центроидами, а потом только с векторами из nprobe ближайших кластеров. Миллион векторов, nlist = 1000, nprobe = 10: 1000 сравнений с центроидами плюс около 10 тысяч с векторами в десяти кластерах (по тысяче в каждом в среднем) — порядка 11 тысяч вместо миллиона. Цена — шанс пропустить соседа из непросмотренного кластера, поэтому поиск называют приближённым. Milvus используется в курсе all-in-rag от Datawhale, им мы займёмся на ступени 8.

BGE (BAAI General Embedding) — семейство моделей эмбеддингов Пекинской академии искусственного интеллекта (BAAI). В статье C-Pack (arXiv:2309.07597, SIGIR 2024) авторы выпустили модели трёх размеров — 24M, 102M и 326M параметров — и бенчмарк C-MTEB: 35 китайских датасетов и 6 типов задач. Одна из задач — кластеризация: хорошие эмбеддинги должны раскладывать тексты по темам так, чтобы k-means восстановил разметку. Код и модели — в репозитории FlagEmbedding. Для русского языка есть аналогичный бенчмарк ruMTEB (arXiv:2408.12503).

Учебники. В «Арбузной книге» кластеризации посвящена глава 9 «Кластеризация» (k-means — в разделе «Кластеризация по прототипам» вместе с LVQ и гауссовыми смесями), PCA — глава 10 «Понижение размерности и обучение метрик». Во втором издании «Методов статистического обучения» Ли Хана добавлена часть об обучении без учителя: глава 14 «Методы кластеризации» (k-means разобран по схеме «модель — стратегия — алгоритм»), глава 15 «Сингулярное разложение» и глава 16 «Метод главных компонент». SVD и PCA там идут подряд, как и в нашем курсе.

Проверь себя

Проверь себя6 вопросов·

1 Почему inertia $J$ не может вырасти на шаге обновления центроидов?

Потому что точки не меняют кластерыСреднее точек кластера минимизирует сумму квадратов расстояний до них, поэтому новый центроид не хуже старогоПотому что центроиды двигаются к началу координатМожет: k-means часто расходится

2 Точки на прямой: 0, 2, 10, 12. k-means с $k = 2$ стартует с центроидов 0 и 2. Чему равна inertia после сходимости?

3 Сингулярные числа центрированной матрицы данных: 4, 2, 1, 1. Какую долю дисперсии объясняет первая главная компонента? Округлите до двух знаков.

4 Какие утверждения о картинке t-SNE верны?Можно выбрать несколько ответов

Размер кластера на картинке не отражает его реальный разбросРасстояние между двумя далёкими кластерами на картинке мало что говорит о сходстве темПри разной perplexity получаются заметно разные картинкиt-SNE — линейная проекция, как PCAКоординаты t-SNE — лучший вход для k-means

5 Вы посчитали inertia k-means для $k$ от 1 до 20 и выбрали $k = 20$, потому что там она минимальна. В чём ошибка?

Ошибки нетInertia монотонно падает с ростом $k$: минимум всегда у максимального $k$, как ошибка на train у самой сложной моделиНужно было выбрать $k = 1$Inertia можно сравнивать только для чётных $k$

6 Признаки клиента — доход в рублях (десятки тысяч) и возраст в годах (десятки). Что сделать перед PCA и k-means?

Ничего, PCA сам разберётсяСтандартизировать признаки, иначе доход задавит возраст и в расстояниях, и в дисперсииУдалить признак возрастаУмножить доход на 1000

Проверить ответы

Домашняя работа

s2-hw01-logreg-from-scratch — итоговая работа модулей 2.1–2.3 (модуль 2.4 завершается своей работой, s2-hw02). На чистом NumPy вы соберёте линейную регрессию (формулой и градиентным спуском), логистическую и softmax-регрессию с L2-регуляризацией, разбиение train/val со стандартизацией без утечек, метрики accuracy, precision, recall, F1 и матрицу ошибок, а на уровне Boss — мини-батчевый спуск с ранней остановкой. В ней сходится всё из модулей 2.1–2.2: признаки и разбиение данных, переобучение и регуляризация, метрики. Условие — в homework/s2-hw01-logreg-from-scratch/README.md.

Проверка из корня репозитория:

python homework/check.py s2-hw01-logreg-from-scratch

Итоги

• k-means минимизирует сумму квадратов расстояний до центроидов. Алгоритм Ллойда чередует назначение и обновление, всегда сходится, но к локальному минимуму. Помогают k-means++ и несколько запусков.
• $k$ не выбирают по минимуму inertia. Признаки стандартизируют, а для некруглых кластеров берут DBSCAN или гауссовы смеси.
• PCA — проекция на собственные векторы ковариационной матрицы. На практике это SVD центрированных данных, доля дисперсии компоненты — $\sigma_i^2 / \sum_j \sigma_j^2$. PCA даёт лучшее приближение низкого ранга, ту же идею, что в LoRA и MLA.
• t-SNE и UMAP сохраняют соседство и строят красивые карты эмбеддингов. Размеры и расстояния между кластерами на них не читаются.
• k-means работает внутри векторных баз (IVF в Milvus), а кластеризация — одна из задач оценки эмбеддингов (C-MTEB).

Дальше: модуль 2.4 — практический ML на табличных данных. Начнём с pandas, затем разведка данных, градиентный бустинг изнутри и проект с честной валидацией.