реализация грубой силы

ВВЕДЕНИЕ

Кластеризацияявляется одной из основных проблем в науке о данныхи других областях AI/ML. Было изобретено множество алгоритмов кластеризации с разными подходами и целями. На мой взгляд,кластеризация на основе центроидов проще всего понять новичкам в науке о данных.

K-means — самый популярный из них. Поиск в Google термина дает вам более 1 миллиарда результатов менее чем за секунду. Однако K-medoids, напоминающий K-means, не обладает такой же привлекательностью, как его «старший брат».

В этой статье я расскажу о своем понимании алгоритма и представлю реализацию #supernaive на Python 3.

Любые предложения и критические замечания приветствуются.

II — КЛАСТЕРИЗАЦИЯ К-МЕДОИДОВ

1.Что такое медоиды?

Согласно Википедии:

Medoids — репрезентативные объекты набора данных или кластера с набором данных, среднее непохожесть которого на все объекты в кластере минимальна.

Другими словами, есть два условия, чтобы стать медоидом:

(1) Элемент (точка данных/объект) набора данных

(2) Суммирование расстояний от него до всех остальных точек данных («средняя несхожесть», короче) в наборе данных минимально.

Условие (1) отмечает самую большую разницу между K-средними и K-medoids.

2.Выбор медоидов

Это дорого.

Потому что медоиды выбираются, а не вычисляются. Программно мы должны перебирать набор данных, останавливаться в каждой точке данных и вычислять «среднее различие», а затем делать минимальное значение медоидом. В моей реализации #supernaive требуется время O(n²) сложности.

3. Алгоритм

K-medoids также известен как PAM – разделение вокруг Medoids

Ввод: набор данных

Вывод: k кластеров, представленных их медоидами.

Шаг 0. Инициализация

Случайным образом выберите k точек данных в качестве исходных медоидов.

Шаг 1. Связывание (маркировка точек данных)

Выполните итерацию по набору данных, вычислите расстояния между каждыми точками данных dp и текущими медоидами. Свяжите dpс ближайшим медоидом m.

Каждому dp теперь присвоена метка, представляющая собой порядковый номер медоида, представляющего кластер, к которому он принадлежит.

Шаг 2. Обновите медоиды

Предположим, что в каждом кластере каждый dp является потенциальным новым медоидом. Если dp имеет меньшую «среднюю несхожесть», чем у текущего медоида, сделайте его новым медоидом.

Шаг 3. Конвергенция?

Если наши кластеры сошлись (медоиды остаются прежними после обновления), останавливаем алгоритм и возвращаем результат. Наоборот, вернитесь к шагу 1.

Реализация Python

Класс K-medoids

Инициализировать

Ассоциировать

Обновление Медоидов

Ради понимания алгоритма я использую метод грубой силы для вычисления, сравнения и выбора новых медоидов.

Конвергенция?

Собираем вместе

Полный код и тестовые примеры можно найти здесь: https://github.com/briverse17/supernaive-kmedoids

Да, тестирование!

Мы будем генерировать данные вокруг трех исходных точек (2,2), (3,6) и (8,3). Ожидается, что наша модель может приблизительно приблизиться к этому состоянию.

#SuperNaive K-medoids
model=k_medoids(k=3)
print('Centers found by your model:')
print(model.fit(X))
pred = model.predict(X)
visualize(X,pred)
Centers found by your model:
[[1.98413249 2.04159709]
 [7.93224207 3.0213355 ]
 [2.98493437 5.97312308]]

sklearn_extra K-medoids
Centers found by scikit-learn extra:
[[1.98413249 2.04159709]
 [7.93224207 3.0213355 ]
 [2.98493437 5.97312308]]

Ссылки

  1. Статья в Википедии о К-медоидах: https://en.wikipedia.org/wiki/К-медоиды
  2. Реализация K-medoids от Tri Nguyen: https://towardsdatascience.com/k-medoids-clustering-on-iris-data-set-1931bf781e05
  3. Github-репозиторий scikit Learn Extra: https://github.com/scikit-learn-contrib/scikit-learn-extra/tree/master/sklearn_extra/cluster