Error when fitting UMAP with a target vector and target_metric != "categorical"
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 8.3k
- Forks
- 871
- Avg merge
- 1d 13h
- Merged PRs (30d)
- 5
Description
Hi,
I tried to fit UMAP with a target vector `y` and several metrics and I got an error.
The following code will result in an error.
```python
import numpy as np
from umap import UMAP
rng = np.random.RandomState(123)
n_samples = 10
n_features = 48
n_classes = 2
X = rng.randn(n_samples, n_features)
y = rng.randint(n_classes, size=n_samples)
umap = UMAP(n_neighbors=3, random_state=123,
target_metric="euclidean", angular_rp_forest=False)
res = umap.fit_transform(X, y)
```
```python
AttributeError Traceback (most recent call last)
in ()
1 umap = UMAP(n_neighbors=3, random_state=123, target_metric="euclidean", angular_rp_forest=False)
----> 2 res = umap.fit_transform(X, y)
~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in fit_transform(self, X, y)
1521 Embedding of the training data in low-dimensional space.
1522 """
-> 1523 self.fit(X, y)
1524 return self.embedding_
1525
~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in fit(self, X, y)
1459 1.0,
1460 1.0,
-> 1461 False,
1462 )
1463 # product = self.graph_.multiply(target_graph)
~/anaconda3/lib/python3.5/site-packages/umap/umap_.py in nearest_neighbors(X, n_neighbors, metric, metric_kwds, angular, random_state, verbose)
246 n_iters = max(5, int(round(np.log2(X.shape[0]))))
247
--> 248 rp_forest = make_forest(X, n_neighbors, n_trees, rng_state, angular)
249 leaf_array = rptree_leaf_array(rp_forest)
250 knn_indices, knn_dists = metric_nn_descent(
~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in make_forest(data, n_neighbors, n_trees, rng_state, angular)
706 result = [
707 flatten_tree(make_tree(data, rng_state, leaf_size, angular), leaf_size)
--> 708 for i in range(n_trees)
709 ]
710 except (RuntimeError, RecursionError):
~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in (.0)
706 result = [
707 flatten_tree(make_tree(data, rng_state, leaf_size, angular), leaf_size)
--> 708 for i in range(n_trees)
709 ]
710 except (RuntimeError, RecursionError):
~/anaconda3/lib/python3.5/site-packages/umap/rp_tree.py in flatten_tree(tree, leaf_size)
638 n_leaves = num_leaves(tree)
639
--> 640 if len(tree.hyperplane.shape) > 1:
641 # sparse case
642 max_hyperplane_nnz = max_sparse_hyperplane_size(tree)
AttributeError: 'NoneType' object has no attribute 'shape'
```
It looks like tree.hyperplane is `None`. Looking at the called functions, `make_tree` calls either `make_angular_tree `, `make_euclidean_tree` or their sparse versions. They all have the same structure, so let's take `make_euclidean_tree`:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L439-L455
The `hyperplane` attribute is set to `None` if the condition is not satisfied. Looking at [euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L131-L217), I don't think this function can return `None` for `hyperplane_vector` because it is defined and modified there only:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L170-L173
I would guess that this error occurs when there is only one node in the graph.
I did a little more testing and it looks like that the error only occurs if one of the following criteria is satisfied:
* `n_samples (i.e. X.shape[0]) <= 10`
* `n_samples > 10` and `n_neighbors >= n_samples `
### Edit 1
It seems like the error occurs in those scenarios because of the definition of `leaf_size` in `make_forest`:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L704
and since `indices.shape[0]` is equal to `n_samples`:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L546
the condition in the `if else` loop of `make_euclidean_tree` is never satisfied.
### Edit 2
`n_neighbors` is defined at the beginning of the `fit` method of UMAP:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1336-L1347
but afterwards, `n_neighbors` and `self.n_neighbors` are both used in the method:
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1361-L1366
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1390-L1392
https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/umap_.py#L1445-L1447
Using only `n_neighbors` is probably what is intended and I think that it would fix the issue for the second setting. The first setting would still raise an error because `leaf_size` would be equal to 10 and it would be greater than or equal to the number of samples.
### NB
[angular_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L29-L53), [euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L132-L156), [sparse_angular_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L221-L250) and [sparse_euclidean_random_projection_split](https://github.com/lmcinnes/umap/blob/d286224a86dfe730c76f082c6f523b69b57bd0f8/umap/rp_tree.py#L331-L360) all have the same docstring issue (the Returns section doesn't match what is returned by the function).
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the supplied fit_transform reproduction, then inspect umap/umap_.py around n_neighbors handling and umap/rp_tree.py around make_forest, make_euclidean_tree, and the random projection split functions. Verify behavior for the reported small-sample and large-n_neighbors cases, and confirm that the documented return values match the split functions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- machine-learning
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100