{'fraction_non_alphanumeric': 0.02491940072065238, 'fraction_numerical': 0.009368480940641001, 'mean_word_length': 4.548400673400673, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Efficient Hybrid Algorithm using Cuckoo Search and Differential Evolution for Data Clustering

In recent years many swarm intelligence-based algorithms have been proposed. Most of them are nature inspired algorithms such as Artificial Bee Colony (ABC)1, Particle Swarm Optimization (PSO)2 and Ant Colony Optimization (ACO)3. Cuckoo Search (CS) is also one of the nature inspired algorithm proposed by Yang and Debin4. Functional evaluation in one evolutionary algorithm indicates to the number of calls of the objective function. In one evolutionary algorithm a good convergence speed and reaching to the good accuracy and also having less number of functional evaluations is important. The CS algorithm has the problems of much number of functional evaluation and also it sometimes easily get trapped in local minima and this point causes having less convergence speed and also less accuracy. To tackle these problems, in this paper a Hybrid approach proposed by combining CS and Differential Evaluation (DE) (HCSDE). The DE algorithm is also an efficient Meta Heuristic algorithm. DE uses the differences between randomly selected vectors (chromosome and individuals)5. The hybrid approach in this paper helps CS algorithm to reduce the number of functional evaluations and also obtaining better convergence speed and accuracy. Data Clustering (cluster analysis) is an unsupervised method for making batches of objects in which objects that belong to a particular cluster are similar to each other and are dissimilar from different clusters. Data Clustering is a vital technique for Image Segmentation6, Fraud Detection7, Biomedical Data8, wireless mobile sensor networks9, and other applications that we encounter in some fields of sciences and engineering. Clustering algorithms is organized in two main types: Hierarchical Abstract


Introduction
In recent years many swarm intelligence-based algorithms have been proposed. Most of them are nature inspired algorithms such as Artificial Bee Colony (ABC) 1 , Particle Swarm Optimization (PSO) 2 and Ant Colony Optimization (ACO) 3 . Cuckoo Search (CS) is also one of the nature inspired algorithm proposed by Yang and Debin 4 . Functional evaluation in one evolutionary algorithm indicates to the number of calls of the objective function. In one evolutionary algorithm a good convergence speed and reaching to the good accuracy and also having less number of functional evaluations is important. The CS algorithm has the problems of much number of functional evaluation and also it sometimes easily get trapped in local minima and this point causes having less convergence speed and also less accuracy. To tackle these problems, in this paper a Hybrid approach proposed by combining CS and Differential Evaluation (DE) (HCSDE). The DE algorithm is also an efficient Meta Heuristic algorithm. DE uses the differences between randomly selected vectors (chromosome and individuals) 5 . The hybrid approach in this paper helps CS algorithm to reduce the number of functional evaluations and also obtaining better convergence speed and accuracy. Data Clustering (cluster analysis) is an unsupervised method for making batches of objects in which objects that belong to a particular cluster are similar to each other and are dissimilar from different clusters. Data Clustering is a vital technique for Image Segmentation 6 , Fraud Detection 7 , Biomedical Data 8 , wireless mobile sensor networks 9 , and other applications that we encounter in some fields of sciences and engineering. Clustering algorithms is organized in two main types: Hierarchical and Partitional clustering algorithm. A Partitional algorithm makes one partition from a dataset and is used for huge datasets whereas the hierarchical type makes array of nested partitions. K-means is one type of partional algorithm that is familiar to most of the researchers who are working on problems related to data clustering issues 10 . Unfortunately k-means algorithm has some problems, first it must know the number of the cluster at the beginning of algorithm, second it is depended on initial centroids and this may send algorithm to the danger of local minima solutions [10][11][12] . Using Evolutionary algorithms, we rarely encounter the drawbacks of k-means algorithm. In recent years, many researchers have proposed many evolutionary algorithms for clustering problem. Niknam et al. proposed an evolutionary optimization algorithm based on ACO and Simulated Annealing (SA) to solve the clustering problem 13 . Niknam et al proposed a Hybrid Evolutionary algorithm based on PSO and SA to find optimal cluster centers 14 . Niknam and Amiri proposed an efficient hybrid approach based on PSO, ACO and K-means for cluster analysis 15 . Chi-Yang Tsai et al proposed a new evolutionary algorithm based on PSO with selective particle regeneration for data clustering 16 20 . This paper focused on the partitional clustering algorithm and it uses the proposed algorithm (HCSDE) for it. We test the efficiency of the proposed algorithm by employing six standard benchmark dataset from UCI machine learning repository and we claim that the proposed algorithm is efficient in terms of reducing number of functional evaluation and also obtaining better convergence speed and accuracy. So the objective and motivation of this work is removing the mentioned problems of CS algorithm and also proposing an efficient algorithm for data clustering in comparison with the employed algorithms. The proposed algorithm also can be used for the other optimization problems. The rest of the paper is organized as follows: In section 2 we will debate the clustering problem. In section 3 we will discuss standard CS. In section 4 we will describe standard DE. We will introduce HCSDE in detail in section 5. In section 6 we will test the proposed algorithm on six datasets from UCI for the clustering problem, finally in section 7 the conclusions will be drawn.

The Clustering Problem
Clustering aims to find a set of patterns, points or objects. It tries to represent n objects, find k groups based on measure of similarity In which objects that are belongs to the same cluster are similar as possible to each other and objects in different clusters are dissimilar as possible. Generally, similarity and dissimilarity are mutual concepts. Usually, similarity used to describe how similar two data points are or how similar two clusters are. If the similarity coefficient be greater, it means that two clusters and two data points are more similar. Dissimilarity measure or distance is the other way around. The greater dissimilarity or distance indicates to that, the two data points or two clusters are more dissimilar 10 . Let O = {o 1 , o 2 ,..., o n be the set of n objects and the k cluster be represented by {c 1 , c 2 ,..., c k }. Then: C i ϕ ≠ for i,j = 1,2,...,k,wC i Ư C j for i,j = 1,2,...,k, and i ≠ j, and One of the similarity criteria is the total Mean Square Quantization Error (MSE) Equation (1). MSE is a clustering quality measure and indicates to the total within cluster variance, and aims are minimizing this measure to find the most compact partitioning for the k partitions. Where ||o j -c j || 2 shows the similarity between the ith object and the center of the jth cluster. The Euclidean distance is probably the most well known metric that we have ever used which is derived from Minkowski metric Equation (2).
Where d (o j , c j ) is a function that denotes to a dissimilarity measure between object i and j. In this research we also use Euclidean distance as a distance metric. As mentioned above, we will focus on partitional algorithms. One of the most used partitional classes is the center based type. K-means, as a well known clustering algorithm, belongs to this class of partitional algorithms 14 .
The steps of k-means algorithm are as follows 21 Where n i is the number of elements that belongs to the cluster c i . 4. Repeat step 2 and 3 until the termination criteria are satisfied.
K-means is a fast algorithm but it is trapped easily in local minima because of the sensitivity to the initial cluster centers.

Cuckoo Search Algorithm
In this section we will introduce Cuckoo Search algorithm briefly.

Cuckoo Breeding Behavior
Cuckoo is one of brood parasites birds. Yang and Deb by studying the life style of this bird proposed an algorithm called cuckoo search in 2009.This bird has a reproduction strategy for her survive. Cuckoo laid her eggs in nest of other birds called host birds. Some host birds can diagnose and detect cuckoo eggs, so in this case they will do two actions, they may throw the cuckoo eggs out or they may abandon their nest and go to another place to live in. One interesting thing about some species of cuckoos is that, they have evolved in such a way that female parasitic cuckoo scan imitate the colors and patterns of the host bird eggs, doing this action can reduce discovery rate and increase their productivity. In addition, egg laying in some species takes time. In general, the cuckoo eggs hatch faster than their host eggs. When the first cuckoo chick hatches, it evicts the host eggs by blindly propelling the eggs out of the nest. This action helps to increase the cuckoo chicks share provided foods by its host bird. Studies also show that cuckoo chick can mimic the call of host chicks and this action also help to improve feeding opportunity 4 .

Levy Flight
The earlier studies show that the foraging path of animal is a random walk, because the next move depends on both, the current location/state and the transition probability to the next location. A random walk is a random activity. It includes taking a series of consecutive random steps. A levy flight is a random walk whose step length obeys the levy distribution. Studies also show that the behaviors of human like ju/hoansi hunter express foraging patterns which are a case of typical features of levy flights. Levy flights have many applications, for example many physical phenomena like cooling behavior and noise, reflect the features of levy flights in right conditions 22 .

Cuckoo Search Algorithm Implementation
Cuckoo search is based on three idealized rules: • Each cuckoo lays one egg at a time, and dumps it in a nest which was chosen randomly. • The nests with high fitness of eggs (solutions) are transferred to the next generation. The number of available host nests is fixed. And the discovery probability rate by the host bird is considered with the probability p a  [0,1]. In this case, the host bird can throw the foreign egg away or abandon the nest and build a completely new nest in another place 23 .
For simplicity, the last assumption can be dealt with the fraction pa of the n nests and replaced by new nests (new random solutions), in a nest each egg represents a solution and a new solution represented by a cuckoo egg. The aim is to use and replace new and high fitness solutions (cuckoos) instead of solutions that are not good. This algorithm can be enhanced to the extended form such that each nest has multiple eggs representing a set of solutions 4,23 . The pseudo code is shown in Figure 1.
When new solution x (t+1) is generating for ith cuckoo the following levy flight performed as: Where ∂ is the step size which should be related to the scales of the problem of interest. We can use ∂ = 1 in most cases. The product ⊕ means entry wise multiplications 23 . Levy flight essentially provides a random walk while their random steps are drawn from a levy distribution for large steps.
( 1 ) Which has an infinite variance with an infinite mean, here the consecutive jumps/steps of a cuckoo essentially from a random walk process, obeys a power-law steplength distribution with a heavy-tail? In the real world if cuckoo eggs be most similar to the host eggs, then the probability of cuckoos egg discovery is less, thus the fitness should be related to difference in solutions. Therefore, it is a good idea to a random walk in a biased way with some random step sizes location 23 . Obviously, the generation of step sizes samples is not trivial using levy flights. A simple scheme in Yang can be briefly discussed as: Here Γ is the standard gamma function.

Differential Evolution Algorithm
Differential Evolution (DE) is one of the evolutionary algorithm aims at evolving a population of NP D-Dimensional Parameters Value 5 . First phase of this algorithm like most of the other evolutionary algorithms is initialization phase. The initial population should cover the entire search space by uniformly randomizing individuals constrained by lower bound and upper bound parameters F o r example the initial value of the jth parameter in the ith individual at the generation G = 0 is generated by:

Mutation Operator
Second phase of the algorithm is mutation operation to produce a mutant vector V I,G with respect to each individual X i,G . in the current population one of mutation strategy is shown as follows: The indices r 1 i ,..., is mutually exclusive integer randomly generated within the range [1; NP], which also different from index i, the scaling factor F is a positive control parameter for scaling the difference vector.

Crossover Operator
The third phase of DE is crossover. It is performed after mutation and is applied to each pair of the target vector X iG and its corresponding mutant vector V i,G to generate a trial vector: ) . Crossover can be performed as the following equation: In equation 11, j = 1, 2,…D, CR indicates to crossover rate. It is a constant value within the range (0;1), which controls the fraction of parameter values copied from the mutant vector. j rand is a randomly chosen integer in the range [1,D]. As it is shown from Eq 11 if rand j [0,1) ≤ CR or j = j rand , the binomial crossover operator copies the jth parameter of the mutant vector V i,G to the corresponding element in the vector U i,G .

Selection
The next generation will be selected among the individuals in current population. The objective function of each trial vector f(u i,G ) is compared with its corresponding target vector f(x i,G ). If f(u i,G ) has less or equal objective function value than the f(x i,G ) in current population, the trial vector will replace the target vector, so the next generation of population will be created, otherwise the target vector will remain in the population for the next generation. Selection can be performed as follows equation: The pseudo code of DE algorithm is shown in Figure 2.

Proposed HCSDE Algorithm
In this section we will introduce the proposed hybrid algorithm. As mentioned in section 3, cuckoos don't make their own nest but they lay their eggs in the nest of other birds called host birds, in this case p a percent of eggs maybe discovered by the host birds, so they will either throw these alien eggs away or simply abandon their nest and build new nest elsewhere. For simplicity in CS algorithm the fraction pa percent of the n nests will be replaced by nests that are produced randomly. The randomly production of nests may make tow weaknesses for the CS algorithm. First as the dimension exchange it doesn't help to have good information exchange among cuckoos, so it causes lower convergence speed. Second it may doesn't help reaches to better nest and subsequently better fitness.  (8). S is a randomly selected solution and bestnest is the best solution ever found.
The pseudo code of the HCSDE is shown in Figure 3. The proposed algorithm is much easier to implement in comparison with the hybrid algorithms mentioned above. First step of the algorithm is initializing population. The HCSDE uses Equation (9) to produce initial population. In step 2 CS algorithm uses Mantegna levy distribution to produce new nests based on the Equation (13). It produces 1-p a percent nests of n nests for the algorithm. Then evaluating the fitness of these nests will be done in this step. In step 3 instead of producing pa percent of nests randomly, the HCSDE benefits from DE algorithm's operators like mutation and crossover to produce new nests. Then evaluating the produced nests of this step will be done. Finally the HCSDE compares the two obtained fitness values of each step 2 and 3 and it stores the best nest (solution) and best fitness. The HCSDE sorts the population for each iteration of algorithm. This means that the proposed algorithm feeds step 2 with top nests. After some experiments we found out that it is better to assign these top nests to this step because by implementing this on the proposed algorithm, it reaches better results finally.

Experimental Results
In this section we will describe the results and statistical analysis in detail. In our experiment we employed six datasets named Iris, Wine, Contraceptive Method Choice (denoted as CMC), Wisconsin Breast Cancer (denoted as cancer), Glass and Vowel. They can be found in 27 . Table 1 shows the properties of these data sets.

Datasets
Iris data (N = 150, d = 4, k = 3). This is the iris data set. These data sets with 150 random samples of flowers from the iris species Setosa, Versicolor and Virginica are collected by Anderson. From each species there are 50 observations for Sepal Length, Sepal Width, and Petal Length and Petal Width in cm. This dataset is illustrated in Figure 1 28 .
Wine data (N = 178, d = 13, k = 3). This is the wine data set, from MCI laboratory. These data are the results of chemical analysis of wines grown in the same region in Italy but derived from three different cultivars. The analysis determined the quantities of 13 constituents found in each of the three types of wines. There are 178 instances with 13 numeric attributes in the wine data set. All attributes are continuous. There is no missing attribute value 28. Contraceptive method choice (N = 1473, d = 9, k = 3). CMC is a subset of the 1987 national Indonesia contraceptive prevalence survey. The samples are married women who were either not pregnant or do not know if they were at the time of the interview. The problem is to predict the current contraceptive method choice (like no use, long-term method, or short-term methods) of a woman based on her demographic and socioeconomic characteristics 28 .
Wisconsin Breast Cancer (N = 683, d = 9, k = 2).The WBC data set consists of 683 objects characterized by nine features: Clump Thickness, Cell Size Uniformity, Cell Shape Uniformity, Marginal Adhesion, Single Epithelial Cell Size, Bare Nuclei, Bland Chromatin, Normal Nuclei, and Mitoses. There are two categories in the data: malignant (444 objects) and benign (239 objects) 28 .

Parameters Setting for the Involved Algorithms
In this experiment, each algorithm was run for 50 individual times with random initial solutions on every datasets. The population size of all algorithms was 50. The comparison algorithms are BH, PSO, GSA, and BB-BC by Hatamlou 29 , and also we implemented clustering on original codes of CS algorithm 4 and DE algorithm 5 . After experiments we found out p a = 0.7 and β = 1.9 have better results for the standard CS and PCR = 0.2 (crossover rate) and sc min = 0.2 and sc max = 0.8 as scaling factor have better results for DE algorithm. As a measure criterion in this experiment we use the max number of running iterations and the iteration size was set to 500 for every algorithm. All algorithms were implemented in Matlab 2009a using a computer with Intel core 3, 2.5GHz, 4GB RAMS. The operating system of the computer was windows 7.

Simulation Results
We will discuss the performance of the proposed algorithm, considering the two following criteria: • Sum of intra-cluster distances as an internal quality measure: The distance between each data vector in a cluster and the centroid of that cluster is calculated and summed up, as defined in Eq. (2). • Error rate (ER): It is defined as the number of misplaced points over the total number of points in the dataset, as shown in Eq. (14).
Where n denoted to the number of data points and M is the total number of misplaced points.
The summary of the intra-cluster distances obtained by the clustering algorithms is shown in Table 2. These values arranged in best, average, worst and STD values. Best indicates the best total within-cluster variance for 50 runs. Average indicates the mean total within-cluster variance for 50 runs. Worst indicates to the worst total within cluster variance for 50 runs and STD indicates the Standard Deviation. It can be seen from Table 2 and 3 that HCSDE outperforms other algorithms in all datasets except in glass dataset. In iris dataset HCSDE and BH have results close to each other but standard deviation of HCSDE is better than the other algorithms which mean that HCSDE reaches minimum value each time. PSO is a little worse than the other algorithms. The convergence speed of HCSDE is much better than the others. The CS algorithm has the worst convergence speed; this is shown in Figure 4(a).
In wine dataset HCSDE outperforms other algorithms and has better intra-cluster distance value. It also has efficient standard deviation in comparison with the other algorithms. DE has closer result to the HCSDE, PSO, GSA and BB-BC algorithms in worst case. The convergence  speed of HCSDE is better than the other algorithms. This is shown in Figure 4(b). In CMC dataset, HCSDE can produces much better results in terms of convergence speed, accuracy and standard deviation in comparison with the other algorithms. BH can produces results close to the proposed algorithm and the results of the other algorithm are much weaker than the two above algorithms. The convergence speed of the algorithms is shown in Figure 4(c).
In cancer dataset HCSDE, DE, BB-BC and BH have closer results to each other but the proposed algorithm can produces better results finally. CS, GSA and PSO have weaker results in comparison with three above algorithms. The proposed algorithm also has superiority in obtaining better Standard Deviation and convergence speed. These are shown in Table 2 and Figure 4(d).      In Glass dataset, BH algorithm outperforms the other algorithms. In this dataset the proposed algorithm is weaker than the BH algorithm but its result is really close to the BH algorithm and also is much better than the other five algorithms. GSA algorithm has the worst result in this dataset with respect to the other algorithms.
In vowel dataset the proposed algorithm has superiority with respect to the other six algorithms. It can obtain much better accuracy and also has reasonable standard deviation. BH algorithm has closer result to the proposed algorithm and PSO algorithm has the worst results in comparison with the other algorithms.
The best centroids obtained by the proposed algorithm are shown in Tables 4-9. The values of these tables can be used for reaching to the best results of Table  2 by assigning the data objects within each dataset to the corresponding centroids in Tables 4-9. Error rate obtained by the clustering algorithms from 50 simulations on the employed datasets is shown in Table 3. In five datasets, the proposed algorithm has minimum error rate except in glass dataset. In iris dataset HCSDE and BH have the minimum error rate in comparison with the other algorithms. In wine, CMC, cancer and vowel HCSDE also has superiority to the others in obtaining the minimum error rate. In glass dataset BH obtained the minimum error rate, however there is no correlation between the intra-cluster distance and the error rate but HCSDE is weaker than BH in this dataset as it was for intra-cluster distance value too.

Statistical Analysis
In this subsection we will have a statistical test on the proposed algorithm.

Wilcox on Signed Rank Test
Swarm intelligence-based algorithms have stochastic nature. Because of this point they sometimes reach the solutions by chance, so it is more important to use statistical tools to test the problem-solving success. A problem based pair wise test is used to check which one of the two algorithms solves a specific numerical optimization problem with greater statistical success 30 . In this paper we also used the global minimum values obtained by 50 runs for the problem-based pair wise of the algorithm. We employed Wilcox on Signed Rank Test for pair wise comparison, with the statistical significance value α = 0.05. Considering the two algorithms named x and y, the null hypothesis H0 for this test, shows there is no difference between the median of the solution obtained by the algorithm x and the median of the solution obtained by the algorithm y. To determine which algorithm obtained better results, the size of ranks were provided by the Wilcox on signed rank test. In Table 10, T + is the sum of ranks for the problem in which the first algorithm outperforms the second one (its rival) and T − shows the sum of the ranks for the second algorithm (the proposed algorithm here) in which it has superiority. "+" indicates the cases in which null hypothesis was rejected and in fact HCSDE shows its superiority in the problembased comparison test at the 95% significant level (α = 0.05), "-" indicates the cases in which the null hypothesis was rejected and HCSDE does not have the superiority, "=" indicate to the cases which there is no statistical difference between the two algorithms. It is shows from Table 10 that HCSDE is statistically more successful in comparison with the other algorithms.

Conclusions and Future Works
In this paper we proposed an efficient hybrid algorithm for data clustering. The proposed algorithm benefits from DE to produce new nests in standard CS in order to obtain better results and it also benefits from Mantegna Levy Flight to boast the local search. It shows that the proposed algorithm outperforms the others and has better total within-cluster variance value in comparison with CS, DE, PSO, GSA, BB-BC and BH. In section 6 we showed that the proposed algorithm satisfies the characteristics that we claimed in section 1. We tested HCSDE with six well known real datasets from UCI machine learning repository. It is obvious from Table 2 and 3 that the proposed algorithm has better accuracy and error rate with respect to the other algorithms. However the proposed algorithms get into local minima in some cases, so improving features of the algorithm could be considered as the future work.