Метод ближнего соседа в кластерном анализе

Две группы объектов могут казаться далёкими в целом, но иметь по одной близкой паре представителей. Метод ближнего соседа объединяет группы именно по такой паре: он ищет минимальное расстояние между их объектами. Повторяя это правило, можно построить иерархию групп и посмотреть, как меняется разбиение при разных порогах расстояния.
Разберём учебный пример из пяти точек на прямой: , , , , . В калькуляторе двигайте порог : связь появляется, когда расстояние не больше , а соединённые цепочкой точки попадают в одну группу. При обратите внимание на расстояние между крайними точками группы.
Правило ближайшей пары
Метод ближнего соседа, или одиночное связывание (single linkage), относится к агломеративным методам кластеризации. Сначала каждый объект образует отдельный кластер. Затем два ближайших кластера сливаются, и процесс повторяется до одного общего кластера либо до выбранного условия остановки. Здесь заранее известные метки классов не нужны: это группировка без учителя.
Пусть и - два непересекающихся кластера, а - выбранное расстояние между объектами. Расстояние между группами определяется так:
Для объединения достаточно одной близкой пары. Например, если расстояния между представителями двух групп равны 3, 5, 6 и 8, то . Остальные пары на это значение не влияют. Среди всех пар текущих кластеров алгоритм выбирает наименьшее .
Слово «сосед» встречается и в методе k ближайших соседей, но там обычно предсказывают известный класс или числовой ответ нового объекта по размеченным примерам. Здесь же мы объединяем неразмеченные объекты в иерархию; параметр соседей для голосования не нужен.
Расстояния и исходная матрица
В примере используем расстояние на прямой . Поэтому , а . Полная симметричная матрица имеет нули на диагонали:
| Объект | А | Б | В | Г | Д |
|---|---|---|---|---|---|
| А | 0 | 1 | 3 | 6 | 10 |
| Б | 1 | 0 | 2 | 5 | 9 |
| В | 3 | 2 | 0 | 3 | 7 |
| Г | 6 | 5 | 3 | 0 | 4 |
| Д | 10 | 9 | 7 | 4 | 0 |
На плоскости вместо модуля разности часто берут евклидово расстояние , но возможны и другие меры. Выбор зависит от смысла признаков: например, для строковых категорий нельзя без обоснования считать разность произвольных числовых кодов.
Если один признак измеряется в тысячах, а другой в единицах, первый может определять расстояния просто из-за масштаба. До расчёта следует решить, нужна ли стандартизация, обработать пропуски и проверить выбросы. Само правило одиночного связывания не исправляет неудачную метрику: изменятся исходные расстояния - может измениться и дерево.
Пошаговый расчёт и обновление матрицы
Первый минимум в таблице равен 1: объединяем и . Теперь для каждого оставшегося кластера берём минимум расстояний от его объектов до или . Например,
Аналогично расстояния от до и равны соответственно 5 и 9. В сокращённой матрице минимум теперь равен 2, значит к группе присоединяется . Далее расстояние от до равно , а до - .
| Шаг | Слияние | Расстояние | Число групп после слияния |
|---|---|---|---|
| 1 | и | 1 | 4 |
| 2 | и | 2 | 3 |
| 3 | и | 3 | 2 |
| 4 | и | 4 | 1 |
Последнее расстояние равно . При объединении и обновление можно записать компактно: . Старые строки и столбцы и заменяются одной строкой и одним столбцом нового кластера.
Для объектов при полном построении выполняется слияние. Если несколько пар одновременно достигают минимума, порядок отдельных слияний зависит от принятого правила разрешения равенства. Его полезно указать; при отсечении по точному порогу все связи на этом расстоянии следует учитывать согласованно.
Порог и цепочный эффект
Положим и включим слияния на высоте, равной порогу. Тогда получаем группы и . У соседних звеньев первой группы длины 1, 2 и 3, но расстояние от до равно 6. Условие распространяется на связи, а не на все пары внутри кластера.

Это и есть цепочный эффект: ряд промежуточных объектов соединяет удалённые области. Он полезен для поиска вытянутых или извилистых структур, но несколько шумовых точек могут создать нежелательный мост между группами. В нашем примере точка участвует в цепочке между и : близость краёв сама по себе не гарантируется.
При все пять объектов раздельны; при групп четыре, при - три, при - две, а при - одна. Порог выбирают с учётом задачи и масштаба данных, а не по универсальному числу. Полезно посмотреть, устойчив ли результат при небольшом изменении и после проверки подозрительных объектов.
Дендрограмма и остовное дерево
Последовательность слияний удобно изобразить деревом: его листья - объекты, а высота каждой развилки - расстояние объединения. Горизонтальный срез на уровне показывает группы для этого порога. Подробное чтение такого рисунка и сравнение правил связывания разобраны в статье об иерархической кластеризации и дендрограмме.
Есть и графовая интерпретация: соединим ребром каждую пару объектов с расстоянием не больше . Кластеры одиночного связывания совпадут с компонентами связности этого графа. Поэтому для двух точек достаточно существования пути из коротких звеньев; прямого ребра между ними не требуется.
Для полного взвешенного графа ту же иерархию пороговых разбиений можно получить из минимального остовного дерева: удалить из него рёбра длиннее и взять оставшиеся компоненты. В нашем примере остов соединяет соседние точки рёбрами длиной 1, 2, 3 и 4. Такой подход лежит в основе реализации single linkage в документации SciPy. Как строится остов, показано на примере алгоритма Краскала.
Когда применять и с чем сравнивать
Одиночное связывание подходит для разведочного поиска связанных цепей и кластеров сложной формы. Но его результат чувствителен к шумовым мостам; это ограничение отмечено и в руководстве scikit-learn. Перед выводами сравните разбиение с предметными знаниями, проверьте масштабирование и исследуйте отдельные длинные рёбра.
Для сравнения метод дальнего соседа берёт максимум межкластерных расстояний, а среднее связывание - среднее по всем межкластерным парам. Они отвечают на разные вопросы: близость одной пары не равна компактности всей группы. На реальных данных, например при кластерном анализе регионов, содержательность результата зависит ещё и от выбора показателей, периода и способа их приведения к сопоставимому масштабу.
Как проверить результат на своих данных
Прежде чем запускать алгоритм, сформулируйте, какие объекты сравниваются и что для них означает близость. Для покупателей это может быть сходство структуры покупок, для документов - сходство представлений текста, для территорий - близость набора социально-экономических показателей. Одна таблица позволяет получить разные разумные разбиения: они отвечают на разные вопросы, если признаки или расстояния выбраны по-разному.
Затем проверьте диапазоны признаков и единицы измерения. Стандартизация по среднему и стандартному отклонению полезна, когда важны отклонения относительно типичного разброса каждого признака, но это содержательное решение, а не обязательная кнопка. Если абсолютная разница в одном показателе важнее остальных, её нельзя автоматически стирать масштабированием. После преобразований стоит заново проверить несколько пар объектов вручную: действительно ли рассчитанная близость соответствует смыслу задачи?
Построив дерево, рассмотрите несколько соседних порогов и состав групп на каждом из них. Обратите внимание на объекты, через которые соединяются крупные части: не являются ли они ошибками ввода, пропусками с условным кодом или необычными наблюдениями? Удалять точку только потому, что она меняет результат, нельзя: сначала выясните причину и сравните расчёты с ней и без неё. Если небольшое изменение порога резко меняет состав, этот факт стоит сообщить вместе с выводом.
Наконец, сравните найденные группы с независимой информацией, если она доступна, и с результатами другого правила связывания. Совпадение не доказывает, что найдено единственно правильное деление, а различия помогают понять, зависит ли вывод от цепочек или от общей компактности. В отчёте укажите признаки, подготовку данных, меру расстояния, правило связывания и порог: тогда расчёт можно воспроизвести и содержательно обсудить.
Частые ошибки
- Объединять по ближайшим центрам. Одиночное связывание использует минимальное расстояние между объектами двух групп, а не расстояние между средними.
- Считать порог максимальным диаметром. Внутри связанной цепи отдельные пары могут быть дальше порога, как и в примере.
- Пересчитывать расстояние до новой группы как среднее. После слияния берётся минимум прежних расстояний; среднее задаёт другое правило.
- Игнорировать равные минимумы и масштаб признаков. Первое влияет на порядок записи слияний, второе - на исходную геометрию и итоговые группы.
FAQ
Сколько кластеров задаёт метод? Само правило задаёт порядок слияний. Число групп определяют условием остановки или срезом дерева на выбранной высоте.
Можно ли использовать матрицу готовых расстояний? Да. Если попарные расстояния осмысленны для задачи, правило минимума применяется к ним без вычисления координат центров.
Всегда ли связанная цепь означает хороший кластер? Нет. Она означает связность при данном пороге. Наличие мостов из шума и интерпретируемость группы нужно проверять отдельно.
Коротко
Метод ближнего соседа последовательно объединяет кластеры по минимальному расстоянию между их представителями. Пороговый срез даёт компоненты связности, поэтому цепочка коротких звеньев может объединить далёкие объекты. Расчёт зависит от метрики, масштаба признаков и выбора порога; эти решения нужно проверять вместе с результатом.
Читайте также

Иерархическая кластеризация: как читать дендрограмму
Иерархическая кластеризация и дендрограмма: как работает агломеративный алгоритм, чем отличаются методы связывания single, complete и average, как выбрать порог отсечения и найти число кластеров.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

Кластерный анализ регионов: показатели и пример
Как провести кластерный анализ регионов: выбрать сопоставимые показатели, стандартизовать данные, рассчитать расстояния, описать группы и проверить устойчивость результата.

Многомерная группировка: признаки и расстояния
Многомерная группировка в экономике: как сравнить объекты по нескольким признакам, выбрать масштаб и расстояние, проверить устойчивость и интерпретировать группы.

Абсолютная и относительная погрешность числа
Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.

Абсолютная пропускная способность СМО: формула
Как найти абсолютную пропускную способность СМО через интенсивность потока и вероятность отказа: формула, пример расчёта и отличие от относительной способности.