Кластеризация: алгоритмы k-means и c-means
Как и обещал, продолжаю серию публикаций о технологии Data Mining. Сегодня хочу рассказать о двух алгоритмах кластеризации (k-means и c-means), описать преимущества и недостатки, дать некоторые рекомендации по их использованию. Итак, поехали…
Кластеризация — это разделение множества входных векторов на группы (кластеры) по степени «схожести» друг на друга.
Кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию (Википедия).
Меры расстояний
Для того, чтобы сравнивать два объекта, необходимо иметь критерий, на основании которого будет происходить сравнение. Как правило, таким критерием является расстояние между объектами.
Есть множество мер расстояния, рассмотрим несколько из них:
Евклидово расстояние — наиболее распространенное расстояние. Оно является геометрическим расстоянием в многомерном пространстве.
Квадрат евклидова расстояния. Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам.
Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат).
Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как «различные», если они различаются по какой-либо одной координате (каким-либо одним измерением).
Степенное расстояние. Иногда желают прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Это может быть достигнуто с использованием степенного расстояния.
Выбор расстояния (критерия схожести) лежит полностью на исследователе. При выборе различных мер результаты кластеризации могут существенно отличаться.
Алгоритм k-means (k-средних)
Наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.
Проблемы алгоритма k-means:
* необходимо заранее знать количество кластеров. Мной было предложено метод определения количества кластеров, который основывался на нахождении кластеров, распределенных по некоему закону (в моем случае все сводилось к нормальному закону). После этого выполнялся классический алгоритм k-means, который давал более точные результаты.
* алгоритм очень чувствителен к выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор класторов, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров. В моем случае на начальном этапе предлагается принимать в качестве центов самые отдаленные точки кластеров.
* не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному.
Нечеткий алгоритм кластеризации с-means
С последней проблемой k-means успешно справляется алгоритм с-means. Вместо однозначного ответа на вопрос к какому кластеру относится объект, он определяет вероятность того, что объект принадлежит к тому или иному кластеру. Таким образом, утверждение «объект А принадлежит к кластеру 1 с вероятностью 90%, к кластеру 2 — 10% » верно и более удобно.
Классический пример с-means — т.н. «бабочка» (butterfly):
Как видно, точка с координатами (3,2) в равной степени принадлежит как первому так и второму кластеру.
Остальные проблемы у с-means такие же, как у k-means, но они нивелируются благодаря нечеткости разбиения.
Алгоритм k средних (k-means)
Алгоритм k средних (англ. k-means) — один из алгоритмов машинного обучения, решающий задачу кластеризации. Этот алгоритм является неиерархическим [1] , итерационным методом кластеризации [2] , он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом [3] и почти одновременно Стюартом Ллойдом [4] . Особую популярность приобрел после публикации работы МакКуина [5] в 1967.
Алгоритм представляет собой версию EM-алгоритма [6] , применяемого также для разделения смеси гауссиан. Основная идея алгоритма k-means заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
Цель алгоритма заключается в разделении [math]n[/math] наблюдений на [math]k[/math] кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.
1.2 Математическое описание алгоритма
- набор из [math]n[/math] наблюдений [math]X=\<\mathbf
_1, \mathbf _2, . \mathbf _n\>, \mathbf _i \in \mathbb ^d, \ i=1. n[/math] ; - [math]k[/math] — требуемое число кластеров, [math]k \in \mathbb
, \ k \leq n[/math] .
Разделить множество наблюдений [math]X[/math] на [math]k[/math] кластеров [math]S_1, S_2, . S_k[/math] :
- [math]S_i \cap S_j= \varnothing, \quad i \ne j[/math]
- [math]\bigcup_
S_i = X[/math]
Действие алгоритма:
Алгоритм k-means разбивает набор [math]X[/math] на [math]k[/math] наборов [math]S_1, S_2, . S_k,[/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра (центр масс кластера). Введем обозначение, [math]S=\
| [math]\arg\min_ |
[math](1)[/math] |
где [math]\mathbf<\mu>_i[/math] – центры кластеров, [math]i=1. k, \quad \rho(\mathbf
Шаги алгоритма:
-
Начальный шаг: инициализация кластеров
Выбирается произвольное множество точек [math]\mu_i, \ i=1. k,[/math] рассматриваемых как начальные центры кластеров: [math]\mu_i^ <(0)>= \mu_i, \quad i=1. k[/math]
Шаг [math]t: \forall \mathbf
Шаг [math]t: \forall i=1. k: \mu_i^ <(t)>= \cfrac<1><|S_i|>\sum_<\mathbf
- if [math]\exists i\in \overline<1,k>: \mu_i^ <(t)>\ne \mu_i^<(t-1)>[/math] then
- [math]t = t + 1[/math] ;
- goto 2;
- stop
1.3 Вычислительное ядро алгоритма
Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.
Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]\mathbf
_i \in X, \ i= 1. n[/math] и центрами кластера [math]\mathbf<\mu>_j, \ j= 1. k[/math] . Таким образом, данный шаг предполагает [math]kn[/math] вычислений расстояний между [math]d[/math] -мерными векторами. Пересчет центров кластеров предполагает [math]k[/math] вычислений центров масс [math]\mathbf<\mu>_i[/math] множеств [math]S_i, \ i=1. k,[/math] представленных выражением в шаге 3 представленного выше алгоритма.
1.4 Макроструктура алгоритма
Инициализация центров масс [math]\mu_1, . \mu_k[/math] .
Наиболее распространенными являются следующие стратегии:
- Метод Forgy
В качестве начальных значений [math]\mu_1, . \mu_k[/math] берутся случайно выбранные векторы. - Метод случайно разделения (Random Partitioning)
Для каждого вектора [math]\mathbf_i \in X, \ i=1. n,[/math] выбирается случайным образом кластер [math]S_1, . S_k[/math] , после чего для каждого полученного кластера вычисляются значения [math]\mu_1, . \mu_k[/math] .
Распределение векторов по кластерам
Для этого шага алгоритма между векторами [math]\mathbf
_i \in X, \ i=1. n,[/math] и центрами кластеров [math]\mu_1. \mu_k[/math] вычисляются расстояния по формуле (как правило, используется Евлидово расстояние): [math] \mathbf _1, \mathbf _2 \in \mathbb ^d, \quad \rho(\mathbf _1, \mathbf _2) = \lVert \mathbf _1- \mathbf _2 \rVert= \sqrt<\sum_ (\mathbf _ <1,i>— \mathbf _<2,i>)^2>[/math] [math](2)[/math] Пересчет центров кластеров
Для этого шага алгоритма производится пересчет центров кластера по формуле вычисления центра масс:
[math] \mu = \cfrac<1><|S|>\sum_<\mathbf \in S>\mathbf [/math] [math](3)[/math] 1.5 Схема реализации последовательного алгоритма
1. Инициализировать центры кластеров [math]\mathbf<\mu>_i^<(1)>, \ i=1. k[/math]
2. [math]t \leftarrow 1[/math]
3. Распределение по кластерам
[math]\quad S_i^<(t)>=\<\mathbf_p: \lVert\mathbf _p-\mathbf<\mu>_i^<(t)>\rVert^2 \leq \lVert\mathbf _p-\mathbf<\mu>_j^<(t)>\rVert^2 \quad \forall j=1. k\>,[/math]
[math]\quad[/math] где каждый вектор [math]\mathbf_p[/math] соотносится единственному кластеру [math]S^<(t)>[/math]
4. Обновление центров кластеров
[math]\quad \mathbf<\mu>_i^ <(t+1)>= \frac<1><|S^<(t)>_i|> \sum_<\mathbf_j \in S^<(t)>_i> \mathbf _j [/math]
5. if [math]\exists i \in \overline<1,k>: \mathbf<\mu>_i^ <(t+1)>\ne \mathbf<\mu>_i^<(t)>[/math] then
[math]\quad t = t + 1[/math] ;
[math]\quad[/math] goto 3;
[math][/math] else
[math]\quad[/math] stop1.6 Последовательная сложность алгоритма
Обозначим [math]\Theta_<\rm centroid>^
Аналогично [math]\Theta_<\rm distance>^d[/math] – временная сложность вычисления расстояния между двумя d-мерными векторами.
Сложность шага инициализации [math]k[/math] кластеров мощности [math]m[/math] в d-мерном пространстве – [math]\Theta_<\rm init>^
- Стратерия Forgy: вычисления не требуются, [math]\Theta_<\rm init>^
- Стратегия случайного разбиения: вычисление центров [math]k[/math] кластеров, [math]\Theta_<\rm init>^
Cложность шага распределения d мерных векторов по [math]k[/math] кластерам – [math]\Theta_<\rm distribute>^
На этом шаге для каждого вектора [math]\mathbf
_i \in X, \ i=1. n,[/math] вычисляется [math]k[/math] расстояний до центров кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math] Сложность шага пересчета центров [math]k[/math] кластеров размера [math]m[/math] в d-мерном пространстве – [math]\Theta_<\rm recenter>^
На этом шаге вычисляется [math]k[/math] центров кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math]
Рассчитаем [math]\Theta_<\rm centroid>^
[math]\Theta_<\rm centroid>^
Рассчитаем [math]\Theta_<\rm distance>^d[/math] в соответствие с формулой [math](2)[/math]
[math]\Theta_<\rm distance>^d[/math] = [math]d[/math] вычитаний + [math]d[/math] умножений + [math](d-1)[/math] сложение
Предположим, что алгоритм сошелся за [math]i[/math] итераций, тогда временная сложность алгоритма [math]\Theta_<\rm k-means>^
[math]\Theta_<\rm k-means>^
[math]\Theta_<\rm k-means>^
Получаем, что временная сложность алгоритма k-means кластеризации [math]n[/math] d-мерных векторов на [math]k[/math] кластеров за [math]i[/math] итераций:
[math] \Theta_<\rm k-means>^
1.7 Информационный граф
Рассмотрим информационный граф алгоритма. Алгоритм k-means начинается с этапа инициализации, после которого следуют итерации, на каждой из которых выполняется два последовательных шага (см. «Схема реализации последовательного алгоритма»):
- распределение векторов по кластерам
- перерасчет центров кластеров
Поскольку основная часть вычислений приходится на шаги итераций, распишем информационные графы данных шагов.
Распределение векторов по кластерам
Информационный граф шага распределения векторов по кластерам представлен на рисунке 1. Исходами данного графа является исходные векторы [math]\mathbf
_1, . \mathbf _n[/math] , а также центры кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math] , вычисленные ранее (на шаге инициализации, если рассматривается первая итерация алгоритма, или на шаге пересчета центров кластеров предыдущей итерации в противном случае). Каждая пара векторов данных [math]\mathbf _i, \ i=1. n,[/math] и центров кластера [math]\mathbf<\mu>_j, \ j=1. k[/math] : ( [math]\mathbf _i[/math] , [math]\mathbf<\mu>_j[/math] ) подаются на независимые узлы «d» вычисления расстояния между векторами (более подробная схема вычисления расстояния представлена далее, рисунок 2). Далее узлы вычисления расстояния «d», соответствующие одному и тому же исходному вектору [math]\mathbf _i[/math] передаются на один узел «m», где далее происходит вычисление новой метки кластера для каждого вектора [math]\mathbf _i[/math] (берется кластер с минимальным результатом вычисления расстояния). На выходе графа выдаются метки кластеров , [math]L_1, . L_n[/math] , такие что [math]\forall \mathbf _i, \ i=1. n, \ \mathbf _i \in S_j \Leftrightarrow L_i = j[/math] . 
Вычисление расстояния между векторами
Подробная схема вычисления расстояния между векторами [math]\mathbf
_i, \mathbf<\mu>_j[/math] представлена на рисунке 2. Как показано на графе, узел вычисления расстояния между векторами «d» состоит из шага взятия разности между векторами (узел » [math]-[/math] «) и взятия нормы получившегося вектора разности (узел » [math]||\cdot||^2[/math] «). Более подробно, вычисление расстояния между векторами [math]\mathbf _i = , . \mu_ >[/math] может быть представлено как вычисление разности между каждой парой компонент [math](x_ , \mu_ ), \ z=1. d[/math] (узел » [math]-[/math] «), далее возведение в квадрат для каждого узла » [math]-[/math] » (узел » [math]()^2[/math] «) и суммирования выходов всех узлов » [math]()^2[/math] » (узел » [math]+[/math] «). 
Пересчет центров кластеров
Информационный граф шага пересчета центров кластеров представлен на рисунке 3. Исходами данного графа является исходные векторы [math]\mathbf
_1, . \mathbf _n[/math] , а также им соответствующие метки кластера, [math]L_1, . L_n[/math] , такие что [math]\forall x_i, \ i=1. n, \ \mathbf _i \in S_j \Leftrightarrow L_i = j[/math] , вычисленные на этапе распределения векторов по кластерам. Все векторы [math]\mathbf _1, . \mathbf _n[/math] подаются в узлы [math]+_1, . +_k[/math] , каждый узел [math]+_m, \ m = 1. k,[/math] соответствует операции сложения векторов кластера с номером [math]m[/math] . Метки кластера [math]L_1, . L_n[/math] также совместно передаются на узлы [math]S_m, \ m=1. k[/math] , на каждом из которых вычисляется количество векторов в соответствующем кластере (количество меток с соответствующим значением). Далее каждая пара выходов узлов [math]+_m[/math] и [math]S_m[/math] подается на узел » [math]/[/math] «, где производится деление суммы векторов кластера на количество элементов в нем. Значения, вычисленные на узлах » [math]/[/math] «, присваиваются новым центрам кластеров (выходные значения графа). 
1.8 Ресурс параллелизма алгоритма
Работа алгоритма состоит из [math]i[/math] итераций, в каждой из которых происходит распределение [math]d[/math] -мерных векторов по [math]k[/math] кластерам, а также пересчет центров кластеров в [math]d[/math] -мерном пространстве. В шаге распределения [math]d[/math] -мерных векторов по [math]k[/math] кластерам расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). Центры масс кластеров также пересчитываются независимо друг от друга. Таким образом, имеет место массовый параллелизм. Вычислим параллельную сложность [math]\Psi_*[/math] каждого из шагов, а также параллельную сложность всего алгоритма, [math]\Psi_<\rm k-means>[/math] . Будем исходить из предположения, что может быть использовано любое необходимое число потоков.
Распределение [math]d[/math] -мерных векторов по [math]k[/math] кластерам
Поскольку на данном шаге для каждой пары векторов [math]\mathbf
_i, \ i=1. n[/math] и [math]\mathbf<\mu>_j, \ j=1. k,[/math] операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на [math]n[/math] потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности [math]d[/math] . При этом каждому вычислительному потоку передаются координаты центров всех кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math] . Таким образом, параллельная сложность данного шага определяется сложностью параллельной операции вычисления расстояния между [math]d[/math] -мерными векторами, [math]\Psi_<\rm distance>^d[/math] и сложностью определения наиболее близкого кластера (паралельное взятие минимума по расстояниям), [math]\Psi_<\rm min>^k[/math] . Для оценки [math]\Psi_<\rm distance>^d[/math] воспользуемся параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания. Аналогично, [math]\Psi_<\rm min>^k = \log(k)[/math] . В результате, [math]\Psi_<\rm distance>^d = O(\log(d))[/math] . Таким образом: Пересчет центров кластеров в d-мерном пространстве
Поскольку на данном шаге для каждого из [math]k[/math] кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, [math]\Psi_<\rm recenter>^
Общая параллельная сложность алгоритма
На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно [7] . Тогда, поскольку сложность каждой итерации определяется [math]\Psi_<\rm distribute>^
1.9 Входные и выходные данные алгоритма
Входные данные
- Матрица из [math]n \cdot d[/math] элементов [math]x_
, \ i=1. n, \ j=1. d,[/math] – координат векторов (наблюдений). - Целое положительное число [math]k, \ k \le n[/math] – количество кластеров.
Объем входных данных
[math]1[/math] целое число + [math]n \cdot d[/math] вещественных чисел (при условии, что координаты – вещественные числа).Выходные данные
[math]n[/math] целых положительных чисел [math]L_1, . L_n[/math] – номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с [math]1[/math] ).Объем выходных данных
[math]n[/math] целых положительных чисел.1.10 Свойства алгоритма
Вычислительная мощность алгоритма k-means равна [math]\frac
= ki [/math] , где [math]k[/math] – число кластеров, [math]i[/math] – число итераций алгоритма. Алгоритм k-means является итерационным. Количество итераций алгоритма в общем случае не фиксируется и зависит от начального расположения объектов в пространстве, параметра [math]k[/math] , а также от начального приближения центров кластеров, [math]\mu_1, . \mu_k[/math] . В результате этого может варьироваться результат работы алгоритма. При неудачном выборе начальных параметров итерационный процесс может сойтись к локальному оптимуму [8] . По этим причинам алгоритм не является ни детермирированным, ни устойчивым.
Соотношение последовательной и параллельной сложности алгоритма
Сильные стороны алгоритма:
- Сравнительно высокая эффективность при простоте реализации
- Высокое качество кластеризации
- Возможность распараллеливания
- Существование множества модификаций
Недостатки алгоритма [9] :
-
Количество кластеров является параметром алгоритма
Чувствительность к начальным условиям
Инициализация центров кластеров в значительной степени влияет на результат кластеризации.
Чувствительность к выбросам и шумам
Выбросы, далекие от центров настоящих кластеров, все равно учитываются при вычислении их центров.
Возможность сходимости к локальному оптимуму
Итеративный подход не дает гарантии сходимости к оптимальному решению.
Использование понятия «среднего»
Алгоритм неприменим к данным, для которых не определено понятие «среднего», например, категориальным данным.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
В настоящем разделе проведено исследование масштабируемости различных параллельных реализации алгоритма [math]k[/math] средних согласно методике AlgoWiki.
2.4.1 Реализация 1
Исследование масштабируемости параллельной реализации алгоритма k-means проводилось на суперкомпьютере «Ломоносов» [10] Суперкомпьютерного комплекса Московского университета. Алгоритм реализован на языке C с использованием средств MPI. Для исследования масштабируемости проводилось множество запусков программы с разным значением параметра (количество векторов для кластеризации), а также с различным числом процессоров. Фиксировались результаты запусков – время работы [math]t[/math] и количество произведенных итераций алгоритма [math]i[/math] .
Параметры запусков для экспериментальной оценки:
- Значения количества векторов [math]n[/math] : 20’000, 30’000, 50’000, 100’000, 200’000, 300’000, 500’000, 700’000, 1’000’000, 1’500’000, 2’000’000.
- Значения количества процессоров [math]p[/math] : 1, 8, 16, 32, 64, 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512.
- Значение количества кластеров [math]k[/math] : 100.
- Значение размерности векторов [math]d[/math] : 10.
Для проведения экспериментов были сгенерированы нормально распределенные псевдослучайные данные (с использованием Python библиотеки scikit-learn):
Для заданной конфигурации эксперимента ( [math]n, d, p, k[/math] ) и полученных результатов ( [math]t, i[/math] ) производительность и эффективность реализации расчитывались по формулам:
- [math] <\rm Performance>= \frac
\ \ (<\rm FLOPS>),[/math]
где [math]N_<\rm k-means>^
- [math] <\rm Efficiency>= \frac<100 \cdot <\rm Performance>><<\rm Performance>_<\rm Peak>^
>\ \ (\%),[/math]
где [math]<\rm Performance>_<\rm Peak>^
[/math] – пиковая производительность суперкомпьютера при [math]p[/math] процессорах, вычисленная согласно спецификациям Intel ® XEON ® X5670 [11] .
Графики зависимости производительности и эффективности параллельной реализации k-means от числа векторов для кластеризации ( [math]n[/math] ) и числа процессоров ( [math]p[/math] ) представлены на рисунках 4 и 5, соответственно.
Метод k-средних (K-means)
Метод k-средних используется для кластеризации данных на основе алгоритма разбиения векторного пространства на заранее определенное число кластеров k . Алгоритм представляет собой итерационную процедуру, в которой выполняются следующие шаги:
- Выбирается число кластеров k .
- Из исходного множества данных случайным образом выбираются k наблюдений, которые будут служить начальными центрами кластеров.
- Для каждого наблюдения исходного множества определяется ближайший к нему центр кластера (расстояния измеряются в метрике Евклида). При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
- Вычисляются центроиды — центры тяжести кластеров. Каждый центроид — это вектор, элементы которого представляют собой средние значения соответствующих признаков, вычисленные по всем записям кластера.
- Центр кластера смещается в его центроид, после чего центроид становится центром нового кластера.
- 3-й и 4-й шаги итеративно повторяются. Очевидно, что на каждой итерации происходит изменение границ кластеров и смещение их центров. В результате минимизируется расстояние между элементами внутри кластеров и увеличиваются междукластерные расстояния.
Остановка алгоритма производится тогда, когда границы кластеров и расположения центроидов не перестанут изменяться от итерации к итерации, т.е. на каждой итерации в каждом кластере будет оставаться один и тот же набор наблюдений. На практике алгоритм обычно находит набор стабильных кластеров за несколько десятков итераций.
Преимуществом алгоритма являются скорость и простота реализации. К недостаткам можно отнести неопределенность выбора начальных центров кластеров, а также то, что число кластеров должно быть задано изначально, что может потребовать некоторой априорной информации об исходных данных.
Существуют методы кластеризации, которые можно рассматривать как происходящие от k-средних. Например, в методе k-медиан (k-medians) для вычисления центроидов используется не среднее, а медиана, что делает алгоритм более устойчивым к аномальным значениям в данных.
Алгоритм g-средних (от gaussian) строит кластеры, распределение данных в которых стремится к нормальному (гауссовскому) и снимает неопределенность выбора начальных кластеров. Алгоритм C-средних использует элементы нечеткой логики, учитывая при вычислении центроидов не только расстояния, но и степень принадлежности наблюдения к множеству объектов в кластере. Также известен алгоритм Ллойда, который в качестве начального разбиения использует не множества векторов, а области векторного пространства.
Идея метода k-средних была одновременно сформулирована Гуго Штейнгаузом и Стюартом Ллойдом в 1957 г. Сам термин «k-средних» был впервые введен Дж. Маккуинном в 1967 г.