执行天际线查询或有效前沿

Question

我知道必须有一个简单的答案,但不知怎的,我似乎无法找到它...

我有一个包含2个数字列的数据框.我想从中删除具有属性的行,数据框中至少存在另一行,其中两列值都大于此行中的列值.

所以,如果我有

    Col1 Col2  
1     2    3  
2     4    7  
3     5    6  

我想删除第一行,因为第二行符合属性并且只保留第2行和第3行.

非常感谢!

Answer 1

这个问题被数据库管理员称为"天际线查询"(他们可能有其他算法)和经济学家的"有效前沿".绘制数据可以清楚地表明我们在寻找什么.

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

算法如下:沿第一个坐标对点进行排序,保持每个观察值,除非它比最后保留的点更差.

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

编辑(2015-03-02):有关更高效的解决方案,请参阅Patrick Roocks的rPref,这是一个"数据库偏好和Skyline计算"的软件包(也在下面的答案中链接).为了表明它找到了与我的代码相同的解决方案,我在这里添加了一个使用它的示例到我的原始答案.

重温Vincent Zoonekynd的启发性反应,这是一个完全矢量化的算法,可能更有效:

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

或者,使用rPref包:

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 3

这是一个sqldf解决方案,其中DF是数据的数据框:

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