Generalized transitive distance with minimum spanning random forest
Zhiding Yu, Weiyang Liu, Wenbo Liu, Xi Peng, Zhuo Hui, B. V. K. Vijaya Kumar · 2015
Transitive distance is an ultrametric with elegant properties for clustering. Conventional transitive distance can be found by referring to the mini-mum spanning tree (MST). We show that such dis-tance metric can be generalized onto a minimum s-panning random forest (MSRF) with element-wise max pooling over the set of transitive distance ma-trices from an MSRF. Our proposed approach is both intuitively reasonable and theoretically attrac-tive. Intuitively, max pooling alleviates undesired short links with single MST when noise is present. Theoretically, one can see that the distance metric obtained max pooling is still an ultrametric, render-ing many good clustering properties. Comprehen-sive experiments on data clustering and image seg-mentation show that MSRF with max pooling im-proves the clustering performance over single MST and achieves state of the art performance on the Berkeley Segmentation Dataset. 1