14.1 Clustering Fundamentals
What is Clustering?
Clustering is a fundamental task in unsupervised machine learning. The goal is to group a set of objects in such a way that objects in the same group (called a cluster) are more similar to each other than to those in other groups. It's a primary tool for data exploration and analysis, helping to uncover hidden structures in data.
Unlike supervised learning, clustering algorithms work with unlabeled data, meaning we don't have a predefined outcome or target variable. The algorithm itself must discover the groupings.
Types of Clustering Algorithms
There are many different ways to approach clustering, each with its own strengths and weaknesses. The main categories include:
- Centroid-based Clustering: Organizes data into non-hierarchical clusters. The most famous example is K-Means, where each cluster is represented by a single mean vector (a centroid).
-
Hierarchical Clustering: Creates a tree of clusters. This can be done in two ways:
- Agglomerative: A "bottom-up" approach where each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
- Divisive: A "top-down" approach where all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.
- Density-based Clustering: Connects areas of high density into clusters. This allows for arbitrarily-shaped clusters and is good at finding outliers. DBSCAN is a popular example.
- Distribution-based Clustering: Assumes that data is composed of a mixture of distributions (e.g., Gaussian distributions). Clusters are then found by identifying the parameters of these distributions.
Measuring Similarity: Distance Metrics
The notion of "similarity" is at the heart of clustering. We quantify it using a distance metric. The choice of metric is crucial and depends on the nature of the data.
1. Euclidean Distance
This is the most common distance metric, representing the straight-line distance between two points in Euclidean space. For two points \(p\) and \(q\) in an n-dimensional space, it is defined as:
\(d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}\)
Euclidean distance is sensitive to the scale of the features, so it's often important to normalize the data before applying it.
2. Manhattan Distance
Also known as the "city block" distance, this metric calculates the sum of the absolute differences of the coordinates. It's the distance you would travel between two points in a city laid out in a grid.
\(d(p, q) = \sum_{i=1}^{n} |p_i - q_i|\)
It is less sensitive to outliers than Euclidean distance.
3. Cosine Similarity
This metric measures the cosine of the angle between two vectors. It is not a measure of distance, but of similarity. It is particularly useful for text data represented as word count vectors, where the magnitude of the vector might not be as important as its direction.
\(\text{similarity}(A, B) = \cos(\theta) = \frac{A \cdot B}{\|A\| \|B\|} = \frac{\sum_{i=1}^{n} A_i B_i}{\sqrt{\sum_{i=1}^{n} A_i^2} \sqrt{\sum_{i=1}^{n} B_i^2}}\)
A value of 1 means the vectors are identical in orientation, 0 means they are orthogonal, and -1 means they are diametrically opposed.
Evaluating Clustering Performance
Evaluating the quality of a clustering result can be challenging, especially since we don't have ground truth labels. However, there are several metrics we can use:
- Silhouette Score: Measures how similar an object is to its own cluster compared to other clusters. The score ranges from -1 to 1, where a high value indicates that the object is well matched to its own cluster and poorly matched to neighboring clusters.
- Davies-Bouldin Index: This index signifies the average similarity between clusters, where the similarity is a measure that compares the distance between clusters with the size of the clusters themselves. A lower value means better clustering.
- Calinski-Harabasz Index: Also known as the Variance Ratio Criterion, it is the ratio of the sum of between-cluster dispersion and of inter-cluster dispersion for all clusters. A higher score indicates better-defined clusters.
These metrics help in choosing the optimal number of clusters and in comparing different clustering algorithms.