Supplementary material to "Consistent Minimization of Clustering Objective Functions"
Ulrike von Luxburg, Max Planck, Stefanie Jegelka, M. Kaufmann · 2007
This paper contains supplementary material to the paper “Consistent Minimization of Clustering Objective Functions”, published at NIPS 2007 (von Luxburg et al., to appear). In particular, this supplement contains detailed proofs of all the theorems. For the general background please see von Luxburg et al. (to appear). An extended version which combines most of the NIPS paper and this supplement, and contains more general results and a more elegant approach to the proofs is available as a preprint (Bubeck and von Luxburg, 2007). For readers who are interested in our results in general we suggest to read the preprint (Bubeck and von Luxburg, 2007) rather than this supplement. Readers who want to see the proofs of the theorems exactly as they have been formulated in the NIPS paper (von Luxburg et al., to appear) should read this supplement. 1 General setup and notation Intuitively, a clustering should discover “meaningful ” groups. As we think that those groups should be “connected ” in some sense, we will only consider clusterings which are continuous in a certain sense. More formally, we represent a clustering of X by a function from X to {1,..., K} which is almost surely