Talip7/scikit-learn-issues-multilabel huggingface dataset:
BUG: trees: `criterion="friedman_mse"` is buggy for multi-output

### Describe the bug

The calculation implemented in `FriedmanMSE.proxy_impurity_improvement` is plain wrong for the multi-output case.

When reading the code, it's fairly obvious that outputs are mixed in a way that doesn't mathematically make sense.

**Note:** I open this issue just for the records, as `"friedman_mse"` will be removed anyway (see #32700 )

### Steps/Code to Reproduce

```Python
import numpy as np
from sklearn.tree import DecisionTreeRegressor, plot_tree

X = [[1], [2], [3], [4]]
y = np.array([
    [1, -1],
    [1, -1],
    [0, 0],
    [0, 0]
])

tree = DecisionTreeRegressor(criterion="friedman_mse")
tree.fit(X, y)
plot_tree(tree);
```

### Expected Results

Split in the middle (x <= 2.5), reducing the error to 0 in one split.

### Actual Results

non-optimal split:

<img width="515" height="389" alt="Image" src="https://github.com/user-attachments/assets/7d42c1b5-0647-4b46-b5f5-9daa3b550247" />

### Versions

```shell
System:
    python: 3.12.11 (main, Aug 18 2025, 19:19:11) [Clang 20.1.4 ]
executable: [/home/arthur/dev-perso/scikit-learn/sklearn-env/bin/python](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/bin/python)
   machine: Linux-6.14.0-35-generic-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.8.dev0
          pip: None
   setuptools: 80.9.0
        numpy: 2.3.4
        scipy: 1.16.2
       Cython: 3.1.5
       pandas: 2.3.3
   matplotlib: 3.10.7
       joblib: 1.5.2
threadpoolctl: 3.6.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: [/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-8fb3d286.so](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-8fb3d286.so)
        version: 0.3.30
threading_layer: pthreads
   architecture: Haswell

       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: [/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so)
        version: 0.3.29.dev
threading_layer: pthreads
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 16
         prefix: libgomp
       filepath: [/usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0](https://file+.vscode-resource.vscode-cdn.net/usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0)
        version: None
```

COMMENT:
> this bug should not be reachable by users at the moment.

What do you mean? `criterion="friedman_mse"` can be passed to decision trees and random forests, and is documented:
*“friedman_mse”, which uses mean squared error with Friedman’s improvement score for potential splits*

Labels: Bug
BUG: trees: `criterion="friedman_mse"` is buggy for multi-output

### Describe the bug

The calculation implemented in `FriedmanMSE.proxy_impurity_improvement` is plain wrong for the multi-output case.

When reading the code, it's fairly obvious that outputs are mixed in a way that doesn't mathematically make sense.

**Note:** I open this issue just for the records, as `"friedman_mse"` will be removed anyway (see #32700 )

### Steps/Code to Reproduce

```Python
import numpy as np
from sklearn.tree import DecisionTreeRegressor, plot_tree

X = [[1], [2], [3], [4]]
y = np.array([
    [1, -1],
    [1, -1],
    [0, 0],
    [0, 0]
])

tree = DecisionTreeRegressor(criterion="friedman_mse")
tree.fit(X, y)
plot_tree(tree);
```

### Expected Results

Split in the middle (x <= 2.5), reducing the error to 0 in one split.

### Actual Results

non-optimal split:

<img width="515" height="389" alt="Image" src="https://github.com/user-attachments/assets/7d42c1b5-0647-4b46-b5f5-9daa3b550247" />

### Versions

```shell
System:
    python: 3.12.11 (main, Aug 18 2025, 19:19:11) [Clang 20.1.4 ]
executable: [/home/arthur/dev-perso/scikit-learn/sklearn-env/bin/python](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/bin/python)
   machine: Linux-6.14.0-35-generic-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.8.dev0
          pip: None
   setuptools: 80.9.0
        numpy: 2.3.4
        scipy: 1.16.2
       Cython: 3.1.5
       pandas: 2.3.3
   matplotlib: 3.10.7
       joblib: 1.5.2
threadpoolctl: 3.6.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: [/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-8fb3d286.so](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-8fb3d286.so)
        version: 0.3.30
threading_layer: pthreads
   architecture: Haswell

       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: [/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so](https://file+.vscode-resource.vscode-cdn.net/home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so)
        version: 0.3.29.dev
threading_layer: pthreads
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 16
         prefix: libgomp
       filepath: [/usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0](https://file+.vscode-resource.vscode-cdn.net/usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0)
        version: None
```

COMMENT:
Indeed, you are right.

Labels: Bug
Add Apriori Algorithm for Association Rule Mining

### Describe the workflow you want to enable

I would like scikit-learn to support association rule mining by implementing the Apriori algorithm. This would allow users to efficiently find frequent itemsets and generate association rules directly within the scikit-learn framework, similar to other supervised and unsupervised learning algorithms.

Use cases include market basket analysis, recommendation systems, and pattern discovery in categorical datasets. The workflow would involve:

-  Inputting transactional or categorical data.

- Generating frequent itemsets with a minimum support threshold.

- Producing association rules with metrics such as confidence, lift, and leverage.

### Describe your proposed solution

Implement an Apriori class or function in the sklearn.preprocessing or sklearn.association module that provides:

- fit() to generate frequent itemsets.

- generate_rules() to produce association rules.

- Support for configurable metrics: support, confidence, lift, leverage.

- Compatibility with pandas DataFrames and NumPy arrays.

### Describe alternatives you've considered, if relevant

Currently, Python libraries like mlxtend
 provide Apriori and association rule mining. However, integrating it into scikit-learn would:

- Ensure consistent API with scikit-learn estimators.

- Enable seamless integration with pipelines and transformers.

- Benefit users who prefer a single framework for all ML tasks.

### Additional context

- Association rule mining is a common unsupervised learning task, widely used in industry.

- Many users are already using mlxtend alongside scikit-learn, but a native implementation would improve performance, maintainability, and ecosystem consistency.

COMMENT:
Thank you for creating this issue thread, @simoderyouch, and for helping make scikit-learn better.

scikit-learn is [selective](https://scikit-learn.org/stable/faq.html#why-are-you-so-selective-on-what-algorithms-you-include-in-scikit-learn) when it comes to adding new algorithms. In particular, there is a clear list of [inclusion criteria for new algorithms](https://scikit-learn.org/stable/faq.html#what-are-the-inclusion-criteria-for-new-algorithms).

Since each line of code adds to the long-term maintenance responsibility, it's important that you strongly justify how your proposed feature or algorithm meets these criteria. Doing so will help maintainers make an informed decision. Without a clear and well-reasoned justification, I will close this issue to avoid unnecessary maintenance overhead.

Labels: New Feature, Needs Info, Needs Triage
Add Apriori Algorithm for Association Rule Mining

### Describe the workflow you want to enable

I would like scikit-learn to support association rule mining by implementing the Apriori algorithm. This would allow users to efficiently find frequent itemsets and generate association rules directly within the scikit-learn framework, similar to other supervised and unsupervised learning algorithms.

Use cases include market basket analysis, recommendation systems, and pattern discovery in categorical datasets. The workflow would involve:

-  Inputting transactional or categorical data.

- Generating frequent itemsets with a minimum support threshold.

- Producing association rules with metrics such as confidence, lift, and leverage.

### Describe your proposed solution

Implement an Apriori class or function in the sklearn.preprocessing or sklearn.association module that provides:

- fit() to generate frequent itemsets.

- generate_rules() to produce association rules.

- Support for configurable metrics: support, confidence, lift, leverage.

- Compatibility with pandas DataFrames and NumPy arrays.

### Describe alternatives you've considered, if relevant

Currently, Python libraries like mlxtend
 provide Apriori and association rule mining. However, integrating it into scikit-learn would:

- Ensure consistent API with scikit-learn estimators.

- Enable seamless integration with pipelines and transformers.

- Benefit users who prefer a single framework for all ML tasks.

### Additional context

- Association rule mining is a common unsupervised learning task, widely used in industry.

- Many users are already using mlxtend alongside scikit-learn, but a native implementation would improve performance, maintainability, and ecosystem consistency.

COMMENT:
Apparently there was an earlier discussion about including associative learning algorithms in issue #2662. After reading through it, I'm even more convinced that pattern mining, while interesting and useful, sits outside the scope of machine learning as defined in scikit-learn. It feels more appropriate for a separate dedicated library.

With that said, I'm leaning toward closing this issue unless other maintainers feel differently

Have you considered contributing this to [scikit-mine](https://github.com/scikit-mine/scikit-mine) or [scikit-learn-contrib](https://github.com/scikit-learn-contrib)? That would fit the use case much better.

Labels: New Feature, Needs Info, Needs Triage
BUG: tree/forest regressor: impurity decrease calculation is wrong for criterion "friedman_mse"

### Describe the bug

Well, everything is in the title.

I noticed that while writing the issue #32700 

I'm opening this issue just for the records, as we plan to remove `"friedman_mse"` criterion anyway.

### Steps/Code to Reproduce

```Python
import numpy as np
from sklearn.tree import DecisionTreeRegressor

X = np.arange(5).reshape(-1, 1)
y = [0, 1, 0, 1, 0]

reg = DecisionTreeRegressor(min_impurity_decrease=0.1, max_depth=1, criterion="friedman_mse")
reg.fit(X, y)

weighted_impurity = reg.tree_.impurity * reg.tree_.n_node_samples / X.shape[0]
actual_decrease = weighted_impurity[0] - weighted_impurity[1:3].sum()

assert actual_decrease >= 0.1
```

Or simply running the test `sklearn/tree/tests/test_tree.py::test_min_impurity_decrease` with criterion `"friedman_mse"`

### Expected Results

No error

### Actual Results

Assertion error

### Versions

```shell
System:
    python: 3.12.11 (main, Aug 18 2025, 19:19:11) [Clang 20.1.4 ]
executable: /home/arthur/dev-perso/scikit-learn/sklearn-env/bin/python
   machine: Linux-6.14.0-35-generic-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.8.dev0
          pip: None
   setuptools: 80.9.0
        numpy: 2.3.4
        scipy: 1.16.2
       Cython: 3.1.5
       pandas: 2.3.3
   matplotlib: 3.10.7
       joblib: 1.5.2
threadpoolctl: 3.6.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: /home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-8fb3d286.so
        version: 0.3.30
threading_layer: pthreads
   architecture: Haswell

       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libscipy_openblas
       filepath: /home/arthur/dev-perso/scikit-learn/sklearn-env/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so
        version: 0.3.29.dev
threading_layer: pthreads
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 16
         prefix: libgomp
       filepath: /usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0
        version: None
```

COMMENT:
Follow-up from this issue: the test `test_min_impurity_decrease` should test all criteria. My PR https://github.com/scikit-learn/scikit-learn/pull/32699 does that.

Labels: Bug
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:
Hi — I ran a small local benchmark comparing sklearn (with sklearnex patched) to test performance on large datasets. I opened a draft PR with the script and a tiny smoke test.

Results I observed locally:

=== n_samples = 50,000 ===  
training_time(s) = 3.525, test_acc = 0.9643 (using_intel=True)

=== n_samples = 100,000 ===  
training_time(s) = 8.011, test_acc = 0.9635 (using_intel=True)

=== n_samples = 200,000 ===  
training_time(s) = 19.350, test_acc = 0.9654 (using_intel=True)

Intel-optimized sklearn used (`sklearnex.patch_sklearn()`).

I can expand the benchmarks, prototype a pure-Python histogram splitter, and propose an opt-in API for RandomForest/bagging.

Draft PR: https://github.com/scikit-learn/scikit-learn/pull/32729

— @vanshy-git

Labels: RFC
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:
@vanshy-git please don't create PRs for issues where the discussion has not yet converged. Those PRs create notifications to a lot of people and tend to split discussions up between PRs and issues. I will close your PR.

Labels: RFC
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 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)).

For my education: what you mean is using something like a `Pipeline` with `KBinsDiscretizer` followed by a `RandomForestClassifier` (with a specialised treatment that is based on the knowledge that all features are now binned)?

A kinda related example https://scikit-learn.org/stable/auto_examples/preprocessing/plot_discretization.html#sphx-glr-auto-examples-preprocessing-plot-discretization-py

Labels: RFC
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 haven't though about using a `Pipeline` for that, but that's exactly the idea. I was just thinking about implementing that inside RFs and adapting the code downstream (using `dtype=uint8` for binned features, using O(n) "counts-sort", ...).

Labels: RFC
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 agree that opening the PR (#32729) was premature, so I’ll keep further work strictly to design + benchmark discussion until we converge on an approach.

Based on the feedback:

1. Histogram-based splitting may not be ideal for deep trees, but
2. Using binned features to unlock O(n) count-based sorting (or a hybrid strategy) does seem like a promising direction for accelerating bagging-based ensembles.

To move the discussion forward without generating noise, I’ll prepare:

• A more complete benchmark matrix (varying n_samples, n_features, max_depth, and node distributions) comparing: current RandomForest, HGB, sklearnex and a pure-Python prototype using binned features + count-sort.

• A minimal, opt-in prototype design (not a PR yet), proposing something like:
RandomForestClassifier(..., binning='auto' or binning=n_bins)
where binning only affects the fit method, remains off by default, and falls back to the existing splitter for small/deep nodes.

The goal is to evaluate whether a hybrid strategy
(binned O(n) sorting for large nodes + classic sort for small nodes)
gives meaningful speedups while preserving current RF behavior.

I’ll share benchmark results and a prototype sketch here before opening any PR.

Labels: RFC
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've recently discussed this work stream with @jovo who had interesting ideas, and exps to back it up. Perhaps he'd like to chime in if he has some time?

tldr:
1. building the histogram bins will likely dominate the runtime if we do it at every split node. Alternatively, doing it only once at the beginning of training trees seems peculiar
2. instead of histogram binning, we should just do random sampling to establish to approximate quantiles. I.e. empirical CDF.

Labels: RFC
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:
Some thoughts:

- YDF histograms once a priori, and then just deals with it. Seems adequate for them.
- Indeed, histograms are slower than exact sorting when leaves don't contain many samples.
- In the lab, we are working on dynamic histogramming, in which we do histograms when the leaves have a lot of samples, but not when they don't.  This works way faster than either option.
- There are lots of ways to histogram, the slowest and likely 'best' is quantiles, rather than equal width bins. 
- Subsampling is much faster than histogramming, and I think probably about as good (though I have nearly no data to support that belief)

Happy to discuss more, or share some results when they are 'clean' enough for public consumption :)

Labels: RFC
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:
Thanks a lot for the helpful insights! Dynamic histogramming sounds promising! Do you combine with multi-threading? (asking this because for small leaves, we also have a problem with multi-threading in [HBGT](https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.HistGradientBoostingClassifier.html), see https://github.com/scikit-learn/scikit-learn/issues/14306. The root problem is similar: both histogram computation and multi-threading have some overhead that makes them counter productive for small leaves).

Labels: RFC
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:
For HGB think we need a strategy to automatically disable (openmp-based) multi-threading for node sizes below a threshold.

For RFs, we could continue using tree-level parallelism instead (and disable node-splitting level parallelism in the Cython code entirely). scikit-learn-intelex and AMD AOCL-DA are probably doing this and this leads to empirical performance improvements for RF models.

Labels: RFC
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:
> Subsampling is much faster than histogramming, and I think probably about as good (though I have nearly no data to support that belief)

I think I had quickly experimented with subsampling a long time ago, but I was disappointed with the results (accuracy vs speed tradeoff) compared to exact RFs. But it's possible that my experimental code was suboptimal, or my evaluation protocol was incomplete though (and I did not keep that branch). If someone wants to investigate in an experimental scikit-learn fork and report back, that would be interesting.

Labels: RFC