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 |
The symbols describe different stages and roles in the formal 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.
- 1Identify the domain
X is the finite collection of four elements that will be organized by the clustering procedure.
- 2Identify 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.
- 3Apply 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.
- 4Read 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
Common mistake Treating d as the clustering function
What it looks likeSaying that d takes X and returns the 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 insteadDescribe d as supplying pairwise dissimilarity information and F as producing the partition.
Common mistake Forgetting that F receives two inputs
What it looks likeDescribing F as operating on d alone
Why it failsThe formal setup states that F consumes X and d together.
Do this insteadName both the finite domain X and the dissimilarity function d when describing the inputs to F.
Common mistake Confusing the domain with the partition
What it looks likeCalling X the groups returned by the clustering function
Why it failsX is the finite domain of elements being clustered. The partition of X is the output returned by F.
Do this insteadUse X for the elements available at the start and partition of X for the resulting grouping.
Common mistake Reducing the axiomatic approach to a particular algorithm
What it looks likeExplaining only how one clustering algorithm behaves
Why it failsThe axiomatic approach asks what should count as clustering independently of one particular algorithm.
Do this insteadFocus 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
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
- 1An axiomatic approach asks what should count as clustering independently of one particular algorithm.
- 2The formal setup uses a finite domain X and a dissimilarity function d over pairs of elements in X.
- 3The clustering function F consumes X and d together.
- 4F returns a partition of X.
- 5d supplies pairwise dissimilarity information; F produces the resulting grouping.
At a glance
- 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.