This paper describes a new k-means type clustering algorithm which gives excellent results for a moderate computational cost. It is particularly suitable for partitioning large data sets into a number of clusters where the conventional k-means algorithm becomes computationally unmanageable. While it does not guarantee to reach a global optimum, its performance in practice is very good indeed, as demonstrated by theoretical analysis and experiments on color image data.