R: Fast way to group matrix rows by considering only the place of NA values

user_1953718 0
Viewed 238

I am trying to group the rows of a matrix by their unique placement of NA values within each columns.

For example with the following matrix:

1, 2, NA, 3 NA
2, 5, NA, 4, 5
3, 2,  1, 0, 7
5, 3, NA, 9, 3
0, 2,  1, 4, 6

The answer would be:

1, 2, 3, 2, 3

Indicating that there were 3 distinct groups and i.e. rows 2 and 4 were in the same group.

The trouble is that I can not come up with a quick way to achieve this. Here is my current implementation:

mat <- matrix(rnorm(10000*100), ncol=100)
mat[sample(length(mat), nrow(mat))] <- NA

getNAgroups <- function(x) {
  allnas  <- t(!is.na(x))
  nacases <- unique(allnas, MARGIN=2)
  groups  <- numeric(nrow(x))
  for(i in 1:ncol(nacases)) {
    groups[colMeans(allnas == nacases[,i]) == 1] <- i
  }
  groups
}

Which is a bit too slow for the purposes I have in mind:

system.time(getNAgroups(mat))
   user  system elapsed
  7.672   1.686   9.386
na r matrix performance
5 Answers

Here is one way using match on list of NA position:

mat <- matrix(c(1, 2, NA, 3, NA,
2, 5, NA, 4, 5,
3, 2,  1, 0, 7,
5, 3, NA, 9, 3,
0, 2,  1, 4, 6), 5, byrow = TRUE)


categ <- apply(is.na(mat), 1, which)
match(categ, unique(categ))
user_63564300

We can paste the values together row-wise and match it to get unique index.

vals <- apply(is.na(mat), 1, toString)
match(vals, unique(vals))
#[1] 1 2 3 2 3
user_39629140

If performance is the concern, I would give the following code a try:

library(dplyr)
getNAgrps = function(df){
  df = df %>% 
    dplyr::mutate(NAgrp = '')
  lapply(1:nrow(df),function(i){
    df$NAgrp[i] <<- paste0(which(is.na(df[i,])),collapse=",")
  })

  return(df)
}

This function takes the input as a dataframe. To convert your matrix to dataframe:

library(dplyr)
dat = as_data_frame(mat)

The performance is as follows:

> system.time(getNAgrps(mat))
   user  system  elapsed 
  0.005  0.000   0.006

Let me know if it works.

Note: Instead of giving integer groups, this will return character vectors with the positions of NAs separated by commas.

user_106622210

In case you don't mind the order you can use interaction to find groups.

tt <- interaction(as.data.frame(is.na(mat)), drop = TRUE)
unclass(tt)
#[1] 3 2 1 2 1

Or a maybe a more performant way is using sweep and rowSums but works only up to 30 columns.

tt  <- is.na(mat)
tt <- rowSums(sweep(tt, 2, cumprod(rep(2L,ncol(tt))), "*"))
match(tt, unique(tt))
#[1] 1 2 3 2 3

Or you can use the bit library, which is not faster but follows the previous idea and works for many rows and might help when memory will limit.

library("bit")
tt <- apply(is.na(mat), 1, as.bit)
match(tt, unique(tt))
#[1] 1 2 3 2 3

#For many columns
tt <- apply(apply(is.na(mat), 1, as.bit), 2, paste, collapse=" ")
match(tt, unique(tt))
#[1] 1 2 3 2 3

Alternatively packBits could be used like:

tt  <- is.na(mat)
tt <- cbind(tt, matrix(TRUE, nrow(tt), ncol=(8 - ncol(tt) %% 8)))
tt <- packBits(t(tt))
tt <- split(tt, rep(seq_len(nrow(mat)), each=length(tt)/nrow(mat)))
match(tt, unique(tt))
#[1] 1 2 3 2 3

or a more performant version using raw2hex from PKI or encryptr.

library(PKI) #or library(encryptr)
tt  <- is.na(mat)
tt <- cbind(tt, matrix(TRUE, nrow(tt), ncol=(8 - ncol(tt) %% 8)))
tt <- raw2hex(packBits(t(tt)))
tt <- matrix(tt, ncol = nrow(mat))
tt <- apply(tt, 2, paste, collapse="")
match(tt, unique(tt))
[1] 1 2 3 2 3
user_104885040 
set.seed(42)
mat <- matrix(rnorm(10000*100), ncol=100)
mat[sample(length(mat), nrow(mat))] <- NA

getNAgroups_Orig <- function(x) {
  allnas  <- t(!is.na(x))
  nacases <- unique(allnas, MARGIN=2)
  groups  <- numeric(nrow(x))
  for(i in 1:ncol(nacases)) {
    groups[colMeans(allnas == nacases[,i]) == 1] <- i
  }
  groups
}

getNAgroups_GKi <- function(mat) {
  tt  <- is.na(mat)
  tt <- rowSums(sweep(tt, 2, cumprod(rep(2L,ncol(tt))), "*"))
  match(tt, unique(tt))
}

getNAgroups_Clemsang <- function(mat) {
  categ <- apply(is.na(mat), 1, which)
  match(categ, unique(categ))
}

getNAgroups_RonakShah <- function(mat) {
  vals <- apply(is.na(mat), 1, toString)
  match(vals, unique(vals))
}

library("bit")
getNAgroups_bit <- function(mat) {
  tt <- apply(apply(is.na(mat), 1, as.bit), 2, paste, collapse=" ")
  match(tt, unique(tt))
}

getNAgroups_GKi2 <- function(mat) {
  tt  <- is.na(mat)
  tt <- cbind(tt, matrix(TRUE, nrow(tt), ncol=(8 - ncol(tt) %% 8)))
  tt <- packBits(t(tt))
  tt <- split(tt, rep(seq_len(nrow(mat)), each=length(tt)/nrow(mat)))
  match(tt, unique(tt))
}

library(PKI) #or library(encryptr)
getNAgroups_GKi3 <- function(mat) {
  tt  <- is.na(mat)
  tt <- cbind(tt, matrix(TRUE, nrow(tt), ncol=(8 - ncol(tt) %% 8)))
  tt <- raw2hex(packBits(t(tt)))
  tt <- matrix(tt, ncol = nrow(mat))
  tt <- apply(tt, 2, paste, collapse="")
  match(tt, unique(tt))
}


system.time(getNAgroups_Orig(mat))
#       User      System verstrichen 
#      6.928       1.316       8.244 

system.time(getNAgroups_GKi(mat))  ###IS NOT WORKING CORRECT DUE TO TOO MANY COLUMNS
#       User      System verstrichen
#      0.016       0.000       0.016 

system.time(getNAgroups_Clemsang(mat))
#       User      System verstrichen 
#      0.045       0.004       0.049 

system.time(getNAgroups_RonakShah(mat))
#       User      System verstrichen 
#      0.347       0.000       0.347

system.time(getNAgroups_bit(mat))
#       User      System verstrichen 
#      0.239       0.000       0.240

system.time(getNAgroups_GKi2(mat))
#       User      System verstrichen 
#      0.119       0.000       0.119 

system.time(getNAgroups_GKi3(mat))
#       User      System verstrichen 
#      0.046       0.000       0.046
user_104885040
Related