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

Пусть имеется набор из 8 точек данных в двумерном пространстве, из которого требуется получить два кластера. Значения точек приведены в таблице 1.

Таблица 1.

Исходные данные

Графическое представление данных показано на рисунке 4.

Рисунок 4 - Начальная инициализация.

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

Шаг 1. Определим число кластеров, на которое требуется разбить исходное множество k=2.

Шаг 2. Случайным образом выберем две точки, которые будут начальными центрами кластеров. Пусть это будут точки m₁=(1; 1) и m₂=(2; 1). На рисунке 4 они представлены ромбами.

Шаг 3, проход 1. Для каждой точки определим к ней ближайший центр кластера с помощью расстояния Евклида. В таблица 2 представлены вычисленные с помощью формулы (1) расстояния между центрами кластеров m₁=(1; 1), m₂=(2; 1) и каждой точкой исходного множества, а также указано, к какому кластеру принадлежит та или иная точка.

Таблица 2.

Определение принадлежности точек к одному из кластеров по мере расстояния Евклида

Таким образом, кластер 1 содержит точки A, E, G, а кластер 2 – точки B, C, D, F, H. Как только определятся члены кластеров, может быть рассчитана сумма квадратичных ошибок:

Шаг 4, проход 1. Для каждого кластера вычисляется его центроид, и центр кластера перемещается в него. Центроид для первого кластера вычисляется как:

Центроид для кластера 2 будет равен:

Расположение кластеров и центроидов после первого прохода алгоритма представлено на рисунок 5.

Рисунок 5 - Расположение кластеров и центроидов после первого прохода алгоритма

На рисунке 5 начальные центры кластеров представлены светлыми ромбами, а центроиды, вычисленные при 1-м проходе алгоритма, – красными ромбами. Они и будут являться новыми центрами кластеров, к которым будет определяться принадлежность точек данных на втором проходе.

Шаг 3, проход 2. После того, как найдены новые центры кластеров, для каждой точки снова определяется ближайший к ней центр и ее отношение к соответствующему кластеру. Для это еще раз вычисляются евклидовы расстояния между точками и центрами кластеров. Результаты вычислений приведены в таблице 3.

Таблица 3.

Определение принадлежности точек к одному из кластеров во втором проходе

Относительно большое изменение m₂ привело к тому, что запись H оказалась ближе к центру m₁, что автоматически сделало ее членом кластера 1. Все остальные записи остались в тех же кластерах, что и на предыдущем проходе алгоритма. Таким образом, кластер 1 будет A, E, G, H, а кластер 2 – B, C, D, F. Новая сумма квадратов ошибок составит

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

Шаг 4, проход 2. Для каждого кластера вновь вычисляется его центроид, и центр кластера перемещается в него. Новый центроид для 1-го кластера вычисляется как:

Центроид для кластера 2 будет:

Расположение кластеров и центроидов после второго прохода алгоритма представлено на рисунке 6.

Рис. 6. Расположение кластеров и центроидов после второго прохода алгоритма

По сравнению с предыдущем проходом центры кластеров изменились незначительно. Шаг 3, проход 3. Для каждой записи вновь ищется ближайший к ней центр кластера. Полученные на данном проходе расстояния представлены в таблице 4.

Таблица 4.

Определение принадлежности точек к одному из кластеров в втретем проходе

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

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

Шаг 4, проход 3. Для каждого кластера вновь вычисляется его центроид, и центр кластера перемещается в него. Но поскольку на данном проходе ни одна запись не изменила своего членства в кластерах, то положение центроида не поменялось, и алгоритм завершает свою работу.

Варианты заданий:

Общее для всех вариантов задание – провести кластеризацию по алгоритму k-means два раза: первый раз с использованием метрики L₂ (Евклидово расстояния), второй раз с использованием метрики L₂ (Расстояние Манхэттена). Оформление отчета должно быть аналогичным тому, как это было представлено выше. Исходные данные должны содержать не менее 50 записей. Количество кластеров – не меньше 3. У каждой записи количество и значения параметров должны соответствовать варианту задания.

1 Вариант: У записей должно быть 3 параметра. Первый изменяется в диапазоне [0, 1; 5], второй параметр – в диапазоне [0, 1; 3], третий параметр может принимать значения – 10%, 20%, 80%, 90%.

2 Вариант: У записей должно быть 3 параметра. Первый изменяется в диапазоне [0, 01; 1], второй параметр – в диапазоне [1; 300], третий параметр может принимать значения – Самара, Тольятти, Чапаевск.

3 Вариант: Первый изменяется в диапазоне [0; 1], второй параметр – в диапазоне [-2; 2], третий параметр может принимать значения – да или нет.

4 Вариант: Первый изменяется в диапазоне [-10; 1], второй параметр – в диапазоне [1; 2], третий параметр может принимать значения – отрицательное значение, положительное значение.