TMM Clustering
Notes for knowledge clip about clustering.
Overall purpose: discover new categories in an unsupervised manner.
Can be used for:
- Organization
- Summarization
- Navigation
- Retrieval
Clustering bias
Our clustering is biased by how we define similarity. So our definition of similarity must be well-defined and we must understand its implications.
Clustering will always give back some structure. But the question is: is that structure meaningful? And how does it compare to alternative structures?
Cf. 14.1 in Eisenstein.
Hierarchical clustering
Hierarchical clustering is the recursive application of clustering that results in a taxonomy.
Taxonomy vs. typology:
A taxonomy: dimensions are based on observations of things in the real world.
Typology: dimensions represent ideal concepts.
Agglomerative vs. Divisive Hierarchical Clustering
Agglomerative is bottom-up; single example clusters, then combine clusters.
Divisive: start with a single big cluster, start splitting up into component subclusters.
Our algorithms usually require specification of k clusters.
Either set manually; or try multiple K and determine the best one with a cluster evaluation function.
Soft clustering
Regular "hard" clustering does not allow for uncertainty in class membership.
We can also generate probabilities that an instance belongs to a cluster. Based on these you can still make a hard decision, or allow instances to be members of multiple clusters, which is soft clustering.
K-means clustering (non-hierarchical)
K-means: non-hierarchical clustering algorithm.
- Assign instances to clusters
- Cluster represented by cluster centroid.
- Seeds: choose initial centroids
- Assign instances clusters with closest centroid
- Similarity is cosine similarity (distance: 1-cosine similarity)
- Recompute the centroids
- Iterate
Challenges:
- K-means is very sensitive to the choice of seeds.
- some seeds lead to very poor convergence, or convergence to suboptimal clusters.
- In other words, for the choice of seeds we use a heuristic or the outcome of another clustering method.
- Sensitive to noise and outliers
- Think about scalability
K-means can only end up in linear separations between clusters.
Cluster evaluation
Internal measure: combines inter and intra cluster distances
A good clustering has:
- Minimized intra-cluster distance: sum of distances between objects in one cluster is minimized; i.e. cluster is as tighly packed and coherent as possible
- Inter-cluster distance: maximize distance between clusters, i.e. make sure they are as distinguished from one another as possible.
External measure: how representative is your clustering, relative to true classes?
- Purity
- Entropy
- F-measure
- rand-index
Purity
This one works without access to the ground truth.
Number of items of the majority class in a cluster; then sum that; divide by the total number of datapoints.
Rand Index
Requires ground truth.
The Rand Index compares pairs of points in ground truth set X to pairs in the predicted set Y.
True positive TP: If points x1 and x2 are in the same class in the ground truth, are they in the same cluster in Y?
True negative: If points x1 and x2 are in different classes in the ground truth, are they also in different clusters in Y?
RI = (TP + TN ) / (TP + FN + FP + TN)
So the difference with accuracy is that we now take into account pairs of points.
We have N choose 2 pairs for N data points.
Ideas on cluster evaluation
From Ulrike Von Luxburg, ACL 2014.
ML researchers make many new algorithms, but practitioners stick with k-means.
There are 5000+ clustering algorithms, we do not need more! What we need is better cluster evaluation methods.
There is no "proof" that one clustering is better than another. So there is a strong need for reliable methods, independent tests. Consider the real purpose in real cases and find a way to measure usefulness.
When we are doing TxMM we are looking for discovering knowledge. Here clusters can be incredibly useful to find patterns.