A novel K-means algorithm of measurement partitioning is proposed to overcome the problem of distance partitioning algorithm in Gaussian mixture probability hypothesis density filter for extended target tracking. The number of the targets is estimated by maximum-likelihood estimator and then the estimates of the target number are used as the cluster number of K-means. An elliptical gate is introduced to remove the clutter measurements for depressing the influence of clusters. Simulation results show that the proposed algorithm reduces the computational complexity obviously, and obtains an improved performance.