Кластеризация: что это такое? Когда это использовать?

Машинное обучение, Data Science

Кластеризация: что это такое и когда ее использовать?

Полное руководство по K-средним, K-средним ++ и DBSCAN.

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

Таблица содержания

1. К-средние

⦁ Знакомство с K-means

⦁ Как работают K-средства?

⦁ Научно-техническая реализация K-means

⦁ Плюсы и минусы K-средних

2. K-средство ++

⦁ Как работает k-means ++?

⦁ Научно-техническая реализация K-means ++

3. DBSCAN

Как работает DBSCAN?
Псевдокод для DBSCAN
Научная реализация DBSCAN
Плюсы и минусы DBSCAN

K-средние

Введение в K-means

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

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

Иногда нам просто нужно систематизировать данные, и тут в игру вступает кластеризация. Его можно использовать как для помеченных, так и для немаркированных данных.

Все слышали о Netflix и его нескончаемой компиляции контента.

Контент хорошо организован по разным жанрам, таким как комедия, драма, триллер и т. Д.

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

Это концепция кластеризации, объединяющая все точки сопутствующих данных в кластер для лучшего и каталогизированного опыта.

Именно так работает K-means.

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

Алгоритм K-средних является частью жесткой кластеризации, что соответствует тому, что каждая точка принадлежит только одному кластеру.

Как работают К-средства?

«К» в К-средних обозначает количество кластеров. Этот алгоритм должен сходиться к решению после нескольких итераций.

Цель: разделить данные между некоторым количеством «K» кластеров.

Инициализировать K-точки.
Классифицируйте каждый элемент по ближайшему среднему значению.
Обновите координаты среднего значения, которое является средним для элементов, категоризированных на данный момент в среднем.
Повторяйте вышеуказанные шаги, пока наш алгоритм не сойдется.

Функция стоимости:

где m = все точки

K = все кластеры

wik = 1 для точки данных, если ith принадлежит кластеру k;

в противном случае wik = 0.

Чтобы минимизировать потери, мы реализуем координатный спуск. Потери, встречающиеся в K-средних, не являются выпуклой функцией, поэтому может быть несколько локальных минимумов.

Это задача минимизации, состоящая из двух частей:

Сначала мы минимизируем J w.r.t. wik и лечить μk исправлено. Затем мы минимизируем J относительно μk и лечить wik исправлено.

E-step: мы различаем J по сравнению с другими. сначала wik и обновите назначения кластера (E-step).

Мы назначаем точку данных xi ближайшему кластеру, оцениваемому по его евклидову расстоянию от центроида кластера.

2. M-шаг: Затем мы дифференцируем J по сравнению с μk и повторно вычислите центроиды после кластерных назначений из предыдущего шага.

Вкратце, сначала мы получим wik, используя E-step, и он классифицирует точку как 0 или 1. Если wik = 1, мы перейдем к M-step и, используя μk, мы получим среднее значение всех точек, чтобы получить обновленный кластерный центр.

Научная реализация K-means

Чтобы указать количество кластеров, есть два метода:

Прямой метод: просто нанесите точки данных и посмотрите, подскажет ли он.
Значение инерции. Идея хорошей кластеризации заключается в небольшом значении инерции и небольшом количестве кластеров.

Величина инерции обратно пропорциональна количеству кластеров. Итак, здесь есть компромисс. Практическое правило: точка изгиба на графике инерции является оптимальным выбором, поскольку после этого изменение значения инерции не имеет значения.

Плюсы и минусы K-means

Плюсы:

Легко реализовать.
Масштабируемость для больших данных
Обеспечьте конвергенцию.

Минусы:

Чувствителен к выбросам.
Выбор количества кластеров - утомительная работа.
Инициализация случайная.
Не подходит для нелинейных данных.

K-означает ++

Введение в K-means ++

K-means ++ - это расширенный вариант K-means. Недостатком метода K-средних было то, что он использовал метод случайной инициализации, который часто приводит к неработоспособному алгоритму, поскольку после случайного выбора центроидов существует высокий риск попадания в локальные минимумы. .

K-средство ++ избегает этого препятствия, выбирая центроиды, которые статистически близки к реальным центрам.

Sci-kit learn по умолчанию использует k-means ++.

Реализация Sci-kit для K-means ++

Но K-means ++ по-прежнему не подходит для нелинейных точек данных.

DBSCAN (Пространственная кластеризация приложений с шумом на основе плотности)

Введение в DBSCAN

DBSCAN - это решение для кластеризации нелинейных точек данных.

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

Он начинается с исследования небольшой области, если плотность этой области «достаточно приличная», она рассматривается как часть кластера и исследует соседей, чтобы увеличить пространственную область кластера.

Работает по одному правилу: если расстояние соседа ‹пороговое расстояние, то оно добавляется в семейство.

Псевдокод для DBSCAN

Найдите все соседние точки в eps и для каждой неназначенной точки ядра создайте новый кластер.
Рекурсивно найдите все точки, связанные плотностью, и добавьте их в тот же кластер, что и центральная точка (центроид).
Повторите процесс для неназначенного соседа.

Реализация Sci-kit

Допустимые параметры:

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

minPoints: минимальное количество точек для образования плотной области, например если мы установим для параметра minPoints значение 8, то нам понадобится как минимум 8 точек, чтобы сформировать плотную область (кластер).

Плюсы и минусы DBSCAN

Плюсы DBSCAN:

Отлично подходит для разделения кластеров с высокой плотностью от кластеров с низкой плотностью в пределах заданного набора данных.
Менее чувствителен к выбросам.

Минусы DBSCAN: