Кластер имеет следующие математические характеристики:

Центр кластера - это среднее геометрическое место точек в пространстве переменных.

(1.2)

Дисперсия кластера - это мера рассеяния точек в пространстве относительно центра кластера:

(1.3)

Среднеквадратичное отклонение (СКО) объектов относительно центра кластера:

(1.4)

Радиус кластера - максимальное расстояние точек от центра кластера [8, с.112]:

(1.5)

Спорный объект - это объект, который по мере сходства может быть отнесен к нескольким кластерам.

Размер кластера может быть определен либо по радиусу кластера, либо по среднеквадратичному отклонению объектов для этого кластера. Объект относится к кластеру, если расстояние от объекта до центра кластера меньше радиуса кластера. Если это условие выполняется для двух и более кластеров, объект является спорным.

Неоднозначность данной задачи может быть устранена экспертом или аналитиком.

Работа кластерного анализа опирается на два предположения: Первое предположение - рассматриваемые признаки объекта в принципе допускают желательное разбиение совокупности объектов на кластеры. Второе предположение - правильность выбора масштаба или единиц измерения признаков.

Выбор масштаба в кластерном анализе имеет большое значение. Рассмотрим пример. Представим себе, что данные признака х в наборе данных А на два порядка больше данных признака у: значения переменной х находятся в диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1.

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

Эта проблема решается при помощи предварительной стандартизации переменных. Стандартизация (standardization) или нормирование (normalization) приводит значения всех преобразованных переменных к единому диапазону значений путем выражения через отношение этих значений к некой величине, отражающей определенные свойства конкретного признака. Существуют различные способы нормирования исходных данных.

Два наиболее распространенных способа:

- деление исходных данных на среднеквадратичное отклонение соответствующих переменных;

- вычисление Z-вклада или стандартизованного вклада.

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

В ходе экспериментов возможно сравнение результатов, полученных с учетом экспертных оценок и без них, и выбор лучшего из них [2, с.82].

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

Эвристический подход характеризуется отсутствием формальной модели изучаемой модели и критерия для сравнения различных решений. Его основой является алгоритм, построенный исходя из интуитивных соображений.

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

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

В задачах кластерного анализа обычной формой представления исходных данных служит прямоугольная таблица, каждая строка которой представляет результат измерения k признаков на одном из n обследованных объектов [3, с.132]:

Таким образом, это матрица X. В конкретных случаях может представлять интерес как группировка объектов, так и группировка признаков.

Числовые значения элементов матрицы X могут соответствовать переменным трех типов: количественным, ранговым и качественным. Количественные переменные обладают свойством упорядоченности и над ними можно производить арифметические операции. Значения ранговых переменных тоже упорядочены, и им в соответствие можно поставить натуральные числа. Однако использование этих чисел в арифметических операциях будет некорретным. Качественными называются переменные, принимающие два или более значений. Этим значениям также можно поставить в соответствие некоторые числа, но без свойств упорядоченности. Исключение составляют дихотомные переменные, два значения которых (как правило, они обозначаются числами 0 и 1) можно считать упорядоченными.

Желательно, чтобы таблица исходных данных соответствовала одному типу переменных. В противном случае разные типы переменных стараются свести к какому-то одному типу переменных. Например, все переменные можно свести к дихотомным, используя следующую процедуру. Количественные переменные переводят в ранговые, разбивая области значений количественной переменной на интервалы, которые затем нумеруются числами натурального ряда. Ранговые переменные автоматически становятся качественными, если не учитывать упорядоченности их значений. Что касается качественных переменных, то каждому из возможных ее значений приходится сопоставлять дихотомную переменную, которая будет равна 1, если качественная переменная приняла заданное значение, и 0 - в противном случае.

Сам кластерный анализ представляет собой ряд формальных процедур, которые мы продемонстрируем на реальном примере.

Таблица 1.2

Профиль сегментов по свойствам синтетических моющих средств [7, с.36]

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

Разработанная анкета содержала ряд вопросов, характеризующих отношение респондентов к свойствам продукта (табл.1.3), а также характеризующих стиль жизни самих респондентов (табл.1.4). Результаты ответов на вопросы первой группы (респонденты должны были проранжировать факторы по степени их значимости, начиная с самого важного - от 1 до 8) были собраны в 4 сегмента, существенно различающиеся между собой по типу важнейших с точки зрения респондентов признаков продукта (они выделены в таблице 1 заливкой). Эти признаки можно считать «сегментоообразующими».

Легко видеть, что самый крупный (размеры сегментов изменены) сегмент 3 (60% от выборки) - это прагматики, для которых важнейшей характеристикой продукта является его цена, а также такие прозаические качества как моющая способность и эффект отбеливания. Следующий по величине сегмент 1, напротив, на первое место ставит безвредность порошка, цена же занимает последнее 8-е место.

Для того, чтобы лучше представить себе покупателей каждой группы, проанализируем их ответы на вопросы следующей части анкеты. В таблице 2 приводятся эти вопросы и величины средних оценок все по той же 8-балльной шкале для каждого вопроса по тем же сегментам. Мы видим, что сегменты 1 и 3 весьма лояльно относятся к новшествам и склонны экспериментировать с новыми продуктами. При этом сегмент 1 относится к импортным порошкам существенно лучше, чем сегмент 3. Сегмент 4 более чувствителен к рекламе и более последователен в выборе: пользоваться как дорогими, так и дешевыми порошками - не для него.

В таблице 1.4 мы приводим в качестве примера описание профиля одного из сегментов (сегмент 1). Информация, представленная в таком виде, является исключительно удобной для восприятия, анализа и принятия решений.

Таблица 1.3

Профили сегментов по восприятию синтетических моющих средств (балльные оценки) [7, с.37]

Таблица 1.4

Пример описания профилей сегментов

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

Следует сделать еще одно важное замечание по поводу использования технологии кластерного анализа. Все исследование, начиная с плана и заканчивая анкетой, должно быть «заточено» под методику кластерного анализа. Это касается и используемых шкал, и метода контакта с аудиторией и многих других факторов. Использование результатов сегментирования на основании кластерного анализа дает компаниям реальный шанс глубже понять своих клиентов и потребителей. Это, в свою очередь, позволит свести к минимуму разницу между представлениями продавцов и покупателей, то есть карта восприятия товара или услуги для них будет практически идентичной.

Что касается программных инструментов обработки результатов, рекомендуются пакеты SPSS и NCSS. Несмотря на их кажущееся сходство с Excel по пользовательскому интерфейсу и представлению данных, эти программы позволяют обрабатывать информацию быстрее и эффективнее. Под эффективностью понимается экономия времени на дополнительной обработке данных и использование методов анализа, недоступных в Excel. Наиболее рутинная работа в SPSS - это ввод данных. При этом каждой переменной ставится в соответствие определенная шкала, что является исключительно важным при обработке данных исследований. Время, затраченное на ввод данных с исполнением всех соответствующих процедур, полностью оправдывает себя на этапе обработки и анализа данных, так как результаты, выдаваемые SPSS, практически не нуждаются в дополнительном «причесывании», в отличие от Excel.

Таким образом, кластерный анализ - метод группировки объектов в классы на основании экспериментальных данных о свойствах объектов.

Кластерный анализ включает в себя набор различных алгоритмов классификации. При этом, как правило, количество классов и принципы разделения на классы определяются заранее исходя из общей информации о наборе объектов и целей кластерного анализа.

Результаты кластер-анализа чаще всего представляются графически, в виде дендрограммы («дерева»), показывающей порядок объединения объектов в кластеры. Интерпретация кластерной структуры, которая во многих случаях начинается с определения числа кластеров, является творческой задачей. Для того, чтобы она могла быть эффективно решена, исследователь должен располагать достаточной информацией о кластеризуемых объектах. При кластеризации «с обучением» результаты могут быть представлены в виде списков объектов, отнесенных к каждому классу.

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

Методы кластерного анализа можно разделить на две группы:

- иерархические;

- неиерархические [5, с.166].

Каждая из групп включает множество подходов и алгоритмов.

Рис. 2.1 Методы кластерного анализа

Используя различные методы кластерного анализа, аналитик может получить различные решения для одних и тех же данных. Это считается нормальным явлением.

Рассмотрим иерархические и неиерархические методы подробно.

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

Иерархические агломеративные методы (Agglomerative Nesting, AGNES) Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.

Принцип работы описанных выше групп методов в виде дендрограммы показан на рис.2.2.

Рис.2.2 Дендрограмма агломеративных и дивизимных методов

Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf.

Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о «схожести» объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).

Иерархические методы кластерного анализа используются при небольших объемах наборов данных.

Преимуществом иерархических методов кластеризации является их наглядность.

Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - «дерево»), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

Дендрограмма (dendrogram) - древовидная диаграмма, содержащая n уровней, каждый из которых соответствует одному из шагов процесса последовательного укрупнения кластеров [6, с.115].

Дендрограмму также называют древовидной схемой, деревом объединения кластеров, деревом иерархической структуры.

Дендрограмма представляет собой вложенную группировку объектов, которая изменяется на различных уровнях иерархии.

Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рис.2.3.

Рис. 2.3 Пример дендрограммы

Числа 11, 10, 3 и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8,9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

Для вычисления расстояния между объектами используются различные меры сходства (меры подобия), называемые также метриками или функциями расстояний. Евклидово расстояние, это наиболее популярная мера сходства.

Квадрат евклидова расстояния. Для придания больших весов более отдаленным друг от друга объектам можем воспользоваться квадратом евклидова расстояния путем возведения в квадрат стандартного евклидова расстояния.

Манхэттенское расстояние (расстояние городских кварталов), также называемое «хэмминговым» или «сити-блок» расстоянием [5, с.167].

Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к результатам, подобным расчетам расстояния евклида. Однако, для этой меры влияние отдельных выбросов меньше, чем при использовании евклидова расстояния, поскольку здесь координаты не возводятся в квадрат.

Расстояние Чебышева. Это расстояние стоит использовать, когда необходимо определить два объекта как «различные», если они отличаются по какому-то одному измерению.

Процент несогласия. Это расстояние вычисляется, если данные являются категориальными.

Когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Возникает следующий вопрос - как определить расстояния между кластерами? Существуют различные правила, называемые методами объединения или связи для двух кластеров.

Метод ближнего соседа или одиночная связь.

Здесь расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В результате работы этого метода кластеры представляются длинными «цепочками» или «волокнистыми» кластерами, «сцепленными вместе» только отдельными элементами, которые случайно оказались ближе остальных друг к другу.

Метод наиболее удаленных соседей или полная связь [1, с.174].

Здесь расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. «наиболее удаленными соседями»). Метод хорошо использовать, когда объекты действительно происходят из различных «рощ». Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является «цепочечным», то этот метод не следует использовать.

Метод Варда (Ward's method).

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

Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)). В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты действительно происходят из различных «рощ», в случаях присутствия кластеров «цепочного» типа, при предположении неравных размеров кластеров.

Метод взвешенного попарного среднего (метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal, 1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере). Этот метод рекомендуется использовать именно при наличии предположения о кластерах разных размеров. Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average (Sneath and Sokal, 1973)).

В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.

Взвешенный центроидный метод

метод взвешенного попарного центроидного усреднения - weighted pair-group method using the centroid average, WPGMC (Sneath, Sokal 1973)). Этот метод похож на предыдущий, разница состоит в том, что для учета разницы между размерами кластеров (числе объектов в них), используются веса. Этот метод предпочтительно использовать в случаях, если имеются предположения относительно существенных отличий в размерах кластеров.

Существует проблема определения числа кластеров. Иногда можно априорно определить это число. Однако в большинстве случаев число кластеров определяется в процессе агломерации/разделения множества объектов. Процессу группировки объектов в иерархическом кластерном анализе соответствует постепенное возрастание коэффициента, называемого критерием Е. Скачкообразное увеличение значения критерия Е можно определить как характеристику числа кластеров, которые действительно существуют в исследуемом наборе данных. Таким образом, этот способ сводится к определению скачкообразного увеличения некоторого коэффициента, который характеризует переход от сильно связанного к слабо связанному состоянию объектов [5, с.178].

Порядок агломерации (протокол объединения кластеров) приведен в таблице 2.1.

В протоколе указаны такие позиции:

- Stage - стадии объединения (шаг);

- Cluster Combined - объединяемые кластеры (после объединения кластер принимает минимальный номер из номеров объединяемых кластеров);

- Coefficients - коэффициенты.

Таблица 2.1

Порядок агломерации

Так, в колонке Cluster Combined можно увидеть порядок объединения в кластеры: на первом шаге были объединены наблюдения 9 и 10, они образовывают кластер под номером 9, кластер 10 в обзорной таблице больше не появляется. На следующем шаге происходит объединение кластеров 2 и 14, далее 3 и 9, и т.д.

В колонке Coefficients приведено количество кластеров, которое следовало бы считать оптимальным; под значением этого показателя подразумевается расстояние между двумя кластерами, определенное на основании выбранной меры расстояния. В нашем случае это квадрат евклидова расстояния, определенный с использованием стандартизированных значений. Процедура стандартизации используется для исключения вероятности того, что классификацию будут определять переменные, имеющие наибольший разброс значений. В SPSS применяются следующие виды стандартизации:

- Z-шкалы (Z-Scores). Из значений переменных вычитается их среднее, и эти значения делятся на стандартное отклонение.

- Разброс от - 1 до 1. Линейным преобразованием переменных добиваются разброса значений от - 1 до 1.

- Разброс от 0 до 1. Линейным преобразованием переменных добиваются разброса значений от 0 до 1.

- Максимум 1. Значения переменных делятся на их максимум.

- Среднее 1. Значения переменных делятся на их среднее.

- Стандартное отклонение 1. Значения переменных делятся на стандартное отклонение.

Кроме того, возможны преобразования самих расстояний, в частности, можно расстояния заменить их абсолютными значениями, это актуально для коэффициентов корреляции. Можно также все расстояния преобразовать так, чтобы они изменялись от 0 до 1.

В таблице 2.1 мы видим, что значение поля Coefficients увеличивается скачкообразно, следовательно, объединение в кластеры следует остановить, иначе будет происходить объединение кластеров, находящихся на относительно большом расстоянии друг от друга.

В нашем примере это скачок с 1,217 до 7,516. Оптимальным считается количество кластеров, равное разности количества наблюдений (14) и количества шагов до скачкообразного увеличения коэффициента (12).

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

Агрегирование данных может быть представлено графически в виде дендрограммы. Она определяет объединенные кластеры и значения коэффициентов на каждом шаге агломерации (отображены значения коэффициентов, приведенные к шкале от 0 до 25).

Дендрограмма для нашего примера приведена на рис.2.4. Разрез дерева агрегирования вертикальной чертой дал нам два кластера, состоящих из 9 и 5 объектов. На верхней линии по горизонтали отмечены номера шагов алгоритма, всего алгоритму потребовалось 25 шагов для объединения всех объектов в один кластер.

Рис. 2.4 Дендрограмма процесса слияния

Пусть имеется шесть объектов. Каждый объект описывается двумя показателями. Исходная матрица наблюдений X имеет вид:

Используя в качестве метрики квадрат Евклидова расстояния, получаем матрицу расстояний:

Применим для образования кластеров метод одиночной связи и метод ближайшего соседа.

1. Объединяем объекты первый и шестой (расстояние равно 1) в первый кластер.

2. Объединяем объекты второй и четвертый (расстояние равно 1) во второй кластер.

3. Включаем в первый кластер третий объект, так как расстояние между ним и первым объектом минимально (равно 2).

4. Включаем во второй кластер пятый объект, так как расстояние между ним и четвертым объектом минимально (равно 2).

5. Объединяем первый и второй кластеры, так как расстояние между вторым и третьим объектом минимально (равно 4).

Последовательность объединения графически представляется в виде графа-дерева (дендрограммы):

Ниже на рисунке в плоскости x₁, x₂ показаны первый и второй кластеры

Необходимо отметить, что результат классификации зависит как от метода классификации и применяемой метрики, так и от нормализации (стандартизации) значений признаков. Например, при решении данной задачи признаки имели естественные значения. Если выполнить нормализацию исходных данных, то матрица Z будет иметь вид:

Напомним, что

z_il = (x_il - x_l) /S_l,

где x_{il -} значение l-го признака i-го объекта;

x_l - среднее арифметическое значение l-го признака;

S_l = (?_i (x_il - x_l) ²/ (n-1)) ^1/2 - стандартное отклонение l-го признака.

В нашем случае x₁ = 2,83, S₁ = 1,72, x₂ = 2,0, S₂ = 0,89.

Матрица расстояний имеет вид:

Применение тех же методов одиночной связи и ближайшего соседа получаем другое разбиение на кластеры:

Отдельным кластером является пятый объект. В плоскости x₁, x₂ показаны первый и второй кластеры.

Однако из дендрограммы очевидно, что удачнее разбиение на три кластера:

Кластер 1: объекты 1 и 6; кластер 2: объекты 2, 3 и 4; кластер 3: объект

Таким образом, выделяют две группы методов кластерного анализа: иерархические и неиерархические.

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

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