Abstract: To optimize natural gas gathering pipeline networks, the wellheads in the area of a natural gas field were clustered by means of K-means clustering algorithm and the penalty minimum spanning tree algorithm was proposed based on the Prim algorithm. Furthermore, a natural gas pipeline network planning model was established and the cost function of natural gas pipeline network planning was deduced. Then, from the view point of global optimization, the natural gas pipeline network planning was studied according to the concept of iterative approximation. Finally, the program of the model was worked out by virtue of SPSS and Matlab software. It is indicated that compared with the traditional natural gas pipeline network of star-dendritic structure, the natural gas gathering pipeline network planned by the penalty minimum spanning tree model is more feasible and flexible with less cost. It can provide the reference for the engineering construction and cost optimization of natural gas gathering system.