关键词: 多目标聚类, 聚类数, 进化算法, 精英集, 多目标优化, 差分进化

Abstract: Determining the number of clusters is a basic yet challenging problem in clustering analysis. On one hand, the optimal number of clusters varies according to different evaluation criteria, user preferences or demands, hence it makes sense to provide the user with multiple clustering results for different number of clusters. On the other hand, increasing the number of clusters without any penalty usually optimizes the within-cluster compactness while deteriorating the between-cluster separation. Therefore, selecting an appropriate number of clusters is, in fact, a multi-objective optimization problem, which needs to choose a balanced solution among a set of tradeoffs between the minimum number of clusters and the maximum compactness or separation of clusters. As a result, in order to deal with the clustering problem with unknown number of clusters, we directly take the number of clusters as one optimization objective, and simultaneously optimize it with another objective function reflecting the within-cluster compactness by a newly designed multi-objective differential evolutionary algorithm with an elitist archive. The proposed algorithm obtains a nearly Pareto-optimal set, which contains multiple clustering results for distinct number of clusters, in a single run. Experiments on several datasets and comparative experiments demonstrate the practicability and effectiveness of our proposed algorithm.

Key words: multi-objective clustering;the number of clusters;evolutionary algorithm, elitist archive;multi-objective optimization;differential evolution