message does not fit sklearn k-means convergence implementation

Question

In order to re-use the convergence criterion for k-means as implemented in scikit-learn KMeans for my tensorflow-based k-means implementation I need to understand it, but made this observation which I would love to have explained:

KMeans converges with this message:

Iteration 45, inertia 6.993125 center shift 2.610457e-03 within tolerance 8.374284e-06

The implementation in https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/cluster/_k_means.py (line 442ff, function _kmeans_single_lloyd) is as follows:

center_shift_total = squared_norm(centers_old - centers)
if center_shift_total <= tol:
    if verbose:
        print("Converged at iteration %d: "
              "center shift %e within tolerance %e"
              % (i, center_shift_total, tol))
    break

The message should be printed only if the value of center_shift_total is smaller or equal than the value of tolerance. As you can see from the output this is not the case in my run of KMeans (center_shift_total is in fact much larger than tol).

How can this happen (or what am I overlooking)? I noted that the "Converged at iteration" part is missing as well, but the observed message definitely makes no sense to me.

Can you please tell us the version of sklearn by using: print(sklearn.__version__). And also, exactly what version of python you're using. — iliar

iliar iliar · Accepted Answer · 2019-11-22T12:30:20

I found it. Go to the file: _k_means_elkan.pyx line 243 (in 0.23.1). In the master branch it would be line 245.

        if verbose:
            print('Iteration %i, inertia %s'
                    % (iteration, np.sum((X_ - centers_[labels]) ** 2 *
                                         sample_weight[:,np.newaxis])))
        center_shift_total = np.sum(center_shift)
        if center_shift_total ** 2 < tol:
            if verbose:
                print("center shift %e within tolerance %e"
                      % (center_shift_total, tol))
            break

It seems that it's checking the square of center_shift_total. While inside k_means_.py it's checking for center_shift_total without squaring it.

message does not fit sklearn k-means convergence implementation

1 Answers