Data Clustering Based on Fuzzy C-Means and Chaotic Whale Optimization Algorithms
* Author to whom correspondence should be addressed.
Sigma Journal of Engineering and Natural Sciences 2019, Vol. 37, Issue 4, pp. 1107-1128; doi.org/10.62051/ytu.sigma-journal-of-engineering-and-natural-sciences-data-clustering-based-on-fuzzy-c-means-and-chaotic-whale-optimization-algorithms
Abstract
Keywords: Data clustering; WOA; FCM; optimization; chaos.
1. Introduction
Population based meta-heuristic algorithms have been developed with inspiration from natural phenomena. These algorithms are often preferred since they do not require gradient information, exceeds to local optimum, are easy to implement, and can be used in many interdisciplinary fields [1]. These algorithms converge to an optimal solution rather than an exact solution. According to the NFL theorem [2], there is no algorithm that best solves all optimization problems. In other
Corresponding Author: e-mail: haticearslan8154@gmail.com 1107
words, a meta-heuristic algorithm may perform well for some problems while doing poorly for others. These algorithms are generally grouped in three different ways, physics-based, evolutionbased, and swarm-based. Physics-based algorithms are developed based on natural physics rules. Simulated Annealing (SA) [3] which mimics the physical annealing process of the solids, Gravitational Search Algorithm (GSA) [4] using Newton's gravity and motion laws, Big Bang Big Crunch Algorithm (BB-BC) [5] inspired by the big bang theory, Gravity Local Search (GLS) [6], Black Hole Optimization (BH) [7] and Beam Algorithm (BA) [8] are examples of physics-based algorithms. The source of inspiration for evolutionary algorithms is Darwin's theory of evolution. The process that begins with the creation of a random population continues with the survival and proliferation of the best and most compatible individual. Genetic Algorithm (GA) [9], Genetic Programming (GP) [10], Evolution Strategy (ES) [11], Probability Based Incremental Learning (PBIL) [12] and Biology Based Optimization (BTO) [13] can be given as examples of evolutionbased algorithms. Swarm-based algorithms have been enhanced with inspiration from behaviors of solving the problems encountered by living creatures acting collectively and behaviors of benefit from each other's experiences to solve a probable problem. Particle Swarm Optimization (PSO) [14] which models bird behaviors in order of food searches, Ant Colony Algorithm (ACA) [15] developed by mathematical modeling of ant colony behaviors, Artificial Bee Colony Algorithm (ABC) [16] inspired by the behaviors of honey bees’ food search, Grey Wolf Optimizer (GWO) [17], Firefly Algorithm (FA) [18], The Ant Lion Optimizer (ALO) [19] and Sine Cosine Algorithm (SCA) [20] can be given as examples to these algorithms. Population based algorithms consist of two parts; exploration of the search field (exploration phase) and use of the best result found (exploitation phase). During the exploration phase, the selected parameters must be as random as possible for better scanning of the search field [1]. The collapsed search region in the exploration phase is tested with the exploitation phase. That is, the optimum point in the exploration phase is used during the exploitation operation and is approached to optimum throughout the iteration. Thus, provide a good balance between exploration and exploitation phases is important for the performance of the algorithm [21]. However, due to the probabilistic behavior of population-based algorithms this balance is not easy to achieve [22]. When the literature is examined, it is seen that the integration of population-based algorithms with chaos theory increases the performance of both the exploration and exploitation phase. Zhang et al. in 2009, applied two chaotic maps to the PSO and the performance of the algorithm was improved [23]. In 2009, Wang and Yao proposed a Hybrid Genetic Algorithm based on chaos and PSO to improve the convergence and inadequate run-time performance of the genetic algorithm [24]. Atalas and his colleagues have improved the performance of the PSO by applying 12 chaotic maps to the PSO in 2009 [25]. They have also shown that the performance of the ABC [26] and Harmony Search (HS) algorithms [27] can be improved by chaos. In the work performed by Yan H. et al. in 2014, chaos has been used to improve the exploitation phase of the genetic algorithm and to increase the accuracy [28]. In addition, meta-heuristic algorithms also used in conjunction with chaos are GA [29], FA [30], SA [31], Differential Evolution (DE) [32] and Krill Herd Algorithm [33]. The examples given support the increase in performance when meta-heuristic optimization algorithms are used together with chaos. In this paper, Whale Optimization Algorithm (WOA) [1], developed by Mirjalili and Lewis based on the hunting behaviors of whales, is used together with chaotic maps to improve the performance of the algorithm. There are studies in the literature where the WOA algorithm was used with chaos functions. In the study done by Tanyıldızı and Cigal, the Logistic map was added to the WOA algorithm and WOA algorithms based on chaos were proposed [34]. Sun and Wang tried to solve the problem of trapped to local optimum by using the WOA algorithm to optimize the Elman neural network. Besides, a chaotic WOA algorithm was proposed to improve the diversity and eccentricity of search agents [35]. Oliva and colleagues applied four different chaos maps to the WOA algorithm for parameter estimation of solar batteries [36]. In this article, unlike other studies, 10 different chaotic maps are applied to the WOA after being passed through the 1108
normalization process proposed in [22]. The efficiency of the proposed algorithms is tested using 13 benchmark functions. Scientific significance of the results is measured by the Wilcoxon Sign Rank Test. In addition, a new approach has been improved to the solution of the data clustering problem by means of the proposed chaotic algorithms. Clustering is the process of dividing a data set into different subsets where similar data are found in the same cluster. It is indicative of a good clustering being intra-cluster similarity is maximum and inter-cluster similarity is minimum [37]. Clustering is used in scientific and engineering applications such as image recognition, data mining, machine learning, signal processing and biology [38]. In the literature there are many clustering algorithms proposed for solving clustering problems. One of these algorithms is the fuzzy clustering based Fuzzy CMeans (FCM) algorithm proposed by Dunn [39] and developed by Bezdek [40]. In this algorithm, the data belongs to a cluster with certain membership grades. Therefore, one element in database can belong to more than one cluster at the same time. Although the FCM is an efficient algorithm, random selection of the initial cluster centers creates a disadvantage by making it easier to trap the algorithm to the local optimum. Clustering problem can also be considered as a kind of optimization problem. In recent years, meta-heuristic algorithms have begun to be widely used to solve such clustering problems [41]. Such algorithms look for an optimal solution for clustering problems and reduce the risk of trapping to the local optimum [38]. For this reason, the FCM algorithm is also combined with many meta-heuristic algorithms. According to the literature, the FCM is integrated with the meta-heuristic algorithms such as GA [42], DE [43], Ant Colony Optimization [44], PSO [45], Artificial Fish Swarm Optimization [46], fuzzy PSO [47], Support Vector Machines [48]. In this paper, FCM and chaotic WOA algorithms are combined and new hybrid clustering algorithms are developed. The proposed algorithms are based on optimizing the cluster centers with the chaotic WOA algorithms. For each cluster center, the FCM-CWOA algorithms updates the cluster centers while trying to minimize the objective function of the FCM algorithm. In addition, to improve performance of the proposed clustering algorithms, Euclid distance function of the FCM algorithm is replaced by the Chebyshev distance function. FCMCWOA algorithms, the classical FCM algorithms and other optimization based hybrid algorithms are tested with six datasets selected from the UCI database [49]. The effect of changing the distance function of the FCM algorithm and of the normalization of chaos maps on the data clustering are evaluated by proposed algorithms (FCWOA-c and FCMWOA* algorithms). The obtained results are compared with the Rand Index and Adjusted Rand Index values and according to these indexes it is seen that the proposed clustering algorithms gives better results than the compared algorithm. As a result, it is observed that using WOA algorithm with normalized chaos maps increases the performance of the algorithm, integrating chaotic WOA algorithms with FCM algorithm improves disadvantages of FCM algorithm and changing distance function increases clustering performance of algorithms. In the second part, WOA algorithm is explained in details; in the third part chaos maps and application methods are given. In the fourth part, the problem of data clustering is identified. Finally, in the fifth section, the study is briefly summarized and evaluated.
2. Whale Optimization Algorithm (WOA)
The whale optimization algorithm (WOA) is a global optimization algorithm developed by Mirjalili and Lewis [1], inspired by the hunting strategies of humpback whales. Humpback whales have a unique hunting behavior. They dive about 12 meters down in the water and form spiralshaped bubbles around their prey, trapping their prey in air bubbles. Then, they swim to the surface to swallow their prey. These unique hunting behaviors of humpback whales are illustrated in figure 1.
Figure 1. Hunting behavior of humpback whale The mathematical model of the WOA algorithm consists of three basic steps; spinning, air bubble attack, and hunting. The algorithm assumes that the target hunt is the closest candidate solution to the optimal hunt model. Each humpback whale is considered a search agent. After the best search agent is identified according to the target prey, other search agents update their location accordingly. The mathematical model of this behavior is defined as follows [1]. ⃗ = |𝐶 . ⃗⃗⃗⃗ 𝐷 𝑋 ∗ (𝑡) − 𝑋(𝑡)|
where, t is current iteration number, 𝐴 and 𝐶 are two coefficient vectors, ⃗⃗⃗⃗ 𝑋 ∗ is the best solution of position vector obtained so far, 𝑋 is the position vector and | | and ∙ means absolute value and elementary multiplication, respectively. If there is a better solution ⃗⃗⃗⃗ 𝑋 ∗ should be updated in every iteration. The vectors 𝐴 and 𝐶 are calculated as follows [1]: 𝐴 = 2𝑎. 𝑟 − 𝑎
where, 𝑎 is a linearly decreasing number from 2 to 0 throughout the iterations (both during the exploration and exploitation phases) and 𝑟 is a random vector in the range [0,1]. The search agent (𝑋, 𝑌) can update the location according to the best available (𝑋 ∗ , 𝑌 ∗ ) location and by chancing the values of 𝐴 and 𝐶 , it can reach to different places near the best search agent. By randomly defining the vector 𝑟, it is possible to reach any position in the search space located between the lock points. Equation 2 allows the search agent to update its position in the neighborhood of the best solution available and to model encircling the prey. The modeling of the bubble-net attacking method of humpback whales involves two approaches [1]. Shrinking encircling mechanism represents the reduction of the circle around the prey by updating the value of 𝑎 in the equation 3 with the following equation [1]. 1110
Thus, 𝐴 takes a random value in the interval [-a, a] with decreasing 𝑎 from 2 to 0 during the iteration. The new position of a search agent can be defined anywhere between the starting position of the agent and the position of the best available agent, if we assign random values in the range [-1,1] for A [1]. Spiral updating computes the distance between the whale located at (𝑋, 𝑌) and the prey located at (𝑋 ∗ , 𝑌 ∗ ). To model the helical movements of humpback whales, the following equation is established between the whale and the prey positions [1]. 𝑋(𝑡 + 1) = ⃗⃗⃗⃗ 𝐷′ . 𝑒 𝑏𝑙 cos(2𝜋𝑙) + ⃗⃗⃗⃗ 𝑋 ∗ (𝑡)
⃗⃗⃗⃗∗ (𝑡) − 𝑋(𝑡)| and shows the distance of the ith whale to prey. b is a constant where ⃗⃗⃗⃗ 𝐷′ = |𝑋 that defines the logarithmic spiral shape; l is a random number in the range [-1,1], and ∙ is elementary product. The humpback whales swim creating shrinking spirals around their prey, simultaneously. To simulate this synchronous behavior, it is assumed that during optimization, the location of the whales has been updated with a probability of 50% among shrinking encircling mechanism and the spiral updating. It is mathematically expressed by the following equation [1]. ⃗⃗⃗⃗ ⃗ 𝑋 ∗ (𝑡) − ⃗⃗⃗ 𝐴. 𝐷 𝑋(𝑡 + 1) = { 𝑏𝑙 ′ ⃗⃗⃗⃗ 𝐷 . 𝑒 cos(2𝜋𝑙) + ⃗⃗⃗⃗ 𝑋 ∗ (𝑡)
where p is a random number between [-1,1]. Search for prey (exploration phase) imitates humpback whales doing random research according to each other's position. To make the search more comprehensive and to keep the whales away from each other, 𝐴 is selected randomly as greater than 1 and less than -1. In contrast to the exploitation phase, during the exploration phase, the position of a search agent is updated with a randomly selected search agent. Selecting |𝐴| > 1 allows the WOA algorithm to conduct a global search. The mathematical model is as follows [1]: ⃗ = |𝐶 . ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗ 𝐷 𝑋𝑟𝑎𝑛𝑑 − 𝑋|
where ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗ 𝑋𝑟𝑎𝑛𝑑 is a random position vector selected from the current population. To summarize, the WOA algorithm begins with a series of random solutions. In each iteration, search agents update their positions to 50% probability, either randomly selected search agents, or the best solution so far. Depending on the value of p, WOA can choose between spiral or circular motion. Finally, the WOA is terminated by provide of the stopping criterion.
3. Chaotic MAPS
Chaos is defined as the randomness produced by mathematically simple deterministic systems [25]. It can also be expressed as an arrangement within the irregularity that focuses on the behavior of dynamic systems that are highly sensitive to their initial values. That is, small changes in the initial conditions can result in large differences (sensitivity). Chaos has similar scatter performance for a random value (randomness). It also consists of values that do not repeat within a certain interval (ergodicity) [26], [50]. Therefore, using chaotic variables instead of random variables in optimization algorithms reduces the likelihood of repeating randomly selected numbers and accumulating at a certain interval. Thus, the problem of trapping to the local optimum of the optimization problems can be solved [50]. The chaotic maps used in this study are shown in Table 1 [22], [50]. 1111
Table 1. Equations of and range of chaotic maps Chaotic Maps Chebyshev Circle Gauss/mouse
𝑎 ) sin 2𝜋𝑥𝑖 , 1) , 𝑎 = 0.5 𝑏 = 0.2 2𝜋 𝑥𝑖 = 0 1 𝑥𝑖+1 { 𝑑𝑖ğ𝑒𝑟 𝑚𝑜𝑑(𝑥𝑖 , 1) 𝑎𝜋 𝑥𝑖+1 = sin 𝑎 = 0.7 𝑥𝑖 𝑥𝑖+1 = 𝑎𝑥𝑖 (1 − 𝑥𝑖 ) 𝑎 = 4
0.5. − 𝑑
2 1 − 𝑥𝑖 1 − 𝑑 ≤ 𝑥𝑖 < 1 { 𝑑 𝑎 𝑥𝑖+1 = sin(𝜋𝑥𝑖 ) 𝑎=4 4 𝑥𝑖+1 = 𝜇(7.86𝑥𝑖 − 23.31𝑥𝑖2 + 28.75𝑥𝑖3 − 13.302875𝑥𝑖4 ), 𝜇 = 2.3 𝑥𝑖+1 = 𝑎𝑥𝑖2 sin(𝜋𝑥𝑖 ), 𝑎 = 2.3
3.1. Application of Chaotic Maps to the WOA Algorithm
In the WOA algorithm, hunting strategy of humpback whales is modeled. The whales create air bubbles around their prey and surround them and prevent them from escaping. This behavior is modeled by the Equation 2. By updating the value 𝑎 in the Equation 3, it is possible to narrow the circle around the prey. In the WOA algorithm, 𝑎 value is chosen from randomly generated numbers. In this work, 𝑎 value has been replaced by chaotic maps to provide both decreasing linearly in the range [0,2] and randomness obtained by chaos maps. In the WOA algorithm, 𝑎 value decreases linearly in the range [0,2]. Accordingly, each of the chaotic maps has been normalized to a predefined range [𝑘, 𝑙], this range represents the added chaos effect to the 𝑎 value. Normalized chaos maps have been added to the current 𝑎 value. The normalization process is performed using the following formulas as done in [22]. 𝑥(𝑡)𝑛 =
Where 𝑥(𝑡) and 𝑥(𝑡)𝑛 are non-normalized and normalized values of the chaotic map at t’th iteration, [𝑚, 𝑛] is the interval of the chaos map given in Table 1, and [𝑘, 𝑙] = [0 0.05] is the normalization interval used in this study. d value is reduced throughout iterations by the following formula [22]. 𝑡
In this Equation, t represents the current iteration and T represents the maximum number of iterations. Chaotic maps are normalized and then combined with 𝑎 value. This process is shown in Figure 3-4 for Chebyshev Map.
Figure 4. Sum of normalized Chebyshev map with 𝑎 value In Figure 5 all the normalized chaos maps with 𝑎 value is shown.
Data Clustering Based on Fuzzy C-Means and … / Sigma J Eng & Nat Sci 37 (4), 1107-1128, 2019 H. Arslan, M. Toz / Sigma J Eng & Nat Sci 37 (4), 1107-1128, 2019
4. Experimental Studies
The performance of chaos-based WOA algorithms developed in this paper has been tested with 13 different benchmark functions that are frequently used in optimization problems [1]. These functions are composed from both single-mode functions (F1-F7) and multi-mode (F8-F13) functions [1]. The equations of these functions are given in Table 2. Table 2. Equations of benchmark functions benchmark functions 𝒏
The WOA algorithm and the proposed CWOA algorithms have been run 30 times in succession. Besides, maximum number of iteration was defined as 1000 and population size was 50. In order to evaluate the mutual performances of the algorithms, mean and standard deviation values were calculated for each run. The best results are indicated in bold type. In addition, nonparametric Wilcoxon Sign Rank Test [51] was calculated at the significance level of 0.05 in order to show the significant differences between the performance of the algorithms. According to Wilcoxon sign rank test used for statistical evaluation of the results, p-values that are less than 0.05 can be considered as strong evidences against the null hypothesis. The p value of less than 0.05 is underlined. All work was done by using MATLAB R2017b program on a computer with Intel Core i7-7700HQ CPU 2.80GHz processor and 16GB Ram in the same conditions. The obtained results of chaos-based WOA algorithms are given in Table 3. The F1-F7 functions are single-mode functions since they have a single local optimum. These functions allow to evaluate the exploitation phase performance of meta-heuristic algorithms [1]. When Table 3 is examined, it is seen that chaos-based WOA algorithms for F1, F2, F3, F5, and F6 functions all yield better results than the WOA algorithm in terms of mean of the objective function values and their standard deviations. At the same time, when p values are examined, it is observed that these results are significantly different. Although the CWOA1, CWOA3, CWOA4, CWOA7, CWOA9 and CWOA10 for the F4 function give better results on average, the results are not significant when p values are considered. All chaos-based algorithms for F7 function are better in terms of average and standard deviation values, but there is a significant difference only for the CWOA4 algorithm. As a result, chaos-based WOA algorithms perform better for 5 out of the 7 functions, so the performance of the exploitation phase seems to be increased. The graphs of benchmark functions for two dimensions are illustrated in figure 6. The functions F8-F13 are multimodal functions with more than one local optimum. For this reason, multimodal functions also allow us to evaluate the performance of the exploration phase [1]. When the results are examined, for F8 function in CWOA1 and CWOA8 algorithms, for F10 function in all algorithms except CWOA1, CWAO5 and CWOA7, for F9 function in all algorithms except CWOA1 and CWOA7, for F11 function in all algorithms except CWOA2 and CWOA6, in all algorithms for F12 function and for F13 function in CWOA1, CWOA5, CWOA6 and CWOA8 algorithms, no significant difference is found although better results are obtained than WOA in terms of standard deviation and mean values.
Table 3. Statistical results of chaos-based WOA algorithms F1 Mean Std p value F2 Mean Std p value
p value F4 Mean Std p value F5 Mean Std p value F6 Mean Std p value F7
0 Woa 30,7143 28,5513 0 Woa 27,2006 0,4039 0 Woa 0,0935 0,1123 0 Woa
Mean Std p value F8 Mean Std p value F9 Mean Std p value F10 Mean Std
0,0014 0,0016 0 Woa -11893,89 1174,24 0 Woa 1,89E-15 1,04E-14 1 Woa 4,32E-15 2,72E-15
0,001 0,001 0,102 CWoa2 -11970,86 -11541,29 832,63 1424,41 0,3709 0,3185 CWoa1 CWoa2 5,68E-15 0,00E+00 2,29E-14 0,00E+00 0,75 1 CWoa1 CWoa2 4,80E-15 3,85E-15 2,16E-15 2,10E-15
0,0009 0,001 0,0719 CWoa7 -11606,59 1398,24 0,4405 CWoa7 0,00E+00 0,00E+00 0,00E+00 0,00E+00 5,68E-15 0,00E+00 0,00E+00 0,00E+00 0,00E+00 2,29E-14 1 1 1 1 0,75 CWoa3 CWoa4 CWoa5 CWoa6 CWoa7 3,73E-15 3,73E-15 4,32E-15 3,61E-15 4,44E-15 2,36E-15 2,54E-15 2,55E-15 2,22E-15 2,47E-15
p value F11 Mean Std p value F12 Mean Std p value F13 Mean Std p value
0 Woa 0,0013 0,0071 1 Woa 0,0077 0,0345 0 Woa 0,0294 0,0304 0
7,41E-108 2,29E-107 1,21E-108 2,62E-108 1,37E+105 1,84E-106 4,64E-107 4,95E-106 7,80E+109 7,05E-107 2,32E-107 1,07E+106 6,36E+108 5,97E-108 7,52E-105 6,33E-106 2,47E-106 1,81E-105 2,27E+108 2,81E-106 0,0007 0,0017 0,0001 0,0014 0,0034 0,0316 0,0001 0,0082 0 0,001
0,0017 0,0026 0,7036 CWoa9 -12091,77 -11496,99 985,96 1506,79 0,3185 0,3709 CWoa8 CWoa9
Figure 6. Graph of benchmark functions Overall, when evaluated, the best performance is shown by the CWOA4 and CWOA8 algorithms, the performance of other algorithms is close to each other, and the performance of the exploitation phase is improved rather than the exploration phase.
4.1. Data Clustering Application
In this section, data clustering problem is solved by combining FCM and the proposed chaos based WOA algorithms. In addition to, the effect of changing the distance function of the FCM algorithm and of the normalization of chaos maps on the data clustering are evaluated. Fuzzy C-Means Algorithm (FCM) The FCM clustering divides a given set of n elements of 𝑋 = {𝑥1 , 𝑥2 , … , 𝑥𝑛 } data into c fuzzy sets [48]. A vector 𝑣𝑖 = [𝑣1 , 𝑣2 , … , 𝑣𝑐 ], represents the ith cluster center. Each data sample has a membership degree represented by the membership matrix. The sum of the membership grades of all the clusters of a dataset should be 1. If data is closest to that cluster, then the membership level of the cluster will be larger. The membership matrix is represented as follows [48]. ∑𝑐𝑖=1 𝑈𝑖𝑗 = 1
The FCM algorithm is an objective function-based algorithm that tries to minimize the following objective function, which is the generalization of the least squares method [48]. 2
The algorithm is initiated by the random assignment of the membership matrix. Then cluster centers are calculated according to Equation 3 [48]. ∑𝑛 𝑈 𝑚 𝑥𝑖
According to the calculated cluster centers, U matrix is updated using the following formula [48]. 𝑈𝑖𝑗 =
The above operations are repeated until the difference between the old matrix and the new matrix is smaller than stopping criteria (𝜀). In FCM algorithm, distance of data to cluster centers is measured by Euclidean distance function which is the shortest distance between two points. The distance between point A and point B is calculated by the following formula, where 𝐴(𝑥1 , 𝑦1 ) and 𝐵(𝑥2 , 𝑦2 ) are two different 1120
points in a plane [52]. 𝑑𝑜𝑘𝑙𝑖𝑑 = √(𝑥1 − 𝑥2 )2 + (𝑦1 − 𝑦2 )2
There are many different techniques for calculating the distance between two points. The suitability of the selected technique may vary according to the nature of the given data and the size of the data set [53]. Since the Euclidean distance is not always efficient in complex shapes [54], in this study Chebyshev distance is selected as the distance function of the FCM algorithm rather than Euclidean distance. The Chebyshev distance is the number of chess moves that must be made to pass another square in the chessboard. Thus, it is also known as the distance of the chessboard. The distance between the points 𝐴(𝑥1 , 𝑦1 ) and 𝐵(𝑥2 , 𝑦2 ) is calculated by the distance function Chebyshev as [52]: 𝑑𝑐ℎ𝑒𝑏𝑦𝑠ℎ𝑒𝑣 = 𝑚𝑎𝑥(|𝑥1 − 𝑥2 |, |𝑦1 − 𝑦2 |)
4.2. Data Clustering with FCM and CWOA Algorithms
Data clustering aims to cluster a data set that composed of a number of data rows in a certain number of clusters according to the ratio of their similarities to each other. A data row can include several features in its columns according to the properties of the data set. In this study the population matrix X for the FCM-CWOA algorithms are defined as follows: 𝑥11 ⋯ 𝑥1,𝑐𝑥𝑘 ⋱ ⋮ ] 𝑋=[ ⋮ (18) 𝑥𝑛1 ⋯ 𝑥𝑛,𝑐𝑥𝑘 where n is the number of elements in the data set, k is the number of features in the k data set, and c is the number of clusters. Each row of the matrix X represents a candidate cluster centers and FCM-CWOA algorithms tries to minimize the FCM objective function. The pseudo code of the FCM-CWOA algorithms are given in Figure 7. Start the whale population, 𝑋𝑖 (𝑖 = 1, 2, … , 𝑛) , with randomly generated cluster centers Calculate FCM objective function for each candidate cluster center 𝑋 ∗ : the best cluster centers While (t<maximum iteration) For each candidate cluster center update a, A, C, l, P update membership matrix U update the location of the current cluster center according to p. end for Check if that any candidate cluster center has exceeded the research space and correct it. Calculate FCM objective function for each candidate cluster center Update 𝑋 ∗ if there is a better solution. t=t+1 end while back to 𝑋 ∗ Figure 7. The pseudo code of the FCM-CWOA Algorithms
4.3. Evaluation Criteria
In order to evaluate the performance of the proposed algorithm on solving data clustering problem, in this study the Rand and the Adjusted Rand Indexes are used.
Rand and Adjusted Rand Index The Rand index, which calculates the similarity ratio between two clusters, is one of the most commonly used indices. It calculates the accuracy of clustering by finding how similar new clusters are to the actual clusters after clustering. The Rand Index is calculated using the following formula [55]: 𝑅𝐼 = (𝑛𝑠 + 𝑛𝑑 )/𝑁
where 𝑛𝑠 is the number of point pairs assigned to the same cluster, 𝑛𝑑 is the number of pairs of points assigned to different clusters, and N is the number of all pairs of points in the dataset. If the two sets being compared are exactly the same, the Rand Index is 1 and if it is completely different, or if it contains a single element, the Rand Index is 0 [55]. The Adjusted Rand Index is the corrected version of the Rand Index. Similarity calculations based on estimation. The Adjusted Rand index gets -1 in the worst estimate and gets 1 the best estimate. The Adjusted Rand Index is calculated by the following formula [56]. 𝐴𝑅𝐼 =
where 𝑎𝑖 is the current index value, 𝑏𝑖 is the expected index value, and max (𝑎𝑖 ) is the maximum index value.
4.4. Experimental Results
Each of the CWOA1, CWOA2…, CWOA10 algorithms were hybridized to the FCM algorithm and data clustering algorithms, named FCM-CWOA1, FCM-CWOA2..., FCMCWOA10, were proposed. In section 3.1, it was mentioned that the chaos maps used were passed through an adaptive normalization process. For better understanding of effect of this normalization process, data clustering was performed with chaotic WOA algorithms integrated with non-normalized chaos maps. These hybrid algorithms were named CWOA1*, CWOA2*…, CWOA10*. In addition, to avoid the existing disadvantages of the Euclidean distance, all distances in the FCM algorithm was calculated with the Chebyshev distance function. And the revised FCM algorithm was integrated with chaotic WOA algorithms and proposed new hybrid algorithms called FCWOA1-c, FCWOA2-c..., FCWOA10-c. Clustering performance of the FCMWOA, FCM-CWOA and FCWOA-c algorithms was evaluated with six different data sets selected from the UCI Machine Learning Repository. These data sets have the following characteristics; Iris dataset that has 150 data with 4 attributes, Balance Scale dataset has 625 data with 4 attributes, User Modeling dataset has 403 data with 5 attributes, Breast Cancer dataset has 699 data with 10 attributes, Seeds dataset has 210 data with 7 attributes, Fertility dataset has 100 data with 10 attributes. Proposed algorithms were compared with each other, K-Means, FCM, FCMALO, FCMGWO, FCMPSO and FCMSCA algorithms. ALO, GWO, PSO and GWO algorithms were hybridized with FCM in the same way as the WOA algorithm. All algorithms have been run 30 times. In the all of the algorithms parameter of m has been selected as 2, maximum number of iterations as 1000 and population size as 50. The closeness of the clustering results of algorithms to the real results was tested with two indexes, Rand Index and Adjusted Rand Index, which are frequently used in the literature. All the work is done under the same conditions as the Intel Core i7-7700HQ CPU with a 2.80GHz processor and 16 GB Ram on a computer with MATLAB R2017b program. The obtained results are shown in Table 4-6. Table 4 shows that in most cases the proposed algorithms give better results than the compared algorithms. When the mean benchmark function, mean Rand Index and mean Adjusted Rand Index values for the Iris dataset are examined, it is seen that all of FCWOA-c algorithms give better results. Although the best maximum index values are obtained by FCMSCA algorithm, the average index values are low. The FCWOA-c algorithms for the Balance Scale dataset yield better results in terms of benchmark function, but only FCWOA2, FCWOA4, 1122
FCWOA6, and FCWOA7 algorithms perform well in terms of mean index values. Also, the clustering performance of the FCMWOA algorithm is significantly better than the FCM. For the User Modeling dataset, the FCMWOA algorithm yield better results than other algorithms. Although FCWOA-c algorithms have minimized the objective function better, it seems that this situation has no effect on clustering accuracy. In addition, the best clustering for this dataset is performed by FCM, FCMALO, FCMPSO, and FCMGWO algorithms. In the Breast Cancer dataset, although the FCM algorithm minimized the benchmark function better, K-means is observed to have higher clustering accuracy. In addition, the best result for maximum index values is obtained by FCWOA3-c algorithm. As for Seeds dataset, the maximum index values in all of the proposed algorithms are higher than the compared algorithms. However, FCWOA2-c, FCWOA7-c and FCWOA9-c algorithms have low mean index values. Lastly, in the Fertility dataset, all of the FCWOA-c algorithms are better than the other algorithms in terms of average benchmark function, maximum and mean index values. Though the aim is to minimize the benchmark function, it is important to note that the benchmark function is not critical in comparing the data clustering results since the distance function is changed here. While the benchmark function values are good, index values may be low. Table 4. The data clustering results of the proposed algorithms
Therefore, Rand and Adjust Rand index values are considered as priorities when evaluating the results. In order to better observe the effect of the distance function on data clustering Table 4, Table 5 and Table 6 should be considered together. 5 out of the FCM-CWOA algorithms for the Iris dataset yield better than FCM, while all of FCWOA-c algorithms are better than FCM. 8 out of the FCM-CWOA algorithms for Balance Scale dataset perform better than FCM but with a minor difference. 4 out of FCWOA-c algorithms are significantly better than FCM for this dataset. In User Modeling dataset, all FCM-CWOA algorithms are better than FCM, however, FCWOA-c algorithms are far behind the FCM in terms of clustering performance. No performance improvement is observed in the FCM-CWOA algorithms for the Seeds dataset. Contrary to this, 7 out of the FCWOA-c algorithms yield better result than existing algorithms for this dataset. The FCM-CWOA algorithms in the Fertility dataset are not better than K-Means, but 1123
perform slightly better than FCM. Namely, it observed that performance of FCWOA-c algorithms is better than FCM-CWOA algorithms. As a result, it can be said that changing the distance function has a positive effect on the clustering performance. Comparison of clustering results of FCM-CWOA and FCM-CWOA* algorithms are given in Table 5 and Table 6. When the results are examined, it is seen that normalization of chaos functions increases the data clustering performance of algorithms. For example, FCM-CWOA* algorithms in Iris and Breast Cancer datasets have very good results in maximum index values but average index values are low. That is, algorithms can achieve good results in only a few of 30 consecutive runs. It is observed that normalization of chaos functions increases the number of successful results by making this situation more stable. Although there is a similar case for the User Modeling and Seeds dataset, FCM-CWOA algorithms are by far better than FCM-CWOA* algorithms. In contrast to these examples, the use of non-normalized chaos functions in the Balance Scale and Fertility datasets are more useful and FCM-CWOA* algorithms perform better than FCM-CWOA algorithms. As a result, it can be concluded that the proposed hybrid algorithms successfully clusters most of the dataset tested and show better clustering performance than the compared algorithms. Table 5. Comparison of clustering results of FCM-CWOA and FCM_CWOA* algorithms
Table 6. Comparison of clustering results of FCM-CWOA and FCM_CWOA* algorithms
5. Conclusion
In this paper, the Whale Optimization Algorithm (WOA), a global optimization algorithm inspired by the hunting behavior of humpback whales, has been hybridized with the Fuzzy CMeans (FCM) algorithm after its performance was improved with chaos maps using an adaptive normalization method. To improve the performance of the WOA algorithm, a randomly selected parameter of the algorithm (a) was modified with 10 different chaos maps which each collected with a value after normalization process. And chaotic WOA algorithms were proposed. The performances of these algorithms were evaluated in terms of mean benchmark function, standard deviation, and Wilcoxon Sign Rank Test at 0.05 significance level and they were tested with 13 different benchmark functions. In addition, hybrid data clustering algorithms were developed by integrating FCM with proposed chaotic algorithms. In order to increase the data clustering performance of the proposed hybrid algorithms, all the distances in the FCM algorithm were calculated by using the Chebyshev distance function instead of Euclidean and the new hybrid clustering algorithms were proposed. The clustering performances of the hybrid data clustering algorithms were measured with the benchmark function, Rand Index and Adjusted Rand Index values for 7 different datasets selected from the UCI Repository database and then compared with the K-means, FCM, FCMWOA, FCMPSO, FCMALO, FCMGWO and FCMSCA algorithms. Also, the effect of changing the distance function of the FCM algorithm and of the normalization 1125
of chaos maps on the data clustering were evaluated. As a result, it has been seen that chaos functions improve the optimization performance of WOA algorithm, integrating chaotic WOA algorithms with FCM algorithm improves disadvantages of FCM algorithm, changing distance function increases clustering performance of algorithms.
Share and Cite
ARSLAN, H.; TOZ, M. Data Clustering Based on Fuzzy C-Means and Chaotic Whale Optimization Algorithms. Sigma Journal of Engineering and Natural Sciences 2019, Vol. 37, pp. 1107-1128. https://doi.org/10.62051/ytu.sigma-journal-of-engineering-and-natural-sciences-data-clustering-based-on-fuzzy-c-means-and-chaotic-whale-optimization-algorithms