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

Это руководство служит введением в метод кластеризации k-средних.

  1. Требования к репликации: что вам понадобится для воспроизведения анализа в этом руководстве
  2. Подготовка данных: подготовка данных для кластерного анализа
  3. Кластеризация мер расстояния: понимание того, как измерять различия в наблюдениях
  4. Кластеризация K-средних: расчеты и методы для создания K подгрупп данных
  5. Определение оптимальных кластеров: определение правильного количества кластеров для группировки данных

Требования к репликации

Чтобы воспроизвести анализ этого руководства, вам необходимо загрузить следующие пакеты:

library(tidyverse)  # data manipulation
library(cluster)    # clustering algorithms
library(factoextra) # clustering algorithms & visualization

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

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

  1. Строки - это наблюдения (отдельные лица), а столбцы - переменные.
  2. Любое отсутствующее значение в данных должно быть удалено или оценено.
  3. Данные должны быть стандартизированы (т. Е. Масштабированы), чтобы сделать переменные сопоставимыми. Напомним, что стандартизация заключается в преобразовании переменных таким образом, чтобы они имели нулевое среднее значение и единичное стандартное отклонение.

Здесь мы будем использовать набор данных об отелях в Индонезии, состоящий из отелей от одной звезды до пятизвездочных отелей в 34 провинциях Индонезии.

Hotel = read.delim("clipboard")
View(Hotel)

теперь делает провинциальную переменную именем столбца, поэтому она не включается в кластеризацию.

hotel = Hotel[,c(2:6)]
rownames(hotel) <- Hotel$Provinsi[1:34]

Сам кластерный метод чувствителен к отсутствующему значению в данных, поэтому необходимо сначала проверить отсутствующее значение. Если есть пропущенное значение, необходимо обработать данные, часто люди обрабатывают недостающее значение, удаляя эти наблюдения из данных, но это не лучший способ обработки, который не объясняется в этой статье. . так как узнать недостающее значение в данных?

summary(is.na(hotel))

Судя по выходным данным, в данных нет пропущенных значений.

Если переменные переменные в данных имеют разные единицы измерения, то сначала необходимо стандартизировать данные.

df <- scale(hotel[-1])
head(df)

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

Кластеризация мер расстояния

Для классификации наблюдений по группам требуются некоторые методы для вычисления расстояния или (несходства) между каждой парой наблюдений. Результат этого вычисления известен как матрица несходства или расстояния. Есть много методов для вычисления этой информации о расстоянии; выбор меры расстояния является критическим шагом в кластеризации. Он определяет, как вычисляется схожесть двух элементов (x, y), и влияет на форму кластеров.

Выбор меры расстояния - важный шаг в кластеризации. Он определяет, как вычисляется схожесть двух элементов (x, y), и влияет на форму кластеров. Классическими методами измерения расстояния являются евклидово и манхэттенское расстояние, которые определены следующим образом:

Евклидово расстояние:

Расстояние до Манхэттена:

Где x и y - два вектора длины n.

Существуют и другие меры несходства, такие как расстояния на основе корреляции, которые широко используются для анализа данных экспрессии генов. Расстояние на основе корреляции определяется путем вычитания коэффициента корреляции из 1. Могут использоваться различные типы методов корреляции, такие как:

Расстояние корреляции Пирсона:

Расстояние корреляции Спирмена:

Метод корреляции Спирмена вычисляет корреляцию между рангом x и рангом переменных y.

В R легко вычислить и визуализировать матрицу расстояний с помощью функций get_dist и fviz_dist из пакета factoextra R. Это начинает показывать, какие состояния имеют большие различия (красный цвет) по сравнению с теми, которые кажутся довольно похожими (бирюзовый).

  • get_dist: для вычисления матрицы расстояний между строками матрицы данных. По умолчанию вычисляется евклидово расстояние; однако get_dist также поддерживает дистанционное управление, описанное в уравнениях 2-5 выше, а также другие.
  • fviz_dist: для визуализации матрицы расстояний
distance <- get_dist(hotel[-1])
fviz_dist(distance, gradient = list(low = "#00AFBB", mid = "white", high = "#FC4E07"))

Кластеризация K-средних

Кластеризация K-средних - это наиболее часто используемый алгоритм машинного обучения без учителя для разделения заданного набора данных на набор из k групп (т. Е. k кластеров), где k представляет количество групп, предварительно определенное аналитиком. Он классифицирует объекты по нескольким группам (т. Е. Кластерам), так что объекты в одном и том же кластере являются как можно более похожими (т. Е. Высокое внутриклассовое сходство), тогда как объекты из разных кластеров как можно более различны (т. Е. Низкое межклассовое сходство). классовое сходство). При кластеризации k-средних каждый кластер представлен своим центром (т. Е. Центроидом), который соответствует среднему значению точек, присвоенных кластеру.

Основная мысль

Основная идея кластеризации k-средних состоит в определении кластеров таким образом, чтобы общая вариация внутри кластера (известная как общая вариация внутри кластера) была сведена к минимуму. Доступно несколько алгоритмов k-средних. Стандартный алгоритм - это алгоритм Хартигана-Вонга (1979), который определяет общую вариацию внутри кластера как сумму квадратов евклидовых расстояний между элементами и соответствующим центроидом:

где:

  • xi - точка данных, принадлежащая кластеру Ck
  • μk - среднее значение точек, отнесенных к кластеру Ck

Каждое наблюдение (xi) назначается данному кластеру, так что сумма квадратов (SS) расстояния наблюдения до назначенных им центров кластера (μk) минимизирована.

Мы определяем общую вариацию внутри кластера следующим образом:

Общая сумма квадратов внутри кластера измеряет компактность (то есть качество) кластеризации, и мы хотим, чтобы она была как можно меньше.

Алгоритм K-средних

Первый шаг при использовании кластеризации k-средних - указать количество кластеров (k), которые будут сгенерированы в окончательном решении. Алгоритм начинается со случайного выбора k объектов из набора данных, которые служат начальными центрами для кластеров. Выбранные объекты также известны как средние кластеры или центроиды. Затем каждому из оставшихся объектов присваивается ближайший к нему центроид, где ближайший определяется с использованием евклидова расстояния (уравнение 1) между объектом и средним значением кластера. Этот шаг называется «этапом назначения кластера». После этапа присваивания алгоритм вычисляет новое среднее значение для каждого кластера. Термин «кластерное обновление центроидов» используется для разработки этого шага. Теперь, когда центры были пересчитаны, каждое наблюдение проверяется снова, чтобы увидеть, может ли оно быть ближе к другому кластеру. Все объекты повторно переназначаются обновленными средствами кластера. Этапы назначения кластера и обновления центроида повторяются итеративно до тех пор, пока назначения кластера не перестанут меняться (т. Е. Пока не будет достигнута сходимость). То есть кластеры, сформированные в текущей итерации, такие же, как кластеры, полученные в предыдущей итерации.

Алгоритм K-средних можно резюмировать следующим образом:

  1. Укажите количество кластеров (K), которые должны быть созданы (аналитиком)
  2. Выбрать случайным образом k объектов из набора данных в качестве начальных центров кластера или средних значений.
  3. Присваивает каждому наблюдению ближайший центроид на основе евклидова расстояния между объектом и центроидом.
  4. Для каждого из k кластеров обновите центроид кластера, вычислив новые средние значения всех точек данных в кластере. Центроид K-го кластера - это вектор длины p, содержащий средние значения всех переменных для наблюдений в k-м кластере; p - количество переменных.
  5. Итеративно минимизируйте общую сумму в пределах суммы квадратов (уравнение 7). То есть повторяйте шаги 3 и 4, пока назначения кластера не перестанут меняться или пока не будет достигнуто максимальное количество итераций. По умолчанию программное обеспечение R использует 10 в качестве значения по умолчанию для максимального количества итераций.

Вычисление кластеризации k-средних в R

Мы можем вычислить k-средние в R с помощью функции kmeans. Здесь данные сгруппированы в два кластера (centers = 2). Функция kmeans также имеет параметр nstart, который пытается выполнить несколько начальных конфигураций и сообщает о наилучшей из них. Например, добавление nstart = 25 сгенерирует 25 начальных конфигураций. Этот подход часто рекомендуется.

k2 <- kmeans(hotel, centers = 2, nstart = 25)
str(k2)
## List of 9 
##  $ cluster     : Named int [1:34] 1 2 2 2 1 2 1 1 ...
##   ..- attr(*, "names")= chr [1:534 "1" "2" "3" "4" ...
##  $ centers     : num [1:2, 1:4] 2.36 55.08 43.78 ...
##   ..- attr(*, "dimnames")=List of 2
##   .. ..$ : chr [1:2] "1" "2"
##   .. ..$ : chr [1:5] "Start.5" "Start.4" "Start.3" "Start.2"
##  $ totss       : num 4981
##  $ withinss    : num [1:2] 17944 6575
##  $ tot.withinss: num 24519
##  $ betweenss   : num 25322
##  $ size        : int [1:2] 15 19
##  $ iter        : int 1
##  $ ifault      : int 0
##  - attr(*, "class")= chr "kmeans"
  • cluster: вектор целых чисел (от 1: k), указывающий кластер, которому назначена каждая точка.
  • centers: Матрица центров кластеров.
  • totss: Общая сумма квадратов.
  • withinss: вектор суммы квадратов внутри кластера, один компонент на кластер.
  • tot.withinss: Общая сумма квадратов внутри кластера, т. Е. Сумма (в пределах).
  • betweenss: Сумма квадратов между кластерами, то есть $ totss-tot.withinss $.
  • size: количество точек в каждом кластере.

Если мы распечатаем результаты, мы увидим, что наши группировки привели к 2 размерам кластеров: 15 и 19. Мы видим центры кластеров (средние значения) для двух групп по четырем переменным (1 = Ачех, 2 = Суматра Утара, 3 = Суматра Барат, 4 = Риау). Мы также получаем назначение кластера для каждого наблюдения (т. Е. Ачех был назначен кластеру 1, Суматра Утара был назначен кластеру 2 и т. Д.).

k2

Мы также можем просмотреть наши результаты, используя fviz_cluster. Это хорошая иллюстрация кластеров. Если имеется более двух измерений (переменных), fviz_cluster выполнит анализ главных компонентов (PCA) и построит точки данных в соответствии с первыми двумя основными компонентами, которые объясняют большую часть дисперсии.

fviz_cluster(k2, data = hotel)

Поскольку количество кластеров (k) должно быть установлено до того, как мы запустим алгоритм, часто бывает полезно использовать несколько различных значений k и изучить различия в результатах. Мы можем выполнить тот же процесс для 3, 4 и 5 кластеров, и результаты показаны на рисунке:

k3 <- kmeans(hotel, centers = 3, nstart = 25)
k4 <- kmeans(hotel, centers = 4, nstart = 25)
k5 <- kmeans(hotel, centers = 5, nstart = 25)
# plots to compare
p1 <- fviz_cluster(k2, geom = "point", data = hotel[-1]) + ggtitle("k = 2")
p2 <- fviz_cluster(k3, geom = "point",  data = hotel[-1]) + ggtitle("k = 3")
p3 <- fviz_cluster(k4, geom = "point",  data = hotel[-1]) + ggtitle("k = 4")
p4 <- fviz_cluster(k5, geom = "point",  data = hotel[-1]) + ggtitle("k = 5")
library(gridExtra)
grid.arrange(p1, p2, p3, p4, nrow = 2)

Хотя эта визуальная оценка говорит нам, где происходят истинные удлинения (или не возникают, например, кластеры 2 и 4 на графике k = 5) между кластерами, она не говорит нам об оптимальном количестве кластеров.

Определение оптимальных кластеров

Как вы помните, аналитик указывает количество используемых кластеров; желательно, чтобы аналитик хотел использовать оптимальное количество кластеров. В помощь аналитику ниже объясняются три наиболее популярных метода определения оптимальных кластеров, в том числе:

  1. Локтевой метод
  2. Силуэтный метод
  3. Статистика разрыва

Метод локтя

Напомним, что основная идея методов разделения кластеров, таких как кластеризация k-средних, состоит в том, чтобы определить кластеры таким образом, чтобы общая вариация внутри кластера (известная как общая вариация внутри кластера или общая сумма квадратов внутри кластера) была минимальной:

где Ck - k-й кластер, а W (Ck) - вариация внутри кластера. Общая сумма квадратов внутри кластера (wss) измеряет компактность кластеризации, и мы хотим, чтобы она была как можно меньше. Таким образом, мы можем использовать следующий алгоритм для определения оптимальных кластеров:

  1. Вычислить алгоритм кластеризации (например, кластеризацию k-средних) для различных значений k. Например, изменяя k от 1 до 10 кластеров.
  2. Для каждого k рассчитайте общую сумму квадратов внутри кластера (wss)
  3. Постройте кривую wss в соответствии с количеством кластеров k.
  4. Расположение изгиба (изгиба) на графике обычно рассматривается как индикатор соответствующего количества кластеров.

Мы можем реализовать это в R с помощью следующего кода. Результаты показывают, что 3 - это оптимальное количество кластеров, поскольку это похоже на изгиб колена (или локтя).

К счастью, этот процесс вычисления «метода локтя» был заключен в одну функцию (fviz_nbclust):

set.seed(123)
fviz_nbclust(hotel, kmeans, method = "wss")

Метод среднего силуэта

Короче говоря, подход среднего силуэта измеряет качество кластеризации. То есть он определяет, насколько хорошо каждый объект находится в своем кластере. Высокая средняя ширина силуэта указывает на хорошую кластеризацию. Метод среднего силуэта вычисляет средний силуэт наблюдений для различных значений k. Оптимальное количество кластеров k - это то, которое максимизирует средний силуэт в диапазоне возможных значений для k

Мы можем использовать функцию silhouette в пакете кластеров, чтобы вычислить среднюю ширину силуэта. Следующий код вычисляет этот подход для 1-15 кластеров. Результаты показывают, что 2 кластера максимизируют средние значения силуэта, при этом 4 кластера входят в качестве второго оптимального числа кластеров.

fviz_nbclust(hotel, kmeans, method = "silhouette")

Статистический метод разрыва

Статистику разрыва опубликовал R. Тибширани, Г. Вальтер и Т. Хасти (Стэндфордский университет, 2001 г.) . Подход может быть применен к любому методу кластеризации (например, кластеризация с использованием K-средних, иерархическая кластеризация). Статистика разрыва сравнивает общую внутрикластерную вариацию для различных значений k с их ожидаемыми значениями при нулевом эталонном распределении данных (т. Е. Распределении без очевидной кластеризации). Базовый набор данных создается с использованием моделирования процесса выборки методом Монте-Карло. То есть для каждой переменной (xi) в наборе данных мы вычисляем ее диапазон [min (xi), max (xj)] [min (xi), max (xj)] и генерируем значения для n точек равномерно из интервала от мин до макс.

Чтобы вычислить метод статистики разрыва, мы можем использовать функцию clusGap, которая предоставляет статистику разрыва и стандартную ошибку для выходных данных.

# compute gap statistic
set.seed(123)
gap_stat <- clusGap(df, FUN = kmeans, nstart = 25,
                    K.max = 10, B = 50)
# Print the result
print(gap_stat, method = "firstmax")
# Visual
fviz_gap_stat(gap_stat)

Извлечение результатов

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

set.seed(123)
final <- kmeans(hotel, 3, nstart = 25)
print(final)

Мы можем визуализировать результаты, используя fviz_cluster:

fviz_cluster(final, data = hotel[-1])

Заключение

Затем мы отобразим фрейм данных тестовых данных, которые были добавлены с результатами кластера, как показано ниже.

df.cluster = data.frame(hotel, final$cluster)
View(df.cluster)

мы увидим следующие характеристики каждого существующего кластера:

k1.1 = subset(df.cluster, k2.cluster == 1)
k1.2 = subset(df.cluster, k2.cluster == 2)
k1.3 = subset(df.cluster, k2.cluster == 3)
meank1.1 = sapply(k1.1, mean)
meank1.2 = sapply(k1.2, mean)
meank1.3 = sapply(k1.3, mean)
mean.tot = rbind(meank1.1, meank1.2, meank1.3)
barplot(t(mean.tot[,-6]), beside = TRUE)

По графику мы знаем, что:

  • В первый кластер входят провинции, которые имеют лучшее качество как 4-звездочных отелей, так и 3-звездочных отелей по сравнению с кластером 2, но не имеют 5-звездочных отелей и имеют самые низкие 1-звездочные гостиничные услуги по сравнению с кластером 2 и кластером. 3.
  • Во второй кластер входят провинции, которые имеют лучшее качество 1-звездочных отелей и 2-звездочных отелей по сравнению с кластерами 1 и 3, но имеют самое низкое качество 3-звездочных отелей и 4-звездочных отелей, но имеют лучшие 5-звездочные отели. отели по сравнению с первым кластером
  • В кластер 3 входят провинции, которые имеют лучшее качество как 5-звездочных отелей, так и 3-звездочных отелей по сравнению с кластером 1 и кластером 2, и имеют качественные 2-звездочные отели, которые почти так же хороши, как кластер 2, и имеют лучшие Качество 1-звездочного отеля по сравнению с кластером 1.

Дополнительные комментарии

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

Одним из потенциальных недостатков кластеризации K-средних является то, что она требует от нас заранее указать количество кластеров. Иерархическая кластеризация - это альтернативный подход, который не требует от нас привязки к конкретному выбору кластеров. Иерархическая кластеризация имеет дополнительное преимущество перед кластеризацией K-средних в том, что она приводит к привлекательному древовидному представлению наблюдений, называемому дендрограммой. В следующем учебном пособии будет продемонстрирован подход иерархической кластеризации.

Дополнительным недостатком K-средних является то, что они чувствительны к выбросам, и могут возникнуть разные результаты, если вы измените порядок данных. Подход кластеризации Partitioning Around Medoids (PAM) менее чувствителен к выбросам и обеспечивает надежную альтернативу k-средствам для работы в таких ситуациях. В следующем учебном пособии будет продемонстрирован подход к кластеризации PAM.

Использованная литература :

Https://uc-r.github.io/kmeans_clustering