Введение
Прежде всего, нам нужно понять, какое место 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», мы должны указать размер кластеров
- Чувствителен к выбросам, особенно если мы выбрали их как первоначальные семена