Partitions in Clustering
Kleinberg's work is presented as an axiomatic attempt to define clustering.
Why Define Clustering Axiomatically
Clustering is often introduced as a collection of algorithms. An axiomatic approach steps back from any one algorithm and asks a more basic question: what should it mean for a result to count as clustering? Kleinberg's work is presented as an attempt to answer that question by describing desired principles for the behavior of a clustering procedure.
The purpose of the axiomatic view is to evaluate clustering at the level of its intended behavior rather than only at the level of implementation. Instead of beginning with a particular algorithm, the approach begins with principles that a clustering procedure should satisfy. These principles are then used to describe what the procedure should do.
The Formal Input and Output
Kleinberg's formal setup uses a finite domain X and a dissimilarity function d defined over pairs of elements in X. A clustering function F consumes X and d together. Its output is a partition of X.
The overall shape is F(X, d) = a partition of X. Here, X and d are the inputs, while F is the procedure that consumes them and the partition is the result.
Three Objects with Different Roles
The notation separates three ideas that are easy to blur together. The domain X is the finite collection of elements being clustered. The dissimilarity function d supplies dissimilarity information for pairs of elements in X. The partition is the grouping of the elements of X produced as the result.
| Object | Role |
|---|---|
| Domain X | The finite set of elements under consideration |
| Dissimilarity function d | A function over pairs of elements in X |
| Clustering function F | The function that consumes X and d |
| Partition | The result returned for X |
The formal setup keeps the inputs, procedure, and result distinct.
A Small Abstract Instance
Tracing the formal setup
Consider a generated example with a finite domain X containing four elements. Suppose a dissimilarity function d is supplied for pairs of those elements. What does the clustering function receive, and what kind of result does it return?
Name the domain: The finite collection of four elements is X. It identifies which objects are available to be clustered.
Identify the dissimilarity information: The function d is defined over pairs of elements in X. It provides the dissimilarity input associated with those pairs.
Apply the clustering function: The clustering function F consumes X together with d. F is not the same object as d; it is the function that uses both formal inputs.
Read the result: The output is a partition of X: the four domain elements are organized into clusters that together represent the clustering result.
The formal trace is: finite domain X plus dissimilarity function d are provided to F, and F returns a partition of X.
This example illustrates the roles without requiring particular numerical dissimilarity values. X identifies the objects, d describes the pairwise dissimilarity input, F performs the clustering transformation, and the partition expresses how X has been divided into clusters.
F and d Are Not Interchangeable
The symbols F and d refer to different kinds of things. The dissimilarity function d operates over pairs of elements in X and supplies dissimilarity information. The clustering function F consumes the domain X and the dissimilarity function d together, then returns a partition of X.
| Question | dissimilarity function d | clustering function F |
|---|---|---|
| What does it operate on? | Pairs of elements in X | The domain X together with d |
| What role does it play? | Supplies dissimilarity information | Produces the clustering result |
| What is its formal output? | Dissimilarity information for pairs | A partition of X |
Common Conceptual Mistakes
Treating d as the clustering function.
d is the dissimilarity function over pairs of elements in X. F is the function that consumes X and d and returns a partition.
Fix:
Reserve d for pairwise dissimilarity information and F for the clustering transformation.Treating F as if it only receives d.
The formal setup states that F consumes X and d together.
Fix:
Name both inputs: the finite domain X and the dissimilarity function d.Confusing the partition with the domain.
X is the finite domain of elements being clustered, while the partition is the result returned for X.
Fix:
Keep the input set X separate from the partition that divides its elements into clusters.Starting with an algorithm instead of the axiomatic question.
The axiomatic approach asks what should count as clustering independently of one particular algorithm.
Fix:
Begin with the desired principles for clustering behavior, then relate the formal function to those principles.
Check Your Understanding
In your own words, trace the formal setup from inputs to output. Identify what X contains, what d is defined over, what F consumes, and what F returns. Then explain in one sentence why d and F cannot be used interchangeably.
Hints
- Start with the phrase finite domain.
- Remember that d is defined over pairs of elements in X.
- The output is a partition of X.
- The essential trace is: X identifies a finite domain, d supplies dissimilarity information over pairs in X, F consumes X and d, and F returns a partition of X.
Key Takeaways
- An axiomatic approach asks what should count as clustering independently of one particular algorithm.
- The formal inputs are a finite domain X and a dissimilarity function d over pairs of elements in X.
- The clustering function F consumes X and d together.
- The output of F is a partition of X.
- d supplies pairwise dissimilarity information, whereas F produces the grouping.