NEWS

---

MergeKmeans 0.3.0 (2026-09-04)

Corrections

• The classification EM of the heteroscedastic variants ("HeSC", "HeEC") now uses the closed-form M-step of the classification likelihood under the implied mixing proportions. Earlier versions iterated the stationarity conditions (Eqs. 14 and 16 of Melnykov and Michael, 2020) as updates with lagged proportions; that recursion is not a contraction (it oscillates for p = 2 and diverges for p > 2), which produced the component collapses and non-convergence documented for version 0.2.0.
• chooseK() seeds every grid point from the calling RNG stream, so the curve and the recommendation are reproducible from set.seed() for any number of cores; previously cores > 1 gave irreproducible results.
• The message of an uncut fit no longer reports the automatic suggestion under Ward's linkage, with which G = "auto" is not available.
• G = "auto" measured gaps on the raw log-overlap scale, so numerical underflow among negligible overlaps (1e-11 versus exactly 0, say) could produce the largest gap and a spurious cut: four well-separated clusters on a line were cut into three. Gaps are now measured on log(overlap + 1e-4), which treats overlaps below 1e-4 as ties. The rule targets well-separated clusters and is now refused with Ward's linkage, where it was never meaningful.
• K-means restarts are seeded individually from the calling RNG stream, so a fit is reproducible from set.seed() for any value of cores (previously results with cores > 1 were not reproducible). The serial init = "random" path is unchanged. On Windows, cores > 1 now emits a message and runs serially instead of being silently ignored.
• The classification EM of the non-spherical variants warns when cem.iter.max is reached without convergence; previously this was visible only in summary().

New features

• start accepts centers as well as labels: a K x p matrix, or a list with a centers/centroids element such as the value of ClusterR::MiniBatchKmeans(). Observations are assigned to the nearest center, which makes the partition consistent with predict() by construction.
• pairwise_overlap() accepts mixing proportions tau in the heteroscedastic cases as well, so the overlap of an arbitrary fitted Gaussian mixture can be computed; the DEMP-K implied proportions remain the default.
• chooseK() locates the elbow by the chord method (the grid point farthest from the line joining the first and last points of the SSB/SSTO curve), which is less sensitive to the starting point of the grid than the previous marginal-gain threshold. The recommendation remains one grid step beyond the elbow.

MergeKmeans 0.2.0 (2026-07-19)

Robustness (pre-release stress campaign; see validation/robustness/REPORT.md)

• Univariate data now default to single linkage: the components of 1-D clusters form a chain that Ward's linkage cuts unreliably.
• Unconverged Hartigan-Wong K-means solutions (Quick-TRANSfer cap at large n) are polished with Lloyd iterations so that the stored components are consistent with the stored centers and predict() reproduces them.
• Diverging classification EM for the heteroscedastic variants (an instability inherent in their implied mixing proportions) now returns the last stable iteration with a warning instead of failing with an internal error; converged CEM fits return exactly the parameters that generated the labels, restoring the predict() round-trip.
• G = "auto" is now computed from the single-linkage merge sequence of the overlap matrix regardless of the fitting linkage (the previous Ward-height gaps were unreliable); its limits (range 2:(K-1), spurious suggestions on structureless data) are documented.
• Fixed: variant = "HeEC" crashed on univariate data; plot(fit, what = "tree") failed for K = 2; Inf values slipped past validation into cryptic downstream errors (MergeKmeans, predict, chooseK); overlap_map() crashed on missing values; predict() silently propagated NA.
• kmeans++ seeding subsamples very large datasets (n > 1e5), removing the dominant cost of the n = 1e6, large-K regime.
• New documentation: linkage guidance (Ward vs unequal cluster sizes and 1-D chains), contamination tolerance, heavy-tailed vs skewed clusters.

New features

• init = "kmeans++" is the new default initialization of the K-means restarts (Arthur & Vassilvitskii, 2007), stabilizing the large-K component solutions on which the merging is built; init = "random" restores the previous behavior.
• start argument: MergeKmeans() can now merge a partition computed by any external engine (a kmeans object, a ClusterR-style list, or a bare label vector), skipping its own K-means step entirely. This removes the single-threaded stats::kmeans ceiling for very large datasets.
• G = "auto" cuts the merge tree at the largest gap in merge heights (also available in recut()); when no G/omega.star is supplied the fit-time message now reports the suggested G.
• K = NULL (new default) selects the number of components automatically via chooseK().
• chooseK() now reports and marks a recommended K (one grid step beyond the detected elbow) and gained a cores argument.
• cores argument forks the K-means restarts via the parallel package (POSIX systems).
• broom tidiers: tidy(), glance(), and augment() methods are registered when broom is loaded.

User-facing changes

• Variant names are matched case-insensitively and accept plain-language aliases ("spherical", "elliptical", "spherical-unequal", "elliptical-unequal").
• omega.star with Ward's linkage is now an error (it previously warned and returned a degenerate unmerged partition).
• A warning is emitted when components contain single observations (K too large relative to n).
• Documentation: scaling guidance, a "when to use what" discussion (including the recommendation to prefer model-based clustering for genuinely overlapping Gaussian ellipsoids), and a recipe for merging mini-batch K-means solutions of massive datasets.

MergeKmeans 0.1.0

• Initial version: DEMP-K merging of K-means solutions (Melnykov & Michael, 2020) with the four K-means variants (HoSC, HoEC, HeSC, HeEC), exact pairwise-overlap computations, single/Ward/average/complete linkages, the overlap map display, recut(), chooseK(), pairwise_overlap(), and print/summary/plot/predict methods.
• All overlap computations validated against MixSim::overlap() and by independent Monte Carlo simulation; the paper's illustrative examples and pen-digits application reproduced.