Алгоритм k-means
Конструктивно алгоритм представляет собой итерационную процедуру следующего вида.
1. Задается число кластеров k, которое должно быть сформировано из объектов исходной выборки.
3. Случайным образом выбирается k записей, которые будут служить начальными центрами кластеров. Начальные точки, из которых потом вырастают кластер, часто называют «семенами». Каждая такая запись представляет собой «эмбрион» кластера, состоящий только из одного элемента.
3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера.
4. Производится вычисление центроидов – центров тяжести кластеров. Это делается путем определения среднего для значений каждого признака всех записей в кластере. Например, если в кластер вошли три записи с наборами признаков (x1, y1), (x2, y2), (x3, y3), то координаты его центроида будут рассчитываться следующим образом:
.
Затем старый центр кластера смещается в его центроид. Таким образом, центроиды становятся новыми центрами кластеров для следующей итерации алгоритма.
Шаги 3 и 4 повторятся до тех пор, пока выполнение алгоритма не будет прервано либо пока не будет выполнено условие в соответствии с некоторым критерием сходимости.
Остановка алгоритма производится, когда границы кластеров и расположение центроидов перестают изменяться, то есть на каждой итерации в каждом кластере остается один и тот же набор записей. Алгоритм k-means обычно находит набор стабильных кластеров за несколько десятков итераций.
Рисунок 3.3 – Пример работы алгоритма k-means