0.25
0.5
0.75
1.25
1.5
1.75
2
The stability of a good clustering
Published on Feb 25, 20075999 Views
If we have found a "good" clustering C of data set X, can we prove that C is not far from the (unknown) best clustering C* of this data set? Perhaps surprisingly, the answer to this question is someti
Related categories
Chapter list
The Stability of a Good Clustering00:05
Optimizing these criteria is NP-hard01:19
Results summary04:01
A graphical view05:25
A graphical view 0105:56
Overview06:09
The Confusion Matrix06:43
The Misclassification Error distance07:28
Representing clusterings as matrices08:52
Representing clusterings as subspaces10:27
Why K-1 dimensions? Intuition11:09
Distortion is quadratic in X13:28
Quadratic functions and the eigengap14:27
Quadratic functions and the eigengap 0114:55
Solve relaxed minimization17:10
Main Theorem20:42
Bound for d(X,Xopt)21:43
Extensions23:21
The normalized cut (Shi & Malik 99)23:42
An improved bound for NCut24:54
Experiments – bounds for best clustering26:36
Experiments – bounds for best clustering 0127:55
Experiments – random perturbation of Xopt29:07
Conclusions30:08