Практически в любом курсе машинного обучения Кластеризация K-средних будет одним из первых алгоритмов, которые будут введены для обучения без учителя. Благодаря этому он стал намного популярнее своего кузена K-Medoids Clustering. Если вы погуглите «k-means», появится 1,49 миллиарда результатов. Сделайте то же самое для «k-medoids», вернется только 231 тысяча результатов.

Это было моей проблемой, когда меня попросили реализовать алгоритм кластеризации k-medoids во время одного из моих выпускных экзаменов. На это потребовалось время, но я справился. Поэтому, чтобы помочь концепции k-medoid увидеть больше действий, я решил разместить здесь алгоритм, который я построил и реализовал, на этот раз на основе «печально известного» набора данных Iris.

Введение

Алгоритмы k-средних и k-medoids являются секционирующими, что предполагает разбиение набора данных на группы. K-средство направлено на минимизацию общей квадратичной ошибки для центральной позиции в каждом кластере. Эти центральные позиции называются центроидами. С другой стороны, k-medoids пытается минимизировать сумму различий между объектами, помеченными как находящиеся в кластере, и одним из объектов, обозначенных как представитель этого кластера. Эти представители называются медоидами.

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

Подготовка данных

Мы будем использовать копию набора данных Iris из библиотеки sklearn. Ради демонстрации алгоритма я пропущу разбиение набора данных на наборы для обучения и тестирования и буду использовать один набор данных для обучения и подгонки модели.

Ниже приведены данные измерения длины, ширины чашелистика; длина лепестка, ширина 3 различных типов ириса: [‘setosa’, ‘versicolor’, ‘virginica’] с обозначениями [0, 1, 2]:

У меня есть привычка масштабировать данные для этих типов проблем, когда данные находятся в разных масштабах по столбцам. Поскольку недостающих данных нет, приступим к масштабированию. Я использовал класс MinMaxScaler из той же библиотеки sklearn. Ниже приведены масштабированные данные:

Есть 4 функции, которые могут быть не идеальными для визуализации и подгонки модели кластеризации, поскольку некоторые из них могут быть сильно коррелированы. Поэтому мы будем использовать анализ главных компонентов (PCA) для преобразования 4-мерных данных в 3-мерные данные, сохраняя при этом значимость этих предикторов с помощью класса PCA из sklearn. . Данные с уменьшенным размером, как показано ниже:

Наконец, мы можем визуализировать их на трехмерной плоскости:

Реализация

Сначала мы рассмотрим функцию несходства. Есть много вариантов, но здесь мы будем использовать обычную функцию Расстояние Минковского заданного порядка. Алгоритм, который мы будем реализовывать, называется алгоритмом Partitioning Around Medoids (PAM) (Кауфман и Руссеу, 1990). Его можно резюмировать следующим образом:

  1. Инициализация: случайным образом выберите 𝑘 из 𝑚 точек данных в качестве медоидов.
  2. Назначение: свяжите каждую точку данных с ближайшим медоидом на основе расстояния Минковского.
  3. Обновление: для каждого medoid 𝑗 и каждой точки данных 𝑖, связанных с 𝑗, поменяйте местами 𝑗 и 𝑖 и вычислите общую стоимость конфигурации (то есть среднее несходство 𝑖 для всех точек данных, связанных с 𝑗). Выберите medoid 𝑗 с наименьшей стоимостью конфигурации. Переходите между шагами 2 и 3, пока не останется изменений в назначениях.

В следующем коде будет удобно использовать наше обычное соглашение о «матрице данных», то есть в матрице данных 𝑋 каждая строка 𝑥̂ является одним из наблюдений, а каждый столбец 𝑥 - одной из функций. .

1. Инициализация Medoid

Чтобы запустить алгоритм, нам нужна первоначальная догадка. Выберем случайным образом 𝑘 наблюдения из данных. В данном случае 𝑘 = 3, что соответствует 3 различным типам радужной оболочки.

Затем мы создадим функцию init_medoids (X, k), чтобы она случайным образом выбирала 𝑘 из данных наблюдений в качестве медоидов. Он должен вернуть массив NumPy размером 𝑘 × 𝑑, где 𝑑 - количество столбцов X.

После инициализации 3 случайных медоидов из точек данных мы имеем:

2. Расчет расстояний

Реализация функции, которая вычисляет матрицу расстояний, 𝑆 = (s_𝑖𝑗) такая, что s_𝑖𝑗 = 𝑑 ^ 𝑝_𝑖𝑗 - это расстояние Минковского порядка 𝑝 от точки 𝑥_𝑖 до медоида 𝜇_𝑖. Он должен вернуть матрицу NumPy 𝑆 с формой (𝑚, 𝑘).

Порядок ^ Расстояние Минковского между двумя точками, 𝑥 и определяется по формуле:

Таким образом, для элементов матрицы 𝑆

Обычно используется расстояние Минковского, где 𝑝 равно 1 или 2, что соответствует Манхэттенскому расстоянию и Евклидову расстоянию соответственно. В расчетах мы будем использовать евклидово расстояние.

Исходя из этого, первые 5 элементов матрицы S:

3. Назначение кластера

Теперь мы создаем функцию, которая воздействует на матрицу расстояний S, чтобы присвоить «метку кластера» 0, 1, 2 каждой точке, используя минимальное расстояние, чтобы найти «наиболее похожий» медоид.

То есть для каждой точки, обозначенной индексом строки 𝑖, если 𝑠_𝑖𝑗 является минимальным расстоянием для точки 𝑖, то индекс 𝑗 является меткой кластера. Другими словами, функция должна возвращать одномерный массив 𝑦 длины 𝑚 такой, что:

Затем мы получаем метки для точек данных первой итерации:

4. Swap Test

На этом этапе для каждого медоида 𝑗 и каждой точки данных 𝑖, связанных с 𝑗 поменять местами 𝑗 и 𝑖, и вычислить общую стоимость конфигурации (то есть среднее несходство 𝑖 со всеми точками данных, ∑𝑠_𝑖𝑗) как Шаг 3. Выберите medoid 𝑗 с наименьшей стоимостью конфигурации.

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

Наконец, нам также нужна функция, которая проверяет, «переместились» ли медоиды, учитывая два экземпляра значений медоидов. Это функция для проверки того, не перемещаются ли медоиды, и следует ли остановить итерацию.

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

Когда мы объединили все вышеперечисленные функции, мы по сути объединяем шаги алгоритма K-Medoids.

Запустив функцию по имеющимся у нас точкам данных, мы обнаружим, что финальные медоиды будут следующими:

И метки кластера для каждой точки данных:

Рассматривая «неточные» совпадения, приведенный выше алгоритм K-Medoids правильно помечает 94,7% точек данных. Это просто для демонстрации того, как работает алгоритм, и это число не имеет большого значения, поскольку мы не разделили данные на наборы для обучения и тестирования.