Talip7/scikit-learn-issues-multilabel huggingface dataset:
RuntimeError: "Cannot clone object ..." when cloning an estimator that copies parameters in either __init__ or get_params

### Describe the bug

Context: https://github.com/scikit-learn/scikit-learn/issues/15722#issuecomment-893942972

Calling `clone()` on a BaseEstimator that copies parameters results in a RuntimeError, even if the parameters are otherwise equal (`estimator.param == clone(estimator).param` returns True but `estimator.param is clone(estimator.param)` returns False).

Either the documentation has an issue in that this is an unspecified requirement for `clone()` to work (and BaseEstimator `__init__()` and `get_params()` documentation should say that parameters must always be the same object), or the equality check in `clone()` is too strict and should be loosened.

### Steps/Code to Reproduce

```python
from sklearn.base import BaseEstimator, clone

class TestEstimator(BaseEstimator):
    def __init__(self, my_dict):
        self.my_dict = my_dict.copy()

some_dict = {'foo': 'bar'}
estimator = TestEstimator(some_dict)

clone(estimator)      # raises RuntimeError: Cannot clone object TestEstimator(my_dict={'foo': 'bar'}), as the constructor either does not set or modifies parameter my_dict
```

### Expected Results

Calling `clone(estimator)` results in a new TestEstimator where the following assertions are true:

```python
from sklearn.base import BaseEstimator, clone

class TestEstimator(BaseEstimator):
    def __init__(self, my_dict):
        self.my_dict = my_dict.copy()

some_dict = {'foo': 'bar'}
estimator = TestEstimator(some_dict)

new_estimator = clone(estimator)

assert estimator is not new_estimator
assert estimator.some_dict == new_estimator.some_dict        #  this isn't strictly necessary, but if clone() is going to assert equality then this seems like the right kind of check
assert estimator.some_dict is not new_estimator.some_dict

# no RuntimeError or AssertionError should be raised after running this snippet
```

### Actual Results

```python
>>> clone(estimator)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/wchill/miniconda/envs/test38/lib/python3.8/site-packages/sklearn/base.py", line 95, in clone
    raise RuntimeError(
RuntimeError: Cannot clone object TestEstimator(my_dict={'foo': 'bar'}), as the constructor either does not set or modifies parameter my_dict
```

### Versions

```shell
>>> import sklearn; sklearn.show_versions()

System:
    python: 3.8.12 (default, Oct 12 2021, 06:23:56)  [Clang 10.0.0 ]
executable: /Users/wchill/miniconda/envs/test38/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
          pip: 21.2.4
   setuptools: 58.0.4
      sklearn: 1.0.2
        numpy: 1.22.3
        scipy: 1.8.0
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.1.0
threadpoolctl: 3.1.0

Built with OpenMP: True
```

COMMENT:
There's a fix here https://github.com/scikit-learn/scikit-learn/pull/22973, but it raises another issue with `ndarray`s.

Labels: Bug
RuntimeError: "Cannot clone object ..." when cloning an estimator that copies parameters in either __init__ or get_params

### Describe the bug

Context: https://github.com/scikit-learn/scikit-learn/issues/15722#issuecomment-893942972

Calling `clone()` on a BaseEstimator that copies parameters results in a RuntimeError, even if the parameters are otherwise equal (`estimator.param == clone(estimator).param` returns True but `estimator.param is clone(estimator.param)` returns False).

Either the documentation has an issue in that this is an unspecified requirement for `clone()` to work (and BaseEstimator `__init__()` and `get_params()` documentation should say that parameters must always be the same object), or the equality check in `clone()` is too strict and should be loosened.

### Steps/Code to Reproduce

```python
from sklearn.base import BaseEstimator, clone

class TestEstimator(BaseEstimator):
    def __init__(self, my_dict):
        self.my_dict = my_dict.copy()

some_dict = {'foo': 'bar'}
estimator = TestEstimator(some_dict)

clone(estimator)      # raises RuntimeError: Cannot clone object TestEstimator(my_dict={'foo': 'bar'}), as the constructor either does not set or modifies parameter my_dict
```

### Expected Results

Calling `clone(estimator)` results in a new TestEstimator where the following assertions are true:

```python
from sklearn.base import BaseEstimator, clone

class TestEstimator(BaseEstimator):
    def __init__(self, my_dict):
        self.my_dict = my_dict.copy()

some_dict = {'foo': 'bar'}
estimator = TestEstimator(some_dict)

new_estimator = clone(estimator)

assert estimator is not new_estimator
assert estimator.some_dict == new_estimator.some_dict        #  this isn't strictly necessary, but if clone() is going to assert equality then this seems like the right kind of check
assert estimator.some_dict is not new_estimator.some_dict

# no RuntimeError or AssertionError should be raised after running this snippet
```

### Actual Results

```python
>>> clone(estimator)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/wchill/miniconda/envs/test38/lib/python3.8/site-packages/sklearn/base.py", line 95, in clone
    raise RuntimeError(
RuntimeError: Cannot clone object TestEstimator(my_dict={'foo': 'bar'}), as the constructor either does not set or modifies parameter my_dict
```

### Versions

```shell
>>> import sklearn; sklearn.show_versions()

System:
    python: 3.8.12 (default, Oct 12 2021, 06:23:56)  [Clang 10.0.0 ]
executable: /Users/wchill/miniconda/envs/test38/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
          pip: 21.2.4
   setuptools: 58.0.4
      sklearn: 1.0.2
        numpy: 1.22.3
        scipy: 1.8.0
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.1.0
threadpoolctl: 3.1.0

Built with OpenMP: True
```

COMMENT:
Oh I see. For that all meta-estimators should be cloning the given estimator in `fit`, not `__init__`, and store it under another attribute such as `self.estimator_`.

Labels: Bug
The fit performance of LinearRegression is sub-optimal

It seems that the performance of Linear Regression is sub-optimal when the number of samples is very large. 

[sklearn_benchmarks](https://github.com/mbatoul/sklearn_benchmarks) measures a [speedup of 48](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/master/20220315T132336/scikit_learn_intelex_vs_scikit_learn.html#linearregression) compared to an optimized implementation from scikit-learn-intelex on a `1000000x100` dataset. For a given set of parameters and a given dataset, we compute the speed-up `time scikit-learn` / `time sklearnex`. A speed-up of 48 means that sklearnex is 48 times faster than scikit-learn on the given dataset.

[Profiling](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/improve_cli/20220314T105014/profiling/sklearn_fit_0c037d7431f8fb8e89db7b3f3f29b083_ddd328af83cd4ef15164ddaa0fa01ba4.json.gz) allows a more detailed analysis of the execution of the algorithm. We observe that most of the execution time is spent in the [`lstsq` solver of scipy](https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.lstsq.html).

<img width="1538" alt="image" src="https://user-images.githubusercontent.com/36322423/158272733-92f107f4-92cf-4e26-887d-2a0818113d2d.png">

The profiling reports of sklearn_benchmarks can be viewed with [Perfetto UI](https://ui.perfetto.dev/).

<details>
  <summary>See benchmark environment information</summary>
  
<img width="946" alt="image" src="https://user-images.githubusercontent.com/36322423/158276716-2ab08b7d-079d-4cb8-82fc-054e6b9e8f40.png">
</details>

It seems that the solver could be better chosen when the number of samples is very large. Perhaps Ridge's solver with a zero penalty could be chosen in this case. On the same dimensions, [it shows better performance](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/improve_cli/20220314T105014/scikit_learn_intelex_vs_scikit_learn.html#Ridge).

Speedups can be reproduced with the following code:

```bash
conda create -n lr_perf -c conda-forge scikit-learn scikit-learn-intelex numpy jupyter
conda activate lr_perf
```

```python
from sklearn.linear_model import LinearRegression as LinearRegressionSklearn
from sklearnex.linear_model import LinearRegression as LinearRegressionSklearnex
from sklearn.datasets import make_regression
import time
import numpy as np

X, y = make_regression(n_samples=1_000_000, n_features=100, n_informative=10)

def measure(estimator, X, y, n_executions=10):
    times = []
    while len(times) < n_executions:
        t0 = time.perf_counter()
        estimator.fit(X, y)
        t1 = time.perf_counter()
        times.append(t1 - t0)

    return np.mean(times)

mean_time_sklearn = measure(
    estimator=LinearRegressionSklearn(),
    X=X,
    y=y
)

mean_time_sklearnex = measure(
    estimator=LinearRegressionSklearnex(),
    X=X,
    y=y
)

speedup = mean_time_sklearn / mean_time_sklearnex
speedup
```

COMMENT:
Then let‘s switch to lsqr or lsmr as default.

Labels: Performance, module:linear_model
The fit performance of LinearRegression is sub-optimal

It seems that the performance of Linear Regression is sub-optimal when the number of samples is very large. 

[sklearn_benchmarks](https://github.com/mbatoul/sklearn_benchmarks) measures a [speedup of 48](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/master/20220315T132336/scikit_learn_intelex_vs_scikit_learn.html#linearregression) compared to an optimized implementation from scikit-learn-intelex on a `1000000x100` dataset. For a given set of parameters and a given dataset, we compute the speed-up `time scikit-learn` / `time sklearnex`. A speed-up of 48 means that sklearnex is 48 times faster than scikit-learn on the given dataset.

[Profiling](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/improve_cli/20220314T105014/profiling/sklearn_fit_0c037d7431f8fb8e89db7b3f3f29b083_ddd328af83cd4ef15164ddaa0fa01ba4.json.gz) allows a more detailed analysis of the execution of the algorithm. We observe that most of the execution time is spent in the [`lstsq` solver of scipy](https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.lstsq.html).

<img width="1538" alt="image" src="https://user-images.githubusercontent.com/36322423/158272733-92f107f4-92cf-4e26-887d-2a0818113d2d.png">

The profiling reports of sklearn_benchmarks can be viewed with [Perfetto UI](https://ui.perfetto.dev/).

<details>
  <summary>See benchmark environment information</summary>
  
<img width="946" alt="image" src="https://user-images.githubusercontent.com/36322423/158276716-2ab08b7d-079d-4cb8-82fc-054e6b9e8f40.png">
</details>

It seems that the solver could be better chosen when the number of samples is very large. Perhaps Ridge's solver with a zero penalty could be chosen in this case. On the same dimensions, [it shows better performance](https://mbatoul.github.io/sklearn_benchmarks/results/github_ci/improve_cli/20220314T105014/scikit_learn_intelex_vs_scikit_learn.html#Ridge).

Speedups can be reproduced with the following code:

```bash
conda create -n lr_perf -c conda-forge scikit-learn scikit-learn-intelex numpy jupyter
conda activate lr_perf
```

```python
from sklearn.linear_model import LinearRegression as LinearRegressionSklearn
from sklearnex.linear_model import LinearRegression as LinearRegressionSklearnex
from sklearn.datasets import make_regression
import time
import numpy as np

X, y = make_regression(n_samples=1_000_000, n_features=100, n_informative=10)

def measure(estimator, X, y, n_executions=10):
    times = []
    while len(times) < n_executions:
        t0 = time.perf_counter()
        estimator.fit(X, y)
        t1 = time.perf_counter()
        times.append(t1 - t0)

    return np.mean(times)

mean_time_sklearn = measure(
    estimator=LinearRegressionSklearn(),
    X=X,
    y=y
)

mean_time_sklearnex = measure(
    estimator=LinearRegressionSklearnex(),
    X=X,
    y=y
)

speedup = mean_time_sklearn / mean_time_sklearnex
speedup
```

COMMENT:
Just following up if there is any updates?

Labels: Performance, module:linear_model
Birch is not finding clusters correctly

### Describe the bug

Birch do not correctly find clusters if the number of samples of one cluster is much larger than another cluster even if the distance between clusters is much larger than threshold.

### Steps/Code to Reproduce

```python
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch
import numpy as np

X1, y1 = make_blobs(n_samples=10000, centers=[[0.6, 0.6]], cluster_std=0.01, random_state=0)
X2, y2 = make_blobs(n_samples=100, centers=[[0.1, 0.1]], cluster_std=0.01, random_state=0)

X = np.append(X1, X2, axis = 0)

brc = Birch(n_clusters=None, threshold = 0.1)
brc.fit(X)

brc.subcluster_centers_
```

### Expected Results

Expected two subclusters  since the distance between clusters is much larger than used threshold.

### Actual Results

Only one subcluster is detected

`brc.subcluster_centers_`:

```
array([[0.59494558, 0.59509375]])
```


### Versions

```shell
System:
    python: 3.8.6 | packaged by conda-forge | (default, Jan 25 2021, 23:21:18)  [GCC 9.3.0]
executable: /home/envs/env1_custom/bin/python
   machine: Linux-4.14.252

Python dependencies:
          pip: 22.0.3
   setuptools: 60.9.3
      sklearn: 1.0.2
        numpy: 1.20.2
        scipy: 1.7.0
       Cython: None
       pandas: 1.2.4
   matplotlib: 3.5.1
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True
```

COMMENT:
Indeed, that looks fishy. Note that the problem goes away when increasing the size of X2 to 300 point but I still don't understand why it happens when X2 has fewer samples. I agree it shouldn't be the case.

Here is a simpler deterministic reproducer where we are sure that the distances between the clusters are larger than the merge threshold:

```python
>>> from sklearn.datasets import make_blobs
... from sklearn.cluster import Birch
... import numpy as np
... 
... X1 = np.array([[0.6, 0.6]] * 10000)
... X2 = np.array([[0.1, 0.1]] * 100)
... 
... X = np.append(X1, X2, axis=0)
... 
... brc = Birch(n_clusters=None, threshold=0.1)
... brc.fit(X)
... 
... brc.subcluster_centers_
```

Labels: Bug, module:cluster
Birch is not finding clusters correctly

### Describe the bug

Birch do not correctly find clusters if the number of samples of one cluster is much larger than another cluster even if the distance between clusters is much larger than threshold.

### Steps/Code to Reproduce

```python
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch
import numpy as np

X1, y1 = make_blobs(n_samples=10000, centers=[[0.6, 0.6]], cluster_std=0.01, random_state=0)
X2, y2 = make_blobs(n_samples=100, centers=[[0.1, 0.1]], cluster_std=0.01, random_state=0)

X = np.append(X1, X2, axis = 0)

brc = Birch(n_clusters=None, threshold = 0.1)
brc.fit(X)

brc.subcluster_centers_
```

### Expected Results

Expected two subclusters  since the distance between clusters is much larger than used threshold.

### Actual Results

Only one subcluster is detected

`brc.subcluster_centers_`:

```
array([[0.59494558, 0.59509375]])
```


### Versions

```shell
System:
    python: 3.8.6 | packaged by conda-forge | (default, Jan 25 2021, 23:21:18)  [GCC 9.3.0]
executable: /home/envs/env1_custom/bin/python
   machine: Linux-4.14.252

Python dependencies:
          pip: 22.0.3
   setuptools: 60.9.3
      sklearn: 1.0.2
        numpy: 1.20.2
        scipy: 1.7.0
       Cython: None
       pandas: 1.2.4
   matplotlib: 3.5.1
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True
```

COMMENT:
Interestingly, the order of the points changes the outcome. This version (notice that I swapped X1 and X2) gives the expected result:
```python
>>> from sklearn.datasets import make_blobs
... from sklearn.cluster import Birch
... import numpy as np
... 
... X1 = np.array([[0.6, 0.6]] * 10000)
... X2 = np.array([[0.1, 0.1]] * 100)
... 
... X = np.append(X2, X1, axis=0)
... 
... brc = Birch(n_clusters=None, threshold=0.1)
... brc.fit(X)
... 
... brc.subcluster_centers_
```

Labels: Bug, module:cluster
Birch is not finding clusters correctly

### Describe the bug

Birch do not correctly find clusters if the number of samples of one cluster is much larger than another cluster even if the distance between clusters is much larger than threshold.

### Steps/Code to Reproduce

```python
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch
import numpy as np

X1, y1 = make_blobs(n_samples=10000, centers=[[0.6, 0.6]], cluster_std=0.01, random_state=0)
X2, y2 = make_blobs(n_samples=100, centers=[[0.1, 0.1]], cluster_std=0.01, random_state=0)

X = np.append(X1, X2, axis = 0)

brc = Birch(n_clusters=None, threshold = 0.1)
brc.fit(X)

brc.subcluster_centers_
```

### Expected Results

Expected two subclusters  since the distance between clusters is much larger than used threshold.

### Actual Results

Only one subcluster is detected

`brc.subcluster_centers_`:

```
array([[0.59494558, 0.59509375]])
```


### Versions

```shell
System:
    python: 3.8.6 | packaged by conda-forge | (default, Jan 25 2021, 23:21:18)  [GCC 9.3.0]
executable: /home/envs/env1_custom/bin/python
   machine: Linux-4.14.252

Python dependencies:
          pip: 22.0.3
   setuptools: 60.9.3
      sklearn: 1.0.2
        numpy: 1.20.2
        scipy: 1.7.0
       Cython: None
       pandas: 1.2.4
   matplotlib: 3.5.1
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True
```

COMMENT:
This should not happen as easily in a *full* implementation of BIRCH/BETULA, when the threshold is handled dynamically. But implementing a good threshold heuristic is in fact hard; with 10k duplicates the best initial threshold will likely be 0 though; and then it will "just work" (unless you hit the numerical issues of BIRCH, that is).
Also, if you use Euclidean distance as radius criterion - which does not depend on the variance - it should not happen. Then the first point of the second cluster should create a new leaf node.
Neither is currently implemented in scikit-learn if I recall correctly.
But I like this example as a case why maybe we should always use Euclidean radius with BIRCH, even if we want to optimize for variance in the end. So far, my opinion was that you should use distance and radius criterion to be the same (not intended in BIRCH, but trivially possible), and align them with your clustering objective (e.g., minimum variance for k-means and Ward).

Labels: Bug, module:cluster
Birch is not finding clusters correctly

### Describe the bug

Birch do not correctly find clusters if the number of samples of one cluster is much larger than another cluster even if the distance between clusters is much larger than threshold.

### Steps/Code to Reproduce

```python
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch
import numpy as np

X1, y1 = make_blobs(n_samples=10000, centers=[[0.6, 0.6]], cluster_std=0.01, random_state=0)
X2, y2 = make_blobs(n_samples=100, centers=[[0.1, 0.1]], cluster_std=0.01, random_state=0)

X = np.append(X1, X2, axis = 0)

brc = Birch(n_clusters=None, threshold = 0.1)
brc.fit(X)

brc.subcluster_centers_
```

### Expected Results

Expected two subclusters  since the distance between clusters is much larger than used threshold.

### Actual Results

Only one subcluster is detected

`brc.subcluster_centers_`:

```
array([[0.59494558, 0.59509375]])
```


### Versions

```shell
System:
    python: 3.8.6 | packaged by conda-forge | (default, Jan 25 2021, 23:21:18)  [GCC 9.3.0]
executable: /home/envs/env1_custom/bin/python
   machine: Linux-4.14.252

Python dependencies:
          pip: 22.0.3
   setuptools: 60.9.3
      sklearn: 1.0.2
        numpy: 1.20.2
        scipy: 1.7.0
       Cython: None
       pandas: 1.2.4
   matplotlib: 3.5.1
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True
```

COMMENT:
Hello,

By any chance do you have a reference on this adaptive threshold ? I was not able to find it...
Scikit-learn's implementation relies on both euclidean distance and absorption threhsold. In this example, the euclidean distance condition is triggered but because one of the clusters is so big, the absorption threshold based on the variance prevents the split.

What I find troublesome is that the outcome of the algorithm depends on the input data ordering. We may be able to find a way to precondition data to make birch more reliable. For example, in this example, shuffling the data before birch leads to :
- 53% outcome with 1 cluster
- 47% outcome with 2 clusters

My guess is that it should be possible to find a not-so-stupid way to prepare the data and achieve better ratios.

Labels: Bug, module:cluster
Birch is not finding clusters correctly

### Describe the bug

Birch do not correctly find clusters if the number of samples of one cluster is much larger than another cluster even if the distance between clusters is much larger than threshold.

### Steps/Code to Reproduce

```python
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch
import numpy as np

X1, y1 = make_blobs(n_samples=10000, centers=[[0.6, 0.6]], cluster_std=0.01, random_state=0)
X2, y2 = make_blobs(n_samples=100, centers=[[0.1, 0.1]], cluster_std=0.01, random_state=0)

X = np.append(X1, X2, axis = 0)

brc = Birch(n_clusters=None, threshold = 0.1)
brc.fit(X)

brc.subcluster_centers_
```

### Expected Results

Expected two subclusters  since the distance between clusters is much larger than used threshold.

### Actual Results

Only one subcluster is detected

`brc.subcluster_centers_`:

```
array([[0.59494558, 0.59509375]])
```


### Versions

```shell
System:
    python: 3.8.6 | packaged by conda-forge | (default, Jan 25 2021, 23:21:18)  [GCC 9.3.0]
executable: /home/envs/env1_custom/bin/python
   machine: Linux-4.14.252

Python dependencies:
          pip: 22.0.3
   setuptools: 60.9.3
      sklearn: 1.0.2
        numpy: 1.20.2
        scipy: 1.7.0
       Cython: None
       pandas: 1.2.4
   matplotlib: 3.5.1
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True
```

COMMENT:
Its mentioned in the original BIRCH papers already, but the details are a bit vague. Only the "outlier" handling is even less vague.

> Tian Zhang, Raghu Ramakrishnan, and Miron Livny. 1996. BIRCH: an efficient data clustering method for very large databases. SIGMOD Rec. 25, 2 (June 1996), 103–114. https://doi.org/10.1145/235968.233324

Page 107, but see also section 5.1.2, which gives a heuristic for choosing a new threshold
> It starts with an initial threshold value, scans the data, and inserts points into the tree. If it runs out of memory before it finishes scanning the data, it increases the threshold value, rebuilds a new, smaller CF tree, by re-inserting the leaf entries of the old tree. 

As a "hot fix", try simply using Euclidean distance as absorption threshold, too. This makes the behavior of this parameter closer to what the submitter of this issue expected.

As for usability, it would of course make sense to be able to default to a threshold of 0 (as in the BIRCH paper, page 108), and let the threshold be indirectly controlled by the memory limit.

Labels: Bug, module:cluster