實施輪廓查詢或有效邊界

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

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

在一個行：

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 

編輯：在jbaums的迴應你的精密光亮，這裏是如何單獨檢查兩個列。

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

下面是一個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 
)" 
) 

Answer 5

編輯（2015年3月2日）：對於更有效的解決方案，請參閱帕特里克Roocks' rPref，用於「數據庫首選項和天際線計算」的包（也在以下答案中鏈接）。爲了表明它找到與我的代碼相同的解決方案，我在這裏附加了一個使用它的例子。

---

Riffing關文森特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 6

這個問題很舊，但同時有一個新的解決方案。我希望在這裏做一些自我推銷是可以的：我開發了一個包rPref，它由於C++算法而進行了有效的Skyline計算。安裝RPREF包從查詢有問題可以通過（假設df是數據集的名稱）來完成：

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

這消除了只有那些元組，其中一些其他的元組是在兩個維度上更好。

如果需要另一個元組在一個維度上嚴格更好（並且在另一個維度上更好或相等），請改爲使用high(Col1) * high(Col2)。