Graph K-means with lost cluster approach for nonlinear manifold clustering

Recently, Graph K-means (GKM) algorithm can attain better performances than other state-of-the-art approaches in nonlinear manifold clustering. However, when the data set has many clusters and the number of samples in each cluster is small, GKM might not perform well. In these cases, the final partition does not have enough clusters as the initial number of clusters, called the lost cluster problem. To overcome this disadvantage, we propose a solution having two steps: (1) determine the right cluster which absorbs other clusters, (2) find the centroid which can be used to recover the lost cluster. The experimental results of two well-known face data sets (ORL and CMU PIE) show that our solution is stable and efficient.