Алгоритм кластеризации 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/