INTRODUCTION

Clustering is a common data analysis task that aims to partition objects into homogeneous groups (classes). Clustering detects new classes of data without any a priori knowledge (Han and Kamber, 2004). Therefore, clustering is often also called unsupervised learning in contrast to classification where the classes are predefined and which is often also called supervised learning. The task of clustering has been effectively applied in statistics (Jain and Dubes, 1988), machine learning (Jain et al., 1999), scientific disciplines (Everitt et al., 2001), quality control (Zarandi and Alaeddini, 2010) and databases. Clustering techniques are categorized into several different approaches: partitioning, hierarchical, density based, subspace based, grid based and soft computing. Partitioning clustering algorithms compute a flat partition of the data set. Such Partitioning clustering are k-means, EM (Mclachlan and Krishnan, 1997), AntClust (Ouadfel and Batouche, 2007) and parallel and distributed k-mean (Hemalatha and Vivekanandan, 2008). Garg and Jain (2006) performed a study on clustering algorithms based on partition and variation of k-means algorithm. Velmurugan and Santhanam (2011) explored the behavior of some of the partition based clustering algorithms in their survey. Hierarchical clustering (Guha et al., 1999; Karypis et al., 1999; Ranjan and Khalil, 2007; Arora et al., 2009) builds a cluster hierarchy or, in other words, a tree of clusters. Hierarchical clustering can be further categorized into agglomerative (Abghari et al., 2009) and divisive methods based on how it is constructed. Subspace clustering technique (Agrawal et al., 1998; Friedman and Meulman, 2004; Zhou et al., 2007; Chu et al., 2009; Chu et al., 2010; Vijendra et al., 2010) searches interesting subsets of objects and their associated subsets of attributes. These techniques can be divided in two categories: partition based and density based approaches. Density-based clustering methods (Ester et al., 1996; Hinneburg and Keim, 1998; Sun et al., 2008; Yousria et al., 2009; Deng et al., 2010; Vijendra, 2011) group neighboring objects into clusters based on local density conditions rather than proximity between objects. In Grid-based clustering (Wang et al., 1997; Nagesh et al., 2001; Milenova and Campos, 2002; Pilevar and Sukumar, 2005) the objectspace rather than the data is divided into a grid. Genetic Algorithms (GAs) Goldberg (1989) are randomized search and optimization techniques guided by the principles of evolution and natural genetics. Murthy and Chowdhury (1996) have considered a partition to be encoded as a string of length n. A comparison of the performance of their algorithm with that of the k-means algorithm is also performed. Bandyopadhyay and Maulik, (2002) proposed a genetic algorithm-based efficient clustering technique that utilizes the principles of k-Means algorithm. It avoids major limitation of getting stuck at locally optimal values. Gautam and Chaudhur (2004) proposed a Genetic Clustering Algorithm with two-phase process. At the first phase the original data set is decomposed into a number of fragmented clusters. At the second phase hierarchical cluster merging algorithm is used for final clustering. Mitra (2004) proposed an evolutionary rough c-means clustering algorithm that model clusters as c rough sets, expressed in terms of upper and lower approximations. Lin et al. (2005) proposed a genetic clustering algorithm that selects the cluster centers directly from the data set. Ioannis et al. (2005) proposed a rule based Novel Evolutionary Algorithm (NOCEA) that evolves individuals of variable-length consisting of disjoint and axis-aligned hyper-rectangular rules with homogeneous data distribution. A new point symmetry distance based genetic clustering algorithm is proposed by (Bandyopadhyay and Saha, 2007), which incorporates both the Euclidean distance as well as a measure of symmetry with respect to a point in its computation. Nguyen and Cios (2008) introduced a novel clustering algorithm that combines the best characteristics of the k-means and EM algorithms but avoids their weaknesses. Lai and Chang (2009) proposed a clustering based approach using a Hierarchical Evolutionary Algorithm (HEA) for medical image segmentation. Vijendra et al. (2010) presented a Euclidean distance-based Genetic Clustering Algorithm (GCA) that finds a globally optimal partition of a given data sets into a specified number of clusters. Singh et al. (2011) also proposed a genetic algorithm with chromosome reorganize that removes the degeneracy of chromosome which makes the evolution process converge fast. In this paper, an evolutionary clustering algorithm is introduced to enhance the performance of clustering. Proposed evolutionary algorithm uses multiple randomized k-d trees to improve the performance for nearest neighbor in high dimensional data.

CLUSTERING

Data clustering is an NP complete problem of finding groups in data by minimizing some measure of dissimilarity. A cluster is a set of points that are similar and points from different clusters are not similar. Let the set of n points {x₁, x₂…., x_n} be represented by the set S and the K clusters be represented by C₁, C₂… C_k. Then:

For hard clustering, given N points to k clusters, the number of all possible clustering is (Liu, 1968):

(1)

For example there are N (25, 5) = 2,436,684,974,110,751 ways of sorting 25 objects into five groups. If the number of clusters is unknown the objects can be sorted:

ways. For our 25 objects this is over 4x10⁸ clustering. It is impractical for an algorithm to exhaustively search the solution space to find the optimal solution. Traditional clustering algorithms search a relatively small subset of the solution space. The probability of success of these methods is small. Clearly, we need an algorithm with the potential to search large solution spaces effectively. Genetic algorithms have been widely employed for optimization problems in several domains. Their success lies in their ability to span a large subset of the search space.

MULTIPLE RANDOMIZED KD TREES BASED NEAREST NEIGHBOR SEARCH

The most widely used algorithm for nearest-neighbor search is the k-d tree (Freidman et al., 1977). k-d tree is a space-partitioning data structure for organizing points in a k-dimensional space which iteratively bisects the search space into two regions containing half the points of the parent region. Queries are performed via traversal of the tree from the root to a leaf by evaluating the query point at each split. k-d tree does not work well for exact nearest neighbor search in high dimensional data because with high dimensional data, a k-d tree usually takes a lot of time to backtrack through the tree to find the optimal solution. The approximate nearest-neighbor approach can be used for improving the search speed over linear search. Proposed evolutionary algorithm nearest neighbor search is based on multiple randomized k-d trees (Silpa-Anan and Hartley, 2008). The k-d tree’s search performance have increased by using Principal Component Analysis that align the principal axes of the data with the coordinate axes.

A fast evolutionary algorithm for automatic evolution of clusters: In this section, the evolutionary clustering algorithm for automatic clustering is proposed. This algorithm uses a variable-length encoded chromosome to automatically clustering the data set. This evolutionary clustering approach is called Fast Automatic Clustering Evolution (FACE). The steps for proposed algorithm is shown in Fig. 2. Its different steps are discussed in the following.

Chromosome representation: Each individual in the population is represented by a chromosome of length n, where n is the number of objects in the data set. For instance, if the data set having 6 (x₁, x₂, x₃, x₄, x₅, x₆) objects is to be clustered according to number of clusters value k = 3. The objects will align from 1 to 6 and each of them will get a cluster number k = {1,2,3}. One example of chromosome representation is shown in Fig. 1.

The use of simple encoding scheme causes two problems. First problem occurs if one clustering solution can be coded by several different chromosomes. Second problem, the clustering invalidity occurs if the recombination operator reproduces new clustering solutions, whose number of clusters is smaller than the given number of clusters. These problems has solved by using the chromosome reorganization method (Singh et al., 2011).

Population initialization: For individual i, the number of clusters, denoted by K_i is randomly generated in the range [K_min, K_max].Here K_min is chosen as 2 and K_max is chosen to be (Lin et al., 2005). Where, N denotes number of objects. Each data points are assigned to the cluster with closed cluster center.

Fitness function: The fitness f of an individual is computed using the inverse of SSE (sum of squared error):

(2)

The SSE is defined as:

(3)

where xεC_i a data point assigned to that cluster C_i and cj is the center of the jth cluster.

Fig. 1:	Chromosome representation

Fig. 2:	Basic steps of FACE algorithm

Evolutionary operators
Selection: In proposed clustering algorithm (FACE), chromosomes are selected by using roulette wheel selection method (Goldberg, 1989). Here, each slot on the roulette wheel represents an individual. The area of the slot is directly proportional to the objective function value (fitness) of the individual. Each individual is selected by a spin of the roulette wheel. The probability of a chromosome being selected in any trial is proportional to its scaled fitness value within its subpopulation.

Crossover: Crossover operator combines the features of two parent chromosomes for generating two child chromosomes. The two problems, clustering invalidity and context insensitivity exists in the classical crossover operator. The FACE algorithm combines clustering solutions of different chromosomes. Randomly two chromosomes are selected form population. FACE randomly chooses j∈ {1, 2, ....., k} clusters from first chromosome and copied them in corresponding genes of second chromosome. Allele values of remaining genes are allocated to nearest clusters according to their centroids and relation between selected clusters of first chromosome and clusters of corresponding genes of second chromosome. In this way, FACE algorithm generates new offspring1 (child chromosome 3). The same procedure is applied for generating new offspring 2 (child chromosome 4) but now considering that the changed clusters of second chromosome are copied into first chromosome. Crossover probability is selected adaptively as in Srinivas and Patnaik (1994).

Let f_max be the maximum fitness value of the current population, be the average fitness value of the population and f’ be the larger of the fitness values of the solutions to be crossed. Then the probability of crossover, p_c, is calculated as:

(4)

Here, the values of k₁ and k₃ are equal to 1.0 (Srinivas and Patnaik, 1994). Clearly, when f_max = , then f’ = f_max and p_c will be equal to k₃.The value of p_c increases when the chromosome is quite poor. In contrast if p_c is low it means chromosome is good.

Mutation: Mutation is applied on each chromosome with fixed probability. During the mutation gene value a_i is replaced with a_i’, with respect to nearest neighbor clusters (according to centroids), for I = 1,…,N. a_i, is a cluster number randomly selected from {1,2,…., k}, with the probability p_j.

(5)

where, jε[1, ..., k] and d (x_i,c_k) is Euclidean distance between object x_i and the center of the cluster k. The mutation probability p_m is selected adaptively for each chromosome as in Srinivas and Patnaik (1994). The expression is given below:

(6)

where, k₂ and k₄ are equal to 0.5. When f_max- value decreases then p_c and p_m both will be increased. As a result GA will come out of local optimum. The default mutation rate (of 0.01) is kept for every solution in the FACE algorithm to overcome from problem of getting stuck at a local optimum.

Termination criterion: The FACE algorithm has been executed for a fixed number of generations. The fixed number is supplied by the user for terminating the algorithm. After termination, the algorithm gives the best string of the last generation that provides the solution to the clustering problem.

EXPERIMENTAL RESULTS

To conduct experiments on the FACE algorithm we have considered various types of the data sets. For this task, several artificial data sets and real data sets that are used to measure the performance of proposed algorithm. One performance measures Adjusted Rand index is used for this purpose. All experiments were run on a PC with a 2.0 GHz processor and 2 GB ram. We compared the performance of FACE algorithm with other algorithms in this area.

Parameter settings: The parameter settings used for FACE in our experimental study are given in Table 1.

Table 1:	Parameter setting for FACE algorithm

Apart from the maximum number of clusters; these parameters are kept constant over the entire range of data sets in our comparison study.

Evaluation of clustering quality: Clustering quality is evaluated using an external measure of clustering quality which can be considered an objective evaluation. Especially we choose the Adjusted Rand Index (Rand, 1971) which is a generalization of the Rand Index. The Rand indices take two partitioning as the input (one of which, in our case, is the known correct solution) and count the number of pair-wise co-assignments of data items between the two partitioning. The Adjusted Rand Index additionally introduces a statistically induced normalization in order to yield values close to 0 for random partitions. Using a representation based on contingency tables, the Adjusted Rand Index A (Hubert, 1985) is given as:

(7)

where, n_lk denotes the number of data items that have been assigned to both cluster l and cluster k. The Adjusted Rand Index return values in the interval (0, 1) and is to be maximized.

Artificial data sets: We applied the proposed algorithm (FACE) to several artificial data sets. The dimensionalities of these data sets are varying between two to fifty. The details features of these data sets are given below:

Real data sets: The proposed algorithm was tested for clustering with real data sets in multi-dimensional feature space obtained from UCI Machine Learning Repository. The performance of the FACE algorithm, CGA algorithm and k-means algorithm are compared through the experiments on the following three real data sets.

Wisconsin breast cancer: It contains two classes namely, malignant and benign with 683 unique data and 9 attributes corresponding to clump thickness, cell size uniformity, cell shape uniformity, marginal adhesion, single epithelial cell size, bare nuclei, bland chromatin, normal nucleoli and mitoses.

Wine: This data set contains 178 samples of a chemical analysis of wines grown in the same region of Italy but brewed by three different brewers. The analysis has determined the quantities of 13 constituents found in each type of wines.

Diabetes: This is the diabetes data set consisting of 768 instances having 8 attributes.

The final clustering results obtained by k-mean, GCA and FACE are given in Fig. 3a-c, of data set1, respectively. We find that the k-means and GCA algorithm cannot work well for this data set but FACE algorithm accurately clustered the points of above data set. Figure 4 (a-c) show the results for k-means, GCA and FACE, respectively of data set 2. The clustering result of data set3 is show in Fig. 5a-c for k-means, GCA and FACE, respectively. The k-means is fail to found correct clusters, the proposed algorithm works well for this data set. Fig. 5 (b) shows that GCA also can’t get good result for this data set. The performance results reported in Table 2, clearly demonstrate the clustering accuracy of k-means, GCA and FACE for real data sets. The high value of Adjusted Rand Index indicates the good quality of clustering result.

Table 2:	Adjusted Rand Index values obtained by k-means, GCA and FACE for real data sets

Fig. 3(a-c):	Clustering of deta set 1 by (a) K-means, (b) GCA and (c) FACE

Fig. 4(a-c):	Clustering of data set 2 by (a) K-means, (b) GCA and (c) FACE

Fig. 5(a-c):	Clustering of data set 3 by (a) k-means, (b) GCA and (c) FACE

Table 3:	Adjusted Rand Index values obtained by k-means, GCA and FACE for eight synthetic data sets

Table 3 indicates the quality of best clustering results in term of Adjusted Rand Index generated by k-means, GCA and FACE for eight artificial data sets. In Table 3, this is reflected in low values of the adjusted Rand Index as dimensionality and number of cluster increased.