R à court de mémoire pendant le calcul de la distance des séries chronologiques

Question

Description du problème

J'ai 45000 de temps (longueur 9) et que vous souhaitez calculer les distances pour une analyse de cluster. Je réalise que cela se traduira par (le triangle inférieur de) une matrice de taille 45000x45000, une matrice avec plus de 2 milliards d'entrées. Sans surprise, j'obtiens:

> proxy::dist(ctab2, method="euclidean") 
Error: cannot allocate vector of size 7.6 Gb 

Que puis-je faire?

Idées

• Augmenter la mémoire disponible/adressable en quelque sorte? Cependant, ces 7.6G sont probablement au-delà de certaines limites qui ne peuvent pas être étendues? Dans tous les cas, le système dispose de 16 Go de mémoire et le même volume d'échange. Par "Gb", R semble signifier Gigabyte, pas Gigabit, donc 7.6Gb nous met déjà dangereusement près d'une limite dure.
• Peut-être qu'une méthode de calcul de distance différente au lieu d'euclidean, disons DTW, pourrait être plus efficace en mémoire? Cependant, comme expliqué ci-dessous, la limite de mémoire semble être la matrice résultante, pas la mémoire requise au moment du calcul.

• Diviser l'ensemble de données en N morceaux et calculer la matrice en N^2 parties (en fait seulement les parties pertinentes pour le triangle inférieur) qui peuvent être réassemblées plus tard? (Cela pourrait ressembler à la solution à un problème similaire proposé .) Il semble que ce soit une solution plutôt salissante, cependant. De plus, j'aurai besoin de la matrice 45K x 45K à la fin de toute façon. Cependant, cela semble atteindre la limite. Le système donne également l'erreur d'allocation de mémoire lors de la génération d'un 45K x 45K matrice aléatoire:

  > N=45000; memorytestmatrix <- matrix(rnorm(N*N,mean=0,sd=1), N, N) Error: cannot allocate vector of size 15.1 Gb

  30K x 30K matrices possibles sans problèmes, R donne la taille résultante comme

  > print(object.size(memorytestmatrix), units="auto") 6.7 Gb

  1 Go de plus et tout irait bien, semble-t-il. Malheureusement, je n'ai pas de gros objets que je pourrais supprimer pour faire de la place. En outre, ironiquement,

  > system('free -m') Warning message: In system("free -m") : system call failed: Cannot allocate memory

  Je dois admettre que je ne suis pas vraiment sûr pourquoi R refuse d'allouer 7,6 Gb; le système a certainement plus de mémoire, mais pas beaucoup plus. ps aux montre le processus R comme le plus gros utilisateur de mémoire. Peut-être y a-t-il un problème avec la quantité de mémoire que R peut traiter même si plus de mémoire est disponible?

Questions connexes

• des réponses à d'autres questions liées à la R à court de mémoire, comme this one, suggèrent d'utiliser une plus mémoire des méthodes efficaces de calcul.
• This very helpful answer suggère de supprimer d'autres objets volumineux pour faire de la place pour l'opération gourmande en mémoire. L'idée de diviser l'ensemble de données et de calculer les distances par blocs est suggérée.

Software & versions

version R est 3.4.1. Le noyau système est Linux 4.7.6, x86_64 (c'est-à-dire 64bit).

> version 
      _       
platform  x86_64-pc-linux-gnu   
arch   x86_64      
os    linux-gnu     
system   x86_64, linux-gnu   
status          
major   3       
minor   4.1       
year   2017       
month   06       
day   30       
svn rev  72865      
language  R       
version.string R version 3.4.1 (2017-06-30) 
nickname  Single Candle 

Modifier (août 27): Quelques informations

• Mise à jour du noyau Linux 4.11.9 n'a aucun effet. Le package bigmemory peut également manquer de mémoire. Il utilise la mémoire partagée dans /dev/shm/ dont le système par défaut (mais en fonction de la configuration) permet la moitié de la taille de la RAM. Vous pouvez augmenter ceci à l'exécution en faisant (par exemple) mount -o remount,size=12Gb /dev/shm, mais cela ne peut toujours pas permettre l'utilisation de 12Gb. (Je ne sais pas pourquoi, peut-être la configuration de la gestion de la mémoire est-elle alors incohérente). En outre, you may end up crashing your system if you are not careful. R semble en réalité permettre réellement l'accès à la RAM complète et peut créer des objets jusqu'à cette taille. Il semble juste échouer pour des fonctions particulières telles que dist. J'ajouterai ceci comme une réponse, mais mes conclusions sont un peu fondées sur des spéculations, alors je ne sais pas dans quelle mesure cela est juste. R

Answer 1

R apparemment permet réellement l'accès à la RAM complète. Cela fonctionne parfaitement bien:

N=45000; memorytestmatrix <- matrix(nrow=N, ncol=N) 

C'est la même chose que j'ai essayé avant comme décrit dans la question initiale, mais avec une matrice de la place de NA de rnorm nombres aléatoires. La réaffectation de l'une des valeurs de la matrice comme flottante (memorytestmatrix[1,1]<-0.5) fonctionne toujours et remanie la matrice en tant que matrice flottante.

Par conséquent, je suppose que vous pouvez avoir une matrice de cette taille, mais vous ne pouvez pas le faire comme la fonction dist tente de le faire. Une explication possible est que la fonction fonctionne avec plusieurs objets de cette taille afin d'accélérer le calcul. Cependant, si vous calculez les distances par élément et changez les valeurs en place, cela fonctionne.

library(mefa)  # for the vec2dist function 

euclidian <- function(series1, series2) { 
    return((sum((series1 - series2)^2))^.5) 
} 

mx = nrow(ctab2) 
distMatrixE <- vec2dist(0.0, size=mx) 
for (coli in 1:(mx-1)) { 
    for (rowi in (coli+1):mx) { 
     # Element indices in dist objects count the rows down column by column from left to righ in lower triangular matrices without the main diagonal. 
     # From row and column indices, the element index for the dist object is computed like so: 
     element <- (mx^2-mx)/2 - ((mx-coli+1)^2 - (mx-coli+1))/2 + rowi - coli 
     # ... and now, we replace the distances in place 
     distMatrixE[element] <- euclidian(ctab2[rowi,], ctab2[coli,]) 
    } 
} 

(Notez que l'adressage dans dist objets est un peu difficile, car ils ne sont pas matrices, mais des vecteurs 1 dimensions de taille (N²-N)/2 refonte comme matrices triangulaires inférieures de taille N X N Si nous parcourons les lignes et les colonnes dans le bon ordre, cela peut aussi être fait avec une variable de compteur, mais le calcul explicite de l'indice d'élément est plus clair, je suppose.)

Notez également qu'il est possible de accélérer cela en utilisant sapply en calculant plus d'une valeur à la fois.

Answer 2

Il existe de bons algorithmes que n'ont pas besoin d'une matrice pleine distance en mémoire.

Par exemple, SLINK et DBSCAN et OPTICS.