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.