Что делает меру расстояния в k-medoid "лучше", чем k-означает?

Я читаю о различии между кластерами k-средних и k-медоидной кластеризацией.

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

Я видел это утверждение, но я еще не видел никаких хороших рассуждений относительно математики, стоящей за этим утверждением.

Что делает парную меру расстояния, обычно используемую в k-medoid лучше? Более точно, как отсутствие квадратного члена позволяет k-медоидам обладать желательными свойствами, связанными с концепцией взятия медианы?

Ответ 1

1. K-medoid более гибкая

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

2. Прочность медоидов

Во-вторых, медоид, используемый k-медоидами, примерно сравним с медианным (на самом деле, также есть k-медианы, которые похожи на K-средства, но для Манхэттенского расстояния). Если вы посмотрите литературу по медианной, вы увидите множество объяснений и примеров, почему медиана более устойчива к выбросам, чем среднее арифметическое. По сути, эти объяснения и примеры также будут иметь место для медоидов. Это более надежная оценка репрезентативной точки, чем среднее значение, используемое в k-значении.

Рассмотрим этот одномерный пример:

1 2 3 4 100 000

Оба медианы и медоиды этого набора равны 3. Среднее значение 20002.

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

Технически в статистике используется понятие точки пробоя. Медиана имеет точку пробоя 50% (т.е. Половина точек данных может быть неправильной, и результат по-прежнему не изменяется), тогда как среднее имеет точку пробоя 0 (т.е. Одно большое наблюдение может дать плохую оценку).

У меня нет доказательств, но я полагаю, что у медоидов будет такая же точка пробоя, как медиана.

3. k-medoids намного дороже

Это главный недостаток. Обычно PAM занимает гораздо больше времени, чем k-означает. Поскольку он включает вычисление всех попарных расстояний, это O(n^2*k*i); тогда как k-средство работает в O(n*k*i), где обычно k раз число итераций k*i << n.

Ответ 2

Я думаю, что это связано с выбором центра для кластера. k-середины выберет "центр" кластера, а k-medoid выберет "наиболее центрированный" член кластера. В кластере с выбросами (т.е. Точками, расположенными далеко от других членов кластера) k-средство поместит центр кластера к выбросам, тогда как k-медоид выберет один из более сгруппированных членов (медоид) в качестве центр.

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

В словах википедии:

"Он [k-medoid] более устойчив к шуму и выбросам по сравнению с k-средствами, поскольку он минимизирует сумму попарных различий вместо суммы квадратов евклидовых расстояний".

Вот пример:

Предположим, вы хотите сгруппировать по одному измерению с k = 2. Один кластер имеет большинство своих членов около 1000, а другой около -1000; но есть выброс (или шум) на 100000. Он, очевидно, принадлежит кластеру около 1000, но k-означает, что центр будет удален от 1000 до 100000. Это может даже сделать некоторые из членов кластера 1000 (например, члена со значением 500) 1000. k-medoid выберет один из членов около 1000 как медоид, он, вероятно, выберет тот, который больше 1000, но не будет выбирать outlier.

Ответ 3

Просто крошечная нота, добавленная к ответу @Eli, K-medoid более устойчива к шуму и выбросам, чем к-означает, потому что последний выбирает центр кластера, который в основном является "точкой добродетели", с другой стороны, бывший выбирает "фактический объект" из кластера.

Предположим, что у вас есть пять двумерных точек в одном кластере с координатами (1,1), (1,2), (2,1), (2,2) и (100,100). Если мы не рассматриваем обмен объектов между кластерами, с k-средствами вы получите центр кластера (21.2,21.2), который довольно отвлекается на точку (100 100). Однако, k-medoid выберет центр среди (1,1), (1,2), (2,1) и (2,2) согласно его алгоритму.

Вот забавный апплет (EM Mirkes, K-средство и апплет K-medoids. University of Leicester, 2011), что вы можете случайно генерировать набор данных в 2D-плоскости и сравнивать процесс обучения k-medoid и k-средств.