Algorithme distribué pour le calcul de la matrice de corrélation croisée de Pearson partitionnée par le temps et la clé

Question

Ce qui pourrait être un algorithme de calcul de la matrice de corrélation croisée de Pearson dans un environnement distribué où mes données sont divisées par id (exemple: 1-4) et temps (disons: Jan-Dec) parmi différents nœuds.

Par exemple:

Node A({id1, Jan}, {id2, Jan}); Node B({id3, Jan}, {id4, Jan}), 
Node C({id1, Feb}, {id2, Feb}); Node A({id1, March}{id2, March}), 
Node C({id3, Feb}, {id4, Feb}); Node B({id3, March}, {id4, March}) 

En fait, je voulais dire les données Jan pour tous les id ne sont pas à un nœud. Je me demande quelle stratégie je pourrais utiliser lorsque je n'aurais pas à envoyer de grandes données d'un nœud à un autre nœud, car la corrélation de Pearson est un calcul par paire. Je suis d'accord avec le transfert de petit résultat intermédiaire entre les nœuds. Comment dois-je partitionner mes données en fonction de l'identifiant et du temps afin de calculer efficacement la matrice de corrélation croisée entre plusieurs identifiants.

La langue de choix est C++

Answer 1

La corrélation entre les deux vecteurs de données est cor(X,Y) = cov(X,Y)/[sd(X) * sd(Y)]. Y a-t-il un moyen de les décomposer en calculs de blocs? Le calcul essentiel nécessaire (depuis sd(X) = sqrt(cov(X,X)) est

cov(X,Y) = <X Y> - <X> <Y> 
     = 1/N (sum[i] X[i] Y[i]) - 1/N (sum[i] X[i]) * 1/N (sum[i] Y[i]) 

Ceci est une somme sur tous les indices i. Chaque indice i, cependant, correspond à un noeud n avec N_n événements et un sous-indice (dans ce nœud) k_n:

cov(X,Y) = 1/N (sum[n] sum[k_n] X[k_n] Y[k_n]) 
     - 1/N^2 (sum[n] sum[k_n] X[k_n]) * (sum[n] sum[k_n] Y[i]) 

Depuis N = sum[n] N_n, cela peut être réécrite comme

cov(X,Y) = (sum[n] N_n/N 1/N_n sum[k_n] X[k_n] Y[k_n]) 
     - (sum[n] N_n/N 1/N_n sum[k_n] X[k_n]) * (sum[n] N_n/N 1/N_n sum[k_n] Y[i]) 
     = (sum[n] N_n/N <XY>_n) - (sum[n] N_n/N <X>_n) * (sum[n] N_n/N <Y>_n) 

Ainsi, chaque noeud a seulement besoin de rapporter son nombre d'entrées N_n et les moyens <X>_n, <Y>_n, et <XY>_n (et, pour les besoins de la corrélation, <X^2>_n et <Y^2>_n) dans le noeud. La covariance globale peut alors être calculée en additionnant ces moyennes avec les poids appropriés(où N = sum[n] N_n encore) pour obtenir les moyennes globales.

Edit: version LATEX

Étant donné que ces équations sont difficiles à analyser sans LaTeX, voici quelques versions d'image plus compréhensible. La covariance de deux listes de données X et Y est défini comme

où chaque quantité <X>, <Y>, et <XY> est une moyenne (de la liste X, la liste Y, et la liste des produits par paires XY) . Le calcul des moyennes peut être décomposé en une somme pondérée sur les différents nœuds. L'appel quelconque de X, Y, XY ou X^2 ou Y^2 (nécessaire pour calculer la corrélation) Z, la moyenne de Z représente:

où <Z>_k est la moyenne de Z sur le k-ème nœud et N_k est le nombre de points de données dans le k-ème nœud. Cela réduit la quantité d'informations nécessaires de chaque nœud à N_k, <X>_k, <Y>_k, <XY>_k, <X^2>_k et <Y^2>_k.

Answer 2

Jetez un oeil à cet article, car il pourrait l'expliquer un peu plus loin: https://en.wikipedia.org/wiki/Covariance_matrix

Prenons deux variables X et Y que vous avez mesuré, ce qui signifie que vous pouvez fournir deux tableaux de la même longueur, de sorte que { D'un point de vue philosophique, la covariance de deux variables X et Y exprime combien est forte la probabilité que la variation de X soit x1i. correspond à une variation de Y.

Pour calculer la matrice de covariance, vous avez besoin de trois éléments:

• est la moyenne arithmétique de X
• est la moyenne arithmétique de Y
• est la moyenne arithmétique du produit élément par élément des matrices X et Y

condition que cov (X, Y) = cov (Y, X) et que cov (X, X) = cov (Y, Y) = 1, vous pouvez utiliser ces propriétés pour minimiser le calcul requis et le besoin de transfert de données, car vous avez seulement besoin de calculer les éléments dans la diagonale supérieure de la matrice.

Par exemple, si vous avez deux variables vous devez calculer un seul élément, pour trois variables dont vous avez besoin pour calculer 3 éléments, et ainsi de suite ...

Answer 3

Est-ce que cette aide de papier? https://pdfs.semanticscholar.org/f02f/0df4922351375aa304de7de296393cdf7224.pdf

« Le premier algorithme est une version parallèle de corrélation Quadrant (QC), et le second est une version parallèle de la méthode Maronna. QC parallèle utilise une bibliothèque de matrice parallèle et peut gérer unidimensionnelle La méthode parallèle de Maronna divise les calculs de corrélation indépendants entre les processeurs et est capable de détecter des valeurs aberrantes unidimensionnelles et bidimensionnelles dans les données. "

Une autre question similaire: Distributed cross correlation matrix computation