Kernel normalized cut: A theoretical revisit

Yoshikazu Terada, Michio Yamamoto

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Citation (Scopus)

    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.

    Original languageEnglish
    Title of host publication36th International Conference on Machine Learning, ICML 2019
    PublisherInternational Machine Learning Society (IMLS)
    Pages10817-10825
    Number of pages9
    ISBN (Electronic)9781510886988
    Publication statusPublished - 2019
    Event36th International Conference on Machine Learning, ICML 2019 - Long Beach, United States
    Duration: Jun 9 2019Jun 15 2019

    Publication series

    Name36th International Conference on Machine Learning, ICML 2019
    Volume2019-June

    Conference

    Conference36th International Conference on Machine Learning, ICML 2019
    Country/TerritoryUnited States
    CityLong Beach
    Period6/9/196/15/19

    ASJC Scopus subject areas

    • Education
    • Computer Science Applications
    • Human-Computer Interaction

    Fingerprint

    Dive into the research topics of 'Kernel normalized cut: A theoretical revisit'. Together they form a unique fingerprint.

    Cite this