Normalized cuts clustering with prior knowledge and a pre-clustering stage. Peluffo-Ordoñez, D., Castro-Ospina, A., E., Chavez-Chamorro, D., Acosta-Medina, C., D., & Castellanos-Dominguez, G. In ESANN 2013 proceedings, 21st European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 2013.
Normalized cuts clustering with prior knowledge and a pre-clustering stage [pdf]Website  abstract   bibtex   
Clustering is of interest in cases when data are not labeled enough and a prior training stage is unfeasible. In particular, spectral clustering based on graph partitioning is of interest to solve problems with highly non-linearly separable classes. However, spectral methods, such as the well-known normalized cuts, involve the computation of eigenvectors that is a highly time-consuming task in case of large data. In this work, we propose an alternative to solve the normalized cuts problem for clustering, achieving same results as conventional spectral methods but spending less processing time. Our method consists of a heuristic search to find the best cluster binary indicator matrix, in such a way that each pair of nodes with greater similarity value are first grouped and the remaining nodes are clustered following a heuristic algorithm to search into the similarity-based representation space. The proposed method is tested over a public domain image data set. Results show that our method reaches comparable results with a lower computational cost.

Downloads: 0