комбинаторной оптимизации в R

Question

Пример моего набора данных выглядит следующим образом:

df = data.frame(cbind(a = c(1,3,5), b = c(4,1,7), c = c(1,9,10))) 
y = c(8, 9, 20) 

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

Например, найти самую сильную корреляцию между всеми этими комбинациями:

cor(df$a, y) 
cor(df$b, y) 
cor(df$c, y) 
cor(df$a+df$b, y) 
cor(df$a+df$c, y) 
cor(df$b+df$c, y) 
cor(df$a+df$b+df$c, y) 

Мой текущий метод:

combination = list() 
for(i in 1:3){combination[[i]]=c(NA,1)} 
names(combination) = c("a", "b", "c") 
combi = arrange(expand.grid(combination), a) 

combi = mutate(combi, cor = NA) 

for (i in 1:2^3){ 
    x = as.numeric(combi[i,]) 
    col = x*c(1:3) 
    col = col[!is.na(col)] 

    if(length(col)>1){ 
    t = rowSums(df[, col]) 
    combi[i, 4] = cor(t,y) 
    } 

    if(length(col)==1){ 
    t = df[, col] 
    combi[i, 4] = cor(t,y) 
    } 

    if(length(col)==0){ 
    combi[i, 4] = NA 
    } 

} 

Есть простой способ оценить все возможные комбинации? Когда общее число столбцов увеличивается, становится очень трудно найти все комбинации. Какую стратегию я должен использовать здесь, чтобы найти наилучшую комбинацию (только локальную оптимизацию) в рамках ограниченных шагов? Как насчет пошагового выбора вперед/назад?

В этом случае модели не существует. Говоря вперед/назад пошаговый выбор, я имею в виду аналогичный метод, как то, что люди делают с регрессионными моделями: Вместо поиска всех возможных комбинаций столбцов все сразу начинайте с каждого столбца индивидуально и найдите тот, который имеет самую сильную корреляцию. Затем рассмотрите только комбинации, которые включают этот столбец.

Большое вам спасибо за советы!

Answer 1

Я не знаю, если есть пакеты вокруг, чтобы сделать всю оценку, но цикл по все возможные случаи могут быть более эффективными с использованием combn:

# basic data 
df = data.frame(cbind(a = c(1,3,5), b = c(4,1,7), c = c(1,9,10))) 
y = c(8, 9, 20) 

# do single correlations first, since the following code with apply refuses single columns 
cors<-data.frame(m=NA,cc=NA) # define cors to collect results 

for (i in 1:ncol(df)){ 
    cors[i,1]<-1 
    cors[i,2]<-cor(df[,i],y) 
} 

# the following code uses combn to find all combinations and perform a function on them, with correlations as result. These are stored in cors 

for (m in 2:ncol(df)){ 
    cv<-combn(ncol(df),m,FUN=function(x) cor(apply(df[,x],1,sum),y)) 
    cors[(i+1):(i+length(cv)),2]<-cv 
    cors[(i+1):(i+length(cv)),1]<-m 
    i<-i+length(cv) 
} 

print(cors) 

Что дает:

m  cc 
1 1 0.9011271 
2 1 0.8260332 
3 1 0.6444459 
4 2 0.9819805 
5 2 0.7317957 
6 2 0.9385110 
7 3 0.9299975 

Где m дает вам количество столбцов в сочетании и cc корреляцию. С некоторыми улучшениями вы также можете сохранить состав комбинации в том же кадре данных, но вы также можете сначала выбрать максимум, а затем узнать, какая комбинация дает максимальный (в этом случае первое значение с m = 2, который указан как combn(ncol(df),m)[,1])