Self-validation and efficient global optimization are two important objectives for feature space clustering. The Gibbs energy minimization of Markov random field (MRF) provides a general framework for the clustering problem. However, the large computational burdenmakes mostMRFbased methods cannot efficiently achieve these two targets simultaneously. In this paper, we propose a fast clustering approach which is self-validated and guarantees stepwise global optimum. We use the net-structured MRF (NS-MRF) to model the feature space and present an iterative cluster evolution algorithm. For each iteration, the cluster evolving is chosen from three hypotheses, i.e., cluster remaining, cluster merging or cluster splitting, in terms of energy minimization. Graph cuts are used to obtain the optimal binary splitting while taking spatial coherence into account. We terminate the evolution process when the whole energy of NS-MRF stops decreasing, thus solve the validation problem. We also provide experimental results and compare our approach with the state of arts.