A generalized automatic clustering algorithm in a multiobjective framework
A generalized automatic clustering algorithm in a multiobjective framework
复制标题
DOI：
10.1016/j.asoc.2012.08.005
复制
发表时间：
2013-01-01
影响因子：
8.7
通讯作者：
Bandyopadhyay, Sanghamitra
中科院分区：
文献类型：
--
作者：
Saha, Sriparna;Bandyopadhyay, Sanghamitra
本文提出了一种新的多目标（MO）聚类技术（GenClustMOO），它可以自动划分成适当数量的集群的数据。每个聚类被划分为若干个超球形的子聚类，所有这些子聚类的中心被编码成一个字符串来表示整个聚类。为了将点分配给不同的聚类，这些局部子聚类被单独考虑。为了目标函数评估的目的，这些子聚类被适当地合并以形成可变数量的全局聚类。三个目标函数，一个反映了总的紧凑性的分区的基础上的欧氏距离，其他反映了总的对称性的集群，最后反映集群的连通性，被认为是在这里。这些优化同时使用AMOSA，一种新开发的基于模拟退火的多目标优化方法，以检测适当数量的集群以及适当的分区。使用新开发的基于点对称的距离来测量分区中存在的对称性。使用相对邻域图概念来测量分区中存在的连通性。由于AMOSA，以及任何其他MO优化技术，提供了一组帕累托最优的解决方案，一个新的方法也被开发来确定一个单一的解决方案，从这个集合。因此，建议GenClustMOO是能够检测到适当数量的集群和适当的分区从数据集具有任何形状或对称的集群，或没有重叠，以及分离的集群。建议GenClustMOO与另一个最近的多目标聚类技术（MOCK），基于单目标遗传算法的自动聚类技术（VGAPS-聚类），K-均值和单链接聚类技术的有效性进行了比较，全面证明了19个人工和7个现实生活中的数据集的不同复杂性。在实验的一部分中，AMOSA作为GenClustMOO中的底层优化技术的有效性也被证明与另一种进化MO算法PESA 2相比。(C)2012年爱思唯尔B。V.保留所有权利。
In this paper a new multiobjective (MO) clustering technique (GenClustMOO) is proposed which can automatically partition the data into an appropriate number of clusters. Each cluster is divided into several small hyperspherical subclusters and the centers of all these small sub-clusters are encoded in a string to represent the whole clustering. For assigning points to different clusters, these local subclusters are considered individually. For the purpose of objective function evaluation, these sub-clusters are merged appropriately to form a variable number of global clusters. Three objective functions, one reflecting the total compactness of the partitioning based on the Euclidean distance, the other reflecting the total symmetry of the clusters, and the last reflecting the cluster connectedness, are considered here. These are optimized simultaneously using AMOSA, a newly developed simulated annealing based multiobjective optimization method, in order to detect the appropriate number of clusters as well as the appropriate partitioning. The symmetry present in a partitioning is measured using a newly developed point symmetry based distance. Connectedness present in a partitioning is measured using the relative neighborhood graph concept. Since AMOSA, as well as any other MO optimization technique, provides a set of Pareto-optimal solutions, a new method is also developed to determine a single solution from this set. Thus the proposed GenClustMOO is able to detect the appropriate number of clusters and the appropriate partitioning from data sets having either well-separated clusters of any shape or symmetrical clusters with or without overlaps. The effectiveness of the proposed GenClustMOO in comparison with another recent multiobjective clustering technique (MOCK), a single objective genetic algorithm based automatic clustering technique (VGAPS-clustering), K-means and single linkage clustering techniques is comprehensively demonstrated for nineteen artificial and seven real-life data sets of varying complexities. In a part of the experiment the effectiveness of AMOSA as the underlying optimization technique in GenClustMOO is also demonstrated in comparison to another evolutionary MO algorithm, PESA2. (C) 2012 Elsevier B. V. All rights reserved.