--- title: Кластеризация seo: title: Кластеризация — Data Scientist description: Тема «Кластеризация» для собеседования Data Scientist. Что такое кластеризация? Какие методы кластеризации вы знаете? --- [Все темы Data Scientist](/data-scientist) ## Что такое кластеризация? [#q-14bee738d69b816da56ecd571a5b0de6] Кластеризация - это задача машинного обучения, направленная на разделение набора данных на группы или кластеры объектов, которые имеют схожие характеристики или поведение. Основная цель кластеризации состоит в том, чтобы найти скрытую структуру в данных и сгруппировать объекты таким образом, чтобы объекты внутри кластера были более похожи друг на друга, чем на объекты из других кластеров. Кластеризация является методом без учителя, что означает отсутствие меток или заранее определенных категорий для объектов данных. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Какие методы кластеризации вы знаете? [#q-14bee738d69b8156a32ee9905cf4ffea] Основные методы кластеризации: 1. K-средних (K-means): Разбивает набор данных на заранее заданное количество кластеров, минимизируя сумму квадратов расстояний между точками и центроидами кластеров. 1. Иерархическая кластеризация (Hierarchical clustering): Строит древовидную структуру кластеров, объединяя или разделяя кластеры на основе близости объектов. 1. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) : Определяет кластеры как области высокой плотности объектов, разделенные областями низкой плотности. 1. Агломеративная кластеризация (Agglomerative clustering): Начинает с отдельных объектов как отдельных кластеров и последовательно объединяет их в более крупные кластеры. 1. Спектральная кластеризация (Spectral clustering): Использует спектральное представление графа данных для выделения кластеров. 1. Mean Shift: Определяет кластеры как области вокруг локальных максимумов плотности данных. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Для чего может использоваться кластеризация? [#q-14bee738d69b811ebb6bc3957a955a72] Кластеризация может использоваться для: 1. Анализа данных: Позволяет выявить скрытые структуры и группировки в данных, что помогает понять их характеристики и взаимосвязи. 1. Сегментации рынка: Помогает разделить клиентов, товары или услуги на группы схожих характеристик для более точного таргетирования рекламы и маркетинговых стратегий. 1. Классификации: Может использоваться для предварительной обработки данных перед классификацией, основанной на метках, или для создания новых признаков. 1. Анализа изображений: Помогает группировать и классифицировать изображения на основе их содержимого или характеристик, таких как цвета и текстуры. 1. Обработки естественного языка: Используется для кластеризации текстовых данных, например, для группировки документов по темам или стилям. 1. Поиска аномалий: Позволяет выявить необычные или аномальные объекты, которые отличаются от общего паттерна данных. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Какова алгоритмическая сложность k-Nearest Neighbors (kNN)? [#q-14bee738d69b81658029ea3111daee94] Алгоритмическая сложность k-Nearest Neighbors (kNN) зависит от количества объектов в обучающем наборе данных и количества соседей, которые необходимо найти. 1. Подготовка: kNN хранит обучающие данные, а при выборе KD-tree или Ball-tree дополнительно строит индекс. Оптимизации весов нет, но время fit не равно нулю. 1. Предсказание прямым перебором: вычисление расстояний до n объектов с d признаками стоит O(nd). Выбор k соседей добавляет затраты, например O(n log k) с кучей; полная сортировка требует O(n log n). Итог зависит от алгоритма поиска, размерности и числа запросов. Деревья могут ускорять поиск в малой размерности, но универсальной сложности O(n log k) для всех вариантов kNN нет. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Как обрабатывать пропуски? [#q-14bee738d69b81c09dfdecec201d5bfd] Обработка пропусков в кластеризации включает следующие шаги: 1. Удаление пропущенных значений: Исключение объектов с пропущенными значениями из анализа может быть вариантом, если количество пропусков невелико и не существенно для общего объема данных. 1. Замена на среднее/медианное значение: Пропущенные значения можно заменить на среднее или медианное значение по соответствующему признаку. 1. Использование алгоритмов заполнения пропусков: Методы, такие как k-ближайших соседей или алгоритмы заполнения пропущенных значений на основе регрессии, могут быть использованы для заполнения пропущенных значений. 1. Использование моделей машинного обучения для заполнения пропусков : Можно обучить модель машинного обучения (например, случайный лес или градиентный бустинг) на имеющихся данных и использовать ее для предсказания пропущенных значений. 1. Использование специальных значений: Пропущенные значения можно заменить специальными значениями, такими как "unknown" или "-1", если это имеет смысл в контексте задачи. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Сравните методы класстеризации. [#q-14bee738d69b818faf40d269a5bd1ce4] Вот краткое сравнение основных методов кластеризации: {/* prettier-ignore */} 1. K-means: - Один из самых популярных и простых методов кластеризации. - Работает на основе центроидов, которые представляют собой средние значения объектов в кластере. - Хорошо работает на больших наборах данных. - Чувствителен к начальным значениям центроидов. 1. Иерархическая кластеризация: - Строит дерево кластеров (дендрограмму), где каждый узел представляет собой кластер, а ребра представляют сходство между кластерами. - Не требует заранее определенного числа кластеров. - Подходит для небольших и средних наборов данных. 1. DBSCAN (Плотностная основанная кластеризация приложений с шумом): - Идентифицирует кластеры на основе плотности точек. - Способен обрабатывать кластеры произвольной формы и шум в данных. - Не требует заранее определенного числа кластеров. - Чувствителен к параметрам радиуса и минимального числа точек. 1. Mean Shift: - Находит локальные максимумы плотности данных (peak points) и считает их центры как центры кластеров. - Не требует заранее определенного числа кластеров. - Может работать с кластерами произвольной формы. - Чувствителен к параметру сглаживания (bandwidth). :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) ::: --- ## Каковы плюсы и минусы kNN? Как ускорить поиск соседей с помощью ANN (approximate nearest neighbours)? [#q-14bee738d69b81e2aaccc707470af1f5] kNN (k-Nearest Neighbors): Плюсы: 1. Прост в реализации и понимании. 1. Не требует обучения, что делает его хорошим выбором для начальной оценки данных. 1. Хорошо подходит для многих типов данных, включая нелинейные и неструктурированные данные. Минусы: 1. Чувствителен к масштабированию признаков. 1. Требует хранения всего набора данных в памяти. 1. Низкая эффективность на больших наборах данных из-за вычислительной сложности поиска ближайших соседей. 1. Неэффективен для данных с большим количеством признаков. АНН (Approximate Nearest Neighbors): 1. Метод локально-чувствительных хэшей (Locality-Sensitive Hashing, LSH) : Алгоритм, который преобразует объекты в хэши таким образом, чтобы похожие объекты имели схожие хэши, что ускоряет поиск ближайших соседей. 1. Методы приближенного поиска ближайших соседей (Approximate Nearest Neighbor Search) : Используются для быстрого поиска ближайших соседей с небольшой потерей точности. Примеры включают в себя методы ближайших соседей с приближенными структурами данных, такие как k-d trees и ball trees. :::note[Ссылки для изучения] 1. [Кластеризация в ML](https://education.yandex.ru/handbook/ml/article/klasterizaciya) :::