Introduction to Clustering

The Clustering Tension

Clustering sounds simple: place similar objects together and keep dissimilar objects apart. The difficulty is that these two goals can conflict. Similarity can connect objects locally without connecting the endpoints of the whole chain. Cluster membership, however, carries through the chain. Understanding this difference is the key to understanding the central challenge of clustering.

A Chain of Local Similarities

The diagram shows three objects connected by neighboring similarities. The first pair, A and B, is similar. The second pair, B and C, is also similar. Nothing in these local relationships guarantees that A and C are similar. They can be dissimilar even though each is similar to the object next to it.

Similarity Is Not Transitive

A relationship is transitive when a relationship from A to B and the same relationship from B to C guarantees that the relationship also holds from A to C. Similarity does not necessarily work this way. A can be similar to B, and B can be similar to C, without A being similar to C. Similarity can therefore form a chain whose endpoints are very dissimilar.

Cluster Sharing Carries Through

Cluster sharing behaves differently from similarity. If A shares a cluster with B, and B shares a cluster with C, then A and C share that cluster as well. This transitive property applies to the act of sharing a cluster, even when similarity itself is not transitive.

Once the similar pair A and B is assigned to one cluster, and the similar pair B and C is assigned to one cluster, B connects those assignments. The result is a shared cluster containing A, B, and C. This does not change the fact that A and C may be dissimilar; it shows that cluster membership can extend farther than direct similarity.

The Forced Decision

Practical Clustering Judgment

When analyzing a clustering decision, inspect both kinds of relationships. First ask which similar neighboring objects the grouping keeps together. Then ask whether transitive cluster sharing has brought dissimilar endpoints into the same group. This makes the trade-off visible instead of treating a cluster as proof that every pair inside it is directly similar.

• Assuming that similarity is transitive.

  The source concept states that similarity is non-transitive. Local similarity does not guarantee similarity between the endpoints.

  Fix: Treat each similarity relationship as local unless the clustering method provides another reason to connect the objects.

• Assuming that objects in one cluster must all be directly similar to one another.

  A and C can be connected through B even when A and C are dissimilar.

  Fix: Distinguish direct similarity from sharing a cluster.

• Expecting both clustering objectives to be satisfied perfectly in every chain.

  The two requirements can contradict each other when a chain connects locally similar pairs to dissimilar endpoints.

  Fix: Recognize that a clustering method must choose how to balance the competing objectives.

Check Your Reasoning

What to Remember

1. Similarity is non-transitive: A can be similar to B and B can be similar to C without A being similar to C.
2. Sharing a cluster is transitive: if A shares a cluster with B and B shares a cluster with C, A and C share that cluster.
3. A chain of neighboring similarities can connect very dissimilar endpoints within one cluster.
4. Keeping all similar pairs together can conflict with keeping all dissimilar pairs apart.
5. Clustering is therefore a balancing decision between preserving local similarity and separating dissimilar objects.