A generalized automatic clustering algorithm in a multiobjective framework

doi:10.1016/j.asoc.2012.08.005

A generalized automatic clustering algorithm in a multiobjective framework

2013-01-01

85

PRE

AI

S

Sriparna Saha *

S

Sanghamitra Bandyopadhyay

DOI：10.1016/j.asoc.2012.08.005

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Clustering

Multiobjective optimization (MOO)

Symmetry

Relative neighborhood graph

Multi-center

Automatic determination of number of clusters

A generalized automatic clustering algorithm in a multiobjective framework

Abstract

AI Summary

Journal

Organization

Cited Papers