Repository: scikit-learn/scikit-learn
Pull request: Fix low level crash in BisectingKMeans.predict on rescaled data
Fixes #27081.

I will first open this PR with the non-regression test that should hopefully make the macOS Intel CI workers segfault (for some reason, this bug seems to stay silent on other platforms)...

Then I will push a fix for the underlying root cause.

Problem statement:
BisectingKMeans floating point exception fatal error on OSX
### Describe the bug

Hi, thanks for this fantastic library 🚀 🎉 

I believe I found a bug. In the BisectingKMeans clustering, the `predict` function cannot be used when the to-be-predicted-data is on a different numerical scale than the fitted data. Other clustering methods like e.g., KMeans dont have this problem.

In the example below, I fitted the BisectingKMeans on random data and then multiplied the data that should be predicted by 50. It causes a floating point exception error which is pretty bad because python silently exits.

### Steps/Code to Reproduce

```py
from sklearn.cluster import BisectingKMeans, KMeans
import numpy as np
x = np.random.rand(3000, 10)

bisect_means = BisectingKMeans(n_clusters=10).fit(x)

labels = bisect_means.predict(50*np.random.rand(100, 10))
print(labels)
```

### Expected Results

A list of predicted class labels

### Actual Results

Python silently exits with:
```
[1]    45074 floating point exception  python foo.py
```
In Jupyter/ipython the kernel simply dies.

### Versions

```shell
System:
    python: 3.9.16 (main, Mar  8 2023, 04:29:44)  [Clang 14.0.6 ]
executable: /Users/jab/miniconda3/envs/qondot/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.0.1
   setuptools: 67.8.0
        numpy: 1.21.6
        scipy: 1.10.1
       Cython: 0.29.35
       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: libomp
       filepath: /Users/jab/miniconda3/envs/qondot/lib/python3.9/site-packages/sklearn/.dylibs/libomp.dylib
        version: None
    num_threads: 8

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /Users/jab/miniconda3/envs/qondot/lib/python3.9/site-packages/numpy/.dylibs/libopenblas.0.dylib
        version: 0.3.17
threading_layer: pthreads
   architecture: Haswell
    num_threads: 4

       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /Users/jab/miniconda3/envs/qondot/lib/python3.9/site-packages/scipy/.dylibs/libopenblas.0.dylib
        version: 0.3.18
threading_layer: pthreads
   architecture: SkylakeX
    num_threads: 4
```

Hints from issue discussion:
This is unexpected and is likely to be something specific to your machine being a MacOS or your environment.

One thing I noticed in your versions is that you have a different OpenBLAS version from numpy and scipy. Could it be the issue, hard to tell.

Could you follow the instructions from https://github.com/scikit-learn/scikit-learn/issues/23574#issuecomment-1248963822 and report back.

The issue persists, even in a new test env, created as described in: https://github.com/scikit-learn/scikit-learn/issues/23574#issuecomment-1248963822

I do not have a M1 Mac!
I tried debugging with `gdb` but I cant get it do work (the thread always keeps pending but this also happens when I "debug" a dummy hello-world file, so it's an unrelated issue with gdb)

Output of `conda list` is below, maybe you can test whether you observe the same behavior @lesteve ?

```txt
# packages in environment at /Users/jab/miniconda3/envs/qondot:
#
# Name                    Version                   Build  Channel
absl-py                   1.4.0                    pypi_0    pypi
adjusttext                0.8                      pypi_0    pypi
aiohttp                   3.8.4                    pypi_0    pypi
aiosignal                 1.3.1                    pypi_0    pypi
anndata                   0.9.1                    pypi_0    pypi
anyio                     3.7.0                    pypi_0    pypi
appnope                   0.1.3                    pypi_0    pypi
argon2-cffi               21.3.0                   pypi_0    pypi
argon2-cffi-bindings      21.2.0                   pypi_0    pypi
arrow                     1.2.3                    pypi_0    pypi
asttokens                 2.2.1                    pypi_0    pypi
async-timeout             4.0.2                    pypi_0    pypi
attrs                     23.1.0                   pypi_0    pypi
backcall                  0.2.0                    pypi_0    pypi
beautifulsoup4            4.12.2                   pypi_0    pypi
black                     23.7.0                   pypi_0    pypi
bleach                    6.0.0                    pypi_0    pypi
blosc2                    2.0.0                    pypi_0    pypi
build                     0.10.0                   pypi_0    pypi
ca-certificates           2023.01.10           hecd8cb5_0  
cachecontrol              0.12.11                  pypi_0    pypi
cached-property           1.5.2                    pypi_0    pypi
certifi                   2023.5.7                 pypi_0    pypi
cffi                      1.15.1                   pypi_0    pypi
cfgv                      3.3.1                    pypi_0    pypi
charset-normalizer        3.1.0                    pypi_0    pypi
chex                      0.1.7                    pypi_0    pypi
cleo                      2.0.1                    pypi_0    pypi
click                     8.1.6                    pypi_0    pypi
comm                      0.1.3                    pypi_0    pypi
condot                    1.0                       dev_0    <develop>
contextlib2               21.6.0                   pypi_0    pypi
contourpy                 1.0.7                    pypi_0    pypi
cpa-tools                 0.3.4                    pypi_0    pypi
crashtest                 0.4.1                    pypi_0    pypi
cryptography              41.0.0                   pypi_0    pypi
cvxpy                     1.3.1                    pypi_0    pypi
cycler                    0.11.0                   pypi_0    pypi
cython                    0.29.35                  pypi_0    pypi
dcor                      0.6                      pypi_0    pypi
debugpy                   1.6.7                    pypi_0    pypi
decorator                 5.1.1                    pypi_0    pypi
defusedxml                0.7.1                    pypi_0    pypi
dill                      0.3.6                    pypi_0    pypi
distlib                   0.3.6                    pypi_0    pypi
dm-tree                   0.1.8                    pypi_0    pypi
docrep                    0.3.2                    pypi_0    pypi
dulwich                   0.21.5                   pypi_0    pypi
dunamai                   1.17.0                   pypi_0    pypi
ecos                      2.0.12                   pypi_0    pypi
equinox                   0.10.10                  pypi_0    pypi
et-xmlfile                1.1.0                    pypi_0    pypi
etils                     1.3.0                    pypi_0    pypi
exceptiongroup            1.1.1                    pypi_0    pypi
executing                 1.2.0                    pypi_0    pypi
fastjsonschema            2.17.1                   pypi_0    pypi
fdasrsf                   2.4.2                    pypi_0    pypi
filelock                  3.12.0                   pypi_0    pypi
findiff                   0.10.0                   pypi_0    pypi
flake8                    6.0.0                    pypi_0    pypi
flax                      0.6.10                   pypi_0    pypi
fonttools                 4.39.4                   pypi_0    pypi
fqdn                      1.5.1                    pypi_0    pypi
frozenlist                1.3.3                    pypi_0    pypi
fsspec                    2023.5.0                 pypi_0    pypi
geomloss                  0.2.6                    pypi_0    pypi
get-version               3.5.4                    pypi_0    pypi
gitdb                     4.0.10                   pypi_0    pypi
gitpython                 3.1.32                   pypi_0    pypi
h5py                      3.8.0                    pypi_0    pypi
html5lib                  1.1                      pypi_0    pypi
identify                  2.5.26                   pypi_0    pypi
idna                      3.4                      pypi_0    pypi
importlib-metadata        6.6.0                    pypi_0    pypi
importlib-resources       5.12.0                   pypi_0    pypi
iniconfig                 2.0.0                    pypi_0    pypi
installer                 0.7.0                    pypi_0    pypi
ipykernel                 6.23.1                   pypi_0    pypi
ipython                   8.13.2                   pypi_0    pypi
ipython-genutils          0.2.0                    pypi_0    pypi
ipywidgets                8.0.6                    pypi_0    pypi
isoduration               20.11.0                  pypi_0    pypi
isort                     5.12.0                   pypi_0    pypi
jaraco-classes            3.2.3                    pypi_0    pypi
jax                       0.4.13                   pypi_0    pypi
jaxlib                    0.4.13                   pypi_0    pypi
jaxopt                    0.7                      pypi_0    pypi
jaxtyping                 0.2.20                   pypi_0    pypi
jedi                      0.18.2                   pypi_0    pypi
jinja2                    3.1.2                    pypi_0    pypi
joblib                    1.2.0                    pypi_0    pypi
jsonpointer               2.3                      pypi_0    pypi
jsonschema                4.17.3                   pypi_0    pypi
jupyter                   1.0.0                    pypi_0    pypi
jupyter-client            8.2.0                    pypi_0    pypi
jupyter-console           6.6.3                    pypi_0    pypi
jupyter-core              5.3.0                    pypi_0    pypi
jupyter-events            0.6.3                    pypi_0    pypi
jupyter-server            2.6.0                    pypi_0    pypi
jupyter-server-terminals  0.4.4                    pypi_0    pypi
jupyterlab-pygments       0.2.2                    pypi_0    pypi
jupyterlab-widgets        3.0.7                    pypi_0    pypi
keyring                   23.13.1                  pypi_0    pypi
kiwisolver                1.4.4                    pypi_0    pypi
lazy-loader               0.3                      pypi_0    pypi
legacy-api-wrap           1.2                      pypi_0    pypi
libcxx                    14.0.6               h9765a3e_0  
libffi                    3.4.4                hecd8cb5_0  
lightning-utilities       0.8.0                    pypi_0    pypi
lineax                    0.0.1                    pypi_0    pypi
llvmlite                  0.38.1                   pypi_0    pypi
lockfile                  0.12.2                   pypi_0    pypi
markdown-it-py            2.2.0                    pypi_0    pypi
markupsafe                2.1.2                    pypi_0    pypi
matplotlib                3.7.1                    pypi_0    pypi
matplotlib-inline         0.1.6                    pypi_0    pypi
mccabe                    0.7.0                    pypi_0    pypi
mdurl                     0.1.2                    pypi_0    pypi
mistune                   2.0.5                    pypi_0    pypi
ml-collections            0.1.1                    pypi_0    pypi
ml-dtypes                 0.1.0                    pypi_0    pypi
more-itertools            9.1.0                    pypi_0    pypi
mpmath                    1.3.0                    pypi_0    pypi
msgpack                   1.0.5                    pypi_0    pypi
mudata                    0.2.2                    pypi_0    pypi
multidict                 6.0.4                    pypi_0    pypi
multimethod               1.9.1                    pypi_0    pypi
multipledispatch          0.6.0                    pypi_0    pypi
mypy                      1.4.1                    pypi_0    pypi
mypy-extensions           1.0.0                    pypi_0    pypi
natsort                   8.3.1                    pypi_0    pypi
nbclassic                 1.0.0                    pypi_0    pypi
nbclient                  0.8.0                    pypi_0    pypi
nbconvert                 7.4.0                    pypi_0    pypi
nbformat                  5.8.0                    pypi_0    pypi
ncurses                   6.4                  hcec6c5f_0  
nest-asyncio              1.5.6                    pypi_0    pypi
networkx                  3.1                      pypi_0    pypi
nodeenv                   1.8.0                    pypi_0    pypi
notebook                  6.5.4                    pypi_0    pypi
notebook-shim             0.2.3                    pypi_0    pypi
ntlm-auth                 1.5.0                    pypi_0    pypi
numba                     0.55.0                   pypi_0    pypi
numexpr                   2.8.4                    pypi_0    pypi
numpy                     1.21.6                   pypi_0    pypi
numpyro                   0.11.0                   pypi_0    pypi
openpyxl                  3.1.2                    pypi_0    pypi
openssl                   1.1.1t               hca72f7f_0  
opt-einsum                3.3.0                    pypi_0    pypi
optax                     0.1.5                    pypi_0    pypi
orbax-checkpoint          0.2.3                    pypi_0    pypi
osqp                      0.6.3                    pypi_0    pypi
ott-jax                   0.2.11                   pypi_0    pypi
overrides                 7.3.1                    pypi_0    pypi
packaging                 23.1                     pypi_0    pypi
pandas                    1.5.3                    pypi_0    pypi
pandocfilters             1.5.0                    pypi_0    pypi
parso                     0.8.3                    pypi_0    pypi
pathspec                  0.11.1                   pypi_0    pypi
patsy                     0.5.3                    pypi_0    pypi
pbr                       5.11.1                   pypi_0    pypi
pexpect                   4.8.0                    pypi_0    pypi
pickleshare               0.7.5                    pypi_0    pypi
pillow                    9.5.0                    pypi_0    pypi
pip                       23.0.1           py39hecd8cb5_0  
pkginfo                   1.9.6                    pypi_0    pypi
platformdirs              3.5.1                    pypi_0    pypi
pluggy                    1.2.0                    pypi_0    pypi
ply                       3.11                     pypi_0    pypi
poetry                    1.5.1                    pypi_0    pypi
poetry-core               1.6.1                    pypi_0    pypi
poetry-plugin-export      1.4.0                    pypi_0    pypi
pot                       0.9.0                    pypi_0    pypi
pre-commit                3.3.3                    pypi_0    pypi
prometheus-client         0.17.0                   pypi_0    pypi
prompt-toolkit            3.0.38                   pypi_0    pypi
psutil                    5.9.5                    pypi_0    pypi
ptyprocess                0.7.0                    pypi_0    pypi
pure-eval                 0.2.2                    pypi_0    pypi
py-cpuinfo                9.0.0                    pypi_0    pypi
pycodestyle               2.10.0                   pypi_0    pypi
pycparser                 2.21                     pypi_0    pypi
pyflakes                  3.0.1                    pypi_0    pypi
pygments                  2.15.1                   pypi_0    pypi
pynndescent               0.5.10                   pypi_0    pypi
pyparsing                 3.0.9                    pypi_0    pypi
pyproject-hooks           1.0.0                    pypi_0    pypi
pyro-api                  0.1.2                    pypi_0    pypi
pyro-ppl                  1.8.5                    pypi_0    pypi
pyrsistent                0.19.3                   pypi_0    pypi
pytest                    7.4.0                    pypi_0    pypi
python                    3.9.16               h218abb5_2  
python-dateutil           2.8.2                    pypi_0    pypi
python-json-logger        2.0.7                    pypi_0    pypi
pytorch-lightning         1.9.5                    pypi_0    pypi
pytz                      2023.3                   pypi_0    pypi
pyyaml                    6.0                      pypi_0    pypi
pyzmq                     25.1.0                   pypi_0    pypi
qdldl                     0.1.7                    pypi_0    pypi
qiskit                    0.43.0                   pypi_0    pypi
qiskit-aer                0.12.0                   pypi_0    pypi
qiskit-ibmq-provider      0.20.2                   pypi_0    pypi
qiskit-terra              0.24.0                   pypi_0    pypi
qondot                    0.0.1                    pypi_0    pypi
qtconsole                 5.4.3                    pypi_0    pypi
qtpy                      2.3.1                    pypi_0    pypi
rapidfuzz                 2.15.1                   pypi_0    pypi
rdata                     0.9                      pypi_0    pypi
readline                  8.2                  hca72f7f_0  
requests                  2.31.0                   pypi_0    pypi
requests-ntlm             1.1.0                    pypi_0    pypi
requests-toolbelt         1.0.0                    pypi_0    pypi
rfc3339-validator         0.1.4                    pypi_0    pypi
rfc3986-validator         0.1.1                    pypi_0    pypi
rich                      13.3.5                   pypi_0    pypi
ruff                      0.0.280                  pypi_0    pypi
rustworkx                 0.12.1                   pypi_0    pypi
scanpy                    1.9.3                    pypi_0    pypi
scikit-datasets           0.2.4                    pypi_0    pypi
scikit-fda                0.8.1                    pypi_0    pypi
scikit-fuzzy              0.4.2                    pypi_0    pypi
scikit-learn              1.3.0                    pypi_0    pypi
scipy                     1.10.1                   pypi_0    pypi
scs                       3.2.3                    pypi_0    pypi
scvi-tools                0.20.3                   pypi_0    pypi
seaborn                   0.11.2                   pypi_0    pypi
send2trash                1.8.2                    pypi_0    pypi
session-info              1.0.0                    pypi_0    pypi
setuptools                67.8.0           py39hecd8cb5_0  
setuptools-scm            7.1.0                    pypi_0    pypi
shellingham               1.5.0.post1              pypi_0    pypi
sinfo                     0.3.4                    pypi_0    pypi
six                       1.16.0                   pypi_0    pypi
smmap                     5.0.0                    pypi_0    pypi
sniffio                   1.3.0                    pypi_0    pypi
soupsieve                 2.4.1                    pypi_0    pypi
sqlite                    3.41.2               h6c40b1e_0  
stack-data                0.6.2                    pypi_0    pypi
statsmodels               0.14.0                   pypi_0    pypi
stdlib-list               0.8.0                    pypi_0    pypi
stevedore                 5.1.0                    pypi_0    pypi
symengine                 0.9.2                    pypi_0    pypi
sympy                     1.12                     pypi_0    pypi
tables                    3.8.0                    pypi_0    pypi
tensorstore               0.1.37                   pypi_0    pypi
terminado                 0.17.1                   pypi_0    pypi
threadpoolctl             3.1.0                    pypi_0    pypi
tinycss2                  1.2.1                    pypi_0    pypi
tk                        8.6.12               h5d9f67b_0  
tomli                     2.0.1                    pypi_0    pypi
tomlkit                   0.11.8                   pypi_0    pypi
toolz                     0.12.0                   pypi_0    pypi
torch                     2.0.1                    pypi_0    pypi
torchmetrics              0.11.4                   pypi_0    pypi
tornado                   6.3.2                    pypi_0    pypi
tqdm                      4.65.0                   pypi_0    pypi
traitlets                 5.9.0                    pypi_0    pypi
trove-classifiers         2023.5.24                pypi_0    pypi
typeguard                 4.0.0                    pypi_0    pypi
typing-extensions         4.6.2                    pypi_0    pypi
tzdata                    2023.3                   pypi_0    pypi
umap-learn                0.5.3                    pypi_0    pypi
uri-template              1.2.0                    pypi_0    pypi
urllib3                   1.26.16                  pypi_0    pypi
virtualenv                20.23.0                  pypi_0    pypi
wasserstein               1.1.0                    pypi_0    pypi
wcwidth                   0.2.6                    pypi_0    pypi
webcolors                 1.13                     pypi_0    pypi
webencodings              0.5.1                    pypi_0    pypi
websocket-client          1.5.2                    pypi_0    pypi
websockets                11.0.3                   pypi_0    pypi
wheel                     0.38.4           py39hecd8cb5_0  
widgetsnbextension        4.0.7                    pypi_0    pypi
wurlitzer                 3.0.3                    pypi_0    pypi
xarray                    2023.7.0                 pypi_0    pypi
xattr                     0.10.1                   pypi_0    pypi
xz                        5.4.2                h6c40b1e_0  
yarl                      1.9.2                    pypi_0    pypi
zipp                      3.15.0                   pypi_0    pypi
zlib                      1.2.13               h4dc903c_0  
```
Thanks a lot for the additional info!

> I do not have a M1 Mac!

Another person in the linked issue seemed to have an Intel MacOS as well https://github.com/scikit-learn/scikit-learn/issues/23574#issuecomment-1152275688 so it looks like this is not only related to M1 Mac.

I would suggest trying to create a new conda environment from scratch using conda-forge and only install scikit-learn to see if the issue persists.

https://github.com/scikit-learn/scikit-learn/issues/23574#issuecomment-1584584081 hints that it could be linked to OpenMP and PyTorch.

> Output of conda list is below, maybe you can test whether you observe the same behavior @lesteve ?

Sorry I should have been explicit: on my Linux machine I can't reproduce the issue.

I tried again on a different Intel Mac, from an entirely different environment from a different person. The same problem occurs. 

I had a closer look, the error occurs in `BisectingKMeans._predict_recursive`, traces down to `_labels_inertia` and then `lloyd_iter_chunked_dense` inside `sklearn.cluster._kmeans`.  The last one is a binary (`_k_means_lloyd.cpython-311-darwin.so*`) so I cant trace the error any further.

I'd appreciate any steps on what to do? Can I pin openblas somehow to a safe version? Maybe an active developer with MacOS access can confirm this issue is real and not just an installation problem. It seems a consistent problem across two machines with a total of 3 envs, all build in separate ways.

The `test-env` has slightly different specs from what I reported above it uses Python 3.11, newer versions of pip, numpy, scipy and openblas:

```txt

System:
    python: 3.11.4 | packaged by conda-forge | (main, Jun 10 2023, 18:10:28) [Clang 15.0.7 ]
executable: /Users/jab/miniconda3/envs/test-env/bin/python
   machine: macOS-13.3.1-x86_64-i386-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.2.1
   setuptools: 68.0.0
        numpy: 1.25.2
        scipy: 1.11.1
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /Users/jab/miniconda3/envs/test-env/lib/libopenblasp-r0.3.23.dylib
        version: 0.3.23
threading_layer: openmp
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 8
         prefix: libomp
       filepath: /Users/jab/miniconda3/envs/test-env/lib/libomp.dylib
        version: None
```


Could you please try to reproduce by installing everything (numpy / scipy / scikit-learn / openblas) from conda-forge?

```
conda create -n debug-env -c conda-forge scikit-learn
conda activate debug-env
python repro_script.py
```

if you can reproduce their, I would also be interested in the output of `conda list` and `sklearn.show_versions()`.

EDIT: added the missing `-c conda-forge`.
Thanks @ogrisel for the suggestion. Yes, I can also reproduce it in this case.

Outputs:
```txt

System:
    python: 3.11.4 (main, Jul  5 2023, 08:41:25) [Clang 14.0.6 ]
executable: /Users/jab/miniconda3/envs/debug-env/bin/python
   machine: macOS-10.16-x86_64-i386-64bit

Python dependencies:
      sklearn: 1.3.0
          pip: 23.2.1
   setuptools: 68.0.0
        numpy: 1.24.3
        scipy: 1.11.1
       Cython: None
       pandas: None
   matplotlib: None
       joblib: 1.2.0
threadpoolctl: 2.2.0

Built with OpenMP: True

threadpoolctl info:
       filepath: /Users/jab/miniconda3/envs/debug-env/lib/libopenblasp-r0.3.21.dylib
         prefix: libopenblas
       user_api: blas
   internal_api: openblas
        version: 0.3.21
    num_threads: 4
threading_layer: pthreads
   architecture: Haswell

       filepath: /Users/jab/miniconda3/envs/debug-env/lib/libomp.dylib
         prefix: libomp
       user_api: openmp
   internal_api: openmp
        version: None
    num_threads: 8
```

`conda list` gives:
```txt
# packages in environment at /Users/jab/miniconda3/envs/debug-env:
#
# Name                    Version                   Build  Channel
blas                      1.0                    openblas
bzip2                     1.0.8                h1de35cc_0
ca-certificates           2023.05.30           hecd8cb5_0
joblib                    1.2.0           py311hecd8cb5_0
libcxx                    14.0.6               h9765a3e_0
libffi                    3.4.4                hecd8cb5_0
libgfortran               5.0.0           11_3_0_hecd8cb5_28
libgfortran5              11.3.0              h9dfd629_28
libopenblas               0.3.21               h54e7dc3_0
llvm-openmp               14.0.6               h0dcd299_0
ncurses                   6.4                  hcec6c5f_0
numpy                     1.24.3          py311hd0e4f0d_0
numpy-base                1.24.3          py311h947b413_0
openssl                   3.0.10               hca72f7f_2
pip                       23.2.1          py311hecd8cb5_0
python                    3.11.4               hf27a42d_0
readline                  8.2                  hca72f7f_0
scikit-learn              1.3.0           py311hdb55bb0_0
scipy                     1.11.1          py311h7695dc5_0
setuptools                68.0.0          py311hecd8cb5_0
sqlite                    3.41.2               h6c40b1e_0
threadpoolctl             2.2.0              pyh0d69192_0
tk                        8.6.12               h5d9f67b_0
tzdata                    2023c                h04d1e81_0
wheel                     0.38.4          py311hecd8cb5_0
xz                        5.4.2                h6c40b1e_0
zlib                      1.2.13               h4dc903c_0
```
Thanks. This is really strange. I am also on a mac, albeit M1,  and I cannot reproduce, neither when install from conda-forge or pypi.org...
Have you tried increasing the scaling factor to a higher number?

My example uses `50`:
```py
labels = bisect_means.predict(50*np.random.rand(100, 10))
```

When I set it to 5, the error occurs only sometimes, so generally higher values seem more problematic.
I noticed that I forgot the `-c conda-forge` in the env creation command of https://github.com/scikit-learn/scikit-learn/issues/27081#issuecomment-1693287454. Can you please try again? The conda list output shows you are using everything from the anaconda defaults channel.
I cannot reproduce even with very large scales:

```python
>>> import numpy as np
>>> x = np.random.rand(3000, 10)
>>> 
>>> bisect_means = BisectingKMeans(n_clusters=10).fit(x)
>>> 
>>> labels = bisect_means.predict(50*np.random.rand(100, 10))
>>> print(labels)
[9 9 3 3 3 3 0 3 4 3 9 3 9 9 3 3 9 3 9 1 3 8 0 3 1 9 3 3 3 3 3 3 3 3 3 9 3
 9 3 3 3 1 3 3 3 3 3 4 3 3 9 3 3 3 3 4 3 9 9 4 1 4 9 9 3 3 3 9 3 9 3 4 9 3
 3 4 9 3 3 3 3 3 3 3 9 4 9 3 3 3 3 3 3 9 9 4 9 3 3 3]
>>> 
>>> labels = bisect_means.predict(5000*np.random.rand(100, 10))
>>> print(labels)
[3 3 9 3 4 3 3 3 3 4 3 3 3 4 9 4 3 9 3 3 1 3 3 4 3 9 3 3 3 9 9 3 3 3 3 3 3
 9 9 3 9 3 3 9 9 3 3 3 9 4 3 4 3 9 3 3 3 3 3 3 3 3 3 9 3 3 3 3 3 3 0 4 3 3
 3 3 3 9 9 3 3 3 9 3 3 4 9 9 3 3 9 3 9 3 3 3 3 3 3 3]
```

Commit message: DOC update changelog

Patch to review:
diff --git a/doc/whats_new/v1.3.rst b/doc/whats_new/v1.3.rst
index d97ccea9469eb..05e9584028647 100644
--- a/doc/whats_new/v1.3.rst
+++ b/doc/whats_new/v1.3.rst
@@ -18,6 +18,13 @@ Changes impacting all modules
 Changelog
 ---------
 
+:mod:`sklearn.cluster`
+......................
+
+- |Fix| :class:`cluster.BisectingKMeans` could crash when predicting on data
+  with a different scale than the data used to fit the model.
+  :pr:`27167` by `Olivier Grisel`_.
+
 :mod:`sklearn.impute`
 .....................
 
diff --git a/sklearn/cluster/_bisect_k_means.py b/sklearn/cluster/_bisect_k_means.py
index 9091445261f70..1209300e511cb 100644
--- a/sklearn/cluster/_bisect_k_means.py
+++ b/sklearn/cluster/_bisect_k_means.py
@@ -508,18 +508,25 @@ def _predict_recursive(self, X, sample_weight, cluster_node):
             self._n_threads,
             return_inertia=False,
         )
-        mask = cluster_labels == 0
+        first_cluster_mask = cluster_labels == 0
 
         # Compute the labels for each subset of the data points.
         labels = np.full(X.shape[0], -1, dtype=np.int32)
 
-        labels[mask] = self._predict_recursive(
-            X[mask], sample_weight[mask], cluster_node.left
-        )
+        if first_cluster_mask.any():
+            labels[first_cluster_mask] = self._predict_recursive(
+                X[first_cluster_mask],
+                sample_weight[first_cluster_mask],
+                cluster_node.left,
+            )
 
-        labels[~mask] = self._predict_recursive(
-            X[~mask], sample_weight[~mask], cluster_node.right
-        )
+        other_cluster_mask = ~first_cluster_mask
+        if other_cluster_mask.any():
+            labels[other_cluster_mask] = self._predict_recursive(
+                X[other_cluster_mask],
+                sample_weight[other_cluster_mask],
+                cluster_node.right,
+            )
 
         return labels
 
diff --git a/sklearn/cluster/_k_means_lloyd.pyx b/sklearn/cluster/_k_means_lloyd.pyx
index 664ec0da2cea2..5e7073a6dba37 100644
--- a/sklearn/cluster/_k_means_lloyd.pyx
+++ b/sklearn/cluster/_k_means_lloyd.pyx
@@ -82,6 +82,13 @@ def lloyd_iter_chunked_dense(
         int n_features = X.shape[1]
         int n_clusters = centers_old.shape[0]
 
+    if n_samples == 0:
+        # An empty array was passed, avoid divide-by-zero error later. It's
+        # useless to call this function this way, but let's avoid low level
+        # errors in case there is a bug in the calling Python code.
+        return
+
+    cdef:
         # hard-coded number of samples per chunk. Appeared to be close to
         # optimal in all situations.
         int n_samples_chunk = CHUNK_SIZE if n_samples > CHUNK_SIZE else n_samples
@@ -267,12 +274,18 @@ def lloyd_iter_chunked_sparse(
           the algorithm. This is useful especially when calling predict on a
           fitted model.
     """
-    # print(X.indices.dtype)
     cdef:
         int n_samples = X.shape[0]
         int n_features = X.shape[1]
         int n_clusters = centers_old.shape[0]
 
+    if n_samples == 0:
+        # An empty array was passed, avoid divide-by-zero error later. It's
+        # useless to call this function this way, but let's avoid low level
+        # errors in case there is a bug in the calling Python code.
+        return
+
+    cdef:
         # Choose same as for dense. Does not have the same impact since with
         # sparse data the pairwise distances matrix is not precomputed.
         # However, splitting in chunks is necessary to get parallelism.
diff --git a/sklearn/cluster/tests/test_bisect_k_means.py b/sklearn/cluster/tests/test_bisect_k_means.py
index f6fb785a076d4..701d6991e038a 100644
--- a/sklearn/cluster/tests/test_bisect_k_means.py
+++ b/sklearn/cluster/tests/test_bisect_k_means.py
@@ -133,3 +133,17 @@ def test_float32_float64_equivalence(csr_container):
 
     assert_allclose(km32.cluster_centers_, km64.cluster_centers_)
     assert_array_equal(km32.labels_, km64.labels_)
+
+
+def test_non_regression_segfault_on_empty_bisections():
+    # Non-regression test for:
+    # https://github.com/scikit-learn/scikit-learn/issues/27081
+    rng = np.random.RandomState(0)
+    X_train = rng.rand(3000, 10)
+    bkm = BisectingKMeans(n_clusters=10).fit(X_train)
+
+    # predict on scaled data to trigger pathologic case
+    # where the inner mask leads to empty bisections.
+    X_test = 50 * rng.rand(100, 10)
+    labels = bkm.predict(X_test)  # should not segfault
+    assert np.isin(np.unique(labels), np.arange(10)).all()


Code review comments:
diff_hunk: @@ -133,3 +133,17 @@ def test_float32_float64_equivalence(csr_container):
 
     assert_allclose(km32.cluster_centers_, km64.cluster_centers_)
     assert_array_equal(km32.labels_, km64.labels_)
+
+
+def test_non_regression_segfault_on_empty_bisections():
path: sklearn/cluster/tests/test_bisect_k_means.py
text: @author:
Better name for the test.

```suggestion
def test_no_crash_on_empty_bisections():
```

Let's wait for the current CI run to complete before merging this suggestion.

diff_hunk: @@ -267,12 +274,18 @@ def lloyd_iter_chunked_sparse(
           the algorithm. This is useful especially when calling predict on a
           fitted model.
     """
-    # print(X.indices.dtype)
     cdef:
         int n_samples = X.shape[0]
         int n_features = X.shape[1]
         int n_clusters = centers_old.shape[0]
 
+    if n_samples == 0:
+        # An empty array was passed, avoid divide-by-zero error later. It's
+        # useless to call this function this way, but let's avoid low level
+        # errors in case there is a bug in the calling Python code.
+        return
path: sklearn/cluster/_k_means_lloyd.pyx
text: @user1:
I think we also port this change to `elkan_iter_chunked_sparse`.

diff_hunk: @@ -133,3 +133,17 @@ def test_float32_float64_equivalence(csr_container):
 
     assert_allclose(km32.cluster_centers_, km64.cluster_centers_)
     assert_array_equal(km32.labels_, km64.labels_)
+
+
+def test_non_regression_segfault_on_empty_bisections():
+    # Non-regression test for:
+    # https://github.com/scikit-learn/scikit-learn/issues/27081
+    rng = np.random.RandomState(0)
+    X_train = rng.rand(3000, 10)
+    bkm = BisectingKMeans(n_clusters=10).fit(X_train)
path: sklearn/cluster/tests/test_bisect_k_means.py
text: @user2:
To also test for `algorithm="elkan"`, taking https://github.com/scikit-learn/scikit-learn/pull/27167/files#r1305929679 into account:
```suggestion
@user1.mark.parametrize("algorithm", ("lloyd", "elkan")):
def test_no_crash_on_empty_bisections(algorithm):
    # Non-regression test for:
    # https://github.com/scikit-learn/scikit-learn/issues/27081
    rng = np.random.RandomState(0)
    X_train = rng.rand(3000, 10)
    bkm = BisectingKMeans(n_clusters=10, algorithm=algorithm).fit(X_train)
```

diff_hunk: @@ -82,6 +82,13 @@ def lloyd_iter_chunked_dense(
         int n_features = X.shape[1]
         int n_clusters = centers_old.shape[0]
 
+    if n_samples == 0:
+        # An empty array was passed, avoid divide-by-zero error later. It's
+        # useless to call this function this way, but let's avoid low level
+        # errors in case there is a bug in the calling Python code.
+        return
path: sklearn/cluster/_k_means_lloyd.pyx
text: @user1:
I think we also port this change to `elkan_iter_chunked_dense`.