On Combining Nature-Inspired Algorithms for Data Clustering

On Combining Nature-Inspired Algorithms for Data Clustering

Hanan Ahmed (Ain Shams University, Egypt), Howida A. Shedeed (Ain Shams University, Egypt), Safwat Hamad (Ain Shams University, Egypt) and Mohamed F. Tolba (Ain Shams University, Egypt)
Copyright: © 2017 |Pages: 30
DOI: 10.4018/978-1-5225-2229-4.ch036
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This chapter proposed different hybrid clustering methods based on combining particle swarm optimization (PSO), gravitational search algorithm (GSA) and free parameters central force optimization (CFO) with each other and with the k-means algorithm. The proposed methods were applied on 5 real datasets from the university of California, Irvine (UCI) machine learning repository. Comparative analysis was done in terms of three measures; the sum of intra cluster distances, the running time and the distances between the clusters centroids. The initial population for the used algorithms were enhanced to minimize the sum of intra cluster distances. Experimental results show that, increasing the number of iterations doesn't have a noticeable impact on the sum of intra cluster distances while it has a negative impact on the running time. K-means combined with GSA (KM-GSA), PSO combined with GSA (PSO-GSA) gave the best performance according to the sum of intra cluster distances while K-means combined with PSO (KM-PSO) and KM-GSA were the best in terms of the running time. Finally, KM-GSA and GSA have the best performance.
Chapter Preview
Top

Introduction

Recently, with the advent of large memory systems and computer networks, the amount of stored data grows very quickly. These data contain useful but hidden information that may be extracted for various purposes. Organizing data into sensible groupings or clusters is one of the most fundamental modes of understanding and learning. Clustering is defined as the unsupervised classification of patterns (observations, data items or feature vectors) into groups (clusters). Clustering algorithms are used in many fields and applications such as: Document clustering and information retrieval applications, where the modified differential evolution algorithm was used in (Abraham, Das, & Konar, 2006, Hassanien, 2016), hybrid harmony search was used for clustering web documents in (Mahdavi, Chehreghani, Abolhassani, & Forsati, 2008) and dynamic hierarchical compact and dynamic hierarchical star were used in (Gil-Gara & Pons-Porrata, 2010) for document clustering; Data compaction applications, where clustering based vector quantization algorithms and set partitioning in hierarchical trees were used in (Yang, Wu, Wang, & Jiao, 2010) for image compression; Anomaly detection applications, where crisp and fuzzy approaches based on the cosine similarity principle were used in (Friedmana, Lastb, Makover, & Kandel, 2007), Genetic algorithm was used in (Kerr, Ruskin, Crane, & Doolan, 2008) and dynamic agglomerative was used in (Liang & Wang, 2007) to cluster gene expression data ; Medicine applications, where spatially constrained kernel clustering was used in (Liao, Lin, & Li, 2008); Computer vision applications, where genetic algorithm, C-means, competitive learning and hierarchicalcompetitive learningwere used in (Scheunders, 19997) and single point iterative weighted fuzzy C-means was usedin (Fan, Han, & Wang, 2009); Construction management applications, where constrained k-prototypes were used in (Cheng & Leu, 2009); Marketing and customer analysis applications, where mixed integer programming was used in (Saglam, Salman, Sayın, & Türkay, 2006) and many other fields where the clustering algorithms were used in the primary task for understanding the nature and the structure of data or used in the pre-processing or post-processing phase for higher level tasks.

Local optimum of an optimization problem is a solution that is optimal (either maximal or minimal) within a neighbouring set of candidate solutions. There is a solution which is the optimal solution among all possible solutions (global optima). From our study for different clustering algorithms, it has been found that the local optimum is the problem of some algorithms and to overcome this problem, search based algorithms (optimization algorithms which are nature based) were used to get optimum centroids(Jain, Murty, & Flynn, 1999, Yamany et al 2015a,b, Tharwat et al. 2015, Hassanien, Aboul Ella & Alamry,E., 2015).

In this paper nature inspired algorithms are combined with K-means and with each other in various orders and a comparative study among these algorithms and their combinations are introduced. Comparative Analysis is done in terms of three measures; the sum of intra cluster distances, the running time and the distances between the clusters centroids. The effect on the performance and the run time for the different number of iterations is also studied.

The rest of the paper is organized as follows: Section 2 provides a brief explanation for data clustering types. The related work will be introduced in Section 3. A theoretical comparative study among the three basic algorithms PSO, GSA and CFO will be introduced in Section 4. The proposed experiments will be explained in Section 5 and the performance will be tested using the famous UCI repository datasets in Section 6. Finally, the conclusion of the work will be presented in section 7.

Key Terms in this Chapter

Hybrid Algorithms: Combining one or more algorithms that solve the same problem in order to enhance the overall performance (the combined algorithms perform better than individuals).

Hard Clustering Algorithms: In hard clustering each data item assigned to one and only one cluster. Hard clustering divided into types hierarchical clustering and partitional clustering.

Hierarchical Clustering Algorithms: A method to build a hierarchy of clusters either in agglomerative (each data item has its own cluster and then merge most similar clusters) or divisive (all data items belongs to the same cluster and this cluster will be divided recursively into smaller clusters).

Stochastic Algorithms: The algorithms that use random parameters in its formulation.

Deterministic Algorithms: The algorithms that don’t use any random parameters in its formulation.

Soft Clustering Algorithms (Also Called: Fuzzy Clustering): In soft clustering each data item assigned to different clusters with different degrees.

Data Clustering: Unsupervised learning operation that groups the data objects, objects in same group are more similar to each other than objects in other groups.

Nature Inspired Algorithms: A group of algorithms that simulate physical or biological phenomena to solve computational problems.

Complete Chapter List

Search this Book:
Reset