Repository: scikit-learn/scikit-learn
Pull request: FIX raise error in HDBSCAN with precomputed X and request centers
closes #27893 

Raise a proper `ValueError` when requesting storing center and `metric="precomputed"`.

Problem statement:
sklearn.cluster.HDBSCAN shape error when making medoids with precomputed metric
### Describe the bug

When fitting with HDBSCAN with metric="precomputed" and store_centers='medoid', it would raise the ValueError
`ValueError: Precomputed metric requires shape (n_queries, n_indexed). Got (11, 300) for 11 indexed.`
Claiming the shape of input distance matrix not square, but the input is actually square. It would only occur when points are clustered, i.e., if all points are noises, this would not occur. It seems the bug is in function \_weighted_cluster_center, where the input matrix for pairwise_distances is the 'variable' defined as
`data = X[mask]`
with X as input matrix and mask as labels_, though I am not sure how to fix it.

### Steps/Code to Reproduce

```python
import numpy as np
from scipy.spatial import distance_matrix
from sklearn.cluster import HDBSCAN

# Could with more rows to ensure cluster in points to reproduce the error
X = np.random.random((100, 2))
dm = distance_matrix(X, X)
clusterer = HDBSCAN(metric="precomputed", store_centers='medoid')
clusterer.fit(d)
```

### Expected Results

No Error is thrown. Fit finished.

### Actual Results
```pytb
ValueError                                Traceback (most recent call last)
Cell In[65], line 1
----> 1 clusterer.fit(d)

File ~/miniconda3/envs/cz_cadd/lib/python3.8/site-packages/sklearn/cluster/_hdbscan/hdbscan.py:852, in HDBSCAN.fit(self, X, y)
    849     self.probabilities_ = new_probabilities
    851 if self.store_centers:
--> 852     self._weighted_cluster_center(X)
    853 return self

File ~/miniconda3/envs/cz_cadd/lib/python3.8/site-packages/sklearn/cluster/_hdbscan/hdbscan.py:912, in HDBSCAN._weighted_cluster_center(self, X)
    909     self.centroids_[idx] = np.average(data, weights=strength, axis=0)
    910 if make_medoids:
    911     # TODO: Implement weighted argmin PWD backend
--> 912     dist_mat = pairwise_distances(
    913         data, metric=self.metric, **self._metric_params
    914     )
    915     dist_mat = dist_mat * strength
    916     medoid_index = np.argmin(dist_mat.sum(axis=1))

File ~/miniconda3/envs/cz_cadd/lib/python3.8/site-packages/sklearn/metrics/pairwise.py:2158, in pairwise_distances(X, Y, metric, n_jobs, force_all_finite, **kwds)
   2152     raise ValueError(
   2153         "Unknown metric %s. Valid metrics are %s, or 'precomputed', or a callable"
   2154         % (metric, _VALID_METRICS)
   2155     )
   2157 if metric == "precomputed":
-> 2158     X, _ = check_pairwise_arrays(
   2159         X, Y, precomputed=True, force_all_finite=force_all_finite
   2160     )
   2162     whom = (
   2163         "`pairwise_distances`. Precomputed distance "
   2164         " need to have non-negative values."
   2165     )
   2166     check_non_negative(X, whom=whom)

File ~/miniconda3/envs/cz_cadd/lib/python3.8/site-packages/sklearn/metrics/pairwise.py:184, in check_pairwise_arrays(X, Y, precomputed, dtype, accept_sparse, force_all_finite, copy)
    182 if precomputed:
    183     if X.shape[1] != Y.shape[0]:
--> 184         raise ValueError(
    185             "Precomputed metric requires shape "
    186             "(n_queries, n_indexed). Got (%d, %d) "
    187             "for %d indexed." % (X.shape[0], X.shape[1], Y.shape[0])
    188         )
    189 elif X.shape[1] != Y.shape[1]:
    190     raise ValueError(
    191         "Incompatible dimension for X and Y matrices: "
    192         "X.shape[1] == %d while Y.shape[1] == %d" % (X.shape[1], Y.shape[1])
    193     )

ValueError: Precomputed metric requires shape (n_queries, n_indexed). Got (64, 100) for 64 indexed.
```



### Versions

```shell
System:
    python: 3.8.15 | packaged by conda-forge | (default, Jan 26 2023, 10:47:49)  [GCC 11.3.0]
executable: /home/bruce/miniconda3/envs/cz_cadd/bin/python3.8
   machine: Linux-4.4.0-19041-Microsoft-x86_64-with-glibc2.10

Python dependencies:
      sklearn: 1.3.2
          pip: 22.3.1
   setuptools: 68.2.2
        numpy: 1.23.5
        scipy: 1.9.3
       Cython: None
       pandas: 2.0.3
   matplotlib: 3.7.3
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 20
         prefix: libopenblas
       filepath: /home/bruce/miniconda3/envs/cz_cadd/lib/libopenblasp-r0.3.25.so
        version: 0.3.25
threading_layer: pthreads
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 20
         prefix: libgomp
       filepath: /home/bruce/miniconda3/envs/cz_cadd/lib/libgomp.so.1.0.0
        version: None
```

Hints from issue discussion:
Reading just the documentation of the private functions, it seems that `_weighted_cluster_center` expect to get the raw data and not the precomputed array. Therefore, we should raise an error much earlier that you cannot store the centroids and medoids in combination with `metric="precomputed"`.

Commit message: update changelog

Patch to review:
diff --git a/doc/whats_new/v1.4.rst b/doc/whats_new/v1.4.rst
index 204cbb9e9c890..51d16ec284193 100644
--- a/doc/whats_new/v1.4.rst
+++ b/doc/whats_new/v1.4.rst
@@ -259,6 +259,10 @@ Changelog
   value instead.
   :pr:`27828` by :user:`Guillaume Lemaitre <glemaitre>`.
 
+- |Fix| Raises a proper `ValueError` when `metric="precomputed"` and requested storing
+  centers via the parameter `store_centers`.
+  :pr:`27898` by :user:`Guillaume Lemaitre <glemaitre>`.
+
 :mod:`sklearn.compose`
 ......................
 
diff --git a/sklearn/cluster/_hdbscan/hdbscan.py b/sklearn/cluster/_hdbscan/hdbscan.py
index 161c64dbab053..da042c67218c0 100644
--- a/sklearn/cluster/_hdbscan/hdbscan.py
+++ b/sklearn/cluster/_hdbscan/hdbscan.py
@@ -699,6 +699,11 @@ def fit(self, X, y=None):
             Returns self.
         """
         self._validate_params()
+        if self.metric == "precomputed" and self.store_centers is not None:
+            raise ValueError(
+                "Cannot store centers when using a precomputed distance matrix."
+            )
+
         self._metric_params = self.metric_params or {}
         if self.metric != "precomputed":
             # Non-precomputed matrices may contain non-finite values.
diff --git a/sklearn/cluster/tests/test_hdbscan.py b/sklearn/cluster/tests/test_hdbscan.py
index beb2bb2b3e753..8fd43e7014cb2 100644
--- a/sklearn/cluster/tests/test_hdbscan.py
+++ b/sklearn/cluster/tests/test_hdbscan.py
@@ -546,3 +546,19 @@ def test_hdbscan_warning_on_deprecated_algorithm_name():
     )
     with pytest.warns(FutureWarning, match=msg):
         HDBSCAN(algorithm="balltree").fit(X)
+
+
+@pytest.mark.parametrize("store_centers", ["centroid", "medoid"])
+def test_hdbscan_error_precomputed_and_store_centers(store_centers):
+    """Check that we raise an error if the centers are requested together with
+    a precomputed input matrix.
+
+    Non-regression test for:
+    https://github.com/scikit-learn/scikit-learn/issues/27893
+    """
+    rng = np.random.RandomState(0)
+    X = rng.random((100, 2))
+    X_dist = euclidean_distances(X)
+    err_msg = "Cannot store centers when using a precomputed distance matrix."
+    with pytest.raises(ValueError, match=err_msg):
+        HDBSCAN(metric="precomputed", store_centers=store_centers).fit(X_dist)


Code review comments:
diff_hunk: @@ -699,6 +699,11 @@ def fit(self, X, y=None):
             Returns self.
         """
         self._validate_params()
path: sklearn/cluster/_hdbscan/hdbscan.py
text: @user2:
can you replace this by a
```
    @user1(
        # HDBSCAN.metric is not validated yet
        prefer_skip_nested_validation=False
    )
```
context ?