Введение
Прежде всего, нам нужно понять, какое место K-Means занимает в сфере машинного обучения.
В сфере машинного обучения у нас есть много разных типов алгоритмов. и множество различных вариантов использования (например, классификация, оптимизация, регрессия и многое другое..)
K-Means решает задачу кластеризации: разделяет набор данных на наборы (так называемые кластеры) с похожими объектами.
«Сходство» может быть субъективной темой, но алгоритмы кластеризации пытаются (и преуспевают) измерить сходство по данным наиболее объективным методом.
Основное различие между алгоритмами заключается в «основной правде», которую мы имеем в наших данных, независимо от того, знаем ли мы что-то о наборе данных, может быть, он предварительно помечен, или, может быть, мы ничего не знаем и хотим провести исследовательский анализ данных (EDA).
Следовательно, естественные деления таковы:
- Алгоритмы с учителем: мы что-то знаем о данных и можем отслеживать процесс обучения
- Неконтролируемые алгоритмы: мы ничего не знаем о данных, но хотим их изучить
K-Means – это частичный неконтролируемый алгоритм кластеризации.
Разделение и иерархия:
- Разделение: конечные кластеры представляют собой непересекающиеся наборы.
- Иерархический: конечные кластеры представляют собой вложенные наборы
«K» в K-Means указывает на конечное количество кластеров, например, «3-Means» решает проблему разделения заданного набора на 3 кластера.
Алгоритм K-средних
Первое, что нам нужно установить, это нашу метрику и представление. Чтобы определить похожие объекты, нам нужна мера подобия в некотором пространстве.
Существует несколько часто используемых метрик, таких как евклидово расстояние, расстояние Манхэттена и косинус. подобия.
Мы сосредоточимся на евклидовой метрике (в евклидовом пространстве).
Евклидово пространство — это векторное пространство над действительными числами:
Пусть A будет набором точек, которые мы хотим сгруппировать в K наборов в евклидовом пространстве.
Центроид любого подмножества B ⊆ A:
Процедура K-средних:
- Выберите K точек из A как Исходные семена — начальные центроиды
Каждый центроид представляет 1 из K наборов. - Цикл:
1. Назначьте каждый x в A ближайшему набору центроидов.
2. Пересчитайте центроиды каждого набора. - Конец: центроид не изменился на последней итерации (Конвергенция).
В конце этой процедуры у нас будет K кластеров, удерживающих точки из A.
«Целевая функция» K-средних по евклидову пространству — это «Сумма квадратичных ошибок»:
Алгоритм минимизирует SSE на каждом шаге цикла. Сходимость алгоритма означает, что функция SSE достигла локального минимума.
Плюсы и минусы K-средних:
Плюсы:
— Простота изучения, настройки и обслуживания
– Простота реализации
– Ориентирован на сферические кластеры (для некоторых приложений может быть недостатком)
– Обрабатывает большие наборы данных
Минусы:
- Непоследовательный (зависит от выбора начального начального числа)
- Вход «K», мы должны указать размер кластеров
- Чувствителен к выбросам, особенно если мы выбрали их как первоначальные семена