Разделение на классы: jenks vs kmeans

Я хочу разбить вектор (длина около 10 ^ 5) на пять классов. С помощью функции classIntervals из пакета classInt я хотел использовать естественные разрывы style = "jenks", но это занимает слишком много времени даже для гораздо меньшего вектора всего 500. Настройка style = "kmeans" выполняется почти мгновенно.

library(classInt)

my_n <- 100
set.seed(1)
x <- mapply(rnorm, n = my_n, mean = (1:5) * 5)

system.time(classIntervals(x, n = 5, style = "jenks"))
R> system.time(classIntervals(x, n = 5, style = "jenks"))
   user  system elapsed 
  13.46    0.00   13.45 

system.time(classIntervals(x, n = 5, style = "kmeans"))
R> system.time(classIntervals(x, n = 5, style = "kmeans"))
   user  system elapsed 
   0.02    0.00    0.02

Что делает алгоритм Jenks настолько медленным, и есть ли более быстрый способ его запуска?

Если нужно, я переместлю последние две части вопроса в stats.stackexchange.com:

При каких обстоятельствах километр является разумной заменой Дженксу?
Разумно ли определять классы, запустив classInt на случайном 1% подмножестве точек данных?

Ответ 1

Чтобы ответить на ваш оригинальный вопрос:

Что делает алгоритм Дженкса настолько медленным, и есть более быстрый способ запустить его?

Действительно, между тем существует более быстрый способ применения алгоритма Jenks, setjenksBreaks в пакете BAMMtools.

Однако помните, что вам нужно установить количество разрывов по-разному, то есть, если вы установите разрывы на 5 в функции classIntervals пакета classInt, вы должны установить разрывы на 6 setjenksBreaks в пакете BAMMtools, чтобы получить те же результаты.

# Install and load library
install.packages("BAMMtools")
library(BAMMtools)

# Set up example data
my_n <- 100
set.seed(1)
x <- mapply(rnorm, n = my_n, mean = (1:5) * 5)

# Apply function
getJenksBreaks(x, 6)

Скорость вверх огромна, т.е.

> microbenchmark( getJenksBreaks(x, 6, subset = NULL),  classIntervals(x, n = 5, style = "jenks"), unit="s", times=10)
Unit: seconds
                                      expr         min          lq        mean      median          uq         max neval cld
       getJenksBreaks(x, 6, subset = NULL) 0.002824861 0.003038748 0.003270575 0.003145692 0.003464058 0.004263771    10  a 
 classIntervals(x, n = 5, style = "jenks") 2.008109622 2.033353970 2.094278189 2.103680325 2.111840853 2.231148846    10

Ответ 2

Из ?BAMMtools::getJenksBreaks

Метод естественных разрывов Дженкса был портирован на C из кода, найденного в пакете classInt R.

Две программы одинаковы; один быстрее другого из-за их реализации (C против R).