Partitions in Clustering
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.
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?
- 1Name the domain
The finite collection of four elements is X. It identifies which objects are available to be clustered.
- 2Identify the dissimilarity information
The function d is defined over pairs of elements in X. It provides the dissimilarity input associated with those pairs.
- 3Apply 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.
- 4Read 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 |
d provides part of the input; F transforms the inputs into a partition.
Common Conceptual Mistakes
Common mistake Treating d as the clustering function.
What it looks likeCalling d the procedure that returns the final clusters.
Why it failsd is the dissimilarity function over pairs of elements in X. F is the function that consumes X and d and returns a partition.
Do this insteadReserve d for pairwise dissimilarity information and F for the clustering transformation.
Common mistake Treating F as if it only receives d.
What it looks likeWriting the setup as though the dissimilarity function were the only input.
Why it failsThe formal setup states that F consumes X and d together.
Do this insteadName both inputs: the finite domain X and the dissimilarity function d.
Common mistake Confusing the partition with the domain.
What it looks likeUsing X to refer to the output grouping.
Why it failsX is the finite domain of elements being clustered, while the partition is the result returned for X.
Do this insteadKeep the input set X separate from the partition that divides its elements into clusters.
Common mistake Starting with an algorithm instead of the axiomatic question.
What it looks likeDefining clustering only as a list of algorithm steps.
Why it failsThe axiomatic approach asks what should count as clustering independently of one particular algorithm.
Do this insteadBegin 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.
- 1The 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.