skyline查询或有效边界的实现

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的，这是一个用于“数据库首选项和天际线计算”的软件包(在他下面的答案中也有链接)。为了表明它找到了与我在这里的代码相同的解决方案，我在这里的原始答案中附加了一个使用它的示例。

这里有一个完全矢量化的算法，它的效率可能更高：

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