Accession Number:

AD1003390

Title:

Modified Cheeger and Ratio Cut Methods Using the Ginzburg-Landau Functional for Classification of High-Dimensional Data

Descriptive Note:

Technical Report

Corporate Author:

University of California, Los Angeles Los Angeles United States

Personal Author(s):

• Merkurjev,Ekaterina
• Bertozzi,Andrea
• Yan,Xiaoran
• Lerman,Kristina

Report Date:

2016-02-01

Pagination or Media Count:

26.0

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.

Descriptors:

• classification
• clustering
• graphs
• algorithms
• video images
• hyperspectral imagery

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE