Optimum cut-based clustering

This paper presents a new method for solving clustering problem. We treat clustering as a graph-partitioning problem and propose a new global criterion, the optimum cut, for segmenting the graph. An important feature is that optimizing the optimum cut criterion can ensure that the intra-cluster similarity is maximized while the inter-cluster similarity is minimized. We show that an efficient computational technique based on an eigenvalue problem can be used to optimize this criterion. The experimental results on a number of hard artificial and real-world data sets show the effectiveness of the approach.