Итеративные методы кластерного анализа

Метод k-средних

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

К группе итеративных методов принадлежит метод 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 предприятий) сравниваются по двум показателям: растениеводству и животноводству. Значения показателей представлены в таблице [3, с.165].

Проведем кластеризацию предприятий используя метод k-средних используя в качестве метрики квадрат евклидова расстояния. Зададим количество кластеров равное трем. Результат кластеризации средствами «Statgraphics» представлен графиком.

Необходимо еще раз напомнить об обязательной нормализации исходных данных. Ниже приведен график кластеризации методом k-средних без нормализации исходных данных.

Обратим внимание — размер и состав кластеров в этом случае резко отличается от результата правильной кластеризации.

Вычислительные процедуры большинства итеративных методов классификации сводятся к выполнению следующих действий:

• 1. Выбор числа кластеров, на которые должна быть разбита совокупность, задание первоначального разбиения объектов и определение центров тяжести кластеров.
• 2. В соответствии с выбранными мерами близости определение нового состава каждого кластера.
• 3. После полного просмотра всех объектов и распределения их по кластерам осуществляется пересчет центров тяжести кластеров.

Шаги 2 и 3 повторяются до тех пор, пока следующая итерация не даст такой же состав кластеров, что и предыдущая.

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