Clustering — Кластеризация

Разбиение объектов на группы похожих без заранее известных меток.

Ключевые тезисы

Семейства: центроидные, плотностные, иерархические, спектральные.
Результат целиком зависит от выбранной метрики расстояния.
Оценка качества без меток — силуэт, Davies–Bouldin, Calinski–Harabasz.

Тема также относится к главам:Топологический анализ данныхПрименение Графы и сетиОсновы

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Семейства алгоритмов

Четыре подхода и данные, для которых каждый создан.

Семейство	Примеры	Форма кластеров	Нужно ли задавать K
Центроидные	k-means, k-medoids	сферические	да
Плотностные	DBSCAN, HDBSCAN	произвольная	нет
Иерархические	агломеративная	любая, дерево вложенности	нет (режем дендрограмму)
Спектральные	spectral clustering	связные, невыпуклые	да

кластеров k3

итераций4

инерция (WCSS)0.880

Число кластеров k3Итерации алгоритма4

k-means на трёх компактных группах — тот случай, где его предположения выполняются

Как понять, что кластеризация удалась

Внутренние метрики, устойчивость и здравый смысл.

Внутренние метрики: силуэт, Davies–Bouldin, Calinski–Harabasz — сравнивают разбиения между собой.
Устойчивость: перезапустите на подвыборках; если разбиение каждый раз новое, структуры в данных, скорее всего, нет.
Внешняя валидация: если есть хоть какая-то разметка (даже частичная), сравните с ARI или NMI.
Интерпретируемость: кластеры должны отличаться по признакам так, чтобы это можно было объяснить словами.

Связанные темы

Работа с корпусами текстов · Машинное обучение на графах · Кластеризация и её оценка

Graph Basics85%

Основы графов · Графы и сети

Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.

Centrality85%

Центральности · Графы и сети

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

PageRank85%

PageRank · Графы и сети

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

Community Detection85%

Поиск сообществ · Графы и сети

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

Graph Embeddings85%

Графовые эмбеддинги · Графы и сети

Векторные представления вершин, в которых близость отражает связанность в графе.

Graph Neural Networks85%

Графовые нейросети · Графы и сети

Нейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.

Message Passing85%

Передача сообщений · Графы и сети

Единая схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.

Link Prediction85%

Предсказание связей · Графы и сети

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

Knowledge Graphs85%

Графы знаний · Графы и сети

Факты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.

Network Motifs85%

Мотивы и триады · Графы и сети

Маленькие повторяющиеся подграфы, встречающиеся чаще, чем в случайной сети. Хорошие признаки для классификации вершин.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.

Topic Modeling75%

Тематическое моделирование · Обработка естественного языка

Автоматическое выделение тем в коллекции документов: от классического LDA до кластеризации эмбеддингов.

Summarization75%

Суммаризация · Обработка естественного языка

Сжатие текста с сохранением смысла: извлекающая (выбор предложений) и абстрактивная (генерация).

Text classification75%

Классификация текстов · Обработка естественного языка

Отнесение документа к одной или нескольким категориям: от спам-фильтра до маршрутизации тикетов.

LLM Evaluation75%

Оценка языковых моделей · Генеративный ИИ

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

Perplexity75%

Перплексия · Метрики

Экспонента кросс-энтропии языковой модели: между сколькими равновероятными вариантами она в среднем выбирает.

k-Means75%

k-средних · Классическое машинное обучение

Разбивает объекты на k кластеров, минимизируя суммарное расстояние до центроидов.

DBSCAN75%

DBSCAN · Классическое машинное обучение

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

GMM75%

Смесь гауссиан · Классическое машинное обучение

Вероятностная модель: данные порождаются смесью нормальных распределений, параметры оцениваются EM-алгоритмом.

Density Estimation75%

Оценка плотности · Обучение без учителя

Восстановление распределения данных: где объекты встречаются часто, а где почти никогда.

Association Rules75%

Ассоциативные правила · Обучение без учителя

Поиск закономерностей вида «если A, то B» в транзакционных данных.

Silhouette Score75%

Силуэт · Метрики

Сравнивает среднее расстояние объекта до своего кластера и до ближайшего чужого.

Davies–Bouldin75%

Индекс Дэвиса — Болдина · Метрики

Отношение внутрикластерного разброса к расстоянию между кластерами; чем меньше, тем лучше.

Calinski–Harabasz75%

Индекс Калинского — Харабаша · Метрики

Отношение межкластерной дисперсии к внутрикластерной; чем больше, тем лучше разделение.

Mapper75%

Алгоритм Mapper · Топологический анализ данных

Строит граф-скелет данных: проекция фильтрующей функцией, покрытие интервалами, локальная кластеризация и склейка.