Repository: scikit-learn/scikit-learn
Pull request: FIX sort radius neighbors results when sort_results=True and algorithm="brute"
Fixes #18583.

Calling `radius_neighbors` method of `NearestNeighbors` was not sorting the result by distance when `sort_results=True`, when fitted with `algorithm="brute"`.
This PR fixes this issue, and clarifies the docstring.

Problem statement:
radius_neighbors method of NearestNeighbors doesn't sort by distance when sort_results=True
#### Bug description
Calling radius_neighbors method of NearestNeighbors doesn't sort indices and distances by distance when sort_results=True is set. It appears to be sorting both by indices values instead, which doesn't seem intuitive. The documentation of the sort_results argument of that method states `If True, the distances and indices will be sorted before being returned. `, which isn't entirely clear.

#### Steps/Code to Reproduce
```python
from sklearn.neighbors import NearestNeighbors
import numpy as np
array_train = np.array([
    [0.2, 9.3, 0.5, 8.0, 2.0],
    [1.0, 4.2, 4.0, 2.5, 0.0],
    [0.0, 1.6, 8.0, 3.0, 0.2],
    [3.0, 5.6, 6.0, 6.7, 8.0],
    [4.2, 1.0, 1.0, 0.3, 6.3]
])
model_knn = NearestNeighbors(metric='cosine')
model_knn.fit(array_train)
distances, indices = model_knn.radius_neighbors(
    X=array_train, radius=0.8, sort_results=True
)
```

returns

`distances`
```python
array([
   array([0.        , 0.22996402, 0.59989965, 0.26014738, 0.73264133]),
   array([0.22996402, 0.        , 0.16869482, 0.22708139, 0.73322147]),
   array([0.59989965, 0.16869482, 0.        , 0.33531797]),
   array([0.26014738, 0.22708139, 0.33531797, 0.        , 0.26980302]),
   array([0.73264133, 0.73322147, 0.26980302, 0.        ])
], dtype=object)
```

`indices`
```python
array([
    array([0, 1, 2, 3, 4]),
    array([0, 1, 2, 3, 4]),
    array([0, 1, 2, 3]),
    array([0, 1, 2, 3, 4]),
    array([0, 1, 3, 4])
], dtype=object)
```

#### Versions
```
System:
    python: 3.7.6 (default, Feb 12 2020, 17:58:16)  [Clang 11.0.0 (clang-1100.0.33.17)]
executable: /src/agg-recs/venv3/bin/python3
   machine: Darwin-19.6.0-x86_64-i386-64bit

Python dependencies:
       pip: 20.2.1
setuptools: 49.2.1
   sklearn: 0.22.2
     numpy: 1.19.1
     scipy: 1.5.2
    Cython: None
    pandas: 1.0.3
matplotlib: 3.3.0
    joblib: 0.16.0

Built with OpenMP: True
```

Hints from issue discussion:
Looks like two changes are needed here, first for the docstring to specify sorting by distance, and second for the sorting logic to go by results instead of indices, yes?

Commit message: FIX PR number

Patch to review:
diff --git a/doc/whats_new/v0.24.rst b/doc/whats_new/v0.24.rst
index edd3afe62dbdf..652fa97ad4479 100644
--- a/doc/whats_new/v0.24.rst
+++ b/doc/whats_new/v0.24.rst
@@ -536,6 +536,10 @@ Changelog
   will raise a `ValueError` when fitting on data with all constant features.
   :pr:`18370` by :user:`Trevor Waite <trewaite>`.
 
+- |Fix| Using `sort_results=True` now correctly sorts the results in methods
+  `radius_neighbors` and `radius_neighbors_graph`, even when using the "brute"
+  algorithm. :pr:`18612` by `Tom Dupre la Tour`_.
+
 :mod:`sklearn.neural_network`
 .............................
 
diff --git a/sklearn/neighbors/_base.py b/sklearn/neighbors/_base.py
index e7beea0083a92..fa7702555a39a 100644
--- a/sklearn/neighbors/_base.py
+++ b/sklearn/neighbors/_base.py
@@ -925,10 +925,10 @@ def radius_neighbors(self, X=None, radius=None, return_distance=True,
             Whether or not to return the distances.
 
         sort_results : bool, default=False
-            If True, the distances and indices will be sorted before being
-            returned. If `False`, the results will not be sorted. If
-            `return_distance=False`, setting `sort_results=True` will
-            result in an error.
+            If True, the distances and indices will be sorted by increasing
+            distances before being returned. If False, the results may not
+            be sorted. If `return_distance=False`, setting `sort_results=True`
+            will result in an error.
 
             .. versionadded:: 0.22
 
@@ -1021,6 +1021,16 @@ class from an array representing our data set and ask who's
                 neigh_ind_list = sum(chunked_results, [])
                 results = _to_object_array(neigh_ind_list)
 
+            if sort_results:
+                if not return_distance:
+                    raise ValueError("return_distance must be True "
+                                     "if sort_results is True.")
+                for ii in range(len(neigh_dist)):
+                    order = np.argsort(neigh_dist[ii], kind='mergesort')
+                    neigh_ind[ii] = neigh_ind[ii][order]
+                    neigh_dist[ii] = neigh_dist[ii][order]
+                results = neigh_dist, neigh_ind
+
         elif self._fit_method in ['ball_tree', 'kd_tree']:
             if issparse(X):
                 raise ValueError(
@@ -1097,9 +1107,9 @@ def radius_neighbors_graph(self, X=None, radius=None, mode='connectivity',
             edges are Euclidean distance between points.
 
         sort_results : bool, default=False
-            If True, the distances and indices will be sorted before being
-            returned. If False, the results will not be sorted.
-            Only used with mode='distance'.
+            If True, in each row of the result, the non-zero entries will be
+            sorted by increasing distances. If False, the non-zero entries may
+            not be sorted. Only used with mode='distance'.
 
             .. versionadded:: 0.22
 
diff --git a/sklearn/neighbors/tests/test_neighbors.py b/sklearn/neighbors/tests/test_neighbors.py
index 9784aa60d70f1..eceb37d6c0e86 100644
--- a/sklearn/neighbors/tests/test_neighbors.py
+++ b/sklearn/neighbors/tests/test_neighbors.py
@@ -678,6 +678,38 @@ def test_radius_neighbors_returns_array_of_objects():
     assert_array_equal(neigh_ind, expected_ind)
 
 
+@pytest.mark.parametrize(["algorithm", "metric"], [("ball_tree", "euclidean"),
+                                                   ("kd_tree", "euclidean"),
+                                                   ("brute", "euclidean"),
+                                                   ("brute", "precomputed")])
+def test_radius_neighbors_sort_results(algorithm, metric):
+    n_samples = 10
+    rng = np.random.RandomState(42)
+    X = rng.random_sample((n_samples, 4))
+
+    if metric == "precomputed":
+        X = neighbors.radius_neighbors_graph(X, radius=np.inf, mode="distance")
+    model = neighbors.NearestNeighbors(algorithm=algorithm, metric=metric)
+    model.fit(X)
+
+    # self.radius_neighbors
+    distances, indices = model.radius_neighbors(X=X, radius=np.inf,
+                                                sort_results=True)
+    for ii in range(n_samples):
+        assert_array_equal(distances[ii], np.sort(distances[ii]))
+
+    # sort_results=True and return_distance=False
+    if metric != "precomputed":  # no need to raise with precomputed graph
+        with pytest.raises(ValueError, match="return_distance must be True"):
+            _ = model.radius_neighbors(X=X, radius=np.inf, sort_results=True,
+                                       return_distance=False)
+
+    # self.radius_neighbors_graph
+    graph = model.radius_neighbors_graph(X=X, radius=np.inf, mode="distance",
+                                         sort_results=True)
+    _is_sorted_by_data(graph)
+
+
 def test_RadiusNeighborsClassifier_multioutput():
     # Test k-NN classifier on multioutput data
     rng = check_random_state(0)


Code review comments:
diff_hunk: @@ -678,6 +678,38 @@ def test_radius_neighbors_returns_array_of_objects():
     assert_array_equal(neigh_ind, expected_ind)
 
 
+@pytest.mark.parametrize(["algorithm", "metric"], [("ball_tree", "euclidean"),
+                                                   ("kd_tree", "euclidean"),
+                                                   ("brute", "euclidean"),
+                                                   ("brute", "precomputed")])
+def test_radius_neighbors_sort_results(algorithm, metric):
+    n_samples = 10
+    rng = np.random.RandomState(42)
+    X = rng.random_sample((n_samples, 4))
+
+    if metric == "precomputed":
+        X = neighbors.radius_neighbors_graph(X, radius=np.inf, mode="distance")
+    model = neighbors.NearestNeighbors(algorithm=algorithm, metric=metric)
+    model.fit(X)
+
+    # self.radius_neighbors
+    distances, indices = model.radius_neighbors(X=X, radius=np.inf,
+                                                sort_results=True)
+    for ii in range(n_samples):
+        assert_array_equal(distances[ii], np.sort(distances[ii]))
+
+    # sort_results=True and return_distance=False
+    if metric != "precomputed":  # no need to raise with precomputed graph
+        with pytest.raises(ValueError, match="return_distance must be True"):
+            _ = model.radius_neighbors(X=X, radius=np.inf, sort_results=True,
+                                       return_distance=False)
path: sklearn/neighbors/tests/test_neighbors.py
text: @user1:
nit
```suggestion
            model.radius_neighbors(X=X, radius=np.inf, sort_results=True,
                                   return_distance=False)
```

diff_hunk: @@ -678,6 +678,38 @@ def test_radius_neighbors_returns_array_of_objects():
     assert_array_equal(neigh_ind, expected_ind)
 
 
+@pytest.mark.parametrize(["algorithm", "metric"], [("ball_tree", "euclidean"),
+                                                   ("kd_tree", "euclidean"),
+                                                   ("brute", "euclidean"),
+                                                   ("brute", "precomputed")])
+def test_radius_neighbors_sort_results(algorithm, metric):
+    n_samples = 10
+    rng = np.random.RandomState(42)
+    X = rng.random_sample((n_samples, 4))
+
+    if metric == "precomputed":
+        X = neighbors.radius_neighbors_graph(X, radius=np.inf, mode="distance")
+    model = neighbors.NearestNeighbors(algorithm=algorithm, metric=metric)
+    model.fit(X)
+
+    # self.radius_neighbors
+    distances, indices = model.radius_neighbors(X=X, radius=np.inf,
+                                                sort_results=True)
+    for ii in range(n_samples):
+        assert_array_equal(distances[ii], np.sort(distances[ii]))
+
+    # sort_results=True and return_distance=False
+    if metric != "precomputed":  # no need to raise with precomputed graph
+        with pytest.raises(ValueError, match="return_distance must be True"):
+            _ = model.radius_neighbors(X=X, radius=np.inf, sort_results=True,
+                                       return_distance=False)
+
+    # self.radius_neighbors_graph
+    graph = model.radius_neighbors_graph(X=X, radius=np.inf, mode="distance",
+                                         sort_results=True)
+    _is_sorted_by_data(graph)
path: sklearn/neighbors/tests/test_neighbors.py
text: @user1:
should this be

```suggestion
    assert _is_sorted_by_data(graph)
```