Aimed at the problems that sensing nodes are uneven in distribution and low in construction efficiency in the construction of electromagnetic spectrum map, a new electromagnetic spectrum map construction algorithm is proposed based on the Kriging algorithm. Firstly, the Kriging algorithm is used to build electromagnetic spectrum map from perceptual data. Secondly, the Kmeans clustering algorithm is introduced to realize the multigranularity division of the perception region, and the whole region is divided into multiple local regions at different levels. Meanwhile, the Kriging algorithm is used to interpolate and estimate the electric field intensity of the local region, and the multiple electromagnetic spectrum maps with different granularity are formed. Finally, according to the distribution of sensing nodes, the weight of local region uniformity under different granularity is calculated based on the Voronoi diagram, and the electromagnetic spectrum map under different granularity is weighted, generating the electromagnetic spectrum map. The simulation results show that the proposed algorithm can reduce the error of electromagnetic spectrum map construction by 2%～5%, and the construction efficiency is much higher than that of the original algorithm when the noise intensity is greater than 8 dBW, and the algorithm is characterized by high construction accuracy and strong fault tolerance.