Computing Earth Movers Distance

[jamied157]

So currently we have two ways of computing EMD, the first is found here which essentially assumes each category is equidistant from one another:

insight/src/synthesized_insight/metrics/metrics.py

Lines 197 to 241 in 8d17059

	class EarthMoversDistance(TwoColumnMetric):
	"""Earth mover's distance (aka 1-Wasserstein distance) between two nominal variables.
	The statistic ranges from 0 to 1, where a value of 0 indicates the two variables follow identical distributions,
	and a value of 1 indicates they follow completely different distributions.
	"""
	name = "earth_movers_distance"
	@classmethod
	def check_column_types(cls, check: ColumnCheck, sr_a: pd.Series, sr_b: pd.Series) -> bool:
	if not check.categorical(sr_a) or not check.categorical(sr_b):
	return False
	return True
	def _compute_metric(self, sr_a: pd.Series, sr_b: pd.Series):
	"""Calculate the metric.
	Args:
	sr_a (pd.Series): values of a nominal variable.
	sr_b (pd.Series): values of another nominal variable to compare.
	Returns:
	The earth mover's distance between sr_a and sr_b.
	"""
	old = sr_a.to_numpy().astype(str)
	new = sr_b.to_numpy().astype(str)
	space = set(old).union(set(new))
	if len(space) > 1e4:
	return np.nan
	old_unique, counts = np.unique(old, return_counts=True)
	old_counts = dict(zip(old_unique, counts))
	new_unique, counts = np.unique(new, return_counts=True)
	new_counts = dict(zip(new_unique, counts))
	p = np.array([float(old_counts[x]) if x in old_counts else 0.0 for x in space])
	q = np.array([float(new_counts[x]) if x in new_counts else 0.0 for x in space])
	p /= np.sum(p)
	q /= np.sum(q)
	distance = 0.5 * np.sum(np.abs(p.astype(np.float64) - q.astype(np.float64)))
	return distance

The second is here which I think takes an already binned set of variables and uses the centre of the bins to calculate the distance:

insight/src/synthesized_insight/metrics/distance.py

Lines 358 to 405 in f88cf96

	class EarthMoversDistanceBinned(BinnedMetricStatistics):
	"""Earth mover's distance (aka 1-Wasserstein distance) statistics between two nominal variables.
	The histograms can represent counts of nominal categories or counts on
	an ordinal range. If the latter, they must have equal binning.
	The metric value ranges from 0 to 1, where a value of 0 indicates the two variables follow identical distributions,
	and a value of 1 indicates they follow completely different distributions.
	"""
	name = "earth_movers_distance_binned"
	def _compute_metric(self, sr_a: pd.Series, sr_b: pd.Series) -> MetricStatisticsResult:
	"""Calculate the metric.
	Args:
	sr_a (pd.Series): values of a nominal variable.
	sr_b (pd.Series): values of another nominal variable to compare.
	Returns:
	MetricStatisticsResult object containing the earth mover's binned distance between sr_a and sr_b,
	p-value and the confidence interval.
	"""
	if sr_a.sum() == 0 and sr_b.sum() == 0:
	return MetricStatisticsResult(0., None, None)
	elif sr_a.sum() == 0 or sr_b.sum() == 0:
	return MetricStatisticsResult(1., None, None)
	# normalise counts for consistency with scipy.stats.wasserstein
	with np.errstate(divide='ignore', invalid='ignore'):
	x = np.nan_to_num(sr_a / sr_a.sum())
	y = np.nan_to_num(sr_b / sr_b.sum())
	if self.bins is None:
	# if bins not given, histograms are assumed to be counts of nominal categories,
	# and therefore distances betwen bins are meaningless. Set to all distances to
	# unity to model this.
	distance = 0.5 * np.sum(np.abs(x.astype(np.float64) - y.astype(np.float64)))
	else:
	# otherwise, use pair-wise euclidean distances between bin centers for scale data
	bin_centers = self.bins[:-1] + np.diff(self.bins) / 2.
	distance = wasserstein_distance(bin_centers, bin_centers, u_weights=x, v_weights=y)
	result = MetricStatisticsResult(metric_value=distance)
	if self.compute_p_val:
	result.p_value = self._compute_p_value(sr_a, sr_b, distance)
	if self.compute_interval:
	result.interval = self._compute_interval(sr_a, sr_b, distance)
	return result

I think we should have a way of calculating distances for affine variables even if they aren't binned. We should check these metrics agree with pyemd.

[simonhkswan]

We have this in the SDK, so shall we move it across?

https://github.com/synthesized-io/synthesized/blob/a894520b7e61abba7b06a94a22377ea598ac6bfc/synthesized/insight/metrics/distance.py#L485-L498

class EarthMoversDistance(DistanceMetric):
    """
    Earth movers distance (EMD), aka Wasserstein 1-distance, between samples from two distributions.
    """

    @property
    def distance(self) -> float:
        """
        Calculate the EMD between two 1d histograms.
        Returns:
            The earth mover's distance.
        """
        return wasserstein_distance(self.x, self.y)

[simonhkswan]

As for comparing to pyemd, this was done when the code was swapped: synthesized-io/synthesized#564

[jamied157]

Great thanks for sharing!