Кластер — множества схожих объектов в данных и вычислениях¶

Кластер — в широком смысле это группа однородных или сходных по определённым признакам объектов, объединённых на основе их близости друг к другу и отличия от объектов других групп. Термин происходит от англ. cluster («скопление», «гроздь») и применяется в информатике, математике, биологии, физике, лингвистике, маркетинге и других областях. В вычислительной технике под кластером также понимают объединение нескольких компьютеров, работающих как единая система.

¶Кластерный анализ

Кластерный анализ — это семейство методов статистики и машинного обучения, задача которых — разбить множество объектов на группы (кластеры) так, чтобы объекты внутри группы были максимально похожи между собой, а группы — максимально различались. Кластерный анализ относится к методам обучения без учителя (unsupervised learning): размеченные примеры «правильных» кластеров не задаются, структура обнаруживается в данных автоматически.

Основные типы задач кластеризации:

• Разбиение (partitioning) — разделить данные на заранее заданное число кластеров;
• Иерархическая кластеризация — построение дерева (дендрограммы) вложенных групп, от крупных к мелким;
• Плотностные методы — выделение кластеров как областей повышенной плотности точек;
• Спектральные методы — использование собственных значений матрицы сходства объектов.

¶Основные алгоритмы

K-means (k-средних) — один из наиболее распространённых алгоритмов. Пользователь задаёт число кластеров k; алгоритм итеративно назначает каждой точке ближайший центр кластера (центроид) и пересчитывает центроиды до сходимости. Метод прост и масштабируем, но чувствителен к начальному выбору центров и плохо работает с кластерами сложной формы.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — алгоритм, основанный на плотности. Он объединяет точки, находящиеся в пределах заданного радиуса друг от друга, и способен обнаруживать кластеры произвольной формы, а также помечать выбросы как шум. Число кластеров задавать заранее не нужно.

Агломеративная иерархическая кластеризация — последовательное объединение самых близких пар кластеров до получения одного дерева. Результат удобно представлять в виде дендрограммы, что позволяет выбирать уровень разбиения постфактум.

Метод k-ближайших соседей и алгоритм OPTICS — продолжение линии плотностных методов, улучшающее работу DBSCAN при varying плотности данных.

¶Метрики и оценка качества

Для измерения близости объектов используются евклидово расстояние, косинусное сходство, манхэттенское расстояние и другие метрики. Качество кластеризации оценивается внутренними индексами — например, силуэтом (silhouette), который сравнивает среднее расстояние до объектов своего кластера и до объектов ближайшего соседнего кластера.

¶Кластеры в информатике и телекоммуникациях

В вычислительной технике кластер — это группа из нескольких компьютеров (узлов), связанных сетью и работающих как единая система. Кластеры применяются для повышения отказоустойчивости (когда при отказе одного узла задачу продолжает выполнять другой — это кластер с высокой доступностью) и для масштабирования производительности (распределение нагрузки между узлами — вычислительный кластер). Примеры — кластеры на базе технологий Linux Virtual Server, Beowulf, а также высокопроизводительные вычислительные кластеры в научных центрах.

В базах данных и хранении данных кластеризация означает физическое упорядочивание строк таблицы по ключу: строки с близкими значениями ключа хранятся рядом на диске, что ускоряет диапазонные запросы. Так называемые кластерные индексы определяют физический порядок данных в таблице.

¶Применение кластерного анализа

• Биология и медицина — группировка генов с похожей активностью (анализ экспрессии ДНК-микроматриц), классификация клеток, выявление подтипов заболеваний.
• Естественные языки — кластеризация документов по темам, выделение словесных групп, кластеризация морфологических форм.
• Маркетинг и экономика — сегментация клиентов по поведению и предпочтениям, анализ покупательских корзин.
• География и геоанализз — выявление городских агломераций, анализ пространственных данных.
• Кибербезопасность — обнаружение аномалий и атак путём группировки сетевого трафика.
• Физика — анализ данных столкновений частиках в ускорителях, изучение галактических сверхскоплений.

¶Ограничения

Кластерный анализ не даёт единственно верного разбиения: результат зависит от выбранного алгоритма, метрики расстояния и числа кластеров. Требование заранее задать k в K-means часто обходится эвристиками (метод локтя, силуэт). Кластеризация чувствительна к масштабированию признаков — признаки с большей разницей значений доминируют в расчётном расстоянии, поэтому данные перед обработкой обычно нормализуют.

¶Интересные факты

• Термин «кластерный анализ» ввёл статистик Роберт Tryon в 1939 году в работе по психологической тестологии.
• Понятие «кластерная экономика» ввёл Майкл Портер для описания географической концентрации взаимосвязанных компаний и институтов (Кремниевая долина как пример).

¶Источники

• Хантер А., Деккер Р. Кластерный анализ // Статистические методы в информатике.
• Мандрик О. Е. Кластерный анализ: учебное пособие. — М.: Финансы и статистика.
• Everitt B. S. Cluster Analysis. — Wiley, 2011.
• Tan P.-N., Steinbach M., Kumar V. Introduction to Data Mining. — Pearson, 2016.