www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Кластеризация K-Medoids на наборе данных радужной оболочки

Дата публикации Oct 24, 2019

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

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

Введение

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

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

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

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

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

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

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

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

Реализация

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

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

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

1. Медоидная инициализация

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

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

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

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

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

Порядок Минковского 𝑝 ^ 𝑡ℎ Расстояние между двумя точками 𝑥 и 𝜇 определяется выражением:

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

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

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

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

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

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

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

4. Своп Тест

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

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

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

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

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

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

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

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

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map