Facing the explosive growth of data, the introduction of cloud computing in the space-air-ground integrated Internet of things (SAGIIoT) can solve the problem of limited computing power of the terminals. At the same time, data security on the cloud is also a focus that cannot be ignored. Secure outsourcing computing is helpful in improving privacy-preserving. Due to the wide applicability of K-means clustering, outsourcing computing for K-means has become a major research hotspot in industry and academia. Most of the existing work on outsourcing K-means clustering is based on homomorphic encryption, which has a high computational overhead due to the mathematical puzzles’ nature of homomorphic encryption. In addition, the high computational overhead of designing a verification algorithm based on homomorphic encryption is unacceptable. To address the above issues, we design a K-means clustering outsourcing algorithm by sparse matrix transformation, which can verify the deceptive behavior of cloud while achieving high efficiency. In this paper, we theoretically prove the accuracy, security, efficiency and verifiability of the proposed algorithm. Extensive experiments indicate that our algorithm is efficient.