Repository: scikit-learn/scikit-learn
Pull request: [MRG] BUG ensure object array are properly casted when dtype=object
closes #16036

Fix a bug where calling `np.array(..., dtype=object)` will create a N-D array while algorithms are expecting a 1-D array with objects inside (similar to a list).

Problem statement:
Using dbscan with precomputed neighbors gives an error in 0.22.X, but not in 0.21.3.
#### Description

Using dbscan with precomputed neighbors gives an error in 0.22.X, but not in 0.21.3. 

I am not sure if this is an intended change or not, but could not see anything on this in the release history. If this is due to a mistake on my part on how to us precomputed neighbors, please tell me, and I will direct my question elsewhere.


#### Steps/Code to Reproduce

```python
import numpy as np
from sklearn.cluster import dbscan
from sklearn.neighbors import radius_neighbors_graph

space = np.ones((4, 3))
neighbors_distances = radius_neighbors_graph(space, radius=2, mode="distance")

core_samples, cluster_labels = dbscan(
    neighbors_distances, min_samples=1, metric="precomputed"
)
print(cluster_labels)
```


The error can also be encountered using a random space, for example:
```python
np.random.seed(3)
space = np.random.random((4, 3))
print(space)
# [[0.5507979  0.70814782 0.29090474]
#  [0.51082761 0.89294695 0.89629309]
#  [0.12558531 0.20724288 0.0514672 ]
#  [0.44080984 0.02987621 0.45683322]]
```

#### Expected Results

Output in 0.21.3:
```
[0 0 0 0]
```

#### Actual Results

Output in 0.22.0 and 0.22.1:
```
Traceback (most recent call last):
  File "test.py", line 29, in <module>
    neighbors_distances, min_samples=1, metric="precomputed"
  File "/home/simen/src/miniconda3/envs/dfs/lib/python3.6/site-packages/sklearn/cluster/_dbscan.py", line 144, in dbscan
    est.fit(X, sample_weight=sample_weight)
  File "/home/simen/src/miniconda3/envs/dfs/lib/python3.6/site-packages/sklearn/cluster/_dbscan.py", line 350, in fit
    dbscan_inner(core_samples, neighborhoods, labels)
  File "sklearn/cluster/_dbscan_inner.pyx", line 19, in sklearn.cluster._dbscan_inner.dbscan_inner
ValueError: Buffer has wrong number of dimensions (expected 1, got 2)
```

#### Versions

Dependencies with 0.21.3:
```
System:
    python: 3.6.8 |Anaconda, Inc.| (default, Dec 30 2018, 01:22:34)  [GCC 7.3.0]
executable: /home/simen/src/miniconda3/envs/dfs/bin/python
   machine: Linux-5.0.0-37-generic-x86_64-with-debian-buster-sid

Python deps:
       pip: 19.1.1
setuptools: 39.1.0
   sklearn: 0.21.3
     numpy: 1.18.0
     scipy: 1.4.1
    Cython: 0.29.2
    pandas: 0.25.3
```

Dependencies with 0.22.0:
```
System:
    python: 3.6.8 |Anaconda, Inc.| (default, Dec 30 2018, 01:22:34)  [GCC 7.3.0]
executable: /home/simen/src/miniconda3/envs/dfs/bin/python
   machine: Linux-5.0.0-37-generic-x86_64-with-debian-buster-sid

Python dependencies:
       pip: 19.1.1
setuptools: 39.1.0
   sklearn: 0.22
     numpy: 1.18.0
     scipy: 1.4.1
    Cython: 0.29.2
    pandas: 0.25.3
matplotlib: 3.1.2
    joblib: 0.14.1

Built with OpenMP: True
```

Hints from issue discussion:
The regression was introduced in https://github.com/scikit-learn/scikit-learn/pull/10482

In 0.21.3, `neighborhoods` was a 1-D numpy array of numpy arrays.
In 0.22, this is a ~~2-D sparse matrix~~ a 2-D numpy array.
I was wrong. The regression was introduced after in: https://github.com/scikit-learn/scikit-learn/pull/15832/files

Basically, `dtype=object` convert the array into a 2D array of dtype object instead of 1D array of dtype object with inside numpy array of dtype int.
We need to create an empty array as commented there:

https://github.com/pandas-dev/pandas/pull/30035/files#r354041213
The fix will be:

```diff
--- a/sklearn/neighbors/_base.py
+++ b/sklearn/neighbors/_base.py
@@ -276,8 +276,12 @@ def _radius_neighbors_from_graph(graph, radius, return_distance):
     indices = indices.astype(np.intp, copy=no_filter_needed)
 
     if return_distance:
-        neigh_dist = np.array(np.split(data, indptr[1:-1]), dtype=object)
-    neigh_ind = np.array(np.split(indices, indptr[1:-1]), dtype=object)
+        distances_ = np.split(data, indptr[1:-1])
+        neigh_dist = np.emtpy(len(distances_), dtype=object)
+        neigh_dist[:] = distances_
+    indices_ = np.split(indices, indptr[1:-1])
+    neigh_ind = np.empty(len(indices_), dtype=object)
+    neigh_ind[:] = indices_
 
     if return_distance:
         return neigh_dist, neigh_ind
```
As a non-regression test, I think that we need to check the output of `NearestNeighbors.radius_neighbors` are numpy array of `dtype=object` and each internal array are numpy array of `dtype=int`.
Hi @glemaitre . I would like to work on this issue. Is it  Ok, or is someone else already on it?
Go ahead. Nobody is on it.
Thanks. I"m on it.
Whoops. Sorry for the incorrect review on #15832. I should have known
better. It would be very helpful to have a regression test.

Commit message: (#16036) refactoring with new function _to_object_array()

Patch to review:
diff --git a/doc/whats_new/v0.23.rst b/doc/whats_new/v0.23.rst
index 53c416c506614..a6e9d62c439e3 100644
--- a/doc/whats_new/v0.23.rst
+++ b/doc/whats_new/v0.23.rst
@@ -118,6 +118,15 @@ Changelog
   when `y=None`.
   :pr: `15918` by :user: `Luca Kubin <lkubin>`.
 
+:mod:`sklearn.neighbors`
+..............................
+
+- |Fix| Fixed bug in function _radius_neighbors_from_graph(), module 
+  neighbours._base.py. The fix ensures _radius_neighbors_from_graph()
+  will always return a numpy.array of objects.
+  :pr:`16076` by :user: `Guillaume Lemaitre <glemaitre>` and  
+  `Alex Shacked <alexshacked>`.
+
 :mod:`sklearn.preprocessing`
 ............................
 
diff --git a/sklearn/neighbors/_base.py b/sklearn/neighbors/_base.py
index 258440d20c836..adc8a48f03f8c 100644
--- a/sklearn/neighbors/_base.py
+++ b/sklearn/neighbors/_base.py
@@ -276,8 +276,8 @@ def _radius_neighbors_from_graph(graph, radius, return_distance):
     indices = indices.astype(np.intp, copy=no_filter_needed)
 
     if return_distance:
-        neigh_dist = np.array(np.split(data, indptr[1:-1]), dtype=object)
-    neigh_ind = np.array(np.split(indices, indptr[1:-1]), dtype=object)
+        neigh_dist = _to_object_array(np.split(data, indptr[1:-1]))
+    neigh_ind = _to_object_array(np.split(indices, indptr[1:-1]))
 
     if return_distance:
         return neigh_dist, neigh_ind
@@ -285,6 +285,12 @@ def _radius_neighbors_from_graph(graph, radius, return_distance):
         return neigh_ind
 
 
+def _to_object_array(sequence):
+    out = np.empty(len(sequence), dtype=object)
+    out[:] = sequence
+    return out
+
+
 class NeighborsBase(MultiOutputMixin, BaseEstimator, metaclass=ABCMeta):
     """Base class for nearest neighbors estimators."""
 
@@ -942,15 +948,12 @@ class from an array representing our data set and ask who's
                 neigh_ind_list = sum(neigh_ind_chunks, [])
                 # See https://github.com/numpy/numpy/issues/5456
                 # to understand why this is initialized this way.
-                neigh_dist = np.empty(len(neigh_dist_list), dtype='object')
-                neigh_dist[:] = neigh_dist_list
-                neigh_ind = np.empty(len(neigh_ind_list), dtype='object')
-                neigh_ind[:] = neigh_ind_list
+                neigh_dist = _to_object_array(neigh_dist_list)
+                neigh_ind = _to_object_array(neigh_ind_list)
                 results = neigh_dist, neigh_ind
             else:
                 neigh_ind_list = sum(chunked_results, [])
-                results = np.empty(len(neigh_ind_list), dtype='object')
-                results[:] = neigh_ind_list
+                results = _to_object_array(neigh_ind_list)
 
         elif self._fit_method in ['ball_tree', 'kd_tree']:
             if issparse(X):
diff --git a/sklearn/neighbors/tests/test_neighbors.py b/sklearn/neighbors/tests/test_neighbors.py
index 03c79086dfedd..88e32669777a1 100644
--- a/sklearn/neighbors/tests/test_neighbors.py
+++ b/sklearn/neighbors/tests/test_neighbors.py
@@ -649,6 +649,30 @@ def test_radius_neighbors_boundary_handling():
         assert_array_equal(results[0], [0, 1])
 
 
+def test_radius_neighbors_returns_array_of_objects():
+    # check that we can pass precomputed distances to
+    # NearestNeighbors.radius_neighbors()
+    # non-regression test for
+    # https://github.com/scikit-learn/scikit-learn/issues/16036
+    X = csr_matrix(np.ones((4, 4)))
+    X.setdiag([0, 0, 0, 0])
+
+    nbrs = neighbors.NearestNeighbors(radius=0.5, algorithm='auto',
+                                      leaf_size=30,
+                                      metric='precomputed').fit(X)
+    neigh_dist, neigh_ind = nbrs.radius_neighbors(X, return_distance=True)
+
+    expected_dist = np.empty(X.shape[0], dtype=object)
+    expected_dist[:] = [np.array([0]), np.array([0]), np.array([0]),
+                        np.array([0])]
+    expected_ind = np.empty(X.shape[0], dtype=object)
+    expected_ind[:] = [np.array([0]), np.array([1]), np.array([2]),
+                       np.array([3])]
+
+    assert_array_equal(neigh_dist, expected_dist)
+    assert_array_equal(neigh_ind, expected_ind)
+
+
 def test_RadiusNeighborsClassifier_multioutput():
     # Test k-NN classifier on multioutput data
     rng = check_random_state(0)


Code review comments:
diff_hunk: @@ -276,15 +276,21 @@ def _radius_neighbors_from_graph(graph, radius, return_distance):
     indices = indices.astype(np.intp, copy=no_filter_needed)
 
     if return_distance:
-        neigh_dist = np.array(np.split(data, indptr[1:-1]), dtype=object)
-    neigh_ind = np.array(np.split(indices, indptr[1:-1]), dtype=object)
+        neigh_dist = _to_object_array(np.split(data, indptr[1:-1]))
+    neigh_ind = _to_object_array(np.split(indices, indptr[1:-1]))
 
     if return_distance:
         return neigh_dist, neigh_ind
     else:
         return neigh_ind
 
 
+def _to_object_array(sequence):
path: sklearn/neighbors/_base.py
text: @user1:
```suggestion
def _to_object_array(sequence):
    """Convert sequence to a 1-D NumPy array of object dtype.
    
    Parameters
    ----------
    sequence : array-like of shape (n_elements,)
        The sequence to be converted
        
    Returns
    -------
    out : ndarray of shape (n_elements,), dtype=object
        The converted sequence into a 1-D NumPy array of object dtype.
    """
```