2016-02-01 4 views
5

Для алгоритма кластеризации, который я реализую, я хотел бы инициализировать назначения кластеров наугад. Однако мне нужно, чтобы не было пробелов. То есть, это не нормально:Создайте N случайных целых чисел без пробелов

set.seed(2) 
K <- 10 # initial number of clusters 
N <- 20 # number of data points 
z_init <- sample(K,N, replace=TRUE) # initial assignments 
z_init 
# [1] 2 8 6 2 10 10 2 9 5 6 6 3 8 2 5 9 10 3 5 1 
sort(unique(z_init)) 
# [1] 1 2 3 5 6 8 9 10 

где метки 4 и 7 не использовались.

Вместо этого, я хотел бы этот вектор будет:

# [1] 2 6 5 2 8 8 2 7 4 5 5 3 6 2 4 7 8 3 4 1 

где метка 5 становится 4 и так далее, чтобы заполнить пустые ниже метки.

Другие примеры:

  • Вектор 1 2 3 5 6 8 должен быть ̀1 2 3 4 5 6 7
  • Вектор 15,5,7,7,10 должен быть ̀1 2 3 3 4

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

Мое решение с использованием for петли

z_init <- c(3,2,1,3,3,7,9) 

idx <- order(z_init) 
for (i in 2:length(z_init)){ 
    if(z_init[idx[i]] > z_init[idx[i-1]]){ 
    z_init[idx[i]] <- z_init[idx[i-1]]+1 
    } 
    else{ 
    z_init[idx[i]] <- z_init[idx[i-1]] 
    } 

} 

z_init 
# 3 2 1 3 3 4 5 
+0

Извините, но я не знаю вывести логику желаемого вывода. Не могли бы вы уточнить, чего вы пытаетесь достичь? – SabDeM

+0

Возможно, вам придется опубликовать данные о процессе. Определите максимальное количество элементов, отсортируйте их и замените. Функция перекодирования из пакета автомобилей подскакивает. – JJFord3

+0

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

ответ

3

Редактировать: @GregSnow придумал самый короткий ответ. Я на 100% убежден, что это самый короткий путь.

Для удовольствия, я решил golf код, то есть написать его как можно короче:

z <- c(3, 8, 4, 4, 8, 2, 3, 9, 5, 1, 4) 
# solution by hand: 1 2 3 3 4 4 4 5 6 6 7 

sort(c(factor(z))) # 18 bits, as proposed by @GregSnow in the comments 
# [1] 1 2 3 3 4 4 4 5 6 6 7 

Некоторые другие (функционирующие) попытки:

y=table(z);rep(seq(y),y) # 24 bits 
sort(unclass(factor(z))) # 24 bits, based on @GregSnow 's answer 
diffinv(diff(sort(z))>0)+1 # 26 bits 
sort(as.numeric(factor(z))) # 27 bits, @GregSnow 's original answer 
rep(seq(unique(z)),table(z)) # 28 bits 
cumsum(c(1,diff(sort(z))>0)) # 28 bits 
y=rle(sort(z))$l;rep(seq(y),y) # 30 bits 

Edit2: Просто чтобы показать что биты еще не все:

z <- sample(1:10,10000,replace=T) 
Unit: microseconds 
             expr  min  lq  mean median  uq  max neval 
         sort(c(factor(z))) 2550.128 2572.2340 2681.4950 2646.6460 2729.7425 3140.288 100 
    {  y = table(z)  rep(seq(y), y) } 2436.438 2485.3885 2580.9861 2556.4440 2618.4215 3070.812 100 
        sort(unclass(factor(z))) 2535.127 2578.9450 2654.7463 2623.9470 2708.6230 3167.922 100 
      diffinv(diff(sort(z)) > 0) + 1 551.871 572.2000 628.6268 626.0845 666.3495 940.311 100 
       sort(as.numeric(factor(z))) 2603.814 2672.3050 2762.2030 2717.5050 2790.7320 3558.336 100 
      rep(seq(unique(z)), table(z)) 2541.049 2586.0505 2733.5200 2674.0815 2760.7305 5765.815 100 
      cumsum(c(1, diff(sort(z)) > 0)) 530.159 545.5545 602.1348 592.3325 632.0060 844.385 100 
{ y = rle(sort(z))$l  rep(seq(y), y) } 661.218 684.3115 727.4502 724.1820 758.3280 857.412 100 

z <- sample(1:100000,replace=T) 
Unit: milliseconds 
             expr  min  lq  mean median  uq  max neval 
         sort(c(factor(z))) 84.501189 87.227377 92.13182 89.733291 94.16700 150.08327 100 
    {  y = table(z)  rep(seq(y), y) } 78.951701 82.102845 85.54975 83.935108 87.70365 106.05766 100 
        sort(unclass(factor(z))) 84.958711 87.273366 90.84612 89.317415 91.85155 121.99082 100 
      diffinv(diff(sort(z)) > 0) + 1 9.784041 9.963853 10.37807 10.090965 10.34381 17.26034 100 
       sort(as.numeric(factor(z))) 85.917969 88.660145 93.42664 91.542263 95.53720 118.44512 100 
      rep(seq(unique(z)), table(z)) 86.568528 88.300325 93.01369 90.577281 94.74137 118.03852 100 
      cumsum(c(1, diff(sort(z)) > 0)) 9.680615 9.834175 10.11518 9.963261 10.16735 14.40427 100 
{ y = rle(sort(z))$l  rep(seq(y), y) } 12.842614 13.033085 14.73063 13.294019 13.66371 133.16243 100 
+1

Функция 'unclass' может быть заменена' c', иногда полезным, иногда отрицательным побочным эффектом 'c' является то, что он удаляет атрибуты, делая эффект' unclass' здесь. Я не знаю, повлияет ли это на время. Было бы интересно также увидеть тайминги для некоторых больших векторов. Некоторые из алгоритмов могут масштабироваться лучше других. –

+0

... Ничего себе. Я был убежден, что я это пробовал. Видимо, не :) Обновлен ваш ответ и обновлен микрообъект до 10000 и 100000 входов. – Laterow

3

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

Один из подходов, который я мог бы подумать, - выбрать случайную награду r_ij для присвоения элемента i кластеру j. Затем я бы определил двоичные переменные решения x_ij, которые указывают, назначен ли элемент i кластеру j. Наконец, я хотел бы использовать смешанную оптимизацию целого числа, чтобы выбрать назначение из элементов в кластерах, который максимизирует собранное вознаграждение с учетом нижеследующих условий:

  • Каждый элемент присваивается ровно один кластер
  • Каждый кластер имеет по меньшей мере один связанный с ним

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

С точки зрения реализации, это довольно легко сделать в R, используя lpSolve пакет:

library(lpSolve) 
N <- 20 
K <- 10 
set.seed(144) 
r <- matrix(rnorm(N*K), N, K) 
mod <- lp(direction = "max", 
      objective.in = as.vector(r), 
      const.mat = rbind(t(sapply(1:K, function(j) rep((1:K == j) * 1, each=N))), 
          t(sapply(1:N, function(i) rep((1:N == i) * 1, K)))), 
      const.dir = c(rep(">=", K), rep("=", N)), 
      const.rhs = rep(1, N+K), 
      all.bin = TRUE) 
(assignments <- apply(matrix(mod$solution, nrow=N), 1, function(x) which(x > 0.999))) 
# [1] 6 5 3 3 5 6 6 9 2 1 3 4 7 6 10 2 10 6 6 8 
sort(unique(assignments)) 
# [1] 1 2 3 4 5 6 7 8 9 10 
3

Вы могли бы сделать так:

un <- sort(unique(z_init)) 
(z <- unname(setNames(1:length(un), un)[as.character(z_init)])) 
# [1] 2 6 5 2 8 8 2 7 4 5 5 3 6 2 4 7 8 3 4 1 
sort(unique(z)) 
# [1] 1 2 3 4 5 6 7 8 

Здесь я заменить элементы un в z_init с соответствующими элементами 1:length(un).

3

Простым (но, возможно, неэффективным) подходом является преобразование в коэффициент, а затем обратно в числовое. Создание фактора будет кодировать информацию как целые числа от 1 до количества уникальных значений, а затем добавлять метки с исходными значениями. Преобразование в Числовой затем падает этикетки и оставляет номера:

> x <- c(1,2,3,5,6,8) 
> (x2 <- as.numeric(factor(x))) 
[1] 1 2 3 4 5 6 
> 
> xx <- c(15,5,7,7,10) 
> (xx2 <- as.numeric(factor(xx))) 
[1] 4 1 2 2 3 
> (xx3 <- as.numeric(factor(xx, levels=unique(xx)))) 
[1] 1 2 3 3 4 

levels = часть в последнем примере задает число, чтобы соответствовать порядку, в котором они появляются в исходном векторе.

Смежные вопросы