RFC: Allow training random forests with histograms on binned feature values

This issue is very related to #27873.

If/when the above is implemented, it should also be possible to refactor the tree code to leverage histogram splits for bagging-based tree ensembles.

Histogram-based split is the main reason, while scikit-learn-intelex's `RandomForestClassifier` is much faster that our `RandomForestClassifier` when trained on datasets with many data points.

COMMENT:
I don't think histogram-based splitting is suited for random forests because **it's not adapted for deep trees.**

Here is a small benchmark comparing splitting speed for HGB and random forests by fitting them in equivalent conditions: same number of trees, same trees depth, same number of threads/processes.

<details>

(warning: takes ~ 12 minutes to run)

```Python
from time import perf_counter

from threadpoolctl import threadpool_limits
import numpy as np
from sklearn.ensemble import HistGradientBoostingRegressor, RandomForestRegressor

n_fit = 4
n_skip = 1
rng = np.random.default_rng()

df_rows = []

for distrib in ['U([0, 1])', 'G(1/3)']:
    for n_jobs in [1, 2, 4]:
        for max_depth in [3, 6, 9, 12]:            
            n = 300_000 // max_depth
            d = 30

            hgb = HistGradientBoostingRegressor(
                max_iter=30,
                max_leaf_nodes=None,
                max_depth=max_depth,
                min_samples_leaf=1,
                early_stopping=False,
            )
            rf = RandomForestRegressor(n_jobs=n_jobs, max_depth=max_depth, n_estimators=30)

            df_row = {
                'distrib': distrib,
                'n_jobs': n_jobs,
                'max_depth': max_depth,
            }
            for name, reg in [('hgb', hgb), ('rf', rf)]:
                dts = []
                for _ in range(n_fit):
                    if distrib == 'U([0, 1])':
                        X = rng.uniform(0, 1, size=(n, d)) #rng.geometric(1/3, size=(n, d))
                        y = X[:, ::3].sum(axis=1) + d/10 * rng.random(n)
                    else:
                        X = rng.geometric(1/3, size=(n, d))
                        y = X[:, ::3].sum(axis=1) + d/3 * rng.random(n)
                    with threadpool_limits(n_jobs):
                        t = perf_counter()
                        reg.fit(X, y) 
                        dts.append(perf_counter() - t)
                avg = np.mean(dts[n_skip:])
                df_row[name] = avg

            df_rows.append(df_row)


import pandas as pd

df = pd.DataFrame(df_rows)
df['t(rf)/t(hgb)'] = (df['rf']/ df['hgb']).round(2)
df['n'] = 300_000 // df['max_depth']
df['t(rf)'] = df['rf'].round(1)
df['t(hgb)'] = df['hgb'].round(1)
df = df.set_index(['distrib', 'n_jobs', 'max_depth', 'n']).drop(columns=['hgb', 'rf'])[['t(rf)', 't(hgb)', 't(rf)/t(hgb)']]
df
```

</details>

**Results:**

<img width="450" height="620" alt="Image" src="https://github.com/user-attachments/assets/74fc1253-470b-4d95-968c-c4fa6d81bb4e" />

Observations:
- HBG is quite slow for deep trees, especially when parallelism is enabled (the threads start-up time probably kills perf in this case).
- The distribution has a big impacts on t(rf): it's because of the sort used in decision trees (3-way partitioning quick-sort, see section below). For the distribution G(1/3) (geometric distribution with p=1/3), this sort is very fast.
- Parallelism is not linearly improving performances. I guess memory bandwidth limits gain you get from parallelism? As fitting trees requires many memory accesses but not that many computations in comparison (something like 3 flops for 1 memory access I would say). **Edit:** my laptop has just overall poor multi-threading performances, results are hard to interpret.

-----

**But I deeply agree that binning would make random forests much faster.** I just think that you don't need histogram-based splitting, you can keep the current logic of sort then left->right swipe and just use the fact you're working with binned values to vastly speed-up the sort (O(n log n) -> O(n)).

I experimented quite a lot with sorting feature values for trees, and here are my thoughts. You have three types of sort that are relevant for decision trees:
- 3-way partitioning quick-sort: the currently implemented sort in decision trees. O(n log n) but very efficient on features where a few values concentrate most of the samples (e.g. 90% of the samples have value 1, 2 or 3).
- 2-way partitioning quick-sort: O(n log n), much faster for features with no duplicates (e.g. `X = np.random.rand(n, d)`), like 3-10x faster IIRC.
- count-based sorting: only works to sort integers in {0, ..., m-1} where m is not too big. Complexity: O(n + m). Ultra fast compared to quick-sort when m << n. This is what binning unlocks. You could also pre-process features to map values to their ranks to be able to use it. This would be very efficient for features with a small number of unique values. Note that this sort isn't interesting for small nodes (which you'll get for deep trees), unless m is really small.

I think the most promising opportunities for speeding up bagging-based tree ensembles lie in using a sorting strategy adapted to each feature. I believe we can achieve a 2–10× speed-up depending on the case if we implement these ideas: using ranks for low-cardinality features, binning for high-cardinality features, or switching to a two-way partitioning quicksort for the latter when appropriate.

Labels: RFC