Repository: scikit-learn/scikit-learn
Pull request: FIX Supports numpy strings and array-like in KMean.init
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/main/CONTRIBUTING.md
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Fixes https://github.com/scikit-learn/scikit-learn/issues/21964

#### What does this implement/fix? Explain your changes.
This PR allows `KMean.init` to support numpy scalar strings and fixes support for `array-likes`.

#### Any other comments?
When we say "array-like", I think we always mean an object that can be `asarray` into a ndarray that is 1d or more. With that in mind, I think `_is_arraylike` should also reject scalars, like `_is_arraylike_not_scalar` in this PR.

Currently, when we use `_is_arraylike` we also have to filter out the scalar case:

https://github.com/scikit-learn/scikit-learn/blob/49588ff1e677d3d6fddf8798603a06f06fdb6e61/sklearn/neighbors/_classification.py#L523-L525

<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
Improper behavior when dealing with numpy.str_
### Describe the bug

For the argument in an algorithm that could accept both a string or a numpy.ndarray. It seems like if you pass the numpy.str_ as the argument type for a string input, it will parse it as a numpy.ndarray, as a result, a ValueError will be raised. I wonder if it is the behavior wanted. 

A sample algorithm could be K-Means clustering, while *init* argument could accept both a string or a numpy.ndarray.

Under the file `sklearn/cluster/_kmean.py` file, the way to check if *init* argument being numpy.ndarray is `hasattr(self.init, "__array__")`. Unfortunately, in numpy, even the string type, numpy.str_, has attribute **__array__**, therefore, treating the numpy.str_ as a numpy.ndarray input, causing the (maybe unwanted) result.

### Steps/Code to Reproduce

```python
import numpy as np

from sklearn.cluster import KMeans

X = np.random.rand(1000, 3)

init_methods = np.array(['k-means++', 'random'])
for init_method in init_methods:
    clustering = KMeans(init=init_method).fit(X)
```


### Expected Results

When passing the string as a python built-in string type, everything looks fine.

```python
import numpy as np

from sklearn.cluster import KMeans

X = np.random.rand(1000, 3)
clustering = KMeans(init='k-means++').fit(X)
```

### Actual Results

```
Traceback (most recent call last):
  File "/***/test4.py", line 10, in <module>
    clustering = KMeans(init=init_method).fit(X)
  File "/***/miniconda3/envs/*/lib/python3.8/site-packages/sklearn/cluster/_kmeans.py", line 991, in fit
    init = check_array(init, dtype=X.dtype, copy=True, order='C')
  File "/***/miniconda3/envs/*/lib/python3.8/site-packages/sklearn/utils/validation.py", line 63, in inner_f
    return f(*args, **kwargs)
  File "/***/miniconda3/envs/*/lib/python3.8/site-packages/sklearn/utils/validation.py", line 673, in check_array
    array = np.asarray(array, order=order, dtype=dtype)
  File "/***/miniconda3/envs/*/lib/python3.8/site-packages/numpy/core/_asarray.py", line 83, in asarray
    return array(a, dtype, copy=False, order=order)
ValueError: could not convert string to float: 'k-means++'
```

### Versions

System:
    python: 3.8.12 | packaged by conda-forge | (default, Oct 12 2021, 21:50:38)  [Clang 11.1.0 ]
executable: /Users/kyle/miniconda3/envs/ml/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
          pip: 21.1.3
   setuptools: 52.0.0.post20210125
      sklearn: 0.24.2
        numpy: 1.19.5
        scipy: 1.6.2
       Cython: None
       pandas: 1.2.5
   matplotlib: 3.3.4
       joblib: 1.0.1
threadpoolctl: 2.2.0

Built with OpenMP: True

Hints from issue discussion:
`init_methods[0]` is a `numpy.str_` and surprisingly (to me at least) `hasattr(init_methods[0], "__array__")` gives `True`. Thus, the code assumes an input type differently.

I suggest using `KMeans(init = str(init_method)).fit(X)`


Yes, I'm also surprised when I find out this situation, I guess that numpy may just treat every object inside as an array in a quite abstract way.
Currently, I am doing the casting operation as you have mentioned, `str(x)`.

Out of curiosity, would you consider to fix this situation in an alternative way, such as `isinstance(init, np.ndarray)`. Obviously, a scalar or a string will not be a np.ndarray type i guess. And honestly, i think, this kind of tiny while surprising situation could be really hard to find when facing an error, just in case, some other unlucky guy faces the same error in future. 
Thank you for raising this! Almost all numpy base classes inherit from `np.generic` which has an `__array__` attribute ([reference](https://numpy.org/doc/stable/reference/arrays.scalars.html?highlight=numpy%20generic#numpy.generic)). Hence  `hasattr(self.init, "__array__")` seems not a valid check for a numpy array.  @ogrisel For improved input validation, should all occurrences of `hasattr(, "__array__")` replaced by `isinstance(, np.ndarray)` as suggested by @Kr4t0n ?
According to the docstring, when `self.init` is passed as an array-like datastructure, it is expected to be an array with pre-initialized centroid locations, not an initialization method name.

If we use `isinstance(self.init, np.ndarray)` we will break existing code that pass array-like datastructures that can be converted to (numeric) numpy arrays with `np.asarray(self.init)` by calling the `__array__` function internally (e.g. pandas dataframes, cupy arrays, ...).

We could instead detect the case where `hasattr(init, "ndim") and init.ndim == 0  and init.dtype.kind == "U"` when the init method name is passed as a 0-dim (also known as "scalar") string numpy array as is the case in the provided reproducer snippet and covert it to a string explicitly in this specific case. But honestly, it's just weird to expect that users will use 0-dim string numpy arrays (with shape `()`) instead of regular `str` objects in their code. Those users will experience all kinds of weird errors with code that expects `str` values.

Alternatively we could check that if `hasattr(self.init, 'ndim' and init.ndim !=2)` we raise a `ValueError` telling the user to either pass a 2-array of initialized centroids or an Python `str`  with the init method name.
@ogrisel Thank you for clarifying the situation, especially about the commonality of the ``__array__`` attribute in pandas and numpy. An additional input validation might not be well enough justified then.

One point to address could be replacing `ndarray` with `array-like` which could create more clarity.
https://github.com/scikit-learn/scikit-learn/blob/0d378913be6d7e485b792ea36e9268be31ed52d0/sklearn/cluster/_kmeans.py#L976-L984

Commit message: DOC Adds whats new nubmer

Patch to review:
diff --git a/doc/whats_new/v1.1.rst b/doc/whats_new/v1.1.rst
index 61d5c64255f71..ebbb17ab4da29 100644
--- a/doc/whats_new/v1.1.rst
+++ b/doc/whats_new/v1.1.rst
@@ -95,6 +95,9 @@ Changelog
   See :func:`cluster.spectral_clustering` for more details.
   :pr:`21148` by :user:`Andrew Knyazev <lobpcg>`
 
+- |Fix| :class:`cluster.KMeans`'s `init` parameter now properly supports
+  array-like input and NumPy string scalars. :pr:`22154` by `Thomas Fan`_.
+
 - |Efficiency| In :class:`cluster.KMeans`, the default ``algorithm`` is now
   ``"lloyd"`` which is the full classical EM-style algorithm. Both ``"auto"``
   and ``"full"`` are deprecated and will be removed in version 1.3. They are
diff --git a/sklearn/cluster/_kmeans.py b/sklearn/cluster/_kmeans.py
index 3112343e05f5f..853f86958e0c9 100644
--- a/sklearn/cluster/_kmeans.py
+++ b/sklearn/cluster/_kmeans.py
@@ -28,6 +28,7 @@
 from ..utils import check_random_state
 from ..utils import deprecated
 from ..utils.validation import check_is_fitted, _check_sample_weight
+from ..utils.validation import _is_arraylike
 from ..utils._openmp_helpers import _openmp_effective_n_threads
 from ..utils._readonly_array_wrapper import ReadonlyArrayWrapper
 from ..exceptions import ConvergenceWarning
@@ -254,6 +255,11 @@ def _tolerance(X, tol):
     return np.mean(variances) * tol
 
 
+def _is_arraylike_not_scalar(array):
+    """Return True if array is array-like and not a scalar"""
+    return _is_arraylike(array) and not np.isscalar(array)
+
+
 def k_means(
     X,
     n_clusters,
@@ -987,16 +993,16 @@ def _check_params(self, X):
 
         # init
         if not (
-            hasattr(self.init, "__array__")
+            _is_arraylike_not_scalar(self.init)
             or callable(self.init)
             or (isinstance(self.init, str) and self.init in ["k-means++", "random"])
         ):
             raise ValueError(
-                "init should be either 'k-means++', 'random', a ndarray or a "
+                "init should be either 'k-means++', 'random', an array-like or a "
                 f"callable, got '{self.init}' instead."
             )
 
-        if hasattr(self.init, "__array__") and self._n_init != 1:
+        if _is_arraylike_not_scalar(self.init) and self._n_init != 1:
             warnings.warn(
                 "Explicit initial center position passed: performing only"
                 f" one init in {self.__class__.__name__} instead of "
@@ -1112,7 +1118,7 @@ def _init_centroids(self, X, x_squared_norms, init, random_state, init_size=None
         elif isinstance(init, str) and init == "random":
             seeds = random_state.permutation(n_samples)[:n_clusters]
             centers = X[seeds]
-        elif hasattr(init, "__array__"):
+        elif _is_arraylike_not_scalar(self.init):
             centers = init
         elif callable(init):
             centers = init(X, n_clusters, random_state=random_state)
@@ -1166,7 +1172,8 @@ def fit(self, X, y=None, sample_weight=None):
 
         # Validate init array
         init = self.init
-        if hasattr(init, "__array__"):
+        init_is_array_like = _is_arraylike_not_scalar(init)
+        if init_is_array_like:
             init = check_array(init, dtype=X.dtype, copy=True, order="C")
             self._validate_center_shape(X, init)
 
@@ -1176,7 +1183,7 @@ def fit(self, X, y=None, sample_weight=None):
             # The copy was already done above
             X -= X_mean
 
-            if hasattr(init, "__array__"):
+            if init_is_array_like:
                 init -= X_mean
 
         # precompute squared norms of data points
@@ -1923,7 +1930,7 @@ def fit(self, X, y=None, sample_weight=None):
 
         # Validate init array
         init = self.init
-        if hasattr(init, "__array__"):
+        if _is_arraylike_not_scalar(init):
             init = check_array(init, dtype=X.dtype, copy=True, order="C")
             self._validate_center_shape(X, init)
 
@@ -2088,7 +2095,7 @@ def partial_fit(self, X, y=None, sample_weight=None):
 
             # Validate init array
             init = self.init
-            if hasattr(init, "__array__"):
+            if _is_arraylike_not_scalar(init):
                 init = check_array(init, dtype=X.dtype, copy=True, order="C")
                 self._validate_center_shape(X, init)
 
diff --git a/sklearn/cluster/tests/test_k_means.py b/sklearn/cluster/tests/test_k_means.py
index 6e395778418c8..93f20c641e3b6 100644
--- a/sklearn/cluster/tests/test_k_means.py
+++ b/sklearn/cluster/tests/test_k_means.py
@@ -1088,7 +1088,7 @@ def test_sample_weight_unchanged(Estimator):
         (
             {"init": "wrong"},
             r"init should be either 'k-means\+\+', 'random', "
-            r"a ndarray or a callable",
+            r"an array-like or a callable",
         ),
     ],
 )
@@ -1205,3 +1205,18 @@ def test_is_same_clustering():
     # mapped to a same value
     labels3 = np.array([1, 0, 0, 2, 2, 0, 2, 1], dtype=np.int32)
     assert not _is_same_clustering(labels1, labels3, 3)
+
+
+@pytest.mark.parametrize(
+    "kwargs", ({"init": np.str_("k-means++")}, {"init": [[0, 0], [1, 1]], "n_init": 1})
+)
+def test_kmeans_with_array_like_or_np_scalar_init(kwargs):
+    """Check that init works with numpy scalar strings.
+
+    Non-regression test for #21964.
+    """
+    X = np.asarray([[0, 0], [0.5, 0], [0.5, 1], [1, 1]], dtype=np.float64)
+
+    clustering = KMeans(n_clusters=2, **kwargs)
+    # Does not raise
+    clustering.fit(X)


Code review comments:
diff_hunk: @@ -254,6 +255,11 @@ def _tolerance(X, tol):
     return np.mean(variances) * tol
 
 
+def _is_arraylike_not_scalar(array):
+    """Return True if array is array-like and not a scalar"""
+    return _is_arraylike(array) and not np.isscalar(array)
path: sklearn/cluster/_kmeans.py
text: @user1:
maybe directly put this in utils.validation. It might be useful elsewhere at some point.