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:
A couple of points while this issue is being discussed (and again, it is great that Scikit-learn is discussing this) which I was aware of while developing RCF -- these would have been awkward distractions from the focus of discussing RCF, but maybe a broader knowledge of these would he helpful to the community. There may be a way to improve isolation forest itself in several ways -- and some of the discussions raised in this thread can apply to RCF as well as towards an isolation forest with more options.

The issue of scale invariance goes both ways -- while it is desirable, it is also often the case that an user does not know the importance of columns. So the basic extent computation (normalization) may be an useful option in any analysis. One way to view the l_i is to think of repeated normalization. This is clearly of importance to dynamic invariant and Gauge Theory stands as  an example -- but while the overt dynamics is streaming, the more subtle dynamics is multiscale analysis. In the RCF package I played around with L_\alpha metrics of the extent boxes (and I would describe Isolation Forest using L0 and RCF using L1) and they could be useful generalizations for both. For example, compute an L_\alpha probability measure (alpha'th power of each side of the box divided by sum of alpha'th power of  all sides) of a box and then split the box probabilistically. 

Second -- the key thinking behind the CoDisp measure was a "bottom up dynamic progamming approach over a tree" as opposed to a top down path following. For example, if the tree is constructed with 3D samples all of which had z-coordinate 0; and we were evaluating a point with z = 1 (standard out of sample generalization), then the bottom up process can easily accomodate that recompute the contrafactual probability (of what it would have been if the point was available at construction time). In fact, once the bottom up evaluation (in CoDisp) is created, it is easy to compute expected_inverse_depth which is a slightly smoother estimate than CoDisp and easier to get to a normalize score by multiplying log_2 sample_size. It is also interesting that E[invese_depth] >= 1/E[depth] via Jensen's inequality and the power of depth based methods may be substantially increased via expected inverse depth. The expected_inverse_depth has properties that ca be proven to allow conformal forecasts as well. Happy to discuss further if the CoDisp/bottom-up evaluation is a feasibility -- because then there would likely be an improved isolation forest as well.
best,

Labels: New Feature, Needs Decision, Needs Decision - Include Feature