## 3 Partition-Based Clustering  
### K-Means  
K-means clustering [2] is a technique that groups instances based on their similarities. This process involves iteratively assigning each instance to a cluster by considering its distance from the cluster's centroid (the mean of the instances in the cluster). The algorithm then updates the centroids until they stabilize. Its major objective is to minimize the within-cluster sum of squares (WCSS), which represents the sum of squared distances between instances and their assigned cluster centroids. Formally, for a set of instances, \(X=\{x_{1},x_{2},\ldots,x_{n}\}\), k-means aims to assign the \(n\) instances to k clusters (\(k\leq n\)) \(S=\{S_{1},S_{2},\ldots,S_{k}\}\) targeting at minimizing the WCSS function:  
\[WCSS=\sum_{j=1}^{k}\sum_{x_{i}\in S_{j}}||x_{i}-\mu_{j}||^{2}\]  
Here, \(\mu_{j}\) represents the mean of cluster \(S_{j}\), and \(||x_{i}-\mu_{j}||\) is the selected distance metric between the instance \(x_{i}\) and the corresponding mean.  
The k-means algorithm commences by initializing k centroids randomly, which serve as the initial cluster centers. Subsequently, each instance is assigned to its closest centroid, and the centroid is updated to the center of the instances that have been assigned to it. This process repeats iteratively until the centroids converge. Algorithm 1 provides a pseudo-code representation of the k-means clustering technique. Initially, the algorithm takes a dataset \(X=x_{1},x_{2},\ldots,x_{n}\) and forms k clusters (\(C\)). The algorithm initially assigns each instance \(x_{i}\) to the cluster with the closest centroid (mean) \(c_{j}\), which is termed as the assignment step (lines 4-6). Following the assignment, the algorithm computes new means, by averaging the instances within each cluster (lines 7-9), which can be computed as  
\[c_{j}=\frac{1}{|C_{j}|}\sum_{x_{i}\in C_{j}}x_{i}\]  
The assignment step is then repeated, incorporating the updated means. Hence, the means are continually adjusted throughout the process. The algorithm stops when there is no change in means (cluster consolidation) between two consecutive iterations (line 10). Given that each instance is closer to the centroid of its respective cluster, the WCSS function is minimized, signifying successful clustering.  
```
0:\(X=x_{1},x_{2},\ldots,x_{n}\)--dataset, k--number of clusters
0:\(C=C_{1},C_{2},\ldots,C_{k}\)--set of clusters
1: Select k initial centroids \(c_{1},c_{2},\ldots,c_{k}\) randomly from \(X\)
2:repeat
3: Create k empty clusters \(C_{1},C_{2},\ldots,C_{k}\)
4:for\(i=1\) to \(n\)do
5: Assign \(x_{i}\) to the cluster \(C_{j}\) with the closest centroid \(c_{j}\)
6:endfor
7:for\(j=1\) to k do
8: Update centroid \(c_{j}\) as the mean of all points in cluster \(C_{j}\)
9:endfor
10:until no more changes in the assignment of points to clusters
```  
**Algorithm 1** K-means clustering.  
K-means has garnered widespread popularity, giving rise to a plethora of variants. Among these, k-medians clustering [29] is a notable variant. In k-medians clustering, the conventional mean calculation is substituted with the median computation. This alteration has a distinct advantage: heightened resilience to the influence of outliers. Outliers, notorious for their potential to disrupt the computation of means, are effectivelyattenuated by the adoption of k-medians. As a result, the robustness of k-medians clustering makes it a promising solution for datasets containing outliers.