Как выполнить алгоритм PAM без создания копии кластеров для каждого свопа?

Question

Я пытаюсь реализовать алгоритм PAM.На этапе обмена мне нужно найти наиболее оптимальный обмен между парой элементов (медоид, немедоид).Моей первоначальной идеей оценки качества свопа было вычисление общей дисперсии до и после свопа и поиск наибольшего значения дельты, чтобы выбрать лучшую пару элементов.Это, однако, требует от меня создания копии всей системы для каждой пары, что может стать очень медленным для больших наборов данных.

Для представления кластера я использую карту, где медоиды отображаются в списокнемедоиды (кластер, который они составляют).

Есть ли более эффективный способ выполнить эту задачу?

Answer 1

Это будет ужасно медленно.

Проведите анализ сложности вашего подхода.PAM должен быть O (k (nk) ²).Существует петля над всеми medoids и всеми non-medoids.Это оставляет вам O (nk), чтобы вычислить стоимость свопа.

PAM вычисляет изменение качества кластеризации непосредственно для достижения этой цели.Возможно, вам придется изучить его более внимательно - не полагайтесь на сводки качества Википедии, которые фокусируются на основной идее, а не на всех деталях.Вместо этого прочитайте книгу Кауфмана и Руссо.