Data are valuable assets in this digital era, inseparable from peoples’ lives. Every decision making process involves data. However, data alone cannot produce valuable information without proper management and interpretation. According to [1], profits are made by data management, not data possession, because data do not have an intrinsic value. Statistics is a branch of mathematics that deals with collection, management, analysis, interpretation, and visualisation of data. It is the main key to data management, providing mathematical and scientific method to managing data. For example, [2] and [3] develop a data management system for demography and primary health facilities respectively that positively impact the society. These two are just a tiny fraction of the essential roles of statistics for human lives.

One of widely used data management method is clustering. Clustering is a method of grouping data to several clusters such that data points in the same cluster have a maximum similarity, while data points in diferent clusters have a maximum diference. This method is used in many sectors, such as manufacture, transport, sustainable energy, health, and public policy, since it makes data, that are not necessarily meaningful, become meaningful (see [4][5][6]. Despite the importance, no clustering methods that fit all [7]. Interestingly, diferent clustering methods applied to the same data set may result diferently. One of notable clustering methods is k-means clustering.

K-means clustering is a clustering method which principle is minimising the distance between every object within a cluster and the centre of the cluster called a centroid. The used distance is the Euclidean distance since the data span Euclidean distance, and the centres of clusters are means on Euclidean spaces [8]1. In other words, objects are grouped into one cluster with the nearest centroid, indicating the maximum similarity centred in the centroid. Some examples of k-means use in data management for further application can be seen in [11][12]. One factor that makes this method widely used is its simplicity [13]. K-means clustering uses simple calculations, such as the Euclidean distance, that are easily calculable by both manually and computationally. K-means clusering also converges fast [13]. However, although it converges faster than k-medoids clustering, k-means clustering needs an initial determination of number of clusters. This number must not be determined negligently.

There are several methods to determine such a number of clusters, such as the elbow method, gap statistics, the silhouette method, and canopy [14]. These methods have unique advantages, disadvantages, and compatibility. However, despite its simplicity, the elbow method has received criticism for its accuracy. The elbow method determines the number of clusters based on a graph that connects some number of clusters and corresponding sum of squared error (SSE) of each cluster. The optimum number of cluster is determined by the point forming an ”elbow”, the pointiest one, indicating that higher numbers of clusters do not significantly reduce the SSE. The criticism lies on the fact that this method relies on subjective visual interpretation where the elbow point is chosen according to the probably biased plot. The elbow point may be chosen inaccurately, thus afecting the clustering result. Here are some examples of the elbow method implementations.

Figure 1 illustrates a clear elbow point; we can immediately choose as the optimum number of clusters since the pointiest point is apparent. However, there may be a case depicted by Figure 2 where the graph is almost smooth such that the pointiest point is not clearly shown. The elbow point is not clearly shown.

The issue extends beyond this point. Although the elbow points appears to be obvious as shown by 1, the ”obvious elbow” is possible to be ”a false elbow”. It is because the scaling of the horizontal and vertical axis are often disproportional. In the case of Figure 1, the horizontal axis scale is 0 to 7, while the vertical axis scale is 0 to 1400. This distortion causes misinterpretations and lead to incorrect choices of optimum number of clusters, thus giving unwanted k-means clustering results.

Figure 4 shows a distorted plot (that unfortunately often occurs during elbow method processes) where the vertical axis scale is not 1:1 proportional with the horizontal axis scale. In contrast, Figure 3 shows the plot with a proportional 1:1 scaling where it indicates absolute SSE decreases. Figure 4 gives impression that the optimum number of cluster is 3, while Figure 3 contradicts it.

Due to the complex subjectivity, k-means clustering often involves another method that is considered less subjective, thus neglecting improvisation of the elbow method. Meanwhile, analytical geometry and real analysis have hidden roles in precising this heuristic method. This paper aims to improve the method by changing the subjectivity into objectivity using some principles of analytical geometry and real analysis.

Shi etc. in [15] provides a method of determining the elbow point precisely using a principle of geometry, namely the cosine rule of a triangle. However, this method involves a long calculation of a triangle side length represented by the distance between two adjacent points. Moreover, this methods uses an inverse trigonometry function that is not a simple standard mathematical operation like addition and multiplication. Sinaga and Yang in [16] create an alternative k-means clustering algorithm where it finds the number of clusters independently without using initial cluster method determination. The method’s disadvantage is similar to that of [15]. It involves a non-standard arithmetic operation namely natural logarithm.

The method proposed in this paper ofers an advantage over the methods in [15][16] that may give similar accuracy but computationally more expensive. It only involves standard arithmetic operations namely addition, subtraction, multiplication, and division, resulting in more eficient algorithm. Not all programming languages have built-in complex mathematical functions like trigonometric inverses and natural logarithm; even C++ needs to add the package cmath in order to use these operations [17]. Therefore, using standard arithmetic functions that are included in all programming languages ofer flexibility and simplicity.

The method uses the principle of measuring an angle between two lines formulated in analytical geometry. The real analysis principle of derivative is also used to optimise the algorithm such that non-standard operations occurring in the algorithm can be omitted. Furthermore, the proposed method also considers every possibility of the elbow method graph behaviour such that the elbow point is chosen more precisely. This method can be an alternative to optimise k-means clustering; results in [15] are even shown to be better than the silhouette method. In the research, the silhouette method exhibits inconsistency to diferent data distribution by giving diferent cluster numbers, unlike the elbow method, and is computationally more expensive.

This section discusses the detailed formulation of determining the elbow point using an analytical geometric approach. Data simulation is also provided using Python.

2.1. Exact Elbow Point Formulation. The following theories about the elbow method, k-means clustering, and SSE are cited from [8][14].

Let X be a collection of n continuous p-dimensional data. Let X denote the i-th data point on X where and . Assume that X does not contain an outlier such that it is suitable for k-means clustering. Suppose that we cluster the data set into k clusters, and the determination of k utilises the elbow method.

We initiate the elbow method by plotting the sequence for 2 where is the sum of squared errors obtained if the data set is grouped into k clusters by k-means clustering. It is defined by

where is the j-th cluster, is the centroid of cluster , and is the Euclidean distance between the data point and its centroid . The SSE plotted here is obtained after iterating the k-means clustering such that no data points change their cluster membership. In other words, the plotted SSE is the most optimum SSE indicated by complete k-means clustering, not the initial SSE calculated when centroids are first-chosen randomly.

K-means clustering groups data points based on the nearest centroid using the Euclidean distance, and centroids change repeatedly by the optimising formula

where denotes the number of data points in the cluster . The change stops when no data points move to another cluster, thus implying the lowest possible SSE. If the number of clusters increases, the number of centroids also increases. Hence, distances between data points and their nearest centroids tend to shrink, resulting in a smaller SSE. this deduction, we conclude that the sequence is monotonically decreasing as greater clusters imply smaller SSEs.

The sequence SSE(k), as illustrated by Figure 5, is plotted monotonically decreasing. We connect adjacent points by a straight line such that all point (terms of form a continuous function consisting of several straight lines. Every corner of the function graph forms an angle that is used to determine the elbow point.

The elbow point is the point in which there is no significant drop of SSE afterwards. The typical elbow method determines the angle closest to since it indicates the last point with a significant drop of SSE i.e. the graph starts flattening beyond the point. However, since the elbow method, at the beginning, is a heuristic method, the closest-to-90^◦ choice is rather ambiguous. Two disputes need to be addressed. First, the angle measurement is not mathematical. Second, the method appears to ignore the possibility of facing-downwards corners chosen as the elbow point (illustrated by Figure 6). The point may indicate the closest one to 90◦ while there is still a significant SSE drop afterwards.

To address the first dispute, we construct a formula to measure the exact angle of the corners. We use the formula of angle between lines that uses line slopes.

Theorem 2.1.Let and be lines with inclination and respectively. Let and denote the slope of and respectively where and . The two lines intersect in a point, forming two supplementary angles, and ψ as illustrated by 7. The following holds:

and

The proof is constructed in [18] using the definition of slope, relation among interior and exterior angles of a triangle, and the property of tangent of sum of angles.

Based on 7, and are supplementary. Therefore, unless both are the former is located in the first quadrant (acute), and the latter is located in the second quadrant (obtuse), or vice versa. The angle located in the first quadrant has a positive tangent, whereas the one located in the second quadrant has a negative tangent.

We use the modified Theorem 2.1 to construct angle measurement formula of the SSE graph since the line behaviours are diferent. However, in this case, we first assume that the second dispute does not exist i.e. the lines forming the graph get more flattened after each term. The flattening condition is indicated by flattening lines i.e. slopes of the lines get closer to 0 as k increases (the slope of horizontal lines). In other words, we assume that m _ {l _ {k - 1}} \end{document} ]]> for

Theorem 2.2. Let denote the straight line connecting the point ) and , and denote the angle of the corner facing upwards. The elbow point is such that it satisfies

where

To prove Theorem 2.2, we first consider the following proposition to prove that is always between 90 ◦ ∗and . This fact ensures that the angle closest to has the smallest tangent.

Proposition 2.3.If ψ is the angle that faces upward, we have

Proof. If denotes the straight line connecting the point and , since for , we have

Moreover, we assume m _ { l _ { k } } \end{document} ]]> which implies 0 \end{document} ]]> . Consequently, since 0 \end{document} ]]> , we have

and

Since tan , the angle must be in quadrant II or III i.e. or . However, since ψ and ϕ are supplementary, it must not exceed 180^◦. Therefore, we have □

Here is the proof of Theorem 2.2.

Proof. Recall that denote the straight line connecting the point and ). As illustrated by Figure 8 we have and are the inclination of and respectively. Since , we have

Elbow point candidates are represented by the angle supplementary to that is . Since the angles are supplementary, the angles have opposites tangents i.e.

The endpoints, and , do not form an angle. Therefore, Equation 2 only holds for

By the formula of slope of a straight line, since connects and , we have and

Therefore, Equation 2 can be written as

By Proposition 2.3, we have . Furthermore, since tan ψ is monotonically increasing within the interval3, the angle ψ closest to must be satisfied by the smallest (most negative) tan ψ. Therefore, we conclude that the elbow point is (k, SSE(k)) that satisfies

2.2. Alternative Method. Theorem 2.2 holds if the second dispute is assumed to be untrue i.e. a facing downward corner, whose angle is the closest to 90◦, is probably chosen as the elbow point despite a still significant SEE drop afterwards. Some data sets cause the elbow method graph violating the assumption. In other words, there can be a case that

In Figure 9, the corner that is an intersection of and may be chosen if it is the closest angle to if the usual elbow point criteria is used. However, it is clear that the corner must no be the elbow point as there a larger drop of SSE onwards. It does not necessarily indicate the sign of flattening SSE drops. In this case, is the more appropriate elbow point since after , there is still a noticeable SSE drop.

Proposition 2.4. , then

Proof. The drop of to |, or for simplicity, since is monotonically decreasing, we have for

Suppose that .

We then have

The Equation 3 indicates a higher drop after the point .Figure 10 illustrates the Proposition 2.4.

Figure 10 shows that has a larger slope that of . It indicates a higher SSE drop after the intersection of the two lines as shown by Equation 3. The corner of the intersection faces downwards.

By discovering the efect of ignoring the second dispute to the elbow point choice, we reconstruct Theorem 2.2 such that it is more universal. We use the same criteria (the closest-to-90^◦) with an additional condition: neglecting the point in Proposition 2.4. In this case, is the more appropriate elbow point since after , there is still a noticeable SSE drop.

Theorem 2.5.Suppose that . Let denote the straight line connecting the point ) and and denote the angle of the corner facing upwards. The elbow point is such that it satisfies m _ {l _ {k - 1}}\right) \end{document} ]]> where

Theorem 2.5 adds a condition that is the negation of condition in Proposition 2.4 into Equation 1. Hence, points indicating a rise of SSE drop, satisfying the condition in Proposition 2.4 is neglected.

2.3. Program Implementation and Simulation. K-means clustering is often implemented by software, computationally, especially if it involves a large data set. Hence, we also provide an implementation of the constructed formula into computer programming. Here is the pseudo-code.

The algorithm begins with defining main variables used for k-means clustering and the elbow method namely a data set and an array containing list of tan ψ. We define some functions to simplify the algorithm that are the Euclidean distance and the SSE. The Euclidean distance function involves a looping as a representative of consecutive summation of squared diferences; the SSE function also involves a looping of Euclidean distances between every variable and its centroid.

The next step is creating a looping to put tan ψk consecutively into the defined array. The formula is of Equation 4. We also put a condition of Theorem 2.5 to ignore corners facing upwards. We put tan for this kind of points. Hence, the points will not be chosen as the elbow point since they will not become the minimum among negative tangents.

Lastly, we define the variable ”angle” as the minimum of tan ψ . The k-means clustering is then run with the number of clusters.

Some programming languages already include standard functions used in this algorithm, such as the Euclidean distance, SSE, and k-means itself. Python is one oh such programming languages. Here is the implementation in Python for some sample data set (we can change it to diferent data set).

Figure 11 shows that the most optimum number of cluster is 3. However, as described in Introduction, it could be misleading. It is answered by Figure 12 which is the output of the Python code for tan ψ calculation.

Figure 12 shows that the smallest tangent is obtained when . It shows that the distorted SSE plot in Figure 11 is indeed misleading.

Figure 13 shows the undistorted plot of SSE. Despite the quite unclear plot, we can conclude that 3 is not the most optimum number of clusters since there is still indeed a significant drop afterwards. The plot starts flattening after k = 6. The result of the k-means clustering is shown in Figure 14.

In comparison to Figure 14, Figure 15 shows the k-means clustering if there are 3 clusters, mistakenly chosen by the biased Figure 11. We see that the clustering still leaves a huge distance between data points and their corresponding centroids. Figure 14 shows a better clustering where the distances are minimum.

The elbow method, known as a heuristic method, is made exact using the formula of angle between lines. Suppose that are tuple points of number of clusters and corresponding SSE. The elbow point is the point that satisfy m _ {l _ {k - 1}}\right) \end{document} ]]>

where

and for . The algorithm is simple such that it is easily implementable in programming. The precision provided by this method also eliminates the possibility of choosing an incorrect elbow point since it results the same regardless of the visual representation.