A Review of Evolutionary Algorithms for Data Mining <s> Individual Representation for Clustering <s> The problem of unsupervised learning of patterns in spatial data is addressed using evolutionary programming. Hyperbox clusters of two-dimensional data are evolved in light of a minimum description length (MDL) principle. A series of experiments of increasing complexity indicates that evolutionary programming can be useful in generating clusters for data when no a priori classification information is available. In some cases, the best evolved clusters have lower MDL scores than the clusters that would correspond to the true probability distribution of the data. Brief consideration is given to using other functions for clustering, such as hyperellipses. <s> BIB001 </s> A Review of Evolutionary Algorithms for Data Mining <s> Individual Representation for Clustering <s> From the Publisher: ::: A reader-friendly introduction to the exciting, vast potential of Genetic Algorithms. ::: The book gives readers a general understanding of the concepts underlying the technology, an insight into its perceived benefits and failings, and a clear and practical illustration of how optimization problems can be solved more efficiently using Falkenauer's new class of algorithms. <s> BIB002 </s> A Review of Evolutionary Algorithms for Data Mining <s> Individual Representation for Clustering <s> Describes a genetically guided approach to optimizing the hard (J/sub 1/) and fuzzy (J/sub m/) c-means functionals used in cluster analysis. Our experiments show that a genetic algorithm (GA) can ameliorate the difficulty of choosing an initialization for the c-means clustering algorithms. Experiments use six data sets, including the Iris data, magnetic resonance, and color images. The genetic algorithm approach is generally able to find the lowest known J/sub m/ value or a J/sub m/ associated with a partition very similar to that associated with the lowest J/sub m/ value. On data sets with several local extrema, the GA approach always avoids the less desirable solutions. Degenerate partitions are always avoided by the GA approach, which provides an effective method for optimizing clustering models whose objective function can be represented in terms of cluster centers. A series random initializations of fuzzy/hard c-means, where the partition associated with the lowest J/sub m/ value is chosen, can produce an equivalent solution to the genetic guided clustering approach given the same amount of processor time in some domains. <s> BIB003 </s> A Review of Evolutionary Algorithms for Data Mining <s> Individual Representation for Clustering <s> A new approach to data clustering is proposed, in which two or more measures of cluster quality are simultaneously optimized using a multiobjective evolutionary algorithm (EA). For this purpose, the PESA-II EA is adapted for the clustering problem by the incorporation of specialized mutation and initialization procedures, described herein. Two conceptually orthogonal measures of cluster quality are selected for optimization, enabling, for the first time, a clustering algorithm to explore and improve different compromise solutions during the clustering process. Our results, on a diverse suite of 15 real and synthetic data sets – where the correct classes are known – demonstrate a clear advantage to the multiobjective approach: solutions in the discovered Pareto set are objectively better than those obtained when the same EA is applied to optimize just one measure. Moreover, the multiobjective EA exhibits a far more robust level of performance than both the classic k-means and average-link agglomerative clustering algorithms, outperforming them substantially on aggregate. <s> BIB004 </s> A Review of Evolutionary Algorithms for Data Mining <s> Individual Representation for Clustering <s> Various methods have been proposed to utilize Genetic Algorithms (GA) in handling the clustering problem. GA work on encoded strings, namely chromosomes, and the representation of different clusters as a linear structure is an important issue about the usage of GA in this domain. In this paper, we present a novel encoding scheme that uses links to identify clusters in a partition. Particularly, we restrict the links so that objects to be clustered form a linear pseudo-graph. A one-to-one mapping is thus achieved between the genotype and phenotype spaces. The other feature of the proposed approach is the use of multiple objectives in the process. One of the two objectives we use is to minimize the Total Within Cluster Variation (TWCV), identical to the one used by other k-means clustering approaches. However, unlike other k-means methods, number of clusters is not required specified in advance. Combined with a second objective, minimizing the number of clusters in a partition, our approach obtains the optimal partitions for all the possible numbers of clusters in the Pareto Optimal set returned by a single GA run. The performance of the proposed approach has been tested using two well-known data sets, namely Iris Data and Ruspini Data. The obtained results are compared with the output of the classical Group Number Encoding and it has been observed that a clear improvement has been achieved with the new representation. <s> BIB005
A crucial issue in the design of an EA for clustering is to decide what kind of individual representation will be used to specify the clusters. There are at least three major kinds of individual representation for clustering  , as follows. Cluster description-based representation -In this case each individual explicitly represents the parameters necessary to precisely specify each cluster. The exact nature of these parameters depends on the shape of clusters to be produced, which could be, e.g., boxes, spheres, ellipsoids, etc. In any case, each individual contains K sets of parameters, where Kis the number of clusters, and each set of parameters determines the position, shape and size of its corresponding cluster. This kind of representation is illustrated, at a high level of abstraction, in Figure 2 , for the case where an individual represents clusters of spherical shape. In this case each cluster is specified by its center coordinates and its radius. The cluster description-based representation is used, e.g., in (Srikanth et al. 1995) , where an individual represents ellipsoid-based cluster descriptions; and in BIB001  , where an individual represents hyperbox-shaped cluster descriptions. In  , for instance, the individuals represent rules containing conditions based on discrete numerical intervals, each interval being associated with a different attribute. Each clustering rule represents a region of the data space with homogeneous data distribution, and the EA was designed to be particularly effective when handling high-dimensional numerical datasets. specification of cluster 1 specification of cluster K center 1 radius 1 center K radius K coordinates . . . . . coordinates Centroid/medoid-based representation -In this case each individual represents the coordinates of each cluster's centroid or medoid. A centroid is simply a point in the data space whose coordinates specify the centre of the cluster. Note that there may not be any data instance with the same coordinates as the centroid. By contrast, a medoid is the most "central" representative of the cluster, i.e., it is the data instance which is nearest to the cluster's centroid. The use of medoids tends to be more robust against outliers than the use of centroids (Krzanowski & Marriot 1995) (p. 83) . This kind of representation is used, e.g., in BIB003  and other EAs for clustering reviewed in  ). This representation is illustrated, at a high level of abstraction, in Figure 3 . Each data instance is assigned to the cluster represented by the centroid or medoid that is nearest to that instance, according to a given distance measure. Therefore, the position of the centroids/medoids and the procedure used to assign instances to clusters implicitly determine the precise shape and size of the clusters. cluster 1 cluster K center 1 coordinates . . . . . center K coordinates Instance-based representation -In this case each individual consists of a string of n elements (genes), where nis the number of data instances. Each gene i, i=1,. . . ,n, represents the index (id) of the cluster to which the i-th data instance is assigned. Hence, each gene i can take one out of Kvalues, where K is the number of clusters. For instance, suppose that n = 10 and K= 3. The individual <2 1 2 3 3 2 1 1 2 3> corresponds to a candidate clustering where the second, seventh and eighth instances are assigned to cluster 1, the first, third, sixth and ninth instances are assigned to cluster 2 and the other instances are assigned to cluster 3. This kind of representation is used, for instance, in (Krishma and Murty 1999; BIB004 . A variation of this representation is used in BIB005 , where the value of a gene represents not the cluster id of a gene's associated data instance, but rather a link from the gene's instance to another instance which is considered to be in the same cluster. Hence, in this approach, two instances belong to the same cluster if there is a sequence of links from one of them to the other. This variation is more complex than the conventional instancebased representation, and it has been proposed together with repair operators that rectify the contents of an individual when it violates some pre-defined constraints. Comparing different individual representations for clusteringIn both the centroid/medoid-based representation and the instance-based representation, each instance is assigned to exactly one cluster. Hence, the set of clusters determine a partition of the data space into regions that are mutually exclusive and exhaustive. This is not the case in the cluster description-based representation. In the latter, the cluster descriptions may have some overlapping -so that an instance may be located within two or more clusters -and the cluster descriptions may not be exhaustive -so that some instance(s) may not be within any cluster. Unlike the other two representations, the instance-based representation has the disadvantage that it does not scale very well for large data sets, since each individual's length is directly proportional to the number of instances being clustered. This representation also involves a considerable degree of redundancy, which may lead to problems in the application of conventional genetic operators BIB002 . For instance, let n = 4 and K = 2, and consider the individuals <1 2 1 2> and <2 1 2 1>. These two individuals have different gene values in all the four genes, but they represent the same candidate clustering solution, i.e., assigning the first and third instances to one cluster and assigning the second and fourth instances to another cluster. As a result, a crossover between these two parent individuals can produce two children individuals representing solutions that are very different from the solutions represented by the parents, which is not normally the case in conventional crossover operators used by genetic algorithms. Some methods have been proposed to try to mitigate some redundancy-related problems associated with this kind of representation. For example, BIB004 proposed a mutation operator that is reported to work well with this representation, based on the idea that, when a gene has its value mutated -meaning that the gene's corresponding data instance is moved to another cluster -the system selects a number of "nearest neighbors" of that instance and moves all those nearest neighbors to the same cluster to which the mutated instance was moved. Hence, this approach effectively incorporates some knowledge of the clustering task to be solved in the mutation operator.