Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Проблема k -медоидов - это проблема кластеризации, аналогичная k- средним . Как k -means, так и k -medoids алгоритмы являются секционирующими (разбиение набора данных на группы) и пытаются минимизировать расстояние между точками, помеченными как находящиеся в кластере, и точкой, обозначенной как центр этого кластера. В отличие от K алгоритма -средних, к -medoids выбирает фактические точки данных в качестве центров ( medoids или экземпляров), и тем самым позволяет повысить интерпретируемости кластерных центров , чем в к- означает, что центр кластера не обязательно является одной из точек входных данных (это среднее значение между точками в кластере). Кроме того, 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) составляет только вычисление изменения стоимости. Наивная реализация, каждый раз пересчитывающая всю функцию стоимости, будет внутри . Это время выполнения можно дополнительно сократить , разделив изменение стоимости на три части, чтобы можно было совместно использовать вычисления или избежать их. [1]


Другие алгоритмы [ править ]

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

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

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

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

Программное обеспечение [ править ]

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

Ссылки [ править ]

  1. ^ а б Шуберт, Эрих; Руссеу, Питер Дж. (2019), Амато, Джузеппе; Дженнаро, Клаудио; Ория, Винсент; Радованович, Милош (ред.), «Более быстрая кластеризация k-Medoids: улучшение алгоритмов PAM, CLARA и CLARANS», Поиск сходства и приложения , Springer International Publishing, 11807 , стр. 171–187, arXiv : 1810.05691 , doi : 10.1007 / 978-3-030-32047-8_16 , ISBN 9783030320461
  2. Перейти ↑ Maranzana, FE (1963). «О расположении точек снабжения для минимизации транспортных расходов». IBM Systems Journal . 2 (2): 129–135. DOI : 10.1147 / sj.22.0129 .
  3. ^ Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer (2001), 468–469.
  4. ↑ Пак, Хэ-Сан; Джун, Чи-Хёк (2009). «Простой и быстрый алгоритм кластеризации K-medoids». Экспертные системы с приложениями . 36 (2): 3336–3341. DOI : 10.1016 / j.eswa.2008.01.039 .
  5. ^ Тейтц, Майкл Б .; Барт, Полли (1968-10-01). «Эвристические методы оценки обобщенной медианы вершин взвешенного графа». Исследование операций . 16 (5): 955–961. DOI : 10.1287 / opre.16.5.955 . ISSN 0030-364X .