What are the hierarchical algorithms actually doing?
⃝c -Trenn, King’s College London 2
What quantity are these algorithms optimizing?
For flat clustering, algorithms designed to optimize some objective function
‚ Remember:
for flat clustering the goal was to find k points μ1 , . . . , μk that minimize, e.g.
1. k-medianobjective 2. k-meansobjective
Nˆ ̇ ÿ
mindpxi,μjq i“1 jPrks
Nˆ ̇2 ÿ
mindpxi,μjq i“1 jPrks
For hierarchical clustering, algorithms have been studied procedurally
‚ Thus,comparisonsbetweenhierarchicalclusteringalgorithmsareonlyqualitative!
⃝c -Trenn, King’s College London 3
What quantity are these algorithms optimizing?
For flat clustering, algorithms designed to optimize some objective function
‚ Remember:
for flat clustering the goal was to find k points μ1 , . . . , μk that minimize, e.g.
1. k-medianobjective 2. k-meansobjective
Nˆ ̇ ÿ
mindpxi,μjq i“1 jPrks
Nˆ ̇2 ÿ
mindpxi,μjq i“1 jPrks
For hierarchical clustering, algorithms have been studied procedurally
‚ Thus,comparisonsbetweenhierarchicalclusteringalgorithmsareonlyqualitative!
[Dasgupta ’16]
“The lack of an objective function has prevented a theoretical understanding”
Dasgupta introduced an objective function to model the hierarchical clustering problem
⃝c -Trenn, King’s College London 4
Dasgupta’s Cost Function
Input:aweightedsimilaritygraphG Edge weights represent similarities
Output: T a tree with leaves labelled by nodes of G
Cost of the output: Sum of the costs of the nodes of T Cost of a node N of the tree:
L “ tu | u is leaf of subtree rooted at NLu
R “ tv | v is leaf of subtree rooted at NRu
a 1 d 8 10 9 2 2
e
c77
f
…… N
The total cost is the sum of costs of all subtrees.
Intuition: Better to cut a high similarity edge at a lower
level
⃝c -Trenn, King’s College London
5
b
3
NL
…
Nr
…
costpN q “ p|L| ` |R|q ̈
ÿ
uPL vPR
similaritypu, vq
abc def
Results
News
Sci
Sports
CS
Phy
Hierarchical Clustering: Objective Functions and Algorithms
Vincent Cohen-Addad, , -Trenn, JACM 2019
⃝c -Trenn, King’s College London 6
Result 1: Is Dasgupta the only reasonable function?
We characterize the set of ‘good’ objective functions based on axioms. ‚ Disconnectedcomponentsmustbeseparatedfirst
‚ Symmetry
‚ Onlythe‘true’hierarchicalclusteringshouldminimizethecostfunction(ifthereis
one).
In some sense Dasgupta is the most natural
⃝c -Trenn, King’s College London 7
Result 2: Algorithms
⃝c -Trenn, King’s College London 8
Hope: Recursive Sparsest Cut
Dissimilarity graph:
‚ We show Avg. Linkage has a 3{2-approximation factor
‚ WealsoshowthatotherpracticalalgorithmshaveaΩpn1{4q-approximationfactor
⃝c -Trenn, King’s College London 9
Hope: Recursive Sparsest Cut
Dissimilarity graph:
‚ We show Avg. Linkage has a 3{2-approximation factor
‚ WealsoshowthatotherpracticalalgorithmshaveaΩpn1{4q-approximationfactor
Similarity graph:
Algorithm: Recursive Sparsest Cut
Input: Weighted graph G “ pV, E, wq
tA, V zAu Ð cut with sparsity ď φ ̈ min wpS, V zSq
SĎV |S| ̈ |V zS|
Recurse on subgraphs GrAs, GrV zAs to obtain trees TA, TV zA
Output: Return tree whose root has subtrees TA, TV zA
⃝c -Trenn, King’s College London 10
Hope: Recursive Sparsest Cut
Dissimilarity graph:
‚ We show Avg. Linkage has a 3{2-approximation factor
‚ WealsoshowthatotherpracticalalgorithmshaveaΩpn1{4q-approximationfactor
Similarity graph:
Algorithm: Recursive Sparsest Cut
Input: Weighted graph G “ pV, E, wq
tA, V zAu Ð cut with sparsity ď φ ̈ min wpS, V zSq
SĎV |S| ̈ |V zS|
Recurse on subgraphs GrAs, GrV zAs to obtain trees TA, TV zA
Output: Return tree whose root has subtrees TA, TV zA
‚ WeshowOpφq-approximation
‚ ImprovestheOplogn ̈φq-approximation[Dasgupta’16] ‚ CurrentbestknownvalueforφisOp?lognq[ARV’09]
⃝c -Trenn, King’s College London 11
For worst case inputs, Recursive Sparsest Cut gives Opφq-approximation Assuming the “Small Set Expansion Hypothesis”, no polytime Op1q-approx.
Real-world graphs are often not worst-case
⃝c -Trenn, King’s College London 12