Clustering Algorithms

Step 1: Specify Number of Clusters

Let the dataset be \[ \mathcal{D} = \{x_1, x_2, \ldots, x_n\}, \quad x_i \in \mathbb{R}^d \]

Fix the number of clusters: \[ K \in \mathbb{N} \]

Step 2: Initialize Centroids Randomly

Select \(K\) distinct data points as initial centroids: \[ \mu_1^{(0)}, \mu_2^{(0)}, \ldots, \mu_K^{(0)} \in \mathcal{D} \]

Step 3: Distance Computation & Assignment Step (Cluster Membership)

For each data point \(x_i\), compute the squared Euclidean distance to all centroids and assign it to the nearest one: \[ c_i^{(t)} = \arg\min_{k \in \{1,\ldots,K\}} \|x_i - \mu_k^{(t)}\|_2^2 \]

Thus, \[ x_i \in C_k^{(t)} \quad \text{if } c_i^{(t)} = k \]

Step 4: Update Step (Centroid Recalculation)

Recompute each centroid as the mean of the data points assigned to that cluster: \[ \mu_k^{(t+1)} = \frac{1}{|C_k^{(t)}|} \sum_{x_i \in C_k^{(t)}} x_i \]

Step 5: Stopping Criterion (Convergence)

Iterate Steps 3–4 until convergence, i.e., stop if either: \[ C_k^{(t+1)} = C_k^{(t)} \quad \forall k \]

or \[ \mu_k^{(t+1)} = \mu_k^{(t)} \quad \forall k \]

• Advantages: Simple, scalable, efficient for large datasets.

• Limitations: Sensitive to initialization, outliers, assumes spherical clusters, requires pre-defined $k$.

K-medoids clustering is similar to K-means but uses actual data points as cluster centers (medoids) instead of the mean. This makes it robust to outliers.

Steps:

1. Initialize $k$ medoids randomly from data points.

2. Assign each point to the nearest medoid.

3. For each cluster, try swapping medoid with another point in cluster; if total cost decreases, update medoid.

4. Repeat step 3 until no improvement.

Step 1: Specify Number of Clusters

Let the dataset be \[ \mathcal{D} = \{x_1, x_2, \ldots, x_n\}, \quad x_i \in \mathbb{R}^d \]

Fix the number of clusters: \[ K \in \mathbb{N} \]

—

Step 2: Initialize Medoids Randomly

Select \(K\) distinct data points as initial medoids: \[ m_1^{(0)}, m_2^{(0)}, \ldots, m_K^{(0)} \in \mathcal{D} \]

Each \(m_k\) is a representative data point of cluster \(C_k\).

—

Step 3: Distance Computation & Assignment Step

Assign each data point to the nearest medoid using a distance metric: \[ c_i^{(t)} = \arg\min_{k \in \{1,\ldots,K\}} \text{dist}(x_i, m_k^{(t)}) \]

Thus, \[ x_i \in C_k^{(t)} \quad \text{if } c_i^{(t)} = k \]

—

Step 4: Update Step (Medoid Recalculation)

For each cluster \(C_k^{(t)}\), choose the new medoid as the data point that minimizes the total distance to all other points in that cluster: \[ m_k^{(t+1)} = \arg\min_{x_j \in C_k^{(t)}} \sum_{x_i \in C_k^{(t)}} \text{dist}(x_i, x_j) \]

—

Step 5: Stopping Criterion (Convergence)

Iterate Steps 3–4 until convergence, i.e., stop if: \[ m_k^{(t+1)} = m_k^{(t)} \quad \forall k \] or cluster assignments do not change.

—

Objective Function

K-medoids minimizes the total within-cluster dissimilarity: \[ \boxed{ \sum_{k=1}^{K} \sum_{x_i \in C_k} \text{dist}(x_i, m_k) } \]

Unlike K-means, the distance need not be squared and can be any valid metric.

• K-means uses mean, sensitive to outliers; K-medoids uses medoid, robust to outliers.

• K-means is faster (simple arithmetic mean), K-medoids is computationally expensive (pairwise distances).

• Both require pre-defined $k$.

Algorithm: Bottom-Up (Agglomerative) Hierarchical Clustering

1. Initialization: Start with each data point as its own cluster: \[ C_i = \{x_i\}, \quad i = 1,2,\dots,n \]

2. Compute Distance Matrix: Compute all pairwise distances between clusters using a chosen metric (e.g., Euclidean distance): \[ d(C_i, C_j) = \min/\max/\text{average}_{x \in C_i, y \in C_j} d(x,y) \] depending on the linkage criterion (single, complete, or average).

3. Merge Clusters: Identify the pair of clusters with the minimum distance according to the chosen linkage criterion and merge them.

4. Update Distances: Recompute distances between the new cluster and all remaining clusters using the linkage criterion.

5. Stopping Criterion: Repeat Steps 3–4 until one of the following conditions is met:

   • Desired number of clusters is reached.

   • Only a single cluster remains (complete hierarchy formed).

Definition: Divisive clustering starts with all points in a single cluster and recursively splits clusters into smaller sub-clusters until each point forms its own cluster or a stopping criterion is satisfied.

Procedure:

1. Start with the full dataset as a single cluster.

2. Select a cluster to split based on a criterion (e.g., maximize intra-cluster distance or minimize inter-cluster similarity).

3. Split the selected cluster into two sub-clusters. This can be done using methods such as:

   • K-means or K-medoids on the cluster to partition it into two groups.

   • Principal Component Analysis (PCA) to find the direction of maximum variance and split along it.

4. Repeat steps 2–3 recursively on the new clusters until stopping criteria are met (e.g., desired number of clusters, minimal cluster size, or distance threshold).

Distance Measure: For splitting, a common choice is the diameter of the cluster: \[ \text{diameter}(C) = \max_{x_i, x_j \in C} \|x_i - x_j\| \] Clusters with larger diameter are often chosen first to split.

Characteristics:

• Produces a hierarchy of clusters similar to agglomerative clustering but in reverse order.

• Computationally more expensive than agglomerative methods for large datasets.

• Flexible in choosing splitting criteria and distance measures.