选择R中最远的n个点

Question

给定一组xy坐标,我如何选择n个点,使得这些n个点彼此距离最远？

对于大数据集可能不会做得太好的低效方法如下(确定最远的1000个中的20个点):

xy <- cbind(rnorm(1000),rnorm(1000))

n <- 20
bestavg <- 0
bestSet <- NA
for (i in 1:1000){
    subset <- xy[sample(1:nrow(xy),n),]
    avg <- mean(dist(subset))
    if (avg > bestavg) {
        bestavg <- avg
        bestSet <- subset
    }
}

Answer 1

此代码基于Pascal的代码,删除距离矩阵中具有最大行和的点.

m2 <- function(xy, n){

    subset <- xy

    alldist <- as.matrix(dist(subset))

    while (nrow(subset) > n) {
        cdists = rowSums(alldist)
        closest <- which(cdists == min(cdists))[1]
        subset <- subset[-closest,]
        alldist <- alldist[-closest,-closest]
    }
    return(subset)
}

在高斯云上运行,m1@ pascal的功能在哪里:

> set.seed(310366)
> xy <- cbind(rnorm(1000),rnorm(1000))
> m1s = m1(xy,20)
> m2s = m2(xy,20)

通过查看点间距离的总和来查看谁做得最好:

> sum(dist(m1s))
[1] 646.0357
> sum(dist(m2s))
[1] 811.7975

方法2获胜!并与随机抽样的20分进行比较:

> sum(dist(xy[sample(1000,20),]))
[1] 349.3905

这与预期相当糟糕.

发生什么了？我们的情节:

> plot(xy,asp=1)
> points(m2s,col="blue",pch=19)
> points(m1s,col="red",pch=19,cex=0.8)

方法1生成红点,红点在空间上均匀分布.方法2创建蓝点,几乎定义周长.我怀疑这个原因很容易解决(在一个维度上更容易......).

使用双峰模式的初始点也说明了这一点:

并且方法2产生的总和距离远远大于方法1,但两者都比随机抽样更好:

> sum(dist(m1s2))
[1] 958.3518
> sum(dist(m2s2))
[1] 1206.439
> sum(dist(xy2[sample(1000,20),]))
[1] 574.34