Алгоритм кластеризации K средних (K-means) является одним из самых популярных методов машинного обучения. Он используется для группировки объектов по сходству, чтобы найти внутри кластеров наиболее похожие объекты и сделать выводы из полученных результатов.
Принцип работы алгоритма K-means заключается в разбиении набора данных на заранее заданное число кластеров и вычислении центров этих кластеров. Каждый объект относится к ближайшему кластеру, а затем снова пересчитываются центры кластеров. Это происходит до тех пор, пока центры кластеров остаются неизменными или изменились меньше, чем на заданную величину.
Формулы и структурные схемы алгоритма K-means:
1. Инициализация: выбор случайных центров кластеров. [1]
2. Начальное разбиение точек на кластеры: каждая точка присваивается ближайшему центру. [1]
3. Вычисление новых центров кластеров: среднее значение всех точек в кластере. [1]
4. Повторение шагов 2-3 до тех пор, пока признаки центров кластеров не перестанут изменяться или их изменения не станут слишком маленькими. [1]
Алгоритм можно описать следующей формулой:
S = argmin θ ∑ i=1:k ∑ x∈C_i ‖ x-θ_i ‖^2
где k - число кластеров, C_i - i-ый кластер, θ_i - центр i-го кластера, ‖ x-θ_i ‖^2 - квадрат евклидова расстояния между точкой x и центром кластера θ_i.
На шаге 1 происходит выбор k случайных точек из набора данных в качестве центров кластеров. На шаге 2 каждая точка относится к ближайшему центру кластера. На шаге 3 вычисляется новый центр кластера путем нахождения среднего значения всех точек в этом кластере. На шаге 4 происходит проверка, изменились ли центры кластеров. Если нет, алгоритм останавливается и возвращается итоговое разбиение. Если центры кластеров изменились, алгоритм повторяется с шага 2.
Пример:
Пусть есть набор данных, состоящий из 6 точек:
[2, 4], [4, 6], [3, 7], [6, 8], [7, 9], [8, 12]
Задано k = 2, то есть нужно разбить данные на 2 кластера.
На первом шаге делаем случайный выбор 2 центров кластеров:
[3, 7], [7, 9]
На втором шаге каждая точка относится к ближайшему центру кластера:
Кластер 1: [2, 4], [4, 6], [3, 7]
Кластер 2: [6, 8], [7, 9], [8, 12]
На третьем шаге вычисляем новые центры каждого кластера:
Кластер 1: [3, 5.67]
Кластер 2: [7, 9.67]
На четвертом шаге осуществляем повторение шагов 2 и 3, пока центры кластеров не перестанут изменяться. В случае с данными примера, на этом шаге алгоритм останавливается, и результатом кластеризации являются два кластера:
Кластер 1: [2, 4], [4, 6], [3, 7]
Кластер 2: [6, 8], [7, 9], [8, 12]
Таким образом, мы разбили исходный набор данных на два кластера походящим друг к другу точкам.
Ссылки:
1. Лекции по машинному обучению Стэнфордского университета
2. Статистика и Data mining: введение в основы K-means: https://habr.com/ru/post/75909/