A spectrum map construction method based on general regression neural network fitting and clustering Kriging was proposed, in which the path-loss and shadowing components were estimated by general regression nerual network for trend-surface fitting to improve the construction accuracy. In order to improve construction efficiency and guarantee the accuracy meanwhile, monitoring data clustering and optimal neighborhood selection were utilized to reduce the amount of calculated data. The proposed method can realize the accurate and fast construction without prior information by only using limited amount electromagnetic environment monitoring data. A spectrum map prototype verification system was designed and implemented, real measured data from vehicle-based collection system was utilized for testification of the feasibility and performance of the proposed method.