设P和Q为整数上的两个有限概率分布,支持0和一些大整数N.P和Q之间的一维earth mover's distance是将P转换为Q必须支付的最小成本,考虑到它的成本为r * |纳米|将与整数n相关联的概率r“移动”到另一个整数m。
有一个简单的algorithm来计算这个。在伪代码中:
previous = 0
sum = 0
for i from 0 to N:
previous = P(i) - Q(i) + previous
sum = sum + abs(previous) // abs = absolute value
return sum
现在,假设您有两个包含概率分布的表。列n
包含整数,列p
包含相应的概率。表是正确的(所有概率都在0和1之间,它们的总和是我想在BigQuery(标准SQL)中计算地球移动器在这两个表之间的距离。
希望我完全理解你的问题。这似乎是你正在寻找的:
WITH Aggr AS (
SELECT rp.n AS n, SUM(rp.p - rq.p)
OVER(ORDER BY rp.n ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS emd
FROM P rp
LEFT JOIN Q rq
ON rp.n = rq.n
) SELECT SUM(ABS(a.emd)) AS total_emd
FROM Aggr a;
WRT问题#2,注意我们只扫描表中的实际内容,无论N如何,假设P中的每个n与Q中的n一对一匹配。
我调整了迈克尔的答案来解决问题,这是我最终解决的问题。假设整数存储在列i
中,并且概率存储在列p
中。首先我加入两个表,然后我使用窗口为所有EMD(i)
计算i
,然后我求和所有绝对值。
WITH
joined_table AS (
SELECT
IFNULL(table1.i, table2.i) AS i,
IFNULL(table1.p, 0) AS p,
IFNULL(table2.p, 0) AS q,
FROM table1
OUTER JOIN table2
ON table1.i = table2.i
),
aggr AS (
SELECT
(SUM(p-q) OVER win) * (i - (LAG(i,1) OVER win)) AS emd
FROM joined_table
WINDOW win AS (
ORDER BY i
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
)
)
SELECT SUM(ABS(emd)) AS total_emd
FROM aggr