Quantum-Inspired Automatic Clustering Technique Using Ant Colony Optimization Algorithm

Quantum-Inspired Automatic Clustering Technique Using Ant Colony Optimization Algorithm

Sandip Dey (OmDayal Group of Institutions, India), Siddhartha Bhattacharyya (RCC Institute of Information Technology, India) and Ujjwal Maulik (Jadavpur University, India)
Copyright: © 2018 |Pages: 28
DOI: 10.4018/978-1-5225-5219-2.ch002


Quantum computing has emerged as the most challenging field of research in efficient computation. This chapter introduces a novel quantum-inspired ant colony optimization technique for automatic clustering. This chapter presents an application of this proposed technique to the automatic clustering of real-life gray-scale image data sets. In contrary to the other techniques, the proposed one requires no previous knowledge of the data to be classified. It finds the optimal number of clusters of the data by itself. The Xie-Beni cluster validity measure has been employed as the objective function for clustering purpose. Effectiveness of the proposed technique is exhibited on four real-life gray-scale images. Superiority of the proposed technique is established over its counterpart with respect to various aspects, which include accuracy, stability, computational time and standard errors. Finally, a statistical supremacy test, called unpaired two-tailed t-test, is conducted between them. It shows that superiority in favor of the proposed technique is established.
Chapter Preview

1. Introduction

Clustering is defined as segregating an unlabeled data set into groups of similar objects. Each group is known as “cluster”. The objects in one cluster are similar between themselves, whereas these objects possess dissimilarity to the objects of any other groups. Formally, clustering can be defined as follows:

(1) where, and for . Subsequently, any object exactly lies in only one where, . From the last few decades, cluster analysis has been used in various fields successfully. These fields include engineering (e.g., electrical and mechanical engineering, machine learning, pattern recognition, artificial intelligence and so on), social sciences (e.g., psychology, sociology, and education), computer sciences (e.g., image segmentation, web mining, textual document collection), medical sciences (e.g., psychiatry, biology, microbiology and pathology), earth sciences (e.g., geology, geography, and remote sensing) and economics (e.g., marketing and business) . In the literature, a number of different clustering algorithms have been introduced for various applications (Jain, 1999; Bakhshi, 2012).

The concept of Quantum Computing (QC) has been emerged by exploiting the principles of quantum mechanical phenomena. To research in this area is probably the most demanding and challenging task of twenty-first century. The behavior of QC can be described by the Schrödinger equation (Han, 2002). Quantum bits (qubits) are the smallest unit in QC. Superposition of states is a very important feature of QC where two states are combined in the fashion of linear superposition satisfying some probabilistic criteria. Unlike classical computer, the state space becomes n-dimensional for an n-qubits QC. Hence, this exponential growth of the state space makes QC perform exponentially faster compared to its classical computer (conventional computer). Like this computer, QC also possesses different quantum logic gates, called Q-gate which operates on a small number of quantum bits. Some popular examples of these quantum logic gates are CNOT, Hadamard gate and rotation gate (Hey, 1999) to name a few.

Quantum computer is much faster than its counterpart in terms of computational capability (Han, 2002). Richard Feynman discovered that the limitation of the computational capability of conventional computers can be overcome successfully with the use of quantum effect (Talbi, 2004). QC can possess its inherent parallelism capability, which in turn makes algorithms to execute exponentially faster compared to others (Talbi, 2006 ; Reiffel, 2000). The use of QC was proved to be very effective to run such algorithms which may require larger solution space. These days, this technique is successfully and efficiently used to solve different complex optimization problems. In the literature, some popular quantum algorithms are Grover’s database search algorithm (Grover, 1996) and Shor’s quantum factoring algorithm (Shor, 1996).

Complete Chapter List

Search this Book: