algorithm - 用于计算按时间和 key 划分的 Pearson 互相关矩阵的分布式算法

Question

在分布式环境中计算 Pearson 互相关矩阵的算法是什么，其中我的数据在不同节点之间按 id(例如:1-4)和时间(例如:Jan-Dec)划分。

例如:

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})

基本上，我的意思是所有 id 的 Jan 数据不在一个节点上。

我想知道我可以使用什么策略，因为 PIL 逊相关性是一种成对计算，所以我不必将大数据从一个节点发送到另一个节点。我可以只在节点之间传输小的中间结果。我应该如何根据 id 和时间对数据进行分区，以便有效计算多个 id 之间的互相关矩阵。

选择的语言是 C++

Answer 1

两个数据向量之间的相关性是 cor(X,Y) = cov(X,Y)/[sd(X) * sd(Y)] 。有什么办法可以将这些分解为 block 计算吗？所需的基本计算(自 sd(X) = sqrt(cov(X,X) 起)是

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])

这是所有索引 i 的总和。然而，每个索引 i 对应于 N_n 的节点 n。事件和子索引(在该节点中)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])

自 N = sum[n] N_n ，这可以重写为

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)

因此，每个节点只需要报告其条目数N_n和手段<X>_n, <Y>_n ，和<XY>_n (并且，为了关联的目的， <X^2>_n 和 <Y^2>_n )在节点内。然后可以通过将这些均值与适当的权重相加来计算全局协方差 N_n/N (又是 N = sum[n] N_n )来获取全局平均值。

编辑:LaTeX 版本

由于这些方程在没有 LaTeX 的情况下很难解析，这里有一些更容易理解的图像版本。两个数据列表 X 和 Y 的协方差定义为

其中每个数量 <X>, <Y> ，和<XY>是(列表 X、列表 Y 和成对乘积列表 XY)的平均值。平均值的计算可以分解为各个节点的加权和。调用 X、Y、XY 或 X^2 或 Y^2(计算相关性所必需的)Z 中的任意一个，Z 的平均值为:

哪里<Z>_k是第 k 个节点上 Z 的平均值，N_k是第 k 个节点中的数据点的数量。这将每个节点所需的信息量减少到 N_k, <X>_k, <Y>_k, <XY>_k, <X^2>_k ，和<Y^2>_k .