Concave Cut: Analyzing the role of concave functions in clustering

To broaden the application of clustering for large-scale datasets, we propose a graph cut framework called Concave-Cut for the scenario with a large scale sample size and a high number of clusters. (defined as the BL-scenario). In Concave-Cut, high quality partitions can be obtained directly by maximizing the compactness of each cluster, without additional regularization or hyper-parameter. Our framework has a concise form, which facilitates the designed optimization algorithm to perform efficiently. Our algorithm can be optimized in linear time with respect to the number of samples n, and its complexity is independent of the number of clusters c. Specifically, the algorithm achieves a time complexity of O(nk) where k denotes the number of neighbors per sample, making it highly efficient for applications in BL-scenario. We conduct a series of experiments on 11 synthetic datasets, and 14 middle, and 10 large scale real-world datasets. The experimental results verify the superiority of the proposed Concave-Cut, especially in BL-scenario.