diff options
-rw-r--r-- | src/python/doc/point_cloud_sum.inc | 4 | ||||
-rw-r--r-- | src/python/gudhi/cubical_complex.pyx | 46 | ||||
-rw-r--r-- | src/python/gudhi/periodic_cubical_complex.pyx | 50 | ||||
-rw-r--r-- | src/python/gudhi/point_cloud/dtm.py | 109 | ||||
-rw-r--r-- | src/python/gudhi/point_cloud/knn.py | 4 | ||||
-rwxr-xr-x | src/python/test/test_dtm.py | 23 |
6 files changed, 195 insertions, 41 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/cubical_complex.pyx b/src/python/gudhi/cubical_complex.pyx index ca979eda..3ace2517 100644 --- a/src/python/gudhi/cubical_complex.pyx +++ b/src/python/gudhi/cubical_complex.pyx @@ -27,20 +27,20 @@ __license__ = "MIT" cdef extern from "Cubical_complex_interface.h" namespace "Gudhi": cdef cppclass Bitmap_cubical_complex_base_interface "Gudhi::Cubical_complex::Cubical_complex_interface<>": - Bitmap_cubical_complex_base_interface(vector[unsigned] dimensions, vector[double] top_dimensional_cells) - Bitmap_cubical_complex_base_interface(string perseus_file) - int num_simplices() - int dimension() + Bitmap_cubical_complex_base_interface(vector[unsigned] dimensions, vector[double] top_dimensional_cells) nogil + Bitmap_cubical_complex_base_interface(string perseus_file) nogil + int num_simplices() nogil + int dimension() nogil cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Cubical_complex_persistence_interface "Gudhi::Persistent_cohomology_interface<Gudhi::Cubical_complex::Cubical_complex_interface<>>": - Cubical_complex_persistence_interface(Bitmap_cubical_complex_base_interface * st, bool persistence_dim_max) - void compute_persistence(int homology_coeff_field, double min_persistence) - vector[pair[int, pair[double, double]]] get_persistence() - vector[vector[int]] cofaces_of_cubical_persistence_pairs() - vector[int] betti_numbers() - vector[int] persistent_betti_numbers(double from_value, double to_value) - vector[pair[double,double]] intervals_in_dimension(int dimension) + Cubical_complex_persistence_interface(Bitmap_cubical_complex_base_interface * st, bool persistence_dim_max) nogil + void compute_persistence(int homology_coeff_field, double min_persistence) nogil + vector[pair[int, pair[double, double]]] get_persistence() nogil + vector[vector[int]] cofaces_of_cubical_persistence_pairs() nogil + vector[int] betti_numbers() nogil + vector[int] persistent_betti_numbers(double from_value, double to_value) nogil + vector[pair[double,double]] intervals_in_dimension(int dimension) nogil # CubicalComplex python interface cdef class CubicalComplex: @@ -80,7 +80,7 @@ cdef class CubicalComplex: perseus_file=''): if ((dimensions is not None) and (top_dimensional_cells is not None) and (perseus_file == '')): - self.thisptr = new Bitmap_cubical_complex_base_interface(dimensions, top_dimensional_cells) + self._construct_from_cells(dimensions, top_dimensional_cells) elif ((dimensions is None) and (top_dimensional_cells is not None) and (perseus_file == '')): top_dimensional_cells = np.array(top_dimensional_cells, @@ -88,11 +88,11 @@ cdef class CubicalComplex: order = 'F') dimensions = top_dimensional_cells.shape top_dimensional_cells = top_dimensional_cells.ravel(order='F') - self.thisptr = new Bitmap_cubical_complex_base_interface(dimensions, top_dimensional_cells) + self._construct_from_cells(dimensions, top_dimensional_cells) elif ((dimensions is None) and (top_dimensional_cells is None) and (perseus_file != '')): if os.path.isfile(perseus_file): - self.thisptr = new Bitmap_cubical_complex_base_interface(perseus_file.encode('utf-8')) + self._construct_from_file(perseus_file.encode('utf-8')) else: raise FileNotFoundError(errno.ENOENT, os.strerror(errno.ENOENT), perseus_file) @@ -101,6 +101,14 @@ cdef class CubicalComplex: "top_dimensional_cells or from a Perseus-style file name.", file=sys.stderr) + def _construct_from_cells(self, vector[unsigned] dimensions, vector[double] top_dimensional_cells): + with nogil: + self.thisptr = new Bitmap_cubical_complex_base_interface(dimensions, top_dimensional_cells) + + def _construct_from_file(self, string filename): + with nogil: + self.thisptr = new Bitmap_cubical_complex_base_interface(filename) + def __dealloc__(self): if self.thisptr != NULL: del self.thisptr @@ -151,8 +159,11 @@ cdef class CubicalComplex: if self.pcohptr != NULL: del self.pcohptr assert self.__is_defined() - self.pcohptr = new Cubical_complex_persistence_interface(self.thisptr, True) - self.pcohptr.compute_persistence(homology_coeff_field, min_persistence) + cdef int field = homology_coeff_field + cdef double minp = min_persistence + with nogil: + self.pcohptr = new Cubical_complex_persistence_interface(self.thisptr, 1) + self.pcohptr.compute_persistence(field, minp) def persistence(self, homology_coeff_field=11, min_persistence=0): """This function computes and returns the persistence of the complex. @@ -204,7 +215,8 @@ cdef class CubicalComplex: cdef vector[vector[int]] persistence_result output = [[],[]] - persistence_result = self.pcohptr.cofaces_of_cubical_persistence_pairs() + with nogil: + persistence_result = self.pcohptr.cofaces_of_cubical_persistence_pairs() pr = np.array(persistence_result) ess_ind = np.argwhere(pr[:,2] == -1)[:,0] diff --git a/src/python/gudhi/periodic_cubical_complex.pyx b/src/python/gudhi/periodic_cubical_complex.pyx index 06309772..bed55101 100644 --- a/src/python/gudhi/periodic_cubical_complex.pyx +++ b/src/python/gudhi/periodic_cubical_complex.pyx @@ -24,20 +24,20 @@ __license__ = "MIT" cdef extern from "Cubical_complex_interface.h" namespace "Gudhi": cdef cppclass Periodic_cubical_complex_base_interface "Gudhi::Cubical_complex::Cubical_complex_interface<Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base<double>>": - Periodic_cubical_complex_base_interface(vector[unsigned] dimensions, vector[double] top_dimensional_cells, vector[bool] periodic_dimensions) - Periodic_cubical_complex_base_interface(string perseus_file) - int num_simplices() - int dimension() + Periodic_cubical_complex_base_interface(vector[unsigned] dimensions, vector[double] top_dimensional_cells, vector[bool] periodic_dimensions) nogil + Periodic_cubical_complex_base_interface(string perseus_file) nogil + int num_simplices() nogil + int dimension() nogil cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Periodic_cubical_complex_persistence_interface "Gudhi::Persistent_cohomology_interface<Gudhi::Cubical_complex::Cubical_complex_interface<Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base<double>>>": - Periodic_cubical_complex_persistence_interface(Periodic_cubical_complex_base_interface * st, bool persistence_dim_max) - void compute_persistence(int homology_coeff_field, double min_persistence) - vector[pair[int, pair[double, double]]] get_persistence() - vector[vector[int]] cofaces_of_cubical_persistence_pairs() - vector[int] betti_numbers() - vector[int] persistent_betti_numbers(double from_value, double to_value) - vector[pair[double,double]] intervals_in_dimension(int dimension) + Periodic_cubical_complex_persistence_interface(Periodic_cubical_complex_base_interface * st, bool persistence_dim_max) nogil + void compute_persistence(int homology_coeff_field, double min_persistence) nogil + vector[pair[int, pair[double, double]]] get_persistence() nogil + vector[vector[int]] cofaces_of_cubical_persistence_pairs() nogil + vector[int] betti_numbers() nogil + vector[int] persistent_betti_numbers(double from_value, double to_value) nogil + vector[pair[double,double]] intervals_in_dimension(int dimension) nogil # PeriodicCubicalComplex python interface cdef class PeriodicCubicalComplex: @@ -81,9 +81,7 @@ cdef class PeriodicCubicalComplex: periodic_dimensions=None, perseus_file=''): if ((dimensions is not None) and (top_dimensional_cells is not None) and (periodic_dimensions is not None) and (perseus_file == '')): - self.thisptr = new Periodic_cubical_complex_base_interface(dimensions, - top_dimensional_cells, - periodic_dimensions) + self._construct_from_cells(dimensions, top_dimensional_cells, periodic_dimensions) elif ((dimensions is None) and (top_dimensional_cells is not None) and (periodic_dimensions is not None) and (perseus_file == '')): top_dimensional_cells = np.array(top_dimensional_cells, @@ -91,13 +89,11 @@ cdef class PeriodicCubicalComplex: order = 'F') dimensions = top_dimensional_cells.shape top_dimensional_cells = top_dimensional_cells.ravel(order='F') - self.thisptr = new Periodic_cubical_complex_base_interface(dimensions, - top_dimensional_cells, - periodic_dimensions) + self._construct_from_cells(dimensions, top_dimensional_cells, periodic_dimensions) elif ((dimensions is None) and (top_dimensional_cells is None) and (periodic_dimensions is None) and (perseus_file != '')): if os.path.isfile(perseus_file): - self.thisptr = new Periodic_cubical_complex_base_interface(perseus_file.encode('utf-8')) + self._construct_from_file(perseus_file.encode('utf-8')) else: print("file " + perseus_file + " not found.", file=sys.stderr) else: @@ -106,6 +102,14 @@ cdef class PeriodicCubicalComplex: "top_dimensional_cells and periodic_dimensions or from " "a Perseus-style file name.", file=sys.stderr) + def _construct_from_cells(self, vector[unsigned] dimensions, vector[double] top_dimensional_cells, vector[bool] periodic_dimensions): + with nogil: + self.thisptr = new Periodic_cubical_complex_base_interface(dimensions, top_dimensional_cells, periodic_dimensions) + + def _construct_from_file(self, string filename): + with nogil: + self.thisptr = new Periodic_cubical_complex_base_interface(filename) + def __dealloc__(self): if self.thisptr != NULL: del self.thisptr @@ -156,8 +160,11 @@ cdef class PeriodicCubicalComplex: if self.pcohptr != NULL: del self.pcohptr assert self.__is_defined() - self.pcohptr = new Periodic_cubical_complex_persistence_interface(self.thisptr, True) - self.pcohptr.compute_persistence(homology_coeff_field, min_persistence) + cdef int field = homology_coeff_field + cdef double minp = min_persistence + with nogil: + self.pcohptr = new Periodic_cubical_complex_persistence_interface(self.thisptr, 1) + self.pcohptr.compute_persistence(field, minp) def persistence(self, homology_coeff_field=11, min_persistence=0): """This function computes and returns the persistence of the complex. @@ -207,7 +214,8 @@ cdef class PeriodicCubicalComplex: cdef vector[vector[int]] persistence_result if self.pcohptr != NULL: output = [[],[]] - persistence_result = self.pcohptr.cofaces_of_cubical_persistence_pairs() + with nogil: + persistence_result = self.pcohptr.cofaces_of_cubical_persistence_pairs() pr = np.array(persistence_result) ess_ind = np.argwhere(pr[:,2] == -1)[:,0] diff --git a/src/python/gudhi/point_cloud/dtm.py b/src/python/gudhi/point_cloud/dtm.py index 13e16d24..55ac58e6 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,111 @@ 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). Optional if it can be guessed + from weights or metric="neighbors". + 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: + self.k = k + if k is None: + assert kwargs.get("metric") == "neighbors", 'Must specify k or weights, unless metric is "neighbors"' + self.weights = None + else: + 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 + k = self.k + weights = self.weights + if self.params["metric"] == "neighbors": + distances = np.asarray(X) + if weights is None: + k = distances.shape[1] + weights = np.full(k, 1.0 / k) + else: + distances = distances[:, :k] + else: + distances = self.knn.transform(X) + distances = distances ** q + dtm = (distances * weights).sum(-1) + if self.normalize: + dtm /= (np.arange(1, k + 1) ** (q / dim) * 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..0a52279e 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,23 @@ 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) + distances = [[0, 1], [2, 0], [1, 3]] + density = DTMDensity(metric="neighbors", dim=1).fit_transform(distances) + assert density == pytest.approx(expected) + density = DTMDensity(weights=[0.5, 0.5], metric="neighbors", dim=1).fit_transform(distances) + assert density == pytest.approx(expected) |