A new multi-objective differential evolution approach for simultaneous clustering and feature selection

Abstract

Today’s real-world data mostly involves incomplete, inconsistent, and/or irrelevant information that causes many drawbacks to transform it into an understandable format. In order to deal with such issues, data preprocessing is a proven discipline in data mining. One of the typical tasks in data preprocessing, feature selection aims to reduce the dimensionality in the data and thereby contributes to further processing. Feature selection is widely used to enhance the performance of a supervised learning algorithm (e.g., classification) but is rarely used in unsupervised tasks (e.g., clustering). This paper introduces a new multi-objective differential evolution approach in order to find relatively homogeneous clusters without the prior knowledge of cluster number using a smaller number of features from all available features in the data. To analyze the goodness of the introduced approach, several experiments are conducted on a various number of real-world and synthetic benchmarks using a variety of clustering approaches. From the analyzes through several different criteria, it is suggested that our method can significantly improve the clustering performance while reducing the dimensionality at the same time.

Introduction

Nowadays vast amounts of data can be stored without more effort thanks to the developments in technological tools such as the World Wide Web, network services, and database storages. On the other hand, due to this massive data growth, the process of knowledge extraction using a data mining method becomes more difficult. The quality of the knowledge extracted from a data does not only depend on the data mining method but also depends on the data quality. The more quality and suitability such data involves, the better the process of knowledge extraction is supposed to be. Unfortunately, not only required and necessary information but also noise, inconsistency, missing values, and a huge number of samples and features may be involved in the data. To deal with such issues, data preprocessing is proven to be a major and essential step to prepare the data for further data mining processes.

One of the critical tasks in data preprocessing, dimensionality reduction is commonly used to alleviate the curse of dimensionality “which is a serious problem as it will impede the operation of most data mining algorithms as the computational cost rise (García et al., 2016)”. Dimensionality reduction approaches are mainly investigated in two categories: space transformation and feature selection. Space transformation tries to transform the original feature set into a small number of projections. The representative examples concerning space transformation are principal component analysis, linear component analysis, and factor analysis (Ekbal and Saha, 2015). Feature selection is the process of eliminating as more irrelevant and redundant features as possible. The goal is to obtain a feature subset from all available features that is far more beneficial to the further process. In other words, feature selection aims to eliminate irrelevant and redundant features which may lead to undesired correlations in further (learning) process. By the way, the further learning process will also be faster and require less storage. Unlike space transformation, feature selection keeps the originality of features and thereby is treated as more general. Feature selection has been widely used to enhance the performance of supervised tasks (e.g., prediction, classification, regression) in data mining and machine learning (Anifowose and Abdulraheem, 2011, Anifowose et al., 2013, Anifowose et al., 2014, Anifowose et al., 2016, Anifowose, 2018). Especially, feature selection approaches have brought significant improvements in both the learning performance and the computational efficiency of the classification algorithms. Such improvements are particularly observed when feature selection approaches are wrapped around evolutionary computation (EC) techniques which are known to be powerful global search methods (Xue et al., 2013).

Despite the popularity in classification, feature selection has been rarely used in unsupervised tasks, e.g., clustering. Clustering is the process of dividing data instances into clusters (or groups) such that the instances within a cluster are highly similar to each other, whereas the instances from different clusters are maximally dissimilar. The representative measures to quantify the similarity between a pair of instances are Euclidean, Mahalanobis, Cityblock, Cosine, Correlation, Hamming, and Jaccard distances (Hancer and Karaboga, 2017). While typically computing the distance between data instances, each feature is considered with equal importance. Unfortunately, this such typical computation may lead to the curse of dimensionality problem in clustering for high dimensional data. It is also reported in Chakraborty and Das (2018) that the performance of arguably well-known clustering algorithms, such as K-means and its variants (MacQueen, 1967) may deteriorate proportionally to the number of features. Another significant and long-standing point concerning clustering is the automatic evolution of clusters since today’s real-world data mostly does not include the information of cluster number. Therefore, it is necessary to integrate the process of automatic cluster evolution with an automated feature selection process, referred to as simultaneous clustering and feature selection. Simultaneous clustering and feature selection has just come into consideration and so there exist only a few attempts to deal with this issue in the literature. In the literature, it has been considered as a single-objective problem using EC techniques, such as niching genetic algorithm (GA) (Shang et al., 2007) and particle swarm optimization (PSO) (Lensen et al., 2016). In these EC-based simultaneous clustering and feature selection approaches, all features are considered during the calculation of similarity measures whereas they are not even selected by the approaches to prevent feature selection introducing bias towards lower cluster numbers. In other words, feature selection is carried out independent of clustering; thus, it is not possible to determine whether the selected feature subset is suitable or not for the partitions obtained by clustering. It can, therefore, be inferred without no doubt that simultaneous clustering and feature selection is still an open issue for researchers.

In this paper, we aim to deal with issues concerning clustering that attract researchers’ attention by developing a new simultaneous clustering and feature selection approach, with the expectation of enhancing the quality of cluster partitions. To achieve this, we propose a variable-string length based multi-objective differential evolution approach. Specifically, we will investigate:

• the performance of the proposed approach versus representative partitional approaches on real-world datasets,

• the performance of the proposed approach versus representative partitional approaches on synthetic datasets, and

• the performance of the proposed approach versus several different clustering approaches.

The rest of the paper is organized as follows. Section 2 outlines differential evolution, cluster analysis, and recent related works. Section 3 introduces the proposed algorithm. Section 4 defines the experimental design. Section 5 presents the results with discussions. Finally, Section 6 states conclusions with future trends.