Разреженная матрица в результате перекрестного производства разреженных матриц

Я работал над этой проблемой некоторое время, но не нашел удовлетворительного решения.

У меня есть данные в двоичной разреженной матрице (TermDocumentMatrix) с тусклым ([1] 340436 763717). Здесь я использую выдержку в качестве доказательства концепции:

m = structure(list(i = c(1L, 2L, 5L, 2L, 4L, 3L, 5L, 4L), j = c(1L, 1L, 1L, 2L, 2L, 
    3L, 3L, 3L), v = c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), nrow = 5L, ncol = 3L, 
    dimnames = list(Terms = c("action", "activities", "advisory", "alike", "almanac"),
                    Docs = c("1000008721", "1000010083","1000013295"))), 
    class = c("TermDocumentMatrix", "simple_triplet_matrix"), weighting = c("binary", "bin"))

inspect(m)
<<TermDocumentMatrix (terms: 5, documents: 3)>>
Non-/sparse entries: 8/7
Sparsity           : 47%
Maximal term length: 10
Weighting          : binary (bin)
Sample             :
            Docs
Terms        1000008721 1000010083 1000013295
  action              1          0          0
  activities          1          1          0
  advisory            0          0          1
  alike               0          1          1
  almanac             1          0          1

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

Ожидаемый результат:

Sparse Matrix:
            Docs
Docs         1000008721 1000010083 1000013295 ... N
  1000008721  1.0000000  0.4082483  0.3333333     .
  1000010083  0.4082483  1.0000000  0.4082483     .  
  1000013295  0.3333333  0.4082483  1.0000000     .
    ...
   N               .          .          .

or also: data.table
 ID1              ID2          v
1000008721     1000008721      1
1000010083     1000008721     0.4082483
1000013295     1000008721     0.3333333
   ...             ...         ...

Этого было бы легко добиться с помощью crossprod_simple_triplet_matrix(m) после применения нормализации с помощью функции, которая делит каждое значение на норму. Евклидова норма в бинарном векторе сводится к sqrt(col_sums(m)).

Поскольку я не могу использовать as.matrix() преобразование («Ошибка: невозможно выделить вектор размером 968,6 Гб»), а другого способа я не нашел, я использовал data.table, который может обойти необходимость применения функции к разреженной матрице:

# exploit the triples and manipulate through data.table
dt = as.data.table(list(i=m$i,j=m$j,v=m$v))

# obtain euclidean norm for every column 
dt[,e.norm:=list(as.numeric(sqrt(sum(v)))),by=j]

# divide the v for the corresponding group, subset and replace
dt = dt[,v.norm:=v/e.norm][,.(i,j,v.norm)][,v:=v.norm][,.(i,j,v)]

m$v <- dt$v
inspect(m)
            Docs
Terms        1000008721 1000010083 1000013295
  action      0.5773503  0.0000000  0.0000000
  activities  0.5773503  0.7071068  0.0000000
  advisory    0.0000000  0.0000000  0.5773503
  alike       0.0000000  0.7071068  0.5773503
  almanac     0.5773503  0.0000000  0.5773503

(Что было бы эквивалентно этому (может быть, с хлопком)?)

ВОПРОС: Учитывая, что crossprod_simple_triplet_matrix(tdm) по-прежнему возвращает плотную матрицу (следовательно, ошибка памяти), можете ли вы подумать о подобном решении data.table для возврата разреженной матрицы с перекрестным произведением двух разреженных матриц или каким-либо альтернативным способом?

3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
0
0
84
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Разреженная матрица 340436 x 763717 с 35879680 ненулевыми элементами приведет к очень большому объекту (~ 30 ГБ). Моя машина не может удерживать этот объект в памяти с 16 ГБ ОЗУ. Тем не менее, перекрестное произведение легко сделать по частям. Функция bigcrossprod ниже выполняет перекрестное произведение по частям, преобразует результаты в data.table объекты, а затем rbinds объекты. crossprod операция разбита на nseg отдельные операции.

library(data.table)
library(Matrix)

bigcrossprod <- function(m, nseg) {
  jmax <- ncol(m)
  # get the indices to split the columns of m into chunks that will have
  # approximately the same expense for crossprod
  sumj <- cumsum(as.numeric(jmax:1))
  dtj <- data.table(
    j = 1:jmax,
    int = sumj %/% (sumj[jmax]/nseg + 1)
  )[
    , .(idx1 = min(j), idx2 = max(j)), int
  ][, idx1:idx2]
  rbindlist(
    lapply(
      1:nseg,
      function(seg) {
        cat("\r", seg) # user feedback
        j1 <- dtj$idx1[seg]
        m2 <- as(triu(crossprod(m[, j1:dtj$idx2[seg],drop = FALSE],
                                m[, j1:jmax])), "dgTMatrix")
        data.table(
          i = attr(m2, "i") + j1,
          j = attr(m2, "j") + j1,
          v = attr(m2, "x")
        )
      }
    )
  )
}

Демонстрация с несколько меньшей разреженной матрицей:

idx <- sample(34043*76371, 358796)
dt <- data.table(i = as.integer(((idx - 1) %% 34043L) + 1),
                 j = as.integer(((idx - 1) %/% 34043L) + 1),
                 key = "j")[, v := 1/sqrt(.N), j]
m <- sparseMatrix(dt$i, dt$j, x = dt$v)
# calculate crossprod on the full matrix and convert the result to triplet
# form in order to represent as a data.table
m2 <- as(crossprod(m), "dgTMatrix")
dt2 <- data.table(i = attr(m2, "i") + 1L,
                  j = attr(m2, "j") + 1L,
                  v = attr(m2, "x"))
# calculate crossprod in 10 chunks
dt3 <- bigcrossprod(m, 10)
#>  1 2 3 4 5 6 7 8 9 10
# convert the result into a symmetric sparse matrix in triplet form (the same as m2)
m3 <- as(forceSymmetric(sparseMatrix(dt3$i, dt3$j, x = dt3$v)), "dgTMatrix")
# remove elements from the data.table objects that are redundant due to symmetry
dt2 <- unique(dt2[i > j, `:=`(i = j, j = i)])
dt3 <- setorder(dt3[i > j, `:=`(i = j, j = i)], i, j)
# check that the dgTMatrix and data.table objects are identical
identical(m2, m3)
#> [1] TRUE
identical(dt2, dt3)
#> [1] TRUE

Чтобы вычислить векторное произведение разреженной матрицы 340436 x 763717 с 35879680 элементами, вместо сохранения списка data.table объектов в списке для передачи rbindlist сохраните отдельные объекты data.table для последующей обработки с помощью пакета fst. Вместо того, чтобы возвращать один data.table, следующая версия bigcrossprod возвращает вектор символов длины nseg, содержащий пути к файлам .fst. Опять же, демонстрируя с меньшей матрицей:

library(data.table)
library(Matrix)
library(fst)

bigcrossprod <- function(m, nseg, path) {
  jmax <- ncol(m)
  # get the indices to split the columns of m into chunks that will have
  # approximately the same expense for crossprod
  sumj <- cumsum(as.numeric(jmax:1))
  dtj <- data.table(
    j = 1:jmax,
    int = sumj %/% (sumj[jmax]/nseg + 1)
  )[
    , .(idx1 = min(j), idx2 = max(j)), int
  ][, idx1:idx2]
  vapply(
    1:nseg,
    function(seg) {
      cat("\r", seg) # user feedback
      j1 <- dtj$idx1[seg]
      m2 <- as(triu(crossprod(m[, j1:dtj$idx2[seg], drop = FALSE],
                              m[, j1:jmax])), "dgTMatrix")
      filepath <- file.path(path, paste0("dt", seg, ".fst"))
      write.fst(
        data.table(
          i = attr(m2, "i") + j1,
          j = attr(m2, "j") + j1,
          v = attr(m2, "x")),
        filepath
      )
      filepath
    },
    character(1)
  )
}

idx <- sample(34043*76371, 358796)
dt <- data.table(i = as.integer(((idx - 1) %% 34043L) + 1),
                 j = as.integer(((idx - 1) %/% 34043L) + 1),
                 key = "j")[, v := 1/sqrt(.N), j]
m <- sparseMatrix(dt$i, dt$j, x = dt$v)
# calculate crossprod on the full matrix and convert the result to triplet
# form in order to represent as a data.table
m2 <- as(crossprod(m), "dgTMatrix")
dt2 <- data.table(i = attr(m2, "i") + 1L,
                  j = attr(m2, "j") + 1L,
                  v = attr(m2, "x"))
# calculate crossprod in 10 chunks, read the resulting .fst files,
# and rbindlist into a single data.table
dt3 <- rbindlist(lapply(bigcrossprod(m, 10, "C:/temp"),
                        function(x) read.fst(x, as.data.table = TRUE)))
#> 1 2 3 4 5 6 7 8 9 10
# convert the result into a symmetric sparse matrix in triplet form (the same as m2)
m3 <- as(forceSymmetric(sparseMatrix(dt3$i, dt3$j, x = dt3$v)), "dgTMatrix")
# remove elements from the data.table objects that are redundant due to symmetry
dt2 <- unique(dt2[i > j, `:=`(i = j, j = i)])
dt3 <- setorder(dt3[i > j, `:=`(i = j, j = i)], i, j)
# check that the dgTMatrix and data.table objects are identical
identical(m2, m3)
#> [1] TRUE
identical(dt2, dt3)
#> [1] TRUE

Я смог обработать разреженную матрицу размером 340436 x 763717 с 35879680 ненулевыми элементами примерно за 15 минут с 16 ГБ ОЗУ.

Объяснение:

Прохождение логики в bigcrossprod с использованием примера матрицы OP 5 x 3:

idx <- c(1,2,5,7,9,13:15)
dt <- data.table(i = as.integer(((idx - 1) %% 5) + 1),
                 j = as.integer(((idx - 1) %/% 5) + 1),
                 key = "j")[, v := 1/sqrt(.N), j]
(m <- sparseMatrix(dt$i, dt$j, x = dt$v))
#> 5 x 3 sparse Matrix of class "dgCMatrix"
#>                                   
#> [1,] 0.5773503 .         .        
#> [2,] 0.5773503 0.7071068 .        
#> [3,] .         .         0.5773503
#> [4,] .         0.7071068 0.5773503
#> [5,] 0.5773503 .         0.5773503
nseg <- 2 # process the cross product of m in two chunks
jmax <- ncol(m)
sumj <- cumsum(as.numeric(jmax:1))
# In order to balance the processing between chunks, process column 1 first,
# then columns 2:3 next. Each crossprod call will result in 3 elements.
(dtj <- data.table(j = 1:jmax, int = sumj %/% (sumj[jmax]/nseg + 1))[, .(idx1 = min(j), idx2 = max(j)), int][, idx1:idx2])
#>    idx1 idx2
#> 1:    1    1
#> 2:    2    3
# process the first chunk
seg <- 1L
j1 <- dtj$idx1[seg]
# cross product of column 1 and the full matrix
(m2 <- as(crossprod(m[, j1:dtj$idx2[seg], drop = FALSE], m[, j1:jmax]), "dgTMatrix"))
#> 1 x 3 sparse Matrix of class "dgTMatrix"
#>                           
#> [1,] 1 0.4082483 0.3333333
# The indices of m2 are 0-based. Add j1 to the i,j indices of m2 when converting
# to a data.table.
(dt1 <- data.table(i = attr(m2, "i") + j1, j = attr(m2, "j") + j1, v = attr(m2, "x")))
#>    i j         v
#> 1: 1 1 1.0000000
#> 2: 1 2 0.4082483
#> 3: 1 3 0.3333333
# process the second chunk
seg <- 2L
j1 <- dtj$idx1[seg] # starts at column 2
# Cross product of columns 2:3 and columns 2:jmax (2:3). The end result
# will be a symmetric matrix, so we need only the upper triangular matrix.
(m2 <- as(triu(crossprod(m[, j1:dtj$idx2[seg], drop = FALSE], m[, j1:jmax])), "dgTMatrix"))
#> 2 x 2 sparse Matrix of class "dgTMatrix"
#>                 
#> [1,] 1 0.4082483
#> [2,] . 1.0000000
(dt2 <- data.table(i = attr(m2, "i") + j1, j = attr(m2, "j") + j1, v = attr(m2, "x")))
#>    i j         v
#> 1: 2 2 1.0000000
#> 2: 2 3 0.4082483
#> 3: 3 3 1.0000000
# the final matrix (in data.table form) is the two data.tables row-bound
# together (in bigcrossprod, the lapply returns a list of data.table objects for
# rbindlist)
(dt3 <- rbindlist(list(dt1, dt2)))
#>    i j         v
#> 1: 1 1 1.0000000
#> 2: 1 2 0.4082483
#> 3: 1 3 0.3333333
#> 4: 2 2 1.0000000
#> 5: 2 3 0.4082483
#> 6: 3 3 1.0000000
# dt3 can be converted to a symmetric sparse matrix
(m3 <- forceSymmetric(sparseMatrix(dt3$i, dt3$j, x = dt3$v)))
#> 3 x 3 sparse Matrix of class "dsCMatrix"
#>                                   
#> [1,] 1.0000000 0.4082483 0.3333333
#> [2,] 0.4082483 1.0000000 0.4082483
#> [3,] 0.3333333 0.4082483 1.0000000

И, наконец, параллельная версия bigcrossprod (для Linux):

library(data.table)
library(Matrix)
library(parallel)
library(fst)

bigcrossprod <- function(m, nseg, path, nthreads = nseg) {
  jmax <- ncol(m)
  # get the indices to split the columns of m into chunks that will have
  # approximately the same expense for crossprod
  sumj <- cumsum(as.numeric(jmax:1))
  dtj <- data.table(
    j = 1:jmax,
    int = sumj %/% (sumj[jmax]/nseg + 1)
  )[
    , .(idx1 = min(j), idx2 = max(j)), int
  ][, idx1:idx2]
  cl <- makeCluster(nthreads, type = "FORK", outfile = "")
  on.exit(stopCluster(cl))
  unlist(
    parLapply(
      cl,
      1:nseg,
      function(seg) {
        j1 <- dtj$idx1[seg]
        m2 <- as(triu(crossprod(m[, j1:dtj$idx2[seg],drop = FALSE],
                                m[, j1:jmax])), "dgTMatrix")
        filepath <- file.path(path, paste0("dt", seg, ".fst"))
        write.fst(
          data.table(
            i = attr(m2, "i") + j1,
            j = attr(m2, "j") + j1,
            v = attr(m2, "x")),
          filepath
        )
        filepath
      }
    )
  )
}

Спасибо... с моими данными у меня "Ошибка в .local(x, y = y,...): ошибка Cholmod "слишком большая проблема" в файле ../Core/cholmod_sparse.c, строка 89" можно попробовать немного уменьшить размер исходной матрицы, отфильтровав не релевантные термины и документы

KArrow'sBest 24.04.2022 12:43

Кроме того, как я могу привести имена столбцов orig m к именам столбцов и именам строк конечного m? (Я хочу получить DT с ID1 ID2 и v, который станет DT с весами для сети) colnames(m) <- names(tdm) ?

KArrow'sBest 24.04.2022 12:51

Какая команда приводит к ошибке?

jblood94 25.04.2022 01:07

Matrix:: crossprod (Matrix:: sparseMatrix (dt $ i, dt $ j, x = dt $ v))

KArrow'sBest 25.04.2022 12:18

Что у вас есть для dim(dt)?

jblood94 25.04.2022 12:32

Дим возвращает 35879680 3

KArrow'sBest 25.04.2022 12:53

В результате получится очень большой объект. Сколько у вас оперативной памяти?

jblood94 25.04.2022 17:58

Взгляните на обновленный ответ для работы с объектами больше, чем может поместиться в памяти.

jblood94 25.04.2022 19:34

Большое спасибо. У меня есть 32 ГБ + подкачка, установленная на 900 ГБ только для этой задачи, но проблема с ошибкой все еще слишком велика. С другой стороны, я мог бы обработать свою матрицу вашим раствором. Я все еще пытаюсь понять функцию (я воспринял ее как черный ящик и пока подал заявку), не могли бы вы написать несколько комментариев о ее логике? как я могу перенести исходные имена документов в новый dt с помощью этой функции?

KArrow'sBest 27.04.2022 09:38

i и j в результирующих data.table(s) соответствуют исходной матрице. Скажем, nms является вектором символов имен столбцов, имена строк в результирующем data.table будут nms[dt$i], а имена столбцов будут nms[dt$j].

jblood94 27.04.2022 12:30

Я добавил пошаговое руководство по логике внизу ответа.

jblood94 27.04.2022 14:32

Я обновил ответ, чтобы использовать triu, чтобы немного упростить bigcrossprod.

jblood94 27.04.2022 14:52

Чем больше я думаю об этом, тем больше мне нравится эта функция, я постараюсь расширить ее до future_lapply, для которой я думаю, что она подходит..

KArrow'sBest 27.04.2022 20:04

Да. Или lapply можно легко заменить на parLapply. Я не делал параллель, потому что уже был близок к тому, чтобы использовать все свои 16 ГБ ОЗУ.

jblood94 27.04.2022 21:36

Только одну вещь, которую вы можете изменить: > m <- sparseMatrix(dt$i, dt$j, x = dt$v) > dim(m) [1] 34043 76371 Вы обработали 34043x76371 с 358796 ненулевыми элементами, а не 340430x763717 с 35879680, но я могу подтвердить, что, немного используя мой своп, функция может достичь этого.

KArrow'sBest 28.04.2022 09:54

Давайте продолжить обсуждение в чате.

KArrow'sBest 28.04.2022 11:07

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