Словарь терминов

Affinity Propagation — алгоритм кластеризации на основе передачи сообщений между объектами, предложенный Б. Фреем и Д. Дьюком. **Основная идея:** Алгоритм рассматривает каждый объект как потенциальный exemplar — representative point, вокруг которого может сформироваться кластер. Между парами объектов итеративно передаются два типа сообщений: 1. **responsibility** $r(i,k)$ — насколько объект $k$ подходит на роль представителя для объекта $i$; 2. **availability** $a(i,k)$ — насколько объект $k$ готов быть представителем для объекта $i$. **Параметр preference:** Количество кластеров не задается напрямую. Оно регулируется через предпочтение объекта быть представителем. Чем выше preference, тем больше exemplars и тем больше итоговых кластеров. **Преимущества:** Метод может находить неравномерные группы и не требует заранее указывать число кластеров $k$. **Ограничения:** Требует матрицу попарного сходства, поэтому плохо масштабируется на очень большие выборки. На практике алгоритм полезен для задач, где важно выбрать реальные объекты-представители, а не абстрактные центроиды.

Агломеративная кластеризация — семейство иерархических методов, в которых дерево кластеров строится снизу вверх. **Принцип работы:** В начале каждый объект считается отдельным кластером. Далее на каждом шаге объединяются две наиболее близкие группы. Процесс продолжается до тех пор, пока все объекты не окажутся в одном корневом кластере или пока не будет достигнут заданный порог расстояния. **Функция близости кластеров:** Разные варианты агломеративного метода отличаются правилом связи: 1. **single linkage** — расстояние между ближайшими объектами двух кластеров; 2. **complete linkage** — расстояние между наиболее удаленными объектами; 3. **average linkage** — среднее попарное расстояние; 4. **Ward linkage** — минимизация прироста внутрикластерной дисперсии. **Результат:** Итогом является дендрограмма, на которой можно выбрать уровень среза и получить нужное число кластеров. **Ограничения:** Метод хорошо интерпретируется визуально, но для больших выборок может быть затратным из-за необходимости хранить или вычислять попарные расстояния.

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) — алгоритм, предложенный Т. Чжаном, Р. Рамакришнаном и М. Ливни для кластеризации очень больших наборов данных. **Основная идея:** BIRCH не хранит все объекты как самостоятельные элементы. Он строит CF-дерево — компактную иерархическую структуру, где каждый узел хранит статистики подкластеров. **Clustering Feature:** Для подмножества объектов используется тройка: $CF = (N, LS, SS)$, где $N$ — число объектов, $LS = \sum x_i$ — линейная сумма объектов, $SS = \sum x_i^2$ — сумма квадратов. По этим значениям можно быстро вычислять центр, радиус и диаметр подкластеров без обращения ко всем исходным точкам. **Параметры:** 1. **threshold** ограничивает радиус или диаметр подкластеров; 2. **branching factor** ограничивает число потомков в узле CF-дерева. **Преимущества:** Алгоритм хорошо подходит для предварительного сжатия больших данных и может работать почти в потоковом режиме. **Ограничения:** Качество зависит от порядка поступления объектов и выбора threshold. Метод лучше работает с компактными кластерами, но может хуже описывать сложные невыпуклые формы.

Bisecting K-Means — дивизимный вариант k-средних, в котором иерархия строится сверху вниз. **Принцип работы:** Сначала все объекты помещаются в один общий кластер. Затем один из существующих кластеров выбирается для разделения и разбивается на две части с помощью K-Means при $k=2$. Процесс повторяется, пока не будет получено требуемое число кластеров. **Критерий выбора кластера для деления:** Обычно выбирается кластер с наибольшей внутрикластерной суммой квадратов: $SSE(C) = \sum_{x_i \in C} \|x_i - \mu_C\|^2$. Такой выбор позволяет сначала дробить наиболее неоднородные группы. **Связь с теорией:** По Б.Г. Миркину такие методы относятся к делимым иерархическим процедурам. Они дают дерево разбиений, но используют локальный критерий k-средних. **Преимущества:** Метод часто устойчивее обычного K-Means при большом числе кластеров и хорошо масштабируется. **Ограничения:** Как и K-Means, предполагает компактные кластеры и чувствителен к инициализации центров при каждом бинарном разбиении.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — классический плотностной алгоритм, предложенный М. Эстером, Х.-П. Кригелем, Й. Сандером и С. Сюй. **Основная идея:** Кластер рассматривается как связная область высокой плотности, отделенная от других кластеров областями низкой плотности. **Параметры:** 1. $\epsilon$ — радиус окрестности объекта; 2. $MinPts$ — минимальное число объектов в $\epsilon$-окрестности. **Типы точек:** 1. **core point** — точка, имеющая не меньше $MinPts$ соседей в радиусе $\epsilon$; 2. **border point** — точка, которая не является core point, но достижима из core point; 3. **noise point** — точка, не принадлежащая плотностно связной области. **Преимущества:** DBSCAN не требует заранее задавать число кластеров и способен находить кластеры произвольной формы, включая кольца и вытянутые структуры. **Ограничения:** Метод чувствителен к выбору $\epsilon$ и хуже работает, если в данных есть кластеры с сильно различающейся плотностью. Для таких случаев используются OPTICS и HDBSCAN.

Gaussian Mixture Model — модельный метод кластеризации, в котором данные рассматриваются как смесь нескольких нормальных распределений. **Вероятностная модель:** Плотность данных задается формулой: $p(x) = \sum_{k=1}^{K} \pi_k \mathcal{N}(x \mid \mu_k, \Sigma_k)$, где $\pi_k$ — вес k-й компоненты, $\mu_k$ — математическое ожидание, $\Sigma_k$ — ковариационная матрица. **EM-алгоритм:** Параметры смеси обычно оцениваются методом максимизации правдоподобия через EM-процедуру: 1. **E-step** — вычисляются вероятности принадлежности объекта компонентам; 2. **M-step** — обновляются параметры распределений. **Особенность кластеризации:** В отличие от K-Means, метод дает мягкую кластеризацию: объект может принадлежать нескольким кластерам с разными вероятностями. **Преимущества:** Модель хорошо описывает эллипсоидальные кластеры и позволяет учитывать ковариации признаков. **Ограничения:** Нужно задавать число компонент $K$, а качество зависит от начальной инициализации и предположения о гауссовой форме кластеров.

HDBSCAN — иерархическое расширение DBSCAN, предназначенное для данных с кластерами переменной плотности. **Основная идея:** Обычный DBSCAN использует один глобальный радиус $\epsilon$. HDBSCAN рассматривает разные уровни плотности и строит иерархию кластеров, после чего выбирает наиболее устойчивые группы. **Ключевые понятия:** 1. **core distance** — расстояние от точки до ее $MinPts$-го соседа; 2. **mutual reachability distance** — преобразованное расстояние, учитывающее локальную плотность; 3. **cluster stability** — устойчивость кластера при изменении уровня плотности. **Преимущества:** Метод не требует задавать $\epsilon$, лучше работает с кластерами разной плотности и автоматически выделяет шум. **Ограничения:** Результат сложнее объяснять начинающему пользователю, чем результат DBSCAN. Кроме того, интерпретация зависит от параметра минимального размера кластера и выбранного способа извлечения устойчивых групп из иерархии.

K-Means — один из наиболее известных алгоритмов разбиения, восходящий к работам Дж. Маккуина и широко используемый в анализе данных. **Цель алгоритма:** Найти такое разбиение объектов на $K$ кластеров, чтобы минимизировать сумму квадратов расстояний от объектов до центров своих кластеров: $J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$. **Итерационный процесс:** 1. выбираются начальные центроиды; 2. каждый объект относится к ближайшему центроиду; 3. центроиды пересчитываются как средние значения объектов своих кластеров; 4. шаги повторяются до стабилизации разбиения. **Предпосылки:** Метод хорошо работает, если кластеры компактны, примерно выпуклы и сравнимы по размеру. Признаки должны быть масштабированы, иначе переменные с большими числовыми диапазонами будут доминировать в евклидовом расстоянии. **Ограничения:** Нужно заранее задать $K$. Алгоритм чувствителен к выбросам и начальной инициализации, а также плохо выделяет кластеры сложной невыпуклой формы.

Mean Shift — плотностной метод кластеризации, связанный с оценкой плотности распределения и поиском ее локальных максимумов. Классическое изложение метода дано Д. Команичиу и П. Меером. **Основная идея:** Каждая точка итеративно смещается в сторону области большей плотности. Направление сдвига задается вектором mean shift: $m(x) = \frac{\sum_i x_i K\left(\frac{x - x_i}{h}\right)}{\sum_i K\left(\frac{x - x_i}{h}\right)} - x$, где $K$ — ядро, $h$ — ширина окна (bandwidth). **Результат:** Точки, сходящиеся к одному и тому же локальному максимуму плотности, образуют кластер. **Преимущества:** Не нужно заранее задавать число кластеров, а форма кластеров может быть сложной. **Ограничения:** Качество сильно зависит от bandwidth. Слишком маленькое окно дробит данные на множество локальных групп, слишком большое — сливает разные структуры. Метод может быть вычислительно тяжелым на больших выборках.

MiniBatch K-Means — масштабируемая модификация K-Means, в которой центроиды обновляются не по всей выборке, а по небольшим случайным пакетам объектов. **Основная идея:** Обычный K-Means на каждом шаге использует все $n$ объектов. MiniBatch K-Means берет пакет размера $b \ll n$ и обновляет центроиды приближенно. Это снижает стоимость одной итерации с $O(nK)$ до $O(bK)$. **Обновление центров:** Центр кластера постепенно сдвигается в сторону объектов мини-пакета, которые были к нему отнесены. Такой процесс напоминает стохастическую оптимизацию. **Преимущества:** Метод особенно полезен для больших наборов данных и интерактивных приложений, где пользователь ожидает быстрый результат. **Ограничения:** Качество может быть немного ниже, чем у полного K-Means, а результат зависит от размера пакета, порядка данных и числа итераций.

OPTICS (Ordering Points To Identify the Clustering Structure) — плотностной алгоритм, предложенный М. Анкерстом и соавторами как развитие идеи DBSCAN. **Основная идея:** Вместо построения одного разбиения при фиксированном $\epsilon$ алгоритм формирует специальный порядок обхода объектов. Для каждой точки вычисляется reachability distance — расстояние достижимости, показывающее, насколько легко точка присоединяется к плотностной области. **Reachability plot:** Результат часто анализируется через график достижимости. Долины на таком графике соответствуют плотным кластерам, а высокие участки — переходам между ними или шуму. **Преимущества:** OPTICS лучше DBSCAN показывает структуру данных при переменной плотности и помогает исследователю увидеть несколько возможных уровней разбиения. **Ограничения:** Алгоритм не всегда сразу возвращает одно простое разбиение: часто требуется интерпретировать reachability plot или использовать дополнительную процедуру извлечения кластеров.

Спектральная кластеризация — метод, который переводит задачу кластеризации в задачу разбиения графа. **Основная идея:** Объекты рассматриваются как вершины графа, а ребра задают степень сходства между ними. По матрице сходства строится графовый Лапласиан: $L = D - W$, где $W$ — матрица весов ребер, $D$ — диагональная матрица степеней вершин. **Алгоритмическая схема:** 1. строится граф ближайших соседей или матрица сходства; 2. вычисляются собственные векторы Лапласиана; 3. объекты отображаются в новое спектральное пространство; 4. в этом пространстве применяется K-Means или другой простой метод разбиения. **Преимущества:** Метод хорошо выделяет кластеры сложной формы, когда в исходном пространстве они не являются линейно разделимыми. **Ограничения:** Требует выбора способа построения графа и может быть затратным для больших выборок из-за вычисления собственных векторов.

Метод Уорда — агломеративный иерархический алгоритм, предложенный Дж. Уордом. Он объединяет кластеры так, чтобы на каждом шаге минимально увеличивать внутрикластерную дисперсию. **Критерий объединения:** Для двух кластеров $A$ и $B$ прирост ошибки можно записать как: $\Delta(A,B) = \frac{|A||B|}{|A| + |B|}\|\mu_A - \mu_B\|^2$, где $\mu_A$ и $\mu_B$ — центры кластеров, $|A|$ и $|B|$ — их мощности. **Интерпретация:** Метод стремится строить компактные кластеры и близок по смыслу к критерию k-средних, но формирует не одно плоское разбиение, а полную иерархию. **Преимущества:** Хорошо подходит для учебной демонстрации, потому что результат можно показать в виде дендрограммы. **Ограничения:** Предпочитает компактные почти сферические кластеры и может плохо работать с вытянутыми или невыпуклыми структурами.

Алгоритм Максимина — эвристический метод выбора центров, описываемый в отечественной традиции кластерного анализа у Б.Г. Миркина и Н.Г. Загоруйко. **Основная идея:** Сначала выбираются наиболее удаленные друг от друга объекты, которые становятся начальными центрами. Затем новые центры добавляются только в том случае, если расстояние от объекта до уже выбранных центров превышает заданный порог. **Критерий:** Для объекта $x_i$ вычисляется расстояние до ближайшего выбранного центра: $d_i = \min_j \rho(x_i, c_j)$. Если максимальное значение $d_i$ превышает порог $T$, соответствующий объект становится новым центром. **Преимущества:** Метод прост, быстро работает и может использоваться для предварительной инициализации центров перед K-Means. **Ограничения:** Результат зависит от порога $T$ и выбранной метрики расстояния. Метод является эвристическим и не гарантирует оптимального разбиения.

ФОРЭЛЬ (ФОРмальный ЭЛемент) — классический эвристический алгоритм кластеризации, предложенный Н.Г. Загоруйко и В.Н. Елкиной. **Принцип работы:** Алгоритм выбирает начальную точку, строит вокруг нее гиперсферу радиуса $R$ и вычисляет центр масс объектов, попавших внутрь этой сферы: $c^{(t+1)} = \frac{1}{|S_R(c^{(t)})|}\sum_{x_i \in S_R(c^{(t)})} x_i$, где $S_R(c)$ — множество объектов, находящихся не дальше радиуса $R$ от текущего центра $c$. **Итерационный процесс:** Центр сферы сдвигается в найденный центр масс. Шаг повторяется до стабилизации положения центра. После этого найденный кластер удаляется из выборки, и процедура запускается снова для оставшихся объектов. **Связь с Mean Shift:** Внутренний цикл ФОРЭЛЬ близок к Mean Shift при использовании жесткого равномерного ядра: объект движется в сторону локального центра масс своей окрестности. **Преимущества:** Метод не требует заранее задавать число кластеров и хорошо объясняется геометрически. **Ограничения:** Результат сильно зависит от радиуса $R$ и порядка выбора начальных точек. Алгоритм лучше всего подходит для компактных сферических кластеров и хуже работает с вытянутыми или невыпуклыми группами.

**Определение:** Метод автоматической классификации (обучения без учителя), целью которого является разбиение множества объектов $X$ на непересекающиеся или пересекающиеся подмножества (кластеры) $Y$, таким образом, чтобы объекты внутри одного кластера были близки друг к другу относительно выбранной метрики $\rho$, а объекты из разных кластеров — существенно различны. **Математическая постановка (по К.В. Воронцову):** Дано пространство объектов $X$ и обучающая выборка $X^\ell = \{x_1, ..., x_\ell\}$. Задана функция расстояния $\rho(x, x')$. Требуется построить алгоритм $a: X \to Y$ (где $Y$ — множество меток кластеров), который минимизирует функционал внутрикластерного расстояния и/или максимизирует функционал межкластерного расстояния. **Фундаментальная проблема:** Задача кластеризации является *некорректно поставленной*. Не существует единственно правильного разбиения. Результат зависит от: 1. Выбора метрики пространства признаков. 2. Выбора критерия качества (функционала). 3. Эвристических допущений конкретного алгоритма (гипотеза компактности, гипотеза плотности и др.).

**Определение:** Семейство методов, целью которых является построение «плоского» (не иерархического) разбиения множества объектов на заданное число $K$ непересекающихся кластеров. **Принцип работы (по Б.Г. Миркину):** Обычно используется итеративный подход чередующейся оптимизации (как в алгоритме Ллойда для K-Means): 1. **Шаг отнесения:** Каждый объект приписывается к ближайшему "представителю" (центроиду или медоиду). 2. **Шаг пересчета:** Положение самих центроидов пересчитывается на основе приписанных к ним объектов. Процесс повторяется до тех пор, пока функционал качества (например, сумма внутрикластерных расстояний) не перестанет уменьшаться. **Особенности:** * **Четкие границы:** Каждый объект принадлежит ровно одному кластеру (в базовых версиях). * **Интерпретируемость:** Кластеры легко описать через их центроиды ("идеальные представители"). * **Уязвимость:** Метод жадный (жадная локальная оптимизация), поэтому сильно зависит от удачного выбора начальных центров (инициализации).

Задача сжатия сверхбольших массивов данных (Big Data) с минимальной потерей их статистических и структурных свойств. **Зачем это нужно:** Многие точные алгоритмы (например, *Агломеративная кластеризация*) имеют кубическую сложность $O(n^3)$ и физически не могут обработать выборку из 1 миллиона строк. **Суть решения:** Используются методы предварительной агрегации (например, алгоритм *BIRCH*). Миллион сырых точек сжимается в 1000 компактных "микро-кластеров" (узлов CF-дерева). Затем эти 1000 микро-кластеров подаются на вход тяжелому алгоритму. Это позволяет радикально ускорить вычисления без потери качества анализа.

Метрика качества, которая сравнивает найденное алгоритмом разбиение с заранее известным эталонным разбиением. **Основная идея:** Внешняя оценка не анализирует геометрию кластеров напрямую. Она проверяет, насколько метки, полученные алгоритмом, согласуются с правильными метками объектов. Поэтому такие метрики применимы только в задачах, где есть эталонная разметка. **Парная интерпретация:** Многие внешние метрики рассматривают пары объектов. Если два объекта находятся в одном классе в эталонной разметке и в одном кластере в результате алгоритма, это считается согласованным решением. Если пара разделена по-разному, возникает расхождение. **Пример:** Скорректированный индекс Рэнда (Adjusted Rand Index), предложенный Хьюбертом и Араби, учитывает случайные совпадения и поэтому удобен для сравнения разных алгоритмов на размеченных наборах данных.

Метрика качества, которая оценивает результат кластеризации без опоры на внешнюю правильную разметку. **Основная идея:** Внутренняя оценка использует только исходные объекты, найденные кластеры и расстояния между ними. Поэтому такие метрики особенно важны в реальных задачах кластеризации, где заранее известных меток классов обычно нет. **Типовые критерии:** 1. **Компактность** — объекты внутри одного кластера должны быть близки друг к другу. 2. **Разделимость** — разные кластеры должны быть достаточно удалены. 3. **Баланс этих требований** — хорошее разбиение одновременно уменьшает внутрикластерный разброс и увеличивает межкластерные расстояния. **Примеры:** Коэффициент силуэта Р. Руссеу, индекс Дэвиса-Болдина и индекс Калински-Харабаша.

Сценарий микро-сегментации, при котором структура данных подразумевает наличие не 2-3 глобальных групп, а десятков или сотен локальных скоплений (паттернов). **Примеры применения:** * В биоинформатике (анализ экспрессии генов), где существуют сотни мелких семейств. * В компьютерном зрении (сегментация изображений на "суперпиксели" с помощью *Mean-Shift*). * Для таких задач отлично подходят алгоритмы, не требующие явного указания числа кластеров $k$, такие как *Affinity Propagation* или *Иерархические методы*, где разбиение формируется на основе взаимных "предпочтений" точек или локальных сдвигов.

Предположение о том, что кластеры представляют собой **выпуклые множества** (convex sets) в Евклидовом пространстве. **Математическая суть:** Алгоритмы этого типа (например, *K-Means*) неявно строят разбиение Вороного. Граница между любыми двумя кластерами всегда является гиперплоскостью (линейной границей). **Последствия:** * Идеально работает на компактных, хорошо разделенных "облаках" точек (Blobs). * Не может корректно разделить вложенные структуры (например, "кольцо внутри кольца") или изогнутые вытянутые формы ("бананы").

Алгоритм способен обрабатывать сверхбольшие объемы данных (сотни тысяч и миллионы наблюдений) за приемлемое время. **Теоретическое обоснование:** * **Сложность:** Линейная $O(n)$ или лог-линейная $O(n \log n)$. * **Механизмы:** 1. **Потоковая обработка (Online Learning):** Обновление параметров модели по мере поступления новых порций данных (батчей), без загрузки всего датасета в память (пример: *MiniBatch K-Means*). 2. **Сжатие данных:** Использование эффективных структур данных, таких как CF-деревья в алгоритме *BIRCH*, которые хранят только агрегированные статистики (суммы и квадраты сумм), а не сами точки. 3. **Пространственная индексация:** Использование KD-деревьев или Ball-деревьев для ускорения поиска соседей (*DBSCAN*).

Топологическая характеристика формы подмножеств в признаковом пространстве, которые алгоритм способен идентифицировать как единый кластер. **1. Выпуклая геометрия (Flat Geometry):** Кластеры аппроксимируются выпуклыми фигурами (гиперсферами, эллипсоидами или многогранниками Вороного). * **Математическая суть:** Алгоритм использует понятие «центра» (центроида) и Евклидово расстояние. Точки группируются вокруг центров. * **Ограничение:** Неспособность разделить вложенные структуры (например, «кольцо внутри кольца») или ленточные кластеры. * *Примеры:* K-Means, Gaussian Mixtures, Ward. **2. Произвольная геометрия (Non-flat / Manifold Geometry):** Кластеры рассматриваются как связные многообразия (manifolds) любой формы. * **Математическая суть:** Близость определяется не расстоянием до центра, а наличием «цепочки» близких соседей (транзитивное замыкание отношения близости). * **Применение:** Эффективно для выделения структур сложной формы (спирали, дуги), но вычислительно дороже. * *Примеры:* DBSCAN, Spectral Clustering, Agglomerative (Single Linkage).

Топологическая мера расстояния, при которой исходное метрическое пространство объектов заменяется графом. **Процесс вычисления:** 1. Каждый объект становится вершиной графа $V$. 2. Ребра $E$ проводятся только между $k$ ближайшими соседями (или точками в пределах радиуса $\epsilon$). 3. Расстояние между точками $A$ и $B$ определяется как длина кратчайшего пути по ребрам графа (алгоритм Дейкстры), либо через оценку связности случайного блуждания. **Применение:** Используется в методах *Спектральной кластеризации* и *Affinity Propagation*. Эта метрика блестяще решает задачу "скрученного рулона" (Swiss Roll), когда точки геометрически лежат близко друг к другу в Евклидовом пространстве, но топологически находятся на разных витках спирали и должны быть разнесены по графу.

Семейство методов, целью которых является построение не одного разбиения, а полной иерархии вложенных кластеров (таксономии). Результат визуализируется в виде **дендрограммы** — дерева, где корень — это все множество объектов, а листья — отдельные точки. **Основные подходы:** 1. **Агломеративные (AGNES — Agglomerative Nesting):** Стратегия «снизу-вверх». В начале каждый объект — это отдельный кластер. На каждом шаге происходит слияние двух самых близких кластеров. * *Математика:* Расстояние между кластерами пересчитывается по рекуррентной **формуле Ланса-Уильямса** (Lance-Williams formula). 2. **Дивизимные (DIANA — Divisive Analysis):** Стратегия «сверху-вниз». В начале все объекты в одном кластере. На каждом шаге один из кластеров расщепляется на два (обычно с помощью K-Means или спектрального метода). **Преимущество:** Не требуют предварительного знания числа кластеров $k$. Можно «разрезать» дерево на любом уровне детализации.

Условие, необходимое для применения внешних метрик качества. **Смысл условия:** Истинные метки классов задают эталонное разбиение объектов. Только при наличии такой разметки можно вычислять метрики, которые сравнивают результат алгоритма с правильным ответом: Rand Index, Adjusted Rand Index, Normalized Mutual Information и другие внешние показатели. **Ограничение:** В типичной задаче кластеризации эталонной разметки нет, поскольку сама цель анализа состоит в поиске неизвестной структуры данных. Поэтому внешние метрики чаще используются в учебных экспериментах, на benchmark-наборах данных или при проверке алгоритмов на размеченных выборках. Если истинные метки отсутствуют, следует применять внутренние метрики качества.

Внутренняя метрика, предложенная Д. Дэвисом и Д. Болдином. Она оценивает, насколько каждый кластер похож на наиболее близкий к нему соседний кластер с точки зрения компактности и расстояния между центрами. **Формула:** $DB = \frac{1}{K}\sum_{i=1}^{K}\max_{j \ne i}\left(\frac{S_i + S_j}{M_{ij}}\right)$, где $K$ — число кластеров, $S_i$ — среднее расстояние объектов i-го кластера до его центра, $M_{ij}$ — расстояние между центрами i-го и j-го кластеров. **Логика критерия:** Чем меньше значение индекса, тем лучше кластеризация: кластеры более компактны и лучше отделены друг от друга. Высокое значение показывает, что хотя бы для части кластеров существует слишком похожий соседний кластер.

Внутренняя метрика, предложенная Т. Калински и Я. Харабашем. Она основана на отношении межкластерной и внутрикластерной дисперсии. **Формула:** $CH = \frac{B_k / (K - 1)}{W_k / (n - K)}$, где $B_k$ — межкластерная дисперсия, $W_k$ — внутрикластерная дисперсия, $K$ — число кластеров, $n$ — число объектов. **Логика критерия:** Чем выше значение индекса, тем более плотными и лучше разделенными считаются найденные кластеры. **Практическое применение:** Используется как быстрая альтернатива полному перебору попарных расстояний при подборе числа кластеров. Метрика особенно удобна для центроидных алгоритмов, где естественно вычисляются внутрикластерные и межкластерные суммы квадратов.

**Обучение с обобщением (Generalization).** Алгоритм строит компактную математическую модель (функцию $a(x)$), которая отделена от обучающей выборки. **Практический смысл:** 1. **Модель:** Мы запоминаем не все точки, а только параметры (например, координаты центроидов в *K-Means* или матрицу ковариации в *GMM*). 2. **Продакшен:** Можно обучить модель один раз, сохранить её, и затем быстро классифицировать новые, ранее невидимые объекты с помощью метода `.predict(new_data)` в реальном времени.

Кластеризация — это задача анализа данных, в которой множество объектов разбивается на группы, называемые кластерами, без заранее заданных меток классов. **Место в машинном обучении:** Кластеризация относится к обучению без учителя. В отличие от классификации, алгоритм не получает готовые правильные ответы, а пытается обнаружить внутреннюю структуру данных по признакам объектов и выбранной мере сходства. **Формальная постановка:** Пусть задано множество объектов $X = \{x_1, x_2, ..., x_n\}$ и мера близости или расстояния $\rho(x_i, x_j)$. Требуется построить разбиение: $C = \{C_1, C_2, ..., C_K\}$, такое, что каждый объект принадлежит одному из кластеров, кластеры не пересекаются, а их объединение образует исходную выборку. В общем виде хорошее разбиение должно обеспечивать два свойства: 1. объекты внутри одного кластера похожи друг на друга; 2. объекты из разных кластеров достаточно различаются. **Критерии качества:** Для центроидных методов, например K-Means, цель часто выражается через минимизацию внутрикластерной суммы квадратов: $J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$, где $\mu_k$ — центр k-го кластера. Однако эта формула не является универсальной для всей кластеризации: плотностные, иерархические, графовые и модельные методы используют другие предположения о структуре данных. **Роль в электронном пособии:** В графе знаний это понятие используется как корневой узел. От него связываются основные группы методов кластеризации, метрики расстояния, параметры алгоритмов, критерии качества, условия применимости и практические сценарии. Такая организация помогает рассматривать кластеризацию не как набор отдельных алгоритмов, а как единую предметную область. **Теоретическая опора:** Описание понятия опирается на классические работы по кластерному анализу и машинному обучению: Б.Г. Миркина, К.В. Воронцова, A.K. Jain, M.N. Murty, P.J. Flynn, а также C.C. Aggarwal и C.K. Reddy.

Требование, согласно которому объекты внутри одного кластера должны быть как можно ближе друг к другу. **Математическая интерпретация:** Компактность обычно связывают с внутрикластерным разбросом. Для центроидных методов она может быть записана через сумму квадратов расстояний от объектов до центров своих кластеров: $W = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$, где $C_k$ — k-й кластер, $\mu_k$ — его центр, $K$ — число кластеров. **Интерпретация:** Чем меньше значение $W$, тем плотнее объекты сгруппированы вокруг своих центров. На этом принципе основан функционал k-средних и многие внутренние метрики качества. Однако минимизация только компактности может привести к искусственному дроблению данных на слишком большое число кластеров. Поэтому компактность обычно рассматривается вместе с разделимостью.

Специфический параметр для алгоритма *Affinity Propagation*, принимающий значения в диапазоне $[0.5, 1.0)$. **Математический смысл:** Алгоритм работает путем итеративного обмена сообщениями (ответственность и доступность) между точками графа. Чтобы избежать численных осцилляций (колебаний, когда точки бесконечно передают друг другу статус "центра"), новые значения сообщений "гасятся" — они рассчитываются как взвешенная сумма старого и нового значения. Чем выше *damping*, тем медленнее и стабильнее сходится алгоритм.

Эталонная внутренняя метрика качества, предложенная Р. Руссеу. Она сравнивает среднее расстояние объекта до своего кластера и до ближайшего соседнего кластера. **Формула:** Для объекта $i$: $s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$, где $a(i)$ — среднее расстояние от объекта $i$ до остальных объектов своего кластера, а $b(i)$ — минимальное среднее расстояние от объекта $i$ до объектов ближайшего чужого кластера. **Интерпретация:** * Значение близко к 1 — объект хорошо вписан в свой кластер. * Значение около 0 — объект находится на границе. * Отрицательное значение — объект, вероятно, отнесен к неверному кластеру. **Практическое применение:** Средний коэффициент силуэта по всем объектам используется для сравнения разных разбиений и подбора числа кластеров $k$ в алгоритмах, где этот параметр задается заранее.

Содержательный аспект, который показывает, что именно считается хорошей кластеризацией. **Смысл понятия:** Критерий качества не является конкретной формулой. Он задает смысловую сторону оценки результата: что нужно улучшать и какие свойства разбиения считать желательными. Уже на основе критерия выбирается конкретная численная метрика. **Основные критерии:** 1. **Компактность** — объекты внутри одного кластера должны быть близки. 2. **Разделимость** — разные кластеры должны быть удалены друг от друга. 3. **Согласованность с эталоном** — найденное разбиение должно совпадать с заранее известной правильной разметкой. В классической литературе по кластерному анализу эти критерии рассматриваются как базовые основания для оценки качества разбиения: внутренние метрики обычно объединяют компактность и разделимость, а внешние метрики оценивают соответствие эталонной классификации.

Способность алгоритма работать не с исходными координатами объектов (матрица "объект-признак"), а с заранее вычисленной квадратной матрицей сходства/различия размера $N \times N$. **Преимущества подхода:** Позволяет использовать *неметрические* или специфические пользовательские функции расстояния. Например, при анализе текстов (NLP) можно подать матрицу расстояний по косинусной мере, а в геномике — процент несовпадения последовательностей (расстояние Левенштейна). * **Представители:** Эту особенность отлично поддерживает общая *Агломеративная кластеризация*.

**Определение:** Вычислительная характеристика алгоритма, описывающая асимптотическую зависимость времени работы ($Time$) и потребления оперативной памяти ($Space$) от объема выборки ($n$ объектов и $d$ признаков). **Теоретический аспект (по К.В. Воронцову):** Многие мощные алгоритмы (Spectral, Agglomerative, Affinity Propagation) требуют вычисления и хранения полной матрицы попарных расстояний. Их сложность составляет $O(n^2)$ или $O(n^3)$. При выборках больше 20 000 объектов такие методы исчерпывают оперативную память. **Инженерные решения для Big Data:** Для достижения высокой масштабируемости применяются структурные и алгоритмические оптимизации: * **Пространственные индексы:** KD-деревья или Ball-деревья снижают сложность поиска соседей с $O(n^2)$ до $O(n \log n)$ (например, оптимизированный DBSCAN). * **Пакетная обработка:** Метод градиентного спуска по мини-батчам (MiniBatch K-Means). * **Предагрегация (Сжатие):** Построение компактного дерева признаков за один проход по данным $O(n)$ (алгоритм BIRCH).

Функционал или численный индекс, предназначенный для оценки качества полученного разбиения. **Роль в учебной системе:** Метрики качества связывают алгоритм кластеризации с этапом анализа результата. Это важно для адаптивного обучения, поскольку студент должен не только запустить метод, но и уметь оценить, насколько осмысленным получилось разбиение. **Основные типы:** 1. **Внутренние метрики** — используют только структуру данных и найденные кластеры. 2. **Внешние метрики** — сравнивают результат с эталонной разметкой, если она известна.

Математическая функция $\rho(x, x')$, определяющая степень «несходства» (dissimilarity) между двумя объектами в пространстве признаков. Согласно **аксиоматике метрического пространства**, должна удовлетворять условиям неотрицательности, симметрии и неравенству треугольника. **Важность выбора (по К.В. Воронцову):** Результат кластеризации часто зависит от выбора метрики сильнее, чем от выбора алгоритма. * Если признаки измерены в разных единицах (кг, метры, рубли), использование метрик без предварительной **стандартизации** (Z-score) бессмысленно — признак с наибольшим масштабом «подавит» остальные. **Основные классы метрик:** 1. **Геометрические ($L_p$ Минковского):** Евклидово ($L_2$), Манхэттенское ($L_1$), Чебышева ($L_\infty$). Подходят для числовых векторов. 2. **Статистические:** Расстояние Махаланобиса (учитывает ковариацию и дисперсию признаков). 3. **Структурные:** Графовые расстояния, редакционное расстояние (для текстов/строк).

Второй важнейший параметр плотностных алгоритмов (*DBSCAN, HDBSCAN, OPTICS*). Определяет минимальное количество соседей (включая саму точку), которое должно находиться внутри $\epsilon$-окрестности, чтобы точка была признана **корневой (Core point)**. **Практический смысл:** Этот параметр напрямую контролирует терпимость алгоритма к шуму. Чем выше *MinPts*, тем более плотными должны быть скопления точек, чтобы образовать кластер, и тем больше точек будет объявлено фоновым шумом.

Семейство методов, рассматривающих кластеризацию как задачу восстановления плотности распределения вероятностей. **Гипотеза:** Наблюдаемые данные $X$ являются случайной выборкой из смеси нескольких вероятностных распределений (компонент смеси), каждое из которых соответствует кластеру. **Ключевые особенности:** 1. **Максимизация правдоподобия:** Цель — найти такие параметры распределений (средние $\mu_k$, дисперсии $\Sigma_k$), которые максимизируют вероятность появления именно такой выборки данных. 2. **EM-алгоритм (Expectation-Maximization):** Итеративный метод решения. * *E-step:* Оценка вероятности принадлежности точки кластеру. * *M-step:* Пересчет параметров распределений. 3. **Мягкая кластеризация (Soft Clustering):** Результат — не метка класса, а вектор вероятностей (например, «точка на 80% в кластере А и на 20% в кластере Б»).

Алгоритм способен корректно обрабатывать дисбаланс классов, когда один кластер содержит в сотни раз больше объектов, чем другой, или имеет значительно большую пространственную протяженность. **Применение:** Это свойство критически важно для реальных задач, таких как: * **Поиск аномалий:** Обычно нормальных данных 99%, а аномалий — 1%. * **Социальный анализ:** Выделение малых социальных групп на фоне общей массы. **Представители:** Плотностные методы (*DBSCAN*) и методы на основе передачи сообщений (*Affinity Propagation*).

Алгоритм не предназначен для обработки больших данных. Эффективен только на малых выборках (обычно до 10 000 - 20 000 объектов). **Причина (Проклятие размерности выборки):** Вычислительная сложность составляет квадратичную $O(n^2)$ или кубическую $O(n^3)$ зависимость. Это связано с необходимостью вычисления и хранения в памяти **полной матрицы попарных расстояний** (affinity matrix) размера $N \times N$. * *Пример:* Для 100 000 объектов матрица расстояний (float64) займет около 75 ГБ оперативной памяти, что делает работу алгоритмов типа *Affinity Propagation* или *Hierarchical (Ward)* невозможной на стандартном оборудовании без предварительного сжатия данных.

Характеристика алгоритма, определяющая его чувствительность к дисбалансу количества элементов в искомых группах. Это ограничение часто вытекает из математической природы оптимизируемого функционала. **1. Равномерные размеры (Even Cluster Size):** Многие итеративные алгоритмы (например, *K-Means*, *Ward*) стремятся минимизировать суммарную квадратичную ошибку (инерцию). Математически это приводит к тому, что алгоритм «штрафует» большие протяженные кластеры, стремясь разбить их на несколько более компактных сфер одинакового радиуса. * *Следствие:* Если в данных есть один гигантский кластер и один маленький, такие алгоритмы часто ошибочно расщепляют большой кластер. **2. Неравномерные размеры (Uneven Cluster Size):** Алгоритмы, основанные на плотности (*DBSCAN*) или графовых связях (*Affinity Propagation*), не накладывают ограничений на количество точек в кластере. Кластер определяется как связная область пространства. * *Следствие:* Позволяет корректно выделять малые группы (аномалии) на фоне массивных структур.

Фундаментальная статистическая задача восстановления неизвестной функции плотности вероятности (Probability Density Function) генеральной совокупности на основе имеющейся конечной выборки. **Практический смысл:** В отличие от "жесткой" кластеризации, здесь решается задача **мягкой кластеризации (Soft Clustering)**. Мы определяем не просто принадлежность точки к кластеру, а *вероятность* того, что данная точка была сгенерирована данным кластером. * **Методы:** Классическим решением является использование смесей распределений (*Gaussian Mixtures*). Это позволяет в дальнейшем использовать полученную модель как генеративную (для создания новых синтетических данных, похожих на исходные).

Управляющие переменные (гиперпараметры) алгоритма, значения которых исследователь должен зафиксировать **до** начала процедуры обучения. **Роль в задаче кластеризации (по Б.Г. Миркину):** Поскольку задача кластеризации формально некорректна (не имеет единственного решения), параметры служат способом введения **априорных знаний** или ограничений на искомую структуру: * Мы *ожидаем* увидеть 3 группы $\rightarrow$ задаем $k=3$. * Мы *считаем* близкими объекты на расстоянии 0.5 метра $\rightarrow$ задаем $\epsilon=0.5$. **Типичные ошибки:** Неверный подбор параметров может привести к тривиальным решениям: * Один гигантский кластер, объединяющий всё. * Каждая точка — отдельный кластер (переобучение).

Класс алгоритмов, базирующихся на **гипотезе плотности**: кластеры — это области пространства с высокой плотностью размещения объектов, которые отделены друг от друга областями с низкой плотностью (шумом). **Теоретические основы (DBSCAN/OPTICS):** Алгоритм оперирует понятиями: * **$\epsilon$-окрестность:** Сфера радиуса $\epsilon$ вокруг точки. * **Корневая точка (Core point):** Точка, в окрестности которой находится не менее $MinPts$ соседей. * **Достижимость по плотности:** Точка $p$ достижима из $q$, если существует цепочка корневых точек, соединяющая их. **Ключевые преимущества:** 1. **Произвольная геометрия:** Способность находить кластеры любой формы (в отличие от центроидных методов, ищущих выпуклые сферы). 2. **Фильтрация шума:** Объекты, не попадающие в плотные области, автоматически помечаются как выбросы (outliers) и не портят центры кластеров. 3. **Автоматическое $k$:** Не нужно заранее знать количество кластеров.

Специфическая задача Data Mining, также известная как **Anomaly Detection** (Обнаружение аномалий). **Теоретическая проблема:** Алгоритмы, минимизирующие дисперсию (как *K-Means*), чувствительны к выбросам: одна аномальная точка может сильно сместить центроид всего кластера. В реальных данных (сенсоры, финансовые транзакции) всегда присутствует фоновый шум. **Решение:** Необходимы плотностные алгоритмы (*DBSCAN, OPTICS*), которые не пытаются "втянуть" каждую точку в кластер. Если точка находится в разреженном пространстве и не имеет достаточного числа соседей (параметр MinPts), она изолируется и помечается как шум (выброс).

Пороговая величина, используемая в иерархических методах (для "срезания" дендрограммы) или в эвристике Максимина. **Принцип действия:** * В **агломеративных методах**: если расстояние между двумя кластерами превышает этот порог, их слияние останавливается. Это позволяет получить "плоское" разбиение из дерева. * В **алгоритме Максимина**: если расстояние от новой точки до существующих центров больше порога $T$, точка объявляется новым независимым центром ("гнездом").

Типовая бизнес-задача или задача анализа данных (Data Mining), для решения которой математические свойства конкретного алгоритма подходят наилучшим образом. **Основные сценарии применения (из введения Б.Г. Миркина):** 1. **Структуризация данных (General-purpose):** Выделение типичных профилей (например, сегментация клиентов банка). Важна хорошая интерпретируемость центроидов (K-Means). 2. **Поиск аномалий (Outlier Removal):** Выявление нетипичных объектов, мошенничества или технического брака. Требует методов, способных изолировать шум, а не втягивать его в ближайший кластер (DBSCAN, OPTICS). 3. **Сокращение размерности / Векторное квантование (Data Reduction):** Замена миллионов сырых объектов небольшим набором "микро-кластеров" для ускорения последующего обучения тяжелых нейросетей (BIRCH). 4. **Оценка плотности вероятности (Density Estimation):** Построение генеративной модели для генерации новых похожих данных (Gaussian Mixtures).

Способность алгоритма выделять кластеры сложной топологической формы (многообразия, manifolds), которые не являются выпуклыми. **Принцип работы:** Основывается на **гипотезе связности** или **плотности**: объекты объединяются в один кластер не потому, что они близки к единому центру, а потому, что между ними существует "цепочка" близких соседей. **Примеры форм:** Спирали, дуги, вложенные сферы. **Алгоритмы:** *DBSCAN, Spectral Clustering, Agglomerative.*

Алгоритм имеет математическое смещение (bias) в сторону создания кластеров примерно одинакового диаметра или количества элементов. **Теоретическая причина:** Многие итеративные алгоритмы (например, *K-Means* или *Ward*) минимизируют функционал суммарной квадратичной ошибки (инерцию). Математически это эквивалентно разбиению Вороного с центрами, стремящимися покрыть пространство равномерно. **Следствие:** Если в данных присутствует один огромный разреженный кластер и один маленький плотный, алгоритм с этим свойством ошибочно "разрежет" большой кластер на части, чтобы уравнять вклад дисперсии.

Требование, согласно которому разные кластеры должны быть как можно дальше друг от друга. **Математическая интерпретация:** Разделимость можно оценивать через расстояния между центрами кластеров или через межкластерную дисперсию. Для центроидной постановки часто используется величина: $B = \sum_{k=1}^{K} n_k \|\mu_k - \mu\|^2$, где $n_k$ — число объектов в k-м кластере, $\mu_k$ — центр кластера, $\mu$ — общий центр выборки. **Интерпретация:** Чем больше межкластерная дисперсия $B$, тем сильнее центры кластеров отделены друг от друга. Хорошее разбиение обычно требует одновременно малой внутрикластерной дисперсии и большой межкластерной дисперсии. На этом соотношении построен, например, индекс Калински-Харабаша.

Один из двух главных параметров алгоритма *DBSCAN*. Задает максимальное физическое расстояние (радиус $\epsilon$-окрестности), при котором две точки считаются "соседями". **Влияние на результат:** * Если $\epsilon$ **слишком мал**: значительная часть нормальных данных не найдет соседей и будет ошибочно размечена как шум (выбросы). * Если $\epsilon$ **слишком велик**: близко расположенные, но независимые кластеры сольются в один гигантский кластер, а шум исчезнет вообще.

Параметр для потоковых версий алгоритмов (например, *MiniBatch K-Means*). Задает количество случайно отбираемых объектов из огромной выборки, которые обрабатываются за одну мини-итерацию. **Суть оптимизации:** Вместо того чтобы на каждом шаге считать расстояние от *каждого* центроида до *миллиона* точек (что требует $O(N \cdot K)$ операций), алгоритм берет пакет, например, из 100 точек, и сдвигает центроиды только относительно них. Это дает колоссальный прирост скорости при минимальной потере качества.

Статистическая мера расстояния, которая оценивает близость точки к центру распределения с учетом дисперсии и ковариации (взаимного влияния) признаков. **Теоретическое значение:** В отличие от Евклидова расстояния, которое формирует сферические области равной вероятности, расстояние Махаланобиса формирует **эллипсоиды**. Оси этих эллипсоидов поворачиваются и вытягиваются в направлении наибольшего разброса данных. * **Применение:** Является сердцем вероятностных модельных методов, таких как *Gaussian Mixtures (Смеси распределений)*. Оно позволяет алгоритму корректно распознавать вытянутые и повернутые облака точек, с которыми не справляется базовый K-Means.

Классическая геометрическая мера расстояния (норма $L_2$), вычисляемая как корень из суммы квадратов разностей координат двух векторов. **Особенности применения:** * Это самая популярная метрика, лежащая в основе *K-Means* и критерия *Уорда*. * **Фундаментальное ограничение (по Б.Г. Миркину):** Использование Евклидова расстояния имеет смысл *только* в том случае, если все признаки измеряются в одной шкале и имеют одинаковую размерность. * **Следствие:** Перед применением алгоритмов с этой метрикой данные обязательно должны быть подвергнуты стандартизации (например, $Z$-масштабированию), иначе признак с наибольшим разбросом (например, "доход в миллионах") полностью подавит влияние остальных признаков.

Локальная метрика связности, используемая в плотностных методах (*DBSCAN*, *HDBSCAN*) и агломеративном методе *Single Linkage*. **Математическая суть:** В отличие от центроидных методов, которые измеряют расстояние от точки до условного центра "масс", здесь оценивается расстояние от текущей точки до **ближайшего к ней соседа** из уже существующего кластера. * **Преимущество:** Это позволяет алгоритму "перепрыгивать" от точки к точке, выстраивая кластеры в виде длинных цепочек, лент или колец (многообразий сложной топологии), игнорируя пустоты между такими лентами.

Внешняя метрика качества, сравнивающая предсказанное разбиение с эталонной кластеризацией. Скорректированный индекс Рэнда был предложен Хьюбертом и Араби как вариант Rand Index с поправкой на случайные совпадения. **Формула:** $ARI = \frac{RI - E[RI]}{\max(RI) - E[RI]}$, где $RI$ — индекс Рэнда, $E[RI]$ — ожидаемое значение индекса при случайном разбиении. **Ключевая особенность:** Индекс скорректирован на случайное совпадение: * значение 0 соответствует случайному угадыванию; * значение 1 соответствует полному совпадению с эталоном. * отрицательные значения возможны, если разбиение хуже случайного ожидания. **Педагогическая ценность:** Полезен в учебных экспериментах, когда студенту нужно сравнить результат алгоритма с заранее известной правильной разметкой.

Критерий качества, при котором результат кластеризации сравнивается с заранее известной правильной разметкой объектов. **Смысл критерия:** Если для набора данных известны истинные метки классов, можно проверить, насколько найденные кластеры совпадают с эталонной структурой. При этом номера кластеров сами по себе не важны: важно, какие пары объектов оказались вместе или раздельно. **Парная логика:** Для пары объектов $(x_i, x_j)$ сравнивается два факта: 1. находятся ли они в одном классе в эталонной разметке; 2. находятся ли они в одном кластере в результате алгоритма. Если эти решения совпадают для большого числа пар, кластеризация считается согласованной с эталоном. На этом принципе основаны Rand Index и Adjusted Rand Index.

Алгоритм эффективно работает на выборках среднего размера (от тысяч до нескольких десятков тысяч объектов), но сталкивается с ограничениями при переходе к Big Data. **Ограничения:** При увеличении объема данных производительность деградирует нелинейно, либо возрастают требования к оперативной памяти. * *Пример:* **Спектральная кластеризация**. Требует вычисления собственных векторов матрицы Лапласиана. Хотя существуют методы для разреженных матриц (Arpack), для очень больших $n$ это становится вычислительно затратным.

Характеристика обобщающей способности алгоритма (Generalization Ability), определяющая, как модель работает с новыми данными, отсутствовавшими в обучающей выборке. **1. Индуктивный вывод (Inductive Learning):** Алгоритм строит решающую функцию (модель) $a: X \to Y$, которая аппроксимирует зависимость на всем пространстве признаков. * *Суть:* Обучение ($fit$) отделено от применения ($predict$). Мы «выучиваем» параметры (например, координаты центроидов $\mu_k$ или матрицу ковариации $\Sigma$). * *Пример:* K-Means. Если придет новая точка, мы просто найдем ближайший к ней центроид, не пересчитывая всё заново. **2. Трансдуктивный вывод (Transductive Learning):** Алгоритм не строит общей модели, а решает задачу разбиения только для *конкретного* конечного множества объектов $X^\ell$. * *Суть:* Метки кластеров выводятся из взаимного расположения всех точек выборки. Понятие «центра» может отсутствовать. * *Проблема:* Для классификации нового объекта $x_{new}$ необходимо добавить его в выборку и перезапустить процесс кластеризации с нуля. * *Пример:* DBSCAN, Spectral Clustering, Hierarchical Clustering.

**Обучение "здесь и сейчас" (Specific-to-Specific).** Алгоритм не создает обобщающей модели, а выводит метки кластеров непосредственно из структуры связей текущей конкретной выборки. **Математическая суть:** Решение задачи (разметка) существует только в контексте полного графа данных. Например, в *Spectral Clustering* кластеры определяются собственными векторами матрицы Лапласиана, размер которой $N \times N$. **Ограничение:** Нельзя классифицировать новый объект отдельно. В библиотеке Scikit-Learn у таких алгоритмов отсутствует метод `.predict()`, есть только `.fit_predict()`.

Типовая задача разведочного анализа данных (EDA — Exploratory Data Analysis), когда исследователь впервые сталкивается с неизвестным датасетом. **Особенности сценария:** * Цель: получить быстрое, интерпретируемое и "грубое" разбиение данных на основные сегменты (например, базовая сегментация клиентов по доходу и возрасту). * Для таких задач традиционно используются быстрые алгоритмы разбиения (в первую очередь, *K-Means*). Они выступают в роли "базлайна" (baseline) — отправной точки, с которой будут сравниваться более сложные и тяжелые модели.

Контекст или дополнительное требование, без которого конкретная метрика качества не может быть корректно применена. **Почему это важно:** Не каждая метрика подходит для любой задачи. Например, внешние метрики требуют эталонных меток классов, а внутренние метрики требуют определенной меры расстояния между объектами или кластерами. Если условие применения нарушено, численное значение метрики может выглядеть формально корректным, но методически ничего не объяснять. **Пример:** Скорректированный индекс Рэнда имеет смысл только при наличии истинных меток классов. Коэффициент силуэта, наоборот, может применяться без эталона, но требует вычисления расстояний между объектами.

Параметр алгоритма *BIRCH*, ограничивающий максимальное количество подкластеров (потомков), которые могут находиться в одном узле дерева признаков кластеризации (CF Tree). **Назначение:** Регулирует степень сжатия данных. Балансирует ширину и глубину строящегося дерева, что позволяет алгоритму обрабатывать миллионы записей, не превышая строгие лимиты оперативной памяти.

Ключевой гиперпараметр для алгоритмов разбиения (*K-Means*, *Spectral Clustering*). Пользователь обязан до начала работы алгоритма указать, на сколько именно групп ($k$) нужно разбить данные. **Теоретическая проблема:** Поскольку задача кластеризации некорректна (нет правильных ответов), выбор $k$ полностью ложится на плечи исследователя. * Если $k$ слишком мало: различные по смыслу кластеры сольются в один. * Если $k$ слишком велико: истинные кластеры будут искусственно раздроблены (переобучение). **Методы подбора:** Эвристика Максимина (для начальных точек), «Метод локтя» (Elbow method) или максимизация Коэффициента силуэта.

Критический параметр для метода *Mean-Shift* и ядерной оценки плотности. Определяет радиус "окна" поиска (сферы), внутри которого вычисляется локальный центр масс. **Метафора (из лекций):** "Дальность обзора человека в тумане". * **Маленький bandwidth:** алгоритм видит только ближайших соседей. Приведет к выделению множества микро-кластеров (каждый локальный бугорок плотности станет кластером). * **Большой bandwidth:** алгоритм усредняет данные по большой площади, сливая всё в несколько глобальных макро-кластеров.