Kernel Normalized Cut: a Theoretical Revisit

Yoshikazu Terada, Michio Yamamoto
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6206-6214, 2019.

Abstract

In this paper, we study the theoretical properties of clustering based on the kernel normalized cut. Our first contribution is to derive a nonasymptotic upper bound on the expected distortion rate of the kernel normalized cut. From this result, we show that the solution of the kernel normalized cut converges to that of the population-level weighted k-means clustering on a certain reproducing kernel Hilbert space (RKHS). Our second contribution is the discover of the interesting fact that the population-level weighted k-means clustering in the RKHS is equivalent to the population-level normalized cut. Combining these results, we can see that the kernel normalized cut converges to the population-level normalized cut. The criterion of the population-level normalized cut can be considered as an indivisibility of the population distribution, and this criterion plays an important role in the theoretical analysis of spectral clustering in Schiebinger et al. (2015). We believe that our results will provide deep insights into the behavior of both normalized cut and spectral clustering.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-terada19a, title = {Kernel Normalized Cut: a Theoretical Revisit}, author = {Terada, Yoshikazu and Yamamoto, Michio}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {6206--6214}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/terada19a/terada19a.pdf}, url = {https://proceedings.mlr.press/v97/terada19a.html}, abstract = {In this paper, we study the theoretical properties of clustering based on the kernel normalized cut. Our first contribution is to derive a nonasymptotic upper bound on the expected distortion rate of the kernel normalized cut. From this result, we show that the solution of the kernel normalized cut converges to that of the population-level weighted k-means clustering on a certain reproducing kernel Hilbert space (RKHS). Our second contribution is the discover of the interesting fact that the population-level weighted k-means clustering in the RKHS is equivalent to the population-level normalized cut. Combining these results, we can see that the kernel normalized cut converges to the population-level normalized cut. The criterion of the population-level normalized cut can be considered as an indivisibility of the population distribution, and this criterion plays an important role in the theoretical analysis of spectral clustering in Schiebinger et al. (2015). We believe that our results will provide deep insights into the behavior of both normalized cut and spectral clustering.} }
Endnote
%0 Conference Paper %T Kernel Normalized Cut: a Theoretical Revisit %A Yoshikazu Terada %A Michio Yamamoto %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-terada19a %I PMLR %P 6206--6214 %U https://proceedings.mlr.press/v97/terada19a.html %V 97 %X In this paper, we study the theoretical properties of clustering based on the kernel normalized cut. Our first contribution is to derive a nonasymptotic upper bound on the expected distortion rate of the kernel normalized cut. From this result, we show that the solution of the kernel normalized cut converges to that of the population-level weighted k-means clustering on a certain reproducing kernel Hilbert space (RKHS). Our second contribution is the discover of the interesting fact that the population-level weighted k-means clustering in the RKHS is equivalent to the population-level normalized cut. Combining these results, we can see that the kernel normalized cut converges to the population-level normalized cut. The criterion of the population-level normalized cut can be considered as an indivisibility of the population distribution, and this criterion plays an important role in the theoretical analysis of spectral clustering in Schiebinger et al. (2015). We believe that our results will provide deep insights into the behavior of both normalized cut and spectral clustering.
APA
Terada, Y. & Yamamoto, M.. (2019). Kernel Normalized Cut: a Theoretical Revisit. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:6206-6214 Available from https://proceedings.mlr.press/v97/terada19a.html.

Related Material