Repository: scikit-learn/scikit-learn
Pull request: FIX `KNeighborsClassifier` raise when all neighbors of some sample have zero weights
#### Reference Issues/PRs

Fixes #25854.

#### What does this implement/fix? Explain your changes.

Raises a `ValueError` when the weights for all neighbors of some sample are zero. Previous behavior: `predict` predicts the first class, `predict_proba` returns all zero probability.

Problem statement:
`KNeighborsClassifier` with Default Label
### Describe the workflow you want to enable

In `KNeighborsClassifier`, for a user-provided callable `weights` parameter, it would be nice to allow for a situation with no winner. Say I want to give a weight of `0.0` to samples that are "too far away". Then, there can be a situation in which *all* neighbors get  a weight of `0.0`.

Currently:
- `predict_proba` would return a row of `0.0`, which is inconsistent, since it doesn't add up to `1.0`.
- `predict` would arbitrarily predict the first element of `classes_`, which is undesirable.

This is similar to the situation in `RadiusNeighborsClassifier`, when no samples are within the query radius. In `RadiusNeighborsClassifier` it is addressed by the `outlier_label` parameter, but in `KNeighborsClassifier` no such mechanism exists.

### Describe your proposed solution

Add a `default_label` parameter to `KNeighborsClassifier`, which would be the prediction in case all other classes get zero probability. Similarly to `outlier_label` in `RadiusNeighborsClassifier`, we can also support a `'most_frequent'` option and raise an exception when a label is not provided.

The basic logic could be implemented by making the following additions:
1. Add `default_label` to the possible `clsses_` by adding to `fit` (after `classes_` has been determined):
```python
if self.default_label is not None:
    if self.outputs_2d_:
        self.classes_ = [np.hstack((c, self.default_label)) for c in self.classes_ if self.default_label not in c]
    elif self.default_label not in self.classes_:
        self.classes_ = np.hstack((self.classes_, self.default_label))
```
2. Add to `predict_proba` (after `probas` has been determined):
```python
if self.default_label is not None:
    if self.outputs_2d_:
        for p, c in zip(probas, self.classes_):
            p[np.all(p == 0, axis=1), c == self.default_label] = 1.0
    else:
        probas[np.all(probas == 0, axis=1), self.classes_ == self.default_label] = 1.0
```
3. Add to `predict` a correction of the `mode`:
```python
for k, classes_k in enumerate(classes_):
    if weights is None:
        mode, _ = _mode(_y[neigh_ind, k], axis=1)
    else:
        mode, _ = weighted_mode(_y[neigh_ind, k], weights, axis=1)
        # Add the following two lines:
        if self.default_label is not None:
            mode[np.all(weights == 0, axis=1), 0] = np.where(classes_k == self.default_label)[0][0]

    mode = np.asarray(mode.ravel(), dtype=np.intp)
    y_pred[:, k] = classes_k.take(mode)
```


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

_No response_

### Additional context

_No response_

Hints from issue discussion:
I agree that the current behavior is problematic. But adding a new public parameter for such an edge case sounds too much.

So my suggestion would be to:
- do a PR to raise an informative error when this case happens (am not sure about the type of exception though) so that they can change there `weights` callable to avoid triggering this case in the first place;
- concurrently, to implement your specific logic, you can subclass scikit-learn `KNeighborsClassifier`'s `predict` and `predict_proba` to do what you want with limited extra maintenance on your side.

Commit message: add any_zero_row to api (is this necessary?)

Patch to review:
diff --git a/doc/developers/utilities.rst b/doc/developers/utilities.rst
index 2525b2b1365ed..f5f2bf048328a 100644
--- a/doc/developers/utilities.rst
+++ b/doc/developers/utilities.rst
@@ -104,6 +104,9 @@ Efficient Linear Algebra & Array Operations
 - :func:`arrayfuncs.min_pos`: (used in ``sklearn.linear_model.least_angle``)
   Find the minimum of the positive values within an array.
 
+- :func:`arrayfuncs.any_zero_row`:
+  (used in :class:`~sklearn.neighbors.KNeighborsClassifier`) Check if any row
+  of a two-dimensional array-like is all zeros.
 
 - :func:`extmath.fast_logdet`: efficiently compute the log of the determinant
   of a matrix.
diff --git a/doc/modules/classes.rst b/doc/modules/classes.rst
index 55336389f93d5..f9c36b681b569 100644
--- a/doc/modules/classes.rst
+++ b/doc/modules/classes.rst
@@ -1817,6 +1817,7 @@ Utilities to operate on arrays
    :toctree: generated/
    :template: function.rst
 
+   utils.arrayfuncs.any_zero_row
    utils.arrayfuncs.min_pos
 
 Metadata routing
diff --git a/doc/whats_new/v1.4.rst b/doc/whats_new/v1.4.rst
index adb362d2802d5..d8bc1eb83a61c 100644
--- a/doc/whats_new/v1.4.rst
+++ b/doc/whats_new/v1.4.rst
@@ -637,6 +637,12 @@ Changelog
   :class:`metrics.DistanceMetric` objects.
   :pr:`26267` by :user:`Meekail Zain <micky774>`.
 
+- |Fix| :meth:`neighbors.KNeighborsClassifier.predict` and
+  :meth:`neighbors.KNeighborsClassifier.predict_proba` now raises an error when the
+  weights of all neighbors of some sample are zero. This can happen when `weights`
+  is a user-defined function.
+  :pr:`26410` by :user:`Yao Xiao <Charlie-XIAO>`
+
 :mod:`sklearn.preprocessing`
 ............................
 
diff --git a/sklearn/neighbors/_classification.py b/sklearn/neighbors/_classification.py
index e921ec3a9d165..31c2b92975a99 100644
--- a/sklearn/neighbors/_classification.py
+++ b/sklearn/neighbors/_classification.py
@@ -20,9 +20,10 @@
     RadiusNeighborsClassMode,
 )
 from ..utils._param_validation import StrOptions
+from ..utils.arrayfuncs import any_zero_row
 from ..utils.extmath import weighted_mode
 from ..utils.fixes import _mode
-from ..utils.validation import _is_arraylike, _num_samples, check_is_fitted
+from ..utils.validation import _is_arraylike, _num_samples, check_array, check_is_fitted
 from ._base import KNeighborsMixin, NeighborsBase, RadiusNeighborsMixin, _get_weights
 
 
@@ -281,6 +282,14 @@ def predict(self, X):
         n_outputs = len(classes_)
         n_queries = _num_samples(X)
         weights = _get_weights(neigh_dist, self.weights)
+        if weights is not None:
+            weights = check_array(weights, dtype=[np.float32, np.float64])
+            if any_zero_row(weights):
+                raise ValueError(
+                    "All neighbors of some sample is getting zero weights. "
+                    "Please modify 'weights' to avoid this case if you are "
+                    "using a user-defined function."
+                )
 
         y_pred = np.empty((n_queries, n_outputs), dtype=classes_[0].dtype)
         for k, classes_k in enumerate(classes_):
@@ -372,6 +381,14 @@ def predict_proba(self, X):
         weights = _get_weights(neigh_dist, self.weights)
         if weights is None:
             weights = np.ones_like(neigh_ind)
+        else:
+            weights = check_array(weights, dtype=[np.float32, np.float64])
+            if any_zero_row(weights):
+                raise ValueError(
+                    "All neighbors of some sample is getting zero weights. "
+                    "Please modify 'weights' to avoid this case if you are "
+                    "using a user-defined function."
+                )
 
         all_rows = np.arange(n_queries)
         probabilities = []
@@ -385,7 +402,6 @@ def predict_proba(self, X):
 
             # normalize 'votes' into real [0,1] probabilities
             normalizer = proba_k.sum(axis=1)[:, np.newaxis]
-            normalizer[normalizer == 0.0] = 1.0
             proba_k /= normalizer
 
             probabilities.append(proba_k)
diff --git a/sklearn/neighbors/tests/test_neighbors.py b/sklearn/neighbors/tests/test_neighbors.py
index 00c53734c9576..05053f4eb2e5c 100644
--- a/sklearn/neighbors/tests/test_neighbors.py
+++ b/sklearn/neighbors/tests/test_neighbors.py
@@ -2343,3 +2343,30 @@ def test_nearest_neighbours_works_with_p_less_than_1():
 
     y = neigh.kneighbors(X[0].reshape(1, -1), return_distance=False)
     assert_allclose(y[0], [0, 1, 2])
+
+
+def test_KNeighborsClassifier_raise_on_all_zero_weights():
+    """Check that `predict` and `predict_proba` raises on sample of all zeros weights.
+
+    Related to Issue #25854.
+    """
+    X = [[0, 1], [1, 2], [2, 3], [3, 4]]
+    y = [0, 0, 1, 1]
+
+    def _weights(dist):
+        return np.vectorize(lambda x: 0 if x > 0.5 else 1)(dist)
+
+    est = neighbors.KNeighborsClassifier(n_neighbors=3, weights=_weights)
+    est.fit(X, y)
+
+    msg = (
+        "All neighbors of some sample is getting zero weights. "
+        "Please modify 'weights' to avoid this case if you are "
+        "using a user-defined function."
+    )
+
+    with pytest.raises(ValueError, match=msg):
+        est.predict([[1.1, 1.1]])
+
+    with pytest.raises(ValueError, match=msg):
+        est.predict_proba([[1.1, 1.1]])
diff --git a/sklearn/utils/arrayfuncs.pyx b/sklearn/utils/arrayfuncs.pyx
index d060c7bada92a..8af644288c78b 100644
--- a/sklearn/utils/arrayfuncs.pyx
+++ b/sklearn/utils/arrayfuncs.pyx
@@ -11,7 +11,7 @@ from ._cython_blas cimport _copy, _rotg, _rot
 
 
 def min_pos(const floating[:] X):
-    """Find the minimum value of an array over positive values
+    """Find the minimum value of an array over positive values.
 
     Returns the maximum representable value of the input dtype if none of the
     values are positive.
@@ -24,6 +24,25 @@ def min_pos(const floating[:] X):
     return min_val
 
 
+def any_zero_row(floating[:, :] X):
+    """Check if any row of a 2D array is all zeros.
+
+    Returns True if any row of `X` is all zeros, and False otherwise.
+    """
+    cdef:
+        Py_ssize_t i, j
+        floating val
+
+    for i in range(X.shape[0]):
+        for j in range(X.shape[1]):
+            val = X[i, j]
+            if val != 0.:
+                break
+        else:
+            return True
+    return False
+
+
 # General Cholesky Delete.
 # Remove an element from the cholesky factorization
 # m = columns
diff --git a/sklearn/utils/tests/test_arrayfuncs.py b/sklearn/utils/tests/test_arrayfuncs.py
index b0a02e13d1639..ff45d9e3af602 100644
--- a/sklearn/utils/tests/test_arrayfuncs.py
+++ b/sklearn/utils/tests/test_arrayfuncs.py
@@ -2,7 +2,7 @@
 import pytest
 
 from sklearn.utils._testing import assert_allclose
-from sklearn.utils.arrayfuncs import min_pos
+from sklearn.utils.arrayfuncs import any_zero_row, min_pos
 
 
 def test_min_pos():
@@ -24,3 +24,16 @@ def test_min_pos_no_positive(dtype):
     X = np.full(100, -1.0).astype(dtype, copy=False)
 
     assert min_pos(X) == np.finfo(dtype).max
+
+
+@pytest.mark.parametrize("dtype", [np.float32, np.float64])
+def test_any_zero_row(dtype):
+    # Check that any_zero_row returns True when a row contains a zero
+    # and False otherwise
+
+    X = np.array([[1, 2, 3], [0, 1, 2]], dtype=dtype)
+    assert not any_zero_row(X)
+
+    # Make a zero row and check return True
+    X[0, :] = 0
+    assert any_zero_row(X)


Code review comments:
diff_hunk: @@ -24,6 +24,25 @@ def min_pos(const floating[:] X):
     return min_val
 
 
+def any_zero_row(floating[:, :] X):
path: sklearn/utils/arrayfuncs.pyx
text: @user1:
I would make this function private for the moment. I think that we can make the function slightly more generatic and looking like NumPy:

```python
ctypedef fused real_numeric:
    short
    int
    long
    float
    double


def _all_with_any_reduction(real_numeric[:, :] array, real_numeric value=0, int axis=0):
    """Check all values are equal to `value` along a specific axis.

    It is equivalent to `np.any(np.all(X == value, axis=axis))` but it avoids to
    materialize the temporary boolean matrices in memory.

    Parameters
    ----------
    array : array-like
        The array to be checked.
    value : short, int, long, float, double
        The value to use for the comparison.
    axis : int, default=0
        Along which axis to perform the `all` operation.

    Returns
    -------
    bool
        Whether or not any rows (i.e. `axis=1`) or any columns (i.e. `axis=0`) contains
        all values equal to `value`.
    """
    cdef:
        Py_ssize_t i, j

    if axis == 0:
        for j in range(X.shape[1]):
            for i in range(X.shape[0]):
                if X[i, j] != value:
                    break
            else:
                return True
        return False
    else:  # axis == 1:
        for i in range(X.shape[0]):
            for j in range(X.shape[1]):
                if X[i, j] != value:
                    break
            else:
                return True
        return False
```

diff_hunk: @@ -281,6 +282,14 @@ def predict(self, X):
         n_outputs = len(classes_)
         n_queries = _num_samples(X)
         weights = _get_weights(neigh_dist, self.weights)
+        if weights is not None:
+            weights = check_array(weights, dtype=[np.float32, np.float64])
path: sklearn/neighbors/_classification.py
text: @user1:
I am wondering if can just keep `dtype="numeric"` by making the Cython function more flexible.
I assume that this can happen with `weights` is passed as a callable.