Этап 4. Выбор мер сходства и формирование групп сходных объектов.

В кластерном анализе объекты представляются точками в координатном пространстве. Размерность пространства определяется числом переменных, используемых для описания объектов. Сходство и различие между точками находятся в соответствии с расстояниями между ними. Считается, что чем меньше расстояние между объектами, тем более схожи они между собой.

Существует большое количество разновидностей методов определения расстояний. Для количественных переменных наиболее часто используется евклидово расстояние:

Квадрат эвклидова расстояния:

X, Y - объекты

Х₁, Х₂, Х₃ … Х_m

Значения переменных 1, 2 … m для объектов X и Y

Y₁, Y₂, Y₃ … Y_m

Для дихотомических переменных используются меры, основанные на частотах, отражающих возможные сочетания значения двух признаков:

Евклидово расстояние:

Квадрат евклидова расстояния:

Разность длин:

Существует множество алгоритмов, с помощью которых происходит формирование групп схожих объектов. Разработанные кластерные методы образуют семь основных семейств:

- Иерархические агломеративные методы;

- Итеративные методы группировки;

- Иерархические дивизимные методы;

- Методы поиска модальных значений плотности;

- Факторные методы;

- Методы сгущений;

- Методы, использующие теорию графов.

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

Иерархический КА -агломеративный (объединяющий) тип алгоритма, представляющий собой последовательное объединение наиболее схожих объектов во все крупные кластеры. На начальном этапе все объекты рассматриваются как отдельные кластеры. Далее между объектами попарно вычисляются расстояния, и отбирается та пара, которая наиболее близко расположена друг к другу. Эта пара объектов объединяется в кластер. Затем вновь вычисляются все попарные расстояния для объединения близких объектов. Процедура может повторяться до тех пор, пока все объекты не попадут в один кластер. Однако обычно она останавливается после того, как получено необходимое число кластеров, поддающихся содержательной интерпретации.

Алгоритм кластеризации методом k-среднихотносится к итеративным методом группировки. Процедура начинается с определения необходимого числа кластеров. Затем рассчитываются расстояния от объекта до центра кластера и определяется, насколько близок этот объект к другим объектам этого кластера или является «выбросом». Объекты распределяются по кластерам по следующему принципу: каждый объект относится к кластеру с ближайшим к этому объекту центром. Т.о. происходит распределение всех объектов по k-кластерам. Затем заново вычисляются центры полученных кластеров и объекты перераспределяются. Процедура повторяется до тех пор, пока центры кластеров не стабилизируются.