Large-scale clustering is a challenging problem for many modern clustering algorithms. The majority of approaches reduce the clustering problem to the optimization problem, which is non-linear, multi-dimensional, and multi-extreme. Evolutionary algorithm based clustering is known as one of the most efficient approaches. Nevertheless, many modern evolutionary algorithms demonstrate low performance when solving large-scale global optimization problems. In this paper, we propose an approach for solving large-scale clustering problems using decomposition-based evolutionary algorithms. We have compared the performance of the standard k-means, k-means++, and the proposed CC-SHADE and CC-SHADE-RAG2 algorithms using benchmark problems with 16 clusters and 512 and 1024 attributes (the corresponding optimization problems use 8192 and 16384 objective variables). The experimental results show the decomposition-based approaches essentially outperform the standard evolutionary and k-means clustering algorithms.