Implementación de consulta horizonte o frontera eficiente

Question

Yo sé que debe haber una respuesta fácil a esto, pero de alguna manera me parece que no puede encontrarlo ...

que tiene una trama de datos con 2 columnas numéricas. Me gustaría eliminar de ella, las filas, que tienen la propiedad, que existe al menos otra fila en el marco de datos, con ambos valores de columna más grandes que los de esta fila.

Así que si tengo

Col1 Col2 
1  2 3 
2  4 7 
3  5 6 

Me gustaría eliminar la primera fila, debido a que el segundo cumple la propiedad y mantener sólo las filas 2 y 3.

muchas gracias!

Answer 1

Ese problema se denomina una "consulta de horizonte" por los administradores de bases de datos (pueden tener otros algoritmos) y una "frontera eficiente" por los economistas. Trazar los datos puede dejar en claro lo que estamos buscando.

n <- 40 
d <- data.frame(
    x = rnorm(n), 
    y = rnorm(n) 
) 
# We want the "extreme" points in the following plot 
par(mar=c(1,1,1,1)) 
plot(d, axes=FALSE, xlab="", ylab="") 
for(i in 1:n) { 
    polygon(c(-10,d$x[i],d$x[i],-10), c(-10,-10,d$y[i],d$y[i]), 
    col=rgb(.9,.9,.9,.2)) 
} 

El algoritmo es el siguiente: ordenar los puntos a lo largo de la primera coordenada, mantener a cada observación a menos que sea peor que la anterior retenida uno.

d <- d[ order(d$x, decreasing=TRUE), ] 
result <- d[1,] 
for(i in seq_len(nrow(d))[-1]) { 
    if(d$y[i] > result$y[nrow(result)]) { 
    result <- rbind(result, d[i,]) # inefficient 
    } 
} 
points(result, cex=3, pch=15) 

Answer 2

d <- matrix(c(2, 3, 4, 7, 5, 6), nrow=3, byrow=TRUE) 
d2 <- sapply(d[, 1], function(x) x < d[, 1]) & 
     sapply(d[, 2], function(x) x < d[, 2]) 
d2 <- apply(d2, 2, any) 
result <- d[!d2, ] 

Answer 3

En una línea:

d <- matrix(c(2, 3, 4, 7, 5, 6), nrow=3, byrow=TRUE) 
d[!apply(d,1,max)<max(apply(d,1,min)),] 

    [,1] [,2] 
[1,] 4 7 
[2,] 5 6 

Editar: A la luz de su precisión en la respuesta jbaums', aquí es cómo comprobar si las dos columnas por separado.

d <- matrix(c(2, 3, 3, 7, 5, 6, 4, 8), nrow=4, byrow=TRUE) 
d[apply(d,1,min)>min(apply(d,1,max)) ,] 

    [,1] [,2] 
[1,] 5 6 
[2,] 4 8 

Answer 4

Aquí es una solución sqldf donde DF es la trama de datos de los datos:

library(sqldf) 
sqldf("select * from DF a 
where not exists (
    select * from DF b 
    where b.Col1 >= a.Col1 and b.Col2 > a.Col2 
     or b.Col1 > a.Col1 and b.Col2 >= a.Col2 
)" 
) 

Answer 5

edición (02/03/2015): Para una solución más eficaz, por favor ver Patrick Roocks' rPref, un paquete para "Preferencias de la base de datos y cómputo del horizonte", (también enlazado en su respuesta a continuación). Para mostrar que encuentra la misma solución que mi código aquí, he agregado un ejemplo que lo usa a mi respuesta original aquí.

---

Riffing fuera de la respuesta esclarecedora de Vincent Zoonekynd, aquí es un algoritmo que está totalmente vectorizado, y probablemente más eficiente:

set.seed(100) 
d <- data.frame(x = rnorm(100), y = rnorm(100)) 

D <- d[order(d$x, d$y, decreasing=TRUE), ] 
res <- D[which(!duplicated(cummax(D$y))), ] 
#    x   y 
# 64 2.5819589 0.7946803 
# 20 2.3102968 1.6151907 
# 95 -0.5302965 1.8952759 
# 80 -2.0744048 2.1686003 


# And then, if you would prefer the rows to be in 
# their original order, just do: 
d[sort(as.numeric(rownames(res))), ] 
#   x   y 
# 20 2.3102968 1.6151907 
# 64 2.5819589 0.7946803 
# 80 -2.0744048 2.1686003 
# 95 -0.5302965 1.8952759 

O, utilizando la rPref paquete:

library(rPref) 
psel(d, high(x) | high(y)) 
#    x   y 
# 20 2.3102968 1.6151907 
# 64 2.5819589 0.7946803 
# 80 -2.0744048 2.1686003 
# 95 -0.5302965 1.8952759 

Answer 6

Esta pregunta es bastante antigua, pero mientras tanto hay una nueva solución. Espero que esté bien hacer una auto-promoción aquí: Desarrollé un paquete rPref que hace un cálculo Skyline eficiente debido a los algoritmos C++.Con el paquete rPref instalada la consulta de la pregunta puede hacerse a través de (suponiendo que df es el nombre del conjunto de datos):

library(rPref) 
psel(df, high(Col1) | high(Col2)) 

Esto elimina sólo aquellas tuplas, donde alguna otra tupla es mejor en ambas dimensiones.

Si se requiere que la otra tupla sea estrictamente mejor en una sola dimensión (y mejor o igual en la otra dimensión), use high(Col1) * high(Col2).