Timezone: »

 
Poster
Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel
Weixuan Liang · Xinwang Liu · Yong Liu · sihang zhou · Jun-Jie Huang · Siwei Wang · Jiyuan Liu · Yi Zhang · En Zhu

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #538
in Poster Session 1 »
Multiple kernel clustering (MKC) is an important research topic that has been widely studied for decades. However, current methods still face two problems: inefficient when handling out-of-sample data points and lack of theoretical study of the stability and generalization of clustering. In this paper, we propose a novel method that can efficiently compute the embedding of out-of-sample data with a solid generalization guarantee. Specifically, we approximate the eigen functions of the integral operator associated with the linear combination of base kernel functions to construct low-dimensional embeddings of out-of-sample points for efficient multiple kernel clustering. In addition, we, for the first time, theoretically study the stability of clustering algorithms and prove that the single-view version of the proposed method has uniform stability as $\mathcal{O}\left(Kn^{-3/2}\right)$ and establish an upper bound of excess risk as $\widetilde{\mathcal{O}}\left(Kn^{-3/2}+n^{-1/2}\right)$, where $K$ is the cluster number and $n$ is the number of samples. We then extend the theoretical results to multiple kernel scenarios and find that the stability of MKC depends on kernel weights. As an example, we apply our method to a novel MKC algorithm termed SimpleMKKM and derive the upper bound of its excess clustering risk, which is tighter than the current results. Extensive experimental results validate the effectiveness and efficiency of the proposed method.
Keywords: Clustering · kernel method · algorithmic stability

Author Information

Weixuan Liang (National University of Defense Technology)
Xinwang Liu (National University of Defense Technology)
Yong Liu (Renmin University of China)
sihang zhou (National University of Defense Technology)
Jun-Jie Huang (National University of Defense Technology)
Siwei Wang (NUDT)
Jiyuan Liu (National University of Defense Technology)
Yi Zhang (NUDT)
En Zhu (National University of Defense Technology)

More from the Same Authors