在R中選擇n個最遠的點

Question

給定一組xy座標，如何選擇n個點使得這n個點彼此距離最遠？

，可能不會有大的數據集搞得太清楚會是以下低效的方法（識別20分滿分的1000是最遙遠的）：

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的代碼，刪除距離矩陣中行數最大的點。

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

見誰通過查看INTERPOINT距離的和做得最好：對高斯雲，其中m1是@帕斯卡的功能

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

運行

> 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 

Answer 2

繼@ Spacedman的建議下，我有寫了一個函數，從最近的一對中刪除一個點，直到剩下所需的點數。它似乎工作得很好，但是，當你添加點時，它會很快變慢。

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

n <- 20 

subset <- xy 

alldist <- as.matrix(dist(subset)) 
diag(alldist) <- NA 
alldist[upper.tri(alldist)] <- NA 

while (nrow(subset) > n) { 
    closest <- which(alldist == min(alldist,na.rm=T),arr.ind=T) 
    subset <- subset[-closest[1,1],] 
    alldist <- alldist[-closest[1,1],-closest[1,1]] 
}