K-Means: report fewer-than-requested distinct centroids via train_result instead of silently returning #3770

Summary

K-Means should be able to tell the caller that it returned fewer than cluster_count distinct centroids. scikit-learn raises a ConvergenceWarning in this situation; oneDAL currently returns the result silently.

This came out of the review of #3742 (thread). Filing it separately because it is a public API addition, not a local fix.

Background

Before #3742, the CPU kernels raised ErrorKMeansNumberOfClustersIsTooLarge from inside the Lloyd iteration when an empty cluster could not be relocated. That check is gone: "fewer distinct rows than clusters" is a ConvergenceWarning case in scikit-learn, not an error, and it now has a well-defined result — every empty cluster is filled with a duplicate of the centroid of the cluster holding the most observations.

That makes the numbers usable, but it also means the degenerate case is no longer distinguishable from a normal one without inspecting the result.

cluster_count > row_count is still rejected up front (detail/train_ops.hpp, kmeans_input_types.cpp), so this is only about the "enough rows, not enough distinct rows" case.

Proposal

Add a flag to the result object rather than raising:

• oneDAL interface: a new field on kmeans::train_result (e.g. get_converged() / a "distinct centroid count" accessor).
• DAAL interface: the equivalent entry in the K-Means result tables.

Both are additive but require a spec change and a version bump, hence targeting the next major release.

The value is free to produce: the pass-3 branch that fills an empty cluster with a duplicate centroid already knows the answer, on all four backends.

Interim mitigation

The condition is derivable from the responses: len(set(labels)) < n_clusters. That is exactly what scikit-learn itself does, unconditionally on every fit (sklearn/cluster/_kmeans.py, 1.9.0):

distinct_clusters = len(set(best_labels))
if distinct_clusters < self.n_clusters:
    warnings.warn(
        "Number of distinct clusters ({}) found smaller than "
        "n_clusters ({}). Possibly due to duplicate points "
        "in X.".format(distinct_clusters, self.n_clusters),
        ConvergenceWarning,
    )

So scikit-learn-intelex can raise the warning today at no cost relative to stock scikit-learn — the same pass over the same labels — and oneDAL adds nothing, since the responses table is produced regardless.

Two things the interim does not cover, which is what the native field is for:

• It is a per-caller O(n) pass over the responses, re-deriving something the kernel already computed.
• It is unavailable to DAAL-interface consumers that do not request assignments (assignFlag == false), which get centroids only.

Note that checking the centroid table for duplicate rows instead is not an equivalent test: two non-empty clusters can share a centroid (a cluster holding {1, 3} and one holding {2} both land on 2). That state is transient, but a run stopping on max_iteration_count can return it, so the centroid-based proxy warns where scikit-learn would not.

Tasks

• Decide the accessor shape (boolean converged flag vs. distinct-centroid count)
• Add the field to kmeans::train_result + oneAPI spec
• Add the DAAL-side result equivalent
• Populate it from the CPU batch, CPU distributed, and GPU dense/CSR backends
• Raise ConvergenceWarning from scikit-learn-intelex based on it (interim: derive it from the responses as above)