nstart для k-средних в R - PullRequest
Новая
       107

nstart для k-средних в R

0 голосов
/ 08 мая 2020

Результаты поиска во многих местах сообщают, что аргумент nstart в функции R kmeans устанавливает количество итераций алгоритма и выбирает «лучший», см., Например, https://datascience.stackexchange.com/questions/11485/k-means-in-r-usage-of-nstart-parameter. Может ли кто-нибудь прояснить , как это делает, т.е. по какой мере он определяет лучше всего?

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

В общем, поэтому я ищу способ получить хороший (например, лучший из $ n $ проб или лучший из nstart) набор начальных экземпляров данных из набора данных в качестве начальных центроидов. Есть ли способ извлечь «выигрышный» (= лучший) набор начальных центроидов из nstart (который я мог бы затем использовать, скажем, в параметре centers в будущем)? Любой другой упрощенный и быстрый способ получить очень хороший набор начальных центроидов (предположительно, достаточно близко к тому месту, где в конечном итоге окажутся центры кластеров)?

Есть ли, по крайней мере, способ извлечения из учитывая запуск kmeans, какие начальные центроиды он выбрал для начала?

1 Ответ

0 голосов
/ 08 мая 2020

Критерий, который kmeans пытается минимизировать, - это трассировка внутренней матрицы разброса, т.е. (к сожалению, этот форум не поддерживает LaTeX, но вы, надеюсь, все же можете его прочитать):

$$ trace (S_w ) = \ sum_ {k = 1} ^ K \ sum {x \ in C_k} || x - \ mu_k || ^ 2 $$

Что касается наилучшей отправной точки: очевидно, «наилучшая» отправная точка точкой будут центры кластеров, в конечном итоге выбранные kmeans . Они возвращаются в атрибуте center : 

km <- kmeans(iris[,-5], 3)
print(km$centers)

Если вы ищете лучшую случайную начальную точку, вы можете сами создать случайные начальные точки (с runif ), проделайте это nstart раз и оцените, какая начальная конфигурация приводит к наименьшему km $ tot.winss : 

nstart <- 10
K <- 3 # number of clusters
D <- 4 # data point dimension

# select possible range
r.min <- apply(iris[,-5], MARGIN=2, FUN=min)
r.max <- apply(iris[,-5], MARGIN=2, FUN=max)

for (i in 1:nstart) {
  centers <- data.frame(runif(K, r.min[d], r.max[d]))
  for (d in 2:D) {
    centers <- cbind(centers, data.frame(runif(K, r.min[d], r.max[d])))
  }
  names(centers) <- names(iris[,-5])

  # call kmeans with centers and compare tot.withinss
  # ...
}
...