Abstract: As a classical data mining technique,clustering is widely used in fields as pattern recognition,machine learning,artificial intelligence,and so on.By effective clustering analysis,the underlying structures of datasets can be identified.As a commonly used partitional clustering algorithm,K-means is simple of implementation and efficient on classifying large scale datasets.However,due to the influence of the convergence rule,the traditional K-means is still suffering problems as sensitive to the initial clustering centers,cannot properly process non-convex distributed datasets and datasets with outliers.This paper proposes the DC-Kmeans (density parameter and center replacement K-means),an improved K-means algorithm based on the density parameter and center replacement.Due to the gradually selecting of initial clustering centers and continuously update imprecision old centers,the DC-Kmeans is more accurate than the traditional K-means.Two novel methods are also proposed for optimally clustering:1)a novel clustering validity index (CVI),SCVI (Sum of the inner-cluster compactness and the inter-cluster separateness based CVI),is proposed to evaluate the results of the DC-Kmeans;2)a new algorithm,OCNS (optimal clustering number determination based on SCVI),is designed to determine the optimal clustering numbers for different datasets.Experimental results demonstrate that the proposed clustering method is effective for many kinds of datasets.

Key words: Cluster center, Clustering algorithm, Clustering validity index, Data mining, Optimal clustering number