scikit-learn · Micky774 · Feb 7, 2023 · Feb 7, 2023 · Feb 8, 2023 · Feb 11, 2023
diff --git a/.gitignore b/.gitignore
@@ -97,6 +97,8 @@ sklearn/metrics/_pairwise_distances_reduction/_datasets_pair.pxd
 sklearn/metrics/_pairwise_distances_reduction/_datasets_pair.pyx
 sklearn/metrics/_pairwise_distances_reduction/_middle_term_computer.pxd
 sklearn/metrics/_pairwise_distances_reduction/_middle_term_computer.pyx
+sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pxd
+sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pyx
 sklearn/metrics/_pairwise_distances_reduction/_radius_neighbors.pxd
 sklearn/metrics/_pairwise_distances_reduction/_radius_neighbors.pyx
 sklearn/neighbors/_ball_tree.pyx

diff --git a/doc/whats_new/v1.4.rst b/doc/whats_new/v1.4.rst
@@ -199,6 +199,18 @@ Changelog
   for CSR × CSR,  Dense × CSR, and CSR × Dense datasets is now 1.5x faster.
   :pr:`26765` by :user:`Meekail Zain <micky774>`
 
+- |Efficiency| :func:`pairwise.pairwise_distances`' performance has been improved
+  when providing dense datasets.
+  :pr:`26983` by :user:`Meekail Zain <micky774>` and
+  :user:`Vincent Maladiere <Vincent-Maladiere>` and
+  :user:`Julien Jerphanion <jjerphan>`.
+
+- |Feature| :func:`pairwise.pairwise_distances` now supports combination of
+  dense arrays and sparse CSR matrices datasets.
+  :pr:`26983` by :user:`Meekail Zain <micky774>` and
+  :user:`Vincent Maladiere <Vincent-Maladiere>` and
+  :user:`Julien Jerphanion <jjerphan>`.
+
 :mod:`sklearn.utils`
 ....................
 

diff --git a/setup.cfg b/setup.cfg
@@ -51,6 +51,8 @@ ignore =
     sklearn/metrics/_pairwise_distances_reduction/_datasets_pair.pyx
     sklearn/metrics/_pairwise_distances_reduction/_middle_term_computer.pxd
     sklearn/metrics/_pairwise_distances_reduction/_middle_term_computer.pyx
+    sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pxd
+    sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pyx
     sklearn/metrics/_pairwise_distances_reduction/_radius_neighbors.pxd
     sklearn/metrics/_pairwise_distances_reduction/_radius_neighbors.pyx
     sklearn/neighbors/_ball_tree.pyx

diff --git a/setup.py b/setup.py
@@ -277,6 +277,12 @@ def check_package_status(package, min_version):
             "include_np": True,
             "extra_compile_args": ["-std=c++11"],
         },
+        {
+            "sources": ["_pairwise_distances.pyx.tp", "_pairwise_distances.pxd.tp"],
+            "language": "c++",
+            "include_np": True,
+            "extra_compile_args": ["-std=c++11"],
+        },
         {
             "sources": ["_argkmin.pyx.tp", "_argkmin.pxd.tp"],
             "language": "c++",

diff --git a/sklearn/metrics/_pairwise_distances_reduction/__init__.py b/sklearn/metrics/_pairwise_distances_reduction/__init__.py
@@ -90,13 +90,15 @@
     ArgKmin,
     ArgKminClassMode,
     BaseDistancesReductionDispatcher,
+    PairwiseDistances,
     RadiusNeighbors,
     sqeuclidean_row_norms,
 )
 
 __all__ = [
     "BaseDistancesReductionDispatcher",
     "ArgKmin",
+    "PairwiseDistances",
     "RadiusNeighbors",
     "ArgKminClassMode",
     "sqeuclidean_row_norms",

diff --git a/sklearn/metrics/_pairwise_distances_reduction/_dispatcher.py b/sklearn/metrics/_pairwise_distances_reduction/_dispatcher.py
@@ -19,6 +19,10 @@
     ArgKminClassMode64,
 )
 from ._base import _sqeuclidean_row_norms32, _sqeuclidean_row_norms64
+from ._pairwise_distances import (
+    PairwiseDistances32,
+    PairwiseDistances64,
+)
 from ._radius_neighbors import (
     RadiusNeighbors32,
     RadiusNeighbors64,
@@ -153,6 +157,150 @@ def compute(
         """
 
 
+class PairwiseDistances(BaseDistancesReductionDispatcher):
+    """Compute the pairwise distances matrix for two sets of vectors.
+
+    The distance function `dist` depends on the values of the `metric`
+    and `metric_kwargs` parameters.
+
+    This class only computes the pairwise distances matrix without
+    applying any reduction on it. It shares most of the underlying
+    code infrastructure with reducing variants to leverage multi-thread
+    parallelism. However contrary to the reducing variants, no chunking
+    is applied to allow for contiguous write access to the final distance
+    array that is not expected to fit in the CPU cache in general.
+
+    This class is not meant to be instantiated, one should only use
+    its :meth:`compute` classmethod which handles allocation and
+    deallocation consistently.
+    """
+
+    @classmethod
+    def valid_metrics(cls) -> List[str]:
+        excluded = {
+            # PyFunc cannot be supported because it necessitates interacting with
+            # the CPython interpreter to call user defined functions.
+            "pyfunc",
+            "mahalanobis",  # is numerically unstable
+            # In order to support discrete distance metrics, we need to have a
+            # stable simultaneous sort which preserves the order of the indices
+            # because there generally is a lot of occurrences for a given values
+            # of distances in this case.
+            # TODO: implement a stable simultaneous_sort.
+            "hamming",
+            *BOOL_METRICS,
+        }
+        return sorted(set(METRIC_MAPPING64.keys()) - excluded)
+
+    @classmethod
+    def compute(
+        cls,
+        X,
+        Y,
+        metric="euclidean",
+        metric_kwargs=None,
+        strategy=None,
+        n_jobs=-1,
+    ):
+        """Return pairwise distances matrix for the given arguments.
+
+        Parameters
+        ----------
+        X : ndarray or CSR matrix of shape (n_samples_X, n_features)
+            Input data.
+
+        Y : ndarray or CSR matrix of shape (n_samples_Y, n_features)
+            Input data.
+
+        metric : str, default='euclidean'
+            The distance metric to use.
+            For a list of available metrics, see the documentation of
+            :class:`~sklearn.metrics.DistanceMetric`.
+
+        metric_kwargs : dict, default=None
+            Keyword arguments to pass to specified metric function.
+
+        strategy : str, {'auto', 'parallel_on_X', 'parallel_on_Y'}, default=None
+            The strategy defining which dataset parallelization are made on.
+
+            For both strategies the computations happens with two nested loops,
+            respectively on rows of X and rows of Y.
+            Strategies differs on which loop (outer or inner) is made to run
+            in parallel with the Cython `prange` construct:
+
+              - 'parallel_on_X' dispatches rows of X uniformly on threads.
+                Each thread then iterates on all the rows of Y. This strategy is
+                embarrassingly parallel and comes with no datastructures
+                synchronisation.
+
+              - 'parallel_on_Y' dispatches rows of Y uniformly on threads.
+                Each thread processes all the rows of X in turn. This strategy is
+                a sequence of embarrassingly parallel subtasks (the inner loop on Y
+                chunks) with no intermediate datastructures synchronisation.
+
+              - 'auto' relies on a simple heuristic to choose between
+                'parallel_on_X' and 'parallel_on_Y': when `X.shape[0]` is large enough,
+                'parallel_on_X' is usually the most efficient strategy.
+                When `X.shape[0]` is small but `Y.shape[0]` is large, 'parallel_on_Y'
+                brings more opportunity for parallelism and is therefore more efficient.
+
+              - None (default) looks-up in scikit-learn configuration for
+                `pairwise_dist_parallel_strategy`, and use 'auto' if it is not set.
+
+        n_jobs : int, default=None
+            The number of jobs to use for the computation. This works by breaking
+            down the pairwise matrix into n_jobs even slices and computing them in
+            parallel.
+
+            ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
+            ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
+            for more details.
+
+        Returns
+        -------
+        pairwise_distances_matrix : ndarray of shape (n_samples_X, n_samples_Y)
+            The pairwise distances matrix.
+
+        Notes
+        -----
+        This public classmethod is responsible for introspecting the arguments
+        values to dispatch to the private dtype-specialized implementation of
+        :class:`PairwiseDistances`.
+
+        All temporarily allocated datastructures necessary for the concrete
+        implementations are therefore freed when this classmethod returns.
+
+        This allows entirely decoupling the API entirely from the
+        implementation details whilst maintaining RAII.
+        """
+        n_jobs = 1 if n_jobs is None else n_jobs
+        Y = X if Y is None else Y
+        if X.dtype == Y.dtype == np.float64:
+            return PairwiseDistances64.compute(
+                X=X,
+                Y=Y,
+                metric=metric,
+                metric_kwargs=metric_kwargs,
+                strategy=strategy,
+                n_jobs=n_jobs,
+            )
+
+        if X.dtype == Y.dtype == np.float32:
+            return PairwiseDistances32.compute(
+                X=X,
+                Y=Y,
+                metric=metric,
+                metric_kwargs=metric_kwargs,
+                strategy=strategy,
+                n_jobs=n_jobs,
+            )
+
+        raise ValueError(
+            "Only float64 or float32 datasets pairs are supported, but "
+            f"got: X.dtype={X.dtype} and Y.dtype={Y.dtype}."
+        )
+
+
 class ArgKmin(BaseDistancesReductionDispatcher):
     """Compute the argkmin of row vectors of X on the ones of Y.
 

diff --git a/sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pxd.tp b/sklearn/metrics/_pairwise_distances_reduction/_pairwise_distances.pxd.tp
@@ -0,0 +1,40 @@
+{{py:
+
+implementation_specific_values = [
+    # Values are the following ones:
+    #
+    #       name_suffix, INPUT_DTYPE_t
+    #
+    #
+    ('64', 'cnp.float64_t'),
+    ('32', 'cnp.float32_t')
+]
+
+}}
+cimport numpy as cnp
+
+from ...utils._typedefs cimport intp_t
+{{for name_suffix, INPUT_DTYPE_t in implementation_specific_values}}
+
+from ._datasets_pair cimport DatasetsPair{{name_suffix}}
+
+
+cdef class PairwiseDistances{{name_suffix}}:
+    """float{{name_suffix}} implementation of PairwiseDistances."""
+
+    cdef:
+        readonly DatasetsPair{{name_suffix}} datasets_pair
+
+        intp_t n_samples_X, n_samples_Y
+        intp_t effective_n_threads
+        bint X_is_Y
+        bint execute_in_parallel_on_Y
+
+        {{INPUT_DTYPE_t}}[:, ::1] pairwise_distances_matrix
+
+    cdef void _parallel_on_X(self) nogil
+
+    cdef void _parallel_on_Y(self) nogil
+
+
+{{endfor}}