A Review of Evolutionary Algorithms for Data Mining <s> Fitness Evaluation for Clustering <s> RECONNAISANCE OF THE DOMAIN. Cluster Analysis: Why, What, How, When. Methods in Clustering Data. Examples and Discussion. Framing of Cluster Analysis Studies. Fuzzy Clustering: A Branch in Fuzzy Logic. RECONSIDERATION OF THE TASK. Indetermination and Uncertainty in Cluster Analysis. The Need and Relevance of Computer-assisted Reasoning in Cluster Analysis. COMPUTER-ASSISTED DECISION SUPPORT IN CLUSTER ANALYSIS. Knowledge-based Expert Systems: An Introduction. Rule Base Developments for Cluster Analysis. Case Study: Analysis of Delphind Sonar Sound Signals. <s> BIB001 </s> A Review of Evolutionary Algorithms for Data Mining <s> Fitness Evaluation 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> BIB002 </s> A Review of Evolutionary Algorithms for Data Mining <s> Fitness Evaluation 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> BIB003 </s> A Review of Evolutionary Algorithms for Data Mining <s> Fitness Evaluation 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> BIB004
In an EA for clustering, the fitness of an individual is a measure of the quality of the clustering represented by the individual. A large number of different measures have been proposed in the literature, but the basic ideas usually involve the following principles. First, the smaller the intra-cluster (withincluster) distance, the better the fitness. The intra-cluster distance can be defined as the summation of the distance between each data instance and the centroid of its corresponding cluster -a summation computed over all instances of all the clusters. Second, the larger the inter-cluster (betweencluster) distance, the better the fitness. Hence, an algorithm can try to find optimal values for these two criteria, for a given fixed number of clusters. These and other clustering-quality criteria are extensively discussed in the clustering literature -see e.g.  BIB001  . A discussion of this topic in the context of EAs can be found in  BIB003 BIB004 Krishma and Murty 1999; BIB002 . In any case, it is important to note that, if the algorithm is allowed to vary the number of discovered clusters without any restriction, it would be possible to minimize intra-cluster distance and maximize inter-cluster distance in a trivial way, by assigning each example to its own singleton cluster. This would be clearly undesirable. To avoid this while still allowing the algorithm to vary the number of clusters, a common response is to incorporate in the fitness function a preference for a smaller number of clusters. It might also be desirable or necessary to incorporate in the fitness function a penalty term whose value is proportional to the number of empty clusters (i.e. clusters to which no data instance was assigned) BIB002 ).