Maximum volume clustering
Gang Niu, Bo Dai, Lin Shang, Masashi Sugiyama · 2011
The large volume principle proposed by Vladimir Vapnik, which advocates that hy-potheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a clustering model based on the large volume principle called maximum volume clustering (MVC), and propose two algorithms to solve it approxi-mately: a soft-label and a hard-label MVC al-gorithms based on sequential quadratic pro-gramming and semi-definite programming, respectively. Our MVC model includes spec-tral clustering and maximum margin cluster-ing as special cases, and is substantially more general. We also establish the finite sample stability and an error bound for soft-label MVC method. Experiments show that the proposed MVC approach compares favorably with state-of-the-art clustering algorithms. 1