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

Department of Mathematics, Faculty of
Mathematics and Natural Sciences, Lambung
Mangkurat University

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 a sample dataset at a speed 110 times faster than the Gap Statistic method for the same dataset, while the Elbow method could not be timed due to its subjective nature. 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.

Keywords: automated clustering, elbow method, K-Means, computational efficiency

Topic: Instrumentation and Computational Physics