r - 计算R中的稀疏成对距离矩阵

Question

我有一个NxM矩阵，我想计算NxN点之间的欧几里得距离的M矩阵。在我的问题中，N约为100,000。当我计划将此矩阵用于k最近邻算法时，我只需要将k保持最小的距离，因此生成的NxN矩阵非常稀疏。例如，这与dist()产生的结果相反，后者会导致矩阵密集(可能是我的大小N的存储问题)。

到目前为止，我发现的kNN软件包(knnflex，kknn等)似乎都使用密集矩阵。另外，Matrix包不提供成对距离函数。

接近我的目标，我看到spam包具有nearest.dist()函数，该函数只允许考虑小于某个阈值delta的距离。但是，在我的情况下，特定的delta值可能会产生太多距离(因此我必须密集存储NxN矩阵)或距离太少(因此我不能使用kNN)。

我已经看过有关尝试使用bigmemory/biganalytics包执行k-means clustering的讨论，但是在这种情况下，我似乎无法利用这些方法。

有人知道一个函数/实现会以稀疏的方式在R中计算距离矩阵吗？我的(可怕的)备份计划是要有两个for循环并将结果保存在Matrix对象中。

Answer 1

好吧，我们不能让您求助于for循环，现在我们可以:)

当然存在如何表示稀疏矩阵的问题。一种简单的方法是使其仅包含最接近的点的索引(并根据需要重新计算)。但是在下面的解决方案中，我将距离('d1'等)和索引('i1'等)都放在一个矩阵中:

sparseDist <- function(m, k) {
    m <- t(m)
    n <- ncol(m)
    d <- vapply( seq_len(n-1L), function(i) { 
        d<-colSums((m[, seq(i+1L, n), drop=FALSE]-m[,i])^2)
        o<-sort.list(d, na.last=NA, method='quick')[seq_len(k)]
        c(sqrt(d[o]), o+i) 
        }, numeric(2*k)
    )
    dimnames(d) <- list(c(paste('d', seq_len(k), sep=''),
        paste('i', seq_len(k), sep='')), colnames(m)[-n])
    d
}

在9个2d点上进行尝试:

> m <- matrix(c(0,0, 1.1,0, 2,0, 0,1.2, 1.1,1.2, 2,1.2, 0,2, 1.1,2, 2,2),
              9, byrow=TRUE, dimnames=list(letters[1:9], letters[24:25]))
> print(dist(m), digits=2)
    a   b   c   d   e   f   g   h
b 1.1                            
c 2.0 0.9                        
d 1.2 1.6 2.3                    
e 1.6 1.2 1.5 1.1                
f 2.3 1.5 1.2 2.0 0.9            
g 2.0 2.3 2.8 0.8 1.4 2.2        
h 2.3 2.0 2.2 1.4 0.8 1.2 1.1    
i 2.8 2.2 2.0 2.2 1.2 0.8 2.0 0.9
> print(sparseDist(m, 3), digits=2)
     a   b   c   d   e   f   g   h
d1 1.1 0.9 1.2 0.8 0.8 0.8 1.1 0.9
d2 1.2 1.2 1.5 1.1 0.9 1.2 2.0  NA
d3 1.6 1.5 2.0 1.4 1.2 2.2  NA  NA
i1 2.0 3.0 6.0 7.0 8.0 9.0 8.0 9.0
i2 4.0 5.0 5.0 5.0 6.0 8.0 9.0  NA
i3 5.0 6.0 9.0 8.0 9.0 7.0  NA  NA

并尝试解决更大的问题(10k点)。不过，在100k点和更多尺寸上，将需要很长时间(例如15-30分钟)。

n<-1e4; m<-3; m=matrix(runif(n*m), n)
system.time( d <- sparseDist(m, 3) ) # 9 seconds on my machine...

附言刚刚注意到您在我写这篇文章时发布了一个答案:这里的解决方案速度大约是它的两倍，因为它不会两次计算相同的距离(点1和13之间的距离与点13和1之间的距离相同)。