k -медоиды - k-medoids

Проблема k -медоидов - это проблема кластеризации, аналогичная k- средним . Название было придумано Леонардом Кауфманом и Питером Дж. Руссеу с их алгоритмом PAM. Как k -means, так и k -medoids алгоритмы являются секционирующими (разбиение набора данных на группы) и пытаются минимизировать расстояние между точками, помеченными как находящиеся в кластере, и точкой, обозначенной как центр этого кластера. В отличие от K алгоритма -средних, к -medoids выбирает фактические точки данных в качестве центров ( medoids или экземпляров), и тем самым обеспечивает большую интерпретируемости кластера центров , чем в K -средних, где центр кластера не обязательно один точек входных данных (это среднее значение между точками в кластере). Кроме того, k -медоиды могут использоваться с произвольными мерами несходства, тогда как k- средние обычно требуют евклидова расстояния для эффективных решений. Поскольку k -медоиды минимизируют сумму попарных несходств вместо суммы квадратов евклидовых расстояний , они более устойчивы к шумам и выбросам, чем k- средние .

k -медоиды - это классический метод разбиения на кластеры, который разбивает набор данных из n объектов на k кластеров, где количество k кластеров считается известным априори (что подразумевает, что программист должен указать k перед выполнениемалгоритма k -medoids ). «Качество» данного значения k можно оценить с помощью таких методов, как метод силуэта .

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

Алгоритмы

PAM выбирает начальные medoids, затем повторяет сходимость для k = 3 кластеров, визуализированных с помощью ELKI .

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

Разделение вокруг Medoids (PAM)

PAM использует жадный поиск, который может не найти оптимального решения, но он быстрее, чем полный поиск. Это работает следующим образом:

  1. (BUILD) Инициализация: жадно выберите k из n точек данных в качестве medoids, чтобы минимизировать затраты
  2. Свяжите каждую точку данных с ближайшим медоидом.
  3. (SWAP) Пока стоимость конфигурации снижается:
    1. Для каждого medoid m и для каждой точки o данных, не относящихся к medoid :
      1. Рассмотрим обмен m и o и вычислим изменение стоимости
      2. Если изменение стоимости является лучшим на данный момент, запомните эту комбинацию m и o
    2. Выполните наилучшую замену и , если это снижает функцию стоимости. В противном случае алгоритм завершается.

Сложность выполнения исходного алгоритма PAM на итерацию (3) составляет только вычисление изменения стоимости. Наивная реализация, каждый раз пересчитывающая всю функцию стоимости, будет внутри . Это время выполнения можно дополнительно сократить , разделив изменение стоимости на три части, чтобы можно было совместно использовать вычисления или избежать их (FastPAM). Время выполнения может быть дополнительно сокращено за счет активного выполнения свопов (FasterPAM), после чего случайная инициализация становится жизнеспособной альтернативой BUILD.


Другие алгоритмы

Алгоритмы, отличные от PAM, также были предложены в литературе, включая следующий метод итераций Вороного :

  1. Выбрать начальные медоиды случайным образом
  2. Итерируйте при уменьшении стоимости:
    1. В каждом кластере сделайте точку, которая минимизирует сумму расстояний внутри кластера, как медоид.
    2. Переназначьте каждую точку кластеру, определенному ближайшим медоидом, определенным на предыдущем шаге.

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

Другие приблизительные алгоритмы, такие как CLARA и CLARANS, торгуют оптимальностью во время выполнения. CLARA применяет PAM к нескольким подвыборкам, сохраняя лучший результат. CLARANS работает со всем набором данных, но только исследует подмножество возможных замен медоидов и немедоидов с помощью выборки.

Программное обеспечение

  • ELKI включает несколько вариантов k -медоидов, включая k -медоиды итерации Вороного, оригинальный алгоритм PAM, улучшения Рейнольдса и алгоритмы O (n²) FastPAM и FasterPAM, CLARA, CLARANS, FastCLARA и FastCLARANS.
  • Julia содержит k- medoid реализацию алгоритма стиля k-средних (быстрый, но с гораздо худшим качеством результата) в пакете JuliaStats / Clustering.jl .
  • KNIME включает реализацию k- medoid, поддерживающую множество эффективных мер матричного расстояния, а также ряд собственных (и интегрированных сторонних) реализаций k- средних.
  • Python содержит FasterPAM и другие варианты в пакете " kmedoids ", дополнительные реализации можно найти во многих других пакетах.
  • R содержит PAM в « кластерном » пакете, включая улучшения FasterPAM с помощью параметров variant = "faster"и medoids = "random". Также существует пакет fastkmedoids.
  • В RapidMiner есть оператор KMedoids, но он не реализует ни один из вышеперечисленных алгоритмов KMedoids. Вместо этого это вариант k-средних, который заменяет среднее значение ближайшей точкой данных (которая не является медоидом), что сочетает в себе недостатки k-средних (ограниченных данными координат) с дополнительными затратами на поиск ближайшей точки. в среднем.
  • У Rust есть ящик kmedoids, который также включает вариант FasterPAM.
  • MATLAB реализует PAM, CLARA и два других алгоритма для решения проблемы кластеризации k- медоидов.

использованная литература