Самый эффективный способ создания симметричной матрицы

У меня есть следующая матрица / dataframe:

> e
  V1 V2 V3 V4 V5
1  0  2  3  4  5
2  0  0  6  8 10
3  0  0  0 12 15
4  0  0  0  0 20
5  0  0  0  0  0

В этом случае N=5 (количество строк = количество столбцов). Я хотел бы заполнить пропущенные значения в этой симметричной матрице (e[1,2]=e[2,1] и т. Д.). Есть ли наиболее эффективный способ заполнить пропущенные значения (размер матрицы в моем случае довольно большой)? Есть ли лучший способ, чем вложенные циклы?

4 ответа

Решение

Просто для завершения я хотел бы также показать эту технику. Добавление транспонирования не будет работать, если в нижней части матрицы (под диагональю) заполнены значения, так как они добавят их в верхнюю часть матрицы.

Используя пакет Matrix, мы можем создать разреженную матрицу, которая в случае создания симметрии большой матрицы потребует гораздо меньше памяти и даже ускорит ее.

Для того чтобы создать симметричную разреженную матрицу из матрицы e мы бы сделали:

library(Matrix)
rowscols <- which(upper.tri(e), arr.ind=TRUE)
sparseMatrix(i=rowscols[,1],    #rows to fill in
             j=rowscols[,2],    #cols to fill in
             x=e[upper.tri(e)], #values to use (i.e. the upper values of e)
             symmetric=TRUE,    #make it symmetric
             dims=c(nrow(e),nrow(e))) #dimensions

Выход:

5 x 5 sparse Matrix of class "dsCMatrix"

[1,] .  2  3  4  5
[2,] 2  .  6  8 10
[3,] 3  6  . 12 15
[4,] 4  8 12  . 20
[5,] 5 10 15 20  .

Microbenchmark:

Давайте создадим функцию для создания симметричной матрицы из матрицы (по умолчанию копирует верхнюю часть матрицы в нижнюю):

symmetrise <- function(mat){
  rowscols <- which(upper.tri(mat), arr.ind=TRUE)
  sparseMatrix(i=rowscols[,1], 
               j=rowscols[,2], 
               x=mat[upper.tri(mat)], 
               symmetric=TRUE, 
               dims=c(nrow(mat),ncol(mat)) )  
}

И проверить:

> microbenchmark(
e + t(e),
symmetrise(e),
e[lower.tri(e)] <- t(e)[lower.tri(e)],
times=1000
)
Unit: microseconds
                                  expr      min       lq      mean   median        uq       max neval cld
                              e + t(e)   75.946   99.038  117.1984  110.841  134.9590   246.825  1000 a  
                         symmetrise(e) 5530.212 6246.569 6950.7681 6921.873 7034.2525 48662.989  1000   c
 e[lower.tri(e)] <- t(e)[lower.tri(e)]  261.193  322.771  430.4479  349.968  395.3815 36873.894  1000  b 

Как вы видете symmetrise на самом деле гораздо медленнее, чем e + t(e) или же df[lower.tri(df)] <- t(df)[lower.tri(df)] но, по крайней мере, у вас есть функция, которая автоматически симметрирует матрицу (берет верхнюю часть и создает нижнюю по умолчанию), и в случае, если у вас большая матрица, где проблема с памятью, это может пригодиться.

PS Везде, где вы видите . в Матрице это представляет ноль. При использовании другой системы разреженная матрица является своего рода "сжатым" объектом, что делает ее более эффективной в использовании памяти.

Также для скорости:

2*symmpart(as.matrix(e))

Вот эталон:

Unit: microseconds
                                      expr      min       lq        mean    median        uq       max neval
                                  e + t(e)  572.505  597.194  655.132028  611.5420  628.4860  8424.902  1000
                             symmetrise(e) 1128.220 1154.562 1215.740071 1167.0020 1185.6585 10656.059  1000
 e[lower.tri(e)] <- e[upper.tri(e, FALSE)]  285.013  311.191  350.846885  327.1335  339.5910  8106.006  1000
                2 * symmpart(as.matrix(e))   78.392   93.953  101.330522  102.1860  107.9215   153.628  1000

Он может получить эту скорость, потому что он создает симметричную матрицу напрямую.

df[lower.tri(df)] <- t(df)[lower.tri(df)]

Выход:

  V1 V2 V3 V4 V5
1  0  2  3  4  5
2  2  0  6  8 10
3  3  6  0 12 15
4  4  8 12  0 20
5  5 10 15 20  0

Данные:

df <- structure(list(V1 = c(0L, 0L, 0L, 0L, 0L), V2 = c(2L, 0L, 0L, 
0L, 0L), V3 = c(3L, 6L, 0L, 0L, 0L), V4 = c(4L, 8L, 12L, 0L, 
0L), V5 = c(5L, 10L, 15L, 20L, 0L)), .Names = c("V1", "V2", "V3", 
"V4", "V5"), class = "data.frame", row.names = c("1", "2", "3", 
"4", "5"))
e + t(e)

Добавление матрицы и транспонирование этой матрицы, это то, что вы хотите?

Другие вопросы по тегам