Computational Implementation of Linear Reference Elbow (LRE) Method for Optimal Cluster Determination in k-Means Algorithm

Abstrak

Abstract The selection of the optimal number of clusters (k) in the K-Means algorithm still relies on the subjective visual elbow method or computationally intensive techniques like the Gap Statistic. LRE was developed to address this issue through an objective and efficient geometric approach. The aim of this research is to provide an automated Python-based solution for determining the optimal k quickly and reproducibly, particularly for industrial applications. The LRE method calculates the orthogonal distance between the points of the WCSS curve and the reference line connecting the first and last points, then selects the k with the maximum distance. LRE successfully processed benchmark datasets (Iris and a synthetic mixed-distribution dataset) at a speed up to 110 times faster than the Gap Statistic method. This deterministic and efficient nature ensures reproducibility and practical applicability for large-scale clustering analysis. This significant difference is particularly evident in algorithmic complexity, where LRE maintains linear time complexity (O(n)), while bootstrap-based methods like the Gap Statistic experience exponential time increases. Testing on two benchmark datasets showed that LRE produced consistent outputs. The deterministic nature of this algorithm eliminates the subjective variability that is the main drawback of manual approaches.

Identifier

• OpenAlex: https://openalex.org/W4416385359
• DOI: https://doi.org/10.1088/1742-6596/3139/1/012038