Вы попали в нужное место, если хотите знать, что такое кластеризация K-средних! Давайте быстро приступим к работе!
Вступление
Типы кластеризации
Кластеризация - это тип обучения без учителя, при котором точки данных группируются в разные наборы на основе их степени сходства.
Подробнее о контролируемом / неконтролируемом обучении - Руководство для начинающих по началу работы с машинным обучением
В основном существует две категории кластеризации:
- Иерархическая кластеризация
- Разделение кластеров
Иерархическая кластеризация
Иерархическая кластеризация подразделяется на:
- Агломеративная кластеризация
- Разделительная кластеризация
Иерархическая кластеризация использует древовидную структуру, например:
В агломеративной кластеризации используется восходящий подход. Мы начинаем с каждого элемента как с отдельного кластера и объединяем их в последовательно более массивные кластеры, как показано ниже:
Разделительная кластеризация - это нисходящий подход. Мы начинаем со всего набора и переходим к его разделению на последовательно более мелкие кластеры, как вы можете видеть ниже:
Разбиение на кластеризацию
Кластеризация секционирования подразделяется на:
- Кластеризация K-средних
- Кластеризация нечетких C-средних
Кластеризация секционирования делится на два подтипа - Кластеризация K-средних и Нечеткие C-средние.
При кластеризации K-средних объекты делятся на несколько кластеров, обозначенных номером «K.»
Итак, если мы скажем K = 2, объекты разделятся на два кластера, c1 и c2, как показано:
Здесь сравниваются признаки или характеристики, и все объекты, имеющие схожие характеристики, группируются вместе.
Нечеткое c-средство очень похоже на k-средство в том смысле, что оно объединяет в кластеры объекты со схожими характеристиками. В кластеризации k-средних один объект не может принадлежать двум разным кластерам. Но в c-means объекты могут принадлежать более чем одному кластеру, как показано.
К-означает кластеризацию
K-средство похоже на KNN, потому что оно смотрит на расстояние, чтобы предсказать принадлежность к классу. Однако, в отличие от KNN, K-means - это алгоритм обучения без учителя. Его цель - обнаружить, как разные точки группируются вместе. Интуиция, лежащая в основе этой математической модели, заключается в том, что похожие точки данных будут ближе друг к другу.
Затем K-means пытается определить различные k-точки, называемые центроидами, которые находятся в центре (наименьшее совокупное расстояние) от других точек того же класса, но дальше от точек другого класса.
Этот алгоритм интуитивно понятен, но требует больших вычислительных затрат, поэтому он в основном используется для исследовательского анализа небольших наборов данных.
Подробнее о KNN - Руководство для начинающих по распознаванию рукописных цифр KNN и MNIST с использованием KNN с нуля
Чтобы лучше понять K-means, возьмем пример из крикета. Представьте, что вы получили данные о большом количестве игроков в крикет со всего мира, которые дают информацию о забегах, забитых игроком, и калитках, выполненных им в последних десяти матчах.
Основываясь на этой информации, нам нужно сгруппировать данные в два кластера, а именно игроки с битой и боулеры. Давайте посмотрим, как создать эти кластеры:
Решение
Назначьте точки данных
Здесь у нас есть набор данных, нанесенный на координаты «x» и «y». Информация по оси Y относится к набранным пробежкам, а по оси X - к калиткам, взятым игроками.
Если мы построим график данных, это будет выглядеть так:
Выполнить кластеризацию
Нам нужно создать кластеры, как показано ниже:
Учитывая тот же набор данных, решим задачу с помощью кластеризации K-средних (принимая K = 2). Первым шагом в кластеризации k-средних является случайное распределение двух центроидов (как K = 2). Две точки обозначены как центроиды.
Их называют центроидами, но изначально они не являются центральной точкой данного набора данных.
Следующим шагом является определение расстояния между каждой из точек данных от случайно назначенных центроидов. Для каждой точки расстояние измеряется как от центроидов, и в зависимости от того, какое расстояние меньше, эта точка назначается этому центроиду.
Вы можете увидеть точки данных, прикрепленные к центроидам и представленные здесь синим и желтым цветом.
Следующим шагом является определение фактического центроида для этих двух кластеров. Исходный случайно назначенный центроид должен быть перемещен в фактический центроид кластеров.
Этот процесс вычисления расстояния и изменения положения центроида продолжается до тех пор, пока мы не получим наш последний кластер. Затем перемещение центроида прекращается.
Как видно выше, центроид больше не нуждается в перемещении, и это означает, что алгоритм сошелся, и у нас есть два кластера с центроидом.
Приложения
Кластеризация K-средних используется в различных примерах или практических примерах из реальной жизни, например:
- Академическая успеваемость
- Диагностические системы
- Поисковые системы
- Беспроводные сенсорные сети
Измерение расстояния
Измерение расстояния определяет сходство между двумя элементами и влияет на форму кластеров.
Кластеризация K-средних поддерживает различные виды измерений расстояния, например:
- мера евклидова расстояния
- Измерение расстояния на Манхэттене
- Евклидово расстояние в квадрате
- Косинусное расстояние
Евклидово расстояние
Самый частый случай - определение расстояния между двумя точками. Если у нас есть точки P и Q, евклидово расстояние представляет собой обычную прямую линию. Это расстояние между двумя точками в евклидовом пространстве.
Формула расстояния между двумя точками показана ниже:
Квадратная мера евклидова расстояния
Это идентично измерению евклидова расстояния, но в конце не извлекается квадратный корень. Формула показана ниже:
Манхэттен Измерение расстояния
Манхэттенское расстояние - это простая сумма горизонтальной и вертикальной составляющих или расстояние между двумя точками, измеренное по осям под прямым углом.
Формула показана ниже:
Измерение косинусного расстояния
В данном случае мы берем угол между двумя векторами, образованный путем соединения точек от начала координат. Формула показана ниже:
Подробнее о мерах расстояния см. - Руководство для начинающих по распознаванию рукописных цифр KNN и MNIST с использованием KNN с нуля
Работающий
На приведенной ниже блок-схеме показано, как работает кластеризация K-средних:
Мы можем использовать метод проб и ошибок, указав значение K (= 3,4,5 ..). По мере продвижения мы продолжаем изменять значение, пока не получим лучшие кластеры.
Другой метод - использовать технику локтя для определения значения K.
Как только мы получим значение K, система случайным образом назначит это количество центроидов и измерит расстояние каждой из точек данных от этих центроидов.
Соответственно, он назначает те точки соответствующему центроиду, от которых расстояние минимально. Таким образом, каждой точке данных будет назначен ближайший к ней центроид. Таким образом, у нас есть K начальных кластеров.
Метод локтя - лучший способ определить количество кластеров. Метод локтя представляет собой выполнение кластеризации K-средних для набора данных.
Затем мы используем сумму квадратов в качестве меры, чтобы найти оптимальное количество кластеров, которые могут быть сформированы для данного набора данных. В пределах суммы квадратов (WSS) определяется как сумма квадратов расстояния между каждым элементом кластера и его центроидом.
WSS измеряется для каждого значения K. Значение K, имеющее наименьшее количество WSS, принимается как оптимальное значение.
Теперь мы рисуем кривую между WSS и количеством кластеров.
Здесь WSS находится на оси y, а количество кластеров - на оси x.
Вы можете видеть, что есть очень постепенное изменение в значении WSS, когда значение K увеличивается с 2.
Итак, вы можете принять значение точки локтя как оптимальное значение K. Оно должно быть либо двумя, либо тремя, либо максимум четырьмя. Но, помимо этого, увеличение количества кластеров не меняет кардинально значение в WSS, оно становится стабилизированным.
Алгоритм кластеризации K-средних
Допустим, у нас есть x1, x2, x3 ……… x (n) в качестве входных данных, и мы хотим разделить их на K кластеров.
Формирование кластеров выполняется следующим образом:
Шаг 1. Выберите K случайных точек в качестве центров кластеров, называемых центроидами.
Шаг 2. Назначьте каждый x (i) ближайшему кластеру, реализовав евклидово расстояние (т. е. вычислив расстояние до каждого центроида).
Шаг 3. Определите новые центроиды, взяв среднее значение назначенных точек.
Шаг 4: повторяйте шаги 2 и 3, пока не будет достигнута сходимость!
Давайте подробно рассмотрим каждый из следующих шагов:
Шаг 1
Мы случайным образом выбираем K (центроидов). Мы называем их c1, c2,… .. ck и можем сказать следующее:
Где C - это набор всех центроидов.
Шаг 2
Мы присваиваем каждой точке данных ближайший к ней центр, что достигается путем вычисления евклидова расстояния.
Где dist () - это евклидово расстояние.
Здесь мы вычисляем расстояние между каждым значением x и каждым значением c, то есть расстояние между x1-c1, x1-c2, x1-c3 и т. Д. Затем мы находим наименьшее значение и присваиваем x1 этому конкретному центроиду.
Аналогичным образом находим минимальное расстояние для x2, x3 и т. Д.
Шаг 3
Мы определяем фактический центроид, беря среднее значение всех точек, назначенных этому кластеру.
Где Si - это набор всех точек, назначенных i-му кластеру.
Это означает, что исходная точка, которая, как мы думали, была центроидом, сместится в новое положение, которое является фактическим центроидом для каждой из этих групп.
Шаг 4
Повторяйте шаги 2 и 3 до достижения сходимости.
Когда кластер становится статическим, алгоритм k-средних считается конвергентным.
Дополнительные ресурсы и ссылки
Дополнительные реализации кластеризации K-средних:
Надеюсь, вам понравилась эта статья и вы ее использовали по максимуму! Следите за моими предстоящими блогами! Обязательно выберите CLAP и ПОДПИСАТЬСЯ, если вы найдете мой контент полезным / информативным!
