所以我试图计算 R
中的帕累托前沿( http://en.wikipedia.org/wiki/Pareto_efficiency )并且能够做到,但是,我无法有效地做到这一点。特别是随着点对数量的增加,计算速度会大大减慢。
所以总的来说,我想要做的是检查所有非支配(或支配)对。现在我一直这样做的方法是找到所有这样的点对 xi > X
和 易 > 是 哪里 (xi, yi) 是一对和 X 和 是 代表所有点 x 和 y .现在,这部分工作非常快并且易于实现,但是,还有多个 的额外可能性。 x 值可能相同但它们会有不同 y 值所以在这种情况下我希望能够识别 x 具有最低值 y 值(反之亦然,对于具有相同 y 值但不同 x 值的点)。
为了说明这一点,这里有一张来自维基百科的图片:
所以基本上我希望能够识别位于红线上的所有点。
这是我的代码确实有效,但对于大型数据集效率很低:
#Example Data that actually runs quickly
x = runif(10000)
y = runif(10000)
pareto = 1:length(x)
for(i in 1:length(x)){
cond1 = y[i]!=min(y[which(x==x[i])])
cond2 = x[i]!=min(x[which(y==y[i])])
for(n in 1:length(x)){
if((x[i]>x[n] & y[i]>y[n]) | (x[i]==x[n] & cond1) | (y[i]==y[n] & cond2)){
pareto[i] = NA
break
}
}
}
#All points not on the red line should be marks as NA in the pareto variable
减速肯定来自计算点
(x[i]==x[n] & cond1) | (y[i]==y[n] & cond2)
但我找不到解决方法或更好的 bool 表达式来捕获我想要的所有内容。非常感谢任何建议!
最佳答案
关注@BrodieG
system.time( {
d = data.frame(x,y)
D = d[order(d$x,d$y,decreasing=FALSE),]
front = D[which(!duplicated(cummin(D$y))),]
} )
user system elapsed
0.02 0.00 0.02
这是 0.86/0.02 = 43 倍快!
关于r - R中帕累托前沿的快速计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21294829/