## 3 Partition-Based Clustering
### Initial Centroids Selection  
The final clusters discovered by partitional-based algorithms are influenced by the randomly chosen initial centroids. As a consequence, the algorithms will yield varying clusters when applied to the same data using different initial cluster centroids. Therefore, the main challenge is that the choice of initial centroids can significantly impact the final clustering outcome. Poor initial centroids might lead to slow convergence or result in suboptimal cluster assignments. In contrast, efficient initial centroids may result in well-separated clusters. Figure 2 presents the result of a poor and an efficient centroids initialization.  
K-means++ [30] is a smart initialization technique for k-means clustering. It helps to spread the initial centroids across the dataset, ensuring that they are not concentrated in a single area. By choosing centroids that are well distributed, k-means++ aims to provide a good starting point for the subsequent iterative assignment and update steps of k-means. K-means++ does so by probabilistically picking initial centroids that are farthest enough from each other. This strategic approach helps mitigate the common issue of k-means clustering being susceptible to suboptimal solutions due to inadequate initialization.  
K-means++ starts by selecting an initial instance at random as the first centroid. Each subsequent centroid is then chosen based on their distance from previous centroids, with a higher probability of selecting instances that are farther apart. More specifically, the algorithm calculates the distance (usually the Euclidean distance) between each instance and its nearest existing centroid. Then, it assigns a probability to each instance, based on the square of its distance to the nearest existing centroid. The farther an instance is located from the existing centroids, the higher its probability of being chosen as the next centroid. K-means++ chooses the next centroid probabilistically, based on the calculated probabilities. The probability ensures that instances which are farther away have a higher chance of being selected as centroids. The algorithms terminates when the desirable number of centroids has been selected.  
Similar to k-means++ which is designed to initialize the initial cluster centroids in the k-means clustering, the Cao method [31] is a common initialization technique used for k-modes clustering. Like k-means++, this method aims to select initial centroids that are well distributed across the dataset in terms of their Hamming distances. It helps in finding better starting points for the centroids, which in turn can lead to efficient clustering results.  
The Cao method is quite similar to k-means++. However, it uses the Hamming distance. More specifically, the Cao method begins by selecting the first centroid randomly from the dataset. For each instance in the dataset, the method calculates the Hamming distance between the instance and the current centroid. Afterwards, the method calculates the probability for each instance to be selected as the next centroid. This probability is based on the distances calculated in the previous step. Instances that are farther away from the current centroid have a higher probability of being selected as the next centroid. The next centroid is selected probabilistically, based on the calculated probabilities. Instances with  
Figure 2: Example of result of a poor and an efficient centroids initialization in k-means clustering.  
higher probabilities are more likely to be chosen. The procedure is repeated until the desired number of initial centroids (k) is selected.