Talip7/scikit-learn-issues-multilabel huggingface dataset:
Implementation of Robust Random Cut Forest (RRCF) Algorithm

### Describe the workflow you want to enable

Enable users to perform robust anomaly detection using the Robust Random Cut Forest (RRCF) algorithm within the scikit-learn library.

### Describe your proposed solution

## Proposed Solution

I suggest the integration of the Robust Random Cut Forest (RRCF) [[paper](http://proceedings.mlr.press/v48/guha16.pdf)] algorithm into the scikit-learn library. The RRCF algorithm is a natural extension of the Isolation Forest. It presents improved capabilities in handling noisy data, outliers, and stream data scenarios.

The core idea behind RRCF is akin to the Isolation Forest—building binary search trees using random cuts in the input data space. The key distinction lies in the _probability of selecting a cut dimension being proportionate to the dimension's length_. This unique characteristic renders RRCF particularly suitable for scenarios where the Isolation Forest may not perform optimally.

## Implementation

The underlying tree and forest structure of RRCF closely resembles that of the existing iForest, as previously mentioned. The primary difference arises in the computation of anomaly scores, specifically within the `decision_function`.

Additionally, to cater to stream data scenarios, the implementation could (and it should) incorporate methods for efficient insertion and deletion of individual points, as mentioned in the paper.

### Existing Implementations

A pre-existing Python implementation of RRCF can be found at https://github.com/kLabUM/rrcf. This implementation appears to be well-structured and accurate, making it a potential reference for scikit-learn's integration.

I would greatly appreciate your consideration of this proposal. Thank you.

On a side note, please don't hesitate to point out any mistakes/enhancements in the proposal. I'll be glad to assist.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

This past summer, I had the opportunity to work with anomaly detection algorithms, and among them, I had the chance to closely explore the Robust Random Cut Forest (RRCF). Interestingly, I discovered that while scikit-learn already has Isolation Forest algorithm, RRCF implementation is still missing. This revelation has sparked a motivating drive within me to advocate for the integration of RRCF.

Although it is plausible that this discussion on this topic might have already been occurred, but I was not able to find anything related to RRCF in the issues section or in [scikit-learn-contrib](https://github.com/scikit-learn-contrib/scikit-learn-contrib) except in [this comment](https://github.com/scikit-learn/scikit-learn/issues/17307#issuecomment-632795440) (where the context is kind of different).

COMMENT:
Any updates on this? @betatim @glemaitre @adam2392

Labels: New Feature, Needs Decision, Needs Decision - Include Feature
Implementation of Robust Random Cut Forest (RRCF) Algorithm

### Describe the workflow you want to enable

Enable users to perform robust anomaly detection using the Robust Random Cut Forest (RRCF) algorithm within the scikit-learn library.

### Describe your proposed solution

## Proposed Solution

I suggest the integration of the Robust Random Cut Forest (RRCF) [[paper](http://proceedings.mlr.press/v48/guha16.pdf)] algorithm into the scikit-learn library. The RRCF algorithm is a natural extension of the Isolation Forest. It presents improved capabilities in handling noisy data, outliers, and stream data scenarios.

The core idea behind RRCF is akin to the Isolation Forest—building binary search trees using random cuts in the input data space. The key distinction lies in the _probability of selecting a cut dimension being proportionate to the dimension's length_. This unique characteristic renders RRCF particularly suitable for scenarios where the Isolation Forest may not perform optimally.

## Implementation

The underlying tree and forest structure of RRCF closely resembles that of the existing iForest, as previously mentioned. The primary difference arises in the computation of anomaly scores, specifically within the `decision_function`.

Additionally, to cater to stream data scenarios, the implementation could (and it should) incorporate methods for efficient insertion and deletion of individual points, as mentioned in the paper.

### Existing Implementations

A pre-existing Python implementation of RRCF can be found at https://github.com/kLabUM/rrcf. This implementation appears to be well-structured and accurate, making it a potential reference for scikit-learn's integration.

I would greatly appreciate your consideration of this proposal. Thank you.

On a side note, please don't hesitate to point out any mistakes/enhancements in the proposal. I'll be glad to assist.

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

This past summer, I had the opportunity to work with anomaly detection algorithms, and among them, I had the chance to closely explore the Robust Random Cut Forest (RRCF). Interestingly, I discovered that while scikit-learn already has Isolation Forest algorithm, RRCF implementation is still missing. This revelation has sparked a motivating drive within me to advocate for the integration of RRCF.

Although it is plausible that this discussion on this topic might have already been occurred, but I was not able to find anything related to RRCF in the issues section or in [scikit-learn-contrib](https://github.com/scikit-learn-contrib/scikit-learn-contrib) except in [this comment](https://github.com/scikit-learn/scikit-learn/issues/17307#issuecomment-632795440) (where the context is kind of different).

COMMENT:
Any updates on this?

Labels: New Feature, Needs Decision, Needs Decision - Include Feature
⚠️ CI failed on Wheel builder ⚠️

**CI failed on [Wheel builder](https://github.com/scikit-learn/scikit-learn/actions/runs/6007650858)** (Aug 29, 2023)

COMMENT:
## CI is no longer failing! ✅

[Successful run](https://github.com/scikit-learn/scikit-learn/actions/runs/6020290075) on Aug 30, 2023

Labels: Needs Triage
⚠️ CI failed on Linux.pylatest_pip_openblas_pandas ⚠️

**CI failed on [Linux.pylatest_pip_openblas_pandas](https://dev.azure.com/scikit-learn/scikit-learn/_build/results?buildId=58415&view=logs&j=78a0bf4f-79e5-5387-94ec-13e67d216d6e)** (Aug 29, 2023)
- test_pairwise_distances_argkmin[45-float32-parallel_on_X-cityblock-0-500]
- test_pairwise_distances_argkmin[45-float32-parallel_on_Y-cityblock-0-500]

COMMENT:
## CI is no longer failing! ✅

[Successful run](https://dev.azure.com/scikit-learn/scikit-learn/_build/results?buildId=58833&view=logs&j=78a0bf4f-79e5-5387-94ec-13e67d216d6e) on Sep 11, 2023

Labels: Needs Triage
⚠️ CI failed on Linux.pylatest_pip_openblas_pandas ⚠️

**CI failed on [Linux.pylatest_pip_openblas_pandas](https://dev.azure.com/scikit-learn/scikit-learn/_build/results?buildId=58415&view=logs&j=78a0bf4f-79e5-5387-94ec-13e67d216d6e)** (Aug 29, 2023)
- test_pairwise_distances_argkmin[45-float32-parallel_on_X-cityblock-0-500]
- test_pairwise_distances_argkmin[45-float32-parallel_on_Y-cityblock-0-500]

COMMENT:
Duplicate of #27126.

Labels: Needs Triage
Better documentation for `RFECV`

There is almost no description in the documentation of how `RFECV` actually works. The [user guide](https://scikit-learn.org/stable/modules/feature_selection.html#rfe) simply says

> [RFECV](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html#sklearn.feature_selection.RFECV) performs RFE in a cross-validation loop to find the optimal number of features.

and the [API page](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html) simply says

> Recursive feature elimination with cross-validation to select features. 

My best guess for what `RFECV` is actually doing is the following.

1. Start with all features.
2. Do the following (in either order):
    a) Fit the estimator on all rows of `X` (for the current subset of features). Use `coefs_` or `feature_importances_` or a callable to select the feature(s) that will be removed in the next round.
    b) Run cross-validation with the estimator on `X` to estimate the accuracy of the estimator trained on the current subset of features.
3. Remove the features chosen for removal in step 2a.
4. Repeat steps 2 and 3 until the minimum number of features has been reached.
5. Select the set of features that maximizes the CV scores calculated in step 2b. (This set of features is recorded in the `support_` attribute.)

Is that correct? Furthermore, can a detailed explanation of what `RFECV` is doing be added to the documentation?

COMMENT:
No, your description does not match what happens here. I gave an answer about this on StackOverflow once; see if it's helpful:  https://stackoverflow.com/a/65557483/10495893

I agree that adding some more details to the documentation would be beneficial.

Labels: Documentation
Better documentation for `RFECV`

There is almost no description in the documentation of how `RFECV` actually works. The [user guide](https://scikit-learn.org/stable/modules/feature_selection.html#rfe) simply says

> [RFECV](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html#sklearn.feature_selection.RFECV) performs RFE in a cross-validation loop to find the optimal number of features.

and the [API page](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html) simply says

> Recursive feature elimination with cross-validation to select features. 

My best guess for what `RFECV` is actually doing is the following.

1. Start with all features.
2. Do the following (in either order):
    a) Fit the estimator on all rows of `X` (for the current subset of features). Use `coefs_` or `feature_importances_` or a callable to select the feature(s) that will be removed in the next round.
    b) Run cross-validation with the estimator on `X` to estimate the accuracy of the estimator trained on the current subset of features.
3. Remove the features chosen for removal in step 2a.
4. Repeat steps 2 and 3 until the minimum number of features has been reached.
5. Select the set of features that maximizes the CV scores calculated in step 2b. (This set of features is recorded in the `support_` attribute.)

Is that correct? Furthermore, can a detailed explanation of what `RFECV` is doing be added to the documentation?

COMMENT:
The description provided by @bmreiniger is correct: a different `RFE` is run on different CV split and we collect scores that are later averaged out by fold. `n_features_` corresponds to the maximum averaged score.

Labels: Documentation
Better documentation for `RFECV`

There is almost no description in the documentation of how `RFECV` actually works. The [user guide](https://scikit-learn.org/stable/modules/feature_selection.html#rfe) simply says

> [RFECV](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html#sklearn.feature_selection.RFECV) performs RFE in a cross-validation loop to find the optimal number of features.

and the [API page](https://scikit-learn.org/stable/modules/generated/sklearn.feature_selection.RFECV.html) simply says

> Recursive feature elimination with cross-validation to select features. 

My best guess for what `RFECV` is actually doing is the following.

1. Start with all features.
2. Do the following (in either order):
    a) Fit the estimator on all rows of `X` (for the current subset of features). Use `coefs_` or `feature_importances_` or a callable to select the feature(s) that will be removed in the next round.
    b) Run cross-validation with the estimator on `X` to estimate the accuracy of the estimator trained on the current subset of features.
3. Remove the features chosen for removal in step 2a.
4. Repeat steps 2 and 3 until the minimum number of features has been reached.
5. Select the set of features that maximizes the CV scores calculated in step 2b. (This set of features is recorded in the `support_` attribute.)

Is that correct? Furthermore, can a detailed explanation of what `RFECV` is doing be added to the documentation?

COMMENT:
So here we need the following:

#### Edit the docstring of the `RFECV` class

```
    Recursive feature elimination with cross-validation to select features.

    The number of features selected is tuned automatically by fitting an :class:`RFE`
    selector on the different cross-validation splits (provided by the `cv` parameter).
    The performance of the :class:`RFE` selector are evaluated using `scorer` for
    different number of selected features and aggregated together. Finally, the scores
    are averaged across folds and the number of features selected is set to the number
    of features that maximize the cross-validation score.
```

#### Edit the user guide (i.e. `feature_selection.rst` file)

```
:class:`RFECV` performs RFE in a cross-validation loop to find the optimal
number of features. In more details, the number of features selected is tuned
automatically by fitting an :class:`RFE` selector on the different
cross-validation splits (provided by the `cv` parameter). The performance
of the :class:`RFE` selector are evaluated using `scorer` for different number
of selected features and aggregated together. Finally, the scores are averaged
across folds and the number of features selected is set to the number of
features that maximize the cross-validation score.
```

Labels: Documentation
F1 score not calculated properly

### Describe the bug

According to the [definition](https://en.wikipedia.org/wiki/F-score) of the F1 score for two classes, it can be calculated as 

$$
2 \frac{2tp}{2tp + fp + fn}
$$

or 

$$
2 \frac{precision * recall}{precision + recall}
$$

From what I can see, scikit-learn [uses](https://github.com/scikit-learn/scikit-learn/blob/38a06e4be504f3971d109d6741b8b4c7192d7323/sklearn/metrics/_classification.py#L1764C11-L1764C11) some variant of the second definition. The problem is that the first definition can be valid, while the second gives a division by zero as the precision is not defined.

$$
precision = \frac{tp}{tp + fp}
$$

$$
recall = \frac{tp}{tp + fn}
$$

For definitions of precision and recall, see [Wikipedia](https://en.wikipedia.org/wiki/Precision_and_recall). 

Below, I give a code example where this happens.

### Steps/Code to Reproduce

```python
from sklearn.metrics import f1_score, precision_score, recall_score
import sklearn.metrics
import numpy as np

y_true = [True, False, True]
y_pred = [False, False, False]

tn, fp, fn, tp = sklearn.metrics.confusion_matrix(
    y_true, y_pred, labels=[False, True]
).ravel()

print("TN:", tn)
print("FP:", fp)
print("FN:", fn)
print("TP:", tp)

precision = tp / (tp + fp)
recall = tp / (tp + fn)
print("Precision:", precision)
print("Recall:", recall)

f1_true = 2 * tp / (2 * tp + fp + fn)
print("F1 (true):", f1_true)

f1_sk = f1_score(y_true, y_pred, zero_division=np.nan)
print("F1 (sklearn):", f1_sk)
```

### Expected Results

```
TN: 1
FP: 0
FN: 2
TP: 0
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): 0.0
```

### Actual Results

```
TN: 1
FP: 0
FN: 2
TP: 0
<ipython-input-1-d59969af6bb0>:17: RuntimeWarning: invalid value encountered in scalar divide
  precision = tp / (tp + fp)
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): nan
```

### Versions

```shell
System:
    python: 3.11.5 | packaged by conda-forge | (main, Aug 27 2023, 03:33:12) [Clang 15.0.7 ]
executable: /Users/Kjell/mambaforge/envs/sklearn/bin/python3.11
   machine: macOS-13.4.1-arm64-arm-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.2.1
   setuptools: 68.1.2
        numpy: 1.25.2
        scipy: 1.11.2
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libopenblas.0.dylib
        version: 0.3.23
threading_layer: openmp
   architecture: VORTEX

       user_api: openmp
   internal_api: openmp
    num_threads: 8
         prefix: libomp
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libomp.dylib
        version: None
```

COMMENT:
You are using scikit-learn 1.2.2 where `zero_division=np.nan` is not implemented yet, thus the error. The documentation you are citing is for version 1.3

Labels: Bug
F1 score not calculated properly

### Describe the bug

According to the [definition](https://en.wikipedia.org/wiki/F-score) of the F1 score for two classes, it can be calculated as 

$$
2 \frac{2tp}{2tp + fp + fn}
$$

or 

$$
2 \frac{precision * recall}{precision + recall}
$$

From what I can see, scikit-learn [uses](https://github.com/scikit-learn/scikit-learn/blob/38a06e4be504f3971d109d6741b8b4c7192d7323/sklearn/metrics/_classification.py#L1764C11-L1764C11) some variant of the second definition. The problem is that the first definition can be valid, while the second gives a division by zero as the precision is not defined.

$$
precision = \frac{tp}{tp + fp}
$$

$$
recall = \frac{tp}{tp + fn}
$$

For definitions of precision and recall, see [Wikipedia](https://en.wikipedia.org/wiki/Precision_and_recall). 

Below, I give a code example where this happens.

### Steps/Code to Reproduce

```python
from sklearn.metrics import f1_score, precision_score, recall_score
import sklearn.metrics
import numpy as np

y_true = [True, False, True]
y_pred = [False, False, False]

tn, fp, fn, tp = sklearn.metrics.confusion_matrix(
    y_true, y_pred, labels=[False, True]
).ravel()

print("TN:", tn)
print("FP:", fp)
print("FN:", fn)
print("TP:", tp)

precision = tp / (tp + fp)
recall = tp / (tp + fn)
print("Precision:", precision)
print("Recall:", recall)

f1_true = 2 * tp / (2 * tp + fp + fn)
print("F1 (true):", f1_true)

f1_sk = f1_score(y_true, y_pred, zero_division=np.nan)
print("F1 (sklearn):", f1_sk)
```

### Expected Results

```
TN: 1
FP: 0
FN: 2
TP: 0
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): 0.0
```

### Actual Results

```
TN: 1
FP: 0
FN: 2
TP: 0
<ipython-input-1-d59969af6bb0>:17: RuntimeWarning: invalid value encountered in scalar divide
  precision = tp / (tp + fp)
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): nan
```

### Versions

```shell
System:
    python: 3.11.5 | packaged by conda-forge | (main, Aug 27 2023, 03:33:12) [Clang 15.0.7 ]
executable: /Users/Kjell/mambaforge/envs/sklearn/bin/python3.11
   machine: macOS-13.4.1-arm64-arm-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.2.1
   setuptools: 68.1.2
        numpy: 1.25.2
        scipy: 1.11.2
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libopenblas.0.dylib
        version: 0.3.23
threading_layer: openmp
   architecture: VORTEX

       user_api: openmp
   internal_api: openmp
    num_threads: 8
         prefix: libomp
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libomp.dylib
        version: None
```

COMMENT:
So is the issue fixed and ready to be closed?

Labels: Bug
F1 score not calculated properly

### Describe the bug

According to the [definition](https://en.wikipedia.org/wiki/F-score) of the F1 score for two classes, it can be calculated as 

$$
2 \frac{2tp}{2tp + fp + fn}
$$

or 

$$
2 \frac{precision * recall}{precision + recall}
$$

From what I can see, scikit-learn [uses](https://github.com/scikit-learn/scikit-learn/blob/38a06e4be504f3971d109d6741b8b4c7192d7323/sklearn/metrics/_classification.py#L1764C11-L1764C11) some variant of the second definition. The problem is that the first definition can be valid, while the second gives a division by zero as the precision is not defined.

$$
precision = \frac{tp}{tp + fp}
$$

$$
recall = \frac{tp}{tp + fn}
$$

For definitions of precision and recall, see [Wikipedia](https://en.wikipedia.org/wiki/Precision_and_recall). 

Below, I give a code example where this happens.

### Steps/Code to Reproduce

```python
from sklearn.metrics import f1_score, precision_score, recall_score
import sklearn.metrics
import numpy as np

y_true = [True, False, True]
y_pred = [False, False, False]

tn, fp, fn, tp = sklearn.metrics.confusion_matrix(
    y_true, y_pred, labels=[False, True]
).ravel()

print("TN:", tn)
print("FP:", fp)
print("FN:", fn)
print("TP:", tp)

precision = tp / (tp + fp)
recall = tp / (tp + fn)
print("Precision:", precision)
print("Recall:", recall)

f1_true = 2 * tp / (2 * tp + fp + fn)
print("F1 (true):", f1_true)

f1_sk = f1_score(y_true, y_pred, zero_division=np.nan)
print("F1 (sklearn):", f1_sk)
```

### Expected Results

```
TN: 1
FP: 0
FN: 2
TP: 0
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): 0.0
```

### Actual Results

```
TN: 1
FP: 0
FN: 2
TP: 0
<ipython-input-1-d59969af6bb0>:17: RuntimeWarning: invalid value encountered in scalar divide
  precision = tp / (tp + fp)
Precision: nan
Recall: 0.0
F1 (true): 0.0
F1 (sklearn): nan
```

### Versions

```shell
System:
    python: 3.11.5 | packaged by conda-forge | (main, Aug 27 2023, 03:33:12) [Clang 15.0.7 ]
executable: /Users/Kjell/mambaforge/envs/sklearn/bin/python3.11
   machine: macOS-13.4.1-arm64-arm-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.2.1
   setuptools: 68.1.2
        numpy: 1.25.2
        scipy: 1.11.2
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libopenblas.0.dylib
        version: 0.3.23
threading_layer: openmp
   architecture: VORTEX

       user_api: openmp
   internal_api: openmp
    num_threads: 8
         prefix: libomp
       filepath: /Users/Kjell/mambaforge/envs/sklearn/lib/libomp.dylib
        version: None
```

COMMENT:
No, issue remains.

Labels: Bug
BUG (maybe) wrong node bound spread in KernelDensity

### Describe the bug

https://github.com/scikit-learn/scikit-learn/blob/a5620f45614ac3f849c430f53146a66319e4908b/sklearn/neighbors/_binary_tree.pxi.tp#L2114-L2116

https://github.com/scikit-learn/scikit-learn/blob/a5620f45614ac3f849c430f53146a66319e4908b/sklearn/neighbors/_binary_tree.pxi.tp#L2121-L2123

These lines do not seem to be correct. The right-hand side seems to be node log max bound but not node log bound spread. Should they instead be

```python
node_log_bound_spreads[i1] = logsubexp(log(N1)+ compute_log_kernel(dist_LB_1, h, kernel),
                                       node_log_min_bounds[i1])
node_log_bound_spreads[i2] = logsubexp(log(N2)+ compute_log_kernel(dist_LB_2, h, kernel),
                                       node_log_min_bounds[i2])
```

I don't really find an unexpected result or something, just got confused when reading the code.

COMMENT:
@jakevdp Do you think that you could have a quick look at those lines?

Labels: Needs Investigation