Clustering attempts to discover significant groups present in a data set. It is an unsupervised process. It is difficult to define when a clustering result is acceptable. Thus, several clustering validity indices are developed to evaluate the quality of clustering algorithms results. In this paper, we propose to improve the quality of a clustering algorithm, called CLUSTER, by using a validity index. CLUSTER is an automatic clustering technique. It is able to identify situations where data do not have any natural clusters. However, CLUSTER has some drawbacks. In several cases, CLUSTER generates small and not well-separated clusters. The extension of CLUSTER with validity indices overcomes these drawbacks. We propose four extensions of CLUSTER with four validity indices Dunn, DunnRNG, DB, and DB*. These extensions provide an adequate number of clusters. The experimental results on real data show that these algorithms improve the clustering quality of CLUSTER. In particular, the new clustering algorithm based on DB* index is more effective than other algorithms.