Week 3: Unsupervised Learning - Clustering - K-means/Kernel K-means

 Introduction to Clustering

Clustering is an unsupervised learning technique used to group data points into clusters based on their similarities. Unlike supervised learning, clustering does not rely on labeled data. Instead, it finds inherent patterns and structures within the data.

K-Means Clustering

K-Means is one of the most widely used clustering algorithms. It partitions data into K clusters, where each cluster is represented by its centroid.

Steps of K-Means Algorithm

1. Choose the number of clusters, K.
2. Randomly initialize K centroids.
3. Assign each data point to the nearest centroid.
4. Update centroids as the mean of the assigned points.
5. Repeat until centroids do not change significantly (convergence).

Mathematical Formulation

The objective function (loss function) for K-Means is the sum of squared distances between data points and their respective cluster centroids:

$$J = \sum_{i=1}^{K} \sum_{x_j \in C_i} || x_j - \mu_i ||^2$$

Where:

• $K$ is the number of clusters.
• $C_i$ is the set of points belonging to cluster $i$.
• $\mu_i$ is the centroid of cluster $i$.
• $|| x_j - \mu_i ||^2$ is the squared Euclidean distance.

Choosing the Value of K

Several methods can help determine an optimal value for K:

1. Elbow Method: Plot the Within-Cluster Sum of Squares (WCSS) for different values of K and look for an 'elbow' point where adding more clusters provides diminishing returns.
2. Silhouette Score: Measures how similar a data point is to its assigned cluster versus other clusters.
3. Gap Statistic: Compares WCSS with expected WCSS under random distribution.

Example of K-Means Clustering

Step 1: Given Data Points

Assume we have the following data points: (2,3), (3,4), (8,7), (9,6), (10,8)

Step 2: Choose K=2 and Initialize Centroids

Let's assume initial centroids are (2,3) and (8,7).

Step 3: Compute Distance and Assign Clusters

Using Euclidean distance, we compute the distance of each point to the centroids and assign clusters.

Step 4: Compute New Centroids

After assigning clusters, update centroids and repeat the process until convergence.

Kernel K-Means Clustering

Kernel K-Means extends K-Means to non-linearly separable data using a kernel function. Instead of computing distances in the original feature space, it transforms data into a higher-dimensional space where clusters become linearly separable.

Kernel Trick

A kernel function $K(x_i, x_j)$ is used to compute distances in transformed space, avoiding explicit transformation. Common kernels:

1. Linear Kernel: $K(x,y) = x^T y$
2. Polynomial Kernel: $K(x,y) = (x^T y + c)^d$
3. Gaussian (RBF) Kernel: $K(x,y) = e^{- \frac{||x - y||^2}{2 \sigma^2}}$

Mathematical Formulation

Instead of centroid-based calculations, Kernel K-Means minimizes the following objective function:

$$J = \sum_{i=1}^{K} \sum_{x_j \in C_i} K(x_j, x_j) - \frac{2}{|C_i|} \sum_{x_j \in C_i} \sum_{x_k \in C_i} K(x_j, x_k)$$

Advantages of Kernel K-Means

• Handles non-linearly separable clusters
• Works well with high-dimensional data
• Utilizes different kernels to adapt clustering to various data distributions

---

20 Knowledge Testing Questions & Answers

#	Question	Answer & Explanation
1	What is the main difference between K-Means and Kernel K-Means?	K-Means uses Euclidean distance, while Kernel K-Means uses a kernel function to transform data into higher dimensions.
2	How does K-Means decide the initial cluster centers?	Randomly selects K points from the dataset as initial centroids.
3	What is the stopping criterion in K-Means?	The algorithm stops when centroids do not change significantly between iterations.
4	What type of clustering does K-Means perform?	Hard clustering, meaning each point belongs to exactly one cluster.
5	What is the computational complexity of K-Means?	O(n * K * d * i), where n = data points, K = clusters, d = dimensions, i = iterations.
6	What is the purpose of the Elbow Method?	It helps determine the optimal number of clusters by plotting WCSS vs. K.
7	How do we compute the new centroids in K-Means?	By taking the mean of all points assigned to each cluster.
8	How is the Silhouette Score interpreted?	A higher silhouette score (close to 1) indicates better clustering.
9	Which kernel is commonly used in Kernel K-Means?	Gaussian (RBF) kernel is commonly used.
10	How does Kernel K-Means differ in centroid computation?	Instead of averaging points, Kernel K-Means uses a similarity matrix.
11	What distance metric does K-Means use?	Euclidean distance.
12	What is a disadvantage of K-Means?	Sensitive to outliers and requires predefining the number of clusters.
13	What is the formula for WCSS?	Sum of squared distances of points from their centroids.
14	How do we choose the best kernel in Kernel K-Means?	Experimentation or cross-validation with different kernels.
15	Why does Kernel K-Means require a similarity matrix?	Because it operates in an implicit high-dimensional space.
16	Why does K-Means sometimes fail to converge optimally?	Poor centroid initialization can lead to local minima.
17	What technique improves K-Means initialization?	K-Means++ selects initial centroids more strategically.
18	What is the role of the kernel trick in Kernel K-Means?	It enables clustering in higher dimensions without explicitly computing transformations.
19	How does Kernel K-Means handle non-linearly separable data?	It transforms data into a space where clusters become linearly separable.
20	Can Kernel K-Means be applied to image segmentation?	Yes, Kernel K-Means is often used for image segmentation in computer vision.

Conclusion

K-Means and Kernel K-Means are powerful clustering techniques. While K-Means is efficient for well-separated clusters, Kernel K-Means extends its capabilities to complex structures using kernel functions. Understanding these algorithms helps in practical applications like image segmentation, anomaly detection, and recommendation systems.

By mastering these concepts, you will be well-prepared for exams and real-world clustering problems!