к -медоиды

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

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

Медоид кластера определяется как объект в кластере, чья сумма (и, что то же самое, среднее) различий со всеми объектами в кластере минимальна, то есть это самая центральная точка кластера.

Алгоритмы

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

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

ПАМ ^[1] использует жадный поиск, который может не найти оптимального решения, но он быстрее, чем полный поиск. Это работает следующим образом:

(СОЗДАНИЕ) Инициализация: жадно выберите $k$ из $n$ точек данных в качестве медоидов, чтобы минимизировать затраты.
Свяжите каждую точку данных с ближайшим медоидом.
(SWAP) При этом стоимость комплектации снижается:
1. Для каждого медоида m и для каждой немедоидной точки данных o :
  1. Рассмотрим замену $m$ и $o$ и вычислим изменение стоимости
  2. Если изменение затрат является лучшим на данный момент, запомните эту «м» и «о». комбинацию
2. Выполните лучший обмен $m_{\text{best}}$ и $o_{\text{best}}$ , если это уменьшает функцию стоимости. В противном случае алгоритм завершается.

Сложность выполнения исходного алгоритма PAM на итерацию (3) равна $O(k(n-k)^{2})$ , вычисляя только изменение стоимости. Наивная реализация, каждый раз пересчитывающая всю функцию стоимости, будет $O(n^{2}k^{2})$ . Это время выполнения можно дополнительно сократить до $O(n^{2})$ , разделив изменение стоимости на три части, чтобы можно было разделить вычисления или избежать их (FastPAM). Время выполнения можно дополнительно сократить за счет быстрого выполнения свопов (FasterPAM), ^[2] в этот момент случайная инициализация становится жизнеспособной альтернативой BUILD.

Альтернативная оптимизация

В литературе также предлагались другие алгоритмы, кроме PAM, в том числе следующий итерационный метод Вороного, известный в литературе как «попеременная» эвристика, поскольку он чередует два этапа оптимизации: ^[3]^[4]^[5]

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

Итерация Вороного в стиле k -means имеет тенденцию давать худшие результаты и демонстрировать «беспорядочное поведение». ^[6]^: 957 Поскольку он не позволяет переназначать точки другим кластерам во время обновления, это означает, что он исследует только меньшее пространство поиска. Можно показать, что даже в простых случаях эта эвристика находит худшие решения, которые могут решить методы на основе замены. ^[2]

Иерархическая кластеризация

несколько вариантов иерархической кластеризации Было предложено с «медоидной связью». Критерий связи минимальной суммы ^[7] напрямую использует цель медоидов, но было показано, что связь с увеличением минимальной суммы дает лучшие результаты (аналогично тому, как связь Уорда использует увеличение квадратичной ошибки). Более ранние подходы просто использовали расстояние кластерных медоидов от предыдущих медоидов в качестве меры связи. ^[8]^[9] но это имеет тенденцию приводить к худшим решениям, поскольку расстояние между двумя медоидами не гарантирует наличие хорошего медоида для комбинации. Эти подходы имеют сложность времени выполнения $O(n^{3})$ , а когда дендрограмма разрезается на определенное количество кластеров k , результаты обычно будут хуже, чем результаты, полученные с помощью PAM. ^[7] Следовательно, эти методы представляют интерес в первую очередь, когда требуется иерархическая древовидная структура.

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Кауфман, Леонард; Руссиу, Питер Дж. (1990-03-08), «Разделение вокруг медоидов (программа PAM)» , Серия Уайли по вероятности и статистике , Хобокен, Нью-Джерси, США: John Wiley & Sons, Inc., стр. 68–125, дои : 10.1002/9780470316801.ch2 , ISBN 978-0-470-31680-1 , получено 13 июня 2021 г.
^ Jump up to: ^а ^б Шуберт, Эрих; Руссиу, Питер Дж. (2021). «Быстрая и энергичная кластеризация k -medoids: улучшение времени выполнения O (k) алгоритмов PAM, CLARA и CLARANS» . Информационные системы . 101 : 101804. arXiv : 2008.05171 . дои : 10.1016/j.is.2021.101804 . S2CID 221103804 .
^ Маранцана, FE (1963). «О расположении точек снабжения для минимизации транспортных расходов». IBM Systems Journal . 2 (2): 129–135. дои : 10.1147/sj.22.0129 .
^ Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer (2001), 468–469.
^ Пак, Хэ-Сан; Джун, Чи-Хек (2009). «Простой и быстрый алгоритм кластеризации K-медоидов». Экспертные системы с приложениями . 36 (2): 3336–3341. дои : 10.1016/j.eswa.2008.01.039 .
^ Тейтц, Майкл Б.; Барт, Полли (1 октября 1968 г.). «Эвристические методы оценки обобщенной медианы вершин взвешенного графа». Исследование операций . 16 (5): 955–961. дои : 10.1287/опре.16.5.955 . ISSN 0030-364X .
^ Jump up to: ^а ^б Шуберт, Эрих (2021). HACAM: Иерархическая агломеративная кластеризация вокруг медоидов – и ее ограничения (PDF) . LWDA'21: Обучение, знания, данные, анализ 01–03 сентября 2021 г., Мюнхен, Германия. стр. 191–204 – через CEUR-WS.
^ Миямото, Садааки; Кайдзу, Юске; Эндо, Ясунори (2016). Иерархическая и неиерархическая кластеризация медоидов с использованием асимметричных мер сходства . 2016 Совместная 8-я Международная конференция по мягким вычислениям и интеллектуальным системам (SCIS) и 17-й Международный симпозиум по передовым интеллектуальным системам (ISIS). стр. 400–403. дои : 10.1109/SCIS-ISIS.2016.0091 .
^ Герр, Доминик; Хан, Ци; Ломанн, Штеффен; Эртл, Томас (2016). Уменьшение визуального беспорядка посредством иерархического проецирования многомерных размеченных данных (PDF) . Графический интерфейс. Графический интерфейс . дои : 10.20380/gi2016.14 . Проверено 4 ноября 2022 г.
^ Тивари, Миссури; Чжан, Мартин Дж.; Мэйклин, Джеймс; Трун, Себастьян; Пих, Крис; Шомороный, Илан (2020). «BanditPAM: кластеризация k-медоидов почти в линейном времени с помощью многоруких бандитов» . Достижения в области нейронных систем обработки информации . 33 .

[:2-1] Jump up to: ^а ^б Кауфман, Леонард; Руссиу, Питер Дж. (1990-03-08), «Разделение вокруг медоидов (программа PAM)» , Серия Уайли по вероятности и статистике , Хобокен, Нью-Джерси, США: John Wiley & Sons, Inc., стр. 68–125, дои : 10.1002/9780470316801.ch2 , ISBN 978-0-470-31680-1 , получено 13 июня 2021 г.

[:1-2] Jump up to: ^а ^б Шуберт, Эрих; Руссиу, Питер Дж. (2021). «Быстрая и энергичная кластеризация k -medoids: улучшение времени выполнения O (k) алгоритмов PAM, CLARA и CLARANS» . Информационные системы . 101 : 101804. arXiv : 2008.05171 . дои : 10.1016/j.is.2021.101804 . S2CID 221103804 .

[3] Маранцана, FE (1963). «О расположении точек снабжения для минимизации транспортных расходов». IBM Systems Journal . 2 (2): 129–135. дои : 10.1147/sj.22.0129 .

[EoSL-4] Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer (2001), 468–469.

[5] Пак, Хэ-Сан; Джун, Чи-Хек (2009). «Простой и быстрый алгоритм кластеризации K-медоидов». Экспертные системы с приложениями . 36 (2): 3336–3341. дои : 10.1016/j.eswa.2008.01.039 .

[6] Тейтц, Майкл Б.; Барт, Полли (1 октября 1968 г.). «Эвристические методы оценки обобщенной медианы вершин взвешенного графа». Исследование операций . 16 (5): 955–961. дои : 10.1287/опре.16.5.955 . ISSN 0030-364X .

[:0-7] Jump up to: ^а ^б Шуберт, Эрих (2021). HACAM: Иерархическая агломеративная кластеризация вокруг медоидов – и ее ограничения (PDF) . LWDA'21: Обучение, знания, данные, анализ 01–03 сентября 2021 г., Мюнхен, Германия. стр. 191–204 – через CEUR-WS.

[8] Миямото, Садааки; Кайдзу, Юске; Эндо, Ясунори (2016). Иерархическая и неиерархическая кластеризация медоидов с использованием асимметричных мер сходства . 2016 Совместная 8-я Международная конференция по мягким вычислениям и интеллектуальным системам (SCIS) и 17-й Международный симпозиум по передовым интеллектуальным системам (ISIS). стр. 400–403. дои : 10.1109/SCIS-ISIS.2016.0091 .

[9] Герр, Доминик; Хан, Ци; Ломанн, Штеффен; Эртл, Томас (2016). Уменьшение визуального беспорядка посредством иерархического проецирования многомерных размеченных данных (PDF) . Графический интерфейс. Графический интерфейс . дои : 10.20380/gi2016.14 . Проверено 4 ноября 2022 г.

[10] Тивари, Миссури; Чжан, Мартин Дж.; Мэйклин, Джеймс; Трун, Себастьян; Пих, Крис; Шомороный, Илан (2020). «BanditPAM: кластеризация k-медоидов почти в линейном времени с помощью многоруких бандитов» . Достижения в области нейронных систем обработки информации . 33 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]