Abstract Consensus clustering emerges as a promising solution to ?nd cluster structures from data. As an ef?cient approach for consensus clustering, the Kmeans based method has garnered attention in the literature, but the existing research is still preliminary and fragmented. In this paper, we provide a systematic study on the framework of K-meansbased Consensus Clustering (KCC). We ?rst formulate the general de?nition of KCC, and then reveal a necessary and suf?cient condition for utility functions that work for KCC, on both complete and incomplete basic partitionings. Experimental results on various real-world data sets demonstrate that KCC is highly ef?cient and is comparable to the state-of-the-art methods in terms of clustering quality. In addition, KCC shows high robustness to incomplete basic partitionings with substantial missing values.