EUVIMEDEUVIMED entdecken
Crossref

Understanding Why Lloyd’s Algorithm in K-Means Clustering Frequently Stalls at Suboptimal Cluster Solutions: Case study in Customer segmentation

Rifat Rayhan ROMY

Business Administration Student Working Papers · 29.07.2026

DOI: 10.24818/baswp.2026.15 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Business Administration Student Working Papers, online erschienen am 29.07.2026. Verfasst von Rifat Rayhan ROMY.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Customer segmentation is one of the most consequential analytical tasks in retail management, and Lloyd's K-Means algorithm remains its dominant computational implementation. HoIver, Lloyd's algorithm carries an inherent and under-quantified vulnerability: because the withincluster sum of squares objective is non-convex, the algorithm is guaranteed to converge only to a local minimum, and the specific solution it returns depends entirely on the random placement of its initial centroids. This paper investigates the severity, structure, and practical consequences of this stalling phenomenon using real point-of-sale transaction data from a single branch of a major European retail chain operating in Southern Poland. Drawing on 162,926 cleaned transactions across three observation windows, I engineered ten transaction-level features and employed a paired Real Data Block and Generated Data Block experimental design that isolates algorithmic stalling from genuine data ambiguity. Using a custom implementation of Lloyd's algorithm that records Mean Centroid Displacement at every iteration, I run 1,000 independent Monte Carlo replications per condition across eleven values of k (2 to 12) and two initialization strategies, totaling 450,000 algorithm executions. I introduce a novel bias metric, Lloyd Bias, defined as mean MCD(k) divided by mean MCD(k_true), which anchors all comparisons to Lloyd's own empirical baseline at the correct number of clusters. Results show that stalling is universal at 99.9% of all runs across all k values when measured within conditions, that cross-run solution consistency collapses from ARI 0.98 at k=2 to ARI 0.49 at k=7, and that K-Means++ initialization provides negligible stall reduction despite its theoretical guarantees. These findings challenge the routine practice of relying on single-run Lloyd segmentation in commercial analytics and establish MCD-based bias as a more principled diagnostic than raw within-cluster sum of squares comparisons.

Zitieren

APA

ROMY, R. R. (2026). Understanding Why Lloyd’s Algorithm in K-Means Clustering Frequently Stalls at Suboptimal Cluster Solutions: Case study in Customer segmentation. Business Administration Student Working Papers. https://doi.org/10.24818/baswp.2026.15

Vancouver

ROMY RR. Understanding Why Lloyd’s Algorithm in K-Means Clustering Frequently Stalls at Suboptimal Cluster Solutions: Case study in Customer segmentation. Business Administration Student Working Papers. 2026. doi:10.24818/baswp.2026.15

BibTeX
@article{ROMY2026,
  author = {ROMY, Rifat Rayhan},
  title = {Understanding Why Lloyd’s Algorithm in K-Means Clustering Frequently Stalls at Suboptimal Cluster Solutions: Case study in Customer segmentation},
  journal = {Business Administration Student Working Papers},
  year = {2026},
  doi = {10.24818/baswp.2026.15}
}
Kostenlos starten →