k означает алгоритм кластеризации

Question

Я хочу выполнить анализ кластеризации k в наборе из 10 точек данных, каждый из которых имеет массив из 4 числовых значений, связанных с ними. Я использую коэффициент корреляции Пирсона как метрику расстояния. Я сделал первые два шага алгоритма кластеризации k, которые были:

1) Выберите набор начальных центров k кластеров. [Я выбрал случайно два начальных центра]

2) Назначьте каждый объект кластеру с ближайшим центром. [Я использовал коэффициент корреляции Пирсона в качестве расстояния метрики - смотрите ниже]

Теперь мне нужна помощь в понимании 3-й шаг в алгоритме:

3) вычисляем новые центры кластеров:

где X, в данном случае представляет собой четырехмерный вектор, а n - количество точек данных в кластере.

Как бы я мог рассчитать C (S), например, следующие данные?

# Cluster 1 
A 10 15 20 25 # randomly chosen centre 
B 21 33 21 23 
C 43 14 23 23 
D 37 45 43 49 
E 40 43 32 32 

# Cluster 2 
F 100 102 143 212 #random chosen centre 
G 303 213 212 302 
H 102 329 203 212 
I 32 201 430 48 
J 60 99 87 34 

Последний шаг алгоритма k означает повторение шагов 2 и 3, пока объект не изменит кластер, который достаточно прост.

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

Answer 1

Шаг 3 соответствует вычислению среднего значения для каждого кластера. Для кластера 1 вы получите новый кластерный центр (B+C+D+E)/4, который равен (35.25 33.75 29.75 21.75), т. Е. Суммируйте каждый компонент для всех точек в кластере отдельно и разделите его на количество точек в кластере.

Центр кластера (A для кластера 1) обычно не часть расчета нового центра кластера.

Answer 2

Для каждого кластера с n-мерными точками вычислите n-мерный центр масс, чтобы получить центроид. В вашем примере есть 4-мерные точки, поэтому центр масс является средним по каждому из четырех измерений. Для кластера 1 центроид равен: (30,20, 30,00, 27,80, 30,40). Например, среднее значение для первого измерения рассчитывается как (10 + 21 + 43 + 37 + 40)/5 = 30,20.

Для получения дополнительной информации см. Wikipedia article on K-Means clustering.

Answer 3

Не вводите другие функции расстояния в k-знач.

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

Снова: k-средства не сводят к минимуму произвольные расстояния.Он сводит к минимуму «сумму квадратов», которая согласуется с квадратичным евклидовым расстоянием.

Если вам нужен алгоритм, который хорошо определен для любых функций расстояния, рассмотрите возможность использования k-medoids (Wikipedia), варианта k-вариантов k-вариантов. PAM гарантированно сходится с произвольными функциями расстояния.