Modified Cheeger and ratio cut methods using the Ginzburg–Landau functional for classification of high-dimensional data. (21st June 2017)

• Record Type: Journal Article
• Authors: Merkurjev, Ekaterina; Bertozzi, Andrea; Yan, Xiaoran; Lerman, Kristina
• Is Part Of: Inverse problems. Volume 33:Number 7(2017:Jul.)
• Publication Date: 2017-06-21
• Subjects: classification -- spectral clustering -- Cheeger cut -- ratio cut -- graphs -- Ginzburg–Landau functional -- total variation; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/1361-6420/33/7/074003
• Languages: English
• ISSNs: 0266-5611

Abstract

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 the data into two classes, and they can be easily extended to the 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.