Кластеризация: метод k-средних

Метод k-средних – это метод кластерного анализа, цель которого является разделение m наблюдений (из пространства ) на k кластеров, при этом каждое наблюдение относится к тому кластеру, к центру (центроиду) которого оно ближе всего. 

В качестве меры близости используется Евклидово расстояние:

, где 

Итак, рассмотрим ряд наблюдений .

Метод k-средних разделяет m наблюдений на k групп (или кластеров) (k ≤ m) , чтобы минимизировать суммарное квадратичное отклонение точек кластеров от центроидов этих кластеров:

, где 

 - центроид для кластера .

Алгоритм

Итак, если мера близости до центроида определена, то разбиение объектов на кластеры сводится к определению центроидов этих кластеров. Число кластеров k задается исследователем заранее.

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

Относим наблюдения к тем кластерам, чье среднее (центроид) к ним ближе всего. Каждое наблюдение принадлежит только к одному кластеру, даже если его можно отнести к двум и более кластерам. 

Затем центроид каждого i-го кластера перевычисляется по следующему правилу:

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

Алгоритм останавливается, когда значения  не меняются: 

Важно: Неправильный выбор первоначального числа кластеров k может привести к некорректным результатам. Именно поэтому при использовании метода k-средних важно сначала провести проверку подходящего числа кластеров для данного набора данных. 

Итак, еще раз подчеркнем некоторые особенности метода k-средних:

1. В качестве метрики используется Евклидово расстояние
2. Число кластеров заранее не известно и выбирается исследователем заранее
3. Качество кластеризации зависит от первоначального разбиения

Связанные определения:
Кластерный анализ (кластеризация)

В начало

Содержание портала