Improve the metrics API

### Describe the workflow you want to enable

Currently metrics in scikit-learn have several shortcomings:
- Although it is possible to pass custom metrics as callables, they are called for each pair of inputs. This makes impossible to create custom metrics with the same performance as the existing ones (#22219).
- Every metric has different additional parameters. This requires that methods using them expose the particular parameters or provide a catch all `metric_params` parameter (and not all of them do that).
- Currently, metrics for types other than numeric vectors are not well supported (#15932).
- Some metrics, such as Mahalanobis, depend on the data. There is currently no way to use them in a cross-validation setting without incurring in data leakage (#6915).

### Describe your proposed solution

IMHO, metrics should be:
- Instances of classes, not functions. The additional parameters of the metrics (e.g. the `p` for Minkowski) could then be passed to the metric at creation time. Advantages: no need to homogeneize args, no need for `metric_params`. If the metrics inherit from `BaseEstimator`, the parameters could also be optimized in cross validation.
- They should accept two matrices with the same first dimension and compute all the paired distances. Advantage: no distinction between provided metrics and custom metrics: all of them could be implemented efficiently without multiple calls for each pair of vectors.
- There should be a way to implement an optimized version of pairwise distances. Although a default ok-ish version can be implemented by calling the function several times with the necessary matrices, for some metrics it is possible to have a better implementation. Either there should be a `Metric` ABC class with a default `pairwise` method that can be overriden, or a `singledispatch` function could be made for pairwise distances, so that one can register the implementation for their class. Advantages: again, allowing custom metrics to be implemented efficiently.
- Metrics know their input types. One should be able to provide metrics to compare strings or other custom types, and algorithms that only need to apply a metric, such as k-NN classification, should delegate the validation to the metric.
- (Optional) Some metrics, such as Mahalanobis, depend on the data. These metrics could have a `fit` method, allowing them to be used in cross-validation without incurring in data leakage.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
> Our scorers are now instances, and with metadata routing some of the issues here are solved. What's left from this issue? Some performance issues?

Sorry, @adrinjalali, I forgot to answer this. This has nothing to do with scorers, we are talking about distances here. And almost all the issues seem unresolved.

Right now in my package ([scikit-fda](https://github.com/GAA-UAM/scikit-fda)), we implement several metrics for functional data in a vectorized way (equivalent to computing `paired_distances` in one call). However, whenever we have to interface with scikit-learn (for example, to use k-NN), we have to use precomputed metrics, because the only way to pass a custom metric is ridiculously slow (it calls the function for each pair of data, instead of just once for all the pairs that need to be computed).

We tried making our metrics inherit from `DistanceMetric` and pass it directly, but it is seemingly not yet supported. If we pass our custom types directly we get this error:

<details>

```python
ValueError                                Traceback (most recent call last)
Cell In[10], line 5
      2 # Use it in KNeighborsClassifier 
      4 neigh = KNeighborsClassifier(n_neighbors=2, metric=my_metric)
----> 5 neigh.fit(X_train, y_train)

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/base.py:1389, in _fit_context.<locals>.decorator.<locals>.wrapper(estimator, *args, **kwargs)
   1382     estimator._validate_params()
   1384 with config_context(
   1385     skip_parameter_validation=(
   1386         prefer_skip_nested_validation or global_skip_validation
   1387     )
   1388 ):
-> 1389     return fit_method(estimator, *args, **kwargs)

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/neighbors/_classification.py:239, in KNeighborsClassifier.fit(self, X, y)
    217 @_fit_context(
    218     # KNeighborsClassifier.metric is not validated yet
    219     prefer_skip_nested_validation=False
    220 )
    221 def fit(self, X, y):
    222     """Fit the k-nearest neighbors classifier from the training dataset.
    223 
    224     Parameters
   (...)
    237         The fitted k-nearest neighbors classifier.
    238     """
--> 239     return self._fit(X, y)

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/neighbors/_base.py:478, in NeighborsBase._fit(self, X, y)
    476 if self.__sklearn_tags__().target_tags.required:
    477     if not isinstance(X, (KDTree, BallTree, NeighborsBase)):
--> 478         X, y = validate_data(
    479             self,
    480             X,
    481             y,
    482             accept_sparse="csr",
    483             multi_output=True,
    484             order="C",
    485             ensure_all_finite=ensure_all_finite,
    486         )
    488     if is_classifier(self):
    489         # Classification targets require a specific format
    490         if y.ndim == 1 or y.ndim == 2 and y.shape[1] == 1:

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/utils/validation.py:2961, in validate_data(_estimator, X, y, reset, validate_separately, skip_check_array, **check_params)
   2959         y = check_array(y, input_name="y", **check_y_params)
   2960     else:
-> 2961         X, y = check_X_y(X, y, **check_params)
   2962     out = X, y
   2964 if not no_val_X and check_params.get("ensure_2d", True):

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/utils/validation.py:1370, in check_X_y(X, y, accept_sparse, accept_large_sparse, dtype, order, copy, force_writeable, force_all_finite, ensure_all_finite, ensure_2d, allow_nd, multi_output, ensure_min_samples, ensure_min_features, y_numeric, estimator)
   1364     raise ValueError(
   1365         f"{estimator_name} requires y to be passed, but the target y is None"
   1366     )
   1368 ensure_all_finite = _deprecate_force_all_finite(force_all_finite, ensure_all_finite)
-> 1370 X = check_array(
   1371     X,
   1372     accept_sparse=accept_sparse,
   1373     accept_large_sparse=accept_large_sparse,
   1374     dtype=dtype,
   1375     order=order,
   1376     copy=copy,
   1377     force_writeable=force_writeable,
   1378     ensure_all_finite=ensure_all_finite,
   1379     ensure_2d=ensure_2d,
   1380     allow_nd=allow_nd,
   1381     ensure_min_samples=ensure_min_samples,
   1382     ensure_min_features=ensure_min_features,
   1383     estimator=estimator,
   1384     input_name="X",
   1385 )
   1387 y = _check_y(y, multi_output=multi_output, y_numeric=y_numeric, estimator=estimator)
   1389 check_consistent_length(X, y)

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/utils/validation.py:1093, in check_array(array, accept_sparse, accept_large_sparse, dtype, order, copy, force_writeable, force_all_finite, ensure_all_finite, ensure_non_negative, ensure_2d, allow_nd, ensure_min_samples, ensure_min_features, estimator, input_name)
   1086         else:
   1087             msg = (
   1088                 f"Expected 2D array, got 1D array instead:\narray={array}.\n"
   1089                 "Reshape your data either using array.reshape(-1, 1) if "
   1090                 "your data has a single feature or array.reshape(1, -1) "
   1091                 "if it contains a single sample."
   1092             )
-> 1093         raise ValueError(msg)
   1095 if dtype_numeric and hasattr(array.dtype, "kind") and array.dtype.kind in "USV":
   1096     raise ValueError(
   1097         "dtype='numeric' is not compatible with arrays of bytes/strings."
   1098         "Convert your data to numeric values explicitly instead."
   1099     )

ValueError: Expected a 2-dimensional container but got <class 'skfda.representation.grid.FDataGrid'> instead. Pass a DataFrame containing a single row (i.e. single sample) or a single column (i.e. single feature) instead.
```
</details>

This could be allowed if the validation is delegated to the metric itself, which was one of my proposals in this issue.

In addition, if we wrap our object as an `ExtensionArray` column in a Pandas DataFrame, we get the following error:

<details>

```python
InvalidParameterError                     Traceback (most recent call last)
Cell In[12], line 2
      1 X_df_test = pd.DataFrame(X_test)
----> 2 neigh.predict(X_df_test)

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/neighbors/_classification.py:274, in KNeighborsClassifier.predict(self, X)
    271         return self.classes_[np.argmax(probabilities, axis=1)]
    272     # In that case, we do not need the distances to perform
    273     # the weighting so we do not compute them.
--> 274     neigh_ind = self.kneighbors(X, return_distance=False)
    275     neigh_dist = None
    276 else:

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/neighbors/_base.py:906, in KNeighborsMixin.kneighbors(self, X, n_neighbors, return_distance)
    902     else:
    903         kwds = self.effective_metric_params_
    905     chunked_results = list(
--> 906         pairwise_distances_chunked(
    907             X,
    908             self._fit_X,
    909             reduce_func=reduce_func,
    910             metric=self.effective_metric_,
    911             n_jobs=n_jobs,
    912             **kwds,
    913         )
    914     )
    916 elif self._fit_method in ["ball_tree", "kd_tree"]:
    917     if issparse(X):

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/utils/_param_validation.py:206, in validate_params.<locals>.decorator.<locals>.wrapper(*args, **kwargs)
    203 to_ignore += ["self", "cls"]
    204 params = {k: v for k, v in params.arguments.items() if k not in to_ignore}
--> 206 validate_parameter_constraints(
    207     parameter_constraints, params, caller_name=func.__qualname__
    208 )
    210 try:
    211     with config_context(
    212         skip_parameter_validation=(
    213             prefer_skip_nested_validation or global_skip_validation
    214         )
    215     ):

File ~/miniconda3/envs/scikit-fda/lib/python3.12/site-packages/sklearn/utils/_param_validation.py:98, in validate_parameter_constraints(parameter_constraints, params, caller_name)
     92 else:
     93     constraints_str = (
     94         f"{', '.join([str(c) for c in constraints[:-1]])} or"
     95         f" {constraints[-1]}"
     96     )
---> 98 raise InvalidParameterError(
     99     f"The {param_name!r} parameter of {caller_name} must be"
    100     f" {constraints_str}. Got {param_val!r} instead."
    101 )

InvalidParameterError: The 'metric' parameter of pairwise_distances_chunked must be a str among {'seuclidean', 'matching', 'minkowski', 'nan_euclidean', 'l2', 'wminkowski', 'cosine', 'l1', 'russellrao', 'correlation', 'rogerstanimoto', 'precomputed', 'canberra', 'sqeuclidean', 'cityblock', 'hamming', 'jaccard', 'sokalsneath', 'haversine', 'chebyshev', 'dice', 'braycurtis', 'yule', 'mahalanobis', 'euclidean', 'manhattan', 'sokalmichener'} or a callable. Got <__main__.myMetric object at 0x7babf0753470> instead.
```

</details>

Thus, I guess that `DistanceMetric` objects are not yet allowed in general.

To summarize, my proposal here would be:
 - That scikit-learn provides a class (or maybe better a protocol) `Metric` that can be used whenever a metric is needed. This class can be subclassed to provide particular metrics, both for scikit-learn metrics (e.g. a `Minkowski` class with a float parameter `p`) or for other packages in the Python scientific ecosystem (the equivalent class for functional data would be `LpDistance`, also with a parameter `p`) .
 - Particular instances of these subclasses can be provided by default for common metrics: `euclidean = Minkowski(p=2)`.
 - Metrics can  be called to compute the paired distance between two arbitrary "arrays" of objects (not necessarily NumPy arrays, but behaving like one).
 - Validation should be left to the metric (probably with a `validate` method, in order to not do it in every call).
 - An optional `pairwise_distances` method can be provided to have a more efficient implementation of pairwise distances. If not provided, a default implementation is used, based on calling the function (which is equivalent to paired distances).
 - Metrics should be estimators, so that some parameters (such as weights) can be optimized for. 
     - In addition, some metrics, like `Mahalanobis`, could benefit if an optional `fit` method was allowed.

I think this would be a **much** better API than the current one, in particular regarding flexibility and extensibility.

Labels: New Feature, API, Needs Decision, module:metrics