Dissimilarity Functions
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.
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?
- 1Step 1: Identify X
X is the finite domain: the collection of elements being considered.
- 2Step 2: Identify d
d is the dissimilarity function. It is defined over pairs of elements in X, so it supplies pairwise dissimilarity information.
- 3Step 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.
- 4Step 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 |
The dissimilarity function and clustering function are different objects with different roles.
Common Category Errors
Common mistake Treating d as the clustering algorithm.
What it looks likeCalling d the function that returns the clustering.
Why it failsd is the dissimilarity function over pairs of elements in X. F is the clustering function that consumes X and d.
Do this insteadReserve d for pairwise dissimilarity information and F for the function that returns a partition.
Common mistake Listing only d as the input to F.
What it looks likeWriting that F consumes d but not X.
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 Calling the partition an input.
What it looks likeDescribing the partition of X as something supplied to F.
Why it failsThe partition is the output returned by F.
Do this insteadDescribe the direction as X and d going into F, with a partition of X coming out.
Common mistake Defining clustering by one algorithm only.
What it looks likeAssuming that a clustering definition must be tied to a particular algorithm.
Why it failsThe axiomatic approach asks what should count as clustering independently of one particular algorithm.
Do this insteadFocus 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
F
F is the clustering function. It consumes X and d together and returns a partition of X.
Key Takeaways
- 1An axiomatic approach describes what clustering should mean through desired principles rather than through 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, while F uses the formal inputs to produce the clustering output.
At a glance
- 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.