# AutoElbow: An Automatic Elbow Detection Method for Estimating the Number of Clusters in a Dataset
## 3 AutoElbow Method
### Description of the Algorithm  
In the AutoElbow method, we adopt the total WSD (TWSD) as the evaluation measure, which is obtained as the sum of the squared Euclidean distances between each point in a cluster and its representative centroid. After each run of the K-means algorithm, the value of TWSD is computed for different cluster numbers \(k=1,2,\ldots,K\), where \(K\) is the maximum number of clusters anticipated in the dataset. The method for determining the TWSD using K-means is described in [15]. Next, we present a detailed explanation of how the AutoElbow technique operates:  
1. Let the input data to be clustered be \(Z=\{z_{i}\}_{i=1}^{N}\), where \(N\) is the total number of data points in \(Z\in\mathbb{R}^{D}\), and \(D\) is dimension of \(Z\). 2. The K-means algorithm is executed repeatedly for different cluster values \(k\) ranging from 1 to \(K\). The K-means algorithm can be implemented as described in [18]. 3. The TWSD, i.e., \(y\) for \(K\) clusters is computed as \[y_{k}=\sum_{k=1}^{K}\sum_{i=1}^{N_{k}}||z_{i}^{(k)}-c_{k}||^{2},\] (1)  
for \(k=1,2,\ldots,K\), where \(k\) represents a single cluster, \(K\) is the maximum number of clusters to be iterated upon, \(i\) is the index of a single data point \(z_{i}\) within a single cluster \(k\), \(N_{k}\) is the total number of data points in cluster \(k\) and \(c_{k}\) represents each cluster's centroid. Figure 1: Representation of the parameters of the AutoElbow method. The elbow-based graph \(G\) is obtained as \(G=\{(x_{k},y_{k})\}_{k=1}^{K}\), where \(\{x_{1}=1\),\(x_{2}=2\), \(\ldots,x_{k}=K\}\) are the actual total number of clusters considered in the iteration process. 5. The graph \(G\) is then inputted to the AutoElbow algorithm, which proceeds to compute the elbow or knee point \(P\) (i.e., \(g_{k^{*}}\)), where \(k^{*}\) is the optimal cluster number, as follows: 1. First, \(G\) is normalized to the interval [0,1]. This is done to ensure that the computed squared Euclidean distances between graph points are same in magnitude. Therefore, the normalized values are denoted as \[G^{norm}=\{(x_{k}^{norm},y_{k}^{norm})\}_{k=1}^{K}.\] (2) where \[x_{k}^{norm}=\frac{x_{k}-\min\{x_{k}\}_{k=1}^{K}}{\max\{x_{k}\}_{k=1}^{K}-\min \{x_{k}\}_{k=1}^{K}},\text{for }k=1,2,\ldots,K\] (3) \[y_{k}^{norm}=\frac{y_{k}-\min\{y_{k}\}_{k=1}^{K}}{\max\{y_{k}\}_{k=1}^{K}-\min \{y_{k}\}_{k=1}^{K}},\text{for }k=1,2,\ldots,K.\] 2. As illustrated in Figure 2, the algorithm then checks for the concavity structure of the graph \(G\) in order to identify the proper locations of \(O\), \(R\), and \(Q\). Figure 2 depicts the relative positions of \(O\) and \(Q\) for each of the four forms of concavity, whereas \(R\) is determined as the equivalent \(x_{k}^{norm}\) value per graph point along the abscissa. The AutoElbow algorithm is designed to identify these distinct graph topologies, thus, making it applicable to both elbow- and knee-based graphs. We introduce a simple test for the concavity form of \(G^{norm}\) as follows: 1. First, we compute the slope of the straight line \(L\) that connects the first and last element in \(G^{norm}\) as \[m=\frac{y_{1}^{norm}-y_{K}^{norm}}{x_{1}^{norm}-x_{K}^{norm}}\] (5) where \(x_{1}^{norm},x_{K}^{norm},y_{1}^{norm}\), and \(y_{K}^{norm}\) are the first and last elements in \(x^{norm}\) and \(y^{norm}\), respectively. 2. Then, a check point \(l_{K/2}\) is computed at the mid-point of \(L\) (i.e., at \(K/2\)) using \[l_{K/2}=y_{1}^{norm}-m\times(x_{1}^{norm}-x_{2}^{norm})\] (6) The midpoint (i.e., \(K/2\)) was selected as the checkpoint for the concavity test since it is the point furthest from the boundary line \(L\). This choice ensures that the concavity test detects no misleading variations at the edges of the elbow- or knee-based graph \(G\). 3. Consequently, the concavity test \(\mathcal{C}\) of \(G^{norm}\) is established as follows \[\mathcal{C}=