Axiomatic Definitions
Kleinberg's work is presented as an axiomatic attempt to define clustering.
From Algorithms to Principles
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 using desired principles, or axioms, to describe what a clustering procedure should do.
The Formal Ingredients
Kleinberg's formal setup has three important pieces. First is a finite domain X: the collection of elements being clustered. Second is a dissimilarity function d over pairs of elements in X: it supplies the dissimilarity information for pairs of data points. Third is the clustering function F. F consumes X and d together and returns a partition of X.
Following the Information
The information flow is easier to understand when each symbol keeps its own job. X identifies what is available to be clustered. d describes the dissimilarity relation for pairs from X. F is the operation that consumes both pieces together. Its output is not another pairwise dissimilarity description; its output is a partition of the entire domain X.
| Symbol | Role | What it is not |
|---|---|---|
| X | The finite domain of elements being clustered | Not the clustering result |
| d | The dissimilarity function over pairs of elements in X | Not the function that returns groups |
| F | The clustering function that consumes X and d | Not the pairwise dissimilarity information |
| Partition of X | The result returned by F | Not an input to F in this setup |
A Symbolic Walkthrough
Tracing X, d, and F
Suppose a finite domain contains four elements: X = {a, b, c, d}. Describe what each part of the axiomatic setup represents without assigning particular dissimilarity values.
Identify the domain: X is the finite collection of four elements that will be organized by the clustering procedure.
Identify the pairwise information: The dissimilarity function d is considered over pairs of elements from X, such as the pair a and b or the pair c and d. The example does not need to assign numerical values to those pairwise dissimilarities.
Apply the clustering function: F consumes the domain X together with the dissimilarity function d. F is therefore different from d: d supplies dissimilarity information, while F performs the clustering operation in the formal setup.
Read the result: The output is a partition of X. In other words, the four elements are represented as resulting groups rather than as a new list of pairwise dissimilarities.
The formal flow is: finite domain X plus dissimilarity function d, consumed together by F, producing a partition of X.
The most important trace to remember is not d produces groups. It is X and d enter F, and F returns a partition of X.
Common Category Errors
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:
Describe d as supplying pairwise dissimilarity information and F as producing the partition.Forgetting that F receives two inputs
The formal setup states that F consumes X and d together.
Fix:
Name both the finite domain X and the dissimilarity function d when describing the inputs to F.Confusing the domain with the partition
X is the finite domain of elements being clustered. The partition of X is the output returned by F.
Fix:
Use X for the elements available at the start and partition of X for the resulting grouping.Reducing the axiomatic approach to a particular algorithm
The axiomatic approach asks what should count as clustering independently of one particular algorithm.
Fix:
Focus on desired principles that describe what a clustering procedure should do.
Check Your Understanding
In one or two sentences, explain the difference between d and F. Then identify the input and output in the expression-like description: F consumes X and d.
Hints
- Ask whether the symbol describes pairs or produces groups.
- Remember that X is the finite domain and the output is a partition of X.
What do you think happens?
If a description says that a function returns a partition of X, is that function playing the role of d or F?
Reveal answer
Answer: F
d is the dissimilarity function over pairs of elements in X. F consumes X and d and returns a partition of X.
Key Takeaways
- An axiomatic approach asks what should count as clustering independently of one particular algorithm.
- The formal setup uses a finite domain X and a dissimilarity function d over pairs of elements in X.
- The clustering function F consumes X and d together.
- F returns a partition of X.
- d supplies pairwise dissimilarity information; F produces the resulting grouping.
Key Takeaways
- An axiomatic approach defines the desired behavior of clustering through principles rather than starting with one particular algorithm.
- X is the finite domain of elements to be clustered.
- d is the dissimilarity function over pairs of elements in X.
- F consumes X and d and returns a partition of X.
- The clustering function F and the dissimilarity function d have different roles: d describes pairwise dissimilarity, while F produces groups.