Presenting a new method in information clustering using a combination of bat algorithm and Fuzzy c-means

Master's thesis in the field of automation and instrumentation engineering

Abstract

Presenting a new method in information clustering using a combination of bat algorithm and Fuzzy c-means

Clustering is placing data in groups where the members of each group are similar from a certain angle.  The similarity between the data within each cluster is maximum and the similarity between data within different clusters is minimum.

Fuzzy c-means is also a fuzzy clustering technique which, despite being sensitive to initialization and convergence to local optimal points, is one of the most common methods due to its efficiency and easy implementation. In this thesis, to solve the existing problems, the combined method based on the bat algorithm and Fuzzy c-means will be used. In order to validate, the proposed method will be implemented on several well-known different data and the results will be compared with forbidden search algorithm, ants, particle community, steel plating and k-means methods. The high ability and robustness of this method will be evident based on the results. 

Introduction

Data and patterns are one of the most important indicators in the world of information, and clustering is one of the best methods that have been provided to work with data. Its ability to enter the data space and recognize their structure has made clustering one of the most ideal mechanisms for working with the huge world of data.

In clustering, samples are divided into categories that are not known in advance. Therefore, clustering is a learning method that independently categorizes data without prior knowledge and observing pre-defined samples.

Clustering is actually finding structure in unclassified data sets. In other words, clustering is putting data into groups where the members of each group are similar from a certain angle. As a result, the similarity between data within each cluster is maximum and the similarity between data within different clusters is minimum. The criterion of similarity here is distance, which means that samples that are closer to each other are placed in a cluster. Therefore, calculating the distance between two data is very important in clustering; Because the quality of the final results will change.

Distance, which is the representative of inhomogeneity, enables movement in the data space and causes the creation of clusters. By calculating the distance between two data, you can understand how close these two data are to each other and whether they are in the same cluster or not? There are various mathematical functions to calculate the distance; Euclidean distance, Hamming distance and .

1-1-Problem statement

Clustering is finding the structure in unlabeled data sets and it can be considered as the most important problem in unsupervised learning. The idea of ??clustering was first proposed in the decade of 1935, and today it has been present in various applications and aspects with the huge advances and leaps that have occurred in it. A simple search on the web or even in a library database reveals its amazing utility.  Clustering algorithms are used in various fields, the following can be listed as examples:

Data mining[1]: discovering new information and structure from existing data

Speech recognition[2]: in building a codebook from feature vectors, in dividing speech according to its speakers or speech compression

Image segmentation[3]: segmenting medical or satellite images

Web (WWW): classification of documents or classification of sites and .

Biology[4]: classification of animals and plants based on their characteristics

Urban planning[5]: classification of houses based on their type and geographical location

Seismography studies [6]: detection of accident-prone areas based on previous observations

Library: classification of books

Insurance: detection of fraudulent people

Marketing[7]: categorizing customers into categories according to their needs through the collection of their latest purchases.

Due to the increasing use of clustering, today we are witnessing the presentation of new and more efficient methods, each of which is provided for a specific application. But despite all these efforts, clustering is still not used as much as it should be in many sciences and there is a lot of potential for it to be expanded.

1-2-Research Background

We live in a world full of data and every day we are faced with a large amount of storing or displaying information. One of the vital methods of controlling and managing these data is clustering. In this method, data that have similar properties are placed in a category or a cluster. For the first time, the idea of ??clustering was presented in the 1935s, and today it has attracted the attention of many researchers with the huge advances and leaps that have occurred in it. Therefore, it has been present in various applications and aspects, and various methods have been proposed for its exploitation [1]. In one sense, clustering algorithms can be divided into two general categories: hard clustering and fuzzy clustering. In hard clustering, a data belongs to one and only one cluster, while in fuzzy clustering, a data may belong to two or more clusters at the same time [2], [3], [4]. Fuzzy c-means algorithm is one of the famous fuzzy clustering methods that can be easily implemented. Unfortunately, its original version has limitations such as dependence on initial values ??and convergence to the local optimal response [5], [6]. In the genetic algorithm, these limitations have disappeared. At the same time, by combining these two algorithms, significant results have been obtained, and the speed of convergence has also increased far more than the previous examples [7]. By combining two genetic algorithms and PSO, Kao and his colleagues invented a method in which he used mutation and crossover operators for genetics. This method was able to solve various problems of continuous functions. Also, significant changes have been achieved in finding the global optimal solution and the convergence ratio [8]. Using the combination of genetic algorithm and fuzzy method, a method was suggested by Asgarian in 2016. In this method, the problem of dependence on the initial number of clusters and the initial location of their centers is high and with the inability to cluster data whose distance from the centers of several clusters is the same; It was countered. Another advantage of this combination is reducing the complexity of calculations [9]. Another combination method that is used in data mining problems is the use of the combination of Fuzzy c-means and PSO, which was able to improve the problem of convergence to local optimality and the speed of convergence [10], [11]. Another new combined method is the combination of FCM algorithm and fuzzy memetic algorithm. In order to improve clustering performance, the results of this technique show that it has better answers and its stability is also higher [12]. The combination of FCM and SA is another example of combined methods used in cancer diagnosis [13], [14], [15], [16]. In line with the mentioned efforts, this thesis tries to take advantage of the advantages of two algorithms in solving clustering problems by using the combination of FCM algorithm and bat algorithm.

1-3-Research Objective

The purpose of this research is to present an algorithm that can cover the existing limitations to an acceptable extent by examining the existing algorithms in the field of clustering. Some of the existing limitations can be listed as follows:

× Performance for high-volume databases

× Discovery of clusters with different shapes

× Insensitivity to the order of input data

× Ability to interpret and use

1-4-Importance of research

Simultaneously with the increase of database systems and multiple tools for storing large volumes of data, there is a need for automatic methods to fully discover knowledge from within the data. It was felt. In addition, due to the high cost of human and material resources to perform operations on massive amounts of data, it was necessary to provide methods with minimal user intervention. Extracting appropriate information from the masses of data and turning them into knowledge needed by organizations - especially in organizational decision-making - required the use of new methods in this field. Data mining [8] is one of these tools that helps to discover knowledge from databases. It can be said that data mining is extracting valid, understandable and reliable information from very large databases, which helps to discover hidden patterns and reliable relationships between data and use it in decision making. In fact, knowing and dealing with data is one of the important goals in data mining.

This process was introduced in the late 90s and entered statistical discussions seriously since 1995, and it is currently one of the most important tools for the effective use of large amounts of data, and its importance is increasing every day.