Title: A MinMaxCut Spectral Method for Data Clustering and Graph Partitioning
Abstract: The goal of data clustering can be formally stated as a min-max clustering principle: data points are grouped into clusters such that (a) between-cluster similarities are minimized while (b) within-cluster similarities are maximized. Existing methods typically focus on one of the above requirements. Here we propose a new method that emphasizes both requirements simultaneously. The MinMaxCut method uses pairwise similarities between all data objects. Viewing them as the adjacency matrix of a weighted graph, MinMaxCut is a graph partitioning method. An important feature is that the continuous solution of the cluster membership indicator vector is the eigenvector of the generalized graph Laplacian matrix; this simplifies the optimization of the min-max clustering objective function. We provide a comprehensive analysis of this principled clustering method; a systematic evaluation on clustering experiments on Internet newsgroups indicates that MinMaxCut outperforms other current popular partitioning/clustering methods.
Publication Year: 2003
Publication Date: 2003-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 21
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot