diff options
| -rw-r--r-- | src/python/doc/point_cloud_sum.inc | 4 | ||||
| -rw-r--r-- | src/python/gudhi/point_cloud/dtm.py | 97 | ||||
| -rw-r--r-- | src/python/gudhi/point_cloud/knn.py | 4 | ||||
| -rwxr-xr-x | src/python/test/test_dtm.py | 18 |
4 files changed, 120 insertions, 3 deletions
diff --git a/src/python/doc/point_cloud_sum.inc b/src/python/doc/point_cloud_sum.inc index 4315cea6..f955c3ab 100644 --- a/src/python/doc/point_cloud_sum.inc +++ b/src/python/doc/point_cloud_sum.inc @@ -3,8 +3,8 @@ +-----------------------------------+---------------------------------------------------------------+-------------------------------------------------------------------+ | | :math:`(x_1, x_2, \ldots, x_d)` | Utilities to process point clouds: read from file, subsample, | :Authors: Vincent Rouvreau, Marc Glisse, Masatoshi Takenouchi | - | | :math:`(y_1, y_2, \ldots, y_d)` | find neighbors, embed time series in higher dimension, etc. | | - | | | :Since: GUDHI 2.0.0 | + | | :math:`(y_1, y_2, \ldots, y_d)` | find neighbors, embed time series in higher dimension, | | + | | estimate a density, etc. | :Since: GUDHI 2.0.0 | | | | | | | | :License: MIT (`GPL v3 </licensing/>`_, BSD-3-Clause, Apache-2.0) | +-----------------------------------+---------------------------------------------------------------+-------------------------------------------------------------------+ diff --git a/src/python/gudhi/point_cloud/dtm.py b/src/python/gudhi/point_cloud/dtm.py index 13e16d24..88f197e7 100644 --- a/src/python/gudhi/point_cloud/dtm.py +++ b/src/python/gudhi/point_cloud/dtm.py @@ -8,6 +8,7 @@ # - YYYY/MM Author: Description of the modification from .knn import KNearestNeighbors +import numpy as np __author__ = "Marc Glisse" __copyright__ = "Copyright (C) 2020 Inria" @@ -68,3 +69,99 @@ class DistanceToMeasure: # We compute too many powers, 1/p in knn then q in dtm, 1/q in dtm then q or some log in the caller. # Add option to skip the final root? return dtm + + +class DTMDensity: + """ + Density estimator based on the distance to the empirical measure defined by a point set, as defined + in :cite:`dtmdensity`. Note that this implementation only renormalizes when asked, and the renormalization + only works for a Euclidean metric, so in other cases the total measure may not be 1. + + .. note:: When the dimension is high, using it as an exponent can quickly lead to under- or overflows. + We recommend using a small fixed value instead in those cases, even if it won't have the same nice + theoretical properties as the dimension. + """ + + def __init__(self, k=None, weights=None, q=None, dim=None, normalize=False, n_samples=None, **kwargs): + """ + Args: + k (int): number of neighbors (possibly including the point itself). + weights (numpy.array): weights of each of the k neighbors, optional. They are supposed to sum to 1. + q (float): order used to compute the distance to measure. Defaults to dim. + dim (float): final exponent representing the dimension. Defaults to the dimension, and must be specified + when the dimension cannot be read from the input (metric is "neighbors" or "precomputed"). + normalize (bool): normalize the density so it corresponds to a probability measure on ℝᵈ. + Only available for the Euclidean metric, defaults to False. + n_samples (int): number of sample points used for fitting. Only needed if `normalize` is True and + metric is "neighbors". + kwargs: same parameters as :class:`~gudhi.point_cloud.knn.KNearestNeighbors`, except that metric="neighbors" means that + :func:`transform` expects an array with the distances to the k nearest neighbors. + """ + if weights is None: + assert k is not None, "Must specify k or weights" + self.k = k + self.weights = np.full(k, 1.0 / k) + else: + self.weights = weights + self.k = len(weights) + assert k is None or k == self.k, "k differs from the length of weights" + self.q = q + self.dim = dim + self.params = kwargs + self.normalize = normalize + self.n_samples = n_samples + + def fit_transform(self, X, y=None): + return self.fit(X).transform(X) + + def fit(self, X, y=None): + """ + Args: + X (numpy.array): coordinates for mass points. + """ + if self.params.setdefault("metric", "euclidean") != "neighbors": + self.knn = KNearestNeighbors( + self.k, return_index=False, return_distance=True, sort_results=False, **self.params + ) + self.knn.fit(X) + if self.params["metric"] != "precomputed": + self.n_samples = len(X) + return self + + def transform(self, X): + """ + Args: + X (numpy.array): coordinates for query points, or distance matrix if metric is "precomputed", + or distances to the k nearest neighbors if metric is "neighbors" (if the array has more + than k columns, the remaining ones are ignored). + """ + q = self.q + dim = self.dim + if dim is None: + assert self.params["metric"] not in { + "neighbors", + "precomputed", + }, "dim not specified and cannot guess the dimension" + dim = len(X[0]) + if q is None: + q = dim + if self.params["metric"] == "neighbors": + distances = np.asarray(X)[:, : self.k] + else: + distances = self.knn.transform(X) + distances = distances ** q + dtm = (distances * self.weights).sum(-1) + if self.normalize: + dtm /= (np.arange(1, self.k + 1) ** (q / dim) * self.weights).sum() + density = dtm ** (-dim / q) + if self.normalize: + import math + + if self.params["metric"] == "precomputed": + self.n_samples = len(X[0]) + # Volume of d-ball + Vd = math.pi ** (dim / 2) / math.gamma(dim / 2 + 1) + density /= self.n_samples * Vd + return density + # We compute too many powers, 1/p in knn then q in dtm, d/q in dtm then whatever in the caller. + # Add option to skip the final root? diff --git a/src/python/gudhi/point_cloud/knn.py b/src/python/gudhi/point_cloud/knn.py index 86008bc3..4652fe80 100644 --- a/src/python/gudhi/point_cloud/knn.py +++ b/src/python/gudhi/point_cloud/knn.py @@ -306,6 +306,10 @@ class KNearestNeighbors: if self.params["implementation"] == "ckdtree": qargs = {key: val for key, val in self.params.items() if key in {"p", "eps", "n_jobs"}} distances, neighbors = self.kdtree.query(X, k=self.k, **qargs) + if k == 1: + # SciPy decided to squeeze the last dimension for k=1 + distances = distances[:, None] + neighbors = neighbors[:, None] if self.return_index: if self.return_distance: return neighbors, distances diff --git a/src/python/test/test_dtm.py b/src/python/test/test_dtm.py index bff4c267..8ab0cc44 100755 --- a/src/python/test/test_dtm.py +++ b/src/python/test/test_dtm.py @@ -8,10 +8,11 @@ - YYYY/MM Author: Description of the modification """ -from gudhi.point_cloud.dtm import DistanceToMeasure +from gudhi.point_cloud.dtm import DistanceToMeasure, DTMDensity import numpy import pytest import torch +import math def test_dtm_compare_euclidean(): @@ -66,3 +67,18 @@ def test_dtm_precomputed(): dtm = DistanceToMeasure(2, q=2, metric="neighbors") r = dtm.fit_transform(dist) assert r == pytest.approx([2.0, 0.707, 3.5355], rel=0.01) + + +def test_density_normalized(): + sample = numpy.random.normal(0, 1, (1000000, 2)) + queries = numpy.array([[0.0, 0.0], [-0.5, 0.7], [0.4, 1.7]]) + expected = numpy.exp(-(queries ** 2).sum(-1) / 2) / (2 * math.pi) + estimated = DTMDensity(k=150, normalize=True).fit(sample).transform(queries) + assert estimated == pytest.approx(expected, rel=0.4) + + +def test_density(): + distances = [[0, 1, 10], [2, 0, 30], [1, 3, 5]] + density = DTMDensity(k=2, metric="neighbors", dim=1).fit_transform(distances) + expected = numpy.array([2.0, 1.0, 0.5]) + assert density == pytest.approx(expected) |