Modified Cheeger and Ratio Cut Methods Using the Ginzburg-Landau Functional for Classification of High-Dimensional Data
Abstract
Recent advances in clustering have included continuous relaxations of the Cheeger cut problem and those which address its linear approximation using the graph Laplacian. In this paper, we show how to use the graph Laplacian to solve the fully nonlinear Cheeger cut problem, as well as the ratio cut optimization task. Both problems are connected to total variation minimization, and the related Ginzburg-Landau functional is used in the derivation of the methods. The graph framework discussed in this paper is undirected. The resulting algorithms are efficient ways to cluster thedata into two classes, and they can be easily extended to case of multiple classes, or used on a multiclass data set via recursive bipartitioning. In addition to showing results on benchmark data sets, we also show an application of the algorithm to hyperspectral video data.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 2016
- Accession Number
- AD1003390
Entities
People
- Andrea Bertozzi
- Ekaterina Merkurjev
- Kristina Lerman
- Xiaoran Yan
Organizations
- University of California