Attuazione della interrogazione orizzonte o di frontiera efficiente

Question

So che ci deve essere una risposta facile a questo, ma in qualche modo io non riesco a trovarlo ...

Ho un frame di dati con 2 colonne numeriche. Vorrei rimuovere da esso, le righe, che hanno la proprietà, che esiste almeno un'altra riga nel frame di dati, con entrambi i valori di colonna più grandi di quelli in questa riga.

Quindi, se ho

Col1 Col2 
1  2 3 
2  4 7 
3  5 6 

Vorrei rimuovere la prima fila, perché il secondo compie la proprietà e mantenere solo le righe 2 e 3.

grazie mille!

Answer 1

Questo problema è chiamato "query dell'orizzonte" dagli amministratori di database (possono avere altri algoritmi) e una "frontiera efficiente" da parte degli economisti. Tracciare i dati può chiarire cosa stiamo cercando.

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)) 
} 

L'algoritmo è il seguente: ordinare i punti lungo la prima coordinata, mantenere ogni osservazione meno che non sia peggiore del precedente trattenuto 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

In una sola riga:

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 

Edit: Alla luce della vostra precisione in risposta jbaums', ecco come fare per verificare la presenza di entrambe le colonne separatamente.

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

Ecco una soluzione sqldf dove DF è la cornice del trattamento dei dati:

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

Edit (2015/03/02): Per una soluzione più efficiente, si prega di consultare Patrick Roocks' rPref, un pacchetto per "Database Preferences e Skyline Computation", (anch'esso collegato nella sua risposta di seguito). Per dimostrare che trova qui la stessa soluzione del mio codice, ho aggiunto un esempio che lo usa alla mia risposta originale qui.

---

riffing off di risposta illuminante di Vincent Zoonekynd, ecco un algoritmo che è pienamente vettorializzare, e probabilmente più efficiente:

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 

Oppure, utilizzando il RPREF pacchetto:

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

Questa domanda è piuttosto vecchia, ma nel frattempo c'è una nuova soluzione. Spero che sia giusto fare un po 'di auto-promozione qui: ho sviluppato un pacchetto rPref che esegue un efficiente calcolo Skyline grazie agli algoritmi C++.Con il pacchetto RPREF installato query dalla questione può essere fatta tramite (supponendo che df è il nome del set di dati):

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

Questo rimuove solo le tuple, dove un altro tupla migliori in entrambe le dimensioni.

Se si richiede che l'altra tupla sia strettamente migliore in una sola dimensione (e migliore o uguale nell'altra dimensione), utilizzare invece high(Col1) * high(Col2).