转换为矩阵，但在 R 中保留一个对角线到 NULL

Question

我有一个巨大的数据集，看起来像这样。 为了节省一些内存，我想计算成对距离，但保留 矩阵的上对角线为 NULL。

library(tidyverse)
library(stringdist)
#> 
#> Attaching package: 'stringdist'
#> The following object is masked from 'package:tidyr':
#> 
#>     extract
df3 <- tibble(fruits=c("apple","banana","ananas","apple","ananas","apple","ananas"),
position=c("135","135","135","136","137","138","138"), 
counts = c(100,200,100,30,40,50,100))
stringdistmatrix(df3$fruits, method=c("osa"), nthread = 4) %>% 
as.matrix()
#>   1 2 3 4 5 6 7
#> 1 0 5 5 0 5 0 5
#> 2 5 0 2 5 2 5 2
#> 3 5 2 0 5 0 5 0
#> 4 0 5 5 0 5 0 5
#> 5 5 2 0 5 0 5 0
#> 6 0 5 5 0 5 0 5
#> 7 5 2 0 5 0 5 0

^{创建于 2022-03-01 由 reprex 软件包 (v2.0.1)}

但是当我将我的字符串矩阵转换为矩阵时(此步骤对我来说是必不可少的)， 我的上对角线充满了数字。

有没有办法转换为矩阵，但保持上对角线为 NULL 并节省内存？

我希望我的数据看起来像这样

1 2 3 4 5 6
2 5          
3 5 2        
4 0 5 5      
5 5 2 0 5    
6 0 5 5 0 5  
7 5 2 0 5 0 5

Answer 1

如果你担心记忆，那么Matrix可能不是答案，原因有两个：

• 距离矩阵不是稀疏的。n×n距离矩阵中有n*(n-1)/2个非冗余元素，所有这些元素都可以为非零元素。渐近地，那是一半的元素！将这些数据存储在sparseMatrix对象中效率低下，因为除了非零元素之外，您还需要将它们的位置存储在矩阵中。两个整数向量i和长度n*(n-1)/2的j将在内存中占用至少4*n*(n-1)个字节(n = 5e+04时为 ~10 GB)。

• Matrix实现了类dspMatrix，用于高效存储密集对称矩阵，包括距离矩阵。但是，dist对象将n*(n-1)/2元素存储在对角线下方，而dspMatrix对象存储这些元素和对角线元素。因此，如果不为新的n*(n+1)/2长度双向量分配4*n*(n+1)字节(同样，n = 5e+04时为 ~10 GB)，就无法从dist强制到dspMatrix。

最有效的方法是保留dist对象并直接为其编制索引，具体取决于您正在执行的任何计算。 您可以利用以下事实：n×n距离矩阵的下三角形中的元素[i, j]存储在相应dist对象的元素[k]中，其中k = i + (2 * (n - 1) - j) * (j - 1) / 2。

例如，要在不构造整个矩阵的情况下获取dist对象x指定的距离矩阵的列(或行)j，可以使用以下函数：

getDistCol <- function(x, j) {
p <- length(x)
n <- as.integer(round(0.5 * (1 + sqrt(1 + 8 * p)))) # p = n * (n - 1) / 2
if (j == 1L) {
return(c(0, x[seq_len(n - 1L)]))
}
ii <- rep.int(j - 1L, j - 1L)
jj <- 1L:(j - 1L)
if (j < n) {
ii <- c(ii, j:(n - 1L))
jj <- c(jj, rep.int(j, n - j))
}
kk <- ii + ((2L * (n - 1L) - jj) * (jj - 1L)) %/% 2L
res <- double(n)
res[-j] <- x[kk]
res
}

fruits <- c("apple", "banana", "ananas", "apple", "ananas", "apple", "ananas")
x <- stringdist::stringdistmatrix(fruits)
##   1 2 3 4 5 6
## 2 5          
## 3 5 2        
## 4 0 5 5      
## 5 5 2 0 5    
## 6 0 5 5 0 5  
## 7 5 2 0 5 0 5
getDistCol(x, 1L)
## [1] 0 5 5 0 5 0 5
lapply(1:7, getDistCol, x = x)
## [[1]]
## [1] 0 5 5 0 5 0 5
## 
## [[2]]
## [1] 5 0 2 5 2 5 2
## 
## [[3]]
## [1] 5 2 0 5 0 5 0
## 
## [[4]]
## [1] 0 5 5 0 5 0 5
## 
## [[5]]
## [1] 5 2 0 5 0 5 0
## 
## [[6]]
## [1] 0 5 5 0 5 0 5
## 
## [[7]]
## [1] 5 2 0 5 0 5 0

如果你坚持一个dspMatrix对象，那么你可以使用这种方法从dist强制：

library("Matrix")
asDspMatrix <- function(x) {
n <- attr(x, "Size")
i <- 1L + c(0L, cumsum(n:2L))
xx <- double(length(x) + n)
xx[-i] <- x
new("dspMatrix", uplo = "L", x = xx, Dim = c(n, n))
}
asDspMatrix(x)
## 7 x 7 Matrix of class "dspMatrix"
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,]    0    5    5    0    5    0    5
## [2,]    5    0    2    5    2    5    2
## [3,]    5    2    0    5    0    5    0
## [4,]    0    5    5    0    5    0    5
## [5,]    5    2    0    5    0    5    0
## [6,]    0    5    5    0    5    0    5
## [7,]    5    2    0    5    0    5    0

Answer 2

我认为您可能需要使用稀疏矩阵。包Matrix有这样的可能性。您可以在以下位置了解有关稀疏矩阵的更多信息：稀疏矩阵

library(Matrix)
m <- sparseMatrix(i = c(1:3, 2:3, 3), j=c(1:3,1:2, 1), x = 1, triangular = T)
m
#> 3 x 3 sparse Matrix of class "dtCMatrix"
#>           
#> [1,] 1 . .
#> [2,] 1 1 .
#> [3,] 1 1 1

要检查矩阵的大小，可以使用函数object.size。

似乎对于小矩阵，使用稀疏矩阵没有区别，但是，对于大矩阵，内存节省是相当可观的：

library(Matrix)
n <- 30
m1 <- matrix(1,n,n)
m2 <- Matrix(m1, sparse = TRUE) 
object.size(m1)
#> 7416 bytes
object.size(m2)
#> 7432 bytes
n <- 300
m1 <- matrix(1,n,n)
m2 <- Matrix(m1, sparse = TRUE) 
object.size(m1)
#> 720216 bytes
object.size(m2)
#> 544728 bytes