Dissimilarity Functions
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 starts one level deeper. Instead of asking how one particular algorithm clusters data, it asks what a result should satisfy in order to count as clustering, independently of one particular algorithm. Kleinberg's work is presented as an attempt to give clustering this kind of axiomatic definition.
The Formal Setup
Kleinberg's formal setup has three distinct objects. First is a finite domain X. Second is a dissimilarity function d defined over pairs of elements in X. Third is the output: a partition of X. The clustering function F consumes the domain and the dissimilarity function together, so its inputs are X and d, and its output is a partition of X.
Tracing the Roles
Following One Formal Input
Suppose a finite domain is represented by X, and a dissimilarity function d is provided for pairs of elements in X. What role does each symbol play?
Step 1: Identify X: X is the finite domain: the collection of elements being considered.
Step 2: Identify d: d is the dissimilarity function. It is defined over pairs of elements in X, so it supplies pairwise dissimilarity information.
Step 3: Apply F: The clustering function F consumes X and d together. F is therefore the function that uses the formal setup rather than one of the pairwise inputs itself.
Step 4: Identify the result: The result returned by F is a partition of X.
The roles can be summarized as X for the finite domain, d for pairwise dissimilarity information, F for the clustering function, and a partition of X for the output.
This trace separates the input stage from the output stage. X and d are supplied to F. The partition is not another input to F in this setup; it is what F returns.
d Compared with F
| Object | Role | Relationship to X |
|---|---|---|
| d | Dissimilarity function | Defined over pairs of elements in X |
| F | Clustering function | Consumes X together with d |
| Partition | Clustering output | A partition of X |
Common Category Errors
Treating d as the clustering algorithm.
d is the dissimilarity function over pairs of elements in X. F is the clustering function that consumes X and d.
Fix:
Reserve d for pairwise dissimilarity information and F for the function that returns a partition.Listing only d as the input to F.
The formal setup states that F consumes X and d together.
Fix:
Name both inputs: the finite domain X and the dissimilarity function d.Calling the partition an input.
The partition is the output returned by F.
Fix:
Describe the direction as X and d going into F, with a partition of X coming out.Defining clustering by one algorithm only.
The axiomatic approach asks what should count as clustering independently of one particular algorithm.
Fix:
Focus on desired principles describing how a clustering procedure should behave.
Practice the Formal Mapping
Write a one-line description of the formal mapping in this setup. Your answer must name the two inputs, the function that consumes them, and the output.
Hints
- Start with the finite domain X.
- Add the dissimilarity function d defined over pairs in X.
- End with the partition of X returned by F.
What do you think happens?
If a description names X and d as inputs and a partition of X as the output, which symbol names the function performing that mapping?
Reveal answer
Answer: F
F is the clustering function. It consumes X and d together and returns a partition of X.
Key Takeaways
- An axiomatic approach describes what clustering should mean through desired principles rather than through 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, while F uses the formal inputs to produce the clustering output.
Key Takeaways
- An axiomatic approach asks what should count as clustering independently of one particular algorithm.
- X is a finite domain, and d is a dissimilarity function defined over pairs of elements in X.
- F is the clustering function that consumes X and d.
- The output of F is a partition of X.
- The symbols d and F have different roles: d provides pairwise dissimilarity information, whereas F produces the clustering result.