Алгоритм k-means применяется к объектам, которые представляются точками в d-мерном векторном пространстве. Таким образом, это кластеры набора d-мерных векторов, D = {xi|i = 1, . . . , N}, где xi ∈ Rd обозначает i-ый объект или «точку данных». Как уже говорилось во введении, k-means является алгоритмом кластеризации, который разделяет D на k кластеров точек. То есть, алгоритм k-means объединяет все точки данных в D так, что каждая точка xi попадает в один и только один из k разделов. Можно отследить, какая точка находится в каком кластере, назначив каждой точке номер кластера. Точки с таким же номером кластера находятся в одном и том же кластере, в то время как точки с различными номерами кластера находятся в разных кластерах. Это можно обозначить как кластерный составной вектор m длинною N, где miявляется номером кластера xi. Значение k является основным из входных данных алгоритма. Как правило, значение k основано на критериях, таких как предварительное знание о том, сколько на самом деле кластеров появится в D, как много кластеров требуется для текущего приложения, или типы кластеров, найденные путем изучения/экспериментирования с различными значениями k. Неважно, каким образом выбран k, для того чтобы понять, как k-means разделяет набор данных D, и мы обсудим, как выбирать k, когда он не задан, в следующем разделе. В k-means, каждый из k кластеров представлен одной точкой в Rd. Обозначим этот набор представителей кластера как множество С = {сj|j=1, &hell