Talip7/scikit-learn-issues-multilabel huggingface dataset:
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Thanks for opening the issue and the reproducer.

This would require more investigation. You could, for instance, profile the code (https://docs.python.org/3/library/profile.html) and find areas where they take long and we could make them faster.

However, on my system I cannot reproduce the issue. Your script (after adjusting for new versions of sklearn) runs under 1 minute:

```
$ /bin/tim python /tmp/1.py          
zsh: correct '/bin/tim' to '/bin/time' [nyae]? y
392.73user 6.50system 0:52.53elapsed 759%CPU (0avgtext+0avgdata 3533596maxresident)k
0inputs+0outputs (0major+81368minor)pagefaults 0swaps
```

Please try using the latest Python and all other dependencies, and if the issue persists, try profiling the code and let us know which areas could be improved.

Labels: New Feature, Needs Triage
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
> Thanks for opening the issue and the reproducer.
> 
> This would require more investigation. You could, for instance, profile the code (https://docs.python.org/3/library/profile.html) and find areas where they take long and we could make them faster.
> 
> However, on my system I cannot reproduce the issue. Your script (after adjusting for new versions of sklearn) runs under 1 minute:
> 
> ```
> $ /bin/tim python /tmp/1.py          
> zsh: correct '/bin/tim' to '/bin/time' [nyae]? y
> 392.73user 6.50system 0:52.53elapsed 759%CPU (0avgtext+0avgdata 3533596maxresident)k
> 0inputs+0outputs (0major+81368minor)pagefaults 0swaps
> ```
> 
> Please try using the latest Python and all other dependencies, and if the issue persists, try profiling the code and let us know which areas could be improved.

According to your trace, the code runs in ~52 s of wall time and ~6.5 minutes of CPU time. It is a very long time for fitting a Gaussian mixture model to 3000 observations. With another data frame of this size, it will take around 1 second, maybe less.  So you reproduced the issue with latest Python and dependencies.

Labels: New Feature, Needs Triage
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Happy to have a look at optimization potentials if you'd be kind and run a profile to figure out which parts of the code need improving.

Labels: New Feature, Needs Triage
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
I profiled the code above and a version that randomises the order in each column, using 3,000,000 rows in the latter instead of 3,000 in the former, in order to have a bit more to measure.

Here is some visual extract for the random (regular) case:
![random](https://github.com/user-attachments/assets/f3aa30a2-6374-4998-87c5-cef9001c2b50)

And the equivalent for the pathological case:
![pathological](https://github.com/user-attachments/assets/da8bf896-01da-4e15-a01c-27695944dc38)

I also join the .pstat files produced by the profiler in both cases.

[profiles.zip](https://github.com/user-attachments/files/16338228/profiles.zip)

It looks like a lot more time is spent in function `_cholesky` in the pathological case, although I am unsure why.

Labels: New Feature, Needs Triage
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Note that at least in your randomly generated data, you're having an extremely sparse categorical column (basically like a unique ID). You're also using `full` as `covariance_type`, which might take longer than others, and you could use a different `init_params` than the default `kmeans`. These would already speed up your process a bit.

Otherwise, I don't see anything particularly suspicious in the trace here, and most of the time is spent on the numpy side.

Labels: New Feature, Needs Triage
GaussianMixture takes very long in pathological cases

### Describe the workflow you want to enable

In general, fitting a GaussianMixture works well and quickly (~1s). However in certain cases it takes very long, even though the data set is not very big. A simple example that takes almost a minute (5.5 minutes of CPU clock time on my computer) follows.

```py
import numpy as np
import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.mixture import GaussianMixture
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import OneHotEncoder, StandardScaler

num_rows = 3000
col_types = {"int_col": "category", "float_col": float, "str_col": "category"}
int_col = [x for x in range(num_rows)]
float_col = [float(x) for x in int_col]
str_col = [str(x) for x in int_col]
x_train = pd.DataFrame({"int_col": int_col, "float_col": float_col, "str_col": str_col}).astype(
    col_types
)

numerical = list(x_train.select_dtypes(include=np.number).columns)
numeric_transformer = Pipeline(steps=[("scaler", StandardScaler())])
categorical = list(x_train.select_dtypes(include="category").columns)
categorical_transformer = Pipeline(
    steps=[("onehot", OneHotEncoder(handle_unknown="ignore", sparse=False))]
)
transformations = ColumnTransformer(
    transformers=[
        ("num", numeric_transformer, numerical),
        ("cat", categorical_transformer, categorical),
    ]
)
gmm = GaussianMixture(n_components=3)
pipeline = Pipeline(
    steps=[
        ("preprocessor", transformations),
        ("gmm", gmm),
    ]
)
pipeline.fit(x_train)
```

### Describe your proposed solution

I do not know enough to propose a solution. However this doesn't seem to be desirable behaviour.


### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_

COMMENT:
Thank you, indeed using "diag" or "spherical" as covariance type makes a big difference.

Labels: New Feature, Needs Triage
KNNImputer - output shape not equal input shape

### Describe the bug

The output of the fit_tranform is not equal to the input shape, when the NaN's are all in one column

### Steps/Code to Reproduce

```
from sklearn.impute import KNNImputer
input  = np.random.rand(5, 5)
input[0,4]=np.nan
input[1,4]=np.nan
input[2,4]=np.nan
input[3,4]=np.nan
input[4,4]=np.nan

output = KNNImputer(n_neighbors=2).fit_transform(input)
input.shape == output.shape
```

### Expected Results

`True`

### Actual Results

`False`

### Versions

```shell
System:
    python: 3.11.9 (main, Apr 19 2024, 16:48:06) [GCC 11.2.0]
executable: /scratch/miniconda3/envs/tls2image/bin/python
   machine: Linux-5.10.102.1-microsoft-standard-WSL2-x86_64-with-glibc2.35
Python dependencies:
      sklearn: 1.5.1
          pip: 23.3.1
   setuptools: 68.2.2
        numpy: 1.26.4
        scipy: 1.13.0
       Cython: None
       pandas: 2.2.1
   matplotlib: 3.8.4
       joblib: 1.4.0
threadpoolctl: 3.5.0
Built with OpenMP: True
threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libopenblas
       filepath: /scratch/miniconda3/envs/tls2image/lib/python3.11/site-packages/numpy.libs/libopenblas64_p-r0-0cf96a72.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Zen
       user_api: blas
   internal_api: openblas
    num_threads: 16
         prefix: libopenblas
       filepath: /scratch/miniconda3/envs/tls2image/lib/python3.11/site-packages/scipy.libs/libopenblasp-r0-24bff013.3.26.dev.so
        version: 0.3.26.dev
threading_layer: pthreads
   architecture: Zen
       user_api: openmp
   internal_api: openmp
    num_threads: 16
         prefix: libgomp
       filepath: /scratch/miniconda3/envs/tls2image/lib/python3.11/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None
       user_api: blas
   internal_api: openblas
    num_threads: 1
         prefix: libopenblas
       filepath: /scratch/miniconda3/envs/tls2image/lib/python3.11/site-packages/opencv_python.libs/libopenblas-r0-f650aae0.3.3.so
        version: None
threading_layer: disabled
   architecture: Barcelona
```

COMMENT:
Hi @SchmidL,

the `KNNImputer` removes features, which consist completely of missing values by intention.
If you want to keep them to keep the dimensions, you could use the `keep_empty_features` attribute:

```python
output = KNNImputer(n_neighbors=2, keep_empty_features=True).fit_transform(input)
```

This solves your problem.
But beware that the missing values will then be set to 0.0, see <https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/impute/_knn.py#L74>.

Labels: Bug, Needs Triage
NDCG in case of abscence of relevant items

### Describe the bug

In `sklearn.metrics._ndcg_sample_scores`, there is a counterintuitive handling of the case where all true relevances are equal to zero for some samples. In this case, DCG = 0, IDCG = 0, and the whole NDCG is not defined. In `sklearn` implementation it is defined as 0 and included in the averaged NDCG calculation.  The least leads to strange effects, like `ndcg_score(y,y) != 1`; moreover, it affects the metric value in non-trivial cases too.

In the original 2002 paper where NDCG is proposed, it is not stated how to handle such situations, but it is clearly mentioned that 
```
The (D)CG vectors for each IR technique can be normalized by dividing them
by the corresponding ideal (D)CG vectors, component by component. In this way,
for any vector position, the normalized value 1 represents ideal performance,
and values in the range [0, 1) the share of ideal performance cumulated by each
technique.
```
meaning that NDCG(y,y) must always be 1. 


I suggest excluding observations without relevant items and/or throwing a warning.

### Steps/Code to Reproduce

```
>>> from sklearn.metrics import ndcg_score
>>> y = np.array([[1.0, 0.0, 1.0], [0.0, 0.0, 0.0]])
>>> ndcg_score(y, y)
```


### Expected Results

1.

### Actual Results

0.5

### Versions

```shell
This code was not changed in 1.5, so I guess for newer versions the issue also is actual.



System:
    python: 3.11.8 (main, Feb 12 2024, 14:50:05) [GCC 13.2.1 20230801]
executable: /usr/bin/python3
   machine: Linux-6.6.19-1-MANJARO-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.3.1
          pip: 24.0
   setuptools: 69.0.3
        numpy: 1.26.4
        scipy: 1.10.1
       Cython: 3.0.9
       pandas: 1.5.3
   matplotlib: 3.7.1
       joblib: 1.2.0
threadpoolctl: 3.1.0

Built with OpenMP: True

threadpoolctl info:
       user_api: openmp
   internal_api: openmp
         prefix: libgomp
       filepath: /home/arabella/.local/lib/python3.11/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None
    num_threads: 8

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /home/arabella/.local/lib/python3.11/site-packages/numpy.libs/libopenblas64_p-r0-0cf96a72.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Haswell
    num_threads: 8

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /home/arabella/.local/lib/python3.11/site-packages/scipy.libs/libopenblasp-r0-41284840.3.18.so
        version: 0.3.18
threading_layer: pthreads
   architecture: Haswell
    num_threads: 8
```

COMMENT:
Interesting one. I tried checking the paper and the PR implementing this version (https://github.com/scikit-learn/scikit-learn/pull/9951) and didn't find a clear discussion on what needs to be done.

cc @jeromedockes @jeremiedbb @glemaitre since you were involved in the PR.

Labels: Bug, help wanted
NDCG in case of abscence of relevant items

### Describe the bug

In `sklearn.metrics._ndcg_sample_scores`, there is a counterintuitive handling of the case where all true relevances are equal to zero for some samples. In this case, DCG = 0, IDCG = 0, and the whole NDCG is not defined. In `sklearn` implementation it is defined as 0 and included in the averaged NDCG calculation.  The least leads to strange effects, like `ndcg_score(y,y) != 1`; moreover, it affects the metric value in non-trivial cases too.

In the original 2002 paper where NDCG is proposed, it is not stated how to handle such situations, but it is clearly mentioned that 
```
The (D)CG vectors for each IR technique can be normalized by dividing them
by the corresponding ideal (D)CG vectors, component by component. In this way,
for any vector position, the normalized value 1 represents ideal performance,
and values in the range [0, 1) the share of ideal performance cumulated by each
technique.
```
meaning that NDCG(y,y) must always be 1. 


I suggest excluding observations without relevant items and/or throwing a warning.

### Steps/Code to Reproduce

```
>>> from sklearn.metrics import ndcg_score
>>> y = np.array([[1.0, 0.0, 1.0], [0.0, 0.0, 0.0]])
>>> ndcg_score(y, y)
```


### Expected Results

1.

### Actual Results

0.5

### Versions

```shell
This code was not changed in 1.5, so I guess for newer versions the issue also is actual.



System:
    python: 3.11.8 (main, Feb 12 2024, 14:50:05) [GCC 13.2.1 20230801]
executable: /usr/bin/python3
   machine: Linux-6.6.19-1-MANJARO-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.3.1
          pip: 24.0
   setuptools: 69.0.3
        numpy: 1.26.4
        scipy: 1.10.1
       Cython: 3.0.9
       pandas: 1.5.3
   matplotlib: 3.7.1
       joblib: 1.2.0
threadpoolctl: 3.1.0

Built with OpenMP: True

threadpoolctl info:
       user_api: openmp
   internal_api: openmp
         prefix: libgomp
       filepath: /home/arabella/.local/lib/python3.11/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None
    num_threads: 8

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /home/arabella/.local/lib/python3.11/site-packages/numpy.libs/libopenblas64_p-r0-0cf96a72.3.23.dev.so
        version: 0.3.23.dev
threading_layer: pthreads
   architecture: Haswell
    num_threads: 8

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /home/arabella/.local/lib/python3.11/site-packages/scipy.libs/libopenblasp-r0-41284840.3.18.so
        version: 0.3.18
threading_layer: pthreads
   architecture: Haswell
    num_threads: 8
```

COMMENT:
the ndcg score in this case is 0 / 0 so maybe the output should be NaN? and skip nans when computing the overall score. Otherwise if we don't want NaNs I agree with @arabel1a that 1.0 might be a better choice than the current 0.0

Labels: Bug, help wanted