Алгоритмы k-means и k-medians

Алгоритм k-средних (k-means) – алгоритм кластеризации данных. Целью задачи кластеризации является разбиение множества объектов на кластеры (классы) на основе некоторой меры сходства объектов.

Дано:

Набор векторов , i = 1,…, p;

k – число кластеров, на которые нужно разбить набор .

Найти:

k средних векторов m _j, j = 1,…, k (центров кластеров);

отнести каждый из векторов к одному из k кластеров;

Алгоритм:

1. Случайным образом выбрать k средних m_j j = 1,…, k;

2. Для каждого x _i i = 1,…, p подсчитать расстояние до каждого из m_j j =1,…, k,

Отнести (приписать) x_i к кластеру j’, расстояние до центра которого m_j’ минимально;

3. Пересчитать средние (центр масс) m_j j =1,…, k по всем кластерам;

4. Повторять шаги 2, 3, пока кластеры не перестанут изменяться.

Пример кластеризации в 2D.

Алгоритм k-medians - это вариация k-means метода кластеризации, где для определения центра кластера вместо среднего вычисляется медиана (по каждому из измерений).

Алгоритм кластеризации k-medoids похож на алгоритм k-means, но в отличие от него на каждой итерации ищет центры кластеров не как среднее точек, а как медоиды точек. То есть, центр кластера должен обязательно являться одной из его точек. Медоидом для множества точек называется одна из точек множества, сумма расстояний до которой от всех точек множества минимальна.

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