Кроме иерархических методов классификации существует группа итеративных методов кластерного анализа. Сущность их заключается в том, что процесс классификации начинается с задания некоторых начальных условий (количество образуемых кластеров, порог завершения процесса классификации и т. д.). Как и в иерархическом кластерном анализе, в итеративных методах существует проблема определения числа кластеров. В общем случае их число может быть неизвестно. Не все итеративные методы требуют первоначального задания числа кластеров, но позволяют используя несколько алгоритмов, меняя либо число образуемых кластеров, либо установленный порог близости для объединения объектов в кластеры добиваться наилучшего разбиения по задаваемому критерию качества.

    К группе итеративных методов принадлежит метод k-средних. Суть метода в следующем.

Пусть имеется n наблюдений, каждое из которых характеризуется p признаками X₁, X₂,..., X_p. Эти наблюдения необходимо разбить на k кластеров. Сначала из n точек исследуемой совокупности отбираются случайным образом или задаются исследователем исходя из каких-либо априорных соображений k точек (объектов). Эти точки принимаются за эталоны. Каждому эталону присваивается порядковый номер, который одновременно является и номером кластера. На первом шаге из оставшихся (n - k) объектов извлекается точка X_i с координатами (x_i1, x_i2, ..., x_ip) и проверяется, к какому из эталонов она находится ближе всего (используется одна из метрик). Эталон заменяется новым, пересчитанным с учетом присоединенной точки, и вес его (количество объектов, входящих в данный кластер) увеличивается на единицу. Если встречаются два или более минимальных расстояния, то i-тый объект присоединяют к центру с наименьшим порядковым номером. На следующем шаге выбирается точка X_i+1 и для нее повторяются все процедуры. Таким образом, через (n - k) шагов все объекты окажутся отнесенными к одному из k кластеров, но на этом процесс разбиения не заканчивается. Что бы добиться устойчивости разбиения по тому же правилу, все объекты X₁, X₂, ..., X_n опять присоединяются к полученным кластерам, при этом веса продолжают накапливаться. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается. В противном случае цикл повторяется. Окончательное разбиение имеет центры тяжести, которые не совпадают с эталонами, их можно обозначать С₁, C₂, ..., C_k. При этом каждая точка X_i (i = 1,2, ..., n) будет относиться к такому кластеру l, для которого

ρ(x_j,c_l) = min ρ(x_j,C_j)

Существуют две модификации метода k - средних. Первая предполагает пересчет центра тяжести кластера после каждого изменения его состава, вторая - лишь после того, как будет завершен просмотр всех данных.

Рассмотрим пример. Сельскохозяйственные предприятия (15 предприятий) сравниваются по двум показателям: растениеводству и животноводству. Значения показателей представлены в таблице.

    Одним из итеративных методов классификации, не требующих задания числа кластеров, является метод поиска сгущений. Метод требует вычисления матрицы расстояний, затем выбирается объект, который является первоначальным центром первого кластера. Выбор такого объекта может быть произвольным, а может основываться на предварительном анализе точек и их окрестностей.

    Выбранная точка принимается за центр гиперсферы заданного радиуса R. Определяется совокупность точек, попавших внутрь этой сферы, и для них вычисляются координаты центра (вектор средних значений признаков). Далее рассматривается гиперсфера такого же радиуса, но с новым центром, и для совокупности попавших в нее точек опять рассчитывается вектор средних значений, который принимается за новый центр сферы и так далее. Когда очередной пересчет координат центра сферы приводит к такому же результату, как на предыдущем шаге, перемещение сферы прекращается, а точки, попавшие в нее, образуют кластер и из дальнейшего процесса кластеризации исключаются. Для всех оставшихся точек процедуры повторяются.