scikit-learn
diff --git a/‎doc/whats_new/v1.2.rst
Copy file name to clipboardExpand all lines: doc/whats_new/v1.2.rst
+7Lines changed: 7 additions & 0 deletions b/‎doc/whats_new/v1.2.rst
Copy file name to clipboardExpand all lines: doc/whats_new/v1.2.rst
+7Lines changed: 7 additions & 0 deletions
diff --git a/‎sklearn/cluster/_bisect_k_means.py
Copy file name to clipboardExpand all lines: sklearn/cluster/_bisect_k_means.py
+3-1Lines changed: 3 additions & 1 deletion b/‎sklearn/cluster/_bisect_k_means.py
Copy file name to clipboardExpand all lines: sklearn/cluster/_bisect_k_means.py
+3-1Lines changed: 3 additions & 1 deletion
@@ -27,6 +27,13 @@ Changes impacting all modules
 Changelog
 ---------
 
+:mod:`sklearn.cluster`
+......................
+
+- |Fix| Fixed a bug in :class:`cluster.BisectingKMeans`, preventing `fit` to randomly
+  fail due to a permutation of the labels when running multiple inits.
+  :pr:`25563` by :user:`Jérémie du Boisberranger <jeremiedbb>`.
+
 :mod:`sklearn.isotonic`
 .......................
 
 
@@ -337,7 +337,9 @@ def _bisect(self, X, x_squared_norms, sample_weight, cluster_to_bisect):
                 X, best_centers, best_labels, sample_weight
             )
         else:  # bisecting_strategy == "largest_cluster"
-            scores = np.bincount(best_labels)
+            # Using minlength to make sure that we have the counts for both labels even
+            # if all samples are labelled 0.
+            scores = np.bincount(best_labels, minlength=2)
 
         cluster_to_bisect.split(best_labels, best_centers, scores)