@@ -226,8 +226,6 @@ def k_means(X, n_clusters, *, sample_weight=None, init='k-means++',
226
226
Relative tolerance with regards to Frobenius norm of the difference
227
227
in the cluster centers of two consecutive iterations to declare
228
228
convergence.
229
- It's not advised to set `tol=0` since convergence might never be
230
- declared due to rounding errors. Use a very small number instead.
231
229
232
230
random_state : int, RandomState instance, default=None
233
231
Determines random number generation for centroid initialization. Use
@@ -358,6 +356,7 @@ def _kmeans_single_elkan(X, sample_weight, centers_init, max_iter=300,
358
356
centers_new = np .zeros_like (centers )
359
357
weight_in_clusters = np .zeros (n_clusters , dtype = X .dtype )
360
358
labels = np .full (n_samples , - 1 , dtype = np .int32 )
359
+ labels_old = labels .copy ()
361
360
center_half_distances = euclidean_distances (centers ) / 2
362
361
distance_next_center = np .partition (np .asarray (center_half_distances ),
363
362
kth = 1 , axis = 0 )[1 ]
@@ -377,6 +376,8 @@ def _kmeans_single_elkan(X, sample_weight, centers_init, max_iter=300,
377
376
init_bounds (X , centers , center_half_distances ,
378
377
labels , upper_bounds , lower_bounds )
379
378
379
+ strict_convergence = False
380
+
380
381
for i in range (max_iter ):
381
382
elkan_iter (X , sample_weight , centers , centers_new ,
382
383
weight_in_clusters , center_half_distances ,
@@ -395,14 +396,24 @@ def _kmeans_single_elkan(X, sample_weight, centers_init, max_iter=300,
395
396
396
397
centers , centers_new = centers_new , centers
397
398
398
- center_shift_tot = ( center_shift ** 2 ). sum ()
399
- if center_shift_tot <= tol :
399
+ if np . array_equal ( labels , labels_old ):
400
+ # First check the labels for strict convergence.
400
401
if verbose :
401
- print (f"Converged at iteration { i } : center shift "
402
- f" { center_shift_tot } within tolerance { tol } ." )
402
+ print (f"Converged at iteration { i } : strict convergence." )
403
+ strict_convergence = True
403
404
break
405
+ else :
406
+ # No strict convergence, check for tol based convergence.
407
+ center_shift_tot = (center_shift ** 2 ).sum ()
408
+ if center_shift_tot <= tol :
409
+ if verbose :
410
+ print (f"Converged at iteration { i } : center shift "
411
+ f"{ center_shift_tot } within tolerance { tol } ." )
412
+ break
404
413
405
- if center_shift_tot > 0 :
414
+ labels_old [:] = labels
415
+
416
+ if not strict_convergence :
406
417
# rerun E-step so that predicted labels match cluster centers
407
418
elkan_iter (X , sample_weight , centers , centers , weight_in_clusters ,
408
419
center_half_distances , distance_next_center ,
@@ -473,6 +484,7 @@ def _kmeans_single_lloyd(X, sample_weight, centers_init, max_iter=300,
473
484
centers = centers_init
474
485
centers_new = np .zeros_like (centers )
475
486
labels = np .full (X .shape [0 ], - 1 , dtype = np .int32 )
487
+ labels_old = labels .copy ()
476
488
weight_in_clusters = np .zeros (n_clusters , dtype = X .dtype )
477
489
center_shift = np .zeros (n_clusters , dtype = X .dtype )
478
490
@@ -483,6 +495,8 @@ def _kmeans_single_lloyd(X, sample_weight, centers_init, max_iter=300,
483
495
lloyd_iter = lloyd_iter_chunked_dense
484
496
_inertia = _inertia_dense
485
497
498
+ strict_convergence = False
499
+
486
500
# Threadpoolctl context to limit the number of threads in second level of
487
501
# nested parallelism (i.e. BLAS) to avoid oversubsciption.
488
502
with threadpool_limits (limits = 1 , user_api = "blas" ):
@@ -496,15 +510,24 @@ def _kmeans_single_lloyd(X, sample_weight, centers_init, max_iter=300,
496
510
497
511
centers , centers_new = centers_new , centers
498
512
499
- center_shift_tot = ( center_shift ** 2 ). sum ()
500
- if center_shift_tot <= tol :
513
+ if np . array_equal ( labels , labels_old ):
514
+ # First check the labels for strict convergence.
501
515
if verbose :
502
- print ("Converged at iteration {0}: "
503
- "center shift {1} within tolerance {2}"
504
- .format (i , center_shift_tot , tol ))
516
+ print (f"Converged at iteration { i } : strict convergence." )
517
+ strict_convergence = True
505
518
break
519
+ else :
520
+ # No strict convergence, check for tol based convergence.
521
+ center_shift_tot = (center_shift ** 2 ).sum ()
522
+ if center_shift_tot <= tol :
523
+ if verbose :
524
+ print (f"Converged at iteration { i } : center shift "
525
+ f"{ center_shift_tot } within tolerance { tol } ." )
526
+ break
527
+
528
+ labels_old [:] = labels
506
529
507
- if center_shift_tot > 0 :
530
+ if not strict_convergence :
508
531
# rerun E-step so that predicted labels match cluster centers
509
532
lloyd_iter (X , sample_weight , x_squared_norms , centers , centers ,
510
533
weight_in_clusters , labels , center_shift , n_threads ,
@@ -617,8 +640,6 @@ class KMeans(TransformerMixin, ClusterMixin, BaseEstimator):
617
640
Relative tolerance with regards to Frobenius norm of the difference
618
641
in the cluster centers of two consecutive iterations to declare
619
642
convergence.
620
- It's not advised to set `tol=0` since convergence might never be
621
- declared due to rounding errors. Use a very small number instead.
622
643
623
644
precompute_distances : {'auto', True, False}, default='auto'
624
645
Precompute distances (faster but takes more memory).
0 commit comments